Spiralling Human Heuristics Exploration with doorway detection - The Minotaur Exploration Algorithm
Authors
Beregaard, Thor ; Schmidt, Rasmus Borrisholt ; Sørensen, Andreas Sebastian
Term
4. term
Education
Publication year
2024
Submitted on
2024-05-31
Pages
20
Abstract
Exploring unknown spaces quickly makes robot swarms more useful, for example in space missions or search and rescue. Earlier methods have often focused on exploring the boundary between known and unknown areas (frontier-based approaches) or on nature-inspired strategies. This thesis introduces Minotaur, a human-heuristics–based exploration algorithm for static buildings. It uses simple rules similar to how people explore: robots follow walls to discover rooms and doorways, then move through already mapped areas using a SLAM map (Simultaneous Localization and Mapping—a map built while the robot also estimates its own position). When a room is finished, robots proceed to the nearest unexplored doorway. Multiple robots share maps and information about doorways and can coordinate to split up, reducing redundant coverage and enabling fast exploration through both designed and emergent behavior. We evaluated Minotaur in the MAES simulator against TNF and a greedy approach. The results show clear improvements, especially when communication is limited. Minotaur takes about one half to one quarter of the time TNF needs to explore a map and is slightly faster than Greed in some cases. Its speed advantage also grows with more robots, indicating that Minotaur scales well to large robot teams.
At kunne udforske ukendte områder hurtigt gør robotsværme mere nyttige, for eksempel i rumfart eller søg‐og‐redning. Tidligere metoder har ofte fokuseret på at udforske grænserne mellem kendt og ukendt område (frontier-baserede metoder) eller på strategier inspireret af naturen. I denne afhandling præsenterer vi Minotaur, en menneskeinspireret udforskningsalgoritme til statiske bygninger. Den bruger simple, velkendte tommelfingerregler: Robotterne følger vægge for at finde rum og døråbninger, og de bevæger sig derefter gennem allerede kortlagte områder ved hjælp af et SLAM-kort (Simultaneous Localization and Mapping – et kort, der bygges, mens robotten samtidig bestemmer sin egen position). Når et rum er udforsket, fortsætter robotterne til den nærmeste uudforskede døråbning. Flere robotter deler kort og viden om døre, og de kan koordinere, så de deler sig op og undgår at dække det samme område flere gange. Det giver hurtig udforskning gennem både planlagte og fremvoksende (emergente) samarbejdsmønstre. Vi sammenlignede Minotaur med TNF og en grådig (greedy) tilgang i MAES-simulatoren. Resultaterne viser en klar forbedring, især når robotterne har begrænset kommunikation. Minotaur bruger omkring halvdelen til en fjerdedel af tiden i forhold til TNF for at udforske et kort og er i nogle tilfælde lidt hurtigere end Greed. Desuden bliver Minotaurs hastighedsfordel større, jo flere robotter der er med, hvilket viser, at metoden er velegnet til systemer med mange robotter.
[This apstract has been rewritten with the help of AI based on the project's original abstract]
Keywords