Distributed Algorithms for Hierarchical Area Coverage Using Teams of Homogeneous Robots
Sriram Raghavan, Satya Sai Baba · 2007
Covering a given area using a team of mobile robots poses several challenges. One such challenge lies in guaranteeing efficient coverage in the absence of complete information. The robots (agents) must cover the area in a manner that the overlap (repeated coverage) in coverage across all the robots is minimized. In this thesis, we introduce “overlap_ratio” to explicitly measure the overlap in coverage for various algorithms. This measure has been shown to adequately represent the performance of any coverage system as it effectively captures the resource usage as well as the time required for coverage. We show systematically how the area coverage algorithms, which perform complete coverage with minimum overlap, can be designed for a team of mobile robots. We begin by understanding the behavior of robots in a random-walk model and successively refine the model to provide the robots with additional capabilities and minimize the overlap. We gradually transition from random decision-making to deterministic decision-making and suggest appropriate algorithms to suit various application needs and capabilities. We also prove that arbitrarily large areas can be covered with simple and elegant coverage algorithms by hierarchically composing it using smaller areas called primitives. An associated theorem called the HC theorem that provides a linear scaling of overlap ratio with exponential increase in area has been proved. Further, this theorem is applicable across arbitrary number of levels in hierarchy. We demonstrate the same experimentally through simulation. Performance of such multi-robot (agent) applications critically depends on the communication architecture that facilitates coordination. A generic architecture often turns out to be burdensome on the robot (agent) due to overhead. With significant increase in the number of applications, a