Affiliations: Consiglio Nazionale delle Ricerche, Istituto di Scienze e Tecnologie della Cognizione, Via S.Martino della Battaglia 44, I-00185 Rome, Italy. {andrea.orlandini, amedeo.cesta, simone.fratini}@istc.cnr.it | Dipartimento di Scienze Fisiche, Università di Napoli ”Federico II”, Via Cinthia, I-80126 Naples, Italy. [email protected] | Dipartimento di Informatica, Università di Roma ”La Sapienza”, Via Salaria 198, I-00198 Rome, Italy. [email protected]
Note: [] Authors are partially supported by EU under the ULISSE project (Contract FP7.218815), and MIUR under the PRIN project 20089M932N (funds 2008). Cesta and Fratini have been partially supported by European Space Agency (ESA) within the Advanced Planning and Scheduling Initiative (APSI). Address for correspondence: Via S.Martino della Battaglia 44, I-00185 Rome, Italy
Note: [] Author is partially supported by EU under the DEXMART project (Contract FP7.216239)
Note: [] Author is partially supported by EU under the ULISSE project (Contract FP7.218815)
Abstract: Timeline-based planning techniques have demonstrated wide application possibilities in heterogeneous real world domains. For a wider diffusion of this technology, a more thorough investigation of the connections with formal methods is needed. This paper is part of a research program aimed at studying the interconnections between timeline-based planning and standard techniques for formal validation and verification (V&V). In this line, an open issue consists of studying the link between plan generation and plan execution from the particular perspective of verifying temporal plans before their actual execution. The present work addresses the problem of verifying flexible temporal plans, i.e., those plans usually produced by least-commitment temporal planners. Such plans only impose minimal temporal constraints among the planned activities, hence are able to adapt to on-line environmental changes by trading some of the retained flexibility. This work shows how a model-checking verification tool based on Timed Game Automata (TGA) can be used to verify such plans. In particular, flexible plan verification is cast as a model-checking problem on those automata. The effectiveness of the proposed approach is shown by presenting a detailed experimental analysis with a real world domain which is used as a flexible benchmark.
Keywords: Timeline-based Planning, Validation and Verification, Model Checking
