BIRS Workshop Lecture Videos
Geodesic complexity and motion planning on graphs Recio-Mitter, David
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).
Item Citations and Data
Attribution-NonCommercial-NoDerivatives 4.0 International