Multi-Robot Guided Sampling-Based Motion Planning With Dynamics in Partially Mapped Environments

Abstract

Multi-robot motion planning is a core capability in robotics, yet is made challenging by the need to simultaneously consider robot dynamics, robots obstructing the paths of their teammates, and static obstacles during deployment, challenges that compound when the map is not known in advance. This paper proposes a multi-robot sampling-based motion-planning framework for navigation and fast replanning that emphasizes performance in partially-known environments. To make the framework work efficiently, we developed a novel two-stage multi-robot adaptive motion planning technique; furthermore, an occupancy grid cell-based distance is introduced to represent the minimum distance a robot should cover before initiating the replanning process. Our framework reaches 90% success-rate with 7 snake-like robots and with 8 car-like robots in all but one of a set of challenging simulated environments, exceeding in all cases the performance of a competitive sampling-based motion planner baseline that struggles to reach 25% success in the most difficult cases. The framework also exhibits significant improvements in both runtime and travel distances.

Keywords

• Mobile robots
• motion planning
• multi-robot systems
• unknown environments
• robot motion