Sökning: onr:"swepub:oai:DiVA.org:liu-79507" >
The Complexity of P...
The Complexity of Planning Revisited - A Parameterized Analysis
-
- Bäckström, Christer (författare)
- Linköpings universitet,Programvara och system,Tekniska högskolan,TCSLAB
-
- Chen, Yue (författare)
- Vienna University of Technology, Austria
-
- Jonsson, Peter (författare)
- Linköpings universitet,Programvara och system,Tekniska högskolan,TCSLAB
-
visa fler...
-
- Ordyniak, Sebastian (författare)
- Vienna University of Technology, Austria
-
- Szeider, Stefan (författare)
- Vienna University of Technology, Austria
-
visa färre...
-
(creator_code:org_t)
- AAAI Press, 2012
- 2012
- Engelska.
-
Ingår i: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. - : AAAI Press. - 9781577355687 - 9781577355694 ; , s. 1735-1741
- Relaterad länk:
-
https://urn.kb.se/re...
Abstract
Ämnesord
Stäng
- The early classifications of the computational complexity of planning under various restrictions in STRIPS (Bylander) and SAS+ (B¨ackstr¨om and Nebel) have influenced following research in planning in many ways. We go back and reanalyse their subclasses, but this time using the more modern tool of parameterized complexity analysis. This provides new results that together with the old results give a more detailed picture of the complexity landscape. We demonstrate separation results not possible with standard complexity theory, which contributes to explaining why certain cases of planning haveseemed simpler in practice than theory has predicted. In particular, we show that certain restrictions of practical interest are tractable in the parameterized sense of the term, and that a simple heuristic is sufficient to make a well-known partialorder planner exploit this fact.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Publikations- och innehållstyp
- ref (ämneskategori)
- kon (ämneskategori)
Hitta via bibliotek
Till lärosätets databas