Path homotopy invariants and their application to optimal trajectory planning (Q1757449): Difference between revisions

This paper considers the problem of optimal path planning with reasoning about homotopy classes of trajectories. Such a study is motivated by practical applications in which the homotopy classes of paths are relevant, such as robots tethered to a base (e.g., a power supply) or teams of robots engaged in capturing objects using trailing flexible cables (e.g., cleaning the ocean surface after an oil spill). Previous work has mainly focussed either on finding optimal paths, or classifying paths according to their homotopy class. The current work combines these two approaches, building on previous work of the first author and collaborators [\textit{S. Bhattacharya} et al., The International Journal of Robotics Research 34, No. 6, 799--815 (2015; \url{doi:10.1177/0278364914562236}); Auton. Robot. 33, No. 3, 273--290 (2012; \url{doi:10.1007/s10514-012-9304-1}); Ann. Math. Artif. Intell. 67, No. 3--4, 251--281 (2013; Zbl 1282.94015)] and superseding the conference publication of the same name [\textit{S. Bhattacharya} and \textit{R. Ghrist}, In: Proceedings of IMA Conference on Mathematics of Robotics (IMAMR), St Anne's College, University of Oxford (2015)]. \par More precisely, given a configuration space $X$ and start and end configurations $x_s,x_e\in X$, one can ask for algorithms which: (1) classify paths in $X$ from $x_s$ to $x_e$ up to homotopy relative to the endpoints (such homotopy classes correspond to elements of the fundamental group of $X$); (2) given a homotopy class of paths from $x_e$ to $x_s$, output an optimal path in that homotopy class. \par The authors explain an approach to (1) using the Seifert-van Kampen theorem and Dehn's algorithm, which can be applied in various cases of interest including planar configuration spaces with obstacles, spatial configuration spaces with obstacles (which may be knotted or linked), and so-called \textit{cylindrically deleted} configurations spaces, including coordination spaces of multiple agents moving in the plane avoiding collisions. Building on this, they describe an approach to (2) which uses graph search-based algorithms in a lift of a graph discretization of $X$ to the universal cover $\widetilde{X}$. They have implemented their algorithms in C++ and offer attractive visualizations of the computed trajectories in cases including the trefoil and Hopf link complements, and for 3 robots moving in the plane.