More Web Proxy on the site http://driver.im/

Article

Free access

Efficient SAT approach to multi-agent path finding under the sum of costs objective

Authors:

Eli BoyarskiAuthors Info & Claims

ECAI'16: Proceedings of the Twenty-second European Conference on Artificial Intelligence

Pages 810 - 818

https://doi.org/10.3233/978-1-61499-672-9-810

Published: 29 August 2016 Publication History

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 sum-of-costs search solvers - the ICTS and ICBS algorithms.

References

[1]

G. Audemard, J. Lagniez, and L. Simon, 'Improving glucose for incremental SAT solving with assumptions: Application to MUS extraction', in Theory and Applications of Satisfiability Testing - SAT 2013, pp. 309-317, (2013).

Digital Library

[2]

G. Audemard and L. Simon, 'Predicting learnt clauses quality in modern SAT solvers', in IJCAI, pp. 399-404, (2009).

Digital Library

[3]

O. Bailleux and Y. Boufkhad, 'Efficient CNF encoding of boolean cardinality constraints', in CP, pp. 108-122, (2003).

Digital Library

[4]

A. Biere, A. Biere, M. Heule, H. van Maaren, and T. Walsh, Handbook of Satisfiability: Volume 185 Frontiers in Artificial Intelligence and Applications, IOS Press, 2009.

Digital Library

[5]

E. Boyarski, A. Felner, R. Stern, G. Sharon, D. Tolpin, O. Betzalel, and S. Shimony, 'ICBS: improved conflict-based search algorithm for multi-agent pathfinding', in IJCAI, pp. 740-746, (2015).

Digital Library

[6]

L. Cohen, T. Uras, and S. Koenig, 'Feasibility study: Using highways for bounded-suboptimal mapf', in SOCS, pp. 2-8, (2015).

[7]

B. de Wilde, A. ter Mors, and C. Witteveen, 'Push and rotate: a complete multi-agent pathfinding algorithm', JAIR, 51, 443-492, (2014).

[8]

K. Dresner and P. Stone, 'A multiagent approach to autonomous intersection management', JAIR, 31, 591-656, (2008).

[9]

E. Erdem, D. G. Kisa, U. Oztok, and P. Schueller, 'A general formal framework for pathfinding problems with multiple agents', in AAAI, (2013).

Digital Library

[10]

M. Goldenberg, A. Felner, R. Stern, G. Sharon, N. Sturtevant, R. Holte, and J. Schaeffer, 'Enhanced partial expansion A*', JAIR, 50, 141-187, (2014).

Digital Library

[11]

M. Järvisalo, D. Le Berre, O. Roussel, and L. Simon, 'The international SAT solver competitions', AI Magazine, 33(1), (2012).

[12]

M. M. Khorshid, R. C. Holte, and N. R. Sturtevant, 'A polynomial-time algorithm for non-optimal multi-agent pathfinding', in Symposium on Combinatorial Search (SOCS), (2011).

[13]

Justyna Petke, Bridging Constraint Satisfaction and Boolean Satisfiability, Artificial Intelligence: Foundations, Theory, and Algorithms, Springer, 2015.

Digital Library

[14]

G. Röger and M. Helmert, 'Non-optimal multi-agent pathfinding is solved (since 1984).', in SOCS), (2012).

[15]

M. Ryan, 'Constraint-based multi-robot path planning', in ICRA, pp. 922-928, (2010).

[16]

G. Sharon, R. Stern, A. Felner, and N. Sturtevant, 'Conflict-based search for optimal multi-agent pathfinding', Artif. Intell., 219, 40-66, (2015).

Digital Library

[17]

G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, 'Conflict-based search for optimal multi-agent pathfinding', Artif. Intell., 219, 40-66, (2015).

Digital Library

[18]

G. Sharon, R. Stern, M. Goldenberg, and A. Felner, 'The increasing cost tree search for optimal multi-agent pathfinding', Artificial Intelligence, 195, 470-495, (2013).

Digital Library

[19]

J. Silva and I. Lynce, 'Towards robust CNF encodings of cardinality constraints', in CP, pp. 483-497, (2007).

Digital Library

[20]

D. Silver, 'Cooperative pathfinding', in AIIDE, pp. 117-122, (2005).

Digital Library

[21]

C. Sinz, 'Towards an optimal CNF encoding of boolean cardinality constraints', in CP, pp. 827-831, (2005).

Digital Library

[22]

A. Srinivasan, T. Ham, S. Malik, and R. Brayton, 'Algorithms for discrete function manipulation', in (ICCAD, pp. 92-95, (1990).

[23]

T. Standley, 'Finding optimal solutions to cooperative pathfinding problems.', in AAAI, pp. 173-178, (2010).

Digital Library

[24]

Nathan R. Sturtevant, 'Benchmarks for grid-based pathfinding', Computational Intelligence and AI in Games, 4(2), 144-148, (2012).

[25]

P. Surynek, 'An optimization variant of multi-robot path planning is intractable', in AAAI, (2010).

Digital Library

[26]

P. Surynek, 'Towards optimal cooperative path planning in hard setups through satisfiability solving', in PRICAI, 564-576, (2012).

Digital Library

[27]

P. Surynek, 'Compact representations of cooperative path-finding as SAT based on matchings in bipartite graphs', in ICTAI, pp. 875-882, (2014).

Digital Library

[28]

P. Surynek, 'A simple approach to solving cooperative path-finding as propositional satisfiability works well', in PRICAI, pp. 827-833, (2014).

[29]

P. Surynek, 'Simple direct propositional encoding of cooperative path finding simplified yet more', in MICAI, pp. 410-425, (2014).

[30]

P. Surynek, 'Reduced time-expansion graphs and goal decomposition for solving cooperative path finding sub-optimally', in IJCAI, pp. 1916-1922, (2015).

Digital Library

[31]

G. Wagner and H. Choset, 'Subdimensional expansion for multirobot path planning', Artif. Intell., 219, 1-24, (2015).

Digital Library

[32]

K. Wang and A. Botea, 'MAPP: a scalable multi-agent path planning algorithm with tractability and completeness guarantees', JAIR), 42, 55-90, (2011).

