planning([]).
planning([on(X,Y,T)|Rest]):-
on(X,Y,T),
planning(Rest).
on(X,Y,T) :- initially(X,Y,T0), T0 #<= T, not moved(X,T0,T).
on(X,Y,T) :- T1 #>0, T1 #<= T, not moved(X,T1,T), move(X,Y,T1).
moved(X,T1,T2) :- Y::1..22, Y ## X, T1 #< T2, between1(T9,T1,T2), move(X,Y,T9).
where on(X,Y,T) is a (the only) property predicate meaning that block X is on block or position Y at time T. The predicate moved(X,T1,T2) corresponding to the clipped predicate of the Event Caclculus, is defined to hold if block X was moved within the time period T1 to T2 thus terminating the previous position of X at T1. Note that in this simple formulation of the problem we are assuming that the effects of moves start to hold instantaneously.
The abducible predicates are A={move(-,-,-)} as we only have one type of action in the example domain that we are considering. This action of move(X,Y,T) means that block X is moved to position Y (that may be another block) at time T. The general integrity constraints for the preconditions of this action are the constraints which state that a block X can be moved to a new position Y only if the block X and the position Y are both clear i.e. there is no block on top of either of them. These can be represented by the following integrity rules in IC:
ic:- move(X,Y,T), initially(Z,X,T1), not moved(Z,T1,T).
ic:- move(X,Y,T), move(Z, X1, T1), T \== T1, not moved(Z,T1,T),
T#>=T1 #/\ X #= X1.
ic:- move(X,Y,T), number(Y), initially(Z,Y,T1), not moved(Z,T1,T).
ic:- move(X,Y,T), move(Z,Y1,T1), T \== T1, not moved(Z,T1,T),
T #>= T1 #/\ Y #= Y1.
ic:- move(X,Y,T), initially(Z,Y1,T1), nott moved(Z,T1,T), Y#=Y1.
Note that in the second integrity constraint X1 is not written (unified) as X but we use an explicit equality X #= X1 so that one way to satisfy this integrity constraint is by setting the constraint X ## X1. Similarly for Y1 and Y in the forth and fifth integrity constraint.
Two more constraints which state that different moves can never take place at the same time instance are:
ic:- move(X1,Y1,T1), other_move(X2,Y2,T2), X1=\=X2, T1 #= T2.
ic:- move(X,Y1,T1), other_move(X,Y2,T2), Y1\==Y2, T1 #= T2.
Negation as failure is treated through abduction and hence all occurances of not moved(-,-,-) in the program P will be replaced by a new predicate not_moved(-,-,-) . Furthermore, the set of integrity constraints IC has to be extended with the additional constraint:
ic:- not_moved(X,T1,T2), moved(X,T1,T2). ,
unfolded to :
ic:- not_moved(X,T1,T2), move(X,Z,T), between1(T,T1,T2).
The set of abducible predicates has to be extended with the declaration abducible_predicate(not_moved/3).
Example. You can retrieve the planning program in its final form here. Initial states with either 15 blocks or 12 blocks can aslo be retrieved and compiled together with the planning program. These two files of the initial states contain also some sample queries together with their answer and their execution time (all the experiments took place on a SUN Ultra workstation with 64 MB RAM).
Job-shop scheduling is defined as the problem of assigning in time n jobs on m machines where each job is a request for the scheduling of a set of tasks with a particular order. Each job has a specified release time after which its execution can start and has to complete its work before a specified deadline. In addition, the schedule must satisfy other basic constraints such as the precedence constraints that define in which order the different tasks of a job should be carried out and the capacity constraints that prevent resources from being allocated to more tasks than they can process at one time (resource capacity). In ACLP the precedence and resource capacity constraints can be represented with the following integrity constraints in IC:
ic :- start(J, T1,R1,S1), previous(J, T1, T2, S2), task(T2,D2,_), S1 #< (S2 + D2).
ic :- start(J1,T1,R,S1),ostart(J2,T2,R,S2),T1=\=T2, not decoupled(T1,S1,T2,S2).
where start(J,T,R,S) denotes that task T of job J starts execution at time S on resource (machine) R and is an abducible predicate. The program P of the ACLP job-shop scheduling theory is a simple representation of the basic features of the problem that generates the abductive hypotheses start(J,T,R,S) for each job and task from some top level goal. It also contains the definition of auxiliary predicates that are used in the integrity constraints e.g. decoupled/4
You can retrieve the program in its final form here . In a relevant file you can also retrieve a set of 20 jobs (100 tasks) together with their release times, their deadlines and durations that can be scheduled using the previous ACLP program.
Other constraints specific to the particular application may be needed, making the problem more difficult to solve. For example, assume that we are given a new requirement on the initial problem which says that: if any task T2 is using the resource R2 then the related with R2 resource R1 has to be idle till the end of T2 . This is represented in ACLP by the integrity constraint:
% Resource R1 must be idle when R2 is running
ic :-
start(J1,T1,R1,S1),start(J2,T2,R2,S2),T1=\=T2, related(R2,R1),
task(T2,Dur,_), S1 #<= S2 + Dur, S2 #< S1.
Such complex constraints can be found in the relevant file.
Another important feature of the ACLP framework is that it facilitates the adoption of new requirements with a small number of changes to the existing solution. One of the main reasons for this is the inherent ability of abduction to reason with a non-empty initial set of assumptions (partial solution) which enables us to use the old solution and recalculate only what is affected (rendered inconsistent) by the changes in the requirements. This helps to achieve a small number of changes in the existing solution.
To illustrate this consider an example where after we have obtained a solution to a given job-shop problem a new requirement is added which says that: resource 5 is temporarly out of order (e.g. between the time points 12 and 20).This new requirement is easily incorporated in the ACLP representation of the problem by adding the new integrity constraint:
% Resource 5 is out of order between the time points 12 and 20
ic :- start(J,T,5,S), S #> 12, S #< 20.
We can now run the ACLP query: