Asynchronous Real-time Decentralized Multi-Robot Trajectory Planning

We present a novel overconstraining and constraint-discarding method for asynchronous, real-time, decentralized, multi-robot trajectory planning that ensures collision avoidance. Our approach utilizes communication between robots. The communication medium is best-effort: messages may be dropped, re-ordered or delayed. Robots conservatively constrain themselves against others assuming they may be working with outdated information, and discard constraints when they receive update messages from others. Our method can augment existing synchronized decentralized receding horizon planning algorithms that utilize separating hyperplanes for collision avoidance thereby making them applicable to asynchronous setups. As an example, we extend an existing model predictive control based, synchronized, decentralized multi-robot planner using our method. We show our method's effectiveness under asynchronous planning and imperfect communication by comparing our extension to the base version. Our extension does not result in any collisions or synchronization-induced deadlocks to which the base version is prone.

Authors

• Baskin Senbaslar
• Gaurav S. Sukhatme

Keywords

• Trajectory planning
• System recovery
• Prediction algorithms
• Real-time systems
• Planning
• Trajectory
• Synchronization
• Media Communication
• Model Predictive Control
• Deadlock
• Planning Algorithm
• Support Vector Machine
• End Time
• Commutative
• Effective Planning
• Voronoi Diagram
• Communication Delay
• Position Of The Robot
• Makespan
• Hypersphere
• Reactive Approach
• Average Metrics
• Robot State
• Swarm Robotics
• Goal Position
• Planning Of Robots
• Current Timestamp
• Bezier Curve
• Central Entity
• Velocity Commands
• Timing Mismatch
• Quadratic Programming
• Communication Network
• Discretion
• Robot Trajectory