Graph-Theoretic Models and Comparative Evaluations of Novel Multi-Robot Path Planning Algorithms for Collision Avoidance and Navigation Optimisation

A comprehensive analysis of three graph-theoretic path planning algorithms designed for multi-robotic systems (MRS) was undertaken. The algorithms were the multi-robot path planning algorithm (MRPP), central algorithm (CA), and the optimisation central algorithm (OCA). The primary objective of these algorithms is to enhance path optimality, mitigate computational complexity, and ensure robust inter-robot collision avoidance. The MRPP is a composite approach integrating the visibility graph (VG) for path generation. The CA, derived from VG principles, utilises a central baseline (CB) approach to reduce vertex count, thereby decreasing computational cost while maintaining path efficiency. The OCA extends CA by integrating obstacle expansion and safety margins to enhance collision avoidance and path optimisation. Comparative analysis through simulations in 2D polygonal environments compared the performance of these algorithms, considering their computational efficiency, path optimisation, and collision avoidance. CA and OCA demonstrated significant improvement over the VG-based approach, especially concerning optimality and optimisation. CA reduced the average path length by 4.3% compared with MRPP, while OCA achieved a 6.8% reduction over MRPP, and 2.5% over CA, demonstrating its superior balance between optimality and efficiency. MRPP offers robust connectivity, making it preferable in scenarios where communication is critical. The study’s findings assist in devising MPRPP solutions.