CAMS: Collision Avoiding Max-Sum for Mobile Sensor Teams

Recent advances in technology have large teams of robots with limited computation and communication skills work together in order to achieve a common goal. Their personal actions need to contribute to the joint effort, however, they also must assure that they do not harm the efforts of the other members of the team, e. g. , as a result of collisions. We focus on the distributed target coverage problem, in which the team must cooperate in order to maximize utility from sensed targets, while avoiding collisions with other agents. State of the art solutions focus on the distributed optimization of the coverage task in the team level, while neglecting to consider collision avoidance, which could have far reaching consequences on the overall performance. Therefore, we propose CAMS: a collision-avoiding version of the Max-sum algorithm, for solving problems including mobile sensors. In CAMS, a factor-graph that includes two types of constraints (represented by functionnodes) is being iteratively generated and solved. The first type represents the task-related requirements, and the second represents collision avoidance constraints. We prove that consistent beliefs are sent by target representing function-nodes during the run of the algorithm, and identify factor-graph structures on which CAMS is guaranteed to converge to an optimal (collision-free) solution. We present an empirical evaluation in extensive simulations, showing that CAMS produces high quality collision-free coverage also in large and complex scenarios. We further present evidence from experiments in a real multi-robot system that CAMS outperforms the state of the art in terms of convergence time.

Authors

• Arseni Pertzovskiy Ben-Gurion University of the Negev
• Roie Zivan Ben-Gurion University of the Negev
• Noa Agmon Department of Computer Science, Bar-Ilan University

Keywords

• Distributed Constraint Optimization Problems (DCOP)
• Mobile Sensor Teams
• Max-sum Belief Propagation