Minimum-Cost Reachability for Priced Timed Automata

Gerd Behrmann, Ansgar Fehnker, Thomas Hune, Kim Guldstrand Larsen, Paul Pettersson, Judi Romijn, Frits W. Vaandrager

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    Abstract

    This paper introduces the model of linearly priced timed automata as an extension of timed automata, with prices on both transitions and locations. For this model we consider the minimum-cost reachability problem: i.e. given a linearly priced timed automaton and a target state, determine the minimum cost of executions from the initial state to the target state. This problem generalizes the minimum-time reachability problem for ordinary timed automata. We prove decidability of this problem by offering an algorithmic solution, which is based on a combination of branch-and-bound techniques and a new notion of priced regions. The latter allows symbolic representation and manipulation of reachable states together with the cost of reaching them.
    Original languageEnglish
    Title of host publicationHybrid Systems: Computation and Control
    Subtitle of host publication4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings
    EditorsMaria Domenica Di Benedetto, Alberto L. Sangiovanni-Vincentelli
    PublisherSpringer
    Pages147-161
    Number of pages15
    ISBN (Electronic)978-3-540-45351-2
    ISBN (Print)978-3-540-41866-5
    DOIs
    Publication statusPublished - 2001
    Event4th International Workshop on Hybrid Systems: Computation and Control 2001 - Rome, Italy
    Duration: 28 Mar 200130 Mar 2001
    Conference number: 4

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume2034

    Conference

    Conference4th International Workshop on Hybrid Systems: Computation and Control 2001
    Abbreviated titleHSCC 2001
    CountryItaly
    CityRome
    Period28/03/0130/03/01

    Fingerprint

    Costs
    Computability and decidability

    Cite this

    Behrmann, G., Fehnker, A., Hune, T., Larsen, K. G., Pettersson, P., Romijn, J., & Vaandrager, F. W. (2001). Minimum-Cost Reachability for Priced Timed Automata. In M. D. D. Benedetto, & A. L. Sangiovanni-Vincentelli (Eds.), Hybrid Systems: Computation and Control: 4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings (pp. 147-161). (Lecture Notes in Computer Science; Vol. 2034). Springer. https://doi.org/10.1007/3-540-45351-2_15
    Behrmann, Gerd ; Fehnker, Ansgar ; Hune, Thomas ; Larsen, Kim Guldstrand ; Pettersson, Paul ; Romijn, Judi ; Vaandrager, Frits W. / Minimum-Cost Reachability for Priced Timed Automata. Hybrid Systems: Computation and Control: 4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings. editor / Maria Domenica Di Benedetto ; Alberto L. Sangiovanni-Vincentelli. Springer, 2001. pp. 147-161 (Lecture Notes in Computer Science).
    @inproceedings{9b7f4608fe2a401a90191541bba23ac5,
    title = "Minimum-Cost Reachability for Priced Timed Automata",
    abstract = "This paper introduces the model of linearly priced timed automata as an extension of timed automata, with prices on both transitions and locations. For this model we consider the minimum-cost reachability problem: i.e. given a linearly priced timed automaton and a target state, determine the minimum cost of executions from the initial state to the target state. This problem generalizes the minimum-time reachability problem for ordinary timed automata. We prove decidability of this problem by offering an algorithmic solution, which is based on a combination of branch-and-bound techniques and a new notion of priced regions. The latter allows symbolic representation and manipulation of reachable states together with the cost of reaching them.",
    author = "Gerd Behrmann and Ansgar Fehnker and Thomas Hune and Larsen, {Kim Guldstrand} and Paul Pettersson and Judi Romijn and Vaandrager, {Frits W.}",
    year = "2001",
    doi = "10.1007/3-540-45351-2_15",
    language = "English",
    isbn = "978-3-540-41866-5",
    series = "Lecture Notes in Computer Science",
    publisher = "Springer",
    pages = "147--161",
    editor = "Benedetto, {Maria Domenica Di} and Sangiovanni-Vincentelli, {Alberto L.}",
    booktitle = "Hybrid Systems: Computation and Control",

    }

    Behrmann, G, Fehnker, A, Hune, T, Larsen, KG, Pettersson, P, Romijn, J & Vaandrager, FW 2001, Minimum-Cost Reachability for Priced Timed Automata. in MDD Benedetto & AL Sangiovanni-Vincentelli (eds), Hybrid Systems: Computation and Control: 4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings. Lecture Notes in Computer Science, vol. 2034, Springer, pp. 147-161, 4th International Workshop on Hybrid Systems: Computation and Control 2001, Rome, Italy, 28/03/01. https://doi.org/10.1007/3-540-45351-2_15

    Minimum-Cost Reachability for Priced Timed Automata. / Behrmann, Gerd; Fehnker, Ansgar; Hune, Thomas; Larsen, Kim Guldstrand; Pettersson, Paul; Romijn, Judi; Vaandrager, Frits W.

    Hybrid Systems: Computation and Control: 4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings. ed. / Maria Domenica Di Benedetto; Alberto L. Sangiovanni-Vincentelli. Springer, 2001. p. 147-161 (Lecture Notes in Computer Science; Vol. 2034).

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    TY - GEN

    T1 - Minimum-Cost Reachability for Priced Timed Automata

    AU - Behrmann, Gerd

    AU - Fehnker, Ansgar

    AU - Hune, Thomas

    AU - Larsen, Kim Guldstrand

    AU - Pettersson, Paul

    AU - Romijn, Judi

    AU - Vaandrager, Frits W.

    PY - 2001

    Y1 - 2001

    N2 - This paper introduces the model of linearly priced timed automata as an extension of timed automata, with prices on both transitions and locations. For this model we consider the minimum-cost reachability problem: i.e. given a linearly priced timed automaton and a target state, determine the minimum cost of executions from the initial state to the target state. This problem generalizes the minimum-time reachability problem for ordinary timed automata. We prove decidability of this problem by offering an algorithmic solution, which is based on a combination of branch-and-bound techniques and a new notion of priced regions. The latter allows symbolic representation and manipulation of reachable states together with the cost of reaching them.

    AB - This paper introduces the model of linearly priced timed automata as an extension of timed automata, with prices on both transitions and locations. For this model we consider the minimum-cost reachability problem: i.e. given a linearly priced timed automaton and a target state, determine the minimum cost of executions from the initial state to the target state. This problem generalizes the minimum-time reachability problem for ordinary timed automata. We prove decidability of this problem by offering an algorithmic solution, which is based on a combination of branch-and-bound techniques and a new notion of priced regions. The latter allows symbolic representation and manipulation of reachable states together with the cost of reaching them.

    U2 - 10.1007/3-540-45351-2_15

    DO - 10.1007/3-540-45351-2_15

    M3 - Conference contribution

    SN - 978-3-540-41866-5

    T3 - Lecture Notes in Computer Science

    SP - 147

    EP - 161

    BT - Hybrid Systems: Computation and Control

    A2 - Benedetto, Maria Domenica Di

    A2 - Sangiovanni-Vincentelli, Alberto L.

    PB - Springer

    ER -

    Behrmann G, Fehnker A, Hune T, Larsen KG, Pettersson P, Romijn J et al. Minimum-Cost Reachability for Priced Timed Automata. In Benedetto MDD, Sangiovanni-Vincentelli AL, editors, Hybrid Systems: Computation and Control: 4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings. Springer. 2001. p. 147-161. (Lecture Notes in Computer Science). https://doi.org/10.1007/3-540-45351-2_15