| 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, 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.
|
|
| 4. |
- 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.
|
|
| 5. |
|
|
| 6. |
- Fridell, Erik, et al.
(författare)
-
Transport work and emissions in MRV : methods and potential use of data
- 2018
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- EU has decided on a system for Monitoring, Reporting and Verifying (MRV) emissions of carbon dioxide from ships in Europe starting 1st of January 2018. This means that ship-owners must develop systems for reporting and that a potential data source for assessing emissions and fuel consumption for ships will emerge. This report demonstrates the methods for preparing the data for reporting, looks at uncertainties and drawbacks and discusses the potential use of the data. Drawbacks identified with MRV, are that other green-house gases, such as methane, not are included, and that upstream emissions, from fuel production and fuel transportation, also are excluded. Further, the reporting procedures for biogenic CO2 are still unclear. However, when large amounts of data are made public in the summer of 2019 there will be an opportunity to improve benchmarking and emission calculations, especially related to transport work, which is important for increasing accuracy of emission inventory studies and cost-benefits studies of shipping.
|
|
| 7. |
- Hult, Åsa, et al.
(författare)
-
Hållbara attraktiva stationssamhällen : bilaga om Medskapande
- 2018
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Bilaga 1: Medborgardialog, enkät om framtidens resor i Lerum, sidan 2 Genomfördes digitalt via SurveyMonkey av RISE Viktoria, RISE (tidigare SP) och IVL under perioden 2016-03-28 - 2016-04-25, 237 deltagare Bilaga 2: Medborgardialog, enkät om framtidens resor i Nödinge, sidan 16 Genomfördes digitalt via SurveyMonkey av RISE Viktoria, RISE (tidigare SP) och IVL under perioden 2016-03-28 - 2016-04-25, 74 deltagare Bilaga 3: Intervjuer angående morgondagens transporttjänster, sidan 31 Genomfördes av RISE Viktoria under perioden 2016-05-12 – 2016-08-22, 12 deltagare Bilaga 4: Mobilitetstjänster workshop, sidan 36 Genomfördes av Chalmers den 2016-11-08 i Lerum, 9 deltagare Bilaga 5: Enkät: Digitala Panelen, sidan 47 Genomfördes digitalt av Chalmers under perioden 2017-05-28 – 2017-06-02, 18 deltagare Bilaga 6: Enkät: Projektutvärdering med projektpartners, sidan 61 Genomfördes av Chalmers under perioden 2018-02-22 – 2018-03-15, 20 deltagare
|
|
| 8. |
- Hult, Åsa, et al.
(författare)
-
Hållbara attraktiva stationssamhällen : bilaga om Effektiv markanvändning
- 2018
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Bilaga 9: Parkering, markanvändning och mobilitet i Nödinge centrum, IVL, sidan 2 Bilaga 10: Diskussionsunderlag för parkering och p-tal vid nybyggnation i Aspen strand, IVL, sidan 30 Bilaga 11: Planeringsverktyg för markexploatering och hållbart mobilitetsindex, IVL, sidan 41 Bilaga 12: Dataunderlag för planeringsverktyg, WSP, sidan 60 Bilaga 13: Integrering av energiaspekter i Göteborgsregionens strukturbild, GR, sidan 75
|
|
| 9. |
|
|
| 10. |
- Hult, Åsa, et al.
(författare)
-
Hållbara och attraktiva stationssamhällen
- 2018
-
Rapport (övrigt vetenskapligt/konstnärligt)abstract
- Stationssamhällena Lerum och Nödinge (i Ale kommun) strax utanför Göteborg har varit testarenor i projektet. 24 projektpartners från olika sektorer har deltagit; kommuner, regioner, forskningsorganisationer, fastighetsbolag, detaljhandel, banker, mäklare, företag inom persontransport samt en it-plattformsleverantör. Projektet tar sin utgångspunkt i två konkreta politiska mål; öka byggandet i kommunerna och minska utsläppen från transporter. Den mark som kommunerna vill bygga på ligger vanligtvis nära stationerna, men upptas ofta av bilen för parkeringar och vägar. En del av projektet handlar om hur man kan använda marken runt stationerna mer effektivt, samtidigt som den blir mer attraktiv. Tanken med minskad parkeringsyta ger skjuts åt andra lösningar än privatbil för resor och transporter. Projektet har därför utvecklat och testat lokala res- och transporttjänster (mobilitetstjänster) kopplade till ett gemensamt belöningssystem. SMART-appen, som belönar hållbart resande, användes i projektet med syftet att testa om belöningar kan få människor att ändra sina resvanor. Vidare utvecklades en affärsmodell för plattformen (appen) för lokala res- och transporttjänster. I projektet har en medskapandeprocess använts, där både projektparter och allmänhet har bjudits in att tycka till och uttrycka sina behov. Parkeringsstudien, planeringsverktyget för markexploatering samt själva projektprocessen har varit till stor nytta f
|
|
