Videos

Topological Techniques in Graph Search-based Motion Planning

March 3, 2014
Keywords:
  • Topological, Graph
MSC:
  • 05C10
Abstract
In this talk I will introduce some techniques for topological reasoning within the purview of graph search-based motion planning. Classically, in robotics and artificial intelligence literature, a popular approach to dealing with complexities in configuration spaces (high dimension or topological non-trivialities) is to create a graph by placing vertices at discrete locations in the configuration space and establishing edges between the "neighbouring" vertices. This approach is simple and is suitable for design of efficient search algorithms like A* and Dijkstra's, and for incremental construction without global information about the entire configuration space to begin with. Such algorithms focus on and use the graph alone for solving problems like path planning, coverage and exploration, while discarding the richer topological information of the original configuration space. The lost information, for example, makes it is impossible to distinguish between paths in the graph that belong to different homotopy or homology classes in the original configuration space. Algebraic topology gives us the tools to "generalize" the notion of a graph to higher dimensions so as to represent the richer topological features of the space as a chain complex (e.g., a simplicial complex). However, there is no natural extension of graph search algorithms like Dijkstra's or A* to such complexes that are efficient and can be executed without knowing the entire complex from the very beginning. In this talk I will reveal tools and techniques that can be used efficiently as add-ons on graph search algorithms like Dijkstra's and A*, that lets us efficiently keep track of homology classes while searching for optimal paths in the graph. In particular, I will introduce a way of computing closed, non-exact differential 1-forms, the integration of which along singular cycles give complete invariants of their homology classes in the free space, and thus explain how this integration can be effectively used to modify graph search algorithms for planning optimal trajectories with consideration of homology classes. This, I will illustrate for N-dimensional Euclidean spaces punctured by obstacles. Although we will be using de Rham cochain complex and its pairing (integration) on singular chain complex with coefficients in the reals, I will give an outline of how this technique can be modified to consider homology with coefficients in Z_2, and thus illustrate the benefit of doing so. I will also introduce similar techniques for reasoning about homotopy classes of trajectories while planning optimal trajectories on a plane punctured by obstacles. After introducing the fundamental theoretical and algorithmic tools, I will demonstrate how these techniques can be applied to efficiently solve some real problems in robotics.