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

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

Related posts :

At the forefront of building with biology

Raman is, as she puts it, “a mechanical engineer through and through.” Today, Ritu Raman leads the Raman Lab and is an Assistant Professor in the Department of Mechanical Engineering.
28 June 2022, by

Hot Robotics Symposium celebrates UK success

An internationally leading robotics initiative that enables academia and industry to find innovative solutions to real world challenges, celebrated its success with a Hot Robotics Symposium hosted across three UK regions last week.
25 June 2022, by

Researchers release open-source photorealistic simulator for autonomous driving

MIT scientists unveil the first open-source simulation engine capable of constructing realistic environments for deployable training and testing of autonomous vehicles.
22 June 2022, by

In this episode, Audrow Nash speaks to Maria Telleria, who is a co-founder and the CTO of Canvas. Canvas makes a drywall finishing robot and is based in the Bay Area. In this interview, Maria talks ab...
21 June 2022, by and

Coffee with a Researcher (#ICRA2022)

As part of her role as one of the IEEE ICRA 2022 Science Communication Awardees, Avie Ravendran sat down virtually with a few researchers from academia and industry attending the conference.

Seeing the robots at #ICRA2022 through the eyes of a robot

Accessbility@ICRA2022 and OhmniLabs provided three OhmniBots for the conference, allowing students, faculty and interested industry members to attend the expo and poster sessions.
17 June 2022, by

©2021 - ROBOTS Association


©2021 - ROBOTS Association