2026-07-20T06:35:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9787 2024-03-06T10:44:55Z ddc:004 open_access

Population Based Methods for Optimising Infinite Behaviours of Timed Automata Tolonen, Lewis French, Tim Reynolds, Mark Timed Automata Heuristic Search Ant Colony Optimisation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lewis Tolonen and Tim French and Mark Reynolds 2018 Is Part Of LIPIcs, Volume 120, 25th International Symposium on Temporal Representation and Reasoning (TIME 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TIME.2018.22 urn:nbn:de:0030-drops-97875 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2018.22 eng https://creativecommons.org/licenses/by/3.0/legalcode