Explorative Max-sum for Teams of Mobile Sensing Agents

Multi-agent applications that include teams of mobile sensing agents are challenging since they are inherently dynamic and a single movement of a mobile sensor can change the problem that the whole team is facing. While agents select their positions with respect to the information available to them in their local environment, by moving to a different location they can reveal new information, e.g., targets, which they were not aware of before. Thus, exploration is required for such information to be revealed. A variation of the DCOP model (DCOP_MST) was previously adjusted to represent such problems along with local search algorithms that were enhanced with exploration methods. In this paper we design an explorative version of Max-sum for solving DCOP_MST, which is based on an iterative process where, at each iteration, agents generate and solve a specific problem instance. We demonstrate that this basic algorithm (Max-sum_MST) converges faster than other standard local search algorithms thatwere adjusted to solve DCOP_MSTs, however, its exploitive naturemakes it inferior to explorative local search algorithms. Thus, we designed exploration methods that when combined with basic Max-sum_MST, significantly outperform the existing explorative local search algorithms. Moreover, the best performing method we propose also eliminates the exponential time complexity of Max-sum by bounding the number of agents involved in each constraint.