Change search

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• 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.

2012. , 47 p.
##### Keyword [en]
planning, automated planning, k-consistency, local consistency, forbidden states, landmarks, projection, variable projection, critical sets, reduction
##### National Category
Computer Sciences
##### Identifiers
ISRN: 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
Technology
##### Examiners
Available from: 2012-10-24 Created: 2012-10-24 Last updated: 2018-01-12Bibliographically approved

#### Open Access in DiVA

##### 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
##### On the subject
Computer Sciences

#### Search outside of DiVA

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: 256 hits

Cite
Citation style
• apa
• ieee
• modern-language-association-8th-edition
• vancouver
• 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
v. 2.29.1
|