Nicola Gigante, Angelo Montanari, Andrea Orlandini, Marta Cialdea Mayer, Mark Reynolds |
PosterID:
42
PDF
Slides
Poster
|
| In timeline-based planning, domains are described as sets of independent, but interacting, components, whose behavior over time (the set of timelines) is governed by a set of temporal constraints. A distinguishing feature of timeline-based planning systems is the ability to integrate planning with execution by synthesizing control strategies for flexible plans. However, flexible plans can only represent temporal uncertainty, while more complex forms of nondeterminism are needed to deal with a wider range of real-world domains. In this paper, we propose a novel game-theoretic approach to timeline-based planning problems, generalizing the state of the art while uniformly handling temporal uncertainty and nondeterminism. We define a general concept of timeline-based game and we show that the notion of winning strategy for these games is strictly more general than that of control strategy for dynamically controllable flexible plans. Moreover, we show that the problem of establishing the existence of such winning strategies is 2EXPTIME-complete. | |
| Canb | 10/28/2020, 17:00 – 18:00 |
| 10/30/2020, 00:00 – 01:00 |
| Paris | 10/28/2020, 07:00 – 08:00 |
| 10/29/2020, 14:00 – 15:00 |
| NYC | 10/28/2020, 02:00 – 03:00 |
| 10/29/2020, 09:00 – 10:00 |
| LA | 10/27/2020, 23:00 – 00:00 |
| 10/29/2020, 06:00 – 07:00 |
On timeline-based games and their complexity
Nicola Gigante, Angelo Montanari, Andrea Orlandini, Marta Cialdea Mayer, Mark Reynolds
On the Computational Complexity of Multi-Agent Pathfinding on Directed Graphs
Bernhard Nebel
Dynamic Controllability and (J,K)-Resiliency in Generalized Constraint Networks with Uncertainty
Matteo Zavatteri, Romeo Rizzi, Tiziano Villa
Search-Guidance Mechanisms for Numeric Planning Through Subgoaling Relaxation
Enrico Scala, Alessandro Saetti, Ivan Serina, Alfonso E. Gerevini