Planning with Continuous Time: Solutions
************************************************
*** REPRESENTATION 1, in the language of smodels
*** By Paolo Ferraris (otto@cs.utexas.edu)
************************************************
% to be executed with:
% lparse -c ms=4 -c t=4 -c l=10 -c a=3 | smodels < car2
% EXPLANATION
%
% a(t) = k(t)*A, where k(t) is
%
% 1 if accelerator is pressed AND v(t) is lower than MS,
% -1 if brake is activated AND v(t) is greater than 0,
% 0 otherwise
%
% If k is constant in [t,t+Dt), if v(t) is the speed of the car at time t
%
% v(t+Dt) = v(t) + k(t)*A*Dt.
%
% we want v to be increased or decreased each time by 1 to be sure that we
% may change value for k when the car reaches its maximum speed (which is
% an integer) or it stops.
%
% Consequently
%
% v(t+Dt) = v(t) + k(t),
%
% and Dt = 1/A.
%
% Now we look at the position of the car s(t)
%
% s(t+Dt) = s(t) + v(t) * Dt + 1/2 * a(t) * Dt^2
% = s(t) + v(t) / A + 1/2 * k(t) * A / A^2
% = s(t) + v(t) / A + k(t) / 2A.
%
% If we multiply the scale of s by A
%
% s'(t+Dt) = s'(t) + v(t) + k(t)/2
%
% which can be rewritten as
% s'(t+Dt) = s'(0) + sum_{0<=i<=t} (v(i) + k(i)/2)
% = s'(0) + sum_{0<=i<=t} v(i) + sum_{0<=i<=t} k(i)/2
% = s'(0) + sum_{0<=i<=t} v(i) + v(t+Dt)/2
%
%
% let s" be defined as
%
% s"(t+Dt) = s"(t) + v(t)
%
% and
%
% s'(t+Dt) = s"(t+Dt) + v(t+Dt)/2
%
% s' is a function of s" and v, so the state can be represented by s" and v,
%
% the advantage of using s" is that s" is an integer. s"=s' when v=0,
% consequently the initial and final state are the same for both s" and s'.
% IMPLEMENTATION
const ms = 4.
const t = 4.
const l = 10.
const a = 3.
const nDt = t * a.
const rL = l * a.
valueK(-1..1).
time(0..nDt).
speed(0..ms).
pos(0..rL).
% +------------ position s" of car (in new scale)
% | +---------- speed of car
% | | +-------- time (in new scale)
% v v v
% state(S,V,T)
%%%%%%%%%%%%%%%%%%%%%%%%%%%
% initial state condition
state(0,0,0).
%%%%%%%%%%%%%%%%%%%%%%%%%%%
% one action done at time T
1 {act(K,T): valueK(K)} 1 :- time(T) , T != nDt.
%%%%%%%%%%%%%%%%%%%%%%%%%%%
% transitions
state(S,V,T) :- state(S1,V1,T-1), act(K,T-1),
pos(S), speed(V), time(T), pos(S1), speed(V1), valueK(K),
S = S1 + V1, V = V1 + K.
%%%%%%%%%%%%%%%%%%%%%%%%%%%
% goal condition
:- not state(rL,0,nDt).
hide.
show act(K,T).
********************************************
*** REPRESENTATION 2, in the language of ccalc
*** By Joohyung Lee (appsmurf@cs.utexas.edu)
********************************************
%%%%%%%%%%%%%%%
% rational.pl
%%%%%%%%%%%%%%%
goodNum(N) :- 0 =< N, N =< 23.
goodDen(D) :- 1 =< D, D =< 6.
rn(N,D) :- gcd(N,D) =:= 1, N =< D*10.
fracSum(N,D,N1,D1,N2,D2) :-
rn(N1,D1), rn(N2,D2),
X is D1*D2, Y is N1*D2, Z is D1*N2,
V is Y+Z, W is gcd(V,X),
N is V//W, D is X//W,
goodNum(N), goodDen(D).
fracDiff(N,D,N1,D1,N2,D2) :-
rn(N1,D1), rn(N2,D2),
X is D1*D2, Y is N1*D2, Z is D1*N2,
V is Y-Z, W is gcd(V,X),
N is V//W, D is X//W,
goodNum(N), goodDen(D).
fracProd(N,D,N1,D1,N2,D2) :-
rn(N1,D1), rn(N2,D2),
X is N1*N2, Y is D1*D2, Z is gcd(X,Y),
N is X//Z, D is Y//Z,
goodNum(N), goodDen(D).
gt(N,D,N1,D1) :-
N*D1 > N1*D.
%%%%%%%%%%%%%%%
% continuous.t
%%%%%%%%%%%%%%%
:- tests rn/2; fracSum/6; fracDiff/6; fracProd/6; gt/4.
:- macros
maxInt -> 23;
maxDen -> 6;
maxSpeed -> 4;
acceleration -> 3.
:- compile('rational-0618.pl').
:- sorts
signAccel;
integer;
divisor.
:- variables
S :: signAccel;
Ns,Nt,Nd,
N,N1 :: integer;
Ds,Dt,Dd,
D,D1 :: divisor;
X,X1,X2,X3,X4,
Y,Y1,Y2,Y3,Y4 :: computed.
:- constants
plus,zero,minus :: signAccel;
0..maxInt :: integer; % range of numerator
1..maxDen :: divisor; % range of denominator
totalTime(integer,divisor) :: fluent;
totalTime1(integer) :: fluent;
totalTime2(divisor) :: fluent;
distance(integer,divisor) :: fluent;
distance1(integer) :: fluent;
distance2(divisor) :: fluent;
speed(integer,divisor) :: fluent;
speed1(integer) :: fluent;
speed2(divisor) :: fluent;
accelerate(signAccel) :: action;
duration1(signAccel,integer) :: attribute(accelerate);
duration2(signAccel,divisor) :: attribute(accelerate);
duration(signAccel,integer,divisor) :: attribute(accelerate).
noconcurrency.
% no waiting
caused false after /\V_A: -o(V_A).
% uniqueness & existence rules
% auxiliary predicates to generate fewer grounded rules
always (\/N: \/D: speed(N,D)).
speed1(N) defined as (\/D: speed(N,D)).
speed2(D) defined as (\/N: speed(N,D)).
caused -speed(N1,D1) if speed1(N) && -(N=N1).
caused -speed(N1,D1) if speed2(D) && -(D=D1).
always (\/N: \/D: distance(N,D)).
distance1(N) defined as (\/D: distance(N,D)).
distance2(D) defined as (\/N: distance(N,D)).
caused -distance(N1,D1) if distance1(N) && -(N=N1).
caused -distance(N1,D1) if distance2(D) && -(D=D1).
always (\/N: \/D: totalTime(N,D)).
totalTime1(N) defined as (\/D: totalTime(N,D)).
totalTime2(D) defined as (\/N: totalTime(N,D)).
caused -totalTime(N1,D1) if totalTime1(N) && -(N=N1).
caused -totalTime(N1,D1) if totalTime2(D) && -(D=D1).
always (\/N: \/D: duration(S,N,D)).
duration1(S,N) defined as (\/D: duration(S,N,D)).
duration2(S,D) defined as (\/N: duration(S,N,D)).
caused -duration(S,N1,D1) if duration1(S,N) && -(N=N1).
caused -duration(S,N1,D1) if duration2(S,D) && -(D=D1).
% maximum speed constraint
never speed(N,D) && gt(N,D,maxSpeed,1).
%%%%%% new speed
% if acceleration > 0, v = v0 + at
caused speed(X1,Y1)
after speed(Ns,Ds) && o(accelerate(plus)) && duration(plus,Nt,Dt)
&& fracProd(X,Y,3,1,Nt,Dt) && fracSum(X1,Y1,Ns,Ds,X,Y).
% if acceleration = 0, v = v0
caused speed(N,D)
after speed(N,D) && o(accelerate(zero)).
% if acceleration > 0, v = v0 - at
caused speed(X1,Y1)
after speed(Ns,Ds) && o(accelerate(minus)) && duration(minus,Nt,Dt)
&& fracProd(X,Y,3,1,Nt,Dt) && fracDiff(X1,Y1,Ns,Ds,X,Y).
%%%%%%% new distance
% if acceleration > 0, d = d0 + v0*t + 1/2 a*t^2
caused distance(X3,Y3)
after distance(Nd,Dd) && speed(Ns,Ds)
&& o(accelerate(plus)) && duration(plus,Nt,Dt)
&& fracProd(X,Y,3,2,Nt,Dt)
&& fracSum(X1,Y1,Ns,Ds,X,Y) % v0 + 1/2a*t
&& fracProd(X2,Y2,X1,Y1,Nt,Dt) % v0*t + 1/2a*t^2
&& fracSum(X3,Y3,Nd,Dd,X2,Y2).
% if acceleration = 0, d = d0 + v0*t
caused distance(X1,Y1)
after distance(Nd,Dd) && speed(Ns,Ds)
&& o(accelerate(zero)) && duration(zero,Nt,Dt)
&& fracProd(X,Y,Ns,Ds,Nt,Dt) % v0t
&& fracSum(X1,Y1,Nd,Dd,X,Y). % d0+v0t
% if acceleration < 0, d = d0 + v0*t - 1/2 a*t^2
caused distance(X3,Y3)
after distance(Nd,Dd) && speed(Ns,Ds)
&& o(accelerate(minus)) && duration(minus,Nt,Dt)
&& fracProd(X,Y,3,2,Nt,Dt)
&& fracDiff(X1,Y1,Ns,Ds,X,Y) % v0 - 1/2a*t
&& fracProd(X2,Y2,X1,Y1,Nt,Dt) % v0*t - 1/2a*t^2
&& fracSum(X3,Y3,Nd,Dd,X2,Y2).
%%%%%% totaltime = totaltime0 + duration(signAccel)
caused totalTime(X,Y)
after totalTime(N,D) && o(accelerate(S))
&& duration(S,N1,D1) && fracSum(X,Y,N,D,N1,D1).
:- show distance(N,D); speed(N,D); totalTime(N,D).
:- plan
time :: 4;
facts ::
0: speed(0,1),
0: distance(0,1),
0: totalTime(0,1),
4: speed(0,1),
4: distance(10,1),
4: totalTime(4,1).
***************************************************
*** REPRESENTATON 3, in the language of smodels
*** By Ricardo Morales (morales@redwood.cs.ttu.edu)
***************************************************
% To obtain integer values of speed (S) and distance traveled (D) we
% consider actions accelerate and brake to be of duration 2 units of time.
% Action release has duration 1 unit of time.
% We use "Resolution" to devide the interval [0..time] into
% time*resolution intervals. Each of this intervals is then considered a
% unit of time.
% Other constants are also scaled appropiently by the resolution
% Whit this aproach SMODELS can compute an "integral" plan. A plan whose
% action take place at integer time units.
% There are no plans of this type when resolution=2.
% Plans are found when resolution=3.
% At higher resolution, LPARSE may fail.
% Constant Declaration
const time = 4.
const mspeed = 4.
const lenght = 10.
% resolution
const resolution = 3.
% The following constants scale the coordinate system using the resolution
const time_limit = time * resolution.
const speed_limit = mspeed * resolution.
const temp = resolution * resolution.
const lenght_area = lenght * temp.
const intmax = time_limit * speed_limit.
% Time_range, speed_range and area_range define the values that the
% time, speed, and distance can take.
time_range(0..time_limit).
speed_range(0..speed_limit).
area_range(0..lenght_area).
% actions
action(accel). % accelerate for 2 units of time.
action(release). % release acceleraton for 1 unit of time.
action(brake). % brake for 2 units of time.
% holds(T,S,D) is true iff the car, at time T, has speed S and has
% travelled distance D.
% Initial Situation.
holds(0,0,0).
% action selection.
1{ occurs(T,A) : action(A) }1 :- holds(T,S,D),
time_range(T),
speed_range(S),
area_range(D).
% The effect of acceleration
holds(T+2, S+6, D+(S*2)+6) :- occurs(T,accel),
holds(T,S,D),
time_range(T),
speed_range(S),
area_range(D).
%The effect of release
holds(T+1, S, D+S) :- occurs(T,release),
holds(T,S,D),
time_range(T),
speed_range(S),
area_range(D).
%The effect of breaking
holds(T+2, S-6, D+(S*2)-6) :- occurs(T,brake),
holds(T,S,D),
time_range(T),
speed_range(S),
area_range(D).
% GOAL
% goal is true iff the car at time time_limit is stationary and has traveled
% distance lenght area.
goal :- holds(time_limit,0,lenght_area).
:- not goal.
% FORMAT...
hide action(X).
hide area_range(X).
hide time_range(X).
hide speed_range(X).
hide holds(T,S,D).
*****************************************************
*** REPRESENTATON 4, in the language of smodels
*** By Monica Nogueira (nogueira@redwood.cs.ttu.edu)
*** and Veena Mellarkod (mellarko@redwood.cs.ttu.edu)
*****************************************************
% This solution consists of a simple transformation that
% maps rational numbers into integers, in order to allow
% for a small ground program and fast computation. The
% result is then converted back to rational numbers and
% displayed.
%
% Our first idea was to write a library of arithmetic and
% logic functions for manipulating fractions. This would
% be a general solution to the problem of representing
% rational numbers and therefore enough for solving the
% continuous time problem. The implementation of this
% idea was straightforward and coding was easily done.
% But our experiments seemed to show that neither Smodels',
% nor DLV's, grounding modules can efficiently handle the
% size of the programs that this approach yields.
% So, we decided to eliminate fractions by transforming
% them into integers. This is achieved as follows:
%
% 1. We express each physical measure (distance, speed, time)
% as a rational number with a fixed denominator. More
% precisely
%
% Let gran be an arbitrary positive integer, a be the
% acceleration, ms be the car maximum speed, ltime the
% maximum time available, and l the length of the road.
%
% We will represent physical time by points
% 0, 1/(a*gran), 2/(a*gran), ..., (ltime*a*gran)/(a*gran)
% The corresponding speeds will range over
% 0, 1/gran, 2/gran, ...,(ms*gran)/gran
% and distances will range over
% 0, 1/(2*a*gran^2), 2/(2*a*gran^2), ...,(l*2*a*gran^2)/(2*a*gran^2)
%
% 2. We introduce three variables, Xn, Vn, Tn, ranging
% over integers, and define an "integer state" of a car
% to be state(Xn,Vn,Tn).
% The physical state of a car can be obtained from its integer
% state by dividing Xn, Vn, Tn by a*gran, gran, 2*a*gran^2,
% respectively.
%
% 3. We represent three actions:
% 3.1 accelerate car for 1/(a*gran) of a second
% 3.2 brake car for 1/(a*gran) of a second
% 3.3 do_nothing for 1/(a*gran) of a second.
%
% The meaning of the first two actions is straightforward,
% while do_nothing indicates that the car travels with
% constant speed for 1/(a*gran) of a second. (We can view
% this action as releasing the brake or accelerator
% and moving by inertia. Probably adopting "release"
% instead of do_nothing would be better.)
%
% Given an integer state X0n, V0n, T0n, and action
% accelerate for 1/(a*gran) of a second, the resulting integer
% state Xn, Vn, Tn can be computed by the following formulae:
% a. If V0n < ms*gran
% Xn = X0n + 2*V0n + 1
% Vn = V0n + 1
% Tn = T0n + 1
% b. Otherwise,
% Xn = X0n + 2*ms*gran
% Vn = ms*gran
% Tn = T0n + 1
%
% Similarly, when braking for 1/(a*gran) of a second,
% a. If V0n > 0
% Xn = X0n + 2*V0n - 1
% Vn = V0n - 1
% Tn = T0n + 1
% b. Otherwise,
% Xn = X0
% Vn = 0
% Tn = T0n + 1
%
% For action do_nothing, the formulae are
% Xn = X0n + 2*V0n
% Vn = V0n
% Tn = T0n + 1
%
% Relation o(A,Tn) says that action A occurs at time Tn/(a*gran),
% and we generate the occurrence of an action for each integer
% in interval [0..ltime*a*gran-1].
%
% Hence, if plan contains atoms o(A,T0), o(A,T1),..., o(A,Tm),
% we say that action A occurs for (Tm-T0+1)/(a*gran) of a second.
%
% Given a problem instance, we start with gran=1. If no
% solution exists for gran=1, then increase to gran=2 and
% try again, and so forth.
%
% Fine granularity requires more time but may give us
% better solutions.
%
%----------------------------------------------------------
const gran = 2. % solution granularity
const l = 10. % road length
const a = 3. % acceleration
const r = -3. % deacceleration
const ms = 4. % car max speed
const ltime = 4. % total time available
const vden = gran. % speed denominator
const tden = a*vden. % time denominator
const xden = vden*(2*tden). % distance denominator
const mtime = ltime*tden. % total time after transformation
const mspd = ms*vden. % car max speed after transf.
const mdist = l*xden. % road length after transf.
time(0..mtime).
spd(0..mspd).
dist(0..mdist).
% Fluents
% state(X,V,T) iff car is at position X/xden, with speed V/vden
% at time T/tden.
% Actions
% action(A) - action A is performed for 1/(a*gran) of a second.
action(accelerate).
action(brake).
action(do_nothing).
% Initial Situation
state(0,0,0).
% Goal Situation
goal :- state(mdist,0,mtime).
:- not goal.
% Generate a plan
1{o(A,T) : action(A)}1 :-
time(T),
lt(T,mtime).
% Effects of actions
% Accelerate
% A1 - Accelerating while car has not reached maximum speed.
state(Xn,Vn,T) :-
next(T0,T), dist(X0n), spd(V0n),
state(X0n,V0n,T0),
lt(V0n,mspd),
o(accelerate,T0),
Xn = X0n+2*V0n+1,
Vn = V0n+1.
% A2 - Accelerating after car has reached maximum speed.
% Note: this rule will never be satisfied when
% constraint C3 is present in the program.
%state(Xn,mspd,T) :-
% next(T0,T), dist(X0n),
% state(X0n,mspd,T0),
% o(accelerate,T0),
% Xn = X0n+2*mspd.
% Brake
% B1 - Braking when the car's speed is not zero.
state(Xn,Vn,T) :-
next(T0,T), dist(X0n), spd(V0n),
state(X0n,V0n,T0),
gt(V0n,0),
o(brake,T0),
Xn = X0n+2*V0n-1,
Vn = V0n-1.
% B2 - Braking when car is at zero speed.
% Note: this rule will never be satisfied when
% constraint C4 is present in the program.
%state(X0n,0,T) :-
% next(T0,T), dist(X0n),
% state(X0n,0,T0),
% o(brake,T0).
% D1 - Do-nothing (speed is constant)
state(Xn,V0n,T) :-
next(T0,T), dist(X0n), spd(V0n),
state(X0n,V0n,T0),
o(do_nothing,T0),
Xn = X0n+2*V0n.
% Auxiliary Predicates
% next(T0,T) iff the next moment of time after T0 is T.
next(T0,T) :- time(T0), time(T),
T = T0+1.
% Executability conditions
% C1 - Release accelerator before braking.
:- next(T0,T), o(accelerate,T0), o(brake,T).
% C2 - Release brake before accelerating.
:- next(T0,T), o(brake,T0), o(accelerate,T).
% "Good driving" requirements
% C3 - Stop accelerating after car reaches maximum speed.
:- time(T), dist(X), state(X,mspd,T), o(accelerate,T).
% C4 - Do not brake after car stops.
:- time(T), dist(X), state(X,0,T), o(brake,T).
% C5 - Always release brake/accelerator at final destination.
:- not o(do_nothing,mtime-1).
% Note: if "good driving" requirements C3 and C4 are
% considered too restrictive, they can be
% substituted by rules A2 and B2 (commented out above).
%-----------------------------------------------------
% Display formatting - prints a "nicer" plan.
% Decreases efficiency. Preferably, use only if gran=1.
%
% Example: If car is accelerated for 1 sec. at T=0,
% then the plan would include
%
% * o(accelerate,0) o(accelerate,1) o(accelerate,2)
% when not using formatting predicates;
%
% * perform(1,accelerate,3,3) when using formatting.
%
% To include display formatting:
% 1. Uncomment lines for predicates perform/4, perf/4,
% other_act/3, below.
% 2. Comment line: show o(X,Y).
% 3. Uncomment line: perform(X,Y,W,Z).
%
%-------------------------------------------------------
% perform(S,A,T,tden) iff A is the plan's S-th action
% and is performed for T/tden of a second.
%perform(S,A,T,tden) :- time(S), time(T0), time(T1),
% action(A),
% perf(S,A,T0,T1),
% T=T1-T0+1.
% perf(S,A,T,Tn) iff A is the S-th action of the plan,
% and occurs at all moment of time
% of interval [T,Tn].
%perf(1,A,0,Tn) :- time(Tn),
% action(A),
% Tn1 = Tn+1,
% o(A,0),
% o(A,Tn),
% not o(A,Tn1),
% not other_act(A,0,Tn).
%perf(S,A,T2,T3) :- next(S0,S),
% time(T0), next(T1,T2), time(T3),
% action(A), action(A0), neq(A0,A),
% perf(S0,A0,T0,T1),
% ge(T3,T2),
% Tn3 = T3+1,
% o(A,T2),
% o(A,T3),
% not o(A,T1),
% not o(A,Tn3),
% not other_act(A,T2,T3).
% other_act(A,T0,Tn) iff some action different of A occurs
% inside (open) interval (T0,Tn).
%other_act(A,T0,Tn) :- time(T), time(T0), time(Tn),
% action(A), action(A1), neq(A,A1),
% gt(T,T0),
% lt(T,Tn),
% o(A1,T).
hide.
show o(X,Y).
%show perform(X,Y,W,Z).