Path Planning for Multiple Robots: An Alternative Duality Approach

We propose an optimization-based framework to find multiple fixed length paths for multiple robots that satisfy the following constraints: (i) bounded curvature, (ii) obstacle avoidance, (iii) and collision avoidance. By using polygonal approximation techniques, we show that path planning problem for multiple robots under various constraints and missions, such as curvature and obstacle avoidance constraints as well as rendezvous and maximal total area coverage, can be cast as a nonconvex optimization problem. Then, we propose an alternative dual formulation that results in no duality gap. We show that the alternative dual function can be interpreted as minimum potential energy of a multi-particle system with discontinuous spring-like forces. Finally, we show that using the proposed duality-based framework, an approximation of the minimal length path planning problem (also known as Dubins' problem) in presence of obstacles can be solved efficiently using primal-dual interior-point methods.