Controller Synthesis for Timeline-based Games

Renato Acampora; Luca Geatti; Nicola Gigante; Angelo Montanari; Valentino Picotti

doi:10.4204/EPTCS.370.9

Controller Synthesis for Timeline-based Games

Renato Acampora^*, Luca Geatti^*, Nicola Gigante^*, Angelo Montanari^*, Valentino Picotti^*

^*Corresponding author for this work

Research output: Contribution to journal › Conference article › Research › peer-review

47 Downloads (Pure)

Abstract

In the timeline-based approach to planning, originally born in the space sector, the evolution over time of a set of state variables (the timelines) is governed by a set of temporal constraints. Traditional timeline-based planning systems excel at the integration of planning with execution by handling temporal uncertainty. In order to handle general nondeterminism as well, the concept of timeline-based games has been recently introduced. It has been proved that finding whether a winning strategy exists for such games is 2EXPTIME-complete. However, a concrete approach to synthesize controllers implementing such strategies is missing. This paper fills this gap, outlining an approach to controller synthesis for timeline-based games.

Original language	English
Book series	Electronic Proceedings in Theoretical Computer Science
Volume	370
Pages (from-to)	131-146
ISSN	2075-2180
DOIs	https://doi.org/10.4204/EPTCS.370.9
Publication status	Published - 20. Sept 2022
Event	13th International Symposium on Games, Automata, Logics and Formal Verification, G and ALF 2022 - Madrid, Spain Duration: 21. Sept 2022 → 23. Sept 2022

Conference

Conference	13th International Symposium on Games, Automata, Logics and Formal Verification, G and ALF 2022
Country/Territory	Spain
City	Madrid
Period	21/09/2022 → 23/09/2022

Documents & Links

10.4204/EPTCS.370.9Licence: CC BY

Open Access VersionFinal published version, 208 KBLicence: CC BY

https://cgi.cse.unsw.edu.au/~eptcs/paper.cgi?GandALF2022.9.pdfLicence: CC BY

Cite this

@inproceedings{0cf9165fee5a4ee586baf10e029fba3f,

title = "Controller Synthesis for Timeline-based Games",

abstract = "In the timeline-based approach to planning, originally born in the space sector, the evolution over time of a set of state variables (the timelines) is governed by a set of temporal constraints. Traditional timeline-based planning systems excel at the integration of planning with execution by handling temporal uncertainty. In order to handle general nondeterminism as well, the concept of timeline-based games has been recently introduced. It has been proved that finding whether a winning strategy exists for such games is 2EXPTIME-complete. However, a concrete approach to synthesize controllers implementing such strategies is missing. This paper fills this gap, outlining an approach to controller synthesis for timeline-based games.",

author = "Renato Acampora and Luca Geatti and Nicola Gigante and Angelo Montanari and Valentino Picotti",

note = "Funding Information: Nicola Gigante and Luca Geatti acknowledge the support of the Free University of Bozen-Bolzano, Faculty of Computer Science, by means of the projects TOTA (Temporal Ontologies and Tableaux Algorithms) and STAGE (Synthesis of Timeline-based Planning Games). Publisher Copyright: {\textcopyright} Acampora et al.; 13th International Symposium on Games, Automata, Logics and Formal Verification, G and ALF 2022 ; Conference date: 21-09-2022 Through 23-09-2022",

year = "2022",

month = sep,

day = "20",

doi = "10.4204/EPTCS.370.9",

language = "English",

volume = "370",

pages = "131--146",

journal = "Electronic Proceedings in Theoretical Computer Science",

issn = "2075-2180",

publisher = "Open Publishing Association",

}

TY - GEN

T1 - Controller Synthesis for Timeline-based Games

AU - Acampora, Renato

AU - Geatti, Luca

AU - Gigante, Nicola

AU - Montanari, Angelo

AU - Picotti, Valentino

N1 - Funding Information: Nicola Gigante and Luca Geatti acknowledge the support of the Free University of Bozen-Bolzano, Faculty of Computer Science, by means of the projects TOTA (Temporal Ontologies and Tableaux Algorithms) and STAGE (Synthesis of Timeline-based Planning Games). Publisher Copyright: © Acampora et al.

PY - 2022/9/20

Y1 - 2022/9/20

N2 - In the timeline-based approach to planning, originally born in the space sector, the evolution over time of a set of state variables (the timelines) is governed by a set of temporal constraints. Traditional timeline-based planning systems excel at the integration of planning with execution by handling temporal uncertainty. In order to handle general nondeterminism as well, the concept of timeline-based games has been recently introduced. It has been proved that finding whether a winning strategy exists for such games is 2EXPTIME-complete. However, a concrete approach to synthesize controllers implementing such strategies is missing. This paper fills this gap, outlining an approach to controller synthesis for timeline-based games.

AB - In the timeline-based approach to planning, originally born in the space sector, the evolution over time of a set of state variables (the timelines) is governed by a set of temporal constraints. Traditional timeline-based planning systems excel at the integration of planning with execution by handling temporal uncertainty. In order to handle general nondeterminism as well, the concept of timeline-based games has been recently introduced. It has been proved that finding whether a winning strategy exists for such games is 2EXPTIME-complete. However, a concrete approach to synthesize controllers implementing such strategies is missing. This paper fills this gap, outlining an approach to controller synthesis for timeline-based games.

U2 - 10.4204/EPTCS.370.9

DO - 10.4204/EPTCS.370.9

M3 - Conference article

AN - SCOPUS:85139943089

SN - 2075-2180

VL - 370

SP - 131

EP - 146

JO - Electronic Proceedings in Theoretical Computer Science

JF - Electronic Proceedings in Theoretical Computer Science

T2 - 13th International Symposium on Games, Automata, Logics and Formal Verification, G and ALF 2022

Y2 - 21 September 2022 through 23 September 2022

ER -

Controller Synthesis for Timeline-based Games

Abstract

Conference

Documents & Links

Fingerprint

Cite this