A Closer Look at Causal Links: Complexity Results for Delete-Relaxation in Partial Order Causal Link (POCL) Planning
| POP POCL planning plan-based search plan existence problem complexity results |
PaperID: 37
pdf
poster
|
| Partial Order Causal Link (POCL) planning follows the principle of least commitment in that it maintains only a partial order on its actions to prevent unnecessary early commitment during search. This can reduce the search space significantly by systematically representing up to an exponential number of action sequences in just a single search node. Progress on goal achievement is represented fully by this partial order and by causal links, which represent the causal relationships between these actions as well as between the initial state and goal. Plan existence for a state in classical planning thus corresponds to plan existence for a partial plan in POCL planning. Yet almost no theoretical investigations for POCL plan existence were conducted so far. While delete-relaxation makes plan existence tractable in classical planning, we show it to be NP-hard in POCL planning unless the current plan is totally ordered or causal links are almost completely ignored. | |
Session 22: Representation | Partial Order Planning | Multi-Agent Planning
A Closer Look at Causal Links: Complexity Results for Delete-Relaxation in Partial Order Causal Link (POCL) Planning
Authors: Pascal Bercher
Keywords:
POPPOCL planningplan-based searchplan existence problemcomplexity results
Decentralized Refinement Planning and Acting
Authors: Ruoxi Li, Sunandita Patra and Dana Nau
Keywords:
Multi-agent systemsDecentralized cooperative agentsHierarchical task refinementIntegrating acting and planningOperational modelsOnline planning
Automated design of fMRI paradigms
Authors: Katherine Esper and Felipe Meneguzzi
Keywords:
PDDL+Neuroscience DomainsNovel Planning Domains
Landmark-based approaches for goal recognition as planning
Authors: Ramon Fraga Pereira, Nir Oren and Felipe Meneguzzi