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.