-
Notifications
You must be signed in to change notification settings - Fork 1
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.
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 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 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 min
and max
, representing the minimum and maximum availability of the resource. Additionally, consumable resources have two fields called initial_amount
and final_amount
, representing the initial and final amount of the resource. Finally, consumable resources have a single constructor which takes four parameters representing the minimum and maximum availability of the resource and the initial and final amount of the resource.
The API for a consumable resource is the following:
class ConsumableResource {
real min;
real max;
real initial_amount;
real final_amount;
ReusableResource(real min, real max,
real initial_amount,
real final_amount) : min(min),
max(max),
initial_amount(initial_amount),
final_amount(final_amount) {
min <= max;
}
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;
Batteries are similar to consumable resources having the minimum availability of the resource constrained to be greater or equal than 0. The behavior, however, is slightly different. Specifically, batteries allow overproductions. In other words it is allowed to exceed the upper limit, however, the surplus is lost. In addition, productions are called charges.
The API for a battery is, therefore, is the following:
class Battery {
real min;
real max;
real initial_amount;
real final_amount;
ReusableResource(real min, real max,
real initial_amount,
real final_amount)
: min(min),
max(max),
initial_amount(initial_amount),
final_amount(final_amount) {
min >= 0;
min <= max;
}
predicate Charge(real amount) : Interval {
amount >= 0;
}
predicate Consume(real amount) : Interval {
amount >= 0;
}
}