Sven Koenig

Intelligent Decision Making
University of Southern California, USA

Title: Progress on Multi-Robot Path Finding

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 postprocess 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
replanning in many cases.

Bio: Sven Koenig is a professor in computer science at the University of Southern
California. Most of his research centers around techniques for decision making
(planning and learning) that enable single situated agents (such as robots or
decision-support systems) and teams of agents to act intelligently in their
environments and exhibit goal-directed behavior in real-time, even if they
have only incomplete knowledge of their environment, imperfect abilities to
manipulate it, limited or noisy perception or insufficient reasoning
speed. Additional information about Sven can be found on his website:

This entry was posted in Uncategorized. Bookmark the permalink.