Motion Planning in High-dimensional Spaces
Motion Planning in High-dimensional Spaces
This project deals with planning for higher dimensional spaces using the Parti-game and RRT algorithms. The Parti-game algorithm is a cell-based planner that creates dynamic discretizations of the environment. It learns the environment over time since the discretization it creates improves with multiple runs in the same environment. The RRT, on the other hand, is a randomized, sample-based search algorithm. By combining the RRT and Parti-game algorithms in a suitable manner, we can solve more planning problems, reduce the planning time and memory consumption while at the same time not compromising on trajectory quality.
Publications
•PDRRTs: Integrating Graph-based and Cell-based Planning
Ananth Ranganathan and Sven Koenig, IROS 2004
When a robot is given an opportunity to perform motion planning and path-finding in the same environment repeatedly, it should take advantage of this by learning about the environment and getting better at these problems with time. In spaces of small dimensionality or when a map of the environment is given, standard motion planning algorithms such as RRTs can provide good solutions. However, in high-dimensional spaces which are unknown apriori, these do not work. This paper provides a novel algorithm for learning unknown environments by solving multiple path-finding problems in them.