[2018] Extending Homotopy-Based Shortest Path (HBSP)

During my time at RISS I collaborated with researchers at CMU to extend planning algorithms for humanoid robots. My work was on the HBSP (Homotopy Based Shortest Path) algorithm which takes a given homotopy-class and generates a heuristic function to accelerate planning. We beat baseline methods (A* with a reverse Dijkstra Heuristic) by several orders of magnitude in environments with many local minima. My contribution to the project was extending the algorithm to work in “2.5 Dimensions” (i.e environments that cannot be projected into a single plane). This was done by extending the previous homotopy-invariants to encode 3-dimensional information. The resulting paper: Effective Footstep Planning Using Homotopy-Class Guidance has been submitted to Artifical Intelligence (an Elsevier journal). Our code is open sourced on Github for extension and application to other systems.