2 An illustrative example

Let us consider the following toy planning problem. We assume a team of robots, made of two robots that are different in terms of efficiency, speed, and energy consumption, but are both initially present at the same location. The team is given the following mission: to deliver a packet to another location by a deadline and with a final level of energy greater than or equal to a given threshold, by choosing for that one of the two robots. No energy production is possible when in motion. More precisely, we assume the following data:

• • a set of locations the robots can use to move from the initial location Li ∈ to the final one Lg ∈ |Lg ≠ Li;

• • an initial time Ti and a deadline Tg, both positive integers;

• • for each robot r ∈ {1, 2}, an initial level of energy Ei[r] and, for both robots, a minimum final level of energy Eg, all positive integers;

• • for each robot r ∈ {1, 2} and each pair of locations l ₁, l ₂ ∈ |l ₁ ≠ l ₂:

  • ○ a boolean Mo[r, l ₁, l ₂] equal to 1 if robot r can move directly from l ₁ to l ₂ and conversely, and equal to 0 otherwise;

  • ○ a positive integer duration Du[r, l ₁, l ₂] of the direct move of robot r from l ₁ to l ₂ and conversely, when possible;

  • ○ a positive integer energy consumption Co[r, l ₁, l ₂] of the direct move of robot r from l ₁ to l ₂ and conversely, when possible too.

Let us consider the specific instance of Figure 3, in which are represented, for each robot, the possible direct moves and, for each of them, the associated duration and energy consumption. In addition, we assume that Li = A, Lg = D, Ti = 0, Tg = 20, Ei[1] = 10, Ei[2] = 8, and Eg = 2. We observe that the first robot is more efficient, faster, but more energy consuming than the second one.

Figure 3

Graphical representation of an instance of the toy planning problem. For each robot and each possible direct move is associated an edge labeled by a pair [d, c], where d is the duration and c is the energy consumption

The only solution of this instance is to use the first robot to move from A to B, C, and finally D.

3 The Constraint Network on Timelines framework

Let us use now the toy planning problem described in the previous section to illustrate the basic definitions of the CNT framework. Although these definitions differ significantly from the ones given in Verfaillie et al. (Reference Verfaillie, Pralet and Lemaître2008), they are semantically equivalent.

3.7 Static constraints

Static constraints are used to limit the possible combinations of assignments of static variables.

Definition 8. A static constraint c is simply a CSP constraint whose scope S(c) is limited to static variables.

In the toy planning problem, there is a priori no such constraint. However, let us assume that we use graph algorithms to precompute for each robot the minimum and the maximum length, in terms of number of edges, to move from the initial to the final location, without going twice through the same location, ignoring the time and energy constraints. Let Nmin[r] and Nmax[r] be these minimum and maximum lengths. For example, in the specific instance we consider, we have: Nmin[1] = Nmin[2] = 2, Nmax[1] = 3, and Nmax[2] = 2. This would allow us to define the following static constraint between static variable r and static horizon variable h:

(1)

3.8 Dynamic constraints

Dynamic constraints are used to limit the possible combinations of assignments of static and dynamic variables. The difficulty is that the set of dynamic variables, associated with time references and timelines, is not fixed. It depends on the assignments of the horizon variables. This leads us to a definition of what is a dynamic constraint which is not as obvious as the previous definitions are. We will use several examples to illustrate it.

Definition 9. A dynamic constraint c is a tuple 〈SV, ST, SX, f〉 where:

• • SV is a finite set of static variables; SV is the scope of c in terms of static variables;

• • ST is a finite set of time references; ST is the scope of c in terms of time references;

• • SX is a finite set of timelines; SX is the scope of c in terms of timelines;

• • let SH be the set of horizon variables associated with the time references in ST and the timelines in SX; we have Footnote 2; f is a function which associates a finite set of CSP constraints with each assignment A of the horizon variables in SH.

For each assignment A of the horizon variables in SH, let SD(A) be the set of dynamic variables induced by A in the time references in ST and the timelines in SX. We have Footnote 3. It is assumed that, for each assignment A of the horizon variables in SH, the scope S(c) of each CSP constraint c in f(A) is included in SV ∪ SD(A).

