DROPS

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.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}
}

Document

DOI: 10.4230/DagSemProc.09351.3

Awareness and forgetting of facts and agents

Authors: Hans Van Ditmarsch and Tim French

Published in: Dagstuhl Seminar Proceedings, Volume 9351, Information processing, rational belief change and social interaction (2009)

Abstract

We propose various logical semantics for change of awareness. The setting is that of multiple agents that may become aware of facts or other agents, or forget about them. We model these dynamics by quantifying over propositional variables and agent variables, in a multi-agent epistemic language with awareness operators, employing a notion of bisimulation with a clause for `same awareness'. The quantification is over all different ways in which an agent can become aware (or forget). Logics for change of awareness combine well with logics for informational change, as when a public announcement simultaneously makes you aware of an issue (`a plane just crashed on Schiphol Airport').

Cite as

Hans Van Ditmarsch and Tim French. Awareness and forgetting of facts and agents. In Information processing, rational belief change and social interaction. Dagstuhl Seminar Proceedings, Volume 9351, pp. 1-8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{vanditmarsch_et_al:DagSemProc.09351.3,
  author =	{Van Ditmarsch, Hans and French, Tim},
  title =	{{Awareness and forgetting of facts and agents}},
  booktitle =	{Information processing, rational belief change and social interaction},
  pages =	{1--8},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2009},
  volume =	{9351},
  editor =	{Giacomo Bonanno and James Delgrande and Hans Rott},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09351.3},
  URN =		{urn:nbn:de:0030-drops-22286},
  doi =		{10.4230/DagSemProc.09351.3},
  annote =	{Keywords: Awareness, knowledge, multi-agent systems, dynamics}
}

Search Results

Documents authored by French, Tim

Population Based Methods for Optimising Infinite Behaviours of Timed Automata

Abstract

Cite as

Awareness and forgetting of facts and agents

Abstract

Cite as

Thanks for your feedback!

Could not send message