Distributed Dynamic Priority Assignment and Motion Planning for Multiple Mobile Robots with Kinodynamic Constraints

Wenhao Luo, Nilanjan Chakraborty and Katia Sycara
Conference Paper, American Control Conference (ACC), July, 2016

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.


We present a distributed on-line coordinated motion planning approach for a group of mobile robots moving amidst dynamic obstacles. The objective for the motion planning is to minimize the total distance traveled by the robots as well as the danger of deadlock. Kinematic constraints, robot-obstacle collision avoidance constraints, and velocity/acceleration constraints are explicitly considered in individual robot’s motion planner. A dynamic priority based scheme is proposed to deal with pair-wise inter-robot collision constraints. In particular, we model the assignment of priority into a minimum linear ordering problem (MLOP). We prove that the objective function of the MLOP is supermodular and propose a decentralized supermodular linear ordering algorithm that interleaves dynamic priority assignment and planning for the robots, such that the overall path length and the danger of deadlock are both minimized. Simulation results are provided to show the effectiveness of the proposed approach.

author = {Wenhao Luo and Nilanjan Chakraborty and Katia Sycara},
title = {Distributed Dynamic Priority Assignment and Motion Planning for Multiple Mobile Robots with Kinodynamic Constraints},
booktitle = {American Control Conference (ACC)},
year = {2016},
month = {July},
} 2017-09-13T10:38:20-04:00