Angle-based multi-goal ordering and path-planning using an improved A-star algorithm

Official URL: https://dx.doi.org/10.1016/j.robot.2025.105001

In the field of autonomous mobile robotics, the demand for highly efficient path-planning algorithms is crucial. Among the various path-planning tasks and challenges, multi-goal path planning stands out as a particularly complex problem, where the objective is to determine the most efficient path for a robot to visit multiple goal nodes. In this paper, we introduce a novel ordering algorithm designed to optimize the sequence in which the goal nodes are visited. The ordering is based on a one-distance-two-angles ordering paradigm, which reduces the dependency on distances as deciding factors and incorporates more angles to gather the necessary information, thereby reducing the computational complexity of the overall ordering procedure. The backbone of the algorithm is an improved version of the A* search algorithm that we developed to further reduce the distance cost of the original A* algorithm by solving some internal issues caused by the nature of the algorithm when dealing with grid-based environments. Extensive experiments were conducted to demonstrate the computational efficiency and cost-effectiveness of our proposed algorithm. The scalability and reproducibility of the proposed ordering algorithm and the improved A* were validated by testing them on various publicly available maps in numerous different scenarios. We also performed comprehensive comparisons with existing state-of-the-art algorithms to evaluate the performance. The conducted experiments report that our proposed algorithm consistently outperformed other algorithms in numerous scenarios, underscoring its reliability and potential to match or even exceed the performance of current state-of-the-art methods in the domain of multi-goal path planning. The entire code, map and other resources of our proposed algorithms are available at https://github.com/abdullah1aloush1/AMuGOPIA.