Planning over Chain Causal Graphs for Variables with Domains of Size 5 Is NP-Hard.
Omer GiménezAnders JonssonPublished in: CoRR (2014)
Keyphrases
- causal graph
- np hardness
- np hard
- planning problems
- causal models
- state variables
- strips planning
- computational complexity
- special case
- scheduling problem
- ai planning
- approximation algorithms
- branch and bound algorithm
- decision problems
- np complete
- worst case
- integer programming
- domain independent
- lower bound
- optimal solution
- dynamic systems
- directed acyclic graph
- structural model
- classical planning
- state space
- plan existence