Topological and geometric techniques in graph search-based robot planning

摘要

Search-based techniques have been widely used in robot path planning for finding optimal or close-to-optimal trajectories in configuration spaces. They have the advantages of being complete, optimal (up to the metric induced by the discretization) and efficient (in low dimensional problems), and broadly applicable, even to complex environments. Continuous techniques, on the other hand, that incorporate concepts from differential and algebraic topology and geometry, have the ability to exploit specific structures in the original configuration space and can be used to solve different problems that do not lend themselves to graph-search based techniques. We propose several novel ideas and develop new methodologies that will let us bring these two separate techniques under one umbrella. Using tools from algebraic topology we define differential forms with special properties whose integral reveal topological information about the solution path allowing us to impose topological constraints on the planning problems. Metric information can be used along with search-based techniques for creating Voronoi tessellations in coverage and exploration problems. In particular, we use entropy as a metric for multi-robot exploration and coverage of unknown or partially known non-convex environments. Finally, in multi-robot constrained planning problems we exploit certain special product structure in the high dimensional configuration space that combine the advantages of graph search methods and gradient descent algorithms allowing us to develop powerful tools to solve very high-dimensional planning problems.