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

DOI10.1007/S10472-017-9560-ZMaRDI QIDQ1688718zbMATH OpenOpenAlexWikidataFDO

Authors 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

conflict-based searchcooperative path-finding (CPF)increasing cost tree searchmakespan-optimalitymulti-agent pathfindingmulti-robot path planningoperator 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)

Recommendations

• On the complexity of optimal parallel cooperative path-finding
• SOLVING ABSTRACT COOPERATIVE PATH-FINDING IN DENSELY POPULATED ENVIRONMENTS
• Migrating techniques from search-based multi-agent path finding solvers to SAT-based approach
• Conflict-based search for optimal multi-agent pathfinding
• Multi-agent Path Finding Modulo Theory with Continuous Movements and the Sum of Costs Objective

Cites work

• Boosting search with variable elimination in constraint optimization and constraint satisfaction problems
• Bridging constraint satisfaction and Boolean satisfiability
• Compiling finite linear CSP into SAT
• Conflict-based search for optimal multi-agent pathfinding
• Efficient CNF encoding of Boolean cardinality constraints
• Exploiting subgraph structure in multi-robot path planning
• Graph puzzles, homotopy, and the alternating group
• scientific article; zbMATH DE number 2080324 (Why is no real title available?)
• scientific article; zbMATH DE number 5493266 (Why is no real title available?)
• scientific article; zbMATH DE number 3313427 (Why is no real title available?)
• Iterative and core-guided maxsat solving: a survey and assessment
• MIP: Theory and practice -- closing the gap
• Network flows. Theory, algorithms, and applications.
• On the complexity of optimal parallel cooperative path-finding
• Planning and control for cooperative manipulation and transportation with aerial robots
• Planning as satisfiability: parallel plans and algorithms for plan search
• Principles and Practice of Constraint Programming – CP 2004
• Push and rotate: a complete multi-agent pathfinding algorithm
• Representative encodings to translate finite CSPs into SAT
• SAT race 2015
• SOLVING ABSTRACT COOPERATIVE PATH-FINDING IN DENSELY POPULATED ENVIRONMENTS
• Subdimensional expansion for multirobot path planning
• The increasing cost tree search for optimal multi-agent pathfinding
• Towards Robust CNF Encodings of Cardinality Constraints

Cited in

(6)

• Multi-agent path finding with mutex propagation
• Multi-agent pathfinding with continuous time
• Multi-Agent Path Finding: A New Boolean Encoding
• Migrating techniques from search-based multi-agent path finding solvers to SAT-based approach
• Optimizing pathfinding for goal legibility and recognition in cooperative partially observable environments
• CBS-budget (CBSB): a complete and bounded suboptimal search for multi-agent path finding

Describes a project that uses

Uses Software

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1688718)