A formal account of planning with flexible timelines

Planning for real world problems with explicit temporal constraints is a challenging problem. Among several approaches, the use of flexible timelines in Planning and Scheduling (P&S) has demonstrated to be successful in a number of concrete applications, such as, for instance, autonomous space systems. A flexible timeline describes an envelope of possible solutions which can be exploited by an executive system for robust on-line execution. A remarkable research effort has been dedicated to design, build and deploy software environments, like EUROPA, ASPEN, and APSI-TRF, for the synthesis of timeline-based P&S applications. Several attempts have also been made to characterize the concept of timelines. Nevertheless, a formal characterization of flexible timelines and plans is still missing. This paper presents a formal account of flexible timelines aiming at providing a general semantics for related planning concepts such as domains, goals, problems, constraints and flexible plans. Some basic properties of the defined concepts are also stated and proved. A simple running example inspired by a real world planning domain is exploited to illustrate the proposed formal notions. Finally, a planning tool, called Extensible Planning and Scheduling Library (EPSL), is briefly presented, which is able to generate flexible plans that are compliant with the given semantics.

Publication type: 
Contributo in atti di convegno
Author or Creator: 
Cialdea Mayer, Marta
Orlandini, Andrea
Umbrico, Alessandro
Source: 
21st International Symposium on Temporal Representation and Reasoning (TIME), pp. 37–46, Verona, Italy, 8-10 September 2014
Date: 
2014
Resource Identifier: 
http://www.cnr.it/prodotto/i/312907
https://dx.doi.org/10.1109/TIME.2014.27
info:doi:10.1109/TIME.2014.27
http://www.scopus.com/record/display.url?eid=2-s2.0-84909590208&origin=inward
urn:isbn:9781479942275
Language: 
Eng
ISTC Author: 
AndreA Orlandini's picture
Real name: