License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TIME.2018.22
URN: urn:nbn:de:0030-drops-97875
URL: https://drops.dagstuhl.de/opus/volltexte/2018/9787/
Tolonen, Lewis ;
French, Tim ;
Reynolds, Mark
Population Based Methods for Optimising Infinite Behaviours of Timed Automata
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.
BibTeX - Entry
@InProceedings{tolonen_et_al:LIPIcs:2018:9787,
author = {Lewis Tolonen and Tim French and Mark Reynolds},
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 = {Natasha Alechina and Kjetil N{\o}rv{\aa}g and Wojciech Penczek},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9787},
URN = {urn:nbn:de:0030-drops-97875},
doi = {10.4230/LIPIcs.TIME.2018.22},
annote = {Keywords: Timed Automata, Heuristic Search, Ant Colony Optimisation}
}
Keywords: |
|
Timed Automata, Heuristic Search, Ant Colony Optimisation |
Collection: |
|
25th International Symposium on Temporal Representation and Reasoning (TIME 2018) |
Issue Date: |
|
2018 |
Date of publication: |
|
08.10.2018 |