Open Collections

Geodesic complexity and motion planning on graphs

Banff International Research Station for Mathematical Innovation and Discovery

The topological complexity TC(X) of a space X was introduced in 2003 by Farber to measure the instability of robot motion planning in X. The motion is not required to be along shortest paths in that setting. We define a new version of topological complexity in which we require the robot to move along shortest paths (more specifically geodesics), which we call the geodesic complexity GC(X). In order to study GC(X) we introduce the total cut locus.

We show that the geodesic complexity is sensitive to the metric and in general differs from the topological complexity, which only depends on the homotopy type of the space. We also show that in some cases both numbers agree. In particular, we construct the first optimal motion planners on configuration spaces of graphs along shortest paths (joint work with Donald Davis and Michael Harrison).

Mathematics; Algebraic topology; Mechanics of particles and systems

video/mp4

Author affiliation: Lehigh University

2021-03-20

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/77571

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/