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).