Glenn Wagner

JAIR Journal 2020 Journal Article

Robust Multi-Agent Path Finding and Executing

• Dor Atzmon
• Roni Stern
• Ariel Felner
• Glenn Wagner
• Roman Barták
• Neng-Fa Zhou

Multi-agent path-finding (MAPF) is the problem of finding a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. In this work, we propose a holistic solution for MAPF that is robust to such unexpected delays. First, we introduce the notion of a k-robust MAPF plan, which is a plan that can be executed even if a limited number (k) of delays occur. We propose sufficient and required conditions for finding a k-robust plan, and show how to convert several MAPF solvers to find such plans. Then, we propose several robust execution policies. An execution policy is a policy for agents executing a MAPF plan. An execution policy is robust if following it guarantees that the agents reach their goals even if they encounter unexpected delays. Several classes of such robust execution policies are proposed and evaluated experimentally. Finally, we present robust execution policies for cases where communication between the agents may also be delayed. We performed an extensive experimental evaluation in which we compared different algorithms for finding robust MAPF plans, compared different ro- bust execution policies, and studied the interplay between having a robust plan and the performance when using a robust execution policy.

IJCAI Conference 2018 Conference Paper

Multi-Agent Path Finding with Deadlines

• Hang Ma
• Glenn Wagner
• Ariel Felner
• Jiaoyang Li
• T. K. Satish Kumar
• Sven Koenig

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.

AAMAS Conference 2018 Conference Paper

Multi-Agent Path Finding with Deadlines: Preliminary Results

• Hang Ma
• Glenn Wagner
• Ariel Felner
• Jiaoyang Li
• T. K. Satish Kumar
• Sven Koenig

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.

SoCS Conference 2018 Conference Paper

Rapid Randomized Restarts for Multi-Agent Path Finding Solvers

• Liron Cohen 0002
• Glenn Wagner
• David M. Chan
• Howie Choset
• Nathan R. Sturtevant
• Sven Koenig
• T. K. Satish Kumar

Multi-Agent Path Finding (MAPF) is an NP-hard problem that has been well studied in artificial intelligence and robotics. Recently, randomized MAPF solvers have been shown to exhibit heavy-tailed distributions of runtimes, which can be exploited to boost their success rate for a given runtime limit. In this paper, we discuss different ways of randomizing MAPF solvers and evaluate simple rapid randomized restart strategies for state-of-the-art MAPF solvers such as iECBS, M* with highways and CBS-CL.

AAMAS Conference 2018 Conference Paper

Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results

• Liron Cohen
• Sven Koenig
• T. K. Satish Kumar
• Glenn Wagner
• Howie Choset
• David Chan
• Nathan Sturtevant

Multi-Agent Path Finding (MAPF) is an NP-hard problem with many real-world applications. However, existing MAPF solvers are deterministic and perform poorly on MAPF instances where many agents interfere with each other in a small region of space. In this paper, we enhance MAPF solvers with randomization and observe that their runtimes can exhibit heavy-tailed distributions. This insight leads us to develop simple Rapid Randomized Restart (RRR) strategies with the intuition that multiple short runs will have a better chance of solving such MAPF instances than one long run with the same runtime limit. Our contribution is to show experimentally that the same RRR strategy indeed boosts the performance of two state-of-the-art MAPF solvers, namely M* and ECBS.

SoCS Conference 2018 Conference Paper

Robust Multi-Agent Path Finding

• Dor Atzmon
• Roni Stern
• Ariel Felner
• Glenn Wagner
• Roman Barták
• Neng-Fa Zhou

In the multi-agent path-finding (MAPF) problem, the task is to find a plan for moving a set of agents from their initial locations to their goals without collisions. Following this plan, however, may not be possible due to unexpected events that delay some of the agents. We explore the notion of k-robust MAPF, where the task is to find a plan that can be followed even if a limited number of such delays occur. k-robust MAPF is especially suitable for agents with a control mechanism that guarantees that each agent is within a limited number of steps away from its pre-defined plan. We propose sufficient and required conditions for finding a k-robust plan, and show how to convert several MAPF solvers to find such plans. Then, we show the benefit of using a k-robust plan during execution, and for finding plans that are likely to succeed.

AAMAS Conference 2018 Conference Paper

Robust Multi-Agent Path Finding

• Dor Atzmon
• Roni Stern
• Ariel Felner
• Glenn Wagner
• Roman Bart�k
• Neng-Fa Zhou

SoCS Conference 2017 Conference Paper

k-Robust Multi-Agent Path Finding

