This project contains RRT and RRT* planners for mobile robot path planning in 2D environments. The /workspace folder contains 8 static maps inside mapsStatic.mat for simulation. The /lib folder contains following planner files written in MATLAB.
This planner is based on the Rapidly-exploring Random Trees (RRT) as described in LaValle et al. [1] which is a incremental sampling-based algorithm for path planning in complex environments. It works by quickly exploring the state space to find new and feasible nodes and adding it to the search tree. The RRT* algorithm by Karaman et al. [2] is a modification of RRT by the addition of two procedures - parent search to find appropriate low cost parent for the candidate node and rewire procedure to reattach an existing node to the candidate node.
The potential function-based RRT* (P-RRT*) is based on paper by Qureshi et al. [3] which used Artificial Potential Function (APF) as a sampling heuristic, to guide the sampling process towards the goal. This is carried out by placing an attractive potential on the goal location.
Quick-RRT* (Q-RRT*) as described in Jeong et al. [4] combines RRT* with an additonal search procedure that searches the ancestry of the selected parent node. This algorithms utilizes the triangle inequality property to come up with lesser cost paths in comparison to those generated by RRT*.
The PQ-RRT* from Li et al. [5] is a hybridization of the P-RRT* and Q-RRT* planners respectively. The sampling is carried out by using APF as seen in P-RRT* and parent search is carried out by using the ancestry search procedures as seen in Q-RRT*.
The PSO-RRT* planner makes use of Particle Swarm Optimization (PSO) technique from Kennedy et al. [6], for sampling. A population is selected in the state-bounds and is incrementally directed towards the goal. 2D sphere centred at the goal is selected as the fitness function. PSOQ-RRT* makes use of the ancestry search procedure from Q-RRT* to select better parents for the candidate node.
All planners make use of the checkIfGoalIsReached.m function to check if the search should be terminated. The PSO sampling uses the fitness function in sphere2D.m.
A function called bezierCurveSmoothing.m has been added to create smooth curves between path states.
Use MATLAB Add-On Explorer to install the necessary add-ons Robotics Systems Toolbox and Navigation Toolbox.
The main.m file contains the code to build and run the planner. The program returns a search tree of all the visited nodes and a tree of the generated feasible path.
The PSO-RRT* algorithm is similar to P-RRT* algorithm with the difference being in sampling process adopted. PSO-RRT* makes use of PSO while P-RRT* uses APF. PSOQ-RRT* is similar to PQ-RRT* in the same manner.
[1] LaValle, S. M., Kuffner, J. J. (2001). Randomized Kinodynamic Planning. The International Journal of Robotics Research, 20(5), 378–400. https://doi.org/10.1177/02783640122067453.
[2] Karaman, S., Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research, 30(7), 846–894. https://doi.org/10.1177/0278364911406761.
[3] Qureshi, A.H., Ayaz, Y. (2016) Potential functions based sampling heuristic for optimal path planning. Autonomous Robots, 40, 1079–1093. https://doi.org/10.1007/s10514-015-9518-0.
[4] Jeong, I.-B., Lee, S.-J., Kim, J.-H. (2019) Quick-RRT*: Triangular inequality-based implementation of RRT* with improved initial solution and convergence rate. Expert Systems with Applications, 123, 82-90. https://doi.org/10.1016/j.eswa.2019.01.032.
[5] Li, Y., Wei, W., Gao, Y., Wang, D., Fan, Z. (2020) PQ-RRT*: An improved path planning algorithm for mobile robots. Expert Systems with Applications, 152, 113425. https://doi.org/10.1016/j.eswa.2020.113425.
[6] Kennedy, J., Eberhart, R. (1995) Particle swarm optimization. Proceedings of ICNN'95 - International Conference on Neural Networks, 4, 1942-1948. https://doi.org/10.1109/ICNN.1995.488968.