Planning and execution with flexible timelines: a formal account

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 has been shown to be successful in a number of concrete applications, such as, for instance, autonomous space systems. This paper builds on previous work and presents a revised and extended formal account of flexible timelines with the aim of providing a general semantics for related planning concepts such as domains, goals, problems, constraints, and flexible plans. Some sources of uncertainty are also modeled in the proposed framework and taken into account in the characterization of valid plans that are assumed not to take decisions on components the planner cannot control. A formal definition of different forms of plan controllability is also proposed.