Data Driven Online Multi-Robot Formation Planning

This work addresses planning for multi-robot formations online in cluttered environments via a data-driven search approach. The user-specified objective function governing formation shape and rotation is expressed in terms of offline demonstrations of robot motions (performed in an obstacle free environment). We leverage the offline demonstration to inform online planning for coordinated motions in the presence of obstacles. We formulate planning as a discrete search over demonstrated multi-robot actions, and select actions using a best-first approach to minimize edge expansions for fast online operation. Actions are selected using a heuristic based on their probability distribution exhibited in the demonstration, and we show that this approach is able to recreate coordinated motions exhibited in the demonstration when navigating in the obstructed conditions of the cluttered test environments. We demonstrate results in simulation over environments with increasing numbers of obstacles, and show that resulting plans are collision free and obey dynamic constraints.

Authors

• Ellen A. Cappo
• Arjav Desai
• Nathan Michael

Keywords

• Robot motion
• Shape
• Navigation
• Linear programming
• Probability distribution
• Planning
• Intelligent robots
• Multi-robot Formation
• Collision
• Objective Function
• Search Approach
• Online Operation
• Discretion
• Singular Value
• Kullback-Leibler
• State Components
• User Input
• Markov Decision Process
• Hamming Distance
• Tree Search
• Representation Of The Environment
• Rotated Component
• String Length
• Graph Size
• Jensen-Shannon Divergence
• Robot State
• Robotic Group
• State St