DMS-EPSRC Topology of automated motion planning
Lead Research Organisation:
Queen Mary University of London
Department Name: Sch of Mathematical Sciences
Abstract
Algebraic topology uses various techniques allowing to reduce problems about flexible geometric objects to questions about rigid algebraic structures. Cohomological methods are currently among the most effective techniques which are used in situations motivated by problems of mathematical analysis, algebraic geometry, engineering and mathematical physics.
In this research we shall use topological tools (and in particular methods of cohomology theory) to analyse algorithms of making decisions in situations when the outcome is a choice made from a continuum of possibilities rather than from a discrete set of values. In many such situations an algorithms can be interpreted as a section of a fibration and the topological concept of Schwartz genus of a fibration is a natural reflection of complexity of the task.
In this research we shall develop mathematical methods to study algorithms for motion planning in engineering, algorithms for coordination of computations in distributed computing and algorithms for aggregation of personal preferences and reaching consensus in negotiations and their relations to social choice theory. Although these problems may appear to be very different at the first glance, they involve quite similar underlying mathematics and can be analysed by analogous methods.
We shall develop theory of parametrised topological complexity which will be applicable
in a variety of real life situations. The fundamental novelty in our approach consists in the assumption that the configuration space is "large" and is known to us only partially and, besides, the motion planning algorithm will operate without prior knowledge of the positions of the obstacles. Mathematically this will be reflected in the assumption that the actual configuration space is one of a large family of spaces parametrised by a base of a fibration.
We shall also study motion planning algorithms in situations when motion of the system is constrained by technical limitations. This theory will be applicable in the context of distributed computing and will help to design computational algorithms for multiple computers performing simultaneous computations and sharing common resources.
We shall tackle the Rationality Conjecture which predicts behaviour of the sequential topological complexity in the case of a large number of intermediate destinations. Besides, we shall further develop theory of geodesic motion planning where one requires that motion planning algorithms produce geodesic paths of minimal lengths.
In the classical theory of social choice the preferences are assumed to be given on discrete sets of alternatives. We shall study a topological approach aiming to devise methods allowing to quantify the necessary failure of aggregation methods of various kind, along the lines of topological complexity and its quantitative variants, and to produce some positive results in this direction.
In this research we shall use topological tools (and in particular methods of cohomology theory) to analyse algorithms of making decisions in situations when the outcome is a choice made from a continuum of possibilities rather than from a discrete set of values. In many such situations an algorithms can be interpreted as a section of a fibration and the topological concept of Schwartz genus of a fibration is a natural reflection of complexity of the task.
In this research we shall develop mathematical methods to study algorithms for motion planning in engineering, algorithms for coordination of computations in distributed computing and algorithms for aggregation of personal preferences and reaching consensus in negotiations and their relations to social choice theory. Although these problems may appear to be very different at the first glance, they involve quite similar underlying mathematics and can be analysed by analogous methods.
We shall develop theory of parametrised topological complexity which will be applicable
in a variety of real life situations. The fundamental novelty in our approach consists in the assumption that the configuration space is "large" and is known to us only partially and, besides, the motion planning algorithm will operate without prior knowledge of the positions of the obstacles. Mathematically this will be reflected in the assumption that the actual configuration space is one of a large family of spaces parametrised by a base of a fibration.
We shall also study motion planning algorithms in situations when motion of the system is constrained by technical limitations. This theory will be applicable in the context of distributed computing and will help to design computational algorithms for multiple computers performing simultaneous computations and sharing common resources.
We shall tackle the Rationality Conjecture which predicts behaviour of the sequential topological complexity in the case of a large number of intermediate destinations. Besides, we shall further develop theory of geodesic motion planning where one requires that motion planning algorithms produce geodesic paths of minimal lengths.
In the classical theory of social choice the preferences are assumed to be given on discrete sets of alternatives. We shall study a topological approach aiming to devise methods allowing to quantify the necessary failure of aggregation methods of various kind, along the lines of topological complexity and its quantitative variants, and to produce some positive results in this direction.
People |
ORCID iD |
Michael Farber (Principal Investigator) |
Publications
Farber M
(2023)
Parametrized topological complexity of sphere bundles
in Topological Methods in Nonlinear Analysis
Farber M
(2023)
Large simplicial complexes: universality, randomness, and ampleness
in Journal of Applied and Computational Topology
Farber M
(2023)
Sequential parametrized motion planning and its complexity, II
in Topology and its Applications
Farber M
(2023)
The homology of random simplicial complexes in the multi-parameter upper model
in Israel Journal of Mathematics
Farber M
(2022)
Sequential Parametrized Motion Planning and its Complexity
Farber M
(2022)
Sequential parametrized motion planning and its complexity
in Topology and its Applications
Cohen D
(2022)
Parametrized topological complexity of collision-free motion planning in the plane
in Annals of Mathematics and Artificial Intelligence
Farber M
(2022)
Sequential parametrized motion planning and its complexity, II