We will use SV(c), ST(c), SX(c), and SH(c) to denote the scope of a dynamic constraint c in terms of, respectively, static variables, time references, timelines, and horizon variables, and f(c) to denote its associated function.

To illustrate this definition, let us come back to our toy planning problem. To specify the initial state, we need the following three constraints c ₂, c ₃, and c ₄:

(2)

(3)

(4)

The first one is a dynamic constraint defined by the tuple c ₂ = 〈∅,{t}, ∅, f ₂〉 with f ₂ the function which associates with each assignment of h the unique unary CSP constraint t ₁ = Ti on dynamic temporal variable t ₁ (in this particular case, function f ₂ is a constant).

The second one is defined by the triple c ₃ = 〈∅, ∅, {l}, f ₃〉 with f ₃ the function which associates with each assignment of h the unique unary CSP constraint l ₁ = Li on dynamic atemporal variable l ₁.

The third one is defined by the triple c ₄ = 〈{r}, ∅, {e}, f ₄〉 with f ₄ the function which associates with each assignment of h the unique binary CSP constraint e ₁ = Ei[r] between static variable r and dynamic atemporal variable e ₁.

Then, to specify state transitions, we need the following three constraints c ₅, c ₆, and c ₇:

(5)

(6)

(7)

For example, the first one is a dynamic constraint defined by the tuple c ₅ = 〈{r}, ∅, {l}, f ₅〉 with f ₅ the function which associates with each assignment a of h the set of (a−1) ternary CSP constraints, each one connecting static variable r and dynamic atemporal variables l _i−1 and l _i.

The second one is defined in a similar way by a triple c ₆ = 〈{r},{t},{l},f ₆〉 and the third one by a triple c ₇ = 〈{r}, ∅, {e, l}, f ₇〉.

To specify the goal state, we need the following constraint c ₈:

(8)

This constraint is defined by the tuple c ₈ = 〈∅, ∅, {l}, f ₈〉 with f ₈ the function which associates with each assignment a of h the unique unary CSP constraint l_a = L_g.

The deadline Tg and the minimum level of energy Eg are enforced via the domains of time reference t and timeline e.

Finally, if we want to enforce that the robot does not go several times through the same location, because this would be counterproductive, we can use the following constraint c ₉:

(9)

This constraint is defined by the tuple c ₉ = 〈∅, ∅, {l}, f ₉〉 with f ₉ the function which associates with each assignment a of h the unique global CSP constraint .

3.12 Solution of a constraint network on timelines

Definition 14. A solution S of a constraint network N on timelines is an assignment of N such that all the constraints in CV(N) and CX(N) are satisfied.

For example, 〈r = 1, h = 4, t ₁ = 0, t ₂ = 5, t ₃ = 13, t ₄ = 18, l ₁ = A, l ₂ = B, l ₃ = C, l ₄ = D, e ₁ = 10, e ₂ = 8, e ₃ = 4, e ₄ = 2〉 is a solution of the instance of the toy planning problem we consider and, in fact, the only solution of this instance. See Figure 4 for a tabular representation of this solution.

Figure 4

Tabular representation of the only solution, with r = 1 (first robot chosen)

4 Modeling the mission management problem for a team of unmanned air vehicles

