| 1. |
- Bäckström, Christer, et al.
(författare)
-
A complete parameterized complexity analysis of bounded planning
- 2015
-
Ingår i: Journal of computer and system sciences (Print). - : Elsevier. - 0022-0000 .- 1090-2724. ; 81:7, s. 1311-1332
-
Tidskriftsartikel (refereegranskat)abstract
- The propositional planning problem is a notoriously difficult computational problem, which remains hard even under strong syntactical and structural restrictions. Given its difficulty it becomes natural to study planning in the context of parameterized complexity. In this paper we continue the work initiated by Downey, Fellows and Stege on the parameterized complexity of planning with respect to the parameter "length of the solution plan." We provide a complete classification of the parameterized complexity of the planning problem under two of the most prominent syntactical restrictions, i.e., the so called PUBS restrictions introduced by Backstrom and Nebel and restrictions on the number of preconditions and effects as introduced by Bylander. We also determine which of the considered fixed-parameter tractable problems admit a polynomial kernel and which do not. (C) 2015 Elsevier Inc. All rights reserved.
|
|
| 2. |
- Bäckström, Christer, 1962-, et al.
(författare)
-
A Refined Understanding of Cost-optimal Planning with Polytree Causal Graphs
- 2018
-
Ingår i: 11th Annual Symposium on Combinatorial Search. - : AAAI Press. - 9781577358022 ; , s. 19-27
-
Konferensbidrag (refereegranskat)abstract
- Complexity analysis based on the causal graphs of planning instances has emerged as a highly important area of research. In particular, tractability results have led to new methods for the identification of domain-independent heuristics. Important early examples of such tractability results have been presented by, for instance, Brafman & Domshlak and Katz & Keyder. More general results based on polytrees and bounding certain parameters were subsequently derived by Aghighi et al. and Ståhlberg. We continue this line of research by analyzing cost-optimal planning restricted to instances with a polytree causal graph, bounded domain size and bounded depth (i.e. the length of the longest directed path in the causal graph). We show that no further restrictions are necessary for tractability, thus generalizing the previous results. Our approach is based on a novel method of closely analysing optimal plans: we recursively decompose the causal graph in a way that allows for bounding the number of variable changes as a function of the depth, using a reording argument and a comparison with prefix trees of known size. We can then transform the planning instances into constraint satisfaction instances; an idea that has previously been exploited by, for example, Brafman & Domshlak and Bäckström. This allows us to utilise efficient algorithms for constraint optimisation over tree-structured instances.
|
|
| 3. |
- Bäckström, Christer, et al.
(författare)
-
Cost-Optimal Planning, Delete Relaxation, Approximability, and Heuristics
- 2021
-
Ingår i: The journal of artificial intelligence research. - : AI ACCESS FOUNDATION. - 1076-9757 .- 1943-5037. ; 70, s. 169-204
-
Tidskriftsartikel (refereegranskat)abstract
- Cost-optimal planning is a very well-studied topic within planning, and it has proven to be computationally hard both in theory and in practice. Since cost-optimal planning is an optimisation problem, it is natural to analyse it through the lens of approximation. An important reason for studying cost-optimal planning is heuristic search; heuristic functions that guide the search in planning can often be viewed as algorithms solving or approximating certain optimisation problems. Many heuristic functions (such as the ubiquitious h(+) heuristic) are based on delete relaxation, which ignores negative effects of actions. Planning for instances where the actions have no negative effects is often referred to as monotone planning. The aim of this article is to analyse the approximability of cost-optimal monotone planning, and thus the performance of relevant heuristic functions. Our findings imply that it may be beneficial to study these kind of problems within the framework of parameterised complexity and we initiate work in this direction.
|
|
| 4. |
- Bäckström, Christer, 1962-, et al.
(författare)
-
Novel Structural Parameters for Acyclic Planning Using Tree Embeddings
- 2018
-
Ingår i: 27th International Joint Conference on Artificial Intelligence. - California : International Joint Conferences on Artificial Intelligence Organization. - 9780999241127 ; , s. 4653-4659
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 5. |
- Bäckström, Christer, et al.
(författare)
-
Parameterized Complexity and Kernel Bounds for Hard Planning Problems
- 2013
-
Ingår i: Algorithms and Complexity. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783642382321 - 9783642382338 ; , s. 13-24
-
Konferensbidrag (refereegranskat)abstract
- The propositional planning problem is a notoriously difficult computational problem. Downey et al. (1999) initiated the parameterized analysis of planning (with plan length as the parameter) and Bäckström et al. (2012) picked up this line of research and provided an extensive parameterized analysis under various restrictions, leaving open only one stubborn case. We continue this work and provide a full classification. In particular, we show that the case when actions have no preconditions and at most e postconditions is fixed-parameter tractable if e ≤ 2 and W[1]-complete otherwise. We show fixed-parameter tractability by a reduction to a variant of the Steiner Tree problem; this problem has been shown fixed-parameter tractable by Guo et al. (2007). If a problem is fixed-parameter tractable, then it admits a polynomial-time self-reduction to instances whose input size is bounded by a function of the parameter, called the kernel. For some problems, this function is even polynomial which has desirable computational implications. Recent research in parameterized complexity has focused on classifying fixed-parameter tractable problems on whether they admit polynomial kernels or not. We revisit all the previously obtained restrictions of planning that are fixed-parameter tractable and show that none of them admits a polynomial kernel unless the polynomial hierarchy collapses to its third level.
|
|
| 6. |
- Bäckström, Christer, et al.
(författare)
-
The Complexity of Planning Revisited - A Parameterized Analysis
- 2012
-
Ingår i: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. - : AAAI Press. - 9781577355687 - 9781577355694 ; , s. 1735-1741
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 7. |
- Bäckström, Sebastian, et al.
(författare)
-
Biogas till tunga fordon drivna av flytande metan – Erfarenheter från lastbilar i trafik : Systemstudier inom projektet Västsvensk arena för flytande biogas
- 2022
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Syftet med studien är att undersöka om lastbilar drivna med förvätskad biometan, LBM (eng. Liquid Bio Methane), i Sverige ofta benämnt LBG, kan användas på samma sätt som lastbilar med konventionell dieselmotor samt vilken klimatnytta som uppstår vid drift av förvätskad metan jämfört med dieselbränslen, fossila såväl som förnybara.Studien har besvarat frågan genom att jämföra driftsdata för ett kalenderår för sammanlagt 10 LBG-lastbilar och 6 diesellastbilar från 3 olika Åkerier. Genom att jämföra detaljerade data loggad i fordonens interna datasystem undersöks skillnader och likheter i hur de olika fordonstyperna presterar.Analysen visade på en likvärdig energianvändning och -330% lägre utsläpp av klimatpåverkande gaser för LBG-fordon tankade med förvätskad biometan (LBG) jämfört med dieselfordon tankade med rent biobränsle (HVO 100). Detta betyder att LBG fordonen när de är tankade med förvätskad biometan, där bränslet producerats med hög andel flytgödsel, redovisar negativa utsläpp av klimatpåverkande gaser, dvs. fordonen gör klimatnytta genom att förbränna metangas.Studiens slutsats är bland annat att det är möjligt för ett åkeri att ersätta dagens dieselfordon med LBG-fordon i fjärrtrafik med likvärdig energianvändning och betydande reduktioner av klimatpåverkande utsläpp.
|
|
| 8. |
- Bäckström, Sebastian, et al.
(författare)
-
Klimatsmarta lägen - Beräkning av minskade utsläpp av växthusgaser genom förtätning av stationsnära lägen
- 2013
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- ”Hur skiljer sig koldioxidutsläppen åt för resor till och från verksamheter som ligger i byggnader nära respektive långt ifrån spårbunden kollektivtrafik och reseknutpunkter?” Svaret på denna fråga är viktig när för- och nackdelar med en förtätning av stationsnära delar av städer bedöms. Att närhet till en järnvägsstation med högfrekvent lokal och regional tågtrafik skapar goda förutsättningar för ett resmönster med minskat inslag av bilåkande är uppenbart. Att tillgången till annan kollektivtrafik vid stationen ytterligare stimulerar val av kollektiva färdmedel förvånar ingen. Att det tillsammans i sin tur leder till fördelar för miljön i form av minskade utsläpp av klimatpåverkande och luftförorenade avgaser är också självklart. Men hur stora är de kvantitativa vinsterna mätt som minskade utsläpp om man bygger vid en knutpunkt för kollektiva transportslag jämfört med lägen sämre försörjda med kollektivtrafik? Och hur påverkar olika verksamheter i byggnaden resmönstret i den geografiska jämförelsen? Detta försöker vi klarlägga genom att utveckla ett kalkylverktyg med vilket det totala antalet resor till och från varje typ av verksamhet i en byggnad beräknas. Därefter inhämtar vi uppgifter om brukarnas olika resmönster, som används för att beräkna det totala transportarbetet, mätt som person-kilometer kopplat till byggnaden. Till sist kombineras dessa uppgifter med de olika trafikslagens utsläpp av koldioxid för att få fram en total siffra för byggnadens reserelaterade emissioner. Genom att ange möjliga alternativa lägen för de ingående verksamheterna i den analyserade byggnaden räknas den potentiella minskningen i koldioxidemissioner ut om etablering sker i det valda, stationsnära läget. Underlagsdata till kalkylverktyget planerades ursprungligen att hämtas från litteraturen och från annan forskning. Inga användbara data fanns dock tillgängliga vad gäller personers resmönster (det vill säga reslängd och val av färdmedel) nedbrutet på målpunkter, varför ett datainsamlingsprojekt initierades. Därför användes webbenkäter, frågeformulär till besökare, som direkta intervjuer i butik för att kunna beskriva hur resmönstret skiljer sig åt till för exempelvis en kund till detaljhandel på Stockholms Centralstation, Södermalm (innerstadsmiljö) och Nacka Forum (extern storhandel). I det typfall som vi har undersökt beräknas utsläppen för en möjlig etablering av en byggnad i Västra city i Stockholm, i direkt anslutning till Centralstationen. Byggnaden är tänkt att innehålla såväl trafikantutrymmen som handel, kontor, service och bostäder. Som jämförelse har vi beräknat resornas emissioner om motsvarande byggnadsytor etableras på alternativa adresser med sämre tillgång till effektiva kollektiva transportsystem. Kalkylen visar på tre till fem gånger högre reserelaterade emissioner i ett externt läge jämfört med det stationsnära i Västra city. Vi ger ett intervall därför att det speglar effekten av om vi antar att besöksfrekvensen till verksamheter med olika geografisk lokalisering är lika (högre siffran) eller olika (lägre siffran). Rent diskussionsmässigt tror vi att sanningen ligger mer åt den högre siffran som en följd av att verksamheter centralt belägna i staden tenderar att använda sig av mindre yta per verksamhet vilket balanserar en skillnad i besöksfrekvens. Kort sagt, det är förmodligen mer riktigt att jämföra en mindre byggnad i den centrala staden med en större i ett mer externt läge, givet att de både innehåller kvantitativt lika mängd verksamheter som utgör målpunkter för ett resande. En etablering av nya kontorsplatser i ett centralt, stationsnära läge indikerar också att 10 procent av de nyanställda kommer att pendla regionalt med tåg. I det externa läget verkar den regionala pendlingen uteslutande ske med bil. Skillnaden i utsläpp från det tillkommande regionala pendlandet är 78 procent till det centrala lägets fördel.
|
|
| 9. |
- Bäckström, Sebastian, et al.
(författare)
-
Low carbon marine freight
- 2018
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- We have studied the possibility to introduce biobased fuels as marine fuels. A business model in which low carbon marine freight is offered to shippers is analysed. The model is in many ways similar to existing schemes in the energy sector (“green electricity”, biogas and district heating). A fundamental principle of the model is that the cost increase in transportation when biobased fuels are used can be transferred to the end consumer. Technical aspects, fuel supply issues, economic implications, and freight market aspects are all considered from a perspective of using liquid biobased fuel on ships. We find that both HVO and FAME/RME are suitable options to blend in fossil marine fuelsIn a continuation of this work, a project with real life tests is aimed for. In a workshop we therefore gathered stakeholders that have key roles in the proposed business model. A number of shippers that joined the workshop showed an interest in trying this model in cooperation with ship owners that provide their transports.
|
|
| 10. |
|
|
