DMS-EPSRC: Topology of Automated Motion Planning

This project will investigate new mathematics useful for understanding the complexity of robotic action in a physical environment. The project thus concentrates on those aspects that are different from purely computational work. Instead, as a robot moves from place to place, it senses its environment, acts within it to achieve some goal, responds to changes in it, and might communicate with others.

The interactions with the external environment are typically achieved via changes to some internal states, so that, for example, a given motion performed on two different occasions (even under identical external conditions) could be the result of different changes to the internal state of the robot. By building abstract topological models of these issues, the PI, in collaboration with M.

Farber in the UK, will use algebraic and geometric tools to shed light on some of the tradeoffs (for example of stability of output against flexibility in being able to handle a variety of environments) that necessarily arise when solving such problems.

The first step in this direction, a numerical invariant that measures the amount of instability necessary, no matter the computational resources available, for robotic motion planning, or equivalently the minimum amount of stochasticity necessary is the topological complexity invented almost twenty years ago by Farber, and frequently studied by cohomological tools. To understand the additional cost of flexibility", the costs imposed by needing to solve a motion planning problem but in a variety of different environments (say for a Roomba to learn its way around a room after the furniture has been moved), D.

Cohen, Farber, and the PI introduced parametrized topological complexity; preliminary calculations show that it does indeed capture some new phenomena that the ordinary complexity does not. Besides further development of topological and parametrized complexity, this project aims to study the role of hidden states (e.g. moving from one fiber to another of a work map), sensing (e.g. the role of incomplete information about the environment that unfolds over time), the development of a useful technology for genus of non-fibrations, and the use of persistent homology to understand about the role of resources (e.g. the speed, path length, energy usage, sensing costs, etc.) in planning tasks.

This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.