Subhrajit Bhattacharya      Dr. Subhrajit Bhattacharya

Post-doctoral Researcher, Department Of Mathematics
University of Pennsylvania
"Topological Techniques in Graph Search-based Planning”
Wednesday, December 10, 4:00 PM
Packard Lab, Room 466

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 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 topological (homotopy or homology) classes created due to presence of obstacles in the original configuration space.

In this talk I will reveal tools originating from the mathematical field of 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 fundamental theoretical and algorithmic tools, I will present a few applications of these for achieving efficient solutions to some real problems in robotics.

Bio:  Subhrajit Bhattacharya is a post-doctoral researcher in the Department of Mathematics of University of Pennsylvania, working under the supervision of Prof. Robert Ghrist and Prof. Vijay Kumar. He completed Ph.D. in Mechanical Engineering and Applied Mechanics under the guidance of Prof. Vijay Kumar and Prof. Maxim Likhachev in 2012. Subhrajit's research interests are centered around applications of algebraic topology and differential geometry to the design and analysis of algorithms in robot motion planning, sensor networks, distributed systems, kinematics and dynamics of robotic systems.

© 2014-2016 Computer Science and Engineering, P.C. Rossin College of Engineering & Applied Science, Lehigh University, Bethlehem PA 18015.