computational robotics

from tasks to motions

Cooperative, Dynamics-Based, and Abstraction-Guided Multi-Robot Motion Planning

Multi-robot systems provide a viable venue to enhance automation so as to increase productivity and reduce operational costs in an increasing number of applications ranging from exploration, inspection, surveillance, search-and-rescue, to transportation. In these settings, as part of the overall operations, the robots are often required to move to different locations while avoiding collisions with obstacles and other robots. As a fundamental requirement to enhance the autonomy, the multi-robot system must possess a motion-planning framework that can efficiently generate feasible motion plans so that each robot safely reaches its goal.

This work develops an effective, cooperative, and probabilistically-complete multi-robot motion planner that enables each robot to move to a desired location while avoiding collisions with obstacles and other robots. The approach takes into account not only the geometric constraints arising from collision avoidance, but also the differential constraints imposed by the motion dynamics of each robot. This makes it possible to generate collision-free and dynamically-feasible trajectories that can be executed in the physical world.

The salient aspect of the approach is the coupling of sampling-based motion planning to handle the complexity arising from the obstacles and robot dynamics with multi-agent search to find solutions over a suitable discrete abstraction. The discrete abstraction is obtained by constructing roadmaps to solve a relaxed problem that accounts for the obstacles but not the dynamics. Sampling-based motion planning expands a motion tree in the composite state space of all the robots by adding collision-free and dynamically-feasible trajectories as branches. Efficiency is obtained by using multi-agent search to find non-conflicting routes over the discrete abstraction which serve as heuristics to guide the motion-tree expansion. When little or no progress is made, the routes are penalized and the multi-agent search is invoked again to find alternative routes. This synergistic coupling makes it possible to effectively plan collision-free and dynamically-feasible motions that enable each robot to reach its goal. Experiments using vehicle models with nonlinear dynamics operating in complex environments, where cooperation among robots is required, show significant speedups over related work.

Related Publications

  • Le D and Plaku E (2018): ``Multi-Robot Motion Planning with Dynamics via Coordinated Sampling-Based Expansion Guided by Multi-Agent Search.'' IEEE Robotics and Automation Letters, under review  [publisher]  [preprint]
  • Le D and Plaku E (2018): ``Cooperative, Dynamics-Based, and Abstraction-Guided Multi-Robot Motion Planning.'' Journal of Artificial Intelligence Research, vol. 63, pp. 361--390  [publisher]  [preprint]
  • Le D and Plaku E (2018): ``Multi-Robot Motion Planning with Dynamics Guided by Multi-Agent Search.'' Proceedings of the International Joint Conferences on Artificial Intelligence, pp. 5314--5318  [publisher]  [preprint]
  • Le D and Plaku E (2017): "Cooperative Multi-Robot Sampling-Based Motion Planning with Dynamics." Proceedings of the International Conference on Planning and Scheduling, pp. 513--521 (Best Robotics Paper)  [publisher]  [preprint]