1 Search Results for "Tolonen, Lewis"

Document
DOI: 10.4230/LIPIcs.TIME.2018.22
Population Based Methods for Optimising Infinite Behaviours of Timed Automata

Authors: Lewis Tolonen, Tim French, and Mark Reynolds

Published in: LIPIcs, Volume 120, 25th International Symposium on Temporal Representation and Reasoning (TIME 2018)

Abstract
Timed automata are powerful models for the analysis of real time systems. The optimal infinite scheduling problem for double-priced timed automata is concerned with finding infinite runs of a system whose long term cost to reward ratio is minimal. Due to the state-space explosion occurring when discretising a timed automaton, exact computation of the optimal infinite ratio is infeasible. This paper describes the implementation and evaluation of ant colony optimisation for approximating the optimal schedule for a given double-priced timed automaton. The application of ant colony optimisation to the corner-point abstraction of the automaton proved generally less effective than a random method. The best found optimisation method was obtained by formulating the choice of time delays in a cycle of the automaton as a linear program and utilizing ant colony optimisation in order to determine a sequence of profitable discrete transitions comprising an infinite behaviour.
Cite as

Lewis Tolonen, Tim French, and Mark Reynolds. Population Based Methods for Optimising Infinite Behaviours of Timed Automata. In 25th International Symposium on Temporal Representation and Reasoning (TIME 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 120, pp. 22:1-22:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{tolonen_et_al:LIPIcs.TIME.2018.22,
  author =	{Tolonen, Lewis and French, Tim and Reynolds, Mark},
  title =	{{Population Based Methods for Optimising Infinite Behaviours of Timed Automata}},
  booktitle =	{25th International Symposium on Temporal Representation and Reasoning (TIME 2018)},
  pages =	{22:1--22:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-089-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{120},
  editor =	{Alechina, Natasha and N{\o}rv\r{a}g, Kjetil and Penczek, Wojciech},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2018.22},
  URN =		{urn:nbn:de:0030-drops-97875},
  doi =		{10.4230/LIPIcs.TIME.2018.22},
  annote =	{Keywords: Timed Automata, Heuristic Search, Ant Colony Optimisation}
}
  • Refine by Author
  • 1 French, Tim
  • 1 Reynolds, Mark
  • 1 Tolonen, Lewis

  • Refine by Classification
  • 1 Theory of computation → Automata over infinite objects

  • Refine by Keyword
  • 1 Ant Colony Optimisation
  • 1 Heuristic Search
  • 1 Timed Automata

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact