Change search
ReferencesLink to record
Permanent link

Direct link
Least-Violating Planning in Road Networks from Temporal Logic Specifications
KTH, School of Computer Science and Communication (CSC), Computer Vision and Active Perception, CVAP.ORCID iD: 0000-0003-4173-2593
2016 (English)In: 2016 ACM/IEEE 7th International Conference on Cyber-Physical Systems, ICCPS 2016 - Proceedings, Institute of Electrical and Electronics Engineers (IEEE), 2016, 7479106Conference paper (Refereed)
Abstract [en]

In this paper, we consider the problem of automated plan synthesis for a vehicle operating in a road network, which is modeled as a weighted transition system. The vehicle is assigned a set of demands, each of which involves a task specification in the form of a syntactically co-safe LTL formula, a deadline for achieving this task, and a demand priority. The demands arrive gradually, upon the run of the vehicle, and hence periodical replanning is needed. We particularly focus on cases, where all tasks cannot be accomplished within the desired deadlines and propose several different ways to measure the degree of demand violation that take into account the demand priorities. We develop a general solution to the problem of least-violating planning and replanning based on a translation to linear programming problem. Furthermore, for a particular subclass of demands, we provide a more efficient solution based on graph search algorithms. The benefits of the approach are demonstrated through illustrative simulations inspired by mobility-on-demand scenarios.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2016. 7479106
Keyword [en]
Embedded systems, Linear programming, Motor transportation, Program translators, Roads and streets, Specifications, Temporal logic, Vehicles, General solutions, Graph search
National Category
Robotics
Identifiers
URN: urn:nbn:se:kth:diva-194577DOI: 10.1109/ICCPS.2016.7479106ISI: 000386348200019ScopusID: 2-s2.0-84979052881ISBN: 978-150901772-0OAI: oai:DiVA.org:kth-194577DiVA: diva2:1041676
Conference
7th ACM/IEEE International Conference on Cyber-Physical Systems, ICCPS 2016, 11 April 2016 through 14 April 2016, Vienna; Austria
Funder
Swedish Research Council
Note

QC 20161031

Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2016-11-18Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Tumova, Jana
By organisation
Computer Vision and Active Perception, CVAP
Robotics

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 20 hits
ReferencesLink to record
Permanent link

Direct link