Digital Library

[33]

J. Yu and S. LaValle, 'Planning optimal paths for multiple robots on graphs', in ICRA, pp. 3612-3617, (2013).

[34]

J. Yu and S. M. LaValle, 'Structure and intractability of optimal multi-robot path planning on graphs', in AAAI, (2013).

Digital Library

Cited By

Tang HBerto FMa ZHua CAhn KPark JDastani MSichman JAlechina NDignum V(2024)HiMAP: Learning Heuristics-Informed Policies for Large-Scale Multi-Agent PathfindingProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663206(2498-2500)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663206
Albert EGarcia de la Banda MHernández-Cerezo AIgnatiev ARubio AStuckey P(2024)SuperStack: Superoptimization of Stack-Bytecode via Greedy, Constraint-Based, and SAT TechniquesProceedings of the ACM on Programming Languages10.1145/36564358:PLDI(1437-1462)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656435
Crombez Lda Fonseca GGerard YGonzalez-Lorenzo ALafourcade PLibralesso L(2022)Shadoks Approach to Low-Makespan Coordinated Motion PlanningACM Journal of Experimental Algorithmics10.1145/352413327(1-17)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.1145/3524133
Show More Cited By

Recommendations

Boolean Satisfiability Approach to Optimal Multi-agent Path Finding under the Sum of Costs Objective: (Extended Abstract)
AAMAS '16: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems

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 ...
Migrating Techniques from Search-based Multi-Agent Path Finding Solvers to SAT-based Approach
In the multi-agent path finding 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, aiming to minimize a given objective function. Many MAPF solvers ...
Mutex Propagation for SAT-based Multi-agent Path Finding
PRIMA 2020: Principles and Practice of Multi-Agent Systems
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ECAI'16: Proceedings of the Twenty-second European Conference on Artificial Intelligence

August 2016

1860 pages

ISBN:9781614996712

Editors:
Gal A. Kaminka
Bar Ilan University, Israel
,
Maria Fox
King's College London, United Kingdom
,
Paolo Bouquet
University of Trento & OKKAM srl, Italy
,
Eyke Hüllermeier
Paderborn University, Germany
,
Virginia Dignum
Delft University of Technology, The Netherlands

Sponsors

ETINN: Essence ITN Network
Vrije Universiteit Amsterdam: Vrije Universiteit Amsterdam, Netherlands
PricewaterhouseCoopers: PricewaterhouseCoopers
TANDFGROUP: Taylor & Francis Group

Publisher

IOS Press

Netherlands

Publication History

Published: 29 August 2016

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

8
Total Citations
View Citations
829
Total Downloads

Downloads (Last 12 months)233
Downloads (Last 6 weeks)35

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tang HBerto FMa ZHua CAhn KPark JDastani MSichman JAlechina NDignum V(2024)HiMAP: Learning Heuristics-Informed Policies for Large-Scale Multi-Agent PathfindingProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems10.5555/3635637.3663206(2498-2500)Online publication date: 6-May-2024
https://dl.acm.org/doi/10.5555/3635637.3663206
Albert EGarcia de la Banda MHernández-Cerezo AIgnatiev ARubio AStuckey P(2024)SuperStack: Superoptimization of Stack-Bytecode via Greedy, Constraint-Based, and SAT TechniquesProceedings of the ACM on Programming Languages10.1145/36564358:PLDI(1437-1462)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656435
Crombez Lda Fonseca GGerard YGonzalez-Lorenzo ALafourcade PLibralesso L(2022)Shadoks Approach to Low-Makespan Coordinated Motion PlanningACM Journal of Experimental Algorithmics10.1145/352413327(1-17)Online publication date: 27-Jul-2022
https://dl.acm.org/doi/10.1145/3524133
Shahar TShekhar SAtzmon DSaffidine AJuba BStern R(2021)Safe Multi-Agent Pathfinding with Time UncertaintyJournal of Artificial Intelligence Research10.1613/jair.1.1239770(923-954)Online publication date: 1-May-2021
https://dl.acm.org/doi/10.1613/jair.1.12397
Lam ELe Bodic PHarabor DStuckey P(2019)Branch-and-cut-and-price for multi-agent pathfindingProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367032.3367215(1289-1296)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367032.3367215
Surynek P(2019)Unifying search-based and compilation-based approaches to multi-agent path finding through satisfiability modulo theoriesProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367032.3367199(1177-1183)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367032.3367199
Li JFelner ABoyarski EMa HKoenig S(2019)Improved heuristics for multi-agent path finding with conflict-based searchProceedings of the 28th International Joint Conference on Artificial Intelligence10.5555/3367032.3367096(442-449)Online publication date: 10-Aug-2019
https://dl.acm.org/doi/10.5555/3367032.3367096
Botea ABonusi DSurynek P(2018)Solving multi-agent path finding on strongly biconnected digraphsJournal of Artificial Intelligence Research10.1613/jair.1.1121262:1(273-314)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1613/jair.1.11212

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents