Robohub.org
 

Sven Koenig: Progress on Multi-Robot Path Finding | CMU RI Seminar


by
10 September 2017



share this:

Link to video on YouTube

Abstract: “Teams of robots often have to assign target locations among themselves and then plan collision-free paths to their target locations. Examples include autonomous aircraft towing vehicles and automated warehouse systems. For example, in the near future, autonomous aircraft towing vehicles might tow aircraft all the way from the runways to their gates (and vice versa), thereby reducing pollution, energy consumption, congestion and human workload. Today, hundreds of robots already navigate autonomously in Amazon fulfillment centers to move inventory pods all the way from their storage locations to the packing stations. Path planning for these robots can be NP-hard, yet one must find high-quality collision-free paths for them in real-time. The shorter these paths are, the fewer robots are needed and the cheaper it is to open new fulfillment centers. In this talk, I describe several variants of the multi-robot path-planning problem, their complexities and algorithms for solving them. I also present a hierarchical planning architecture that combines ideas from artificial intelligence and robotics. It makes use of a simple temporal network to post-process the output of a multi-robot path-finding algorithm in polynomial time to create a plan-execution schedule that take the maximum translational and rotational velocities of non-holonomic robots into account, provides a guaranteed safety distance between them, and exploits slack to absorb imperfect plan executions and avoid time-intensive re-planning in many cases. This research is joint research with N. Ayanian, T. Cai, L. Cohen, W. Hoenig, S. Kumar, H. Ma, G. Sharon, C. Tovey, T. Uras, H. Xu, S. Young, D. Zhang, and other colleagues and students.”




John Payne

            AUAI is supported by:



Subscribe to Robohub newsletter on substack



Related posts :

Robot swarms trained by trial and error in simulation keep working on real robots

  17 Nov 2026
Researchers have developed a new approach to reinforcement learning that helps robot swarms, allowing behaviours learned in simulation to transfer reliably to real-world robots.

Watch the IROS 2026 plenary and keynote talks

  16 Nov 2026
Catch up on the invited presentations from the International Conference on Intelligent Robots and Systems.

Robot Talk Episode 170 – Robots in the real world, with Daniela Shchegelskaya

  13 Nov 2026
In the latest episode of the Robot Talk podcast, Claire chatted to Daniela Shchegelskaya from the University of Twente about getting robots to operate reliably in safety-critical environments.

AI100 report released: embodied AI highlighted as grand challenge

  11 Nov 2026
Embodied AI is listed as one of the most inspiring open grand challenges.

AIhub coffee corner: Are humanoids the future of embodied AI?

  09 Nov 2026
The AIhub coffee corner captures the musings of AI experts over a short conversation.

Robot Talk Episode 169 – Robot sensing inspired by nature, with Dexter Shepherd

  06 Nov 2026
In the latest episode of the Robot Talk podcast, Claire chatted to Dexter Shepherd from the University of Sussex about using artificial intelligence to help robots understand and adapt to their environment.

Robots in society, business and culture: October 2026

We showcase a selection of robotics stories from society, business, research and culture.

Muscle coordination can be mimicked by electric motors – it could lead to improved robots

  02 Nov 2026
Researchers built a physical model using ordinary electric motors to try and simulate how muscles may perform tasks.


↑


AUAI is supported by:







Subscribe to Robohub newsletter on substack




 















©2026.05 - Association for the Understanding of Artificial Intelligence