Development and Evaluation of Multi-Robot Motion Planning Graph Algorithm

摘要

A new multi-robot path planning algorithm (MRPPA) for 2D static environments is developed and evaluated. It combines a roadmap method, utilising the visibility graph (VG), with the algebraic connectivity (second smallest eigenvalue (λ2)) of the graph’s Laplacian and Dijkstra's algorithm. The paths depend on the planning order, i.e., they are in sequence path-by-path, based on the measured values of algebraic connectivity of the graph’s Laplacian and the determined weights functions. Algebraic connectivity maintains robust communication between the robots during their movements while avoiding collision. The algorithm efficiently balanced connectivity maintenance and path length minimisation thus improving the performance of path finding. It produced solutions with optimal paths, i.e., the shortest and safest route. The devised MRPPA significantly improved path length efficiency across different configurations. The results demonstrated a highly efficient and robust solution for multi-robot systems requiring both optimal path planning and reliable connectivity, making it well-suited in scenarios where communication between robots is necessary. Simulation results demonstrated the performance of the proposed algorithm in balancing the path optimality and network connectivity across multiple static environments with varying complexities. The algorithm is suitable for identifying optimal and complete collision-free paths. The results illustrated the algorithm's effectiveness, computational efficiency, and adaptability.