A Topology-Aware Sampling-Based Motion Planner
TimeTuesday, September 1412:45pm - 1:30pm CDT
DescriptionAs human beings, we often solve complex problems by solving them sequentially and/or using multiple levels of abstraction. For instance, when planning our motion from one place to another, we plan a path by spontaneously avoiding collision with the obstacles on our way. Such a problem becomes computationally difficult to solve when it comes to an autonomous robotic system. The computational problem of finding a valid path from source to destination while satisfying the robot's constraints is known as the motion planning problem. A robot often requires pre-planned information about its surroundings that effectively avoid colliding with obstacles when planning its path. Sampling-based planners have proven effective in these domains by finding a solution if one exists, as the number of sampled robot configurations in the space goes to infinity. However, the topological information extracted by these planners is either not reusable or does not provide much information about the robot's space. In this work, we introduce an analytical or computational tool that exploits both the topological and geometrical representations of the robot's environment to attain an improved efficiency for sampling-based methods with low computation time and memory. We used the Vietoris-Rips complex method to construct a clique using graph components, i.e., vertices and edges, and performed symmetric differences to remove vertices that were part of more than one clique. The topological graph preserved the important collision-free vertices of the environment representing unique regions of free space. We formally defined the relation between a real-valued function, i.e., discrete Morse function, and the clique to extract the geometrical representation of the obstacles in this environment. The discrete Morse function applied on the topological graph identified intricate corner points of the obstacles that helped planning a shorter path at a safer distance from the obstacles.