Skip directly to content

Minimize RSR Award Detail

Research Spending & Results

Award Detail

Doing Business As Name:University of Chicago
  • Shmuel Weinberger
  • (773) 702-7349
Award Date:06/17/2021
Estimated Total Award Amount: $ 311,427
Funds Obligated to Date: $ 311,427
  • FY 2021=$311,427
Start Date:07/01/2021
End Date:06/30/2024
Transaction Type:Grant
Awarding Agency Code:4900
Funding Agency Code:4900
CFDA Number:47.049
Primary Program Source:040100 NSF RESEARCH & RELATED ACTIVIT
Award Title or Description:DMS-EPSRC: Topology of Automated Motion Planning
Federal Award ID Number:2105553
DUNS ID:005421136
Parent DUNS ID:005421136
Program Officer:
  • Christopher Stark
  • (703) 292-4869

Awardee Location

Street:6054 South Drexel Avenue
Awardee Cong. District:01

Primary Place of Performance

Organization Name:University of Chicago
Street:5734 S. University Ave
Cong. District:01

Abstract at Time of Award

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.

For specific questions or comments about this information including the NSF Project Outcomes Report, contact us.