An executable semantics of flexible plans in terms of timed game automata

Robust plan execution in uncertain and dynamic environments
is a critical issue for plan-based autonomous systems,
especially when uncertain events coexist with temporal flexibility.
In this regard, many Planning and Scheduling systems model
temporal uncertainty by means of flexible timelines, each of which
describes the behavior of one of the system components, and
consists of a sequence of events whose begin and end times range
within given intervals.
This work enriches a previously proposed formal characterization
of flexible timelines and plans, considering the difference
between controllable and uncontrollable activities. Two main
sources of uncertainty are considered: i) some components of the
system may depend on an external environment and cannot be
planned by the executive; ii) there may be tasks whose duration
cannot be exactly foreseen in advance. Such notions are formally
defined and the consequent controllability issues are addressed,
focusing, in particular, on dynamic controllability.
Partially controllable flexible plans are given a semantics in
terms of networks of timed game automata (TGA), showing
how they can be encoded into such networks. The translation
allows for exploiting existing verification tools for TGA, such as
UPPAAL-TIGA, in order to check the dynamic controllability
property for flexible plans and, possibly, generate a dynamic
execution strategy that can be used for robust plan execution.
Some preliminary experiments aimed at evaluating the feasibility
of the approach are also presented.

Publication type: 
Contributo in atti di convegno
Author or Creator: 
Marta Cialdea Mayer
Andrea Orlandini
International Symposium on Temporal Representation and Reasoning (TIME 2015), pp. 160–169, 2015
Resource Identifier:
ISTC Author: 
AndreA Orlandini's picture
Real name: