DMS-EPSRC Topology of automated motion planning

点击翻译按钮获取中文摘要

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.