" } @INPROCEEDINGS{Koen21b, AUTHOR= "J. Li and A. Tinka and S. Kiesel and J. Durham and S. Kumar and S. Koenig", TITLE= "Lifelong Multi-Agent Path Finding in Large-Scale Warehouses", BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)", PAGES= "11272--11281", YEAR= "2021", PDF= "http://idm-lab.org/bib/abstracts/papers/aaai21b.pdf", FLAGS= ":2021:,:jiaoyangli:,:svenkoenig:", ABSTRACT= "Multi-Agent Path Finding (MAPF) is the problem of moving a team of agents to their goal locations without collisions. In this paper, we study the lifelong variant of MAPF, where agents are constantly engaged with new goal locations, such as in large-scale automated warehouses. We propose a new framework Rolling-Horizon Collision Resolution (RHCR) for solving lifelong MAPF by decomposing the problem into a sequence of Windowed MAPF instances, where a Windowed MAPF solver resolves collisions among the paths of the agents only within a bounded time horizon and ignores collisions beyond it. RHCR is particularly well suited to generating pliable plans that adapt to continually arriving new goal locations. We empirically evaluate RHCR with a variety of MAPF solvers and show that it can produce high-quality solutions for up to 1,000 agents for simulated warehouse instances, significantly outperforming existing work.

" } @INPROCEEDINGS{Koen21c, AUTHOR= "T. Huang and S. Koenig and B. Dilkina", TITLE= "Learning to Resolve Conflicts for Multi-Agent Path Finding with Conflict-Based Search", BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)", PAGES= "11246--11253", YEAR= "2021", PDF= "http://idm-lab.org/bib/abstracts/papers/aaai21c.pdf", FLAGS= ":2021:,:taoanhuang:,:svenkoenig:,:bistradilkina:", ABSTRACT= "Conflict-Based Search (CBS) is a state-of-the-art algorithm for multi-agent path finding. On the high level, CBS repeatedly detects conflicts and resolves one of them by splitting the current problem into two subproblems. Previous work chooses the conflict to resolve by categorizing conflicts into three classes and always picking one from the highest-priority class. In this work, we propose an oracle for conflict selection that results in smaller search tree sizes than the one used in previous work. However, the computation of the oracle is slow. Thus, we propose a machine-learning (ML) framework for conflict selection that observes the decisions made by the oracle and learns a conflict-selection strategy represented by a linear ranking function that imitates the oracle's decisions accurately and quickly. Experiments on benchmark maps indicate that our approach, ML-guided CBS, significantly improves the success rates, search tree sizes and runtimes of the current state-of-the-art CBS solver." } @INPROCEEDINGS{Koen21f, AUTHOR= "E. Boyarski and A. Felner and P. Le Bodic and D. Harabor and P. Stuckey and S. Koenig", TITLE= "f-Aware Conflict Prioritization & Improved Heuristics for Conflict-Based Search", BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)", PAGES= "12241--12248", YEAR= "2021", PDF= "http://idm-lab.org/bib/abstracts/papers/aaai21d.pdf", FLAGS= ":2021:,:eliboyarski:,:arielfelner:,:pierrelebodic:,:danielharabor:,:peterstuckey:,:svenkoenig:", ABSTRACT= "Conflict-Based Search (CBS) is a leading two-level algorithm for optimal Multi-Agent Path Finding (MAPF). The main step of CBS is to expand nodes by resolving conflicts (where two agents collide). Choosing the `right' conflict to resolve can greatly speed up the search. CBS first resolves conflicts where the costs (g-values) of the resulting child nodes are larger than the cost of the node to be split. However, the recent addition of high-level heuristics to CBS and expanding nodes according to f=g+h reduces the relevance of this conflict prioritization method. Therefore, we introduce an expanded categorization of conflicts, which first resolves conflicts where the f-values of the child nodes are larger than the f-value of the node to be split, and present a method for identifying such conflicts. We also enhance all known heuristics for CBS by using information about the cost of resolving certain conflicts with only a small computational overhead. Finally, we experimentally demonstrate that both the expanded categorization of conflicts and the improved heuristics contribute to making CBS even more efficient." } @INPROCEEDINGS{Koen21e, AUTHOR= "T. Huang and B. Dilkina and S. Koenig", TITLE= "Learning Node-Selection Strategies in Bounded-Suboptimal Conflict-Based Search for Multi-Agent Path Finding", BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)", PAGES= "611--619", YEAR= "2021", PDF= "http://idm-lab.org/bib/abstracts/papers/aamas21b.pdf", FLAGS= ":2021:,:taoanhuang:,:bistradilkina:,:svenkoenig:", ABSTRACT= "Multi-Agent Path Finding (MAPF) is an NP-hard problem that has important applications for distribution centers, traffic management and computer games, and it is still difficult for current solvers to solve large instances optimally. Bounded suboptimal solvers, such as Enhanced Conflict-Based Search (ECBS) and its variants, are more efficient than optimal solvers in finding a solution with suboptimality guarantees. ECBS is a tree search algorithm that expands the search tree by repeatedly selecting search tree nodes from a focal list. In this work, we propose to use machine learning (ML) to learn a node-selection strategy to speed up ECBS. In the first phase of our framework, we use imitation learning and curriculum learning to learn node-selection strategies iteratively for different numbers of agents from training instances. In the second phase, we deploy the learned models in ECBS and test their solving performance on unseen instances drawn from the same distribution as the training instances. We demonstrate that our solver, ECBS+ML, shows substantial improvement in terms of the success rates and runtimes over ECBS on five different types of grid maps from the MAPF benchmark." } @INPROCEEDINGS{Koen21h, AUTHOR= "J. Li and Z. Chen and Y. Zheng and S.-H. Chan and D. Harabor and P. Stuckey and H. Ma and S. Koenig", TITLE= "Scalable Rail Planning and Replanning: Winning the 2020 Flatland Challenge", BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)", PAGES= "477--485", YEAR= "2021", PDF= "http://idm-lab.org/bib/abstracts/papers/icaps21a.pdf", FLAGS= ":2021:,:jiaoyangli:,:zhechen:,:yizheng:,:shaohungchan:,:danielharabor:,:peterstuckey:,:hangma:,:svenkoenig:", ABSTRACT= "Multi-Agent Path Finding (MAPF) is the combinatorial problem of finding collision-free paths for multiple agents on a graph. This paper describes MAPF-based software for solving train planning and replanning problems on large-scale rail networks under uncertainty. The software recently won the 2020 Flatland Challenge, a NeurIPS competition trying to determine how to efficiently manage dense traffic on rail networks. The software incorporates many state-of-the-art MAPF or, in general, optimization technologies, such as prioritized planning, large neighborhood search, safe interval path planning, minimum communication policies, parallel computing, and simulated annealing. It can plan collision-free paths for thousands of trains within a few minutes and deliver deadlock-free actions in real-time during execution.

For more information on winning the Flatland competition, see our overview page.

" } @INPROCEEDINGS{Koen21o, AUTHOR= "S.-H. Chan and J. Li and G. Gange and D. Harabor and P. Stuckey and S. Koenig", TITLE= "ECBS with Flex Distribution for Bounded-Suboptimal Multi-Agent Path Finding [Abstract]", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", PAGES= "159--161", YEAR= "2021", FLAGS= ":2021:,:shaohungchan:,:jiaoyanli:,:graemegange:,:danielharabor:,:peterstuckey:,:svenkoenig:", PDF= "http://idm-lab.org/bib/abstracts/papers/socs21c.pdf", ABSTRACT= "Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents. CBS is a leading optimal two-level MAPF solver whose low level plans optimal paths for single agents and whose high level runs a best-first search on a Constraint Tree (CT) to resolve the collisions between the paths. ECBS, a bounded-suboptimal variant of CBS, speeds up CBS by reducing the number of collisions that need to be resolved on the high level. It achieves this by generating bounded-suboptimal paths with fewer collisions with the paths of the other agents on the low level and expanding bounded-suboptimal CT nodes that contain fewer collisions on the high level. In this paper, we propose Flexible ECBS (FECBS) that further reduces the number of collisions that need to be resolved on the high level by using looser suboptimal bounds on the low level while still providing bounded-suboptimal solutions. Instead of requiring the cost of each path to be bounded-suboptimal, FECBS requires only the overall cost of the paths to be bounded-suboptimal, which gives us the freedom to distribute the cost leeway among different agents according to their needs. Our empirical results show that FECBS can solve more MAPF instances than state-of-the-art ECBS variants within 5 minutes." } @INPROCEEDINGS{Koen21n, AUTHOR= "H. Zhang and M. Yao and Z. Liu and J. Li and L. Terr and S.-H. Chan and S. Kumar and S. Koenig", TITLE= "A Hierarchical Approach to Multi-Agent Path Finding [Abstract]", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", PAGES= "209--211", YEAR= "2021", FLAGS= ":2021:,:hanzhang:,:jiaoyangli:,:shaohungchan:,:satishkumar:,:svenkoenig:", PDF= "http://idm-lab.org/bib/abstracts/papers/socs21c.pdf", ABSTRACT= "Solving Multi-Agent Path Finding (MAPF) instances optimally is NP-hard, and existing optimal and bounded suboptimal MAPF solvers thus usually do not scale to large MAPF instances. Greedy MAPF solvers scale to large MAPF instances, but their solution qualities are often bad. In this paper, we therefore propose a novel MAPF solver, Hierarchical Multi-Agent Path Planner (HMAPP), which creates a spatial hierarchy by partitioning the environment into multip le regions and decomposes a MAPF instance into smaller MAPF sub-instances for each region. For each sub-instance, it uses a bounded-suboptimal MAPF solver to solve it with good solution quality. Our experimental results show that HMAPP is able to solve as large MAPF instances as greedy MAPF solvers while achieving better solution qualities on various maps." } @INPROCEEDINGS{Koen21m, AUTHOR= "E. Boyarski and A. Felner and P. Le Bodic and D. Harabor and P. Stuckey and S. Koenig", TITLE= "Further Improved Heuristics for Conflict-Based Search [Doctoral Dissertation Abstract]", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", PAGES= "213--215", YEAR= "2021", FLAGS= ":2021:,:eliboyarski:,:arielfelner:,:pierrelebodic:,:danielharabor:,:peterstuckey:,:svenkoenig:", PDF= "http://idm-lab.org/bib/abstracts/papers/socs21d.pdf", ABSTRACT= "N/A" } @ARTICLE{GSart21a, AUTHOR= "M. Damani and Z. Luo and E. Wenzel and G. Sartoretti", TITLE= "{PRIMAL2}: Pathfinding via Reinforcement and Imitation Multi-Agent Learning - Lifelong", JOURNAL= "IEEE Robotics and Automation Letters", VOLUME="6", NUMBER="2", PAGES= "2666--2673", YEAR= "2021", PDF= "https://arxiv.org/pdf/2010.08184.pdf", FLAGS= ":2021:,:guillaumesartoretti:", ABSTRACT= "Multi-agent path finding (MAPF) is an indispensable component of large-scale robot deployments in numerous domains ranging from airport management to warehouse automation. In particular, this work addresses lifelong MAPF (LMAPF) - an online variant of the problem where agents are immediately assigned a new goal upon reaching their current one - in dense and highly structured environments, typical of real-world warehouse operations. Effectively solving LMAPF in such environments requires expensive coordination between agents as well as frequent replanning abilities, a daunting task for existing coupled and decoupled approaches alike. With the purpose of achieving considerable agent coordination without any compromise on reactivity and scalability, we introduce PRIMAL2, a distributed reinforcement learning framework for LMAPF where agents learn fully decentralized policies to reactively plan paths online in a partially observable world. We extend our previous work, which was effective in low-density sparsely occupied worlds, to highly structured and constrained worlds by identifying behaviors and conventions which improve implicit agent coordination, and enable their learning through the construction of a novel local agent observation and various training aids. We present extensive results of PRIMAL2 in both MAPF and LMAPF environments and compare its performance to state-of-the-art planners in terms of makespan and throughput. We show that PRIMAL2 significantly surpasses our previous work and performs comparably to these baselines, while allowing real-time re-planning and scaling up to 2048 agents.

Additional videos can be found on the YouTube playlist of the paper." } @PHDTHESIS{Ma20, AUTHOR= "H. Ma", TITLE= "Target Assignment and Path Planning for Navigation Tasks with Teams of Agents", SCHOOL= "Department of Computer Science, University of Southern California", ADDRESS= "Los Angeles (California)", YEAR= "2020", FLAGS= ":2020:,:hangma:", PDF= "http://idm-lab.org/bib/abstracts/papers/dissertation-ma.pdf", ABSTRACT= "N/A", } @INPROCEEDINGS{Koen20t, AUTHOR= "E. Boyarski and A. Felner and D. Harabor and P. Stuckey and L. Cohen and J. Li and S. Koenig", TITLE= "Iterative-Deepening Conflict-Based Search", BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)", PAGES= "(in print)", YEAR= "2020", PDF= "http://idm-lab.org/bib/abstracts/papers/ijcai20b.pdf", FLAGS= ":2020:,:svenkoenig:,:eliboyarski:,:arielfelner:,:danielharabor:,:peterstuckey:,:lironcohen:,:jiaoyangli:", ABSTRACT= "Conflict-Based Search (CBS) is a leading algorithm for optimal Multi-Agent Path Finding (MAPF). CBS variants typically compute MAPF solutions using some form of A* search. However, they often do so under strict time limits so as to avoid exhausting the available memory. In this paper, we present IDCBS, an iterative-deepening variant of CBS which can be executed without exhausting the memory and without strict time limits. IDCBS can be substantially faster than CBS due to incremental methods that it uses when processing CBS nodes." } @INPROCEEDINGS{Koen20r, AUTHOR= "G. Belov and W. Du and M. Garcia de la Banda and D. Harabor and S. Koenig and X. Wei", TITLE= "From Multi-Agent Pathfinding to 3D Pipe Routing", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", PAGES= "(in print)", YEAR= "2020", PDF= "http://idm-lab.org/bib/abstracts/papers/socs20g.pdf", FLAGS= ":2020:,:glebbelov:,:danielharabor:,:svenkoenig:", ABSTRACT= "The 2D Multi-Agent Path Finding (MAPF) problem aims at finding collision-free paths for a number of agents, from a set of start locations to a set of goal locations in a known 2D environment. MAPF has been studied in theoretical computer science, robotics, and artificial intelligence over several decades, due to its importance for robot navigation. It is currently experiencing significant scientific progress due to its relevance for automated warehouses (such as those operated by Amazon) and other important application areas. In this paper, we demonstrate that some recently developed MAPF algorithms apply more broadly than currently believed in the MAPF research community. In particular, we describe the 3D Pipe Routing (PR) problem, which aims at placing collision-free pipes from given start locations to given goal locations in a known 3D environment. The MAPF and PR problems are similar: a solution to a MAPF instance is a set of blocked cells in x-y-t space, while a solution to the corresponding PR instance is a set of blocked cells in x-y-z space. We show how to use this similarity to apply several recently developed MAPF algorithms to the PR problem, and discuss their performance on real-world PR instances. This opens up a new direction of industrial relevance for the MAPF research community.

"
}
@INPROCEEDINGS{Koen20k,
AUTHOR= "J. Li and G. Gange and D. Harabor and P. Stuckey and H. Ma and S. Koenig",
TITLE= "New Techniques for Pairwise Symmetry Breaking in Multi-Agent Path Finding",
BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)",
PAGES= "(in print)",
YEAR= "2020",
PDF= "http://idm-lab.org/bib/abstracts/papers/icaps20d.pdf",
FLAGS= ":2020:,:jiaoyangli:,:graemegange:,:danielharabor:,:peterstuckey:,:hangma:,:svenkoenig:",
ABSTRACT=
"We consider two new classes of pairwise path symmetries which appear in the
context of Multi-Agent Path Finding (MAPF). The first of them, corridor
symmetry, arises when two agents attempt to pass through the same narrow
passage in opposite directions. The second, target symmetry, arises
when the shortest path of one agent passes through the target location of a
second agent after the second agent has already arrived at it. These
symmetries can produce an exponential explosion in the space of possible
collision resolutions, leading to unacceptable runtimes even for
state-of-the-art MAPF algorithms such as Conflict-Based Search (CBS). We
propose to break these symmetries using new reasoning techniques that:
(1) detect each class of symmetry and (2) resolve them by introducing
specialized constraints. We experimentally show that our techniques can, in
some cases, more than double the success rate of CBS and improve its runtime
by one order of magnitude."
}
@INPROCEEDINGS{Koen20j,
AUTHOR= "H. Zhang and J. Li and P. Surynek and S. Koenig and S. Kumar",
TITLE= "Multi-Agent Path Finding with Mutex Propagation",
BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)",
PAGES= "(in print)",
YEAR= "2020",
PDF= "http://idm-lab.org/bib/abstracts/papers/icaps20c.pdf",
FLAGS= ":2020:,:hanzhang:,:jiaoyangli:,:pavelsurynek:,:svenkoenig:,:satishkumar:",
NOTE= "**Outstanding ICAPS Student Paper Award**",
ABSTRACT=
"Mutex propagation is a form of efficient constraint propagation popularly
used in AI planning to tightly approximate the reachable states from a given
state. We utilize this idea in the context of Multi-Agent Path Finding
(MAPF). When adapted to MAPF, mutex propagation provides stronger constraints
for conflict resolution in Conflict-Based Search (CBS), a popular optimal MAPF
algorithm, and provides it with the ability to identify and reason with
symmetries in MAPF. While existing work identifies a limited form of
symmetries using rectangle reasoning and requires the manual design of
symmetry-breaking constraints, mutex propagation is more general and allows
for the automated design of symmetry-breaking constraints. Our experimental
results show that CBS with mutex propagation is capable of outperforming CBSH
with rectangle reasoning, a state-of-the-art variant of CBS, with respect to
runtime and success rate."
}
@INPROCEEDINGS{Koen20i,
AUTHOR= "D. Atzmon and R. Stern and A. Felner and N. Sturtevant and S. Koenig",
TITLE= "Probabilistic Robust Multi-Agent Path Finding",
BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)",
PAGES= "(in print)",
YEAR= "2020",
PDF= "http://idm-lab.org/bib/abstracts/papers/icaps20b.pdf",
FLAGS= ":2020:,:doratzmon:,:ronistern:,:arielfelner:,:nathansturtevant:,:svenkoenig:",
ABSTRACT=
"In a multi-agent path finding (MAPF) problem, the task is to move a set of
agents to their goal locations without conflicts. In the real world,
unexpected events may delay some of the agents. In this paper, we therefore
study the problem of finding a p-robust solution to a given MAPF problem, which
is a solution that succeeds with probability at least p, even though
unexpected delays may occur. We propose two methods for verifying that given
solutions are p-robust. We also introduce an optimal CBS-based algorithm,
called pR-CBS, and a fast suboptimal algorithm, called pR-GCBS, for finding
such solutions. Our experiments show that a p-robust solution reduces the
number of conflicts compared to optimal, non-robust solutions."
}
@INPROCEEDINGS{Koen20f,
AUTHOR= "J. Li and K. Sun and H. Ma and A. Felner and S. Kumar and S. Koenig",
TITLE= "Moving Agents in Formation in Congested Environments",
BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)",
PAGES= "(in print)",
YEAR= "2020",
PDF= "http://idm-lab.org/bib/abstracts/papers/aamas20a.pdf",
FLAGS= ":2020:,:jiaoyangli:,:hangma:,:arielfelner:,:satishkumar:,:project-p2:,:project-p4:",
ABSTRACT=
"In this paper, we formalize and study the Moving Agents in Formation (MAiF)
problem, that combines the tasks of finding short collision-free paths for
multiple agents and keeping them in close adherence to a desired
formation. Previous work includes controller-based algorithms, swarm-based
algorithms, and potential-field-based algorithms. They usually focus on only
one or the other of these tasks, solve the problem greedily without systematic
search, and thus generate costly solutions or even fail to find solutions in
congested environments. In this paper, we develop a two-phase search
algorithm, called SWARM-MAPF, whose first phase is inspired by swarm-based
algorithms (in open regions) and whose second phase is inspired by multi-agent
path-finding (MAPF) algorithms (in congested regions). In the first phase,
SWARM-MAPF selects a leader among the agents and finds a path for it that is
sufficiently far away from the obstacles so that the other agents can preserve
the desired formation around it. It also identifies the critical segments of
the leader's path where the other agents cannot preserve the desired formation
and the refinement of which has thus to be delegated to the second phase. In
the second phase, SWARM-MAPF refines these segments. Theoretically, we prove
that SWARM-MAPF is complete. Empirically, we show that SWARM-MAPF scales well
and is able to find close-to-optimal solutions.

