Development and Evaluation of a Multi-Robot Path Planning Graph Algorithm
A new multi-robot path planning (MRPP) algorithm for 2D static environments was developed and evaluated. It combines a roadmap method, utilising the visibility graph (VG), with the algebraic connectivity (second smallest eigenvalue (λ<sub>2</sub>)) of the graph’s Laplacian and Dijkstra’s...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-05-01
|
| Series: | Information |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2078-2489/16/6/431 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849472108924502016 |
|---|---|
| author | Fatma A. S. Alwafi Xu Xu Reza Saatchi Lyuba Alboul |
| author_facet | Fatma A. S. Alwafi Xu Xu Reza Saatchi Lyuba Alboul |
| author_sort | Fatma A. S. Alwafi |
| collection | DOAJ |
| description | A new multi-robot path planning (MRPP) algorithm for 2D static environments was developed and evaluated. It combines a roadmap method, utilising the visibility graph (VG), with the algebraic connectivity (second smallest eigenvalue (λ<sub>2</sub>)) 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 weight functions. Algebraic connectivity maintains robust communication between the robots during their navigation while avoiding collisions. The algorithm efficiently balances 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 MRPP algorithm significantly improved path length efficiency across different configurations. The results demonstrated highly efficient and robust solutions 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 illustrate the algorithm’s effectiveness, computational efficiency, and adaptability. |
| format | Article |
| id | doaj-art-d666cb2cce794c3e8159352df99ebaae |
| institution | Kabale University |
| issn | 2078-2489 |
| language | English |
| publishDate | 2025-05-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Information |
| spelling | doaj-art-d666cb2cce794c3e8159352df99ebaae2025-08-20T03:24:36ZengMDPI AGInformation2078-24892025-05-0116643110.3390/info16060431Development and Evaluation of a Multi-Robot Path Planning Graph AlgorithmFatma A. S. Alwafi0Xu Xu1Reza Saatchi2Lyuba Alboul3School of Engineering and Built Environment, Sheffield Hallam University, Howard Street, Sheffield S1 1WB, UKSchool of Computer Science, The University of Sheffield, Western Bank, Sheffield S10 2TN, UKSchool of Engineering and Built Environment, Sheffield Hallam University, Howard Street, Sheffield S1 1WB, UKSchool of Engineering and Built Environment, Sheffield Hallam University, Howard Street, Sheffield S1 1WB, UKA new multi-robot path planning (MRPP) algorithm for 2D static environments was developed and evaluated. It combines a roadmap method, utilising the visibility graph (VG), with the algebraic connectivity (second smallest eigenvalue (λ<sub>2</sub>)) 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 weight functions. Algebraic connectivity maintains robust communication between the robots during their navigation while avoiding collisions. The algorithm efficiently balances 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 MRPP algorithm significantly improved path length efficiency across different configurations. The results demonstrated highly efficient and robust solutions 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 illustrate the algorithm’s effectiveness, computational efficiency, and adaptability.https://www.mdpi.com/2078-2489/16/6/431multi-robot path planning algorithmrobotic graph algorithmsrobotic path findingrobotic collision avoidancegraph theoryrobot navigations |
| spellingShingle | Fatma A. S. Alwafi Xu Xu Reza Saatchi Lyuba Alboul Development and Evaluation of a Multi-Robot Path Planning Graph Algorithm Information multi-robot path planning algorithm robotic graph algorithms robotic path finding robotic collision avoidance graph theory robot navigations |
| title | Development and Evaluation of a Multi-Robot Path Planning Graph Algorithm |
| title_full | Development and Evaluation of a Multi-Robot Path Planning Graph Algorithm |
| title_fullStr | Development and Evaluation of a Multi-Robot Path Planning Graph Algorithm |
| title_full_unstemmed | Development and Evaluation of a Multi-Robot Path Planning Graph Algorithm |
| title_short | Development and Evaluation of a Multi-Robot Path Planning Graph Algorithm |
| title_sort | development and evaluation of a multi robot path planning graph algorithm |
| topic | multi-robot path planning algorithm robotic graph algorithms robotic path finding robotic collision avoidance graph theory robot navigations |
| url | https://www.mdpi.com/2078-2489/16/6/431 |
| work_keys_str_mv | AT fatmaasalwafi developmentandevaluationofamultirobotpathplanninggraphalgorithm AT xuxu developmentandevaluationofamultirobotpathplanninggraphalgorithm AT rezasaatchi developmentandevaluationofamultirobotpathplanninggraphalgorithm AT lyubaalboul developmentandevaluationofamultirobotpathplanninggraphalgorithm |