Mobile agents cover unknown spaces while staying connected
On the Control of Mobile Ad-Hoc Agent Deployments in Partially Observed Space
Robotics
Summary
This paper looks at how groups of mobile agents (like robots or sensors) can explore and cover an unknown space made of straight walls with corners and holes. The authors prove a method called CADENCE that guarantees full coverage while keeping the agents connected by sight, using relatively few agents. They also test different ways to decide the order in which agents move to finish faster or with fewer agents. This helps understand how to deploy teams that watch over areas without losing contact with each other.
What this means in practice
- •For security teams: Deploy mobile security agents to fully monitor complex indoor spaces while keeping a communication link open among them.
- •For robotics engineers: Plan robot teams to explore and cover unknown indoor environments effectively with guarantees on connectivity and coverage.
Authors
Edwin Meriaux, Louis-Roy Langevin, Shuo Wen, Ndiamé Ndiaye, Gregory Dudek, Antonio Loría
Abstract
We study the online deployment of mobile ad hoc networks in unknown orthogonal environments, formalized as the Partially Observable Cooperative Guard Art Gallery Problem. We give a full proof that CADENCE algorithms achieve full coverage while maintaining a connected visibility graph using at most $n/2 + h - 2$ agents in orthogonal worlds with $n$ corners and $h$ holes. We further evaluate deployment-order heuristics that reduce agent count and deployment time in practice.