• Dor Atzmon
• Ariel Felner
• Roni Stern
• Glenn Wagner
• Roman Barták
• Neng-Fa Zhou

In the multi-agent path-finding (MAPF) problem a plan is needed to move a set of agents from their initial location to their goals without collisions. In this paper we introduce and study the k-robust MAPF problem, where we seek a plan that is robust to k unexpected delays per agent.

ICAPS Conference 2017 Conference Paper

Path Planning for Multiple Agents under Uncertainty

• Glenn Wagner
• Howie Choset

Multi-agent systems in cluttered environments require path planning that not only prevents collisions with static obstacles, but also safely coordinates the motion of many agents. The challenge of multi-agent path finding becomes even more difficult when the agents experience uncertainty in their pose. In this work, we develop a multi-agent path planner that considers uncertainty, called uncertainty M* (UM*), which is based on a prior multi-agent path approach called M*. UM* plans a path through the belief space for each individual agent and then uses a strategy similar to M* that coordinates only agents that are “likely” to collide. This approach has the same scalability advantages as M*. We then introduce an extension called Permuted UM* (PUM*) that uses randomized restarts to enhance performance. We finish by presenting a belief space representation appropriate for multi-agent path planning with uncertainty and validate the performance of UM* and PUM* in simulation and mixed-reality experiments.

SoCS Conference 2017 Conference Paper

Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges

• Ariel Felner
• Roni Stern
• Solomon Eyal Shimony
• Eli Boyarski
• Meir Goldenberg
• Guni Sharon
• Nathan R. Sturtevant
• Glenn Wagner

Multi-agent pathfinding (MAPF) is an area of expanding research interest. At the core of this research area, numerous diverse search-based techniques were developed in the past 6 years for optimally solving MAPF under the sum-of-costs objective function. In this paper we survey these techniques, while placing them into the wider context of the MAPF field of research. Finally, we provide analytical and experimental comparisons that show that no algorithm dominates all others in all circumstances. We conclude by listing important future research directions.

IROS Conference 2016 Conference Paper

Multirobot sequential composition

• Glenn Wagner
• Howie Choset
• Avinash Siravuru

Conventional path planning algorithms compute a single path through the configuration space. There is no guarantee that a physical robot will be able to track the trajectory while avoiding collisions, particularly in the presence of environmental perturbations and errors in the process model. Sequential composition combines planning and control by computing a sequence of controllers to execute rather than a single trajectory, offering greater safety guarantees. In this paper, we apply sequential composition to multirobot systems in a scalable fashion using M*, an advanced multirobot path planning algorithm. Controllers will vary in size and geometry, and thus take different amounts of time to execute. To handle these differences, we introduce the time augmented joint prepares graph and the approximate time augmented joint prepares graph which simplifies implementation by discretizing time. We validate our approach in a mixed reality test framework.

SoCS Conference 2016 Conference Paper

Recursive Constraint Manifold Subsearch for Multirobot Path Planning with Cooperative Tasks

• Péter Karkus
• Glenn Wagner
• Howie Choset

The Cooperative Path Planning (CPP) problem seeks to determine a path for a group of robots which form temporary teams to perform tasks. The multi-scale effects of simultaneously coordinating many robots distributed across the workspace while also tightly coordinating the members of teams increases the difficulty of planning. Previous research produced the Constraint Manifold Subsearch (CMS) algorithm that can find minimal length paths to the CPP problem. However, CMS as currently formulated cannot handle more general cost functions, such as minimizing energy expenditure, and cannot handle task schedules that require multiple input teams to merge to form a set of multiple output teams. Furthermore, as CMS must couple planning for all interacting teams, it does not scale well to very large environments. In this paper, we rederive the CMS algorithm using a task graph to reason about inter-team dependencies, allowing the use of more general cost functions and task schedules. We then introduce the recursive CMS (rCMS) algorithm that exploits the reformulation to split the CPP into independent subproblems, significantly reducing computational complexity. Simulation studies show that rCMS can solve substantially larger problems than CMS.

ICRA Conference 2015 Conference Paper

Constraint Manifold Subsearch for multirobot path planning with cooperative tasks

• Glenn Wagner
• Jae-il Kim
• Konrad Urban
• Howie Choset

The cooperative path planning problem seeks to determine a path for a group of robots which form temporary teams to perform tasks that require multiple robots. The multi-scale effects of simultaneously coordinating many robots distributed across the workspace while also tightly coordinating robots in cooperative teams increases the difficulty of planning. This paper describes a new approach to cooperative path planning called Constraint Manifold Subsearch (CMS). CMS builds upon M*, a high performance multirobot path planning algorithm, by modifying the search space to restrict teams of robots performing a task to the constraint manifold of the task. CMS can find optimal solutions to the cooperative path planning problem, or near optimal solutions to problems involving large numbers of robots.

