Path Planning for Piano Mover’s Problem

Key Takeaway: The RRT algorithm is computationally efficient but does not computes the optimal (or longer) paths, however A* computes optimal path with longer computation time. Thus, A* should be used for planning problems with dimension (or DOF) less than 6 and RRT (or sampling-based) planner should be used for problems with larger dimension.

Project Overview: Piano mover’s problem is a famous Motion Planning problem in which the piano has to be manipulated through the halls and door way in order to move it from one room to another. I have implemented a 3D (x,y, Θ) RRT and A* path planning algorithm. The animation above, shows the path computed by both the algorithms. The path computed by RRT is 35.04% longer and it takes 4.53 secs of computation time. On the other hand, the path computed by A* is 25.95% shorter as compared to RRT, however it takes 8.77 secs of computation time. The computation time of the A* search can be improved by use of improve heuristic like Fast Marching Method, etc.

---

Implementing RRT* for 7DOF Baxter Manipulator

Key Takeaway: RRT* computes paths of shorter length as compared to RRT with marginal increase in computational time. RRT* computes paths that are asymptotically optimal, i.e., with the increase in randomly drawn samples, the algorithm will eventually compute optimal path.

Project Methodology:
In this project, I have developed a path planning algorithm for collision free motion for a 7-DOF arm on Baxter robot. The dimension of the planning problem is large and the used of graph search-based algorithm is computationally infeasible. Thus, I decided to use sampling-based planner like Rapidly exploring Random Trees (RRT), Probabilistic Roadmaps (PRMs), etc. PRMs are advantageous in the problems that doesn’t vary the map (or obstacles) and requires the planner to compute collision free repeatedly (or multi-query). In my case, the problem was relatively simple and does not require multiple query.

In the case of RRT, the algorithm randomly samples a configuration in the configuration space and attaches it to the nearest node in the graph (see the above figure). However, the nearest node is not necessarily the cheapest way to reach the randomly samples configuration. This results in longer and non-smooth paths. On the other hand, RRT* considers all the nodes within a certain bounds (dotted blue circle) and connects the randomly sampled configuration to the node which minimizes the cost of traversal from the root node. This ensures the path is locally the shortest path and generates paths that are relatively smoother as compared to RRT. Thus, I decided to implement RRT* as compared to RRT.