Distributed Constraint Optimization for large teams of mobile sensing agents

Abstract

A team of mobile sensors can be used for coverage of targets in different environments. The dynamic nature of such an application requires the team of agents to adjust their locations with respect to changes which occur. The dynamic nature is caused by environment changes, changes in the agents’ tasks and by technology failures. A new model for representing problems of mobile sensor teams based on Distributed Constraint Optimization Problems (DCOP), is proposed. The proposed model, needs to handle a dynamic problem in which the alternative assignments for agents and set of neighbors, derive from their physical location which is dynamic. DCOP MST enables representation of variant dynamic elements which a team of mobile sensing agents face. A reputation model is used to determine the credibility of agents. By representing the dynamic sensing coverage requirements in the same scale as the agents’ credibility, the deployment of sensors in the area can be evaluated and adjusted with correspondence to dynamic changes. In order to solve a DCOP MST, a local (incomplete) search algorithm (MGM MST) based on the MGM algorithm is proposed and combined with various exploration methods. While existing exploration methods are evidently not effective in DCOP MSTs, new exploration methods which are designed for these special applications are found to be successful in our experimental study.