Comparing Four Sampling-Based Path Planners for an N DOF Robot Arm.

Intricacies of Dynamic Path Planning

In this intensive project, I engineered a robust planner that facilitated a robotic arm in accurately moving to a target, which involved complex path planning within a grid space filled with obstacles. The approach involves comparing four common sampling based planners: RRT, RRT Connect, RRT*, and PRM.

Problem Setup

The simulation environment was a complex 2D grid with various obstacles, with an N DOF robot arm. The task was to calculate a path in minimal time, ensuring the robot could achieve the goal position without obstacle collision.

The Planner

• RRT: I employed the RRT algorithm with a loop that continues until the goal is reached. Random nodes are generated and the closest node on the existing tree is determined. If the distance to the nearest node exceeds a threshold (epsilon), a new node is added in the direction of the random node at a distance epsilon. This ensures a consistent growth of the tree towards unexplored areas. Validity checks for configurations and transitions are performed at each iteration, ensuring the integrity of the path. My chosen parameters were epsilon = numDOF/3 and step_size of 0.1 for transition validity checks.

• RRT Connect: My implementation of the RRTConnect algorithm involved two trees and utilized the extend function similar to the RRT algorithm. After each extension, the trees are swapped and an attempt is made to connect the most recently added node to its nearest neighbor in the other tree. This process continues until a valid connection is established, with regular checks for configuration and transition validity. Parameters were set to epsilon = numDOF/3, step_size of 0.1.

• RRTStar: In RRTStar, my approach involved extending the tree similar to the RRT algorithm, but with additional steps for rewiring to optimize the path. The goal is not a terminating condition; instead, the algorithm continues to search and rewire to improve the path even after the goal is reached. The number of rewiring attempts post-goal is determined by a predefined number of samples. The radius for neighbor selection decreases as the number of nodes increases, with parameters set to epsilon = numDOF/3 and a constant of 0.5 for radius computation.

• PRM: My PRM approach constructs a graph with 5000 random nodes, including the start and goal states. Nodes are connected if they fall within a specified radius (5 nodes in this case), and are not already connected. The neighbors for each node are selected based on their distances, with a priority queue managing the neighbor selection process. The queue is limited to three contents, ensuring efficient neighbor selection. Once the graph is constructed, A* algorithm is employed to find the optimal path.

• C++ for Performance: The code was executed in C++, chosen for its execution speed and low-level memory management capabilities, critical for real-time applications.
• Memory Management: Employing dynamic allocation, I ensured efficient memory usage, crucial for maintaining performance during the planner’s runtime.

Performance and Results

The planner was rigorously tested, showing that it could catch the target in a variety of grid configurations. Performance times ranged from a swift 126 seconds in simpler scenarios to more complex ones requiring up to 4672 seconds, demonstrating the planner’s adaptability.

Conclusions and Future Work

In conclusion, while RRT Connect shines in terms of speed and path quality, PRM offers robustness with its perfect success rate but at the cost of longer planning times. RRT and RRT* offer a balance between planning time and path quality, with RRT* leaning more towards efficiency over path optimality. Depending on the specific requirements of the application, one might prioritize speed (RRT Connect), robustness (PRM), or a balance (RRT, RRT*).

My full report details the entire process and can be found here.