Distributed Multi-Robot Partition-based Patrolling with Fault Tolerance
Authors
van Peet, Henrik ; Santhirasegaram, Puvikaran ; Mogensen, Mads Beyer
Term
4. term
Education
Publication year
2025
Submitted on
2025-06-13
Pages
10
Abstract
Patruljeopgaver med flere robotter er vigtige i fx overvågning og monitorering, hvor målet er at holde tiden mellem besøg på et givent sted så kort som muligt. Dette projekt præsenterer Heuristic Meeting-based Patrolling (HMP), en ny distribueret og fejltolerant algoritme, der koordinerer robotter uden en central controller og med meget begrænset kommunikation. Miljøet er opdelt i områder, og robotterne patruljerer hver deres del. Ved lejlighedsvise synkroniseringsmøder på fælles mødesteder udveksler robotterne små mængder information for at opdage fejl hos teammedlemmer og fordele opgaverne på ny, så dækningen fortsætter. HMP bygger på den tidligere Heuristic Conscientious Reactive (HCR)-strategi og tilføjer periodiske møder, der muliggør decentral koordination og dynamisk fejlretning. Vi testede HMP og simplere varianter i en række simulerede miljøer med Multi-Agent Exploration and Patrolling Simulator (MAEPS). I vores tests klarede HMP sig godt både under normale forhold og ved robotfejl og opnåede ventetider mellem besøg (idleness) på niveau med førende patruljestrategier. Vi fandt også begrænsninger: I nogle fejlscenarier kan planlægningen af møder bryde sammen og føre til kaskaderende fejl, hvor ét problem udløser andre. Vi skitserer forbedringsmuligheder, herunder smartere mødeplanlægning og adaptiv opdeling, der kan re-fordele områderne, når forholdene ændrer sig.
Patrolling with teams of robots is important for tasks like surveillance and monitoring, where the goal is to keep the time between visits to any location as short as possible. This project introduces Heuristic Meeting-based Patrolling (HMP), a new distributed and fault-tolerant algorithm that coordinates robots without a central controller and with very limited communication. The environment is divided into regions, and robots patrol their parts. At occasional synchronization meetings at shared points, robots exchange small amounts of information to detect teammate failures and reassign areas so coverage continues. HMP builds on the earlier Heuristic Conscientious Reactive (HCR) strategy, adding periodic meetings to enable decentralized coordination and dynamic recovery from faults. We tested HMP and simpler variants in a range of simulated environments using the Multi-Agent Exploration and Patrolling Simulator (MAEPS). In our tests, HMP performed strongly under both normal conditions and robot failures, achieving visit delays (idleness) comparable to leading patrolling methods. We also found limits: under some failure scenarios, the scheduling of meetings can break down and lead to cascading failures, where one problem triggers others. We outline opportunities for improvement, including smarter meeting scheduling and adaptive partitioning that can re-divide the environment as conditions change.
[This summary has been rewritten with the help of AI based on the project's original abstract]
Keywords
Documents