Sökning: id:"swepub:oai:DiVA.org:liu-158234" >
Novel Structural Pa...
Novel Structural Parameters for Acyclic Planning Using Tree Embeddings
-
- Bäckström, Christer, 1962- (författare)
- Linköpings universitet,Institutionen för datavetenskap,TCSLAB
-
- Jonsson, Peter (författare)
- Linköpings universitet,Institutionen för datavetenskap,TCSLAB
-
- Ordyniak, Sebastian (författare)
- University of Sheffield
-
(creator_code:org_t)
- California : International Joint Conferences on Artificial Intelligence Organization, 2018
- 2018
- Engelska.
-
Ingår i: 27th International Joint Conference on Artificial Intelligence. - California : International Joint Conferences on Artificial Intelligence Organization. - 9780999241127 ; , s. 4653-4659
- Relaterad länk:
-
https://www.ijcai.or...
-
visa fler...
-
https://urn.kb.se/re...
-
https://doi.org/10.2...
-
visa färre...
Abstract
Ämnesord
Stäng
- We introduce two novel structural parameters for acyclic planning (planning restricted to instances with acyclic causal graphs): up-depth and down-depth. We show that cost-optimal acyclic planning restricted to instances with bounded domain size and bounded up- or down-depth can be solved in polynomial time. For example, many of the tractable subclasses based on polytrees are covered by our result. We analyze the parameterized complexity of planning with bounded up- and down-depth: in a certain sense, down-depth has better computational properties than up-depth. Finally, we show that computing up- and down-depth are fixed-parameter tractable problems, just as many other structural parameters that are used in computer science. We view our results as a natural step towards understanding the complexity of acyclic planning with bounded treewidth and other parameters.
Ä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