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

June 2010

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

Authors:

Subhrajit Bhattacharya, Vijay Kumar, and Maxim Likhachev

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.
@conference{Bhattacharya-2010-109592,
author = {Subhrajit Bhattacharya And Vijay Kumar And Maxim Likhachev},
title = {Distributed Optimization with Pairwise Constraints and its Application to Multi-robot Path Planning},
booktitle = {Proceedings of Robotics: Science and Systems (RSS '10)},
year = {2010},
month = {June},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.