Brick & Mortar: an on-line multi-agent exploration algorithm

When an emergency occurs within a building, it is critical to explore the area as fast as possible in order to find victims and identify hazards. We propose Brick& Mortar, an algorithm for the autonomous exploration of unknown terrains by a team of mobile nodes, referred to as agents. Because of the unreliability and short range of wireless communications in an indoor environment we suggest that agents communicate indirectly with each other by tagging the environment. Agents have no prior knowledge of the terrain map, but are able to coordinate in order to explore a variety of terrains with different topological features. In our experimental evaluation, we show that Brick&Mortar significantly outperforms the competing algorithms, namely Ants and Multiple Depth First Search, in terms of exploration time. The observed performance benefits suggest that our algorithm is suitable for safety-critical applications that require rapid area coverage for real-time event detection and response.

Authors

• Ettore Ferranti
• Niki Trigoni
• Mark Levene

Keywords

• Mortar
• Hazards
• Wireless communication
• Indoor environments
• Chemicals
• Terrorism
• Robotics and automation
• Tagging
• Event detection
• Explosives
• Exploration Algorithm
• Multi-agent Exploration
• First Search
• Topological Features
• Exploration Time
• Multiple Search
• Depth-first
• Multiple Depths
• Variable Terrain
• Cell State
• Use Of Resources
• Number Of Steps
• Search Algorithm
• Adjacent Cells
• Grid Cells
• Number Of Agents
• Network Infrastructure
• Hybrid Algorithm
• Presence Of Loop
• Loop Closure
• Exploration Task
• Rescue Teams
• Emergency Scenarios
• West Direction