New Strategies for multi-robot coordination in optimal deployment problems

Abstract

In recent years, multi-robot systems have played an increasing role in many real world applications thanks to its flexibility, robustness, and reduced cost when compared to single-robot solutions. One of the important challenges in this field is to efficiently distribute and coordinate a team of robots over the environment, so that desired tasks can be properly performed by this team. In this work we extend previousmethods on multi-robot deployment in order to improve safety, convergence, applicability and computational time. In the first extension, we propose a new strategy based on the locational optimization framework. Our approach models the optimal deploymentproblem as a constrained optimization problem with inequality and equality constraints. In order to consider the generation of safe paths during the deployment or in future excursions through the environment, this optimization model is built by incorporating: the classical Generalized Voronoi Diagram (GVD); and a new metric to compute distance in the environment. GVD is commonly used as a safe roadmap in the context of path planning, and the new metric induces a new Voronoi partitionof the environment. Furthermore, inspired by the classical Dijkstra algorithm, we present a novel efficient distributed algorithm to compute solutions in complicated environments. A new distributed multi-robot deployment algorithm is proposed as the second extension. By relying on the novel strategy of continuous movement in a discrete approximation of the environment, the convergence of the algorithm is proven. Furthermore, as our third extension, we present a new implementation of the proposed deployment algorithm. When the number of robots is large or the region corresponding to each robot is large, the computational time of the locational optimization framework might be high. Thus, a new algorithm is proposed, which is able to run in parallel setup. CUDA is used as a platform for running the proposed algorithm. In our fourth extension, we propose a new discrete deployment strategy which properly works on a topological framework. This framework represents environments as a topological map, which transforms the original two or three-dimensional problem into a one-dimensional, simplified problem, thus reducing the computational cost of the solution. It also makes the new deployment model suitable for the environments that can be represented by a topological map, such as block-shape cities or corridorbased buildings i.e. departments in universities, hospitals, governmental offices, etc. It is important to mention that this combination of our discrete deployment with the topological framework is appropriate for the scenarios, where the map is large and the response must be fast. All the extensions are validated in simulations or actual robots experiments.