This proposal describes an aggressive program of research in computational topology with a focus on computing and characterizing shortest paths in a variety of domains relevant to applications in robotics, coordination, and locomotion. We will investigate efficient descriptions of shortest-path information and geodesic structures in spaces with different types of constraints. The three main goals of our project are (1) developing algorithms to compute optimal paths, cycles, and other one-dimensional substructures, primarily in two-dimensional surfaces; (2) applying tools from Alexandrov geometry and topology to more efficiently characterize and compute shortest paths in non-positively curved spaces; and (3) developing languages to characterize spaces of optimal paths for motion systems with mechanical and/or nonholonomic constraints. Our proposed work draws on techniques from low-dimensional geometric and algebraic topology, combinatorial group theory, computational geometry, and non-holonomic motion planning.
At a high level, our research focuses on techniques for computing the cheapest way to move from one point to another in a variety of interesting spaces. Consider, for example, a collection of robots moving around a factory floor. The positions of the robots can be encoded as a single point in a high-dimensional configuration space. The geometry of this space is governed by certain mechanical and/or kinematic constraints; for example, robots must never collide with each other, and they have a limited rate of acceleration. A shortest path in the configuration space describes a set of motions of the robots from one set of locations to another that is as efficient as possible. We plan to develop algorithms that compute such shortest paths quickly, by exploiting the overall ``shape" of the underlying space.
