Minimum-Cost Reachability for Priced Timed Automata

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

January 2001

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

Available as PostScript, PDF.

 

Last modified: 2003-06-08 by webmaster.