" } @INPROCEEDINGS{Koen20bb, AUTHOR= "S.-H. Chan and J. Li and D. Harabor and P. Stuckey and G. Gange and L. Cohen and S. Koenig", TITLE= "Nested ECBS for Bounded-Suboptimal Multi-Agent Path Finding", BOOKTITLE= "Proceedings of the IJCAI Workshop on Multi-Agent Path Finding", YEAR= "2020", PDF= "http://idm-lab.org/bib/abstracts/papers/ijcai-workshop20.pdf", FLAGS= ":2020:,:shaohungchan:,:jiaoyangli:,:danielharabor:,:peterstuckey:,:graemegange:,:lironcohen:,:svenkoenig:", ABSTRACT= "Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents on a map. Conflict-Based Search (CBS) is a powerful, complete, and optimal MAPF solver, while Enhanced CBS (ECBS) improves the efficiency of CBS by only guaranteeing a bounded-suboptimal solution. Both MAPF solvers suffer from the weakness of repeatedly resolving the same collisions between the same agents. Merging agents into meta-agents and planing their paths in the joint state space can be used to overcome this problem. However, a joint-state-space MAPF solver makes resolving collisions within meta-agents inefficient. In this paper, we therefore propose Nested ECBS (NECBS), a nested architecture based on ECBS, where collisions within meta-agents are resolved with ECBS. NECBS preserves the important properties of ECBS, namely its completeness and bounded-suboptimality. Empirically, NECBS has a higher success rate than ECBS and its state-of-the-art variants for a runtime limit of 5 minutes.

" } @INPROCEEDINGS{Koen20g, AUTHOR= "J. Li and A. Tinka and S. Kiesel and J. Durham and S. Kumar and S. Koenig", TITLE= "Lifelong Multi-Agent Path Finding in Large-Scale Warehouses", BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)", PAGES= "(in print)", YEAR= "2020", PDF= "http://idm-lab.org/bib/abstracts/papers/aamas20b.pdf", FLAGS= ":2020:,:jiaoyangli:,:satishkumar:,:svenkoenig:", ABSTRACT= "Multi-Agent Path Finding (MAPF) is the problem of moving a team of agents from their start locations to their goal locations without collisions. We study the lifelong variant of MAPF where agents are constantly engaged with new goal locations, such as in warehouses. We propose a new framework for solving lifelong MAPF by decomposing the problem into a sequence of Windowed MAPF instances, where a Windowed MAPF solver resolves collisions among the paths of agents only within a finite time horizon and ignores collisions beyond it. Our framework is particularly well suited to generating pliable plans that adapt to continually arriving new goal locations. We evaluate our framework with a variety of MAPF solvers and show that it can produce high-quality solutions for up to 1,000 agents, significantly outperforming existing methods." } @INPROCEEDINGS{Koen20x, AUTHOR= "P. Surynek and J. Li and H. Zhang and S. Kumar and S. Koenig", TITLE= "Mutex Propagation for SAT-Based Multi-Agent Path Finding", BOOKTITLE= "Proceedings of the International Conference on Principles and Practice of Multi-Agent Systems (PRIMA)", YEAR= "2020", PDF= "http://idm-lab.org/bib/abstracts/papers/prima20.pdf", FLAGS= ":2020:,:pavelsurynek:,:jiaoyangli:,:hanzhang:,:satishkumar:,:svenkoenig:", ABSTRACT= "Multi-agent path finding (MAPF) is the problem of planning a set of non-colliding paths for a set of agents so that each agent reaches its individual goal location following its path. A mutex from classical planning is a constraint forbidding a pair of facts to be both true or a pair of actions to be executed simultaneously. In the context of MAPF, mutexes are used to rule out the simultaneous occurrence of a pair of agents in a pair of locations, which can prune the search space. Previously mutex propagation had been integrated into conflict-based search (CBS), a major search-based approach for solving MAPF optimally. In this paper, we introduce mutex propagation into the compilation-based (SAT-based) solver MDD-SAT, an alternative to search-based solvers. Our experiments show that, despite mutex propagation being computationally expensive, it prunes the search space significantly so that the overall performance of MDD-SAT is improved.", } @INPROCEEDINGS{OSalz22a, AUTHOR= "N. Greshler, and O. Gordon and O. Salzman and N. Shimkin", TITLE= "Cooperative Multi-Agent Path Finding: Beyond Path Planning and Collision Avoidance", BOOKTITLE= "Proceedings of the International Symposium on Multi-Robot and Multi-Agent Systems (MRS)", PAGES= "20--28", YEAR= "2021", PDF="https://crl.cs.technion.ac.il/wp-content/uploads/2022/01/Cooperative_Multi_Agent_Path_Finding__Beyond_Path_Planning_and_Collision_Avoidance__IEEE_MRS_2021_.pdf", FLAGS= ":2021:,:nirgreshler:,:ofirgordon:,:yuvalfilmus:,:orensalzman:", ABSTRACT= "We introduce the Cooperative Multi-Agent Path Finding (Co-MAPF) problem, an extension to the classical MAPF problem, where cooperative behavior is incorporated. In this setting, a group of autonomous agents operate in a shared environment and have to complete cooperative tasks while avoiding collisions with each other. This extension naturally models many real-world applications, where groups of agents must work together to complete a given task. To this end, we formalize the Co-MAPF problem and introduce Cooperative Conflict-Based Search (Co-CBS), a CBS-based algorithm for solving the problem optimally for a wide set of Co-MAPF problems. Co-CBS uses a cooperation-planning module integrated into CBS such that cooperation planning is decoupled from path planning, while ensuring that paths obtained are optimal. Finally, we present empirical results on several MAPF benchmarks demonstrating our algorithm's properties." } @INPROCEEDINGS{OSalz21a, AUTHOR= "O. Gordon, and Y. Filmus, and O. Salzman", TITLE= "Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", PAGES= "64--72", YEAR= "2021", PDF="https://crl.cs.technion.ac.il/wp-content/uploads/2021/06/Revisiting-the-Complexity-Analysis-of-Conflict-Based-Search.pdf", FLAGS= ":2021:,:ofirgordon:,:yuvalfilmus:,:orensalzman:", ABSTRACT= "The problem of Multi-Agent Path Finding (MAPF) calls for finding a set of conflict-free paths for a fleet of agents operating in a given environment. Arguably, the state-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS). In this work we revisit the complexity analysis of CBS to provide tighter bounds on the algorithm's run-time in the worst-case. Our analysis paves the way to better pinpoint the parameters that govern (in the worst case) the algorithm's computational complexity. Our analysis is based on two complementary approaches: In the first approach we bound the run-time using the size of a Multi-valued Decision Diagram (MDD)--a layered graph which compactly contains all possible single-agent paths between two given vertices for a specific path length. In the second approach we express the running time by a novel recurrence relation which bounds the algorithm's complexity. We use generating functions-based analysis in order to tightly bound the recurrence. Using these technique we provide several new upper-bounds on CBS's complexity. The results allow us to improve the existing bound on the running time of CBS for many cases. For example, on a set of common benchmarks we improve the upper-bound by a factor of at least 2 to the power of 10,000,000." } @INPROCEEDINGS{OSalz20a, AUTHOR= "O. Salzman and R. Stern", TITLE= "Research Challenges and Opportunities in Multi-Agent Path Finding and Multi-Agent Pickup and Delivery Problems", BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)", PAGES= "1711--1715", YEAR= "2020", PDF= "http://www.orensalzman.com/docs/AAMAS20.pdf", FLAGS= ":2020:,:orensalzman:,:ronistern:", ABSTRACT= "Recent years have shown a large increase in applications and research of problems that include moving a fleet of physical robots. One particular application that is currently a multi-billion industry led by tech giants such as Amazon robotics and Alibaba is warehouse robots. In this application, a large number of robots operate autonomously in the warehouse picking up, carrying, and putting down the inventory pods. In this paper, we outline several key research challenges and opportunities that manifest in this warehouse application. The first challenge, known as the Multi-Agent Path Finding (MAPF) problem, is the problem of finding a non-colliding path for each agent. While this problem has been well-studied in recent years, we outline several open questions, including understanding the actual hardness of the problem, learning the warehouse to improve online computations, and distributing the problem. The second challenge is known as the Multi-Agent Package and Delivery (MAPD) problem, which is the problem of moving packages in the warehouse. This problem has received some attention, but with limited theoretical understanding or exploitation of the incoming stream of requests. Finally, we highlight a third, often overlooked challenge, which is the challenge of designing the warehouse in a way that will allow efficient solutions of the two above challenges." } @INPROCEEDINGS{Koen19s, AUTHOR= "J. Li and A. Felner and E. Boyarski and H. Ma and S. Koenig", TITLE= "Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search", BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)", PAGES= "(in print)", YEAR= "2019", PDF= "http://idm-lab.org/bib/abstracts/papers/ijcai19a.pdf", FLAGS= ":2019:,:hangma:,:jiaoyangli:,:arielfelner:,:eliboyarski:,:svenkoenig:", ABSTRACT= "Conflict-Based Search (CBS) and its enhancements are among the strongest algorithms for Multi-Agent Path Finding. Recent work introduced an admissible heuristic to guide the high-level search of CBS. In this work, we prove the limitation of this heuristic, as it is based on cardinal conflicts only. We then introduce two new admissible heuristics by reasoning about the pairwise dependencies between agents. Empirically, CBS with either new heuristic significantly improves the success rate over CBS with the recent heuristic and reduces the number of expanded nodes and runtime by up to a factor of 50." } @INPROCEEDINGS{Koen19k, AUTHOR= "R. Stern and N. Sturtevant and A. Felner and S. Koenig and H. Ma and T. Walker and J. Li and D. Atzmon and L. Cohen and S. Kumar and E. Boyarski and R. Bartak", TITLE= "Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks [Position Paper]", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", PAGES= "(in print)", YEAR= "2019", PDF= "http://idm-lab.org/bib/abstracts/papers/socs19a.pdf", FLAGS= ":2019:,:arielfelner:,:ronistern:,:nathansturtevant:,:svenkoenig:,:thaynewalker:,:eliboyarski:,:romanbartak:,:hangma:,:lironcohen:,:jiaoyangli:,:satishkumar:,:introduction:", ABSTRACT= "The MAPF problem is the fundamental problem of planning paths for multiple agents, where the key constraint is that the agents will be able to follow these paths concurrently without colliding with each other. Applications of MAPF include automated warehouses and autonomous vehicles. Research on MAPF has been flourishing in the past couple of years. Different MAPF research papers make different assumptions, e.g., whether agents can traverse the same road at the same time, and have different objective functions, e.g., minimize makespan or sum of agents' actions costs. These assumptions and objectives are sometimes implicitly assumed or described informally. This makes it difficult to establish appropriate baselines for comparison in research papers, as well as making it difficult for practitioners to find the papers relevant to their concrete application. This paper aims to fill this gap and support researchers and practitioners by providing a unifying terminology for describing common MAPF assumptions and objectives. In addition, we also provide pointers to two MAPF benchmarks. In particular, we introduce a new grid-based benchmark for MAPF, and demonstrate experimentally that it poses a challenge to contemporary MAPF algorithms." } @INPROCEEDINGS{Koen19j, AUTHOR= "J. Li and H. Zhang and M. Gong and Z. Liang and W. Liu and Z. Tong and L. Yi and R. Morris and C. Pasareanu and S. Koenig", TITLE= "Scheduling and Airport Taxiway Path Planning under Uncertainty", BOOKTITLE= "Proceedings of the AIAA Aviation Forum and Exposition (AIAA)", PAGES= "(in print)", YEAR= "2019", PDF= "http://idm-lab.org/bib/abstracts/papers/aiaa19.pdf", FLAGS= ":2019:,:jiaoyangli:,:hanzhang:,:svenkoenig:", ABSTRACT= "Congestion and uncertainty on the airport surface are major constraints to the available capacity of the air transport system. This project seeks to study the problem of planning and scheduling airport surface movement at large airports. Specifically, we focus on scheduling and taxiway path planning of multiple aircraft. In this paper we describe a simulation tool that is capable of simulating aircraft movement along the taxiway, including models of uncertainty during aircraft movement. We introduce a new approach to scheduling that includes models for predicting surface movement uncertainty." } @INPROCEEDINGS{SKoen19a, AUTHOR= "H. Ma and D. Harabor and P. Stuckey and J. Li and S. Koenig", TITLE= "Searching with Consistent Prioritization for Multi-Agent Path Finding", BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)", PAGES= "(in print)", YEAR= "2019", PDF= "http://idm-lab.org/bib/abstracts/papers/aaai19b.pdf", FLAGS= ":2019:,:svenkoenig:,:hangma:,:jiaoyangli:,:danielharabor:,:peterstuckey:", ABSTRACT= "We study prioritized planning for Multi-Agent Path Finding (MAPF). Existing prioritized MAPF algorithms depend on rule-of-thumb heuristics and random assignment to determine a fixed total priority ordering of all agents a priori. We instead explore the space of all possible partial priority orderings as part of a novel systematic and conflict-driven combinatorial search framework. In a variety of empirical comparisons, we demonstrate state-of-the-art solution qualities and success rates, often with similar runtimes to existing algorithms. We also develop new theoretical results that explore the limitations of prioritized planning, in terms of completeness and optimality, for the first time." } @INPROCEEDINGS{SKoen19b, AUTHOR= "H. Ma and W. Hoenig and S. Kumar and N. Ayanian and S. Koenig", TITLE= "Lifelong Path Planning with Kinematic Constraints for Multi-Agent Pickup and Delivery", BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)", PAGES= "(in print)", YEAR= "2019", PDF= "http://idm-lab.org/bib/abstracts/papers/aaai19a.pdf", FLAGS= ":2019:,:svenkoenig:,:satishkumar:,:hangma:,:noraayanian:,:wolfganghoenig:", ABSTRACT= "The Multi-Agent Pickup and Delivery (MAPD) problem models applications where a large number of agents attend to a stream of incoming pickup-and-delivery tasks. Token Passing (TP) is a recent MAPD algorithm that is efficient and effective. We make TP even more efficient and effective by using a novel combinatorial search algorithm, called Safe Interval Path Planning with Reservation Table (SIPPwRT), for single-agent path planning. SIPPwRT uses an advanced data structure that allows for fast updates and lookups of the current paths of all agents in an online setting. The resulting MAPD algorithm TP-SIPPwRT takes kinematic constraints of real robots into account directly during planning, computes continuous agent movements with given velocities that work on non-holonomic robots rather than discrete agent movements with uniform velocity, and is complete for well-formed MAPD instances. We demonstrate its benefits for automated warehouses using both an agent simulator and a standard robot simulator. For example, we demonstrate that it can compute paths for hundreds of agents and thousands of tasks in seconds and is more efficient and effective than existing MAPD algorithms that use a post-processing step to adapt their paths to continuous agent movements with given velocities.

The proof can be found in an appendix.

" } @INPROCEEDINGS{SKoen19c, AUTHOR= "J. Li and P. Surynek and A. Felner and H. Ma and S. Kumar and S. Koenig", TITLE= "Multi-Agent Path Finding for Large Agents", BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)", PAGES= "(in print)", YEAR= "2019", PDF= "http://idm-lab.org/bib/abstracts/papers/aaai19c.pdf", FLAGS= ":2019:,:svenkoenig:,:satishkumar:,:jiaoyangli:,:hangma:,:arielfelner:,:pavelsurynek:", ABSTRACT= "Multi-Agent Path Finding (MAPF) has been widely studied in the AI community. For example, Conflict-Based Search (CBS) is a state-of-the-art MAPF algorithm based on a two-level tree-search. However, previous MAPF algorithms assume that an agent occupies only a single location at any given time, e.g., a single cell in a grid. This limits their applicability in many real-world domains that have geometric agents in lieu of point agents. Geometric agents are referred to as 'large' agents because they can occupy multiple points at the same time. In this paper, we formalize and study LA-MAPF, i.e., MAPF for large agents. We first show how CBS can be adapted to solve LA-MAPF. We then present a generalized version of CBS, called Multi-Constraint CBS (MC-CBS), that adds multiple constraints (instead of one constraint) for an agent when it generates a high-level search node. We introduce three different approaches to choose such constraints as well as an approach to compute admissible heuristics for the high-level search. Experimental results show that all MC-CBS variants outperform CBS by up to three orders of magnitude in terms of runtime. The best variant also outperforms EPEA* (a state-of-the-art A*-based MAPF solver) in all cases and MDD-SAT (a state-of-the-art reduction-based MAPF solver) in some cases." } @INPROCEEDINGS{SKoen19d, AUTHOR= "J. Li and D. Harabor and P. Stuckey and H. Ma and S. Koenig", TITLE= "Symmetry-Breaking Constraints for Grid-Based Multi-Agent Path Finding", BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)", PAGES= "(in print)", YEAR= "2019", PDF= "http://idm-lab.org/bib/abstracts/papers/aaai19d.pdf", FLAGS= ":2019:,:svenkoenig:,:jiaoyangli:,:hangma:,:danielharabor:,:peterstuckey:", ABSTRACT= "We describe a new way of reasoning about symmetric collisions for Multi-Agent Path Finding (MAPF) on 4-neighbor grids. We also introduce a symmetry-breaking constraint to resolve these conflicts. This specialized technique allows us to identify and eliminate, in a single step, all permutations of two currently assigned but incompatible paths. Each such permutation has exactly the same cost as a current path, and each one results in a new collision between the same two agents. We show that the addition of symmetry-breaking techniques can lead to an exponential reduction in the size of the search space of CBS, a popular framework for MAPF, and report significant improvements in both runtime and success rate versus CBSH and EPEA* - two recent and state-of-the-art MAPF algorithms." } @ARTICLE{SKoen19e, AUTHOR= "G. Sartoretti and J. Kerr and Y. Shi and G. Wagner and S. Kumar and S. Koenig and H. Choset", TITLE= "{PRIMAL}: Pathfinding via Reinforcement and Imitation Multi-Agent Learning", JOURNAL= "IEEE Robotics and Automation Letters", XOLUME="(in print)", XUMBER="(in print)", PAGES= "(in print)", YEAR= "2019", PDF= "http://idm-lab.org/bib/abstracts/papers/ral19.pdf", FLAGS= ":2019:,:svenkoenig:,:skumar:,:howiechoset:,:glennwagner:,:guillaumesartoretti:", ABSTRACT= "Multi-agent path finding (MAPF) is an essential component of many large-scale, real-world robot deployments, from aerial swarms to warehouse automation. However, despite the community's continued efforts, most state-of-the-art MAPF planners still rely on centralized planning and scale poorly past a few hundred agents. Such planning approaches are maladapted to real-world deployments, where noise and uncertainty often require paths be recomputed online, which is impossible when planning times are in seconds to minutes. We present PRIMAL, a novel framework for MAPF that combines reinforcement and imitation learning to teach fully-decentralized policies, where agents reactively plan paths online in a partially-observable world while exhibiting implicit coordination. This framework extends our previous work on distributed learning of collaborative policies by introducing demonstrations of an expert MAPF planner during training, as well as careful reward shaping and environment sampling. Once learned, the resulting policy can be copied onto any number of agents and naturally scales to different team sizes and world dimensions. We present results on randomized worlds with up to 1024 agents and compare success rates against state-of-the-art MAPF planners. Finally, we experimentally validate the learned policies in a hybrid simulation of a factory mockup, involving both real-world and simulated robots.

