Distributed constraint optimization for teams of mobile sensing agents

Abstract

Coordinating a mobile sensor team (MST) to cover targets is a challenging problem in many multiagent applications. Such applications are inherently dynamic due to changes in the environment, technology failures, and incomplete knowledge of the agents. Agents must adaptively respond by changing their locations to continually optimize the coverage of targets. We propose distributed constraint optimization problems (DCOP)_MST, a new model for representing MST problems that is based on DCOP. In DCOP_MST, agents main- tain variables for their physical positions, while each target is represented by a constraint that reflects the quality of coverage of that target. In contrast to conventional, static DCOPs, DCOP_MST not only permits dynamism but exploits it by restricting variable domains to nearby locations; consequently, variable domains and constraints change as the agents move through the environment. DCOP_MST confers three major advantages. It directly represents the multiple forms of dynamism inherent in MSTs. It also provides a compact representation that can be solved efficiently with local search algorithms, with information and communi- cation locality based on physical locality as typically occurs in MST applications. Finally, DCOP_MST facilitates organization of the team into multiple sub-teams that can specialize in different roles and coordinate their activity through dynamic events. We demonstrate how a search-and-detection team responsible for finding new targets and a surveillance sub-team tasked with coverage of known targets can effectively work together to improve performance while using the DCOP_MST framework to coordinate. We propose different algorithms to meet the specific needs of each sub-team and several methods for cooperation between sub- teams. For the search-and-detection team, we develop an algorithm based on the DSA that forces intensive exploration for new targets. For the surveillance sub-team, we adapt several incomplete DCOP algorithms, including MGM, DSA, DBA, and Max-sum, which requires us to develop an efficient method for agents to find the value assignment in their local envi- ronment that is optimal in minimizing the maximum unmet coverage requirement over all targets. The disadvantage of dynamic domains based on physical locality is that adaptations of standard local search algorithms tend to become trapped in local optima where targets beyond the immediate range of the agents go uncovered. To address this shortcoming we develop exploration methods to be used with the local search algorithms. Our algorithms are extensively evaluated in a simulation environment. We use a reputation model to determine the individual credibility of agents and consider both additive and submodular joint credi- bility functions for determining coverage of targets by multiple agents. The performance is measured on two objectives: minimizing the maximum remaining coverage requirement, and minimizing the sum of remaining coverage requirements. Our results show that DSA and MGM with the exploration heuristics outperform the other incomplete algorithms across a wide range of settings. Furthermore, organizing the team into two sub-teams leads to signif- icant gains in performance, and performance continues to improve with greater cooperation between the sub-teams.