This is a promotion video for the cooperative path-finding project. Watch agents moving on Michael Jackson's "They Don't Care About Us" !

Movements of agents were planned by the BIBOX algorithm developed in 2009 (see Publications section). It is a complete polynomial-time algorithm for cooperative path-finding over bi-connected graphs. The video was recorded on 9 cameras in the HD resolution by the Graphrec tool.

Agents move into the unoccupied position only in the prelude. In the main motif, movements were post-processed by the critical-path method (also similar to Bellman-Ford algorithm) so agents move in parallel if possible. This mode allows an agent entering a position being simultaneously vacated by another agent which enables to reduce the makespan significantly.

Our Most Relevant Publications to CPF

If you want to refer to our work on cooperative-path plannig please cite some of the following works. Publications are ordered according to our perception of their importance. The most important works are on the top. See commentary of each publication.

This is our first work on the topic of cooperative-path planning. The BIBOX algorithm in its basic version is introduced in the work.

A Novel Approach to Path Planning for Multiple Robots in Bi-connected Graphs Pavel Surynek. Proceedings of the 2009 IEEE International Conference on Robotics and Automation (ICRA 2009), Kobe, Japan, pp. 3613-3619, IEEE Press, 2009, ISBN 978-1-4244-2789-5, ISSN 1050-4729.

[ full text  | full text  | presentation  | digest  ]

In this work, NP-completeness of parallel variant of cooperative path-planning is shown.

An Optimization Variant of Multi-Robot Path Planning is Intractable Pavel Surynek. Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI 2010), Atlanta, GA, USA, pp. 1261-1263, AAAI Press, 2010, ISBN 978-1-57735-463-5.

[ full text  | full text  | poster  ]

Result obtained in the algebraic approach to problems of pebble motion on graphs are applied in cooperative path-planning.

An Application of Pebble Motion on Graphs to Abstract Multi-robot Path Planning Pavel Surynek. Proceedings of the 21st International Conference on Tools with Artificial Intelligence (ICTAI 2009), Newark, NJ, USA, pp. 151-158, IEEE Press, 2009, ISBN 978-0-7695-3920-1, ISSN 1082-3409.

[ full text  | full text  | presentation  ]

In this article, we study how to improve makespan sub-optimal solutions of cooperative path-planning problems towards the shorter makespan.

Redundancy Elimination in Highly Parallel Solutions of Motion Coordination Problems Pavel Surynek. Proceedings of the 23rd IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2011), Boca Raton, FL, USA, pp. 701-708, IEEE Press, 2011, ISBN 978-0-7695-4596-7, ISSN 1082-3409.

[ full text  | full text  | presentation  ]