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
Identifying Unsolvable Instances, Forbidden States and Irrelevant Information in Planning
Linköping University, Department of Computer and Information Science. Linköping University, The Institute of Technology.
2012 (English)Independent thesis Advanced level (degree of Master (Two Years)), 20 credits / 30 HE creditsStudent thesis
Abstract [en]

Planning is a central research area in artificial intelligence, and a lot of effort has gone into constructing more and more efficient planning algorithms. In real-world examples, many problem instances do not have a solution. Hence, there is an obvious need for methods that are capable of identifying unsolvable instances efficiently. It is not possible to efficiently identify all unsolvable instances due to the inherent high complexity of planning, but many unsolvable instances can be identified in polynomial time. We present a number of novel methods for doing this.

We adapt the notion of k-consistency (a well-studied concept from constraint satisfaction) for testing unsolvability of planning instances. The idea is to decompose a given problem instance into a number of smaller instances which can be solved in polynomial time. If any of the smaller instances are unsolvable, then the original instance is unsolvable. If all the smaller instances are solvable, then it is possible to extract information which can be used to guide the search. For instance, we introduce the notion of forbidden state patterns that are partial states that must be avoided by any solution to the problem instance. This can be viewed as the opposite of pattern databases which give information about states which can lead to a solution. 

We also introduce the notion of critical sets and show how to identify them. Critical sets describe operators or values which must be used or achieved in any solution. It is a variation on the landmark concept, i.e., operators or values which must be used in every solution. With the help of critical sets we can identify superfluous operators and values. These operators and values can be removed by preprocessing the problem instance to decrease planning time.

Place, publisher, year, edition, pages
2012. , 47 p.
Keyword [en]
planning, automated planning, k-consistency, local consistency, forbidden states, landmarks, projection, variable projection, critical sets, reduction
National Category
Computer Science
Identifiers
URN: urn:nbn:se:liu:diva-84846ISRN: LIU-IDA/LITH-EX-A--12/036--SEOAI: oai:DiVA.org:liu-84846DiVA: diva2:562466
Subject / course
Computer and information science at the Institute of Technology
Uppsok
Technology
Supervisors
Examiners
Available from: 2012-10-24 Created: 2012-10-24 Last updated: 2012-12-10Bibliographically approved

Open Access in DiVA

fulltext(587 kB)104 downloads
File information
File name FULLTEXT01.pdfFile size 587 kBChecksum SHA-512
52c8d578f6f2be4ef3d14288dd07f623da501ca16a39206059daf28630b71e9beaf169d2947df6e25d48dfec325c116ecfc3dc88f768378d61751747098784e9
Type fulltextMimetype application/pdf

By organisation
Department of Computer and Information ScienceThe Institute of Technology
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 104 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 252 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