Michael Rencheck | ROS Motion Planning from Scratch

Robot Motion Planning from Scratch

Implementing various components to a motion planning stack to combine with various robotic navigation techniques. This project consisted of representing the map either as an occupancy grid or a probabilistic road map. These graphs were then used to implement four different heuristic-based search algorithms to identify the best path between the start and the goal. These algorithms were A*, Theta*, LPA*, and D* Lite. Also implemented is a Potential Field global planner which is capable of planning in a continuous map. Lastly, Model Predictive Path Integral control was implemented as a means of controlling a robot to follow one of the paths identified by the global planner.

A deeper dive in the details of the project, all source code, and API is hosted on Github.

View Repo

All of the search algorithms were implemented in C++ and the MPPI control was implemented using Python. Each library was used in various ROS nodes to demonstrate their function. All components of this project were developed from scratch and also used some of the packages developed in my other ROS Navigation from Scratch project.

The content for this project was compiled through the efforts of myself and three other peers doing research on one of the components and preparing lecture content to teach the subject to the others.

This project came about through a self-study course developed by myself and three other peers. We delegated out each section of the material to individually research and prepare lecture content to teach the others about the topic. My topics covered the various heuristic-based global search methods. Below are the materials and the resources used :

Slides

1. LaValle, Steven M. Planning Algorithms. Section 2.3. Cambridge university press, 2006.

2. Daniel, Kenny, et al. "Theta*: Any-angle path planning on grids." Journal of Artificial Intelligence Research 39 (2010): 533-579.

3. Nash, Alex, Sven Koenig, and Craig Tovey. "Lazy Theta*: Any-angle path planning and path length analysis in 3D." Twenty-Fourth AAAI Conference on Artificial Intelligence. 2010.

4. Stentz, Anthony. "Optimal and efficient path planning for partially known environments." Intelligent Unmanned Ground Vehicles. Springer, Boston, MA, 1997. 203-220.

5. Koenig, Sven, and Maxim Likhachev. "Fast replanning for navigation in unknown terrain." IEEE Transactions on Robotics 21.3 (2005): 354-363.

6. Ferguson, Dave, and Anthony Stentz. "Field D*: An interpolation-based path planner and replanner." Robotics research. Springer, Berlin, Heidelberg, 2007. 239-253.

7. Nash, Alex, Sven Koenig, and Maxim Likhachev. "Incremental Phi*: Incremental any-angle path planning on grids." Twenty-First International Joint Conference on Artificial Intelligence. 2009.