extended-abstract

Boolean Satisfiability Approach to Optimal Multi-agent Path Finding under the Sum of Costs Objective: (Extended Abstract)

Authors:

Pavel Surynek,

Ariel Felner,

Roni Stern,

Eli BoyarskiAuthors Info & Claims

AAMAS '16: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems

Pages 1435 - 1436

Published: 09 May 2016 Publication History

Get Access

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.

References

[1]

B. de Wilde, A. W. ter Mors, and C. Witteveen. Push and rotate: cooperative multi-agent path planning. In AAMAS, pages 87--94, 2013.

Digital Library

Google Scholar

[2]

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

Google Scholar

[3]

M. Ryan. Constraint-based multi-robot path planning. In ICRA, pages 922--928, 2010.

Crossref

Google Scholar

[4]

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

Google Scholar

[5]

G. Sharon, R. Stern, M. Goldenberg, and A. Felner. The increasing cost tree search for optimal multi-agent pathfinding. Artif. Intell., 195:470--495, 2013.

Digital Library

Google Scholar

[6]

D. Silver. Cooperative pathfinding. In AIIDE, pages 117--122, 2005.

Digital Library

Google Scholar

[7]

C. Sinz. Towards an optimal CNF encoding of boolean cardinality constraints. In CP 2005, pages 827--831, 2005.

Digital Library

Google Scholar

[8]

T. S. Standley. Finding optimal solutions to cooperative pathfinding problems. In AAAI, 2010.

Digital Library

Google Scholar

[9]

P. Surynek. An optimization variant of multi-robot path planning is intractable. In AAAI, 2010.

Digital Library

Google Scholar

[10]

P. Surynek. Compact representations of cooperative path-finding as SAT based on matchings in bipartite graphs. In ICTAI, pages 875--882, 2014.

Digital Library

Google Scholar

[11]

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

Digital Library

Google Scholar

Index Terms

Boolean Satisfiability Approach to Optimal Multi-agent Path Finding under the Sum of Costs Objective: (Extended Abstract)

Recommendations

A satisfiability procedure for quantified boolean formulae
The renesse issue on satisfiability

We present a satisfiability tester QSAT for quantified Boolean formulae and a restriction QSAT_CNF of QSAT to unquantified conjunctive normal form formulae. QSAT makes use of procedures which replace subformulae of a formula by equivalent formulae. By a ...
Efficient SAT approach to multi-agent path finding under the sum of costs objective
ECAI'16: Proceedings of the Twenty-second European Conference on Artificial Intelligence

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 ...
Backjumping for quantified Boolean logic satisfiability

The implementation of effective reasoning tools for deciding the satisfiability of Quantified Boolean Formulas (QBFs) is an important research issue in Artificial Intelligence. Many decision procedures have been proposed in the last few years, most of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

AAMAS '16: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems

May 2016

1580 pages

ISBN:9781450342391

General Chairs:
Catholijn M. Jonker
TU Delft, Netherlands
,
Stacy Marsella
University of Southern California, USA
,
Program Chairs:
John Thangarajah
RMIT University. Australia
,
Karl Tuyls
University of Liverpool, UK

In-Cooperation

SIGAI: ACM Special Interest Group on Artificial Intelligence

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 09 May 2016

Check for updates

Author Tags

Qualifiers

Extended-abstract

Conference

AAMAS '16

Sponsor:

AAMAS '16: International Conference on Agents and Multiagent Systems

May 9 - 13, 2016

Singapore, Singapore

Acceptance Rates

AAMAS '16 Paper Acceptance Rate 137 of 550 submissions, 25%;

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

0
Total Citations
79
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 10 Dec 2024

Other Metrics

View Author Metrics

Citations

View Options

Login options

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

Index Terms

Recommendations

A satisfiability procedure for quantified boolean formulae

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

Backjumping for quantified Boolean logic satisfiability