| 1. |
- Bäckström, Christer, et al.
(author)
-
Parameterized Complexity and Kernel Bounds for Hard Planning Problems
- 2013
-
In: Algorithms and Complexity. - Berlin, Heidelberg : Springer Berlin/Heidelberg. - 9783642382321 - 9783642382338 ; , s. 13-24
-
Conference paper (peer-reviewed)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.
|
|
| 2. |
- Bäckström, Christer, et al.
(author)
-
The Complexity of Planning Revisited - A Parameterized Analysis
- 2012
-
In: Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence. - : AAAI Press. - 9781577355687 - 9781577355694 ; , s. 1735-1741
-
Conference paper (peer-reviewed)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.
|
|
| 3. |
- Bäckström, Sebastian, et al.
(author)
-
Klimatsmarta lägen - Beräkning av minskade utsläpp av växthusgaser genom förtätning av stationsnära lägen
- 2013
-
Reports (other academic/artistic)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.
|
|
| 4. |
- Yaramenka, Katarina, et al.
(author)
-
Energy demand impacts of Long Heavy Duty Vehicles -Analysis of possible ways to introduce the effects of long vehicles into the GAINS model
- 2014
-
Reports (other academic/artistic)abstract
- The objective of this study was to explore possible approaches to explicitly include the use of long heavy duty vehicles (vehicles with a total weight over 40 ton and a total length over 18.75 meter) as an energy efficiency measure in the GAINS model, to assess their efficiency in terms of transport work (ton-kilometres) and traffic work (vehicle-kilometres), and to provide a basis for the analysis of the emission mitigation potential with respect to this vehicle category, currently not distinguished in the model. Potential substitution of long heavy duty vehicles with conventional European vehicles for goods transportation in Sweden was modelled and analysed. Calculation results indicated that one conventional European vehicle would consume 22 per cent less fuel per traffic work but 30 per cent more fuel per transport work than one long heavy duty vehicle. As a net effect, the total fuel consumption of heavy duty trucks would increase by 24 percent if long heavy duty vehicles were withdrawn. For the Swedish conditions represented in this analysis, the use of long heavy duty vehicles appears to be more fuel efficient than to use conventional EU vehicles. The main conclusions of this study is that it is possible to develop an integrated assessment model method for presenting long heavy duty vehicles as a fuel efficiency option in the transport sector, but that the benefit of the option is dependent on assumptions in the input data. Improved system understanding, statistical data, and scenarios would be needed for representation of long heavy duty vehicles as a general fuel efficiency option in future analyses.
|
|
| 5. |
- Åström, Stefan, et al.
(author)
-
Åtgärder för att minska utsläpp av utsläpp av NOx och PM2,5 från den svenska transportsektorn 2025 - potential och kostnader
- 2013
-
Reports (other academic/artistic)abstract
- År 2013 är EU:s ”luftår”. Under detta år ser EU över den Tematiska Strategin för Luftföroreningar (TSAP) och reviderar inom detta EU:s utsläppstaksdirektiv (NEC). Denna rapport är framtagen för att ge svenskt underlag kring åtgärdspotential och åtgärdskostnader för utsläppsminskningar av NOx och PM2,5 i den svenska transportsektorn år 2025. Analyserna genomfördes genom att utgå från officiella prognoser för aktivitet och utsläpp från vägtransporter och arbetsmaskiner. Ur litteratur söktes sedan efter möjliga åtgärder som skulle kunna minska utsläpp ytterligare. Information om åtgärder och dess effekt på prognoserna kvantifierades och resulterande utsläpp samt åtgärdskostnader beräknades. Endast ett urval av åtgärder kunde analyseras inom den tillgängliga projekttiden. Analysens resultat byggde på några viktiga förutsättningar: utsläpp enligt utsläppskrav motsvarar faktiska utsläpp; förbättring av bränsleeffektivitet sker enligt prognos; analyserade åtgärder som medförde ändringar i fordons- och maskinbestånd minskar antalet gamla fordon mest; det är hypotetiskt möjligt att ändra utsläppskrav så att energieffektivisering kan följas av lägre NOx och PM2,5-utsläpp. Den åtgärd som föreföll mest lovande för utsläppsminskning av NOx var en föryngring av lastbilsflottan. Hybridisering av arbetsmaskiner var visserligen mer kostnadseffektivt men har till 2025 en mycket liten potential. Då nya personbilar antas bli mer energieffektiva än nuvarande, och dessutom ha lägre utsläpp av NOx och PM2,5 tydde analyserna på att det vore fördelaktigt med styrmedel som forcerar föryngring av personbilsflottan till 2025.
|
|