ICRA Conference 2015 Conference Paper

Gaussian reconstruction of swarm behavior from partial data

• Glenn Wagner
• Howie Choset

Swarms consist of large numbers of individual agents that generally maintain no fixed relative positions, which makes describing the behavior of the swarm as a whole difficult. Furthermore, the high number of agents leads to frequent occlusions that prevent observations of the entire swarm. In this paper, we represent the behavior of swarms using velocity fields, yielding a description which is invariant to the number of agents in a swarm, and the position, orientation, and scale of the swarm. The velocity field representation allows the behavior of swarms to be modeled as a Gaussian distribution. We demonstrate that this Gaussian model can be used to reconstruct the behavior of the swarm as a whole from partial observations.

AIJ Journal 2015 Journal Article

Subdimensional expansion for multirobot path planning

• Glenn Wagner
• Howie Choset

ICRA Conference 2013 Conference Paper

ODrM* optimal multirobot path planning in low dimensional search spaces

• Cornelia Ferner
• Glenn Wagner
• Howie Choset

We believe the core of handling the complexity of coordinated multiagent search lies in identifying which subsets of robots can be safely decoupled, and hence planned for in a lower dimensional space. Our work, as well as those of others take that perspective. In our prior work, we introduced an approach called subdimensional expansion for constructing low-dimensional but sufficient search spaces for multirobot path planning, and an implementation for graph search called M*. Subdimensional expansion dynamically increases the dimensionality of the search space in regions featuring significant robot-robot interactions. In this paper, we integrate M* with Meta-Agent Constraint-Based Search (MA-CBS), a planning framework that seeks to couple repeatedly colliding robots allowing for other robots to be planned in low-dimensional search space. M* is also integrated with operator decomposition (OD), an A*-variant performing lazy search of the outneighbors of a given vertex. We show that the combined algorithm demonstrates state of the art performance.

ICRA Conference 2012 Conference Paper

Probabilistic path planning for multiple robots with subdimensional expansion

• Glenn Wagner
• Minsu Kang
• Howie Choset

Probabilistic planners such as Rapidly-Exploring Random Trees (RRTs) and Probabilistic Roadmaps (PRMs) are powerful path planning algorithms for high dimensional systems, but even these potent techniques suffer from the curse of dimensionality, as can be seen in multirobot systems. In this paper, we apply a technique called subdimensional expansion in order to enhance the performance of probabilistic planners for multirobot path planning. We accomplish this by exploiting the structure inherent to such problems. Subdimensional expansion initially plans in each individual robot's configuration space separately. It then couples those spaces when robots come into close proximity with one another. In this way, we constrain a probabilistic planner to search a low dimensional space, while dynamically generating a higher dimensional space where necessary. We show in simulation that subdimensional expansion enhanced PRMs can solve problems involving 32 robots and 128 total degrees of freedom in less than 10 minutes. We also demonstrate that enhancing RRTs and PRMs with subdimensional expansion can decrease the time required to find a solution by more than an order of magnitude.

SoCS Conference 2012 Conference Paper

Subdimensional Expansion and Optimal Task Reassignment

• Glenn Wagner
• Howie Choset
• Nora Ayanian

Multirobot path planning and task assignment are traditionally treated separately, however task assignment can greatly impact the difficulty of the path planning problem, and the ultimate quality of solution is dependent upon both. We introduce task reassignment, an approach to optimally solving the coupled task assignment and path planning problems. We show that task reassignment improves solution quality, and reduces planning time in some situations.

IROS Conference 2011 Conference Paper

M*: A complete multirobot path planning algorithm with performance bounds

• Glenn Wagner
• Howie Choset

Multirobot path planning is difficult because the full configuration space of the system grows exponentially with the number of robots. Planning in the joint configuration space of a set of robots is only necessary if they are strongly coupled, which is often not true if the robots are well separated in the workspace. Therefore, we initially plan for each robot separately, and only couple sets of robots after they have been found to interact, thus minimizing the dimensionality of the search space. We present a general strategy called subdimensional expansion, which dynamically generates low dimensional search spaces embedded in the full configuration space. We also present an implementation of subdimensional expansion for robot configuration spaces that can be represented as a graph, called M*, and show that M* is complete and finds minimal cost paths.