Revista Matemática Iberoamericana


Full-Text PDF (174 KB) | Metadata | Table of Contents | RMI summary
Volume 34, Issue 4, 2018, pp. 1679–1684
DOI: 10.4171/rmi/1039

Published online: 2018-12-03

Topological complexity and efficiency of motion planning algorithms

Zbigniew Błaszczyk[1] and José Gabriel Carrasquel-Vera[2]

(1) Adam Mickiewicz University, Poznan, Poland
(2) Adam Mickiewicz University, Poznan, Poland

We introduce a variant of Farber’s topological complexity, defined for smooth compact Riemannian manifolds, which takes into account only motion planners with the lowest possible “average length” of the output paths. We prove that it never differs from topological complexity by more than 1, thus showing that the latter invariant addresses the problem of the existence of motion planners which are “efficient”.

Keywords: Cut locus, geodesic, motion planning, topological complexity

Błaszczyk Zbigniew, Carrasquel-Vera José Gabriel: Topological complexity and efficiency of motion planning algorithms. Rev. Mat. Iberoam. 34 (2018), 1679-1684. doi: 10.4171/rmi/1039