Spiralling Human-Inspired Exploration Algorithm with Doorway Detection
Rasmus B. Schmidt, Andreas Sørensen, Thor Beregaard, Michele Albano · 2025
Exploration of unknown environments is an important task for autonomous robot swarm systems. The faster they can fully explore an area, the faster a coordinated plan can be made, or points of interest found, to support further tasks. Previous algorithms have often focused either on frontier based, or nature-inspired heuristics. We present a human-inspired exploration algorithm, Minotaur, that enables simple and efficient exploration of buildings. We studied how Minotaur and a state-of-the-art algorithm, namely The Next Frontier (TNF), perform. Minotaur follows walls to discover doorways, after which it coordinates with robots in the same room to extend the exploration to rooms accessible through the discovered doorways. Most algorithms assume either perfect communication, or line-of-sight (LOS) communication, which hinders the realism of the simulation results. We then modified an existing simulator to take into account realistic communication technologies that have limited penetration of materials through walls. Comparative experiments between Minotaur, TNF, and a simple greedy algorithm show the superiority of Minotaur when multiple robots are exploring buildings-like maps. However, when considering cave-like maps, Minotaur appears to have bad performance, but the greedy algorithm outperforms TNF, particularly when the algorithms are limited in their communication capabilities.