Additional videos can be found on the
YouTube playlist of the paper."
}
@INPROCEEDINGS{SKoen19f,
AUTHOR= "M. Liu and H. Ma and J. Li and S. Koenig",
TITLE= "Task and Path Planning for Multi-Agent Pickup and Delivery",
BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)",
PAGES= "(in print)",
YEAR= "2019",
PDF= "http://idm-lab.org/bib/abstracts/papers/aamas19a.pdf",
FLAGS= ":2019:,:svenkoenig:,:hangma:,:jiaoyangli:",
ABSTRACT=
"We study the offline Multi-Agent Pickup-and-Delivery (MAPD) problem, where a
team of agents has to execute a batch of tasks with release times in a known
environment. To execute a task, an agent has to move first from its current
location to the pickup location of the task and then to the delivery location
of the task. The MAPD problem is to assign tasks to agents and plan
collision-free paths for them to execute their tasks. Online MAPD algorithms
can be applied to the offline MAPD problem, but do not utilize all of the
available information and may thus not be effective. Therefore, we present two
novel offline MAPD algorithms that improve a state-of-the-art online MAPD
algorithm with respect to task planning, path planning, and deadlock avoidance
for the offline MAPD problem. Our MAPD algorithms first compute one task
sequence for each agent by solving a special traveling salesman problem and
then plan paths according to these task sequences. We also introduce an
effective deadlock avoidance method, called 'reserving dummy paths.'
Theoretically, our MAPD algorithms are complete for well-formed MAPD
instances, a realistic subclass of all MAPD instances. Experimentally, they
produce solutions of smaller makespans and scale better than the online MAPD
algorithm in simulated warehouses with hundreds of robots and thousands of
tasks."
}
@INPROCEEDINGS{SKoen19h,
AUTHOR= "J. Wang and J. Li and H. Ma and S. Koenig and S. Kumar",
TITLE= "A New Constraint Satisfaction Perspective on Multi-Agent Path Finding: Preliminary Results",
BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)",
PAGES= "(in print)",
YEAR= "2019",
PDF= "http://idm-lab.org/bib/abstracts/papers/aamas19b.pdf",
FLAGS= ":2019:,:svenkoenig:,:hangma:,:jiaoyangli:",
ABSTRACT=
"In this paper, we adopt a new perspective on the Multi-Agent Path Finding
(MAPF) problem and view it as a Constraint Satisfaction Problem (CSP). A
variable corresponds to an agent, its domain is the set of all paths from the
start vertex to the goal vertex of the agent, and the constraints allow only
conflict-free paths for each pair of agents. Although the domains and
constraints are only implicitly defined, this new CSP perspective allows us to
use successful techniques from CSP search. With the concomitant idea of using
matrix computations for calculating the size of the reduced domain of an
uninstantiated variable, we apply Dynamic Variable Ordering and Rapid Random
Restarts to the MAPF problem. In our experiments, the resulting simple
polynomial-time MAPF solver, called Matrix MAPF solver, either outperforms or
matches the performance of many state-of-the-art solvers for the MAPF problem
and its variants."
}
@INPROCEEDINGS{SKoen19i,
AUTHOR= "J. Li and D. Harabor and P. Stuckey and A. Felner and H. Ma and S. Koenig",
TITLE= "Disjoint Splitting for Multi-Agent Path Finding with Conflict-Based Search",
BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)",
PAGES= "(in print)",
YEAR= "2019",
PDF= "http://idm-lab.org/bib/abstracts/papers/icaps19a.pdf",
FLAGS= ":2019:,:svenkoenig:,:jiaoyangli:,:arielfelner:,:hangma:,:danielharabor:,:peterstuckey:",
ABSTRACT=
"Multi-Agent Path Finding (MAPF) is the planning problem of finding
collision-free paths for a team of agents. We focus on Conflict-Based Search
(CBS), a two-level tree-search state-of-the-art MAPF algorithm. The standard
splitting strategy used by CBS is not disjoint, i.e., when it splits a problem
into two subproblems, some solutions are shared by both subproblems, which can
create duplication of search effort. In this paper, we demonstrate how to
improve CBS with disjoint splitting and how to modify the low-level search of
CBS to take maximal advantage of it. Experiments show that disjoint splitting
increases the success rates and speeds of CBS and its variants by up to 2
orders of magnitude."
}
@INPROCEEDINGS{SKoen18o,
AUTHOR= "H. Ma and G. Wagner and A. Felner and J. Li and S. Kumar and S. Koenig",
TITLE= "Multi-Agent Path Finding with Deadlines",
BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)",
YEAR= "2018",
PAGES= "417--423",
PDF= "http://idm-lab.org/bib/abstracts/papers/ijcai18b.pdf",
FLAGS= ":2018:,:svenkoenig:,:hangma:,:jiaoyangli:,:satishkumar:,:arielfelner:,:glennwagner:",
ABSTRACT=
"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."
}
@INPROCEEDINGS{SKoen18p,
AUTHOR= "L. Cohen and M. Greco and H. Ma and C. Hernandez and A. Felner and S. Kumar and S. Koenig",
TITLE= "Anytime Focal Search with Applications",
BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)",
YEAR= "2018",
PAGES= "1434--1441",
PDF= "http://idm-lab.org/bib/abstracts/papers/ijcai18c.pdf",
FLAGS= ":2018:,:svenkoenig:,:lironcohen:,:hangma:,:satishkumar:,:arielfelner:",
ABSTRACT=
"Focal search (FS) is a bounded-suboptimal search (BSS) variant of A*. Like A*,
it uses an open list whose states are sorted in increasing order of their
f-values. Unlike A*, it also uses a focal list containing all states from
the open list whose f-values are no larger than a suboptimality factor times
the smallest f-value in the open list. In this paper, we develop an anytime
version of FS, called anytime FS (AFS), that is useful when deliberation time
is limited. AFS finds a 'good' solution quickly and refines it to better and
better solutions if time allows. It does this refinement efficiently by
reusing previous search efforts. On the theoretical side, we show that AFS is
bounded suboptimal and that anytime potential search (ATPS/ANA*), a
state-of-the-art anytime bounded-cost search (BCS) variant of A*, is a special
case of AFS. In doing so, we bridge the gap between anytime search algorithms
based on BSS and BCS. We also identify different properties of priority
functions, used to sort the focal list, that may allow for efficient reuse of
previous search efforts. On the experimental side, we demonstrate the
usefulness of AFS for solving hard combinatorial problems, such as the
generalized covering traveling salesman problem and the multi-agent
pathfinding problem."
}
@INPROCEEDINGS{SKoen18r,
AUTHOR= "D. Sigurdson and V. Bultiko and W. Yeoh and C. Hernandez and S. Koenig",
TITLE= "Multi-Agent Pathfinding with Real-Time Heuristic Search",
BOOKTITLE= "Proceedings of the IEEE Conference on Computational Intelligence and Games (CIG)",
YEAR= "2018",
PDF= "http://idm-lab.org/bib/abstracts/papers/cig18.pdf",
FLAGS= ":2018:,:svenkoenig:,:williamyeoh:",
PAGES= "1--8",
ABSTRACT=
"Multi-agent pathfinding, namely finding collision-free paths for several
agents from their given start locations to their given goal locations on a
known stationary map, is an important task for non-player characters in video
games. A variety of heuristic search algorithms have been developed for this
task. Non-real-time algorithms, such as Flow Annotated Replanning (FAR), first
find complete paths for all agents and then move the agents along these
paths. However, their searches are often too expensive. Real-time algorithms
have the ability to produce the next moves for all agents without finding
complete paths for them and thus allow the agents to move in real
time. Real-time heuristic search algorithms have so far typically been
developed for single-agent pathfinding. We, on the other hand, present a
real-time heuristic search algorithm for multi-agent pathfinding, called
Bounded Multi-Agent A* (BMAA*), that works as follows: Every agent runs an
individual real-time heuristic search that updates heuristic values assigned
to locations and treats the other agents as (moving) obstacles. Agents do not
coordinate with each other, in particular, they neither share their paths nor
heuristic values. We show how BMAA* can be enhanced by adding FAR-style flow
annotations and allowing agents to push other agents temporarily off their
goal locations, when necessary. In our experiments, BMAA* has higher
completion rates and lower completion times than FAR."
}
@INPROCEEDINGS{SKoen18w,
AUTHOR= "L. Cohen and G. Wagner and D. Chan and H. Choset and N. Sturtevant and S. Koenig and S. Kumar",
TITLE= "Rapid Randomized Restarts for Multi-Agent Path Finding Solvers",
BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)",
YEAR= "2018",
PAGES= "148--152",
PDF= "http://idm-lab.org/bib/abstracts/papers/socs18c-good.pdf",
XLAGS= ":2018:,:lironcohen:,:satishkumar:,:howiechoset:,:glennwagner:",
ABSTRACT=
"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 rates for given runtime
limits. 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* and CBS-CL.**Comment:** We did not get the
polished version of the paper (shown here) submitted in time and thus they
published an intermediate version with the same experimental results but
less polished text."
}
@INPROCEEDINGS{SKoen18a,
AUTHOR= "A. Felner and J. Li and E. Boyarski and H. Ma and L. Cohen and S. Kumar and S. Koenig",
TITLE= "Adding Heuristics to Conflict-Based Search for Multi-Agent Path Finding",
BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)",
YEAR= "2018",
PDF= "http://idm-lab.org/bib/abstracts/papers/icaps18a.pdf",
FLAGS= ":2018:,:svenkoenig:,:arielfelner:,:hangma:,:jiaoyangli:,:lironcohen:,:satishkumar:,:eliboyarski:",
PAGES= "83--87",
ABSTRACT=
"Conflict-Based Search (CBS) and its enhancements are among the strongest
algorithms for the multi-agent path-finding problem. However, existing
variants of CBS do not use any heuristics that estimate future work. In this
paper, we introduce different admissible heuristics for CBS by aggregating
cardinal conflicts among agents. In our experiments, CBS with these heuristics
outperforms previous state-of-the-art CBS variants by up to a factor of five."
}
@INPROCEEDINGS{SKoen18k,
AUTHOR= "L. Cohen and S. Koenig and S. Kumar and G. Wagner and H. Choset and D. Chan and N. Sturtevant",
TITLE= "Rapid Randomized Restarts for Multi-Agent Path Finding: Preliminary Results",
BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)",
YEAR= "2018",
PAGES= "1909--1911",
PDF= "http://idm-lab.org/bib/abstracts/papers/aamas18a.pdf",
FLAGS= ":2018:,:svenkoenig:,:lironcohen:,:satishkumar:,:howiechoset:,:glennwagner:",
ABSTRACT=
"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."
}
@INPROCEEDINGS{SKoen18m,
AUTHOR= "H. Ma and G. Wagner and A. Felner and J. Li and S. Kumar and S. Koenig",
TITLE= "Multi-Agent Path Finding with Deadlines: Preliminary Results",
BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)",
YEAR= "2018",
PAGES= "2004--2006",
PDF= "http://idm-lab.org/bib/abstracts/papers/aamas18b.pdf",
FLAGS= ":2018:,:svenkoenig:,:hangma:,:arielfelner:,:jiaoyangli:,:satishkumar:,:glennwagner:",
ABSTRACT=
"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."
}
@ARTICLE{SKoen17s,
AUTHOR= "H. Ma and W. Hoenig and L. Cohen and T. Uras and H. Xu and S. Kumar and N. Ayanian and S. Koenig",
TITLE= "Overview: A Hierarchical Framework for Plan Generation and Execution in Multirobot Systems",
JOURNAL= "IEEE Intelligent Systems",
YEAR= "2017",
VOLUME= "32",
NUMBER= "6",
PAGES= "6--12",
PDF= "http://idm-lab.org/bib/abstracts/papers/ieee-intelligent-systems17.pdf",
FLAGS= ":2017:,:svenkoenig:,:hangma:,:lironcohen:,:tanseluras:,:hongxu:,:satishkumar:,:noraayanian:,:wolfganghoenig:",
ABSTRACT=
"The authors present an overview of a hierarchical framework for coordinating
task- and motion-level operations in multirobot systems. Their framework is
based on the idea of using simple temporal networks to simultaneously reason
about precedence/causal constraints required for task-level coordination and
simple temporal constraints required to take some kinematic constraints of
robots into account. In the plan-generation phase, the framework provides a
computationally scalable method for generating plans that achieve high-level
tasks for groups of robots and take some of their kinematic constraints into
account. In the plan-execution phase, the framework provides a method for
absorbing an imperfect plan execution to avoid time-consuming re-planning in
many cases. The authors use the multirobot path-planning problem as a case
study to present the key ideas behind their framework for the long-term
autonomy of multirobot systems."
}
@INPROCEEDINGS{SKoen17a,
AUTHOR= "H. Ma and S. Kumar and S. Koenig",
TITLE= "Multi-Agent Path Finding with Delay Probabilities",
BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)",
PAGES= "3605--3612",
YEAR= "2017",
PDF= "http://idm-lab.org/bib/abstracts/papers/aaai17.pdf",
FLAGS= ":2017:,:svenkoenig:,:hangma:,:satishkumar:",
ABSTRACT=
"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."
}
@INPROCEEDINGS{SKoen17d,
AUTHOR= "H. Ma and J. Li and S. Kumar and S. Koenig",
TITLE= "Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks",
BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)",
PAGES= "837--845",
YEAR= "2017",
PDF= "http://idm-lab.org/bib/abstracts/papers/aamas17.pdf",
FLAGS= ":2017:,:svenkoenig:,:hangma:,:satishkumar:,:jiaoyangli:",
ABSTRACT=
"The multi-agent path-finding (MAPF) problem has recently received a lot of
attention. However, it does not capture important characteristics of many
real-world domains, such as automated warehouses, where agents are constantly
engaged with new tasks. In this paper, we therefore study a lifelong version
of the MAPF problem, called the multi-agent pickup and delivery (MAPD)
problem. In the MAPD problem, agents have to attend to a stream of delivery
tasks in an online setting. One agent has to be assigned to each delivery
task. This agent has to first move to a given pickup location and then to a
given delivery location while avoiding collisions with other agents. We
present two decoupled MAPD algorithms, Token Passing (TP) and Token Passing
with Task Swaps (TPTS). Theoretically, we show that they solve all well-formed
MAPD instances, a realistic subclass of MAPD instances. Experimentally, we
compare them against a centralized strawman MAPD algorithm without this
guarantee in a simulated warehouse system. TP can easily be extended to a
fully distributed MAPD algorithm and is the best choice when real-time
computation is of primary concern since it remains efficient for MAPD
instances with hundreds of agents and tasks. TPTS requires limited
communication among agents and balances well between TP and the centralized
MAPD algorithm."
}
@INPROCEEDINGS{SKoen17g,
AUTHOR= "W. Hoenig and S. Kumar and L. Cohen and H. Ma and H. Xu and N. Ayanian and S. Koenig",
TITLE= "Summary: Multi-Agent Path Finding with Kinematic Constraints",
BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)",
PAGES= "4869--4873",
YEAR= "2017",
PDF= "http://idm-lab.org/bib/abstracts/papers/ijcai17.pdf",
XLAGS= ":2017:,:satishkumar:,:lironcohen:,:hangma:,:hongxu:,:noraayanian:,:wolfganghoenig:",
ABSTRACT=
"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 velocity limits)
and suffer from imperfect plan-execution capabilities. We therefore introduce
MAPF-POST 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, considers kinematic constraints, provides a
guaranteed safety distance between robots, and exploits slack to avoid
time-intensive replanning in many cases. We evaluate MAPF-POST in simulation
and on differential-drive robots, showcasing the practicality of our
approach."
}
@INPROCEEDINGS{SKoen17k,
AUTHOR= "H. Ma and J. Yang and L. Cohen and S. Kumar and S. Koenig",
TITLE= "Feasibility Study: Moving Non-Homogeneous Teams in Congested Video Game Environments",
BOOKTITLE= "Proceedings of the Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE)",
PAGES= "270--272",
YEAR= "2017",
XDF= "papers/aiide17.pdf",
XLAGS= ":2017:,:satishkumar:,:lironcohen:,:hangma:",
ABSTRACT=
"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 MAPF
algorithms from artificial intelligence for moving such non-homogeneous teams
in congested video game environments.

" } @ARTICLE{SKoen17m, AUTHOR= "H. Ma and S. Koenig", TITLE= "{AI} Buzzwords Explained: Multi-Agent Path Finding ({MAPF})", JOURNAL= "AI Matters", YEAR= "2017", VOLUME= "3", NUMBER= "3", PAGES= "15--19", PDF= "http://idm-lab.org/bib/abstracts/papers/aimatters17a.pdf", FLAGS= ":2017:,:svenkoenig:,:hangma:", ABSTRACT= "N/A" } @INPROCEEDINGS{SKoen16a, AUTHOR= "H. Ma and C. Tovey and G. Sharon and S. Kumar and S. Koenig", TITLE= "Multi-Agent Path Finding with Payload Transfers and the Package-Exchange Robot-Routing Problem", BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)", YEAR= "2016", PDF= "http://idm-lab.org/bib/abstracts/papers/aaai16.pdf", FLAGS= ":2016:,:svenkoenig:,:hangma:,:satishkumar:,:gunisharon:", PAGES= "3166--3173", ABSTRACT= "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." } @INPROCEEDINGS{SKoen16h, AUTHOR= "L. Cohen and T. Uras and S. Kumar and H. Xu and N. Ayanian and S. Koenig", TITLE= "Improved Solvers for Bounded-Suboptimal Multi-Agent Path Finding", BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)", YEAR= "2016", PAGES= "3067--3074", PDF= "http://idm-lab.org/bib/abstracts/papers/ijcai16.pdf", FLAGS= ":2016:,:svenkoenig:,:lironcohen:,:tanseluras:,:satishkumar:,:hongxu:,:noraayanian:", ABSTRACT= "Multi-Agent Path Finding (MAPF) with the objective to minimize the sum of the travel times of the agents along their paths is a hard combinatorial problem. Recent work has shown that bounded-suboptimal MAPF solvers, such as Enhanced Conflict-Based Search or ECBS(w1) for short, run often faster than optimal MAPF solvers at the cost of incurring a suboptimality factor w1, that is due to using focal search. Other recent work has used experience graphs to guide the search of ECBS(w1) and speed it up, at the cost of incurring a separate suboptimality factor w2, that is due to inflating the heuristic values. Thus, the combination has suboptimality factor w1 w2. In this first feasibility study, we develop a bounded-suboptimal MAPF solver, Improved-ECBS or iECBS(w1) for short, that has suboptimality factor w1 rather than w1 w2 (because it uses experience graphs to guide its search without inflating the heuristic values) and can run faster than ECBS(w1). We also develop two first approaches for automatically generating experience graphs for a given MAPF instance. Finally, we observe heavy-tailed behavior in the runtimes of these MAPF solvers and develop a simple rapid randomized restart strategy that can increase the success rate of iECBS(w1) within a given runtime limit.

Scroll down to download the paper.

Examples of learned highways include:

"
}
@INPROCEEDINGS{SKoen16e,
AUTHOR= "H. Ma and S. Koenig",
TITLE= "Optimal Target Assignment and Path Finding for Teams of Agents",
BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)",
YEAR= "2016",
PAGES= "1144--1152",
PDF= "http://idm-lab.org/bib/abstracts/papers/aamas16a.pdf",
FLAGS= ":2016:,:svenkoenig:,:hangma:",
ABSTRACT=
"We study the TAPF (combined target-assignment and path-finding) problem for
teams of agents in known terrain, which generalizes both the anonymous and
non-anonymous multi-agent path-finding problems. Each of the teams is given
the same number of targets as there are agents in the team. Each agent has to
move to exactly one target given to its team such that all targets are
visited. The TAPF problem is to first assign agents to targets and then plan
collision-free paths for the agents to their targets in a way such that the
makespan is minimized. We present the CBM (Conflict-Based Min-Cost-Flow)
algorithm, a hierarchical algorithm that solves TAPF instances optimally by
combining ideas from anonymous and non-anonymous multi-agent path-finding
algorithms. On the low level, CBM uses a min-cost max-flow algorithm on a
time-expanded network to assign all agents in a single team to targets and
plan their paths. On the high level, CBM uses conflict-based search to resolve
collisions among agents in different teams. Theoretically, we prove that CBM
is correct, complete and optimal. Experimentally, we show the scalability of
CBM to TAPF instances with dozens of teams and hundreds of agents and adapt it
to a simulated warehouse system."
}
@INPROCEEDINGS{SKoen16g,
AUTHOR= "W. Hoenig and S. Kumar and L. Cohen and H. Ma and H. Xu and N. Ayanian and S. Koenig",
TITLE= "Multi-Agent Path Finding with Kinematic Constraints",
BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)",
NOTE= "**Best ICAPS Paper Award (Robotics Track)**",
YEAR= "2016",
PDF= "http://idm-lab.org/bib/abstracts/papers/icaps16.pdf",
PAGES= "477--485",
FLAGS= ":2016:,:svenkoenig:,:satishkumar:,:lironcohen:,:hangma:,:hongxu:,:noraayanian:,:wolfganghoenig:",
ABSTRACT=
"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.

