Flexible Timeline-based Planning
Planning is one of the core fields of Artificial Intelligence. Planning aims at providing systems (agents) with the capacity of autonomously solve problems. Broadly speaking a planning process synthesises a set of actions that, if executed, bring the agent from a known initial state to a desired goal state. Autonomy is a key feature in contexts where human intervention is not always possible (e.g. Mars rover exploration or AUVs controllers).
There is a huge amount of literature about planning in AI. Many different approaches have been developed ranging from those based on pure logical formalisms (e.g. STRIPS/PDDL) to other combining techniques from other fields (e.g. operational research or constraint programming). The Flexible Timeline-based Planning (FTLP) is a relatively recent paradigm, introduced in early 90s by Nicola Muscettola. FTLP solving process focuses on the temporal properties of a problem. A plan describes an envelope of possible temporally flexible behaviours of domain features. These behaviours are called flexible timelines. Temporal flexibility is an important feature of this approach because it allows to consider at planning time, possible delays in the execution of planned activities. Flexible timeline can be exploited by an executive system for robust online execution of plans. Therefore in FTLP we talk about Planning & Scheduling (P&S) as the solving process aims at integrating the synthesis of the actions (Planning) needed to solve a problem with the temporal placement of them (Scheduling).
Several Timeline-based applications have been successfully applied in different real world scenarios thanks to its capacity of dealing with temporal and resource constraints. A remarkable research effort has been dedicated to design, build and deploy software environments (EUROPA, APSI-TRF or IxTeT) for the synthesis of Timeline-based Planning & Scheduling (P&S) applications. However despite its practical success a uniform formalisation of FTLP approach is still missing.
In this context we are working at proposing a formal account of flexible timelines aiming at providing a general semantics of related planning concepts [Cialdea, Orlandini, Umbrico – TIME 2014]. Our objective is to completely formalise FTLP approach by describing what timeline-based planning is and how to model and solve problems by defining general heuristics. Simultaneously we are developing a tool, the Extensible Planning & Scheduling Library (EPSL) which implements the semantics we are proposing to actually solve timeline-based problems [ESA-ASTRA 2013]. Moreover we are also interested in considering execution issues by taking into account controllability properties and robust execution of (temporally) flexible plans.
