Distributed Optimization with Pairwise Constraints and its Application to Multi-robot Path Planning

Abstract

Distributed approaches to constrained optimization problems have immense applications to multi-robot path planning, scheduling, task allocation and other problems requiring multiple robots to optimize a global objective function. The aim of these approaches is to solve a series of smaller optimization problems for each robot while sharing information among the robots, and in the process, solve the global optimization problem, which otherwise would have been intractable. Distributed approaches to separable convex optimization problems with linear constraints have been studied extensively in the past using techniques of dual and Lagrangian decomposition. In the present work, we investigate a distributed implementation of a general separable optimization problem with pair-wise non-linear constraints. On the theoretical side, we show the conditions under which the algorithm converges to an optimal solution. On the experimental side, we demonstrate the utility of the algorithm on the problem of multi-robot path planning with pair-wise distance constraints in large complex 2-D environments with obstacles.