" } @INPROCEEDINGS{SKoen16k, AUTHOR= "W. Hoenig and S. Kumar and H. Ma and S. Koenig and N. Ayanian", TITLE= "Formation Change for Robot Groups in Occluded Environments", BOOKTITLE= "Proceedings of the International Conference on Intelligent Robots and Systems (IROS)", YEAR= "2016", PDF= "http://idm-lab.org/bib/abstracts/papers/iros16.pdf", PAGES= "4836--4842", FLAGS= ":2016:,:svenkoenig:,:satishkumar:,:hangma:,:noraayanian:,:wolfganghoenig:", ABSTRACT= "We study formation change for robot groups in known environments. We are given a team of robots partitioned into groups, where robots in the same group are interchangeable with each other. A formation specifies the locations occupied by each group. The objective is to find collision-free paths that move all robots from a given start formation to a given goal formation. Our algorithm TAPF* has the following features: (a) it incorporates kinematic constraints of robots in form of velocity limits; (b) it maintains a user-specified safety distance between robots; (c) it attempts to minimize the makespan; and (d) it runs efficiently for hundreds of robots and dozens of groups even in dense 3D environments with narrow corridors and other occlusions. We demonstrate the efficiency and effectiveness of TAPF* in simulation and on robots.

" } @INPROCEEDINGS{SKoen16m, AUTHOR= "W. Hoenig and S. Kumar and L. Cohen and H. Ma and S. Koenig and N. Ayanian", TITLE= "Path Planning with Kinematic Constraints for Robot Groups", BOOKTITLE= "Proceedings of the Southern California Robotics Symposium", YEAR= "2016", PDF= "http://idm-lab.org/bib/abstracts/papers/scr16.pdf", XLAGS= ":2016:,:satishkumar:,:lironcohen:,:hangma:,:noraayanian:,:wolfganghoenig:", ABSTRACT= "Path planning for multiple robots is well studied in the AI and robotics communities. For a given discretized environment, robots need to find collision-free paths to a set of specified goal locations. Robots can be fully anonymous, non-anonymous, or organized in groups. Although powerful solvers for this abstract problem exist, they make simplifying assumptions by ignoring kinematic constraints, making it difficult to use the resulting plans on actual robots. In this paper, we present a solution which takes kinematic constraints, such as maximum velocities, into account, while guaranteeing a user-specified minimum safety distance between robots. We demonstrate our approach in simulation and on real robots in 2D and 3D environments." } @INPROCEEDINGS{SKoen16j, AUTHOR= "L. Cohen and S. Koenig", TITLE= "Bounded Suboptimal Multi-Agent Path Finding Using Highways", BOOKTITLE= "IJCAI-16 Doctoral Consortium", YEAR= "2016", PAGES= "3978--3979", PDF= "http://idm-lab.org/bib/abstracts/papers/ijcai-dc16.pdf", XLAGS= ":2016:,:lironcohen:", ABSTRACT= "N/A", } @INPROCEEDINGS{SKoen16i, AUTHOR= "H. Ma and S. Koenig and N. Ayanian and L. Cohen and W. Hoenig and S. Kumar and T. Uras and H. Xu and C. Tovey and G. Sharon", TITLE= "Overview: Generalizations of Multi-Agent Path Finding to Real-World Scenarios", BOOKTITLE= "Proceedings of the IJCAI-16 Workshop on Multi-Agent Path Finding", YEAR= "2016", PDF= "http://idm-lab.org/bib/abstracts/papers/ijcai16-workshop.pdf", FLAGS= ":2016:,:svenkoenig:,:hangma:,:lironcohen:,:satishkumar:,:tanseluras:,:hongxu:,:noraayanian:,:wolfganghoenig:,:gunisharon:", ABSTRACT= "Multi-agent path finding (MAPF) is well-studied in artificial intelligence, robotics, theoretical computer science and operations research. We discuss issues that arise when generalizing MAPF methods to real-w orld scenarios and four research directions that address them. We emphasize the importance of addressing these issues as opposed to dev eloping faster methods for the standard formulation of the MAPF problem. " } @INPROCEEDINGS{SKoen16n, AUTHOR= "H. Ma and S. Koenig", TITLE= "Artificial Intelligence Buzzword: Explained", BOOKTITLE= "AI Matters", YEAR= "2016", PDF= "http://idm-lab.org/bib/abstracts/papers/aimatters16.pdf", XLAGS= ":2016:,:hangma:", ABSTRACT= "N/A" } @INPROCEEDINGS{SKoen15d, AUTHOR= "L. Cohen and T. Uras and S. Koenig", TITLE= "Feasibility Study: Using Highways for Bounded-Suboptimal Multi-Agent Path Finding", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", YEAR= "2015", PAGES= "2--8", PDF= "http://idm-lab.org/bib/abstracts/papers/socs15b.pdf", FLAGS= ":2015:,:svenkoenig:,:lironcohen:,:tanseluras:", ABSTRACT= "Multi-agent path-finding (MAPF) is important for applications such as the kind of warehousing done by Kiva systems. Solving the problem optimally is NP-hard, yet finding low-cost solutions is important. Bounded-suboptimal MAPF algorithms, such as enhanced conflict-based search (ECBS), often do not perform well in warehousing domains with many agents. We therefore develop bounded-suboptimal MAPF algorithms, called CBS+HWY and ECBS+HWY, that exploit the problem structure of a given MAPF instance by finding paths for the agents that include edges from user-provided highways, which encourages a global behavior of the agents that avoids collisions. On the theoretical side, we develop a simple approach that uses highways for MAPF and provides suboptimality guarantees. On the experimental side, we demonstrate that ECBS+HWY can decrease the runtimes and solution costs of ECBS in Kiva-like domains with many agents if the highways capture the problem structures well." } @INPROCEEDINGS{SKoen14k, AUTHOR= "M. Cirillo and T. Uras and S. Koenig", TITLE= "A Lattice-Based Approach to Multi-Robot Motion Planning for Non-Holonomic Vehicles", BOOKTITLE= "Proceedings of the International Conference on Intelligent Robots and Systems (IROS)", YEAR= "2014", PAGES= "232--239", PDF= "http://idm-lab.org/bib/abstracts/papers/iros14.pdf", FLAGS= ":2014:,:svenkoenig:,:tanseluras:,:marcellocirillo:", ABSTRACT= "Coordinating fleets of autonomous, non-holonomic vehicles is paramount to many industrial applications. While there exists solutions to efficiently calculate trajectories for individual vehicles, an effective methodology to coordinate their motions and to avoid deadlocks is still missing. Decoupled approaches, where motions are calculated independently for each vehicle and then centrally coordinated for execution, have the means to identify deadlocks, but not to solve all of them. We present a novel approach that overcomes this limitation and that can be used to complement the deficiencies of decoupled solutions with centralized coordination. Here, we formally define an extension of the framework of lattice-based motion planning to multi-robot systems and we validate it experimentally. Our approach can jointly plan for multiple vehicles and it generates kinematically feasible and deadlock-free motions." } @INPROCEEDINGS{SKoen14b, AUTHOR= "M. Cirillo and F. Pecora and H. Andreasson and T. Uras and S. Koenig", TITLE= "Integrated Motion Planning and Coordination for Industrial Vehicles", BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)", YEAR= "2014", PAGES= "463--471", PDF= "http://idm-lab.org/bib/abstracts/papers/icaps14a.pdf", FLAGS= ":2014:,:svenkoenig:,:tanseluras:,:marcellocirillo:", ABSTRACT= "A growing interest in the industrial sector for autonomous ground vehicles has prompted significant investment in fleet management systems. Such systems need to accommodate on-line externally imposed temporal and spatial requirements, and to adhere to them even in the presence of contingencies. Moreover, a fleet management system should ensure correctness, i.e., refuse to commit to requirements that cannot be satisfied. We present an approach to obtain sets of alternative execution patterns (called trajectory envelopes) which provide these guarantees. The approach relies on a constraint-based representation shared among multiple solvers, each of which progressively refines trajectory envelopes following a least commitment principle." } @ARTICLE{WHoen19a, AUTHOR= "W. Hoenig and S. Kiesel and A. Tinka and J. Durham and N. Ayanian", TITLE= "Persistent and Robust Execution of {MAPF} Schedules in Warehouses", JOURNAL= "IEEE Robotics and Automation Letters", VOLUME= "4", NUMBER= "2", PAGES= "1125--1131", YEAR= "2019", PDF= "http://act.usc.edu/publications/Hoenig_RAL2019.pdf", FLAGS= ":2019:,:wolfganghoenig:,:noraayanian:", ABSTRACT= "Multi-Agent Path Finding (MAPF) is a well-studied problem in Artificial Intelligence that can be solved quickly in practice when using simplified agent assumptions. However,real-world applications, such as warehouse automation, require physical robots to function over long time horizons without collisions. We present an execution framework that can use existing single-shot MAPF planners and ensures robust execution in the presence of unknown or time-varying higher-order dynamic limits, unforeseen robot slow-downs, and unpredictable obstacle appearances. Our framework also naturally enables the overlap of re-planning and execution for persistent operation and requires little communication between robots and the centralized planner. We demonstrate our approach in warehouse simulations and in a mixed reality experiment using differential drive robots. We believe that our solution closes the gap between recent research in the artificial intelligence community and real-world applications." } @INPROCEEDINGS{WHoen19b, AUTHOR= "D. Albani, W. Hoenig, N. Ayanian, D. Nardi, and V. Trianni", TITLE= "Summary: Distributed Task Assignment and Path Planning with Limited Communication for Robot Teams", BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)", PAGES= "(in print)", YEAR= "2019", PDF= "http://act.usc.edu/publications/Albani_AAMAS2019.pdf", FLAGS= ":2019:,:wolfganghoenig:,:noraayanian:", ABSTRACT= "N/A" } @ARTICLE{WHoen18a, AUTHOR= "W. Hoenig and J. Preiss and S. Kumar and G. Sukhatme and N. Ayanian", TITLE= "Trajectory Planning for Quadrotor Swarms", JOURNAL= "IEEE Transactions on Robotics", VOLUME= "34", NUMBER= "4", PAGES= "856--869", YEAR= "2018", PDF= "http://act.usc.edu/publications/Hoenig_TRO2018.pdf", FLAGS= ":2018:,:wolfganghoenig:,:noraayanian:,:satishkumar:", ABSTRACT= "We describe a method for multirobot trajectory planning in known, obstacle-rich environments. We demonstrate our approach on a quadrotor swarm navigating in a warehouse setting. Our method consists of following three stages: 1) roadmap generation that generates sparse roadmaps annotated with possible interrobot collisions; 2) discrete planning that finds valid execution schedules in discrete time and space; 3) continuous refinement that creates smooth trajectories. We account for the downwash effect of quadrotors, allowing safe flight in dense formations. We demonstrate computational efficiency in simulation with up to 200 robots and physical plausibility with an experiment on 32 nano-quadrotors. Our approach can compute safe and smooth trajectories for hundreds of quadrotors in dense environments with obstacles in a few minutes." } @INPROCEEDINGS{WHoen18b, AUTHOR= "W. Hoenig and S. Kiesel and A. Tinka and J. Durham and N. Ayanian", TITLE= "Conflict-Based Search with Optimal Task Assignment", BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)", PAGES= "757--765", YEAR= "2018", PDF= "http://act.usc.edu/publications/Hoenig_AAMAS2018a.pdf", FLAGS= ":2018:,:wolfganghoenig:,:noraayanian:", ABSTRACT= "We consider a variant of the Multi-Agent Path-Finding problem that seeks both task assignments and collision-free paths for a set of agents navigating on a graph, while minimizing the sum of costs of all agents. Our approach extends Conflict-Based Search (CBS), a framework that has been previously used to find collision-free paths for a given fixed task assignment. Our approach is based on two key ideas: (i) we operate on a search forest rather than a search tree; and (ii) we create the forest on demand, avoiding a factorial explosion of all possible task assignments. We show that our new algorithm, CBS-TA, is complete and optimal. The CBS framework allows us to extend our method to ECBS-TA, a bounded suboptimal version. We provide extensive empirical results comparing CBS-TA to task assignment followed by CBS, Conflict-Based Min-Cost-Flow (CBM), and an integer linear program (ILP) solution, demonstrating the advantages of our algorithm. Our results highlight a significant advantage in jointly optimizing the task assignment and path planning for very dense cases compared to the traditional method of solving those two problems independently. For large environments with many robots we show that the traditional approach is reasonable, but that we can achieve similar results with the same runtime but stronger suboptimality guarantees." } @INPROCEEDINGS{AFeln18a, AUTHOR= "D. Atzmon and R. Stern and A. Felner and G. Wagner and R. Bartak and N. Zhou", TITLE= "Robust Multi-Agent Path Finding", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", PAGES= "2--9", YEAR= "2018", PDF= "https://docs.wixstatic.com/ugd/749b4b_c781f993ea8d4a21bfd764720d1dc76c.pdf", FLAGS= ":2018:,:ronistern:,:arielfelner:,:romanbartak:,:glennwagner:", ABSTRACT= "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." } @INPROCEEDINGS{PSury21a, AUTHOR= "J. Chudy and P. Surynek", TITLE= "ESO-MAPF: Bridging Discrete Planning and Continuous Execution in Multi-Agent Pathfinding", BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)", YEAR= "2021", FLAGS= ":2021:,:janchudy:,:pavelsurynek:", PDF= "https://ojs.aaai.org/index.php/AAAI/article/view/17997/17802", ABSTRACT= "We present ESO-MAPF, a research and educational platform for experimenting with multi-agent path finding (MAPF). ESO-MAPF focuses on demonstrating the planning-acting chain in the MAPF domain. MAPF is the task of finding collision free paths for agents from their starting positions to given individual goals. The standard MAPF uses the abstraction where agents move in an undirected graph via traversing its edges in discrete steps. The discrete abstraction simplifies the planning phase however resulting discrete plans often need to be executed in the real continuous environment. ESO-MAPF shows how to bridge discrete planning and the acting phase in which the resulting plans are executed on physical robots. We simulate centralized plans on a group of OZOBOT Evo robots using their reflex functionalities and outputs on the surface of the screen that serves as the environment. Various problems arising along the planning-acting chain are illustrated to emphasize the educational point of view.

