Multi-Agent Motion Planning For Differential Drive Robots Through Stationary State Search
Jingtian Yan, Jiaoyang Li · 2024
Read Multi-Agent Motion Planning For Differential Drive Robots Through Stationary State Search by Jingtian Yan, Jiaoyang Li (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-13359.txt.
Introduction
Jingtian Yan and Jiaoyang Li tackle route plans for fleets of small drive robots in a 2024 paper. Such robots can only turn in place or roll straight ahead, within speed and ramp limits. Past fleet methods often used loose models of that motion, which made their plans hard to use in real halls and yards.
Their three-step method pairs fleet search with a new search that holds robots still at key states. A shifting window lets the same plan run on and on for warehouse work. In grid and warehouse tests, the method moved far more goods per hour than past methods, by up to four times.
Catalog record
| CREATOR | Jingtian Yan, Jiaoyang Li |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-13359
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Multi-Agent Motion Planning For Differential Drive Robots Through Stationary State Search Jingtian Yan, Jiaoyang Li Abstract Multi-Agent Motion Planning (MAMP) finds various applications in fields such as traffic management, airport operations, and warehouse automation. In many of these environments, differential drive robots are commonly used. These robots have a kinodynamic model that allows only in-place rotation and movement along their current orientation, subject to speed and acceleration limits. However, existing Multi-Agent Path Finding (MAPF)-based methods often use simplified models for robot kinodynamics, which limits their practicality and realism. In this paper, we introduce a three-level framework called MASS to address these challenges. MASS combines MAPF-based methods with our proposed stationary state search planner to generate high-quality kinodynamically-feasible plans. We further extend MASS using an adaptive window mechanism to address the lifelong MAMP problem. Empirically, we tested our methods on the single-shot grid map domain and the lifelong warehouse domain. Our method shows up to 400% improvements in terms of throughput compared to existing methods. 1 Introduction We study the Multi-Agent Motion Planning (MAMP) problem which aims to find collision-free kinodynamically feasible paths for a team of agents in a fully observable environment while minimizing their arrival time. This problem finds various real-world applications, including traffic management ( Ho et al. 2019 ) , airport operations ( Li et al. 2019 ) , and warehouse automation ( Kou et al. 2019 ) . Differential drive robots are widely used in many of these environments. These robots, often navigating on a grid map, can move forward along their orientation with bounded velocity and acceleration. They can only change their orientation through in-place rotation when at zero speed. Although much work has been done to address the MAMP problem, existing methods often either fail to account for the orientations of robots or overlook continuous dynamic constraints. Figure 1: Speed profile of agent A (blue line: linear velocity, red line: angular velocity) generated by (a) MAPF, (b) MAPF+ADG, (c) SIPP-IP, (d) PSB, and (e) MASS. Agent A first moves upward (ACT1) while adjusting its speed to avoid collisions with agent B, performs an in-place rotation (ACT2), and then moves to the right (ACT3). Multi-Agent Path Finding (MAPF) ( Stern et al. 2019 ) methods are a promising solution that scales to hundreds of agents. However, they assume instantaneous movement and infinite acceleration capabilities, resulting in plans that are unrealistic for real-world execution (see Fig. 1 (a) for an example). To apply MAPF methods to MAMP, ADG ( Hönig et al. 2019 ) post-processes the speed profiles of the MAPF plan to meet kinodynamic constraints while maintaining the passing orders of agents at each location. However, as shown in Fig. 1 (b), such methods can lead to long execution time as the initial MAPF plan ( Fig. 1 (a)) overlooks kinodynamic constraints. SIPP-IP ( Ali and Yakovlev 2023 ) extends MAPF methods to MAMP by searching with a fixed number of predefined actions with discretized speeds and accelerations. However, as shown in Fig. 1 (c), due to its discretized nature, the limited action choices can lead to long execution time or even failures in solving certain cases. Moreover, to account for the different choices of speeds and accelerations, SIPP-IP explores a high-dimensional state space which compromises its efficiency. The recent work PSB ( Yan and Li 2024 ) avoids such discretization by combining search-based and optimization-based methods, but it does not consider the orientations of agents, making it hard to apply to differential drive robots, as shown in Fig. 1 (d). In this work, we introduce MA PF- S SIPP- S PS (MASS), a framework to address the MAMP problem for differential drive robots. MASS uses a key observation that the plan for these robots always alternates between rotation and movement. Thus, the state at the transition between two actions (finish a movement to start rotation or the reverse) is critically important. Since those states must have zero speed, we refer to them as stationary states . Instead of searching at high-dimensional state space that models various speeds of robots, we focus our search on these stationary states and actions that connect them. In MASS, we use a MAPF-based planner at Level 1 to resolve collisions between agents. This level imposes temporal constraints on Level 2 and calls it to get a plan for each agent. We propose Stationary Safe Interval Path Planning (SSIPP) at Level 2 to search for a single-agent kinodynamically feasible plan. Compared to standard SIPP ( Phillips and Likhachev 2011 ) , SSIPP uses stationary node expansion to find neighboring stationary states and the actions needed to reach them. At Level 3, an optimization-based speed profile solver (SPS) is used to determine the speed profiles for these actions. Our main contributions include: 1. We propose a framework called MASS, a three-level MAMP planner capable of finding collision-free plans for a large group of differential drive robots. 2. We evaluate MASS on the standard MAPF benchmark, showing significant improvement in terms of success rate, especially for large-scale maps. 3. We extend MASS to address the lifelong MAMP problem where agents are assigned new goals after they reach their current ones. We evaluate MASS in a high-fidelity automated warehouse simulator (shown in Figure 7 ). MASS shows up to 400% improvement in terms of solution cost compared to a MAPF planner with a post-processing framework. 2 Background In this section, we begin with a review of MAPF algorithms. After that, we go through the related work in MAMP. MAPF Algorithms MAPF methods have achieved remarkable progress in finding discrete collision-free paths for hundreds of agents. Most state-of-the-art MAPF methods, such as Conflict-Based Search (CBS) ( Sharon et al. 2015 ; Andreychuk et al. 2022 ) and Priority-Based Search (PBS) ( Ma et al. 2019 ) , use a bi-level structure. At the high level, they resolve collisions among agents by introducing temporal obstacles into low-level single-agent solvers. These solvers then plan paths for individual agents trying to avoid those temporal obstacles. In our experiments, we test MASS with two MAPF algorithms, PP and PBS. In Priority Planning (PP) ( Erdmann and Lozano-Perez 1987 ) , the planner begins by assigning a total priority ordering to all agents requiring lower-priority agents to avoid collisions with higher-priority ones. Then, the PP plans paths for each agent from high priority to low priority. During this process, agents treat the path from higher priority agents as temporal obstacles. Priority-Based Search (PBS) ( Ma et al. 2019 ) searches for a good priority ordering that prevents collisions among agents. PBS explores a binary Priority Tree (PT) in a depth-first manner, where each PT node contains a set of partial priority orderings and corresponding paths. The root node starts with no priority orderings. When a collision between agents a_{i} and a_{j} is detected, the PT is expanded by creating two child nodes, each with an additional priority ordering i\prec j or j\prec i , indicating a_{i} has higher or lower priority than a_{j} . In each child node, PBS uses a low-level planner to replan the paths based on the updated priority orderings. The search terminates when a PT node with collision-free paths is found. MAMP Algorithms The first