Penn Arts & Sciences Logo

Geometry-Topology Seminar

Thursday, February 12, 2015 - 4:30pm

Subhrajit Bhattacharya

UPenn

Location

University of Pennsylvania

DL 4C8

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 discretize the configuration space to construct a graph, and use efficient algorithms such as Dijkstra's and A*, which focus on and use the graph alone for solving problems like path planning. However, as a consequence of the discretization, we discard the richer topological information of the original configuration space. The lost information, for example, makes it is impossible to distinguish between paths that belong to different homotopy or homology classes created due to presence of obstacles in the original configuration space. In this talk I will discuss some simple tools from algebraic topology that can be used efficiently as modules on graph search algorithms such as Dijkstra's and A*, that lets us efficiently keep track of homology classes of trajectories while searching for optimal paths in the graph. In particular, I will introduce certain 'closed differential 1-forms', the integration of which along paths give complete invariants of their homology classes, and thus explain how this integration can be effectively used to modify graph search algorithms for planning optimal trajectories constrained to specific homology classes. We will also discuss ways of reasoning about homotopy in similar optimal path planning problems. After introducing the main algorithmic tools, I will present a few applications of these for achieving efficient solutions to some real problems in robotics.