" } @INPROCEEDINGS{PSury21b, AUTHOR= "P. Surynek", TITLE= "Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering", BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)", YEAR= "2021", FLAGS= ":2021:,:pavelsurynek:", PDF= "https://ojs.aaai.org/index.php/AAAI/article/view/17472/17279", ABSTRACT= "We introduce multi-goal multi agent path finding (MG-MAPF) which generalizes the standard discrete multi-agent path finding (MAPF) problem. While the task in MAPF is to navigate agents in an undirected graph from their starting vertices to one individual goal vertex per agent, MG-MAPF assigns each agent multiple goal vertices and the task is to visit each of them at least once. Solving MG-MAPF not only requires finding collision free paths for individual agents but also determining the order of visiting agent's goal vertices so that common objectives like the sum-of-costs are optimized. We suggest two novel algorithms using different paradigms to address MG-MAPF: a heuristic search-based algorithm called Hamiltonian-CBS (HCBS) and a compilation-based algorithm built using the satisfiability modulo theories (SMT), called SMT-Hamiltonian-CBS (SMT-HCBS)." } @INPROCEEDINGS{PSury20a, AUTHOR= "P. Surynek", TITLE= "On Satisfiability Modulo Theories in Continuous Multi-Agent Path Finding: Compilation-Based and Search-Based Approaches Compared", BOOKTITLE= "Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART)", YEAR= "2020", FLAGS= ":2020:,:pavelsurynek:", PDF= "http://surynek.net/publications/files/Surynek_On-SMT-in-Continuous-MAPF_ICAART-2020.pdf", ABSTRACT= "Multi-agent path finding (MAPF) in continuous space and time with geometric agents, i.e. agents of various geometric shapes moving smoothly between predefined positions, is addressed in this paper. We analyze a new solving approach based on satisfiability modulo theories (SMT) that is designed to obtain makespan optimal solutions. The standard MAPF is a task of navigating agents in an undirected graph from given starting vertices to given goal vertices so that agents do not collide with each other in vertices or edges of the graph.In the continuous version (MAPF-R), agents move in an n-dimensional Euclidean space along straight lines that interconnect predefined positions. Agents themselves are geometric objects of various shapes occupying certain volume of the space - circles, polygons, etc. For simplicity, we work with circular omni-directional agents having constant velocities in the 2D plane. As agents can have different shapes/sizes and are moving smoothly along lines, a movement along certain lines done with small agents can be non-colliding while the same movement may result in a collision if performed with larger agents. Such a distinction rooted in the geometric reasoning is not present in the standard MAPF. The SMT-based approach for MAPF-R called SMT-CBS-R reformulates the well established Conflict-based Search (CBS) algorithm in terms of SMT. Lazy generation of decision variables and constraints is the key idea behind SMT-CBS. Each time a new conflict is discovered, the underlying encoding is extended with new variables and constraints to eliminate the conflict.We compared SMT-CBS-R and adaptations of CBS for the continuous variant of MAPF experimentally." } @INPROCEEDINGS{PSury20b, AUTHOR= "P. Surynek", TITLE= "Bounded Sub-Optimal Multi-Robot Path Planning Using Satisfiability Modulo Theory {(SMT)} Approach", BOOKTITLE = "Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)", YEAR= "2020", FLAGS = ":2020:,:pavelsurynek:", PDF= "http://surynek.net/publications/files/Surynek_Bounded-Suboptimal-MRPP_IROS-2020.pdf", ABSTRACT= "Multi-robot path planning (MRPP) is a task of planning collision free paths for a group of robots in a graph.Each robot starts in its individual starting vertex and its task is to reach a given goal vertex. Existing techniques for solving MRPP optimally under various objectives include search-based and compilation-based approaches. Often however finding an optimal solution is too difficult hence sub-optimal algorithms that trade-off the quality of solutions and the runtime have been devised. We suggest eSMT-CBS, a new bounded sub-optimal algorithm built on top of recent compilation-based method for optimal MRPP based on satisfiability modulo theories (SMT). We compare eSMT-CBS with ECBS, a major representative of bounded sub-optimal search-based algorithms.The experimental evaluation shows significant advantage of eSMT-CBS across variety of scenarios." } @INPROCEEDINGS{PSury20c, AUTHOR= "J. Chudy and N. Popov and P. Surynek", TITLE= "Deployment of Multi-Agent Pathfinding on a Swarm of Physical Robots Centralized Control via Reflex-Based Behavior", BOOKTITLE= "Proceedings of the International Conference on Robotics, Computer Vision and Intelligent Systems (ROBOVIS)", YEAR= "2020", FLAGS = ":2020:,:janchudy:,nestorpopov:,:pavelsurynek:", PDF= "http://surynek.net/publications/files/Chudy-Popov-Surynek_OZOBOTs-MAPF_ROBOVIS-2020.pdf", ABSTRACT= "Multi-agent pathfinding is a problem of finding paths for multiple agents from their initial configuration to their goal configuration that results in a plan execution without collisions. In this paper, we deploy MAPF solutions on a swarm of small mobile robots. During the plan execution, we mitigate the problem of desynchronization that comes with the plan execution on physical hardware using the reflex-based behavior of the robots. Such deployment can help researchers and educators to demonstrate and test their findings in the physical world.The robot has a line-following capability that can be used for simulation of discrete MAPF solutions. The control curves are displayed in real-time on a display on which the robots move during their path execution.A prototype of the deployment was built and tested experimentally." } @INPROCEEDINGS{PSury20d, AUTHOR= "J. Chudy and N. Popov and P. Surynek", TITLE= "Emulating Centralized Control in Multi-Agent Pathfinding Using Decentralized Swarm of Reflex-Based Robots", BOOKTITLE= "Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC)", YEAR= "2020", FLAGS= ":2020:,:janchudy:,nestorpopov:,:pavelsurynek:", PDF= "http://surynek.net/publications/files/Chudy-Popov-Surynek_OZOBOT-Swarm_SMC-2020.pdf", ABSTRACT= "Multi-agent pathfinding (MAPF) represents a core problem in robotics. In its abstract form, the task is to navigate agents in an undirected graph to individual goal vertices so that conflicts between agents do not occur. Many algorithms for finding feasible or optimal solutions have been devised. We focus on the execution of MAPF solutions with a swarm of simple physical robots. Such execution is important for understanding how abstract plans can be transferred into reality and vital for educational demonstrations. We show how to use a swarm of reflex-based Ozobot Evo robots for MAPF execution. We emulate centralized control of the robots using their reflex-based behavior by putting them on a screen’s surface, where control curves are drawn in real-time during the execution. We identify critical challenges and ways to address them to execute plans successfully with the swarm. The MAPF execution was evaluated experimentally on various benchmarks." } @INPROCEEDINGS{PSury19a, AUTHOR= "P. Surynek", TITLE= "Unifying Search-Based and Compilation-Based Approaches to Multi-Agent Path Finding through Satisfiability Modulo Theories", BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)", PAGES= "1177--1183", YEAR= "2019", PDF= "http://surynek.net/publications/files/Surynek_Unifying-SMT_IJCAI-2019.pdf", FLAGS= ":2019:,:pavelsurynek:", ABSTRACT= "We unify search-based and compilation-based approaches to multi-agent path finding (MAPF) through satisfiability modulo theories (SMT). The task in MAPF is to navigate agents in an undirected graph to given goal vertices so that they do not collide. We rephrase Conflict-Based Search (CBS), one of the state-of-the-art algorithms for optimal MAPF solving, in the terms of SMT. This idea combines SAT-based solving known from MDDSAT, a SAT-based optimal MAPF solver, at the low-level with conflict elimination of CBS at the high-level. Where the standard CBS branches the search after a conflict, we refine the propositional model with a disjunctive constraint. Our novel algorithm called SMT-CBS hence does not branch at the high-level but incrementally extends the propositional model. We experimentally compare SMTCBS with CBS, ICBS, and MDD-SAT." } @INPROCEEDINGS{PSury19b, AUTHOR= "P. Surynek", TITLE= "Conflict Handling Framework in Generalized Multi-Agent Path Finding: Advantages and Shortcomings of Satisfiability Modulo Approach", BOOKTITLE= "Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART)", PAGES= "192--203", YEAR= "2019", PDF= "http://surynek.net/publications/files/Surynek_Conflict-Handling_ICAART-2019.pdf", FLAGS= ":2019:,:pavelsurynek:", ABSTRACT= "We address conflict reasoning in generalizations of multi-agent pathfinding (MAPF). We assume items placed in vertices of an undirected graph with at most one item per vertex. Items can be relocated across edges while various constraints depending on the concrete type of MAPF must be satisfied. We recall a general problem formulation that encompasses known types of item relocation problems such as multi-agent path finding (MAPF) and token swapping (TSWAP). We show how to express new types of relocation problems in the general problem formulation. We thoroughly evaluate a novel solving method for item relocation that combines satisfiability modulo theory (SMT) with conflict-based search (CBS). CBS is interpreted in the SMT framework where we start with the basic model and refine the model with a collision resolution constraint whenever a collision between items occurs. The key difference between the standard CBS and the SMT-based modification of CBS (SMT-CBS) is that the standard CBS branches the search to resolve the collision while SMT-CBS iteratively adds a single disjunctive collision resolution constraint. Our experimental evaluation revealed that although SMT-CBS performs better than CBS in small densely occupied instances of variants of MAPF, it is outperformed on large sparsely occupied environments. The performed analysis shows that individual paths in large environments of relocation instances can be found faster using simple A*-based algorithm than by the SMT solver. On the other hand the SMT solver performs better when many conflicts between items need to be resolved." } @INPROCEEDINGS{PSury19c, AUTHOR= "P. Surynek", TITLE= "Lazy Compilation of Variants of Multi-Robot Path Planning with Satisfiability Modulo Theory (SMT) Approach", BOOKTITLE= "Proceedings of the International Conference on Intelligent Robots and Systems (IROS)", PAGES= "3282--3287", YEAR= "2019", PDF= "http://surynek.net/publications/files/Surynek_Lazy-Relocation_IROS-2019.pdf", FLAGS= ":2019:,:pavelsurynek:", ABSTRACT= "We address variants of multi-robot path planning in graphs (MRPP). We assume robots placed in vertices of an undirected graph with at most one robot per vertex. Robots can move across edges while various problem specific constraints must be satisfied. We introduce a general problem formulation that encompasses known types of robot relocation problems such as multi-robot path planning (MRPP), token swapping (TSWAP), token rotation (TROT), and token permutation (TPERM). We generalize SMT-CBS, a recent solving approach for MRPP based on satisfiability modulo theories (SMT). SMT-CBS compiles MRPP lazily within the SMT framework, starting with the basic model that is refined with a collision resolution constraints whenever collisions between robots occur in the current solution. We show modifications the SMT-CBS algorithm for variants of MRPP and evaluate them experimentally." } @INPROCEEDINGS{PSury19d, AUTHOR= "P. Surynek", TITLE= "Multi-Agent Path Finding with Generalized Conflicts: An Experimental Study", BOOKTITLE= "Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART)", PAGES= "118--142", YEAR= "2019", PDF= "http://surynek.net/publications/files/Surynek_General-Conflicts-Experimental_ICAART-LNCS-2019.pdf", FLAGS= ":2019:,:pavelsurynek:", ABSTRACT= "This paper gives an overview of conflict reasoning in generalizations of multi-agent path finding (MAPF). MAPF and derived variants assume items placed in vertices of an undirected graph with at most one item per vertex. Items can be relocated across edges while various constraints depending on the concrete type of relocation problem must be satisfied. We recall a general problem formulation that encompasses known types of item relocation problems such as multi-agent path finding (MAPF), token swapping (TSWAP), token rotation (TROT), and token permutation (TPERM). We then focused on three existing optimal algorithms for MAPF: search-based CBS, and propositional satisfiability (SAT)-based MDD-SAT and SMT-CBS. These algorithms were modified to tackle various types of conflicts. The major contribution of this paper is a thorough experimental evaluation of CBS, MDD-SAT, and SMT-CBS on various types of relocation problems." } @INPROCEEDINGS{AFeln18b, AUTHOR= "P. Surynek and A. Felner and R. Stern and E. Boyarski", TITLE= "Sub-Optimal {SAT}-Based Approach to Multi-Agent Path-Finding Problem", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", PAGES= "90--105", YEAR= "2018", PDF= "https://docs.wixstatic.com/ugd/749b4b_f28d63b09e5546479f1f541f19804681.pdf", FLAGS= ":arielfelner:,:ronistern:,:eliboyarski:,:pavelsurynek:", ABSTRACT= "In multi-agent path finding (MAPF) the task is to find nonconflicting paths for multiple agents. In this paper we focus on finding suboptimal solutions for MAPF for the sum-of-costs variant. Recently, a SAT-based approached was developed to solve this problem and proved beneficial in many cases when compared to other search-based solvers. In this paper, we present SAT-based unbounded- and bounded-suboptimal algorithms and compare them to relevant algorithms. Experimental results show that in many case the SAT-based solver significantly outperforms the search-based solvers." } @INPROCEEDINGS{AFeln17a, AUTHOR= "P. Surynek and J. Svancara and A. Felner and E. Boyarski", TITLE= "Integration of Independence Detection into {SAT}-Based Optimal Multi-Agent Path Finding - A Novel {SAT}-based Optimal {MAPF} Solver", BOOKTITLE= "Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART)", PAGES= "85--95", YEAR= "2017", PDF= "https://docs.wixstatic.com/ugd/749b4b_8045b531d493420e9bcf415b8e9d7037.pdf", FLAGS= ":2017:,:arielfelner:,:eliboyarski:,:pavelsurynek:", ABSTRACT= "The problem of optimal multi-agent path finding (MAPF) is addressed in this paper. The task is to find optimal paths for mobile agents where each of them need to reach a unique goal position from the given start with respect to the given cost function. Agents must not collide with each other which is a source of combinatorial difficulty of the problem. An abstraction of the problem where discrete agents move in an undirected graph is usually adopted in the literature. Specifically, it is shown in this paper how to integrate independence detection (ID) technique developed for search based MAPF solving into a compilation-based technique that translates the instance of the MAPF problem into propositional satisfiability formalism (SAT). The independence detection technique allows decomposition of the instance consisting of a given number of agents into instances consisting of small groups of agents with no interaction across groups. These small instances can be solved independently and the solution of the original instance is combined from small solutions eventually. The reduction of the size of instances translated to the target SAT formalism has a significant impact on performance as shown in the presented experimental evaluation. The new solver integrating SAT translation and the independence detection is shown to be state-of-the-art in its class for optimal MAPF solving." } @INPROCEEDINGS{AFeln17b, AUTHOR= "P. Surynek and J. Svancara and A. Felner and E. Boyarski", TITLE= "Variants of Independence Detection in {SAT}-Based Optimal Multi-Agent Path Finding", BOOKTITLE= "Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART)", PAGES= "116--136", YEAR= "2017", PDF= "https://docs.wixstatic.com/ugd/749b4b_8045b531d493420e9bcf415b8e9d7037.pdf", FLAGS= ":2017:,:arielfelner:,:eliboyarski:,:pavelsurynek:", ABSTRACT= "In multi-agent path finding (MAPF) on graphs, the task is to find paths for distinguishable agents so that each agent reaches its unique goal vertex from the given start while collisions between agents are forbidden. A cumulative objective function is often minimized in MAPF. The main contribution of this paper consists in integrating independence detection technique (ID) into a compilation-based MAPF solver that translates MAPF instances into propositional satisfiability (SAT). The independence detection technique in search-based solvers tries to decompose a given MAPF instance into instances consisting of small groups of agents with no interaction across groups. After the decomposition phase, small instances are solved independently and the solution of the original instance is combined from individual solutions to small instances. The presented experimental evaluation indicates significant reduction of the size of instances translated to the target SAT formalism and positive impact on the overall performance of the solver." } @INPROCEEDINGS{AFeln17c, AUTHOR= "A. Felner and R. Stern and E. Shimony and M. Goldenberg and G. Sharon and N. Sturtevant and G. Wagner and P. Surynek", TITLE= "Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", PAGES= "28--37", YEAR= "2017", PDF= "https://docs.wixstatic.com/ugd/749b4b_e9f4afe500e14e09b02699b8237fc7bb.pdf", FLAGS= ":2017:,:arielfelner:,:ronistern:,:nathansturtevant:,:gunisharon:,:pavelsurynek:,:glennwagner:", ABSTRACT= "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." } @INPROCEEDINGS{AFeln17d, AUTHOR= "D. Atzmon and A. Felner and R. Stern and G. Wagner and R. Bartak and N. Zhou", TITLE= "k-Robust Multi-Agent Path Finding", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", PAGES= "157--158", YEAR= "2017", PDF= "https://static.wixstatic.com/ugd/749b4b_7a9bd574342d4fccba32245cc14b6b36.pdf", FLAGS= ":2017:,:arielfelner:,:ronistern:,:romanbartek:,:glennwagner:", ABSTRACT= "N/A" } @INPROCEEDINGS{AFeln17e, AUTHOR= "P. Surynek and A. Felner and R. Stern and E. Boyarski", TITLE= "Modifying Optimal {SAT}-Based Approach to Multi-Agent Path-Finding Problem to Suboptimal Variants", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", PAGES= "169--170", YEAR= "2017", PDF= "https://static.wixstatic.com/ugd/749b4b_f28d63b09e5546479f1f541f19804681.pdf", FLAGS= ":2017:,:arielfelner:,:ronistern:,:eliboyarski:,:pavelsurynek:", ABSTRACT= "In multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. Recently, a SAT-based approach was developed to solve this problem and proved beneficial in many cases when compared to other search-based solvers. In this paper, we introduce SAT-based unbounded- and bounded-suboptimal algorithms and compare them to relevant search-based algorithms." } @INPROCEEDINGS{AFeln16a, AUTHOR= "P. Surynek and A. Felner and R. Stern and E. Boyarski", TITLE= "Boolean Satisfiability Approach to Optimal Multi-Agent Path Finding under the Sum of Costs Objective", BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)", PAGES= "1435--1436", YEAR= "2016", PDF= "http://surynek.com/publications/files/Surynek-Felner-Stern-Boyarski_MAPF-MDD-SAT_AAMAS-2016.pdf", FLAGS= ":2016:,:arielfelner:,:ronistern:,:eliboyarski:,:pavelsurynek:", ABSTRACT= "This paper focuses on finding optimal solutions to the multi-agent path finding (MAPF) problem over undirected graphs where the task is to find non-colliding paths for multiple agents, each with a different start and goal position. An encoding of MAPF to Boolean satisfiability (SAT) is already known to the makespan optimal variant of the problem. In this paper we present the first SAT-solver for minimizing the sum of costs enabled by introducing cardinality constraints into the SAT encoding. An experimental evaluation on grid graphs indicate promising performance of the new SAT-based method in comparison with the best variants of previous sum-of-costs search solvers." } @INPROCEEDINGS{AFeln16b, AUTHOR= "P. Surynek and A. Felner and R. Stern and E. Boyarski", TITLE= "Efficient {SAT} Approach to Multi-Agent Path Finding Under the Sum of Costs Objective", BOOKTITLE= "Proceedings of the European Conference on Artificial Intelligence (ECAI)", PAGES= "810--818", YEAR= "2016", PDF= "https://docs.wixstatic.com/ugd/749b4b_c7d1fe5a70a84dbe8f52a6695e45457b.pdf", FLAGS= ":2016:,:arielfelner:,:ronistern:,:eliboyarski:,:pavelsurynek:", ABSTRACT= "In the multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. In this paper we present the first SAT-solver for the sum-of-costs variant of MAPF which was previously only solved by search-based methods. Using both a lower bound on the sum-of-costs and an upper bound on the makespan, we are able to have a reasonable number of variables in our SAT encoding. We then further improve the encoding by borrowing ideas from ICTS, a search-based solver. Experimental evaluation on several domains showed that there are many scenarios where the new SAT-based method outperforms the best variants of previous sumof-costs search solvers - the ICTS and ICBS algorithms." } @INPROCEEDINGS{AFeln16c, AUTHOR= "P. Surynek and A. Felner and R. Stern and E. Boyarski", TITLE= "An Empirical Comparison of the Hardness of Multi-Agent Path Finding under the Makespan and the Sum of Costs Objectives", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", PAGES= "145--147", YEAR= "2016", PDF= "https://static.wixstatic.com/ugd/749b4b_f5ae7c3603d64948a5204fef3890361e.pdf", FLAGS= ":2016:,:arielfelner:,:ronistern:,:eliboyarski:,:pavelsurynek:", ABSTRACT= "In the multi-agent path finding (MAPF) the task is to find non-conflicting paths for multiple agents. Recently, existing makespan optimal SAT-based solvers for MAPF have been modified for the sum-of-costs objective. In this paper, we empirically compare the hardness of solving MAPF with SAT-based and search-based solvers under the makespan and the sum-of-costs objectives in a number of domains. The experimental evaluation shows that MAPF under the makespan objective is easier across all the tested solvers and domains." } @ARTICLE{AFeln15a, AUTHOR= "G. Sharon and R. Stern and A. Felner and N. Sturtevant", TITLE= "Conflict-Based Search for Optimal Multi-Agent Pathfinding", JOURNAL= "Artificial Intelligence", VOLUME= "219", PAGES= "40--66", YEAR= "2015", PDF= "https://static.wixstatic.com/ugd/749b4b_f423259608bb455aa51ebca1a5aae01c.pdf", FLAGS= ":2015:,:gunisharon:,:ronistern:,:arielfelner:,:nathansturtevant:", ABSTRACT= "In the multi-agent pathfinding problem (MAPF) we are given a set of agents each with respective start and goal positions. The task is to find paths for all agents while avoiding collisions. Most previous work on solving this problem optimally has treated the individual agents as a single 'joint agent' and then applied single-agent search variants of the A* algorithm. In this paper we present the Conflict Based Search (CBS) a new optimal multi-agent pathfinding algorithm. CBS is a two-level algorithm that does not convert the problem into the single 'joint agent' model. At the high level, a search is performed on a Conflict Tree (CT) which is a tree based on conflicts between individual agents. Each node in the CT represents a set of constraints on the motion of the agents. At the low level, fast single-agent searches are performed to satisfy the constraints imposed by the high level CT node. In many cases this two-level formulation enables CBS to examine fewer states than A* while still maintaining optimality. We analyze CBS and show its benefits and drawbacks. Additionally we present the Meta-Agent CBS (MA-CBS) algorithm. MA-CBS is a generalization of CBS. Unlike basic CBS, MA-CBS is not restricted to single-agent searches at the low level. Instead, MA-CBS allows agents to be merged into small groups of joint agents. This mitigates some of the drawbacks of basic CBS and further improves performance. In fact, MA-CBS is a framework that can be built on top of any optimal and complete MAPF solver in order to enhance its performance. Experimental results on various problems show a speedup of up to an order of magnitude over previous approaches." } @INPROCEEDINGS{AFeln15b, AUTHOR= "E. Boyarski and A. Felner and G. Sharon and R. Stern", TITLE= "Don't Split, Try To Work It Out: Bypassing Conflicts in Multi-Agent Pathfinding", BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)", PAGES= "47--51", YEAR= "2015", PDF= "https://docs.wixstatic.com/ugd/749b4b_6c85984d14ff4379b3a4400aab955b7b.pdf", FLAGS= ":2015:,:eliboyarski:,:arielfelner:,:gunisharon:,:ronistern:", ABSTRACT= "Conflict-Based Search (CBS) is a recently introduced algorithm for Multi-Agent Path Finding (MAPF) whose runtime is exponential in the number of conflicts found between the agents’ paths. We present an improved version of CBS that bypasses conflicts thereby reducing the CBS search tree. Experimental results show that this improvement reduces the runtime by an order of magnitude in many cases." } @INPROCEEDINGS{AFeln15c, AUTHOR= "E. Boyarski and A. Felner and R. Stern and G. Sharon and O. Betzalel and D. Tolpin and E. Shimony", TITLE= "{ICBS}: The Improved Conflict-Based Search Algorithm for Multi-Agent Pathfinding", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", PAGES= "223--225", YEAR= "2015", PDF= "https://docs.wixstatic.com/ugd/749b4b_0b1d4e2537f24f44b5b3e210b10dccbc.pdf", FLAGS= ":eliboyarski:,:arielfelner:,:ronistern:,:gunisharon:", ABSTRACT= "Conflict-Based Search (CBS) and its enhancements, Meta-Agent CBS and bypassing conflicts are amongst the strongest newly introduced algorithms for Multi-Agent Path Finding. This paper introduces two new improvements to CBS and incorporates them into a coherent, improved version of CBS, namely ICBS. Experimental results show that each of these improvements further reduces the runtime over the existing CBS-based approaches. When all improvements are combined, an even larger improvement is achieved, producing state-of-the art results for a number of domains." } @INPROCEEDINGS{AFeln14a, AUTHOR= "Z. Bnaya and A. Felner", TITLE= "Conflict-Oriented Windowed Hierarchical Cooperative {A}*", BOOKTITLE= "Proceedings of the International Conference on Robotics and Automation (ICRA)", PAGES= "3743--3748", YEAR= "2014", PDF= "https://docs.wixstatic.com/ugd/749b4b_00dbf5f980df47f499096fef03eb4123.pdf", FLAGS= ":arielfelner:", ABSTRACT= "In the Multi-Agent Path Finding problem (MAPF), we are given a map and a set of agents with distinct source and goal locations. The task is to compute a path for each agent from its initial location to its goal location without conflicting with other agents. MAPF solvers can be divided into classes based on their purpose. One of these classes is the class of online MAPF algorithms, in which the search for paths is interleaved with the actual physical moves of the agents. A prominent algorithm in this class is the Windowed Hierarchical Cooperative A* algorithm (WHCA*) where paths are planned for each agent individually and cooperation is obtained using a reservation table. A number of extensions for WHCA* already exist. In this paper we propose a general approach for the baseline WHCA* algorithm which is orthogonal to all other existing extensions. We improve WHCA* by introducing the Conflict Oriented (CO) principle for focusing the agent coordination around conflicts. In addition, we provide a conflict-oriented prioritization mechanism that intelligently chooses which agent should act next. Experimental results demonstrate the advantage of our approach over WHCA*." } @INPROCEEDINGS{AFeln14b, AUTHOR= "M. Barer and G. Sharon and R. Stern and A. Felner", TITLE= "Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem", BOOKTITLE= "Proceedings of the European Conference on Artificial Intelligence (ECAI)", PAGES= "961--962", YEAR= "2014", PDF= "https://docs.wixstatic.com/ugd/749b4b_6c64831cb81c4ddc942fa612dffa5882.pdf", FLAGS= ":2014:,:gunisharon:,:ronistern:,:arielfelner:", ABSTRACT= "The task in the multi-agent path finding problem (MAPF) is to find paths for multiple agents, each with a different start and goal position, such that agents do not collide. A successful optimal MAPF solver is the conflict-based search (CBS) algorithm. CBS is a two level algorithm where special conditions ensure it returns the optimal solution. Solving MAPF optimally is proven to be NP-hard, hence CBS and all other optimal solvers do not scale up. We propose several ways to relax the optimality conditions of CBS trading solution quality for runtime as well as bounded-suboptimal variants, where the returned solution is guaranteed to be within a constant factor from optimal solution cost. Experimental results show the benefits of our new approach; a massive reduction in running time is presented while sacrificing a minor loss in solution quality. Our new algorithms outperform other existing algorithms in most of the cases." } @INPROCEEDINGS{AFeln13a, AUTHOR= "G. Sharon and R. Stern and M. Goldenberg and A. Felner", TITLE= "The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding", JOURNAL= "Artificial Intelligence", VOLUME= "195", PAGES= "470--495", YEAR= "2013", PDF= "https://docs.wixstatic.com/ugd/749b4b_fb8081578d2d450f88ffa20176f3c819.pdf", FLAGS= ":2013:,:gunisharon:,:ronistern:,:arielfelner:", ABSTRACT= "We address the problem of optimal pathfinding for multiple agents. Given a start state and a goal state for each of the agents, the task is to find minimal paths for the different agents while avoiding collisions. Previous work on solving this problem optimally, used traditional single-agent search variants of the A* algorithm. We present a novel formalization for this problem which includes a search tree called the increasing cost tree (ICT) and a corresponding search algorithm, called the increasing cost tree search (ICTS) that finds optimal solutions. ICTS is a two-level search algorithm. The high-level phase of ICTS searches the increasing cost tree for a set of costs (cost per agent). The low-level phase of ICTS searches for a valid path for every agent that is constrained to have the same cost as given by the high-level phase. We analyze this new formalization, compare it to the A* search formalization and provide the pros and cons of each. Following, we show how the unique formalization of ICTS allows even further pruning of the state space by grouping small sets of agents and identifying unsolvable combinations of costs. Experimental results on various domains show the benefits and limitations of our new approach. A speedup of up to 3 orders of magnitude was obtained in some cases." } @INPROCEEDINGS{AFeln13b, AUTHOR= "Z. Bnaya and R. Stern and A. Felner and R. Zivan and S. Okamoto", TITLE= "Multi-Agent Path Finding for Self Interested Agents", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", YEAR= "2013", PDF= "https://docs.wixstatic.com/ugd/749b4b_a24287955d87430dafe9ffcd04573576.pdf", FLAGS= ":2013:,:ronistern:,:arielfelner:", ABSTRACT= "Multi-agent pathfinding (MAPF) deals with planning paths for individual agents such that a global cost function (e.g., the sum of costs) is minimized while avoiding collisions between agents. Previous work proposed centralized or fully cooperative decentralized algorithms assuming that agents will follow paths assigned to them. When agents are self-interested, however, they are expected to follow a path only if they consider that path to be their most beneficial option. In this paper we propose the use of a taxation scheme to implicitly coordinate self-interested agents in MAPF. We propose several taxation schemes and compare them experimentally. We show that intelligent taxation schemes can result in a lower total cost than the non coordinated scheme even if we take into consideration both travel cost and the taxes paid by agents." } @INPROCEEDINGS{AFeln12a, AUTHOR= "M. Goldenberg and A. Felner and R. Stern and G. Sharon and J. Schaeffer", TITLE= "{A}* Variants for Optimal Multi-Agent Pathfinding", BOOKTITLE= "AAAI-12 Workshop on Multi-Agent Pathfinding", YEAR= "2012", PDF= "https://static.wixstatic.com/ugd/749b4b_eea19cb1ca7d42679b29d43a10f57177.pdf", FLAGS= ":2012:,:arielfelner:,:ronistern:,:gunisharon:", ABSTRACT= "Several variants of A* have been recently proposed for finding optimal solutions for the multi-agent pathfinding (MAPF) problem. However, these variants have not been deeply compared either quantitatively or qualitatively. In this paper we aim to fill this gap. In addition to obtaining a deeper understanding of the existing algorithms, we describe in detail the application of the new enhanced partial-expansion technique to MAPF and show how pattern databases can be applied on top of this technique." } @INPROCEEDINGS{AFeln12b, AUTHOR= "G. Sharon and R. Stern and A. Felner and N. Sturtevant", TITLE= "Meta-Agent Conflict-Based Search For Optimal Multi-Agent Path Finding", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", YEAR= "2012", PDF= "https://docs.wixstatic.com/ugd/749b4b_5a0769be20b84852923aeb69d518dd27.pdf", FLAGS= ":2012:,:gunisharon:,:ronistern:,:arielfelner:,:nathansturtevant:", ABSTRACT= "The task in the multi-agent path finding problem (MAPF) is to find paths for multiple agents, each with a different start and goal position, such that agents do not collide. It is possible to solve this problem optimally with algorithms that are based on the A* algorithm. Recently, we proposed an alternative algorithm called Conflict-Based Search (CBS) (Sharon et al. 2012), which was shown to outperform the A*-based algorithms in some cases. CBS is a two-level algorithm. At the high level, a search is performed on a tree based on conflicts between agents. At the low level, a search is performed only for a single agent at a time. While in some cases CBS is very efficient, in other cases it is worse than A*-based algorithms. This paper focuses on the latter case by generalizing CBS to Meta-Agent CBS (MA-CBS). The main idea is to couple groups of agents into meta-agents if the number of internal conflicts between them exceeds a given bound. MACBS acts as a framework that can run on top of any complete MAPF solver. We analyze our new approach and provide experimental results demonstrating that it outperforms basic CBS and other A*-based optimal solvers in many cases." } @INPROCEEDINGS{AFeln12c, AUTHOR= "G. Sharon and R. Stern and A. Felner and N. Sturtevant", TITLE= "Conflict-Based Search for Optimal Multi-Agent Path Finding", BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)", YEAR= "2012", PDF= "https://docs.wixstatic.com/ugd/749b4b_f0c43af4b6d745d2abcd0611e62efa33.pdf", FLAGS= ":2011:,:gunisharon:,:ronistern:,:arielfelner:,:nathansturtevant:", ABSTRACT= "In the multi-agent path finding problem (MAPF) paths should be found for several agents, each with a different start and goal position such that agents do not collide. Previous optimal solvers applied global A*-based searches. We present a new search algorithm called Conflict Based Search (CBS). CBS is a two-level algorithm. At the high level, a search is performed on a tree based on conflicts between agents. At the low level, a search is performed only for a single agent at a time. In many cases this reformulation enables CBS to examine fewer states than A* while still maintaining optimality. We analyze CBS and show its benefits and drawbacks. Experimental results on various problems shows a speedup of up to a full order of magnitude over previous approaches." } @INPROCEEDINGS{AFeln11a, AUTHOR= "G. Sharon and R. Stern and A. Felner and N. Sturtevant", TITLE= "The Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding", BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)", YEAR= "2011", PAGES= "662--667", PDF= "https://docs.wixstatic.com/ugd/749b4b_762279ca388e4a259f43dc10aef13914.pdf", FLAGS= ":2011:,:gunisharon:,:ronistern:,:arielfelner:,:nathansturtevant:", ABSTRACT= "We address the problem of optimal path finding for multiple agents where agents must not collide and their total travel cost should be minimized. Previous work used traditional single-agent search variants of the A* algorithm. We present a novel formalization for this problem which includes a search tree called the increasing cost tree (ICT) and a corresponding search algorithm that finds optimal solutions. We analyze this new formalization and compare it to the previous state-of-the-art A*-based approach. Experimental results on various domains show the benefits and drawbacks of this approach. A speedup of up to 3 orders of magnitude was obtained in a number of cases." } @INPROCEEDINGS{AFeln11b, AUTHOR= "G. Sharon and R. Stern and M. Goldenberg and A. Felner", TITLE= "Pruning Techniques for the Increasing Cost Tree Search for Optimal Multi-Agent Pathfinding", BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)", YEAR= "2011", PDF= "https://docs.wixstatic.com/ugd/749b4b_762279ca388e4a259f43dc10aef13914.pdf", FLAGS= ":2011:,:gunisharon:,:ronistern:,:arielfelner:", ABSTRACT= "We address the problem of optimal path finding for multiple agents where agents must not collide and their total travel cost should be minimized. Previous work used traditional single-agent search variants of the A* algorithm. In Sharon et. al. (2011), we introduced a novel two-level search algorithm framework for this problem. The high-level searches a novel search tree called increasing cost tree (ICT). The low-level performs a goal test on each ICT node. The new framework, called ICT search (ICTS), showed to run faster than the previous state-of-the-art A* approach by up to three orders of magnitude in many cases. In this paper we focus on the low-level of ICTS which performs the goal test. We introduce a number of optional pruning techniques that can significantly speed up the goal test. We discuss these pruning techniques and provide supporting experimental results." } @INPROCEEDINGS{DHara19b, AUTHOR= "E. Lam and P. Le Bodic and D. Harabor and P. Stuckey", TITLE= "Branch-and-Cut-and-Price for Multi-Agent Pathfinding", BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)", PAGES= "(in print)", YEAR= "2019", PDF= "https://ed-lam.com/papers/E. Lam, P. Le Bodic, D. Harabor, P. J. Stuckey - Branch-and-Cut-and-Price for Multi-Agent Pathfinding (2019).pdf", FLAGS= ":2019:,:edwardlam:,:pierrelebodic:,:danielharabor:,:peterstuckey:", ABSTRACT= "There are currently two broad strategies for optimal Multi-agent Pathfinding (MAPF): (1) search-based methods, which model and solve MAPF directly, and (2) compilation-based solvers, which reduce MAPF to instances of well-known combinatorial problems, and thus, can benefit from advances in solver techniques. In this work, we present an optimal algorithm, BCP, that hybridizes both approaches using branch-and-cut-and-price, a decomposition framework developed for mathematical optimization. We formalize BCP and compare it empirically against CBSH and CBSH-RM, two leading search-based solvers. Conclusive results on standard benchmarks indicate that its performance exceeds the state-of-the-art: solving more instances on smaller grids and scaling reliably to 100 or more agents on larger game maps.

