Time-expanded graph-based propositional encodings for makespan-optimal solving of cooperative path finding problems

DOI10.1007/s10472-017-9560-zzbMath1423.68474OpenAlexW2739829010WikidataQ58682808 ScholiaQ58682808MaRDI QIDQ1688718

Pavel Surynek

Publication date: 11 January 2018

Published in: Annals of Mathematics and Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10472-017-9560-z

zbMATH Keywords

multi-robot path planningconflict-based searchcooperative path-finding (CPF)increasing cost tree searchmakespan-optimalitymulti-agent pathfindingoperator decomposition/independence detectionpebble motion on graphspropositional satisfiability (SAT)time-expanded graphs

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Agent technology and artificial intelligence (68T42)

Related Items (2)

Multi-agent pathfinding with continuous time ⋮ Multi-agent path finding with mutex propagation

Uses Software

• Boolector
• Gurobi
• Walksat
• Gecode
• Graphplan
• Glucose
• Sugar
• Azucar

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• SAT race 2015
• The increasing cost tree search for optimal multi-agent pathfinding
• Compiling finite linear CSP into SAT
• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Graph puzzles, homotopy, and the alternating group
• Subdimensional expansion for multirobot path planning
• Conflict-based search for optimal multi-agent pathfinding
• Iterative and core-guided maxsat solving: a survey and assessment
• Planning as satisfiability: parallel plans and algorithms for plan search
• Bridging constraint satisfaction and Boolean satisfiability
• On the Complexity of Optimal Parallel Cooperative Path-Finding
• Planning and Control for Cooperative Manipulation and Transportation with Aerial Robots
• Push and Rotate: a Complete Multi-agent Pathfinding Algorithm
• SOLVING ABSTRACT COOPERATIVE PATH-FINDING IN DENSELY POPULATED ENVIRONMENTS
• Towards Robust CNF Encodings of Cardinality Constraints
• Representative Encodings to Translate Finite CSPs into SAT
• Principles and Practice of Constraint Programming – CP 2003
• Principles and Practice of Constraint Programming – CP 2004

This page was built for publication: Time-expanded graph-based propositional encodings for makespan-optimal solving of cooperative path finding problems