Koenig, Sven


Multi-Agent Path Finding with Deadlines

arXiv.org Artificial Intelligence

We formalize Multi-Agent Path Finding with Deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within the deadline, without colliding with each other. We first show that MAPF-DL is NP-hard to solve optimally. We then present two classes of optimal algorithms, one based on a reduction of MAPF-DL to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network and the other one based on novel combinatorial search algorithms. Our empirical results demonstrate that these MAPF-DL solvers scale well and each one dominates the other ones in different scenarios.


Multi-Agent Path Finding with Deadlines: Preliminary Results

arXiv.org Artificial Intelligence

We formalize the problem of multi-agent path finding with deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within a given deadline, without colliding with each other. We first show that the MAPF-DL problem is NP-hard to solve optimally. We then present an optimal MAPF-DL algorithm based on a reduction of the MAPF-DL problem to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network.


The FastMap Algorithm for Shortest Path Computations

arXiv.org Artificial Intelligence

We present a new preprocessing algorithm for embedding the nodes of a given edge-weighted undirected graph into a Euclidean space. The Euclidean distance between any two nodes in this space approximates the length of the shortest path between them in the given graph. Later, at runtime, a shortest path between any two nodes can be computed with A* search using the Euclidean distances as heuristic. Our preprocessing algorithm, called FastMap, is inspired by the data mining algorithm of the same name and runs in near-linear time. Hence, FastMap is orders of magnitude faster than competing approaches that produce a Euclidean embedding using Semidefinite Programming. FastMap also produces admissible and consistent heuristics and therefore guarantees the generation of shortest paths. Moreover, FastMap applies to general undirected graphs for which many traditional heuristics, such as the Manhattan Distance heuristic, are not well defined. Empirically, we demonstrate that A* search using the FastMap heuristic is competitive with A* search using other state-of-the-art heuristics, such as the Differential heuristic.


Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments

AAAI Conferences

Multi-agent path finding (MAPF) is a well-studied problem in artificial intelligence, where one needs to find collision-free paths for agents with given start and goal locations. In video games, agents of different types often form teams. In this paper, we demonstrate the usefulness of MAPFalgorithms from artificial intelligence for moving such non-homogeneous teams in congested video game environments.



Multi-Agent Path Finding with Delay Probabilities

AAAI Conferences

Several recently developed Multi-Agent Path Finding (MAPF) solvers scale to large MAPF instances by searching for MAPF plans on 2 levels: The high-level search resolves collisions between agents, and the low-level search plans paths for single agents under the constraints imposed by the high-level search. We make the following contributions to solve the MAPF problem with imperfect plan execution with small average makespans: First, we formalize the MAPF Problem with Delay Probabilities (MAPF-DP), define valid MAPF-DP plans and propose the use of robust plan-execution policies for valid MAPF-DP plans to control how each agent proceeds along its path. Second, we discuss 2 classes of decentralized robust plan-execution policies (called Fully Synchronized Policies and Minimal Communication Policies) that prevent collisions during plan execution for valid MAPF-DP plans. Third, we present a 2-level MAPF-DP solver (called Approximate Minimization in Expectation) that generates valid MAPF-DP plans.


Robot Planning in the Real World: Research Challenges and Opportunities

AI Magazine

Recent years have seen significant technical progress on robot planning, enabling robots to compute actions and motions to accomplish challenging tasks involving driving, flying, walking, or manipulating objects. However, robots that have been commercially deployed in the real world typically have no or minimal planning capability. Although these robots are highly successful in their respective niches, a lack of planning capabilities limits the range of tasks for which currently deployed robots can be used. In this article, we highlight key conclusions from a workshop sponsored by the National Science Foundation in October 2013 that summarize opportunities and key challenges in robot planning and include challenge problems identified in the workshop that can help guide future research towards making robot planning more deployable in the real world.


Robot Planning in the Real World: Research Challenges and Opportunities

AI Magazine

Recent years have seen significant technical progress on robot planning, enabling robots to compute actions and motions to accomplish challenging tasks involving driving, flying, walking, or manipulating objects. However, robots that have been commercially deployed in the real world typically have no or minimal planning capability. These robots are often manually programmed, teleoperated, or programmed to follow simple rules. Although these robots are highly successful in their respective niches, a lack of planning capabilities limits the range of tasks for which currently deployed robots can be used. In this article, we highlight key conclusions from a workshop sponsored by the National Science Foundation in October 2013 that summarize opportunities and key challenges in robot planning and include challenge problems identified in the workshop that can help guide future research towards making robot planning more deployable in the real world.


Multi-Agent Path Finding with Kinematic Constraints

AAAI Conferences

Multi-Agent Path Finding (MAPF) is well studied in both AI and robotics. Given a discretized environment and agents with assigned start and goal locations, MAPF solvers from AI find collision-free paths for hundreds of agents with user-provided sub-optimality guarantees. However, they ignore that actual robots are subject to kinematic constraints (such as finite maximum velocity limits) and suffer from imperfect plan-execution capabilities. We therefore introduce MAPF-POST, a novel approach that makes use of a simple temporal network to postprocess the output of a MAPF solver in polynomial time to create a plan-execution schedule that can be executed on robots. This schedule works on non-holonomic robots, takes their maximum translational and rotational velocities 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. We evaluate MAPF-POST in simulation and on differential-drive robots, showcasing the practicality of our approach.


Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem

AAAI Conferences

We study transportation problems where robots have to deliver packages and can transfer the packages among each other. Specifically, we study the package-exchange robot-routing problem (PERR), where each robot carries one package, any two robots in adjacent locations can exchange their packages, and each package needs to be delivered to a given destination. We prove that exchange operations make all PERR instances solvable. Yet, we also show that PERR is NP-hard to approximate within any factor less than 4/3 for makespan minimization and is NP-hard to solve for flowtime minimization, even when there are only two types of packages. Our proof techniques also generate new insights into other transportation problems, for example, into the hardness of approximating optimal solutions to the standard multi-agent path-finding problem (MAPF). Finally, we present optimal and suboptimal PERR solvers that are inspired by MAPF solvers, namely a flow-based ILP formulation and an adaptation of conflict-based search. Our empirical results demonstrate that these solvers scale well and that PERR instances often have smaller makespans and flowtimes than the corresponding MAPF instances.