EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

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

Fatma A. S. Alwafi, Reza Saatchi, Xu Xu, Lyuba Alboul

Applied Sciences · 15.03.2026 · 16 (6) · 2822

DOI: 10.3390/app16062822 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Applied Sciences, online erschienen am 15.03.2026. Verfasst von Fatma A. S. Alwafi und 3 weiteren Autor:innen. Die Arbeit nennt 61 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Alwafi, F. A. S., Saatchi, R., Xu, X., & Alboul, L. (2026). Graph-Theoretic Models and Comparative Evaluations of Novel Multi-Robot Path Planning Algorithms for Collision Avoidance and Navigation Optimisation. Applied Sciences, 16(6), 2822. https://doi.org/10.3390/app16062822

Vancouver

Alwafi FAS, Saatchi R, Xu X, Alboul L. Graph-Theoretic Models and Comparative Evaluations of Novel Multi-Robot Path Planning Algorithms for Collision Avoidance and Navigation Optimisation. Applied Sciences. 2026;16(6):2822. doi:10.3390/app16062822

BibTeX
@article{Alwafi2026,
  author = {Alwafi, Fatma A. S. and Saatchi, Reza and Xu, Xu and Alboul, Lyuba},
  title = {Graph-Theoretic Models and Comparative Evaluations of Novel Multi-Robot Path Planning Algorithms for Collision Avoidance and Navigation Optimisation},
  journal = {Applied Sciences},
  year = {2026},
  volume = {16},
  number = {6},
  pages = {2822},
  doi = {10.3390/app16062822}
}
Kostenlos starten →