liu.seSearch for publications in DiVA
Endre søk
Link to record
Permanent link

Direct link
BETA
Ståhlberg, Simon
Publikasjoner (3 av 3) Visa alla publikasjoner
Ståhlberg, S. (2017). Methods for Detecting Unsolvable Planning Instances using Variable Projection. (Doctoral dissertation). Linköping: Linköping University Electronic Press
Åpne denne publikasjonen i ny fane eller vindu >>Methods for Detecting Unsolvable Planning Instances using Variable Projection
2017 (engelsk)Doktoravhandling, monografi (Annet vitenskapelig)
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.

sted, utgiver, år, opplag, sider
Linköping: Linköping University Electronic Press, 2017. s. 147
Serie
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1863
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-139802 (URN)10.3384/diss.diva-139802 (DOI)9789176854983 (ISBN)
Disputas
2017-10-03, Ada Lovelace, hus B, Campus Valla, Linköping, 13:15 (engelsk)
Opponent
Veileder
Forskningsfinansiär
CUGS (National Graduate School in Computer Science)
Tilgjengelig fra: 2017-09-11 Laget: 2017-09-08 Sist oppdatert: 2019-10-12bibliografisk kontrollert
Aghighi, M., Jonsson, P. & Ståhlberg, S. (2015). Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs. In: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence: . Paper presented at 29th AAAI Conference on Artificial Intelligence (AAAI-15), January 25–30, Austin, TX, USA. AAAI Press
Åpne denne publikasjonen i ny fane eller vindu >>Tractable Cost-Optimal Planning over Restricted Polytree Causal Graphs
2015 (engelsk)Inngår i: Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, AAAI Press, 2015Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Causal graphs are widely used to analyze the complexity of planning problems. Many tractable classes have been identified with their aid and state-of-the-art heuristics have been derived by exploiting such classes. In particular, Katz and Keyder have studied causal graphs that are hourglasses (which is a generalization of forks and inverted-forks) and shown that the corresponding cost-optimal planning problem is tractable under certain restrictions. We continue this work by studying polytrees (which is a generalization of hourglasses) under similar restrictions. We prove tractability of cost-optimal planning by providing an algorithm based on a novel notion of variable isomorphism. Our algorithm also sheds light on the k-consistency procedure for identifying unsolvable planning instances. We speculate that this may, at least partially, explain why merge-and-shrink heuristics have been successful for recognizing unsolvable instances.

sted, utgiver, år, opplag, sider
AAAI Press, 2015
Serie
Proceedings of the AAAI Conference on Artificial Intelligence, ISSN 2159-5399, E-ISSN 2374-3468
Emneord
automated planning, causal graph, polynomial-time algorithm, cost-optimal planning, polytree
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-118729 (URN)978-1-57735-703-2 (ISBN)
Konferanse
29th AAAI Conference on Artificial Intelligence (AAAI-15), January 25–30, Austin, TX, USA
Forskningsfinansiär
CUGS (National Graduate School in Computer Science)
Tilgjengelig fra: 2015-06-03 Laget: 2015-06-03 Sist oppdatert: 2017-05-17
Bäckström, C., Jonsson, P. & Ståhlberg, S. (2013). Fast Detection of Unsolvable Planning Instances Using Local Consistency. In: Proceedings of the Sixth International Symposium on Combinatorial Search: . Paper presented at 6th Annual Symposium on Combinatorial Search (SoCS-2013), 11-13 July 2013, Leavenworth, WA, USA (pp. 29-37). AAAI Press
Åpne denne publikasjonen i ny fane eller vindu >>Fast Detection of Unsolvable Planning Instances Using Local Consistency
2013 (engelsk)Inngår i: Proceedings of the Sixth International Symposium on Combinatorial Search, AAAI Press, 2013, s. 29-37Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

There has been a tremendous advance in domain-independent planning over the past decades, and planners have become increasingly efficient at finding plans. However, this has not been paired by any corresponding improvement in detecting unsolvable instances. Such instances are obviously important but largely neglected in planning. In other areas, such as constraint solving and model checking, much effort has been spent on devising methods for detecting unsolvability. We introduce a method for detecting unsolvable planning instances that is loosely based on consistency checking in constraint programming. Our method balances completeness against efficiency through a parameter k: the algorithm identifies more unsolvable instances but takes more time for increasing values of k. We present empirical data for our algorithm and some standard planners on a number of unsolvable instances, demonstrating that our method can be very efficient where the planners fail to detect unsolvability within reasonable resource bounds. We observe that planners based on the h^m heuristic or pattern databases are better than other planners for detecting unsolvability. This is not a coincidence since there are similarities (but also significant differences) between our algorithm and these two heuristic methods.

sted, utgiver, år, opplag, sider
AAAI Press, 2013
HSV kategori
Identifikatorer
urn:nbn:se:liu:diva-102667 (URN)978-1-57735-632-5 (ISBN)
Konferanse
6th Annual Symposium on Combinatorial Search (SoCS-2013), 11-13 July 2013, Leavenworth, WA, USA
Tilgjengelig fra: 2013-12-18 Laget: 2013-12-18 Sist oppdatert: 2018-01-11bibliografisk kontrollert
Organisasjoner