On the complexity of optimal parallel cooperative path-finding

DOI10.3233/FI-2015-1192MaRDI QIDQ2805441zbMATH OpenOpenAlexFDO

Authors Pavel Surynek

Publication date 11 May 2016

Published in Fundamenta Informaticae (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3233/fi-2015-1192

zbMATH Keywords

complexitymulti-agent systemNP-completenessparallelism15-puzzlecooperative path-finding (CPF)\((N^2 - 1)\)-puzzle\(N\times N\)-puzzledomain-dependent planningsliding puzzle

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Agent technology and artificial intelligence (68T42)

Recommendations

• Optimal parallel algorithms for path problems on planar graphs
• Parallelism and the maximal path problem
• Optimized versions of a distributed algorithm for solving path problems
• On efficient parallel computations of costs of paths on a grid graph
• scientific article; zbMATH DE number 966593
• A parallel algorithm for the maximal path problem
• Parallel complexity of computing a maximal set of disjoint paths
• Parallel search paths for the simplex algorithm

Cited in

(6)

• Optimal path selection approach for fuzzy reliable shortest path problem
• SOLVING ABSTRACT COOPERATIVE PATH-FINDING IN DENSELY POPULATED ENVIRONMENTS
• Cooperative pursuit with Voronoi partitions
• Time-expanded graph-based propositional encodings for makespan-optimal solving of cooperative path finding problems
• The computational complexity of multi-agent pathfinding on directed graphs
• Discovery Science

This page was built for publication: On the complexity of optimal parallel cooperative path-finding

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