  In timeline-based planning, domains are described as sets of independent, but
interacting, components, whose behaviour 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 synthesising 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 realistic
problems. In this paper, we propose a novel game-theoretic approach to
timeline-based planning problems, generalising 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 decidable using a
doubly exponential amount of space.
