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

DOI10.1016/J.ARTINT.2012.08.005MaRDI QIDQ2446582zbMATH OpenOpenAlexFDO

Authors Ronen 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

classical planningcomplexitymulti-agent planningtree-width

Mathematics Subject Classification ID

Agent technology and artificial intelligence (68T42)

Recommendations

• A single-agent approach to multiagent planning
• The influence of k-dependence on the complexity of planning
• The complexity of planning problems with simple causal graphs
• Extending SATPLAN to multiple agents
• scientific article; zbMATH DE number 1929179

Cites work

• Abstract reasoning for planning and coordination
• Approximation algorithms for treewidth
• Automatically generating abstractions for planning
• Branching and pruning: An optimal temporal POCL planner based on constraint programming
• Complexity of Finding Embeddings in a k-Tree
• Complexity results for standard benchmark domains in planning
• Concise finite-domain representations for PDDL planning tasks
• Fast planning through planning graph analysis
• Fixed-parameter complexity in AI and nonmonotonic reasoning
• Graph minors. III. Planar tree-width
• Graph searching and a min-max theorem for tree-width
• scientific article; zbMATH DE number 1573293 (Why is no real title available?)
• scientific article; zbMATH DE number 1946870 (Why is no real title available?)
• Implicit abstraction heuristics
• Modeling and Reasoning with Bayesian Networks
• New islands of tractability of cost-optimal planning
• Partial-order planning with concurrent interacting actions
• Planning as constraint satisfaction: Solving the planning graph by compiling it into CSP
• Planning in a hierarchy of abstraction spaces
• S-functions for graphs
• STRIPS: A new approach to the application of theorem proving to problem solving
• The complexity of planning problems with simple causal graphs
• The computational complexity of propositional STRIPS planning
• The fast downward planning system

Cited in

(7)

• 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
• A single-agent approach to multiagent planning
• Safe learning of multi-agent action models from concurrent joint action observations
• Equilibria for games with combined qualitative and quantitative objectives

Describes a project that uses

Uses Software

• Graphplan

This page was built for publication: On the complexity of planning for agent teams and its implications for single agent planning

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