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
Methods for Detecting Unsolvable Planning Instances using Variable Projection
Linköping University, Department of Computer and Information Science, Software and Systems. Linköping University, Faculty of Science & Engineering. (Theoretical Computer Science Laboratory)
2017 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

In this thesis we study automated planning, a branch of artificialintelligence, which deals with construction of plans. A plan is typically an action sequence that achieves some specific goal. In particular, we study unsolvable planning instances, i.e. there is no plan. Historically, this topic has been neglected by the planning community, and up to recently the International Planning Competition has only evaluated planners on solvable planning instances. For many applications we can know, e.g. by design, that there is a solution, but this cannot be a general assumption. One example is penetration testing in computer security, where a system inconsidered safe if there is no plan for intrusion. Other examples are resource bound planning instances that have insufficient resources to achieve the goal.

The main theme of this thesis is to use variable projection to prove unsolvability of planning instances. We implement and evaluate two planners: the first checks variable projections with the goal of finding an unsolvable projection, and the second builds a pattern collection to provide dead-end detection. In addition to comparing the planners to existing planners, we also utilise a large computer cluser to statistically assess whether they can be optimised further. On the benchmarks of planning instances that we used, it turns out that further improvement is likely to come from supplementary techniques rather than optimisation. We pursued this and enhanced variable projections with mutexes, which yielded a very competitive planner. We also inspect whether unsolvable variable projections tend to be composed of variables that play different roles, i.e. they are not 'similar'. We devise a variable similarity measure to rate how similar two variables are on a scale, and statistically analyse it. The measure can differentiate between unsolvable and solvable planning instances quite well, and is integrated into our planners. We also define a binary version of the measure, namely, that two variables are isomorphic if they behave exactly the same in some optimal solution (extremely similar). With the help of isomorphic variables we identified a computationally tractable class of planning instances that meet certain restrictions. There are several special cases of this class that are of practical interest, and this result encompass them.

Place, publisher, year, edition, pages
Linköping: Linköping University Electronic Press, 2017. , p. 147
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1863
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:liu:diva-139802DOI: 10.3384/diss.diva-139802ISBN: 9789176854983 (print)OAI: oai:DiVA.org:liu-139802DiVA, id: diva2:1139680
Public defence
2017-10-03, Ada Lovelace, hus B, Campus Valla, Linköping, 13:15 (English)
Opponent
Supervisors
Funder
CUGS (National Graduate School in Computer Science)Available from: 2017-09-11 Created: 2017-09-08 Last updated: 2019-10-12Bibliographically approved

Open Access in DiVA

Methods for Detecting Unsolvable Planning Instances using Variable Projection(1577 kB)250 downloads
File information
File name FULLTEXT02.pdfFile size 1577 kBChecksum SHA-512
aa3e69f25fe04211607a5add01f5ba584359daa4c16a78084658f4528234d014f45ae986358c3c9f2e67d343fb6cf9b87bf427ddc12af9df10902c4ca84e793e
Type fulltextMimetype application/pdf
omslag(8698 kB)12 downloads
File information
File name COVER01.pdfFile size 8698 kBChecksum SHA-512
1df90962495efa90c8ad8c6d9c09684d3e4b527a11f5aa06c8a562dfc584f29b11ae59a9ef0036507618b4171556967113e4a55cfd9f33c69f1aa97950f215da
Type coverMimetype application/pdf
Order online >>

Other links

Publisher's full text

Authority records BETA

Ståhlberg, Simon

Search in DiVA

By author/editor
Ståhlberg, Simon
By organisation
Software and SystemsFaculty of Science & Engineering
Computer Sciences

Search outside of DiVA

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

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 922 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