Planning is a core field of Artificial Intelligence since its beginnings and, there are many planning techniques that have been introduced in the literature. The timeline-based approach is a particular temporal planning paradigm which has been successfully applied in many real world scenarios. However despite its practical success, there is not a shared view of this approach. In this context, my PHD project aims at investigating timeline-based planning and applying this technique to solve real-world problems. The main research objectives this paper describe are: (i) formally characterize timeline-based approach to planning by taking into account also controllability features of a domain; (ii) develop a planning framework (EPSL) and propose a methodology for modeling and solving problems with timelines; (iii) apply the proposed approach to real-world problems. Concerning this last point, Human-Robot Collaboration (HRC) scenarios present many critical points a planning technique must deal with in order to successfully face this kind of problems. In this regards, several characteristics of the envisaged approach to timeline-based planning, are well-suited for this kind of applications. Thus the paper presents some initial contributions for an HRC scenario within an ongoing research project.
Timeline-based planning has been introduced in early 90s [
The timeline-based approach provides an expressive representation of time and temporal constraints and allows an ”easy” integration of planning and scheduling within the same solving approach. This is a key point for addressing real-world problem where time and concurrency represent important features of the problems. However, despite its practical success of timeline-based planning, a clear and common formalization of the related planning concepts is missing. Each systems applies its own interpretation of timeline-based planning. Therefore, there is not a common semantics for timelinebased concepts, there are differences in the way timeline-based problems are modeled and even solved. In this context, it is not easy to compare the features of the different approaches and also make a comparison with more ”standard” planning techniques like PDDL. 2
In this context, my PHD project aims at investigating timeline-based planning approach in order to propose a comprehensive and shared semantics for the main planning concepts, propose a modeling and solving approach for designing effective P&S applications and realize a general-purpose planning framework which complies with the proposed interpretation. Specifically my PHD project pursues the idea of integrating temporal uncertainty and hierarchy-based solving capabilities. Temporal uncertainty allows to model more realistic domains because in real-world usually not all the relevant features of a planning domain are controllable. A controllability-aware solving approach allows to generate plans with some desired properties with respect to their (robust) execution. Moreover a hierarchy-based modeling and solving approach is wellsuited to effectively address real-world problems. It allows a description of the problem at different levels of abstractions and a structured solving procedure.
At the current state of the work we have obtained some interesting results with
respect to the research objectives described above. Specifically, the work [
A timeline-based planning domain is composed by a set of features to be controlled over time. These features are modeled by means of multi-valued state variables that specify causal and temporal constraints characterizing the allowed temporal behavior. A state variable describes the set of values v 2 V the related feature may assume over time with their flexible duration. For each value vi 2 V the state variable describes also the set of values vj 2 V (where i 6= j) that are allowed to follow vi and the related controllability property. If a value v 2 V is tagged as controllable then the system can decide the actual duration of the value. If a value v 2 V is tagged as uncontrollable instead, the system cannot decide the duration of the value, the value is under the control of the environment. There are two types of state variable in a planning domain. The planned variables that model the domain features the system can control (or partially control). The external variables that model domain features completely outside the control of the system. External state variables model features of the environment the system cannot control but that must care about in order to successfully carry out activities.
The behavior of state variables may be further restricted by means of synchronization rules that specify additional temporal constraints between different values. Synchronization rules represent global constraints that describe how different features of the domain must behave together. Planning with timelines usually entails considering sequence of valued intervals and time flexibility is taken into account by requiring that the duration of valued intervals, called tokens, range within given bounds. In this regard, a flexible plan is composed by a set of flexible timelines that represent an envelop of non-flexible behaviors of the related domain features.
Given the concepts above, a planning problem is defined by a temporal horizon H, a planning domain D, a planning goal G which specifies a set of tokens and constraints to satisfy and the observations O which completely describes the flexible timelines for all the external variables of the domain. In this context, a flexible plan is a solution for a planning problem if it satisfies the planning goal and if it does not make any hypothesis on the behavior of the external variables (i.e. the plan does not change the observation of the problem). 2.2
Given the concepts above it is not easy to generate an effective timeline-based specification which captures all the relevant features of the problem and provides a wellsuited structure to facilitate problem solving. Hierarchical approaches, like HTN have shown good results and capabilities to effectively solve real-world problems. Indeed, hierarchy-based approaches decompose complex problems in several levels of abstractions by providing a structured specification the solving procedure may exploit to generate solutions.
In this regard, the proposed modeling approach identifies two additional state variables with respect to the external ones introduced by the formalization. The primitive variables model the set of low-level tasks that can be directly executed by the system to control. The functional variables model the complex tasks that can be performed by combining the available primitive ones. Namely functional variables abstract the behavior of the system by modeling the functional capabilities it can perform. Thus, synchronization rules define a hierarchical task decomposition which decomposes the values of functional variables in terms of temporal constraints between values of variables at different hierarchical levels going from functional values to primitive values (complex domains may have several functional layers between the top of the hierarchy and the primitive layer). The resulting hierarchical structure of the domain is then exploited by the solving process through domain independent heuristics that encode useful information for problem resolution. 2.3
The hierarchical timeline-based planning approach with uncertainty pursued within the
PHD project has been implemented by developing a general-purpose planning
framework called EPSL (Extensible Planning and Scheduling Library). EPSL provides a
modular and general-purpose software library to support the design of timeline-based
applications [
The key point of EPSL modularity is the planner interpretation. Indeed, in the EPSL
framework, a planner is a compound element whose solving process is affected by the
specific set of modules applied. Thus, EPSL-based P&S applications are obtained as
the composition of several modules each of which is responsible for managing a
particular aspect of the problem resolution. Moreover, EPSL relies on and extends the
representation functionalities of APSI-TRF framework [
In this regard, EPSL complies with the pursued approach to timelines therefore, it
provides solving capabilities to generate plans showing some desired properties with
respect to the controllability problem. Specifically, EPSL-based planners try to generate
pseudo-controllable plans, where pseudo-controllability represents a necessary but not
sufficient requirement for dynamic controllability [
Industrial robots have demonstrated their capability to meet the needs of many application domains, offering accuracy, efficiency and flexibility of use. A current pursued challenge is the co-presence of robot and human in the same work environment collaborating in a common goal. In general when robot-worker collaboration is needed, there are a number of open issues to be taken into account, first of those is human safety that needs to be enforced in a comprehensive way. A key open trend in manufacturing is the design of shared fenceless working spaces in which safe human-robot collaboration is seamlessly implemented. In general, future human-robot-systems will necessarily be able to dynamically adapt their actions in a cost-effective way, act safely and allow for preserving the specific competences and skills of human workers in their interactions with robots. Classical approaches are not very efficient to face the different dynamics of the human behaviors. In this regard, they often require major overhauls of the control code in order to adapt the system to the specific needs of the human or the production process.
In such contexts, planning techniques can provide the flexibility needed to
dynamically adapt the control process. As part of the overall FOURBYTHREE control
architecture, a dynamic task planner is to provide continuous task synthesis features, safety
critical properties at execution time, and user modeling ability for adapting tasks to the
particular human at work. The integration of plan synthesis and continuous plan execution
has been demonstrated in both the main approaches to Artificial Intelligence planning:
timeline based planning (e.g., [
A possible application of the envisaged approach to timeline-based planning is represented by the HRC scenarios considered within the research project FOURBYTHREE1. In general, HRC scenarios represent an interesting application context for the objectives of my PHD project. Indeed, this kind of applications entail features like the capability of managing the temporal uncertainty of the human behavior, managing temporal flexible events/activities and a hierarchical specification of the production processes, that are well-suited for the proposed timeline-based approach. In such a context, there are several features the planning framework must care about in order to control the robot and guarantee a safe collaboration with the human operator. In particular, it is possible to identify three main features to address: (i) supervision, to represent and satisfy the production requirements to complete the factory processes; (ii) coordination, to assign tasks to the human and the robot according to the desired collaboration modalities; (iii) uncertainty, to manage the temporal uncertainty about the activities of the human operator that the system cannot control.
Thus, we are currently developing an EPSL-based task planning framework which
models the human as a planned variable where all values are uncontrollable. It means
that the dynamic task planing framework must plan for coordinating robot’s and
human’s tasks to be performed by not making any hypothesis on the actual duration of
human’s operations. Indeed, human’s tasks are uncontrollable, so the system must carry
out robot’s tasks by dynamically adapting to the actual behavior of the human. The
dynamic task planning framework leverage the capabilities of the hierarchical
timelinebased planning with uncertainty approach in order to realize a human aware planning
mechanism which provides the robot with the capability to safely interact with the
human. In this regards, the work [
This paper has described the research context and the main objectives of my PHD project. Specifically, the paper has briefly described the main results obtained that concern the formal characterization of timeline-based planning with uncertainty, the hierarchy-based modeling/solving approach and the development of EPSL, a general purpose framework which concretely applies the proposed approach and provides the reasoning capabilities for generating pseudo-controllable plans. Finally the paper has introduced an on-going work concerning an HRC scenario in a manufacturing context which shows many features that may show the capabilities of the envisaged approach to timeline-based planning. 1 http://www.fourbythree.eu