Applications of Logic Programming to Planning: Discussion Date: Wed, 10 Feb 1999 From: Son Tran To: Esra Erdem It was interesting to read your paper. The examples and the results of your experiment are very interesting. Looking at the way you presented the example, I have the following question: (perhaps you did have the answer already) Do you have (or plan to have) a program which (automatic) translates domain descriptions in a high-level action description language, say A, B, or C, into programs which are suitable to pose to SMODELS, DLV, or CCALC. I believe that this would be an interesting program and very helpful for others researchers who want to test these systems. =============== Date: Tue, 16 Feb 1999 From: Son Tran To: Esra Erdem This message has two attachment files: 1. the gsm.pl file is the program for translating a B-domain into an input file for SMODELS. To run it, you need to 1. consult the program 2. run the query gen. 3. it will ask for the file name containing the domain you want to translate 4. and the output file name 2. the sp1.pl file is an example about encoding a B-domain description. Note that for the program to run, you have to have the clauses: fluent(..) ---- defining the fluents of the domain action(..) ---- defining the actions of the domain causes(A, F, List) ---- dynamic causal rule that stands for A causes F if List causes(F, List) ---- static causal rule that stands for F if List neg(F) ---- classical negation of F Please let me know if you experience any problems (and I anticipate there will be some!) ---------- X-Sun-Data-Type: default X-Sun-Data-Name: sp1.pl X-Sun-Content-Lines: 25 is_claps(l1). is_claps(l2). fluent(open). fluent(up(X)):- is_claps(X). action(toggle(X)):- is_claps(X). causes(toggle(X), neg(up(X)), [up(X)]):- is_claps(X). causes(toggle(X), up(X), [neg(up(X))]):- is_claps(X). causes(open, [up(l1), up(l2)]). initially(neg(open)). ---------- X-Sun-Data-Type: default X-Sun-Data-Name: gsm.pl X-Sun-Content-Lines: 275 :- use_module(library(files)). :- use_module(library(lineio)). :- use_module(library(strings)). %%% Collecting static causal laws %%% and translating them into rules suitable for SMODELS pr_static_causal(Id):- findall((X,Y), causes(X,Y), Z), nl(Id), write(Id, '%%% Section: static causal laws %%%%'), nl(Id), nl(Id), pr_static_causal(Z, Id). pr_static_causal([], Id):- nl(Id), write(Id, '%%% End section: static causal laws %%%%'), nl(Id). pr_static_causal([(L,C)|T], Id):- add_time(L, 'T', Id), write(Id, ' :- time(T), '), add_time_list(C, 'T', Id), write(Id, '.'), nl(Id), pr_static_causal(T, Id). %%% Collecting dynamic causal laws %%% and translating them into rules suitable for SMODELS pr_dynamic_causal(Id) :- findall((A,X,Y), causes(A,X,Y), Z), nl(Id), write(Id, '%%% Section: dynamic causal laws %%%%'), nl(Id), pr_dynamic_causal(Z, Id). pr_dynamic_causal([], Id):- nl(Id), write(Id, '%%% End section: dynamic causal laws %%%%'), nl(Id). pr_dynamic_causal([(A,L,C)|T], Id):- add_time(L, 'T1', Id), write(Id, ' :- '), write(Id, ' next(T,T1),'), add_time(A, 'T', Id), length(C,N), ( eq(N,0) -> write(Id, '.'), nl(Id) | write(Id, ','), add_time_list(C, 'T', Id), write(Id, '.'), nl(Id) ), pr_dynamic_causal(T, Id). %%% %%% Generating inertial rules for fluent literals %%% one rule per fluent literal %%% pr_inertial(Id):- findall(X, fluent(X), Y), nl(Id), write(Id, '%%% Section: inertial %%%%'), nl(Id), pr_inertial(Y, Id). pr_inertial([], Id):- nl(Id), write(Id, '%%% End section: inertial %%%%'), nl(Id). pr_inertial([H|T], Id):- pr_line(H, Id), nl(Id), pr_line(neg(H), Id), nl(Id), pr_inertial(T, Id). pr_line(H, Id):- fluent(H), add_time(H, 'T1', Id), write(Id, ' :- next(T,T1),'), add_time(H, 'T', Id), write(Id, ', not '), add_time(neg(H), 'T1', Id), write(Id, '.'). pr_line(neg(H), Id):- fluent(H), add_time(neg(H),'T1', Id), write(Id, ' :- next(T,T1),'), add_time(neg(H), 'T', Id), write(Id, ', not '), add_time(H, 'T1', Id), write(Id, '.'). %%% %%% Generating initial rules for fluent literals %%% one rule per fluent literal %%% pr_initial(Id) :- findall(X, fluent(X), Z), nl(Id), write(Id, '%%% Section: initial conditions are exogenous %%%%'), nl(Id), pr_initial(Z, Id). pr_initial([], Id):- nl(Id), write(Id, '%%% End section: initial conditions are exogenous %%%%'), nl(Id). pr_initial([L|T], Id):- pri_line(L, Id), nl(Id), pri_line(neg(L), Id),nl(Id), pr_initial(T, Id). pri_line(H, Id):- fluent(H), add_time(H, '0', Id), write(Id, ' :- not '), add_time(neg(H), '0', Id), write(Id, '.'). pri_line(neg(H), Id):- fluent(H), add_time(neg(H),'0', Id), write(Id, ' :- not '), add_time(H, '0', Id), write(Id, '.'). %%% %%% Generating rules for 'actions are exogenous' %%% two rules for one action %%% pr_ex_action(Id):- findall(A, action(A), Z), nl(Id), write(Id, '%%% Section: actions are exogenous %%%%'), nl(Id), pr_ex_action(Z, Id). pr_ex_action([], Id):- nl(Id), write(Id, '%%% End of section: actions are exogenous %%%%'), nl(Id). pr_ex_action([A|T], Id):- add_time(A, 'T', Id), write(Id, ' :- time(T), not '), add_time(neg(A), 'T', Id), write(Id, '.'), nl(Id), add_time(neg(A), 'T', Id), write(Id, ' :- time(T), not '), add_time(A, 'T', Id), write(Id, '.'), nl(Id), pr_ex_action(T, Id). %%% %%% Generating for section 'no actions are executed at last time %%% one per action %%% pr_no_action(Id):- findall(A, action(A), Z), nl(Id), write(Id, '%%% Section: no actions are executed at last time %%'), nl(Id), pr_no_action(Z, Id). pr_no_action([], Id):- nl(Id), write(Id, '%%% End of section: no actions are executed at last time %%%%'), nl(Id). pr_no_action([A|T], Id):- write(Id, ':- '), add_time(A, 'lasttime', Id), write(Id, '.'), nl(Id), pr_no_action(T, Id). % % Add the two auxiliary predicates % to the file % pr_auxiliary(Id):- write(Id, '%%% Auxiliary predicates '), nl(Id), nl(Id), write(Id, 'time(0..lasttime).'), nl(Id), write(Id, 'next(T,T1):- time(T), time(T1), T1 = T + 1.'), nl(Id). % % add_time(Term, Y, Id) % inserting one parameter to Term % the parameter indicates the time point % Y can be: now (T), next (T1), last (lasttime), zero (0) % add_time(Term, Y, Id):- Term =.. X, length(X,N), ( eq(N,1) -> write_first(X, Id), write(Id, '('), write(Id, Y), write(Id, ')') | write_time(X, Y, Id) ). write_first([X|_], Id):- write(Id, X). write_time([A|T], Y, Id):- ( eq(neg,A) -> write(Id, 'n'), add_time_list(T, Y, Id) | write(Id, A), write_arg(T, Y, Id) ). write_arg(T, Y, Id):- write(Id, '('), write_next(T, Y, Id). write_next([], Y, Id):- write(Id, Y), write(Id, ')'). write_next([H|T], Y, Id):- write(Id, H), write(Id, ','), write_next(T, Y, Id). add_time_list([], _, Id). add_time_list([H|T], Y, Id):- add_time(H, Y, Id), length(T,N), ( eq(N,0) -> write(Id, '') | write(Id, ',') ), add_time_list(T, Y, Id). eq(X,X). %%% %%% for quintus program %%% gen:- write(' Enter domain description file name: '), get_line(S), atom_chars(Source, S), %%% get the source file name consult(Source), write(' Enter the output file name: '), get_line(F), atom_chars(FileDescr, F), %%% get the file name write(' Generating .... '), open_file(FileDescr, write, X), pr_dynamic_causal(X), pr_static_causal(X), pr_inertial(X), pr_initial(X), pr_ex_action(X), pr_no_action(X), pr_auxiliary(X), close(X). ============ Date: Thu, 30 Sep 1999 From: Esra Erdem and Vladimir Lifschitz To: TAG In order to compare the efficiency of search as performed by answer set solvers and propositional solvers, we have conducted some experiments using CCALC, DLV and SMODELS with blocks world problems represented as logic programs. The following chart summarizes the computation times (in seconds) that we observed using CCALC 1.22 with SATO, using SMODELS 2.23, and using DLV released on June 10, 1999 : Sussman P1 P2 P3 P4 grounding + completion (CCALC) 0.35 0.85 1.14 8.32 21.96 * model-finding (CCALC with SATO) 0.01 0.03 0.05 0.25 1.67 grounding (LPARSE) 0.13 0.24 0.47 1.84 4.77 * model-finding (SMODELS) 0.12 0.29 0.68 17.85 54.97 grounding + model-finding (DLV) 0.33 1.23 4.98 153.52 695.47 Two versions of the program for the Sussman example--the SMODELS input and the CCALC input--are shown below. For the descriptions of planning problems P1-P4, see http://www.cs.utexas.edu/users/esra/experiments/experiments.html The numbers in the two rows marked by stars confirm our conjecture that it is computationally advantageous to use propositional solvers instead of answer set solvers when this is possible. %%%%%%%%%%%%%%%%%%%%%%%%% File: bw_domain_m1 %%%%%%%%%%%%%%%%%%%%%%%%%% % blocks world domain presented to SMODELS % non(B,L,T) represents the classical negation of on(B,L,T), and similarly % for the other predicates with mysterious names beginning with n. % effect of moving a block on(B,L,T1) :- block(B), location(L), move(B,L,T), next(T,T1). % a block can be moved only when it's clear :- location(L), block(B), block(B1), time(T), move(B,L,T),on(B1,B,T). % any two blocks cannot be on the same block at the same time :- block(B), block(B1), block(B2), time(T), not eq0(B1,B2), on(B1,B,T), on(B2,B,T). % wherever a block is, it's not anywhere else non(B,L1,T) :- time(T), location(L1), location(L), block(B), on(B,L,T), not eq0(L,L1). % every block is supported by the table supported(B,T) :- block(B), time(T), on(B,table,T). supported(B,T) :- block(B), block(B1), time(T), on(B,B1,T), supported(B1,T), not eq0(B,B1). :- block(B), time(T), not supported(B,T). % no actions are executed at last time :- block(B), location(L), move(B,L,lasttime). % no concurrency move1(B,T) :- location(L), block(B), time(T), move(B,L,T). :- time(T), block(B1), block(B2), move1(B1,T), move1(B2,T), not eq0(B1,B2). % inertia on(B,L,T1) :- location(L), block(B), on(B,L,T), not non(B,L,T1), next(T,T1). % initial values and actions are exogeneous on(B,L,0) :- block(B), location(L), not non(B,L,0). non(B,L,0) :- block(B), location(L), not on(B,L,0). move(B,L,T) :- block(B), location(L), time(T), not nmove(B,L,T). nmove(B,L,T) :- block(B), location(L), time(T), not move(B,L,T). % consistency :- block(B), location(L), time(T), on(B,L,T), non(B,L,T). :- block(B), location(L), time(T), move(B,L,T), nmove(B,L,T). % auxiliary predicates time(0..lasttime). next(T,T1) :- time(T), time(T1), T1 = T + 1. location(L) :- block(L). location(table). eq0(L,L) :- location(L). %%%%%%%%%%%%%%%%%%%%%%%%% File: bw_sussman %%%%%%%%%%%%%%%%%%%%%%%%%% % Sussman Anomaly presented to SMODELS: block(b0). block(b1). block(b2). % initial conditions and goal compute 1 { on(b1, table,0), on(b2, b0,0), on(b0, table, 0), on(b1, b0,lasttime), on(b2, b1, lasttime),on(b0,table,lasttime)} %%%%%%%%%%%%%%%%%%%%%%%%% File: bw_domain_m1.b %%%%%%%%%%%%%%%%%%%%%%%%%% % blocks world domain presented to CCALC :- macros next(#1,#2) -> (#1) < maxtime, (#2) is (#1) + 1. :- op(600,fx,not). :- macros not (#1) -> -(#1). :- sorts location >> block; time0. :- variables B, B1, B2 :: block; L, L1 :: location; T :: time0. % since time is a reserved word in CCALC 1.22 % we used time0 :- computed T1. :- constants table :: location; 0..maxtime :: time0; on(block, location, time0), supported(block, time0), move1(block, time0), move(block, location, time0) :: atomicFormula. :- show none. % effect of moving a block on(B,L,T1) <- move(B,L,T), next(T,T1). % a block can be moved only when it's clear <- move(B,L,T), on(B1,B,T). % any two blocks cannot be on the same block at the same time. <- on(B2,B,T), on(B1,B,T), -(B1=B2). % wherever a block is, it's not anywhere else -on(B,L1,T) <- on(B,L,T), -(L=L1). % every block is supported by the table supported(B,T) <- on(B,table,T). supported(B,T) <- on(B,B1,T), supported(B1,T), -(B=B1). <- not supported(B,T). % no actions are executed at last time <- move(B,L,maxtime). % no concurrency move1(B,T) <- move(B,L,T). <- move1(B1,T), move1(B2,T), -(B2=B1). -move1(B,T) <- not move1(B,T). % inertia on(B,L,T1) <- on(B,L,T), next(T,T1), not -on(B,L,T1). % initial values and actions are exogenous on(B,L,0) <- not -on(B,L,0). -on(B,L,0) <- not on(B,L,0). move(B,L,T) <- not -move(B,L,T). -move(B,L,T) <- not move(B,L,T). %%%%%%%%%%%%%%%%%%%%%%%%% File: bw_sussman_m1.b %%%%%%%%%%%%%%%%%%%%%%%%%%%%% % File: bw_sussman_m1.b % Blocks world problem: sussman anomaly presented to CCALC % the initial state % 2 % 0 1 % ------ % the goal state % 2 % 1 % 0 % --- :- macros maxtime -> 3. :- include 'bw_domain_m1.b'. :- constants b0, b1, b2 :: block. <- not on(b1,table,0). <- not on(b2,b0,0). <- not on(b0,table,0). <- not on(b0,table,maxtime). <- not on(b1,b0,maxtime). <- not on(b2,b1,maxtime). =============== Date: Tue, 23 Nov 1999 From: Yuliya Babovich To: TAG In Version 2 of Smodels there are two convenient new features: choice rules and constraint rules. I used these features to simplify the planning program for the blocks world from a paper by Niemelae, and it turned out that the modified program is not only simpler, it also leads to fewer ground rules and runs faster. Here is a table that shows the running times and the numbers of ground rules for both programs. (Niemelae's original program and the test cases mentioned below are available at http://www.tcs.hut.fi/ini/lp-csp-long.ps.gz .) Original program Modified program bw-large.c 7 time 15.18 4.12 ground rules 72527 15167 bw-large.c 8 time 36.16 10.26 ground rules 81681 17151 bw-large.d 8 time 26.60 6.15 ground rules 115109 21779 bw-large.d 9 time 67.95 17.58 ground rules 127999 24299 bw-large.e 9 time 40.24 8.46 ground rules 191621 30079 bw-large.e 10 time 109.82 25.87 ground rules 127999 33199 Description of the changes made: In Niemelae's program, the action of moving X to Y at time T is expressed by moveop(X,Y,T). His program uses also the auxiliary predicate blocked_move, which is essentially the classical negation of moveop. Our modifications eliminated this predicate altogether. 1. The choice rule 0{moveop(X,Y,T)}:- time(T), block(X), object(Y), X != Y, on_something(X,T), available(Y,T), not covered(X,T), not covered(Y,T), not goal(T). replaced the following three rules from the original program: % operator preconditions moveop(X,Y,T):- time(T), block(X), object(Y), X != Y, on_something(X,T), available(Y,T), not covered(X,T), not covered(Y,T), not blocked_move(X,Y,T). % Stop applying operators when the goal has been reached blocked_move(X,Y,T):- block(X), object(Y), time(T), goal(T). % moveop(X,Y,T) is blocked if its not chosed (not moveop(X,Y,T) holds) blocked_move(X,Y,T) :- time(T), block(X), object(Y), not moveop(X,Y,T). 2. The constraint rule :-2{moveop(X,Y,T):object(Y)}, block(X),time(T). replaced the rule % An object can be moved by one move operation at a time blocked_move(X,Y,T) :- block(X), object(Y), object(Z), time(T), moveop(X,Z,T), Y != Z. 3. The rule :- moveop(X,Y,T),block(X), object(Y), time(T), moving(Y,T). replaced the rule % An object cannot be moved on top of an object that is moved blocked_move(X,Y,T) :- block(X), object(Y), time(T), moving(Y,T). 4. Constraint rule :-2{moveop(X,Y,T):block(X)}, block(Y),time(T). replaced the rule % Two objects cannot be moved on top of the same object by % one move operation at a time blocked_move(X,Y,T) :- block(X), block(Y), block(Z), time(T), moveop(Z,Y,T), X != Z. =============== Date: Sun, 12 Dec 1999 From: Yuliya Babovich To: TAG Monica Nogueira pointed out to me that some numbers in the table of run times that I sent you on November 23 were incorrect. Here is the corrected table: Original Modified program bw-large.c 7 time 15.18 4.12 ground rules 72527 15167 bw-large.c 8 time 36.16 10.26 ground rules 81681 17151 bw-large.d 8 time 26.60 6.15 ground rules 115109 21779 bw-large.d 9 time 67.95 17.58 ground rules 127999 24299 bw-large.e 9 time 40.24 8.46 ground rules 174099 30079 bw-large.e 10 time 109.82 25.87 ground rules 191621 33199 =============== Date: Fri, 7 Jul 2000 From: Joohyung Lee To: TAG While experimenting with a formalization of Blocks World domain, we found a result we would like to share. It is usual in satisfiability planning and in answer set planning to make the process of plan generation more efficient by allowing concurrent actions as long as their effects are not in conflict. Such a plan can be easily turned into a sequential plan: any actions that are scheduled to be executed in the same step can be instead executed consecutively, in any order. You may have seen such examples of Blocks World planning in "Logic programs with stable model semantics as a constraint programming paradigm" by Ilkka Niemela. According to that paper, the minimal number of steps needed to solve benchmark problem bw-large.c (with 15 blocks) is 8. This number is much smaller than the length of the corresponding sequential plan (that is, the total number of actions). This is why allowing concurrency is a useful computational trick. What we found is that there is a tradeoff between the number of steps and the total number of actions in the plan. For problem bw-large.c, the relationship between the number of steps and the smallest possible number of actions is summarized in the following table. Number of Smallest possible steps number of actions ------------------------------- 8 18 9 16 10 15 This observation shows that limiting the number of steps may prevent us from finding efficient sequential plans. Incidentally, the number of actions in the 8-step plan generated by smodels in Niemela's work is 29, a lot more than necessary. =============== Date: Sun, 9 Jul 2000 From: Paolo Ferraris To: Joohyung Lee The existence of this tradeoff for this problem does not surpise me so much. In fact we can have it even with simpler problems. Consider this problem: We have four blocks a b c and d. This is the initial state a b c d ------- Our goal is to exchange blocks a and b, then to have the following goal position for the blocks. b a c d ------- We have plans of lenght two steps with at minimum four actions (moving both a and b on the table and then back on the stacks in the goal position), or of lenght three with three actions (for example putting block a on the table, moving b on c and then a on d).