Representing Timelines

The presented basic core is, probably, expressive enough to represent any problem we are interested in (and, given the undecidability of the theory, even some problems in which we are not interested in). It is worth to notice, in this regard, that nothing prevents to use numeric variables as predicate arguments. It might be cumbersome, however, to represent some specific problems for which we have specialized resolution procedures. This introduces, also, some issues related to the efficiency which, probably, would be affected if not using such specialized algorithms.

To this purpose, as already mentioned, it has been introduced a procedure for verifying the consistency of the objects that appear as allowed values for all the tau variables of all the atomic formulas. Such consistency check allows the introduction of further constraints (or, more in general, decision points) that will be automatically taken into account by the resolution algorithm. The key point consists in calling different consistency check procedures according to the type of the tau variable.

Note that this does not affect the structure of the language in any way. In particular, the language does not require any changes in case the addition of additional features is demanded. The basic core (and the solver, as well) will remain agnostic of the consistency checking functions, implementing specialized algorithms, provided by possible (future) extension modules. To demonstrate the effectiveness of this approach, however, it will be shown how it applies to the case of the timelines and, specifically, to the most used of them. Specifically, each of the following timeline has its own specific behavior therefore, in order to provide its specialized algorithm, each of these timeline is implemented as a type in a native language (e.g. Java or C++).

First of all, any timeline-based planning problem requires the introduction of two numeric variables which will become always accessible by any code block. Furthermore, two predicates will be introduced for representing temporal impulses and temporal intervals. In all, before the definition of any timeline-based planning problem the following code is sent to the solver:

predicate Impulse(real at) {
  at >= origin;
  at <= horizon;
}

predicate Interval(real start, real end, real duration) {
  start >= origin;
  end <= horizon;
  duration == end - start;
  duration >= 0;
}

real origin;
real horizon;
origin >= 0;
horizon >= origin;

This will allow us to define some standard behaviors for all the timelines. In particular, this will allow us to easily express temporally scoped assertions. The following sections describe, from a language point of view, how to use some of the timelines.

State-variables

The first timeline that will be presented is the state-variable. The semantic of a state variable is that, for each time instant, the timeline can assume only one value. In order to define a state-variable it is sufficient to define a new derived type whose base type is a StateVariable. All instances of the derived type will be, consequently, state-variables. Similarly, the predicates defined within the new type will be considered as predicates of a state-variable. This allows the modeler to define predicates and rules for the state-variables at domain definition phase. As an example, the following code creates a type Robot which is a StateVariable.

class Robot : StateVariable {
}

Every predicate associated to a state-variable implicitly inherit from the Interval, therefore there is no need to define start, end and duration arguments. Furthermore, applying a rule on a derived predicate will result in the application of the Interval rule.

As an example, the following code

class Robot : StateVariable {

  predicate At(Location l) {
    duration >= 1;
    goal gt = new GoingTo(l:l, end:start);
  }

  predicate GoingTo(Location l) {
    duration >= 10;
    goal at = new At(end:start);
  }
}

defines a Robot, which is a StateVariable, which can navigate between locations. A possible problem can be

Location l0 = new Location(0, 0);
Location l1 = new Location(1, 1);
Location l2 = new Location(2, 2);

Robot r = new Robot();

fact at_0 = new r.At(l:l0, start:origin);
at_0.duration >= 1;

goal at_1 = new r.At(l:l2);

Notice that the goal at_1 cannot unify with the fact at_0 because of the different locations. Calling the consistency check procedure at this stage would put a constraint between the goal at_1 and the fact at_0 (namely, at_1.start >= at_0.end) in order to avoid the overlapping of different values in time, as required by the specific behavior of a state variable. At this stage, in order to achieve the goal at_1, the solver would execute the body of the rule associated to the At predicate which, in turn, would add the gt subgoal. Finally, the new sobgoal would be achieved by executing the code within the rule associated to the GoingTo predicate which would produce a new subgoal at that, at this stage, could unify with the initial fact at_0 leading to a solution for the whole problem.

Notice that the sequence of the above steps is not related to the language but to the solver. In particular, choosing when to call the consistency check procedures might affect strongly the overall performance of the resolution process.

Reusable resources

Reusable resources are another predefined type offered by the solver and build on top of the basic logic core. The semantic of a reusable resource is that concurrent usages of the same resource cannot exceed the capacity of the resource. Since the sole distinctive element among the different reusable resources is the capacity, the reusable resource type is completely defined. Specifically, the reusable resource is defined as a type having a single predefined predicate called Use with an amount argument representing the amount of resource usage. The Use predicate inherits from the Interval the start, end and duration arguments as well as its temporal constraints. Consequently, facts of type Use represent the usage of an amount of a resource in a given temporal interval. In addition, reusable resources have a single field called capacity which can be passed to the resource through its constructor. Finally, reusable resources has a single constructor which instantiates the capacity of the resource.

The application programming interface (API) for a reusable resource is the following:

class ReusableResource {

  real capacity;

  ReusableResource(real capacity) : capacity(capacity) {
    capacity >= 0;
  }

  predicate Use(real amount) : Interval {
    amount >= 0;
  }
}

Notice that the capacity of the resource is constrained to be greater or equal than zero. Similarly, the amount of each resource usage is constrained to be between zero and the resource capacity. Furthermore, as a reinforcement to what has been said till now, it is worth saying that creating such a type would not be enough for defining a reusable resource. This is because, in the above code, there is no trace of the specified algorithm which would avoid the temporal overlapping of too much resource usages. For this reason reusable resources have been implemented in a native language and not just in the domain description language.

The following code shows an example of reusable resources usage.

ReusableResource rr = new ReusableResource(5);

fact use = new rr.Use(amount:3, duration:5);
use.start >= 10;

Consumable resources

Consumable resources are another predefined type offered by the solver. The semantic of a consumable resource is that, despite productions and consumptions, its level must be within a max and a min value. Associated to consumable resources, two predefined predicates called Produce and Consume each one with its amount argument are intended for representing resource productions and resource consumptions. Similarly to the previous timelines, both the predicates inherit from the Interval, therefore there is no need to define start, end and duration arguments nor to introduce temporal consistency constraints. Consumable resources have two fields called capacity, representing the maximum availability of the resource, and initial_amount, representing the initial amount of the resource. Finally, consumable resources have a single constructor which takes two parameters representing the initial amount and the capacity of the resource.

The API for a consumable resource is the following:

class ConsumableResource {

  real initial_amount;
  real capacity;

  ReusableResource(real initial_amount,
                   real capacity) : initial_amount(initial_amount),
                                    capacity(capacity) {
  }

  predicate Produce(real amount) : Interval {
    amount >= 0;
  }

  predicate Consume(real amount) : Interval {
    amount >= 0;
  }
}

Notice that the minimum availability of the resource is constrained to be lower than the maximum availability of the resource.

The following code shows an example of consumable resources usage.

ConsumableResource cr = new ConsumableResource(-2, 7, 1, 5);

fact p = new cr.Produce(amount:3, duration:5);
p.start >= 10;
fact c = new cr.Consume(amount:1, duration:5);
c.start >= 10;