Abstract
We consider an optimal-reachability problem for a timed automaton with respect to a linear cost function which results in a weighted timed automaton. Our solution to this optimization problem consists of reducing it to a (parametric) shortest-path problem for a finite directed graph. The directed graph we construct is a refinement of the region automaton due to Alur and Dill. We present an exponential time algorithm to solve the shortest-path problem for weighted timed automata starting from a single state, and a doubly-exponential time algorithm to solve this problem starting from a zone of the state space.
This work is partially supported by the DARPA/ITO MoBIES grant F33615-00-C-1707, the NSF Career award CCR97-34115, the SRC award 99-TJ-688, the MURST grant TOSCA, the DARPA JFACC grant N66001-99-C-8510, and the University of Pennsylvania Research Foundation.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R. Alur, C. Courcoubetis, and T.A. Henzinger. Computing accumulated delays in real-time system. In Proc. of the Fifth International Conference on Computer-Aided Verification, CAV’93, LNCS 697, pages 181–193, 1993.
R. Alur and D.L. Dill. A theory of timed automata. Theoretical Computer Science, 126:183–235, 1994.
E. Asarin and O. Maler. As soon as possible: Time optimal control for timed automata. In Proc. of the 2nd International Workshop on Hybrid Systems: Computation and Control, LNCS 1569, pages 19–30, 1999.
E. Asarin, O. Maler, and A. Pnueli. Symbolic controller synthesis for discrete and timed systems. In Proc. of the 2nd International Workshop on Hybrid Systems, LNCS 999, pages 1–20, 1995.
G. Behrman, T. Hune, A. Fehnker, K. Larsen, P. Pettersson, R. Romijn, and F. Vaandrager. Minimum-cost reachability for priced timed automata. In this Volume.
A. Church. Logic, arithmetic, and automata. In Proc. of the International Congress of Mathematics, pages 23–35, 1962.
C. Courcoubetis and M. Yannakakis. Minimum and maximum delay problems in real-time systems. In Proc. of the 3rd International Conference on Computer Aided Verification, LNCS 575, pages 399–409, 1991.
R. M. Karp and J. R. Orlin. Parametric shortest path algorithm with an application to cyclic staffing. Discrete Applied Math., 3:37–45, 1981.
J. Lygeros, C. Tomlin, and S.S. Sastry. Controllers for reachability specifications for hybrid systems. Automatica, 35(3):349–370, March 1999.
O. Maler, A. Pnueli, and J. Sifakis. On the synthesis of discrete controllers for timed systems. In Proc. of the 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS’95, LNCS 900, pages 229–242, 1995.
P. Nierbert, S. Tripakis, and S. Yovine. Minimum-time reachability for timed automata. In Proc. of the 8-th IEEE Mediterranean Conference on Control and Automation, 2000.
O. Shakernia, G. J. Pappas, and S. Sastry. Decidable controller synthesis for classes of linear systems. In Proc. of the 3rd International Workshop on Hybrid Systems: Computation and Control, HSCC’00, LNCS 1790, pages 407–420, 2000.
W. Thomas. On the synthesis of strategies in infinite games. In Ernst W. Mayr and Claude Puech, editors, 12th Annual Symposium on Theoretical Aspects of Computer Science, STACS’95, LNCS 900, pages 1–13, 1995.
H. Wong-Toi. The synthesis of controllers for linear hybrid automata. In Proc. of the 36th IEEE CDC, San Diego, CA, December 1997.
N. E. Young, R. Tarjan, and J. Orlin. Faster parametric shortest path and minimum balance algorithms. Networks, 21 (2):205–221, 1991.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Alur, R., La Torre, S., Pappas, G.J. (2001). Optimal Paths in Weighted Timed Automata. In: Di Benedetto, M.D., Sangiovanni-Vincentelli, A. (eds) Hybrid Systems: Computation and Control. HSCC 2001. Lecture Notes in Computer Science, vol 2034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45351-2_8
Download citation
DOI: https://doi.org/10.1007/3-540-45351-2_8
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41866-5
Online ISBN: 978-3-540-45351-2
eBook Packages: Springer Book Archive