On the complexity of planning for agent teams and its implications for single agent planning

DOI10.1016/j.artint.2012.08.005zbMath1284.68564MaRDI QIDQ2446582

Ronen I. Brafman, Carmel Domshlak

Publication date: 17 April 2014

Published in: Artificial Intelligence (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.artint.2012.08.005

zbMATH Keywords

complexity; tree-width; classical planning; multi-agent planning

Mathematics Subject Classification ID

68T42: Agent technology and artificial intelligence

Related Items

Equilibria for games with combined qualitative and quantitative objectives, Algorithms for electric vehicle scheduling in large-scale mobility-on-demand schemes, Star-topology decoupled state space search, Backdoors to planning, From model checking to equilibrium checking: reactive modules for rational verification

Uses Software

• Graphplan

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. III. Planar tree-width
• Complexity results for standard benchmark domains in planning
• Concise finite-domain representations for PDDL planning tasks
• Approximation algorithms for treewidth
• S-functions for graphs
• Graph searching and a min-max theorem for tree-width
• Automatically generating abstractions for planning
• The computational complexity of propositional STRIPS planning
• Fast planning through planning graph analysis
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Planning in a hierarchy of abstraction spaces
• Branching and pruning: An optimal temporal POCL planner based on constraint programming
• STRIPS: A new approach to the application of theorem proving to problem solving
• Implicit Abstraction Heuristics
• Modeling and Reasoning with Bayesian Networks
• Complexity of Finding Embeddings in a k-Tree
• Planning as constraint satisfaction: Solving the planning graph by compiling it into CSP