Change search
ReferencesLink to record
Permanent link

Direct link
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
URN: urn:nbn:se:liu:diva-84846ISRN: LIU-IDA/LITH-EX-A--12/036--SEOAI: diva2:562466
Subject / course
Computer and information science at the Institute of Technology
Available from: 2012-10-24 Created: 2012-10-24 Last updated: 2012-12-10Bibliographically approved

Open Access in DiVA

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

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

Search outside of DiVA

GoogleGoogle Scholar
Total: 78 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

Total: 194 hits
ReferencesLink to record
Permanent link

Direct link