liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
When Acyclicity is not Enough: Limitations of the Causal Graph
Universitat Pompeu Fabra, Barcelona, Spain.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, The Institute of Technology.
2013 (English)In: Proceedings of the Twenty-Third International Conference on Automated Planning and Scheduling, AAAI Press, 2013, 117-125 p.Conference paper, Published paper (Refereed)
Abstract [en]

Causal graphs are widely used in planning to capture the internal  structure of planning instances. In the past, causal graphs have been exploited to generate hierarchical plans, to compute heuristics, and  to identify classes of planning instances that are easy to solve. It  is generally believed that planning is easier when the causal graph is acyclic. In this paper we show that this is not true in the worst  case, proving that the problem of plan existence is PSPACE-complete  even when the causal graph is acyclic. Since the variables of the  planning instances in our reduction are propositional, this result  applies to STRIPS planning with negative pre-conditions. Having  established that planning is hard for acyclic causal graphs, we study  a subclass of planning instances with acyclic causal graphs whose  variables have strongly connected domain transition graphs. For this  class, we show that plan existence is easy, but that bounded plan  existence is hard, implying that optimal planning is significantly  harder than satisficing planning for this class.

Place, publisher, year, edition, pages
AAAI Press, 2013. 117-125 p.
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-102660ISBN: 978-1-57735-609-7 (print)OAI: oai:DiVA.org:liu-102660DiVA: diva2:680720
Conference
23rd International Conference on Automated Planning and Scheduling (ICAPS-2013), 10-14 June 2013, Rome, Italy
Available from: 2013-12-18 Created: 2013-12-18 Last updated: 2017-02-23Bibliographically approved

Open Access in DiVA

No full text

Other links

Link to paper

Authority records BETA

Jonsson, PeterLööw, Tomas

Search in DiVA

By author/editor
Jonsson, PeterLööw, Tomas
By organisation
Software and SystemsThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 42 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf