BIRS Workshop Lecture Videos

Banff International Research Station Logo

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 Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International