Title: IQ-RRT*: a path planning algorithm based on informed-RRT* and quick-RRT*

Authors: Afroze Rahman; Anindita Kundu; Sumanta Banerjee

Addresses: Department of Computer Science and Engineering, Heritage Institute of Technology, Kolkata – 700107, India ' Department of Software Systems, School of Computer Science and Engineering (SCOPE), Vellore Institute of Technology, Vellore – 632014, India ' Department of Mechanical Engineering, Heritage Institute of Technology, Kolkata – 700107, India

Abstract: Optimal path planning algorithms such as the RRT* and its variants seek to generate the best feasible path from an initial state to a goal state in the least possible time. Prior work on RRT* has focused on improving the convergence rate of the algorithm while keeping its computational complexity unchanged. Informed-RRT* and quick-RRT* are two such variants that, in certain scenarios, converge to the optimal path faster than RRT* does. This work focuses on the novel addition of informed sampling to quick-RRT* to enhance its convergence rate. The resultant algorithm provides initial solutions with costs comparable to quick-RRT* and convergence rates at par with quick-RRT* in the worst case. The authors have concluded that this new algorithm, named IQ-RRT*, outperforms informed-RRT* and quick-RRT* in a multitude of scenarios. IQ-RRT*, unlike quick-RRT*, is a faster alternative to informed-RRT* even in cluttered environments and mazes with long corridors.

Keywords: path planning; informed sampling; fast convergence; rapidly-exploring random tree; RRT*.

DOI: 10.1504/IJCSE.2025.146087

International Journal of Computational Science and Engineering, 2025 Vol.28 No.3, pp.303 - 313

Received: 31 Aug 2023
Accepted: 17 May 2024
Published online: 06 May 2025 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article