The problem we consider is inspired from the international competition of small unmanned air vehicles (Micro Air Vehicle Conference Competition; see, for example, http://www.nal.res.in/mav08/). Its data are as follows:

• • a number NA of areas to be visited, each containing a target; areas are assumed to be all different; they are numbered from 1 to NA;

• • for each area a∈[1..NA], its type TY_a, with three possible values EI, SC, and DR:

  • ○ if TY_a = EI, a contains a target to be identified by using a camera and performing an eight over a;

  • ○ if TY_a = SC, a contains a target to be localized by using a camera too and performing a scan over a;

  • ○ if TY_a = DR, a contains a target to be touched by using one marble and performing a drop;

• • a unique takeoff and landing area HO for all the vehicles; number 0 is associated with this area;

• • a number NV of vehicles; vehicles are numbered from 1 to NV;

• • for each vehicle v∈[1..NV], a boolean CA_v equal to 1 if and only if v embeds a camera, the number NM_v of marbles initially available in v, and the speed SP_v of v;

• • for each vehicle v∈[1..NV] and each action ac among actions TO, LA, EI, SC, and DR (takeoff, landing, eight, scan, and drop), the expected duration DU_{v, ac} of a when performed by v;

• • for each pair a, a′∈[0..NA] of areas, including HO, the distance DI_a,a′ from a to a′;

• • a minimum duration DUmin between two takeoffs or landings of different vehicles at HO.

• • a maximum mission duration MD;

The problem is to visit and handle all the areas using the team of vehicles. See Figure 5 for a graphical representation of a solution of an instance involving three vehicles, four targets to be identified, three to be localized, and three to be touched.

Figure 5

Graphical representation of a solution of the mission management problem for a team of unmanned air vehicles

To show the modeling power and the versatility of the CNT framework, we propose three models of this problem:

1. 1. in Section 4.1, an action-based model, inspired from SAT or CSP encodings of planning problems (Kautz & Selman, Reference Kautz and Selman1992), which describes the preconditions and the effects of the possible actions and uses only dynamic variables and constraints, except the static horizon variables;

2. 2. in Section 4.2, a mixed model, which modifies the previous one by introducing some static variables and constraints;

3. 3. in Section 4.3, a constraint-based model, inspired from CSP encodings of resource constrained scheduling problems (Baptiste et al., Reference Baptiste, Pape and Nuijten2001), which uses only static variables and constraints.

4.1 Action-based model

Let AC = {TO, LA, EI, SC, DR, GO, NO} (takeoff, landing, eight, scan, drop, goto, and nothing) be the set of possible actions. The NO action is useful because all the vehicles but one must wait before taking off because of the minimum duration between takeoffs and landings.

We have NV vehicles that will evolve in parallel, with no synchronization between the starting times of the actions performed by each vehicle. As a consequence, NV sets of timelines can be used to model this problem, each set associated with one vehicle and having its own time reference. With each vehicle v∈[1..NV], we associate a time reference ti_v and four timelines, which share the same time reference ti_v: a timeline fl_v to represent the fact that v is flying or not, a timeline at_v to represent its current position (area), a timeline nm_v to represent the current number of available marbles, and a timeline ac_v to represent the current action.

Since, for each vehicle v, there is at least one step associated with the initial state and at most NSmax = 2·NA + 3 steps in the case in which all the areas are handled by the same vehicle, the domain of the horizon of each time reference ti_v is [1..NSmax]. Since MD is the maximum duration, the domain of each time reference ti_v is [0..MD]. For each vehicle v, the domains of the timelines fl_v, at_v, nm_v, and ac_v are, respectively, {0, 1}, [0..NA], [0..NM_v], and AC. These choices result in the following constraints:

Initial state of each vehicle:

(10)

(11)

(12)

(13)

(14)

Final state of each vehicle:

(15)

(16)

(17)

Conditions and effects of a takeoff:

(18)

Conditions and effects of a landing:

(19)

Conditions and effects of an eight:

(20)

Conditions and effects of a scan:

(21)

Conditions and effects of a drop:

(22)

Conditions and effects of a move:

(23)

Conditions of a null action:

(24)

Conditions of change for attributes fl, at, and nm:

(25)

(26)

(27)

Each area must be handled once and only once by the team of vehiclesFootnote 4:

(28)

Minimum duration between takeoffs and landings:

(29)

For each vehicle, an action cannot be followed by the same action:

(30)

No landing can be followed by a takeoff:

(31)

For each vehicle, null actions occur only at the beginning or at the end of the sequence of actions:

(32)

Such a modeling is driven by two principles used by SAT or CSP encodings of planning problems (Kautz & Selman, Reference Kautz and Selman1992):

• • the presence of an action implies its preconditions and its effects, and effects are effective changes in timeline values (see constraints c ₁₈ to c ₂₄);

• • any effective change in a timeline value is justified by an action (see constraints c ₂₅ to c ₂₇).

Constraints c ₂₈ are global constraints on the actions performed by the team of vehicles. Constraints c ₃₀ to c ₃₂ constrain the sequence of actions performed by each vehicle and rule out inconsistent or sub-optimal solutions, such as performing a landing followed by a takeoff.

Resource constraints such as the fact that a drop cannot be triggered when the number of available marbles is null are enforced by the domain of timelines nm_v. In the same way, the maximum mission duration is enforced by the domain of time references ti_v.

4.2 Mixed model

We can modify the previous model by introducing static variables such as, for each area, the vehicle in charge of handling it. For each area a∈[1..NA], let v_a be a static variable of domain [1..NV], which represents the vehicle in charge of a.

The introduction of such variables modifies constraints c ₂₀, c ₂₁, and c ₂₂. For example, constraint c ₂₀, which specifies the conditions and effects of an eight, becomes:

(33)

More importantly, it simplifies constraint c ₂₈, because it suffices now to specify that each area must be handled once and only once by the vehicle in charge of it:

(34)

It would be possible to go further by introducing other static variables, such as, for each vehicle v and each position p in the sequence of the areas visited by v, the area visited by v at position p in the sequence. We do not detail the associated model and go directly to a pure constraint-based model.

4.3 Constraint-based model

It is indeed possible to build a pure constraint-based model, using only static variables and constraints. Let us consider the following static variables:

• • for each area a ∈ [1..NA], a variable V_a of domain [1..NV], which represents the vehicle in charge of a;

• • for each vehicle v ∈ [1..NV], a variable n_v of domain [0..NA], which represents the number of areas handled by v;

• • for each vehicle v ∈ [1..NV] and each position p ∈ [1..NA], a variable a_{v ,p} of domain [0..NA], which represents the area visited by v at position p in the sequence of the areas visited by v; by default, a_{v, p} = 0 when no area is visited by v at position p;

• • for each vehicle v ∈ [1..NV], a variable s_v of domain [0..MD], which represents the starting time of the takeoff of v;

• • finally, for each vehicle v ∈ [1..NV], a variable e_v of domain [0..MD], which represents the ending time of the landing of v.

Note that some variables, such as n_v or e_v, are redundant, but useful to express some constraints in a more concise way. This choice of variables induces the following constraints:

Constraints between variables v_a and variables n_v:

(35)

Constraints on variables a_{v, p}:

(36)

Constraints between variables v_a and variables a_{v, p}:

(37)

Constraints between variables n_v and variables a_v,p:

(38)

A camera is required for identification and localization:

(39)

One marble is required for each touching:

(40)

Duration of the mission of each vehicle:

(41)

Minimum duration between takeoffs and landings. Let be the set of the takeoff and landing temporal intervals enlarged by DUmin. For any set ints of temporal intervals, let be the global scheduling constraint which enforces that there is no overlap between temporal intervals in ints:

(42)

5 Modeling the mission management problem for an Earth observing satellite

The problem we consider now is a very simplified version of the problem of management of the observations performed by an autonomous Earth observing satellite. For example, data memorization and downloading constraints are omitted. A description of the whole problem, a timeline-based model, and approximate solving algorithms are presented in Pralet and Verfaillie (Reference Pralet and Verfaillie2008a). The data of the simplified version are as follows:

• • a planning horizon defined by its starting and ending times STA and END;

• • satellite features such as the minimum and maximum levels of energy ENmin and ENmax, the power Psun delivered by the solar panels during day periods, the powers Psat and Pob consumed, respectively, by the platform and by any observation action, and the rotation speed MS of the sight mirror;

• • an initial state defined by the initial energy level EN ₀ and the initial orientation OR ₀ of the sight mirror;

• • a set OB of observations to be performed with, for each observation o ∈ OB, the observation duration DO_o, the number NO_o of possible observation windows over the planning horizon and, for each window k ∈ [1..NO_o], its starting time SO_{o, k} and the required orientation OR_{o, k} of the sight mirror;

• • a number NE of eclipse windows for the satellite over the planning horizon with, for each window k ∈ [1..NE], its starting time SE_k and its duration DE_k.

Two observations of different ground areas cannot be performed in parallel. Moreover, sufficient time is necessary between the end of an observation and the beginning of the following one to allow change in the sight mirror orientation to be performed.

The problem is to perform an optimal subset of OB over the planning horizon. The definition of the optimization criterion is omitted in this article. See Figure 6 for a temporal representation of a solution involving nine observation windows and two eclipse windows.

Figure 6

Temporal representation of a solution of the mission management problem for an Earth observing satellite

Although we proposed three different models of the mission management problem for a team of unmanned air vehicles in Section 4, we propose only one mixed model of this problem which we consider to be the most appropriate. This CNT model combines static variables to represent observation decisions with dynamic variables to represent the way state attributes such as energy evolve with time. It therefore combines static and dynamic constraints.

To represent observation decisions, we can first use the following static variables: for each observation o ∈ OB, the chosen observation window no_o ∈ [0..NO_o] (value 0 represents the fact that o is not performed) and the associated observation starting and ending times so_o and eo_o ∈ [STA..END].

Then, to represent the evolution of the state of the satellite, we can use a set of fully synchronized timelines. In fact, we consider one time reference ti and three timelines, which share the same time reference ti: two timelines ob and ec, which respectively, represent the fact that the satellite is observing or not and in an eclipse period or not, and one timeline en which represents the current level of available energy.

Since there are at least two steps associated with times STA and END and at most steps in the case where all the observations are performed and all the window starting and ending times are different, the domain of time reference ti is [STA..END] and the domain of its horizon is [2..NSmax]. The domains of timelines ob, ec, and en are, respectively, {0,1}, {0,1}, and [ENmin..ENmax]. These choices result in the following constraints:

Starting and ending times of an observation: the starting time is the starting time of the chosen window; the ending time is the starting time plus the duration; if the observation is not performed, then the starting and ending times are arbitrarily set to STA:

(43)

(44)

(45)

Constraints between observations: if two observation windows are conflicting and if the first one is performed, the second one cannot be performed; moreover, if an observation window is in conflict with the initial mirror orientation, it cannot be performed:

(46)

(47)

Initial state:

(48)

(49)

Observing and eclipse states:

(50)

(51)

Energy evolution: it is assumed to be piecewise linear; the available energy is therefore equal to the energy previously available, plus what has been produced by the solar panels if the satellite was not in an eclipse period and minus what has been consumed by the platform and by observation if the satellite was observing, with a maximum of ENmax; note that the minimum level of energy ENmin is enforced via the domain of timeline en:

(52)

Temporal positions of the successive steps: let and be, respectively, the sets of effective observation and eclipse starting and ending times; let ; the temporal position of the next step is defined as follows:

(53)

Final state:

(54)

Constraints c ₄₃ to c ₄₇ are static, whereas the following ones are dynamic.

Taking advantage of the bounded number of steps, this model has been first implemented using the CP tool Comet (http://www.comet-online.org/). Then, we designed a more efficient dedicated algorithm, implemented in Java and intended to be embedded in the on-board control software of a satellite.

6 How to use the Constraint Network on Timelines framework

The objective of the CNT framework is to offer a modeler all the basic elements that enable him/her to model any discrete event dynamic system and the properties he/she knows or wants to verify or to enforce on it. However, since these elements are very basic, it may be difficult to select the right ones and to organize them in order to model properly a complex system. In this section, we provide a modeler with some guidelines that may help him/her in this task.

First, since the CNT framework is an extension of the CSP framework, it is possible to reuse all the modeling experience accumulated in the CSP framework and in related frameworks such as SAT or ILP, by looking at models of scheduling and planning problems in these frameworks.

Second, experience in modeling using variable and constraint-based frameworks such as CSP, SAT, or ILP shows that the crucial choice is the choice of the variables. Since the CNT framework distinguishes static variables from dynamic ones, it is crucial to decide on what the static and dynamic variables will be. Although the three models of the same problem in Section 4 show that several options are often candidate, some sensible rules can be followed. Static variables are useful to represent choices that must be made once and only once such as, for example, in the illustrative problem of Section 2, the robot that is chosen for the mission or, in the problem of Section 4, for each area a, the vehicle in charge of a. Time references are naturally useful to represent the temporal positions of the successive steps. As for the timelines, they are useful to represent the choices that must be made at each step such as, for example, in the illustrative problem of Section 2, the location that is visited at each step. They are also useful to represent the consequences at each step of the choices made for static or dynamic variables such as, for example, in the illustrative problem of Section 2, the level of energy at each step. In fact, it is sensible to associate a timeline with each dynamic attribute x of the system, that is, with each attribute x whose value evolves step after step, whatever x represents: a component of the state of the system or its environment, or an event from the system, its environment, or its controller. Then, the definition of constraints naturally follows the choice of variables. If constraints cannot be easily expressed with the chosen variables, the choice of variables must be reconsidered.

Third, timelines may be either synchronized by sharing the same time reference, or non-synchronized by using several time references. Synchronized timelines are useful when evolutions are fully synchronized, as in the illustrative problem of Section 2, or partially but strongly synchronized as in the problem of Section 5, where observations and eclipses together impact the level of energy. In contrast, non-synchronized timelines are useful when evolutions are fully non-synchronized or partially but weakly synchronized as in the problem of Section 4, where vehicles must synchronize their actions only when taking off and landing. Using several time references implies defining temporal constraints between time references in order to partially synchronize them, as Constraint 29 does in the problem of Section 4.

7 Related work

Contrary to classical frameworks used in the planning and scheduling community, such as STRIPS, RCPSP, or PDDL (Fox & Long, Reference Fox and Long2003), which are all built around the notions of action, precondition, effect, duration, and resource consumption, the CNT framework is a more basic modeling framework, built around the notions of time reference, timeline, and constraint. As shown in this article, this is one of its strengths because this allows complex dynamic phenomena such as concurrent interdependent evolutions or complex requirements such as constraints on sequences of actions or states to be precisely modeled. From the knowledge engineering point of view, this may be one of its weaknesses because building and checking models may be more difficult when using lower-level constructs. However, nothing prevents us from building on top of the basic CNT framework generic higher-level constructs that would be closer to the modeler point of view. This would enable the modeler to choose freely, according to his own habits and needs, between low and high level modeling constructs. However, the identification of the right constructs and their implementation remains a work to be done, for which experience in planning, scheduling, and CP will be useful.

With regard to the use of constraints in planning and scheduling, the CSP framework and associated CP tools have been used for many years to model and solve scheduling problems (Baptiste et al., Reference Baptiste, Pape and Nuijten2001). Things are more recent and a bit more problematic with planning problems. The main obstacle to a CSP modeling of planning problems is clearly the unknown, possibly unbounded, number of steps, and thus of variables and constraints. Such an obstacle is absent from scheduling problems, where the number of tasks and resources to manage is known. Nareyek et al. (Reference Nareyek, Freuder, Fourer, Giunchiglia, Goldman, Kautz, Rintanen and Tate2005) propose a survey of various attempts to overcome this obstacle and to combine Artificial Intelligence planning and CP. The CNT framework follows the last approach among the three they distinguish:

• • in the first approach used by planning tools such as IxTeT (Ghallab & Laruelle, Reference Ghallab and Laruelle1994) or RAX-PS (Jónsson et al., Reference Jónsson, Morris, Muscettola, Rajan and Smith2000), CP is used as a kind of subroutine to efficiently solve subproblems, such as time or resource problems, generated by the main planning procedure;

• • in the second approach initialized by Kautz and Selman (Reference Kautz and Selman1992)in the SAT framework and extended by van Beek and Chen (Reference van Beek and Chen1999)and Do and Kambhampati (Reference Do and Kambhampati2001) to the CSP framework, a CSP is built to solve planning problems over a fixed horizon of k steps, and k is incremented when no plan is found;

• • in the last approach, a planning problem is tackled as a kind of dynamic CSP with a horizon that is not fixed; such an approach is used by the Visopt ShopFloor system (Barták, Reference Barták2002), by the EUROPA planner, built on top of the CAIP framework (Constraint-based Attribute and Interval Planning (Frank & Jónsson, Reference Frank and Jónsson2003)), and by the CPT planner (Vidal & Geffner, Reference Vidal and Geffner2006).

With regard to the use of timelines and constraints on timelines to model planning and scheduling problems, this idea is present in many works at the frontier between planning and scheduling (Ghallab & Laruelle, Reference Ghallab and Laruelle1994; Muscettola, Reference Muscettola1994; Cesta & Oddi, Reference Cesta and Oddi1996; Barták, Reference Barták2002; Frank & Jónsson, Reference Frank and Jónsson2003; Fratini et al., Reference Fratini, Pecora and Cesta2008).

However, in Ghallab and Laruelle (Reference Ghallab and Laruelle1994), Muscettola (Reference Muscettola1994), and Cesta and Oddi (Reference Cesta and Oddi1996), constraints are mainly used to manage temporal and resource constraints, whereas a classical planning procedure is used to manage causal links between actions. In contrast, in the CNT framework, all the decisions related to actions, time, and resources are managed the same way via constraints and via the same procedure, which can combine constraint propagation and search.

The CAIP framework (Frank & Jónsson, Reference Frank and Jónsson2003) is probably the closest one to the CNT framework. Attributes in the CAIP framework are equivalent to timelines in the CNT framework. However, in the CAIP framework, relations between attributes take the form of intervals on which a given predicate holds, linking a given set of attributes. Constraints between intervals take the form of configuration rules, which specify that the presence of a given interval implies the presence of at least one set of intervals among a given set of sets of intervals. In contrast, the CNT framework uses more basic notions of step and of temporal position and value associated with any step. This allows any kind of constraint to be defined between any kind of variable: dynamic temporal and atemporal variables and static variables, including horizon variables (see, for example, Constraint 8 (resp. 54) for a constraint which links a horizon variable with atemporal (resp. temporal) variables). However, if we consider that the notion of interval is important, nothing prevents us from defining it by using the basic elements of the CNT framework, following the same philosophy that led to the introduction in CP Optimizer (http://www.ilog.com/products/cpoptimizer/) of interval variables that can be used in any model together with classical variables.

The modeling principles used by the Visopt ShopFloor system (Barták, Reference Barták2002) are close to the ones of the CAIP framework: use of intervals, called slots. Each slot is filled by an activity and a sequence of slots is associated with each resource. Constraints link temporal positions and activities of slots. Constraint Logic programming (CLP) allows slots and constraints on them to be dynamically introduced. As previously said, the CNT framework is more basic and thus more flexible. However, the notions of resource, activity, and slot could be built on top of it, if useful.

Last, (Fratini et al., Reference Fratini, Pecora and Cesta2008) propose a generic software architecture, called OMPS, which allows timeline-based models of component and inter-component behaviors to be defined and managed. Such an architecture could be used on top of the CNT framework.

Although many works inspired by First-order Logics, such as PDDL or CAIP, adopt a predicate-based modeling style, the CNT framework, inspired by practice in Automatic Control (see, for example, automata and synchronous languages (Benveniste et al., Reference Benveniste, Caspi, Edwards, Halbwachs, Guernic and de Simone2003)), adopts a more natural attribute-based modeling style, as the recent ANML language (Smith et al., Reference Smith, Frank and Cushing2008) does.

To sum up, we think that the key advantage of the CNT framework is to be a pure CSP framework from which it inherits a clear semantics and all the associated solving algorithms (constraint propagation, backtrack search, local search … ), which only need to be extended to the new framework.

In this article, we focused on planning and scheduling problems, but it must be stressed that the modeling capabilities of the CNT framework can be used in other contexts such as failure diagnosis, situation recognition, or validation. For example, the problem of building a consistent activity plan and the problem of identifying a consistent failure scenario can be modeled the same way as a CNT consistency problem. Moreover, the problem of proving that a given controller will never lead a system to an undesirable state or to a constraint violation can be modeled as a CNT inconsistency problem.

8 Research directions

Extending the CNT framework to optimization is straightforward, either by introducing optimization variables that are constrained by other problem variables, as is usually done in CP, or by allowing local soft constraints that are local cost functions as done in the WCSP framework (Weighted CSP (Schiex et al., Reference Schiex, Fargier and Verfaillie1995)).

Our current work focuses on algorithmic issues. We have already designed and implemented generic CNT solving algorithms, using a combination of tree search and lazy introduction of variables and constraints, on top of the CP Choco solver (http://choco-solver.net/). These algorithms work assuming finite domains for horizon variables, time references, and timelines. They show that it is possible and may be beneficial not to systematically assign horizon variables first. They have been successfully experimented on planning problems coming from the IPC (Pralet & Verfaillie, Reference Pralet and Verfaillie2008b). Further work will focus on generic CNT solving algorithms, using greedy or local search.

Another important direction of research is the extension of the CNT framework to uncertainty (Puterman, Reference Puterman1994) via a necessary distinction between controllable and uncontrollable timelines and via the introduction of local feasibility, plausibility, and utility functions, as was done, for example, in the PFU framework (Pralet et al., Reference Pralet, Verfaillie and Schiex2007) in a static context.