The code is available on
bitbucket."
}
@INPROCEEDINGS{DHara19a,
AUTHOR= "G. Gange and D. Harabor and P. Stuckey",
TITLE= "Lazy {CBS}: Implict Conflict-Based Search Using Lazy Clause Generation",
BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)",
YEAR= "2019",
PDF= "http://harabor.net/data/papers/ghs-lcbsicbsulcg-icaps19.pdf",
FLAGS= ":2019:,:graemegange:,:danielharabor:,:peterstuckey:",
ABSTRACT=
"We describe a new way of reasoning about symmetric collisions for Multi-Agent
Path Finding (MAPF) on 4-neighbor grids. We also introduce a symmetry-breaking
constraint to resolve these conflicts. This specialized technique allows us to
identify and eliminate, in a single step, all permutations of two currently
assigned but incompatible paths. Each such permutation has exactly the same
cost as a current path, and each one results in a new collision between the
same two agents. We show that the addition of symmetry-breaking techniques can
lead to an exponential reduction in the size of the search space of CBS, a
popular framework for MAPF, and report significant improvements in both
runtime and success rate versus CBSH and EPEA* -- two recent and
state-of-the-art MAPF algorithms."
}
@INPROCEEDINGS{DHara12a,
AUTHOR= "A. Botea and D. Harabor and K. Wang",
TITLE= "Towards Search-Free Multiagent Pathfinding",
BOOKTITLE= "Proceedings of the AAAI-12 Workshop on Multiagent Pathfinding",
YEAR= "2012",
PDF= "http://harabor.net/data/papers/botea-harabor-wang-womp12.pdf",
FLAGS= ":2012:,:danielharabor:,:adibotea:",
ABSTRACT=
"We introduce MARS (Multi-Agent Ring Slidable), an algorithm that
combines ideas from the MAPP algorithm (Wang and Botea 2009) and CPDs (Botea
2011) to eliminate expensive runtime searches. We define a class of instances
where MARS is complete. We prove theoretical properties of the algorithm. To
the best of our knowledge, this could be the first work that aims at
eliminating runtime search in MAPF."
}
@INPROCEEDINGS{GWagn16a,
AUTHOR= "P. Karkus and G. Wagner and H. Choset",
TITLE= "Recursive Constraint Manifold Subsearch for Multirobot Path Planning with Cooperative Tasks",
BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)",
YEAR= "2016",
PAGES= "54--62",
FLAGS = ":2016:,:glennwagner:,:howiechoset:",
PDF= "http://mapf.info/papers/wagner1.pdf",
ABSTRACT=
"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.",
}
@INPROCEEDINGS{GWagn16b,
AUTHOR= "G. Wagner and H. Choset and A. Siravuru",
TITLE= "Multirobot Sequential Composition",
BOOKTITLE= "Proceedings of the International Conference on Intelligent Robots and Systems (IROS)",
PAGES= "2081--2088",
YEAR= "2016",
PDF= "http://mapf.info/papers/wagner2.pdf",
FLAGS= ":2016:,:glennwagner:,:howiechoset:",
ABSTRACT=
"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."
}
@ARTICLE{GWagn15a,
AUTHOR= "G. Wagner and H. Choset",
TITLE= "Subdimensional Expansion for Multirobot Path Planning",
JOURNAL= "Artificial Intelligence",
VOLUME= "219",
PAGES= "1--24",
YEAR= "2015",
PDF= "http://biorobotics.ri.cmu.edu/papers/paperUploads/subdim_journal.pdf",
FLAGS= ":2015:,:glennwanger:,:howiechoset:",
ABSTRACT=
"Planning optimal paths for large numbers of robots is computationally
expensive. In this paper, we introduce a new framework for multirobot path
planning called subdimensional expansion, which initially plans for each robot
individually, and then coordinates motion among the robots as needed. More
specifically, subdimensional expansion initially creates a one-dimensional
search space embedded in the joint configuration space of the multirobot
system. When the search space is found to be blocked during planning by a
robot–robot collision, the dimensionality of the search space is locally
increased to ensure that an alternative path can be found. As a result, robots
are only coordinated when necessary, which reduces the computational cost of
finding a path. We present the M∗ algorithm, an implementation of
subdimensional expansion that adapts the A∗ planner to perform efficient
multirobot planning. M∗ is proven to be complete and to find minimal cost
paths. Simulation results are presented that show that M∗ outperforms existing
optimal multirobot path planning algorithms."
}
@INPROCEEDINGS{GWag15b,
AUTHOR= "G. Wagner and J. Kim and K. Urban and H. Choset",
TITLE= "Constraint Manifold Subsearch for Multirobot Path Planning with Cooperative Tasks",
BOOKTITLE= "Proceedings of the International Conference on Robotics and Automation (ICRA)",
PAGES= "6094--6100",
YEAR= "2015",
PDF= "http://biorobotics.ri.cmu.edu/papers/paperUploads/1898.pdf",
FLAGS= ":2015:,:glennwagner:,:howiechoset:",
ABSTRACT=
"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."
}
@INPROCEEDINGS{GWagn13a,
AUTHOR= "C. Ferner and G. Wagner and H. Choset",
TITLE= "{ODrM}*: Optimal Multirobot Path Planning in Low Dimensional Search Spaces",
BOOKTITLE= "Proceedings of the International Conference on Robotics and Automation (ICRA)",
PAGES= "3854--3859",
YEAR= "2013",
PDF= "http://biorobotics.ri.cmu.edu/papers/paperUploads/ICRA2013_Ferner_ODrM_Optimal_Multirobot_Path_Planning_in_Low_Dimensional_Search_Spaces.pdf",
FLAGS= ":2013:,:glennwagner:,:howiechoset:",
ABSTRACT=
"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.",
}
@INPROCEEDINGS{GWagn12a,
AUTHOR= "G. Wagner and M. Kang and H. Choset",
TITLE= "Probabilistic Path Planning for Multiple Robots with Subdimensional Expansion",
BOOKTITLE= "Proceedings of the International Conference on Robotics and Automation (ICRA)",
PAGES= "2886--2892",
YEAR= "2012",
PDF= "http://biorobotics.ri.cmu.edu/papers/paperUploads/ICRA2012_Wagner.pdf",
FLAGS= ":2012:,:glennwagner:,:howiechoset:",
ABSTRACT=
"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."
}
@INPROCEEDINGS{GWagn12b,
AUTHOR= "G. Wagner and H. Choset and N. Ayanian",
TITLE= "Subdimensional Expansion and Optimal Task Reassignment",
BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)",
PAGES= "177--178",
YEAR= "2012",
PDF= "http://www.aaai.org/ocs/index.php/SOCS/SOCS12/paper/download/5390/5199",
FLAGS= ":2012:,:noraayanian:,:howiechoset:,:glennwagner:",
ABSTRACT=
"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.",
}
@INPROCEEDINGS{GWagn11a,
AUTHOR= "G. Wagner and H. Choset",
TITLE= "{M}*: A Complete Multirobot Path Planning Algorithm with Performance Bounds",
BOOKTITLE= "Proceedings of the International Conference on Intelligent Robots and Systems (IROS)",
PAGES= "3260--3267",
YEAR= "2011",
PDF= "http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.221.1909&rep=rep1&type=pdf",
FLAGS= ":2011:,:glennwagner:,:howiechoset:",
ABSTRACT=
"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."
}
@INPROCEEDINGS{JSvan19a,
AUTHOR= "J. Svancara and M. Vlk and R. Stern and D. Atzmon and R. Bartak",
TITLE= "Online Multi-Agent Pathfinding",
BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)",
PAGES= "(in print)",
YEAR= "2019",
PDF= "http://svancara.net/files/AAAI_CR.pdf",
FLAGS= ":2019:,:jirisvancara:,:marekvlk:,:ronistern:,:doratzmon:,:romanbartak:",
ABSTRACT=
"Multi-agent pathfinding (MAPF) is the problem of moving a group of agents to
a set of target destinations while avoiding collisions. In this work, we study
the online version of MAPF where new agents appear over time. Several variants
of online MAPF are defined and analyzed theoretically, showing that it is not
possible to create an optimal online MAPF solver. Nevertheless, we propose
effective online MAPF algorithms that balance solution quality, runtime, and
the number of plan changes an agent makes during execution."
}
@INPROCEEDINGS{JSvan19b,
AUTHOR= "J. Svancara and R. Bartak",
TITLE= "Combining Strengths of Optimal Multi-Agent Path Finding Algorithms",
BOOKTITLE= "Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART)",
PAGES= "226--231",
YEAR= "2019",
PDF= "http://svancara.net/files/ICAART_2019_145.pdf",
FLAGS= ":2019:,:jirisvancara:,:romanbartak:",
ABSTRACT=
"The problem of multi-agent path finding (MAPF) is studied in this
paper. Solving MAPF optimally is a computationally hard problem and many
different optimal algorithms have been designed over the years. These
algorithms have good runtimes for some problem instances, while performing
badly for other instances. Interestingly, these hard instances are often
different across the algorithms. This leads to an idea of combining the
strengths of different algorithms in such a way that an input problem instance
is split into disjoint subproblems and each subproblem is solved by
appropriate algorithm resulting in faster computation than using either of the
algorithms for the whole instance. By manual problem decomposition we will
empirically show that the above idea is viable. We will also sketch a possible
future work on automated problem decomposition."
}
@INPROCEEDINGS{JSvan18a,
AUTHOR= "R. Bartak and J. Svancara and V. Skopkova and D. Nohejl",
TITLE= "Multi-Agent Path Finding on Real Robots: First Experience with {Ozobots}",
BOOKTITLE= "Proceedings of the Ibero-American Conference on Artificial Intelligence (IBERAMIA)",
NOTE= "**Best IBERAMIA Paper Award**",
PAGES= "290--301",
YEAR= "2018",
PDF= "http://svancara.net/files/iberamia2018.pdf",
FLAGS= ":2018:,:romanbartak:,:jirisvancara:,:veraskopkova:",
ABSTRACT=
"The problem of Multi-Agent Path Finding (MAPF) is to find paths for a fixed
set of agents from their current locations to some desired locations in such a
way that the agents do not collide with each other. This problem has been
extensively theoretically studied, frequently using an abstract model, that
expects uniform durations of moving primitives and perfect synchronization of
agents/robots. In this paper we study the question of how the abstract plans
generated by existing MAPF algorithms perform in practice when executed on
real robots, namely Ozobots. In particular, we use several abstract models of
MAPF, including a robust version and a version that assumes turning of a
robot, we translate the abstract plans to sequences of motion primitives
executable on Ozobots, and we empirically compare the quality of plan
execution (real makespan, the number of collisions)."
}
@INPROCEEDINGS{JSvan18b,
AUTHOR= "R. Bartak and J. Svancara and M. Vlk",
TITLE= "A Scheduling-Based Approach to Multi-Agent Path Finding with Weighted and Capacitated Arcs",
BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)",
PAGES= "748--756 ",
YEAR= "2018",
PDF= "http://ifaamas.org/Proceedings/aamas2018/pdfs/p748.pdf",
FLAGS= ":2018:,:romanbartak:,:jirisvancara:,:marekvlk:",
ABSTRACT=
"Multi-agent path finding (MAPF) deals with the problem of finding a
collision-free path for a set of agents. The agents are located at nodes of a
directed graph, they can move over the arcs, and each agent has its own
destination node. It is not possible for two agents to be at the same node at
the same time. The usual setting is that each arc has length one so at any
time step, each agent either stays in the node, where it is, or moves to one
of its neighboring nodes. This paper suggests to model the MAPF problem using
scheduling techniques, namely, nodes and arcs are seen as resources. The
concept of optional activities is used to model which nodes and arcs an agent
will visit. We first describe a model, where each agent can visit each node at
most once. Then, we extend the model to allow agents re-visiting the nodes.
The major motivation for the scheduling model of MAPF is its capability to
naturally include other constraints. We will study particularly the problems,
where the capacity of arcs can be greater than one (more agents can use the
same arc at the same time), and the lengths of arcs can be greater than one
(moving between different pairs of nodes takes different times). These
extensions make the model closer to reality than the original MAPF
formulation. We compare the efficiency of models experimentally"
}
@INPROCEEDINGS{JSvan18c,
AUTHOR= "J. Svancara",
TITLE= "Bringing Multi-Agent Path Finding Closer to Reality",
BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)",
YEAR= "2018",
PAGES= "5787--5788",
PDF= "https://www.ijcai.org/proceedings/2018/0837.pdf",
FLAGS= ":2018:,:jirisvancara:",
ABSTRACT=
"Multi-agent path finding is the problem of navigating multiple agents from their current locations to
their goal locations in such a way that there are no
collisions between the agents. The classical definition of the problem assumes that the set of agents
is unchangeable, and that the distances in the graph
are homogeneous.
We propose to add to the problem specification a
set of new attributes to bring it closer to the real
world. These attributes include varying distances,
number of agents that can occupy an edge or node,
and dynamic appearance of new agents."
}
@INPROCEEDINGS{JSvan18d,
AUTHOR= "J. Svancara",
TITLE= "Bringing Multi-Agent Path Finding Closer to Reality",
BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)",
YEAR= "2018",
PAGES= "1784--1785",
PDF= "http://ifaamas.org/Proceedings/aamas2018/pdfs/p1784.pdf",
FLAGS= ":2018:,:jirisvancara:",
ABSTRACT=
"Multi-agent path finding is the problem of navigating multiple agents,
located in a graph, from their current locations to their goal locations in
such a way that there are no collisions between the agents. The classical
definition of the problem assumes that the set of agents is unchangeable, and
that the distances in the graph are homogeneous. We propose to add to the
problem specification a set of new attributes to bring it closer to the real
world. These attributes include varying distances, number of agents that can
occupy an edge or node, and dynamic appearance of new agents."
}
@INPROCEEDINGS{JSvan17a,
AUTHOR= "R. Bartak and J. Svancara and M. Vlk",
TITLE= "Scheduling Models for Multi-Agent Path Finding",
BOOKTITLE= "Proceedings of the Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA)",
PAGES= "189--200",
YEAR= "2017",
PDF= "http://svancara.net/files/MISTA_2017_paper_44.pdf",
FLAGS= ":2017:,:romanbartak:,:jirisvancara:,:marekvlk:",
ABSTRACT=
"Multi-agent path finding (MAPF) deals with the problem of finding a collision
free path for a set of agents. The agents are located at nodes of a directed
graph, they can move over the arcs, and each agent has its own destination
node. It is not possible for two agents to be at the same node at the same
time. This paper suggests to model the MAPF problem using scheduling
techniques, namely, nodes are seen as unary resources. We present three models
of the problem. One model is motivated by network flows, another model uses
classical unary resource constraints together with path constraints, and the
last model works with optional activities. We compare the efficiency of models
experimentally."
}
@INPROCEEDINGS{JSvan17b,
AUTHOR= "J. Svancara and P. Surynek",
TITLE= "New Flow-based Heuristic for Search Algorithms Solving Multi-Agent Path Finding",
BOOKTITLE= "Proceedings of the International Conference on Agents and Artificial Intelligence (ICAART)",
PAGES= "451--458",
YEAR= "2017",
PDF= "http://svancara.net/files/ICAART_2017_46_CR.pdf",
FLAGS= ":2017:,:jirisvancara:,:pavelsurynek:",
ABSTRACT=
"We address the problem of optimal multi-agent path finding (MAPF) in this
paper. The task is to find a set of actions for each agent in know terrain so
that each agent arrives to its desired destination from a given starting
position. Agents are not allowed to collide with each other along their
paths. Furthermore, a solution that minimizes the total time is required. In
this paper we study search-based algorithms that systematically explore state
space. These algorithms require a good heuristic function that can improve the
computational effectiveness by changing the order in which the states are
expanded. We propose such new heuristic, which is based on relaxation of MAPF
solving via its reduction to multi-commodity flow over time expanded graph.
The multi-commodity flow is relaxed to single commodity flow, which can be
solved in polynomial time. We show that our new heuristic is monotone and
therefore can be used in search-based algorithms effectively. We also give
theoretical analysis of the new heuristic and compare it experimentally with
base-line heuristics that are often used."
}
@INPROCEEDINGS{JSvan17c,
AUTHOR= "R. Barak and N. Zhou and R. Stern and E. Boyarski and P. Surynek",
TITLE= "Modeling and Solving the Multi-Agent Pathfinding Problem in {Picat}",
BOOKTITLE= "Proceedings of the International Conference on Tools with Artificial Intelligence (ICTAI)",
PAGES= "959--966",
YEAR= "2017",
PDF= "http://www.picat-lang.org/papers/ictai17.pdf",
FLAGS= ":2017:,:romanbartak:,:ronistern:,:pavelsurynek:,:eliboyarski:",
ABSTRACT=
"The multi-agent pathfinding (MAPF) problem has attracted considerable
attention because of its relation to practical applications. In this paper, we
present a constraint-based declarative model for MAPF, together with its
implementation in Picat, a logic-based programming language. We show
experimentally that our Picat-based implementation is highly competitive and
sometimes outperforms previous approaches. Importantly, the proposed Picat
implementation is very versatile. We demonstrate this by showing how it can be
easily adapted to optimize different MAPF objectives, such as minimizing
makespan or minimizing the sum of costs, and for a range of MAPF
variants. Moreover, a Picat-based model can be automatically compiled to
several general-purpose solvers such as SAT solvers and Mixed Integer
Programming solvers (MIP). This is particularly important for MAPF because
some MAPF variants are solved more efficiently when compiled to SAT while
other variants are solved more efficiently when compiled to MIP. We analyze
these differences and the impact of different declarative models and encodings
on empirical performance."
}
@ARTICLE{PSury18a,
AUTHOR= "A. Botea and D. Bonusi and P. Surynek",
TITLE= "Solving Multi-Agent Path Finding on Strongly Biconnected Digraphs",
JOURNAL= "Journal of Artificial Intelligence Research",
VOLUME= "62",
NUMBER= "06/18",
PAGES= "273--314",
YEAR= "2018",
PDF= "https://jair.org/index.php/jair/article/download/11212/26423",
FLAGS= ":2018:,:adibotea:,:pavelsurynek:",
ABSTRACT=
"Much of the literature on suboptimal, polynomial-time algorithms for
multi-agent path finding focuses on undirected graphs, where motion is
permitted in both directions along a graph edge. Despite this, traveling on
directed graphs is relevant in navigation domains, such as path finding in
games, and asymmetric communication networks. We consider multi-agent path
finding on strongly biconnected directed graphs. We show that all instances
with at least two unoccupied positions have a solution, except for a
particular, degenerate subclass where the graph has a cyclic shape. We present
diBOX, an algorithm for multi-agent path finding on strongly biconnected
directed graphs. diBOX runs in polynomial time, computes suboptimal solutions
and is complete for instances on strongly biconnected digraphs with at least
two unoccupied positions. We theoretically analyze properties of the algorithm
and properties of strongly biconnected directed graphs that are relevant to
our approach. We perform a detailed empirical analysis of diBOX, showing a
good scalability. To our knowledge, our work is the first study of multi-agent
path finding focused on directed graphs."
}
@ARTICLE{PSury17a,
AUTHOR= "P. Surynek",
TITLE= "Time-Expanded Graph-Based Propositional Encodings for Makespan-Optimal Solving of Cooperative Path Finding Problems",
JOURNAL= "Annals of Mathematics and Artificial Intelligence",
VOLUME= "81",
NUMBER= "3--4",
PAGES= "329--375",
YEAR= "2017",
PDF= "http://surynek.com/publications/files/SurynekPavel_Time-Expansion-CPF-SAT_AMAI-Preprint-2017.pdf",
FLAGS= ":2017:,:pavelsurynek:",
ABSTRACT=
"This paper deals with solving cooperative pathfinding (CPF) problems in a
makespan-optimal way. A feasible solution to the CPF problem lies in the
moving of mobile agents where each agent has unique initial and goal
positions. The abstraction adopted in CPF assumes that agents are discrete
units that move over an undirected graph by traversing its edges. We focus
specifically on makespan-optimal solutions to the CPF problem where the task
is to generate solutions that are as short as possible in terms of the total
number of time steps required for all agents to reach their goal positions. We
demonstrate that reducing CPF to propositional satisfiability (SAT) represents
a viable way to obtain makespan-optimal solutions. Several ways of encoding
CPFs into propositional formulae are proposed and evaluated both theoretically
and experimentally. Encodings based on the log and direct representations of
decision variables are compared. The evaluation indicates that SAT-based
solutions to CPF outperform the makespan-optimal versions of such search-based
CPF solvers such as OD+ID,CBS, and ICTS in highly constrained scenarios (i.e.,
environments that are densely occupied by agents and where interactions among
the agents are frequent). Moreover, the experiments clearly show that CPF
encodings based on the direct representation of variables can be solved
faster, although they are less space-efficient than log encodings."
}
@ARTICLE{PSury16a,
AUTHOR= "P. Surynek and P. Michalik",
TITLE= "The Joint Movement of Pebbles in Solving the (N^2-1)-Puzzle Suboptimally and its Applications in Rule-Based Cooperative Path-Finding",
JOURNAL= "Autonomous Agents and Multi-Agent Systems",
VOLUME= "31",
NUMBER= "3",
PAGES= "715-763",
YEAR= "2016",
PDF= "http://surynek.com/publications/files/Surynek-Michalik_Puzzle_Preprint-arXiv-2016.pdf",
FLAGS= ":2016:,:pavelsurynek:,:petrmichalik:",
ABSTRACT=
"The problem of solving (N^2−1)-puzzle and cooperative path-finding (CPF)
sub-optimally by rule-based algorithms is addressed in this manuscript. The
task in the puzzle is to rearrange N^2−1 pebbles on the square grid of the
size of NxN using one vacant position to a desired goal configuration. An
improvement to the existent polynomial-time algorithm is proposed and
experimentally analyzed. The improved algorithm is trying to move pebbles in a
more efficient way than the original algorithm by grouping them into so-called
snakes and moving them jointly within the snake. An experimental evaluation
showed that the algorithm using snakes produces solutions that are 8 to 9
percent shorter than solutions generated by the original algorithm."
}
@INPROCEEDINGS{PSury15a,
AUTHOR= "P. Surynek",
TITLE= "Reduced Time-Expansion Graphs for Solving Cooperative Path Finding Sub-Optimally",
BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)",
PAGES= "1916--1922",
YEAR= "2015",
PDF= "http://surynek.com/publications/files/SurynekPavel_Reduced-Code_IJCAI-2015.pdf",
FLAGS= ":2015:,:pavelsurynek:",
ABSTRACT=
"Solving cooperative path finding (CPF) by translating it to propositional
satisfiability represents a viable option in highly constrained situations.
The task in CPF is to relocate agents from their initial positions to given
goals in a collision free manner. In this paper, we propose a reduced time
expansion that is focused on makespan sub-optimal solving. The suggested
reduced time expansion is especially beneficial in conjunction with a goal
decomposition where agents are relocated one by one."
}
@INPROCEEDINGS{PSury14a,
AUTHOR= "P. Surynek",
TITLE= "Compact Representations of Cooperative Path-Finding as {SAT} Based on Matchings in Bipartite Graphs",
BOOKTITLE= "Proceedings of the 26th International Conference on Tools with Artificial Intelligence (ICTAI)",
PAGES= "875--882",
YEAR= "2014",
PDF= "http://surynek.com/publications/files/SurynekPavel_Matching-Code_ICTAI-2014.pdf",
FLAGS= ":2014:,:pavelsurynek:",
ABSTRACT=
"This paper addresses makespan optimal solving of cooperative path-finding
problem (CPF) by translating it to propositional satisfiability (SAT). The
task is to relocate set of agents to given goal positions so that they do not
collide with each other. A novel SAT encoding of CPF is suggested. The novel
encoding uses the concept of matching in a bipartite graph to separate spatial
constraint of CPF from consideration of individual agents. The separation
allowed reducing the size of encoding significantly. The conducted
experimental evaluation shown that novel encoding can be solved faster than
existing encodings for CPF and also that the SAT based methods dominates over
A* based methods in environment densely occupied by agents."
}
@INPROCEEDINGS{PSury14b,
AUTHOR= "M. Ivanova and P. Surynek",
TITLE= "Adversarial Cooperative Path-Finding: Complexity and Algorithms",
BOOKTITLE= "Proceedings of the International Conference on Tools with Artificial Intelligence (ICTAI)",
PAGES= "75--82",
YEAR= "2014",
PDF= "http://surynek.com/publications/files/Ivanova-Surynek_ACPF_ICTAI-2014.pdf",
FLAGS= ":2014:,:pavelsurynek:,:marikaivanova:",
ABSTRACT=
"The paper addresses a problem of adversarial co-operative path-finding (ACPF)
which extends the well-studied problem of cooperative path-finding (CPF) with
adversaries. In addition to cooperative path-finding where non-colliding paths
for multiple agents connecting their initial positions and destinations are
searched, consideration of agents controlled by the adversary is included in
ACPF. This work is focused on both theoretical properties and practical
solving techniques of the considered problem. We study computational
complexity of the problem where we show that it is PSPACE-hard and belongs to
the EXPTIME complexity class. Possible methods suitable for practical solving
of the problem are introduced and thoroughly evaluated. Suggested solving
approaches include greedy algorithms, minimax methods, Monte Carlo Tree
Search, and adaptation of an algorithm for the cooperative version of the
problem. Solving methods for ACPF were compared in a tournament in which all
the pairs of suggested strategies were compared. Surprisingly frequent
success rate of greedy methods and rather weaker results of Monte Carlo Tree
Search were indicated by the conducted experimental evaluation."
}
@ARTICLE{PSury14c,
AUTHOR= "P. Surynek",
TITLE= "On the Complexity of Optimal Parallel Cooperative Path-Finding",
JOURNAL= "Fundamenta Informaticae",
VOLUME="137",
NUMBER="4",
PAGES= "517--548",
YEAR= "2014",
PDF= "http://surynek.com/publications/files/SurynekPavel_Multirobots-Theory_FundInf-2014.pdf",
FLAGS= ":2014:,:pavelsurynek:",
ABSTRACT=
"A parallel version of the problem of cooperative path-finding (pCPF) is
introduced in this paper. The task in CPF is to determine a spatial-temporal
plan for each member of a group of agents. Each agent is given its initial
location in the environment and its task is to reach the given goal
location. Agents must avoid obstacles and must not collide with one
another. The environment where agents are moving is modeled as an undirected
graph. Agents are placed in vertices and they move along edges. At most one
agent is placed in each vertex and at least one vertex remains unoccupied. An
agent can only move into a currently unoccupied vertex in the standard version
of CPF. In the parallel version, an agent can also move into a vertex being
currently vacated by another agent supposing the character of this movement is
not cyclic. The optimal pCPF where the task is to find the smallest possible
solution of the makespan is particularly studied. The main contribution of
this paper is the proof of NP-completeness of the decision version of the
optimal pCPF. A reduction of propositional satisfiability (SAT) to the problem
is used in the proof."
}
@ARTICLE{PSury14d,
AUTHOR= "P. Surynek",
TITLE= "Solving Abstract Cooperative Path-Finding in Densely Populated Environments",
JOURNAL= "Computational Intelligence",
VOLUME= "30",
NUMBER= "2",
PAGES= "402--450",
YEAR= "2014",
PDF= "http://surynek.com/publications/files/SurynekPavel_Multirobots-BIBOX_COIN-2012.pdf",
FLAGS= ":2014:,:pavelsurynek:",
ABSTRACT=
"The problem of cooperative path-finding is addressed in this work. A set of
agents moving in a certain environment is given. Each agent needs to reach a
given goal location. The task is to find spatial temporal paths for agents
such that they eventually reach their goals by following these paths without
colliding with each other. An abstraction where the environment is modeled as
an undirected graph is adopted - vertices represent locations and edges
represent passable regions. Agents are modeled as elements placed in the
vertices while at most one agent can be located in a vertex at a time. At
least one vertex remains unoccupied to allow agents to move. An agent can
move into unoccupied neighboring vertex or into a vertex being currently
vacated if a certain additional condition is satisfied. Two novel scalable
algorithms for solving cooperative path-finding in bi-connected graphs are
presented. Both algorithms target environments that are densely populated by
agents. A theoretical and experimental evaluation shows that suggested
algorithms represent a viable alternative to search based techniques as well
as to techniques exploiting permutation groups on the studied class of the
problem."
}
@INPROCEEDINGS{PSury14e,
AUTHOR= "P. Surynek",
TITLE= "Towards Optimal Cooperative Path Planning in Hard Setups through Satisfiability Solving",
BOOKTITLE= "Proceedings of the Pacific Rim International Conference on Artificial Intelligence (PRICAI)",
PAGES= "564--576",
YEAR= "2012",
PDF= "http://surynek.com/publications/files/SurynekPavel_Cooperative-Compression-SAT_PRICAI-2012.pdf",
FLAGS= ":2012:,:pavelsurynek:",
ABSTRACT=
"A novel approach to cooperative path-planning is presented. A SAT solver is
used not to solve the whole instance but for optimizing the makespan of a
sub-optimal solution. This approach is trying to exploit the ability of
state-of-the-art SAT solvers to give a solution to relatively small instance
quickly. A sub-optimal solution to the instance is obtained by some existent
method first. It is then submitted to the optimization process which
decomposes it into small subsequences for which optimal solutions are found by
a SAT solver. The new shorter solution is subsequently obtained as
concatenation of optimal sub-solutions. The process is iterated until a fixed
point is reached. This is the first method to produce near optimal solutions
for densely populated environments; it can be also applied to
domain-independent planning supposed that sub-optimal planner is available."
}
@INPROCEEDINGS{PSury09a,
AUTHOR= "P. Surynek",
TITLE= "A Novel Approach to Path Planning for Multiple Robots in Bi-Connected Graphs",
BOOKTITLE= "Proceedings of the International Conference on Robotics and Automation (ICRA)",
PAGES= "3613--3619",
YEAR= "2009",
PDF= "http://surynek.com/publications/files/SurynekPavel_BIBOX_ICRA-2009.pdf",
FLAGS= ":2009:,:pavelsurynek:",
ABSTRACT=
"This paper addresses a problem of path planning for multiple robots. An
abstraction where the environment for robots is modeled as an undirected graph
with robots placed in its vertices is used (this abstraction is also known as
the problem of pebble motion on graphs). A class of the problem with
bi-connected graph and at least two unoccupied vertices is defined. A novel
polynomial-time solution algorithm for this class of problem is proposed. It
is shown in the paper that the new algorithm significantly outperforms the
existing state-of-the-art techniques applicable to the problem. Moreover, the
performed experimental evaluation indicates that the new algorithm scales up
well which make it suitable for practical problem solving."
}
@INPROCEEDINGS{ABote18a,
AUTHOR= "A. Botea and D. Bonusi and P. Surynek",
TITLE= "Solving Multi-Agent Path Finding on Strongly Biconnected Digraphs",
BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)",
YEAR= "2018",
PAGES= "5563--5567",
PDF= "https://www.ijcai.org/proceedings/2018/785",
FLAGS= ":2018:,:adibotea:,:pavelsurynek:",
ABSTRACT=
"We present and evaluate diBOX, an algorithm for multi-agent path finding on
strongly biconnected directed graphs. diBOX runs in polynomial time, computes
suboptimal solutions and is complete for instances on strongly biconnected
digraphs with at least two unoccupied positions. A detailed empirical analysis
shows a good scalability for diBOX."
}
@INPROCEEDINGS{ABote17a,
AUTHOR= "F. Xie and A. Botea and A. Kishimoto",
TITLE= "A Scalable Approach to Chasing Multiple Moving Targets with Multiple Agents",
BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)",
YEAR= "2017",
PAGES= "4470--4476",
PDF= "https://www.ijcai.org/proceedings/2017/624",
FLAGS= ":2017:,:adibotea:",
ABSTRACT=
"Chasing multiple mobile targets with multiple agents is important in several
applications, such as computer games and police chasing scenarios. Existing
approaches can compute optimal policies. However, they have a limited
scalability, as they implement expensive minimax searches. We introduce a
sub-optimal but scalable approach that assigns individual agents to individual
targets and that can dynamically re-compute such assignments. We provide a
theoretical analysis, including upper bounds on the number of time steps
required to solve an instance. In a detailed empirical evaluation on grid
maps, our algorithm scales up very convincingly beyond the limits of previous
methods. On small problems, where a comparison to a minimax approach is
possible, the results demonstrate a good solution quality for our method."
}
@INPROCEEDINGS{ABote15a,
AUTHOR= "A. Botea and P. Surynek",
TITLE= "Multi-Agent Path Finding on Strongly Biconnected Digraphs",
BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)",
YEAR= "2015",
PAGES= "2024--2030",
PDF= "https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/download/9653/9499",
FLAGS= ":2015;,:adibotea:,:pavelsurynek:",
ABSTRACT=
"Much of the literature on multi-agent path finding focuses on undirected
graphs, where motion is permitted in both directions along a graph
edge. Despite this, travelling on directed graphs is relevant in navigation
domains, such as pathfinding in games, and asymmetric communication
networks. We consider multi-agent path finding on strongly biconnected
directed graphs. We show that all instances with at least two unoccupied
positions can be solved or proven unsolvable. We present a polynomial-time
algorithm for this class of problems, and analyze its complexity. Our work may
be the first formal study of multi-agent path finding on directed graphs."
}
@INPROCEEDINGS{ABote14a,
AUTHOR= "C. Wilt and A. Botea",
TITLE= "Spatially Distributed Multiagent Path Planning",
BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)",
YEAR= "2014",
PAGES= "332--340",
PDF= "http://www.chriswilt.com/papers/wilt_icaps_14.pdf",
FLAGS= ":2014:,:adibotea:",
ABSTRACT=
"Multiagent path planning is important in a variety of fields, ranging from
games to robotics and warehouse management. Although centralized control in
the joint action space can provide optimal plans, this often is
computationally infeasible. Decoupled planning is much more scalable.
Traditional decoupled approaches perform a unit-centric decomposition,
replacing a multi-agent search with a series of single-agent searches, one for
each mobile unit. We introduce an orthogonal, significantly different
approach, following a spatial distribution that partitions a map into
highcontention, bottleneck areas and low-contention areas. Local agents called
controllers are in charge with one local area each, routing mobile units in
their corresponding area. Distributing the knowledge across the map, each
controller can observe only the state of its own area. Adjacent controllers
can communicate to negotiate the transfer of mobile units. We evaluate our
implemented algorithm, SDP, on real game maps with a mixture of larger areas
and narrow, bottleneck gateways. The results demonstrate that spatially
distributed planning can have substantial benefits in terms of makespan
quality and computation speed."
}
@INPROCEEDINGS{ABote11a,
AUTHOR= "C. Wang and A. Botea",
TITLE= "{MAPP}: A Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees",
JOURNAL= "Journal of Artificial Intelligence Research (JAIR)",
VOLUME="42",
NUMBER="1",
YEAR= "2011",
PAGES= "55--90",
PDF= "http://abotea.rsise.anu.edu.au/data/wang-botea-jair11.pdf",
FLAGS= ":2011:,:adibotea:,:cindywang:",
ABSTRACT=
"Multi-agent path planning is a challenging problem with numerous real-life
applications. Running a centralized search such as A* in the combined state
space of all units is complete and cost-optimal, but scales poorly, as the
state space size is exponential in the number of mobile units. Traditional
decentralized approaches, such as FAR and WHCA*, are faster and more scalable,
being based on problem decomposition. However, such methods are incomplete and
provide no guarantees with respect to the running time or the solution
quality. They are not necessarily able to tell in a reasonable time whether
they would succeed in finding a solution to a given instance. We introduce
MAPP, a tractable algorithm for multi-agent path planning on undirected
graphs. We present a basic version and several extensions. They have
low-polynomial worst-case upper bounds for the running time, the memory
requirements, and the length of solutions. Even though all algorithmic
versions are incomplete in the general case, each provides formal guarantees
on problems it can solve. For each version, we discuss the algorithm's
completeness with respect to clearly defined subclasses of instances.
Experiments were run on realistic game grid maps. MAPP solved 99.86 percent of
all mobile units, which is 18-22 percent better than the percentage of FAR and
WHCA*. MAPP marked 98.82 percent of all units as provably solvable during the
first stage of plan computation. Parts of MAPP's computation can be re-used
across instances on the same map. Speed-wise, MAPP is competitive or
significantly faster than WHCA*, depending on whether MAPP performs all
computations from scratch. When data that MAPP can re-use are preprocessed
offline and readily available, MAPP is slower than the very fast FAR algorithm
by a factor of 2.18 on average. MAPP's solutions are on average 20 percent
longer than FAR's solutions and 7-31 percent longer than WHCA*'s solutions." }
@INPROCEEDINGS{ABote11b,
AUTHOR= "C. Wang and A. Botea and P. Kilby",
TITLE= "On Improving the Quality of Solutions in Large-Scale Cooperative Multi-Agent Pathfinding",
BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)",
YEAR= "2011",
PAGES= "",
PDF= "http://abotea.rsise.anu.edu.au/data/ko-hsin-etal-socs11.pdf",
FLAGS= ":2011:,:adibotea:,:cindywang:",
ABSTRACT=
"N/A"
}
@INPROCEEDINGS{ABote11c,
AUTHOR= "C. Wang and A. Botea and P. Kilby",
TITLE= "Solution Quality Improvements for Massively Multi-Agent Pathfinding",
BOOKTITLE= "Proceedings of the AAAI Conference on Artificial Intelligence (AAAI)",
YEAR= "2011",
PAGES= "1824--1825",
PDF= "http://abotea.rsise.anu.edu.au/data/ko-hsin-etal-stud-abstract-aaai11.pdf",
FLAGS= ":2011:,:adibotea:,:cindywang:",
ABSTRACT=
"N/A"
}
@INPROCEEDINGS{ABote10,
AUTHOR= "C. Wang and A. Botea",
TITLE= "Scalable Multi-Agent Pathfinding on Grid Maps with Tractability and Completeness Guarantees",
BOOKTITLE= "Proceedings of the European Conference on Artificial Intelligence (ECAI)",
YEAR= "2010",
PAGES= "977--978",
PDF= "http://abotea.rsise.anu.edu.au/data/wang-botea-ecai10.pdf",
FLAGS= ":2010:,:adibotea:,:cindywang:",
ABSTRACT=
"N/A"}
@INPROCEEDINGS{ABote09,
AUTHOR= "C. Wang and A. Botea",
TITLE= "Tractable Multi-Agent Path Planning on Grid Maps",
BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)",
YEAR= "2009",
PAGES= "1870--1875",
PDF= "http://users.rsise.anu.edu.au/~cwang/ijcai09-paper.pdf",
FLAGS= ":2009:,:adibotea:,:cindywang:",
ABSTRACT=
"Multi-agent path planning on grid maps is a challenging problem and has
numerous real-life applications. Running a centralized, systematic search such
as A* is complete and cost-optimal but scales up poorly in practice, since
both the search space and the branching factor grow exponentially in the
number of mobile units. Decentralized approaches, which decompose a problem
into several subproblems, can be faster and can work for larger problems.
However, existing decentralized methods offer no guarantees with respect to
completeness, running time, and solution quality. To address such limitations,
we introduce MAPP, a tractable algorithm for multi-agent path planning on grid
maps. We show that MAPP has low-polynomial worst-case upper bounds for the
running time, the memory requirements, and the length of solutions. As it runs
in low-polynomial time, MAPP is incomplete in the general case. We identify a
class of problems for which our algorithm is complete. We believe that this is
the first study that formalises restrictions to obtain a tractable class of
multi-agent path planning problems."
}
@INPROCEEDINGS{ABote08,
AUTHOR= "C. Wang and A. Botea",
TITLE= "Fast and Memory-Efficient Multi-Agent Pathfinding",
BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)",
YEAR= "2008",
PAGES= "380--387",
PDF= "http://users.rsise.anu.edu.au/~cwang/icaps08-paper.pdf",
FLAGS= ":2008:,:adibotea:,:cindywang:",
ABSTRACT=
"Multi-agent path planning has been shown to be a PSPACE-hard problem. Running
a complete search such as A* at the global level is often intractable in
practice, since both the number of states and the branching factor grow
exponentially as the number of mobile units increases. In addition to the
inherent difficulty of the problem, in many real-life applications such as
computer games, solutions have to be computed in real time, using limited CPU
and memory resources. In this paper we introduce FAR (Flow Annotation
Replanning), a method for multi-agent path planning on grid maps. When
building a search graph from a grid map, FAR implements a flow restriction
idea inspired by road networks. The movement along a given row (or column) is
restricted to only one direction, avoiding head-to-head collisions. The
movement direction alternates from one row (or column) to the next. Additional
rules ensure that two locations reachable from each other on the original map
remain connected (in both directions) in the graph. After building the search
graph, an A* search is independently run for each mobile unit. During plan
execution, deadlocks are detected as cycles of units that wait for each other
to move. A heuristic procedure for deadlock breaking attempts to repair plans
locally, instead of running a larger scale, more expensive replanning
step. Experiments are run on a collection of maps extracted from Baldur's
Gate, a popular commercial computer game. We compare FAR with WHCA*, a recent
successful algorithm for multi-agent path planning on grid maps. FAR is shown
to run significantly faster, use much less memory, and scale up to problems
with more mobile units."
}
@INPROCEEDINGS{NStur21a,
AUTHOR= "T. Walker and N. Sturtevant and A. Felner and H. Zhang and J. Li and S. Kumar",
TITLE= "Conflict-Based Increasing Cost Search",
BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)",
PAGES= "385--395",
YEAR= "2021",
PDF= "https://ojs.aaai.org/index.php/ICAPS/article/download/15984/15795",
FLAGS= ":2021:,:thaynewalker:,:nathansturtevant:,:arielfelner:,:hanzhang:,:jiaoyangli:,:satishkumar:",
ABSTRACT=
"Two popular optimal search-based solvers for the multi-agent pathfinding
(MAPF) problem, Conflict-Based Search (CBS) and Increasing Cost Tree Search
(ICTS), have been extended separately for continuous time domains and symmetry
breaking. However, an approach to symmetry breaking in continuous time domains
remained elusive. In this work, we introduce a new algorithm, Conflict-Based
Increasing Cost Search (CBICS), which is capable of symmetry breaking in
continuous time domains by combining the strengths of CBS and ICTS. Our
experiments show that CBICS often finds solutions faster than CBS and ICTS in
both unit time and continuous time domains."
}
@ARTICLE{NStur19a,
AUTHOR= "T. Walker and N. Sturtevant",
TITLE= "Collision Detection for Agents in Multi-Agent Pathfinding",
JOURNAL= "arXiv preprint arXiv:1908.09707",
YEAR= "2019",
PDF= "https://arxiv.org/pdf/1908.09707",
FLAGS= ":2019:,:thaynewalker:,:nathansturtevant:",
ABSTRACT=
"Recent work on the multi-agent pathfinding problem (MAPF) has begun to study
agents with motion that is more complex, for example, with non-unit action
durations and kinematic constraints. An important aspect of MAPF is collision
detection. Many collision detection approaches exist, but often suffer from
issues such as high computational cost or causing false negative or false
positive detections. In practice, these issues can result in problems that
range from inefficiency and annoyance to catastrophic. The main contribution
of this technical report is to provide a high-level overview of major
categories of collision detection, along with methods of collision detection
and anticipatory collision avoidance for agents that are both computationally
efficient and highly accurate."
}
@INPROCEEDINGS{NStur18a,
AUTHOR= "T. Walker and N. Sturtevant and A. Felner",
TITLE= "Extended Increasing Cost Tree Search for Non-Unit Cost Domains",
BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)",
PAGES= "534--540",
YEAR= "2018",
PDF= "https://docs.wixstatic.com/ugd/749b4b_9c2bd2dc3b9147199e2a9c6358245756.pdf",
FLAGS= ":2018:,:thaynewalker:,:nathansturtevant:,:arielfelner:",
ABSTRACT=
"Multi-agent pathﬁnding (MAPF) has applications in navigation, robotics, games
and planning. Most work on search-based optimal algorithms for MAPF has
focused on simple domains with unit cost actions and unit time steps. Although
these constraints keep many aspects of the algorithms simple, they also
severely limit the domains that can be used. In this paper we introduce a new
definition of the MAPF problem for non-unit cost and non-unit time step
domains along with new multiagent state successor generation schemes for these
domains. Finally, we deﬁne an extended version of the increasing cost tree
search algorithm (ICTS) for non-unit costs, with two new sub-optimal variants
of ICTS: epsilon-ICTS and w-ICTS. Our experiments show that higher quality
sub-optimal solutions are achievable in domains with ﬁnely discretized
movement models in no more time than lower-quality, optimal solutions in
domains with coarsely discretized movement models."
}
@INPROCEEDINGS{NStur17a,
AUTHOR= "T. Walker and D. Chan and N. Sturtevant",
TITLE= "Using Hierarchical Constraints to Avoid Conflicts in Multi-Agent Pathfinding",
BOOKTITLE= "Proceedings of the International Conference on Automated Planning and Scheduling (ICAPS)",
PAGES= "316--324",
YEAR= "2017",
PDF= "http://www.cs.du.edu/~sturtevant/papers/walker2017hierarchical.pdf",
FLAGS= ":2017:,:thaynewalker:,davidchan:,:nathansturtevant:",
ABSTRACT=
"Recent work in multi-agent path planning has provided a number of optimal and
suboptimal solvers that can efficiently find solutions to problems of growing
complexity. Solvers based on Conflict-Based Search (CBS) combine single-agent
solvers with shared constraints between agents to find feasible
solutions. Suboptimal variants of CBS introduce alternate heuristics to avoid
conflicts. In this paper we study the multi-agent planning problem in the
context of non-holonomic vehicles planning on a lattice. We propose that in
addition to using heuristics to avoid conflicts, we can plan using a hierarchy
of movement constraints to efficiently avoid conflicts. We develop a new
extension to the CBS algorithm, CBS with constraint layering (CBS+CL), which
iteratively applies different movement constraint models during the CBS
planning process. Our results show that this approach allows us to solve for
about 2.4 times more agents in the same amount of time when compared to
regular CBS without using a constraint hierarchy."
}
@INPROCEEDINGS{NStur11a,
AUTHOR= "M. Khorshid and R. Holte and N. Sturtevant",
TITLE= "A Polynomial-Time Algorithm for Non-Optimal Multi-Agent Pathfinding",
BOOKTITLE= "Proceedings of the Symposium on Combinatorial Search (SoCS)",
PAGES= "76--83",
YEAR= "2011",
PDF= "http://www.aaai.org/ocs/index.php/SOCS/SOCS11/paper/viewFile/4039/4361",
FLAGS= ":2011:,:robertholte:,:nathansturtevant:",
ABSTRACT=
"Multi-agent pathﬁnding, where multiple agents must travelto their goal
locations without getting stuck, has been studied in both theoretical and
practical contexts, with a variety of both optimal and sub-optimal algorithms
proposed for solving problems. Recent work has shown that there is a
lineartime check for whether a multi-agent pathﬁnding problem can be solved in
a tree, however this was not used to actually produce solutions. In this paper
we provide a constructive proof of how to solve multi-agent pathﬁnding
problems in a tree that culminates in a novel approach that we call the
tree-based agent swapping strategy (TASS). Experimental results showed that
TASS can ﬁnd solutions to the multi-agent pathﬁnding problem on a highly
crowded tree with 1000 nodes and 996 agents in less than 8 seconds. These
results are far more efﬁcient and general than existing work, suggesting that
TASS is a productive line of study for multiagent pathﬁnding."
}
@INPROCEEDINGS{NStur08a,
AUTHOR= "M. Jansen and N. Sturtevant",
TITLE= "Direction Maps for Cooperative Pathfinding",
BOOKTITLE= "Proceedings of the Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE)",
PAGES= "185--190",
YEAR= "2008",
PDF= "http://www.cs.du.edu/~sturtevant/papers/aiide_dm.pdf",
FLAGS= ":2008:,:nathansturtevant:",
ABSTRACT=
"Cooperative behavior is a desired trait in many ﬁelds from computer games to
robotics. Yet, achieving cooperative behavior is often difﬁcult, as
maintaining shared information about the dynamics of agents in the world can
be complex. We focus on the speciﬁc task of cooperative pathﬁnding and
introduce a new approach based on the idea of 'direction maps' that learns
about the movement of agents in the world. This learned data then is used to
produce implicit cooperation between agents. This approach is less expensive
and has better performance than several existing cooperative algorithms."
}
@INPROCEEDINGS{NStur08b,
AUTHOR= "M. Jansen and N. Sturtevant",
TITLE= "A New Approach to Cooperative Pathfinding",
BOOKTITLE= "Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS)",
PAGES= "1401--1404",
YEAR= "2008",
ORGANIZATION= "International Foundation for Autonomous Agents and Multiagent Systems",
PDF= "http://www.cs.du.edu/~sturtevant/papers/coop_path.pdf ",
FLAGS= ":2008:,:nathansturtevant:",
ABSTRACT=
"In the multi-agent pathﬁnding problem, groups of agents need to plan paths
between their respective start and goal locations in a given environment,
usually a two-dimensional map. Existing approaches to this problem include
using static or dynamic information to help coordination. However, the
resulting behaviour is not always desirable, in that too much information is
hand-coded into the problem, agents take paths which look unintelligent, or
because the agents collide and must re-plan frequently. We present a
distributed approach in which agents share information about the direction in
which they traveled when passing through each location. This information is
then used to encourage agents passing through the same location to travel in
the same direction as previous agents. In addition to this new approach, we
present performance metrics for multi-agent path planning as well as
experimental results for the new approach. These results indicate that the
number of collisions between agents is reduced and that the visual ﬁdelity is
improved."
}
@INPROCEEDINGS{NStur06a,
AUTHOR= "N. Sturtevant and M. Buro",
TITLE= "Improving Collaborative Pathfinding using Map Abstraction",
BOOKTITLE= "Proceedings of the Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE)",
PAGES= "80--85",
YEAR= "2006",
PDF= " http://www.cs.du.edu/~sturtevant/papers/CPRA.pdf",
FLAGS= ":2006:,:nathansturtevant:",
ABSTRACT=
"In this paper we combine recent pathﬁnding research on spatial abstractions,
partial reﬁnement, and space-time reservations to construct new collaborative
pathﬁnding algorithms. We ﬁrst present an enhanced version of WHCA* and then
show how the ideas from WHCA* can be combined with PRA* to form CPRA*. These
algorithms are shown to effectively plan trajectories for many objects
simultaneously while avoiding collisions, as the original WHCA* does. These
new algorithms are not only faster than WHCA* but also use less memory."
}
@INPROCEEDINGS{Nguy17a,
AUTHOR= "V. Nguyen and P. Obermeier and T. Son and T. Schaub and W. Yeoh",
TITLE= "Generalized Target Assignment and Path Finding Using Answer Set Programming",
BOOKTITLE= "Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)",
PAGES= "1216--1223",
YEAR= "2017",
PDF= "https://www.ijcai.org/proceedings/2017/0169.pdf",
FLAGS= ":2017:",
ABSTRACT=
"In Multi-Agent Path Finding (MAPF), a team of agents needs to find
collision-free paths from their starting locations to their respective
targets. Combined Target Assignment and Path Finding (TAPF) extends
MAPF by including the problem of assigning targets to agents as a
precursor to the MAPF problem. A limitation of both models is their
assumption that the number of agents and targets are equal, which is
invalid in some applications such as autonomous warehouse systems. We
address this limitation by generalizing TAPF to allow for (1) unequal
number of agents and tasks; (2) tasks to have deadlines by which they
must be completed; (3) ordering of groups of tasks to be completed;
and (4) tasks that are composed of a sequence of checkpoints that must
be visited in a specific order. Further, we model the problem using
answer set programming (ASP) to show that customizing the desired
variant of the problem is simple one only needs to choose the
appropriate combination of ASP rules to enforce it. We also
demonstrate experimentally that if problem specific information can be
incorporated into the ASP encoding then ASP based method can be
efficient and can scale up to solve practical applications."
}