Source-linked AI summary
Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots
Michal Čáp, Peter Novák, Alexander Kleiner, Martin Selecký
TL;DR
The paper addresses the incompleteness of prioritized planning and its centralized design for collision-free multi-robot trajectory coordination. It revises the algorithm, characterizes sufficient solvability conditions, and introduces asynchronous decentralized variants. Experiments and analysis show reliable performance on supported instances and faster convergence than synchronized decentralization.
Problem
Prioritized planning is practical but generally incomplete, lacks formal solvability analysis, and is centralized.
Method
The paper proposes revised prioritized planning with sufficient solvability conditions and asynchronous decentralized variants of classical and revised schemes.
Results
Experiments on real-world indoor maps show RPP solves instances where classical prioritized planning and ORCA fail, while asynchronous decentralization is faster than synchronized decentralization.
Takeaways & Limitations
RPP can reliably coordinate robots in valid infrastructures, and asynchronous decentralization can support faster distributed planning and online multi-UAV conflict resolution.
Abstract
from arXiv · showhide
An important capability of autonomous multi-robot systems is to prevent collision among the individual robots. One approach to this problem is to plan conflict-free trajectories and let each of the robots follow its pre-planned trajectory. A widely used practical method for multi-robot trajectory planning is prioritized planning, which has been shown to be effective in practice, but is in general incomplete. Formal analysis of instances that are provably solvable by prioritized planning is still missing. Moreover, prioritized planning is a centralized algorithm, which may be in many situations undesirable. In this paper we a) propose a revised version of prioritized planning and characterize the class of instances that are provably solvable by the algorithm and b) propose an asynchronous decentralized variant of prioritized planning, which maintains the desirable properties of the centralized version and in the same time exploits the distributed computational power of the individual robots, which in most situations allows to find the joint trajectories faster. The experimental evaluation performed on real-world indoor maps shows that a) the revised version of prioritized planning reliably solves a wide class of instances on which both classical prioritized planning and popular reactive technique ORCA fail and b) the asynchronous decentralized algorithm provides solution faster than the previously proposed synchronized decentralized algorithm.
I. INTRODUCTION
Multi-robot coordination must prevent collisions, but coupled planning scales poorly and decoupled methods can be incomplete. The paper revises prioritized planning and develops asynchronous decentralized variants to address solvability and coordination efficiency.
- Collision-free trajectory coordination is crucial when mobile robots share workspace.
- Coupled planning can find optimal solutions but scales poorly as the number of conflicting robots increases.
- Decoupled planning is fast enough for real-time applications but typically suffers from incompleteness.
- Prioritized planning assigns unique priorities and sequentially plans each robot around higher-priority trajectories.
- The paper proposes a revised prioritized scheme with sufficient solvability conditions and asynchronous decentralized variants that exploit distributed computation.
1 Algorithm PP
Classical prioritized planning sequentially avoids higher-priority robots but can fail even when a coordinated solution exists. Its failure modes motivate conditions and a revised scheme that also protects lower-priority start positions.
- Classical prioritized planning terminates with failure when no satisfying trajectory exists or every such trajectory conflicts with a higher-priority robot.
- Type A conflict occurs when a lower-priority trajectory is blocked by a higher-priority robot already sitting at its destination.
- Type B conflict occurs when a lower-priority trajectory is run over by a moving higher-priority robot.
- A sufficient condition for sequential conflict-free construction is a satisfying path for every robot that avoids lower-priority starts and higher-priority goals.
- Revised prioritized planning avoids lower-priority start positions while avoiding conflicts with higher-priority robots.
- RPP inherits termination and soundness from classical prioritized planning when valid trajectories are found.
1 Algorithm RPP
RPP strengthens prioritized planning by requiring trajectories to avoid lower-priority starts, yielding guaranteed solutions under explicit path conditions. Valid infrastructures provide a practical environment class satisfying those conditions.
- RPP may fail on solvable instances because the required trajectory avoiding lower-priority starts and higher-priority regions is not guaranteed to exist.
- With a complete single-robot planner, RPP is guaranteed to terminate with a conflict-free solution when every robot has a lower-start-avoiding and higher-goal-avoiding path.
- Valid infrastructures require paths between endpoints with at least r-clearance from workspace boundaries and 2r-clearance from other endpoints.
- Valid infrastructures separate long-term endpoint locations from transit areas, as in road networks, offices, and factories.
- In valid infrastructures, endpoint-to-endpoint coordination queries are successfully solved by RPP when single-robot planning is complete.
Checking Solvability
The analysis contrasts classical and revised prioritized planning, showing that neither dominates across all instance classes and that the revised method can produce longer trajectories. Decentralized planning distributes computation across robots to support local replanning.
- RPP completely covers a class of instances that PP does not, but PP also solves instances that RPP fails to solve.
- In the illustrated case, RPP fails because robot 1 cannot avoid robot 2’s start position, whereas PP finds conflict-free trajectories.
- Neither PP nor RPP is superior in terms of overall instance coverage.
- RPP solutions tend to be slightly longer because it preemptively avoids lower-priority robots’ start regions, even when they can be safely traversed.
- Decentralized implementations let robots compute trajectories locally and exchange messages, allowing parallel computation and potentially faster conflict-free solutions.
1 Algorithm SD-(R)PP
SD-(R)PP coordinates robots through trajectory stores containing higher-priority robots’ occupied space-time regions. It is guaranteed to terminate and, under sufficient path conditions and complete single-robot planning, to return conflict-free solutions.
- Each robot maintains a trajectory store containing space-time regions occupied by higher-priority robots.The occupied regions are represented as pairs (j, ∆j), and their union forms the dynamic obstacle set considered during planning.
- SD-(R)PP robots check trajectory consistency against stored higher-priority trajectories and replan or report failure as needed.
- SD-(R)PP is guaranteed to terminate, with termination defined through robots stopping computation and message exchange.
- When SD-(R)PP successfully terminates, all robots hold mutually conflict-free trajectories.
- If every robot has an S>i-avoiding, G<i-avoiding satisfying path and Best-traj is complete, SD-RPP is guaranteed to terminate with a conflict-free solution.
Asynchronous Decentralized Implementation
AD-(R)PP replaces globally synchronized rounds with message-triggered local reactions, reducing idle waiting among robots. It preserves termination, soundness, and the revised scheme’s supported solvability condition.
- Asynchrony addresses idle waiting by allowing robots to resolve conflicts while slower robots continue planning.In the illustrated case, robot 3 begins resolving its conflict immediately after learning about it, rather than waiting for robot 2’s computation.
- AD-(R)PP replaces synchronized rounds with reactions to incoming INFORM messages.A robot updates the sender’s trajectory, checks consistency, and replans only when its current trajectory becomes inconsistent.
- AD-(R)PP terminates, and successful termination yields mutually conflict-free trajectories.
- If every robot has an S>i-avoiding, G<i-avoiding satisfying path and Best-traj is complete, AD-RPP is guaranteed to terminate.
V. EXPERIMENTAL ANALYSIS
The experiments compare centralized and decentralized variants of prioritized planning across real-world environments and task sets, measuring coverage, runtime, communication, and trajectory quality. Revised prioritized planning achieves full coverage for infrastructure tasks, while asynchronous decentralized variants improve speed-up over synchronized versions.
- Experimental setup: The evaluation compares PP, RPP, SD-PP, SD-RPP, AD-PP, and AD-RPP across three real-world environments and free-formed or infrastructure tasks.Measured characteristics include coverage, runtime, communication complexity, and solution quality.
- Experimental limitation: Higher-robot-count free-formed corridor and warehouse instances have low success rates and are excluded from statistically significant conclusions.The corresponding plots use only the few instances solved by every tested algorithm.
- Coverage: All tested algorithms exhibit incomplete coverage on free-formed tasks, with RPP-based algorithms solving fewer instances than PP-based algorithms.RPP failures more often arise because paths avoiding higher-priority robots’ start positions do not exist.
- Coverage: RPP-based algorithms achieve full instance coverage on infrastructure tasks, including instances that PP-based algorithms and ORCA leave unsolved.This outcome agrees with the paper’s theoretical analysis of infrastructure instances.
- Time to solution: Asynchronous decentralized PP and RPP consistently achieve higher speed-up than synchronized implementations, especially as the number of robots increases.Independent conflict clusters can progress at different rates and converge faster under asynchronous execution.
- Replannings/Communication: AD-(R)PP broadcasts more messages than SD-(R)PP because immediate replanning can respond separately to conflicts detected in the same round.Synchronized variants may resolve multiple conflicts in one replanning and one INFORM message.
- Prolongation: RPP-based and decentralized algorithms generate slightly longer trajectories than PP-based and centralized approaches.RPP avoids lower-priority start positions preemptively, while decentralized replanning does not always exploit trajectory improvements that remain consistent.
VI. DEPLOYMENT
The paper evaluates its decentralized planning approach in realistic communication conditions by deploying it as a conflict-resolution mechanism in a multi-UAV system.
- Deployment: The proposed algorithm is deployed as a conflict-resolution mechanism in a multi-UAV system to test applicability under realistic communication conditions.The testbed supports missions such as patrolling, target tracking, and area surveillance.
Multi-UAV Robotic Testbed
The multi-UAV testbed combines physical and simulated aircraft with onboard computation and direct UAV-to-UAV communication. Large cylindrical safety zones model trajectory-tracking uncertainty, while the radio link has limited capacity and unreliable delivery.
- Hardware and communication: The testbed consists of two hardware UAVs and an arbitrary number of simulated UAVs.Hardware aircraft use Unicorn airframes, Kestrel Autopilots, Gumstix onboard computers, and Xbee radio modules.
- Safety model: UAVs are modeled as cylindrical safety zones with 100 m radius and 10 m half-height to reflect imprecise execution in difficult wind conditions.The parameters were chosen empirically to represent autopilot trajectory-tracking precision.
- Hardware and communication: The UAV radio link provides 5 kBps shared capacity under ideal conditions, with raw data transfer and no guaranteed delivery.The communication design aims to keep latency low and use bandwidth efficiently.
Closed-Loop AD-PP
Closed-loop AD-PP adapts decentralized trajectory coordination to changing tasks, execution deviations, and communication losses during UAV missions. The deployment chooses classical PP over RPP and uses asynchronous execution because the application cannot guarantee RPP’s path conditions or synchronized termination over unreliable links.
- Deployment constraints: Real UAV deployment must handle changed goals, imprecise trajectory execution, and unreliable radio communication.These conditions complicate direct application of standard planned trajectories and coordination assumptions.
- Algorithm choice: Classical PP is selected over RPP because arbitrary replanning locations cannot guarantee the required start- and goal-avoiding paths, and PP can return shorter solutions in relevant scenarios.Neither algorithm can guarantee completeness in this application setting.
- Algorithm choice: Asynchronous AD-PP is preferred to synchronized SD-PP because unreliable communication makes distributed termination detection generally impossible.The asynchronous design also supports dynamic mission mechanisms more naturally than centralized or synchronized alternatives.
- Closed-loop AD-PP: CLAD-PP continuously monitors execution and replans when a UAV receives a new task or deviates from its planned trajectory.Forced replanning can trigger coordination queries and cascading replannings for lower-priority UAVs.
- Demonstration: A four-UAV superconflict scenario places each aircraft at a square corner with its goal at the opposite corner, producing an initial central conflict.Two UAVs are hardware-in-the-loop and two are simulated.
1 Algorithm CLAD-PP
CLAD-PP updates plans from the robot’s current position when tasks change or a robot is diverted, and reports failure when no plan is available.
- If no trajectory is available, the algorithm reports failure and terminates.
- CLAD-PP plans from the robot’s current position when its task changes or it is diverted from its trajectory.
16 Periodically
The experiment runs CLAD-PP across hardware and simulated UAVs, producing traces in which the highest-priority UAV retains its initial trajectory while others adapt.
- 16 Periodically: Hardware UAVs use a 110 m safe-zone radius, while simulated UAVs use a 70 m radius.
- 16 Periodically: The hardware and simulated UAVs run identical control software and communicate through XBee radio modules.
- 16 Periodically: During the mission, UAVs execute CLAD-PP and produce recorded traces shown in Figure 13c.
- 16 Periodically: Plane 1 retains its first straight-lane trajectory, while the other UAVs alter theirs to adapt.
VII. CONCLUSION
The paper develops revised and asynchronous decentralized prioritized-planning algorithms, establishing when they are guaranteed to work and evaluating their performance. RPP handles instances that classical prioritized planning and ORCA cannot, while the asynchronous variant converges faster than the synchronized approach in tested environments.
- VII. CONCLUSION: The paper compares six prioritized-planning algorithms, four of which are introduced as novel contributions.
- VII. CONCLUSION: RPP is guaranteed to provide a solution when each robot has a path avoiding lower-priority starts and higher-priority goals.
- VII. CONCLUSION: Valid infrastructures satisfy RPP’s condition when robots move between two endpoints, enabling coordinated-trajectory planning in such environments.
- VII. CONCLUSION: In valid infrastructures, RPP solves instances that classical prioritized planning and ORCA otherwise leave unsolved.
- VII. CONCLUSION: The asynchronous decentralized implementation terminates and has the same solution guarantee as centralized RPP under the stated conditions.
- VII. CONCLUSION: In the test environments, the asynchronous approach converges faster than the previously known synchronized approach.
- VII. CONCLUSION: Future work will extend the decentralized algorithms to open multi-robot systems with local communication.