The Shuttle Domain: Discussion Date: Tue, 15 Dec 1998 From: Vladimir Lifschitz To: Richard Watson Several TAG members met yesterday in Austin to talk about your paper. Among other things, we discussed the feasibility of planning in the domain that you described. We have two questions in connection with this. 1. How large approximately is the domain description represented by your logic program? In other words, consider the set of all ground atoms beginning with 'causes', 'impossible' and 'definition' that are entailed by your program. How large would it be, in your opinion -- 10^4, or 10^5, or more than that? My impression is that the largest part of the domain desciption would come from the definition of open_path(X,Y). Is this right? The size of this definition is the number of triples that satisfy valve_path(X,Y,Z). What is the order of magnitude of this number? 2. In Section 4.4 you write that approximately 20 actions might be needed to ready the shuttle for a maneuver. Does the order of actions matter in a plan like this? If we are allowed to perform actions concurrently, how many time intervals will we need? Theoretically speaking, can all 20 actions be performed at the same time, or do we need to perform some of them first to ensure preconditions for the others? =================== Date: Thu, 17 Dec 98 From: Richard Watson To: Vladimir Lifschitz Here are my answers to your questions. Question: > 1. How large approximately is the domain description represented > by your logic program? In other words, consider the set of all ground > atoms beginning with 'causes', 'impossible' and 'definition' that are > entailed by your program. How large would it be, in your opinion -- > 10^4, or 10^5, or more than that? > My impression is that the largest part of the domain description would > come from the definition of open_path(X,Y). Is this right? The size of > this definition is the number of triples that satisfy valve_path(X,Y,Z). > What is the order of magnitude of this number? Answer: Before grounding, there are 2 Dynamic Causal Laws, 1 Impossibility Proposition, 3 Static Causal Laws, and 36 Definition Propositions (some of which are already ground). Let us count the number of ground instances of each type of proposition in the language. First, it is important to note that we may not need all possible groundings of all the propositions. For example, the fluent `open_path(X,Y)' is not meant to be a fluent we ask queries about, it is meant to be an auxiliary predicate, therefore we don't necessarily need all possible grounding, just the ones relevant to other rules. For open_path, this cuts the number of groundings from ~1300 to ~100. Now on to the number of ground propositions. Dynamic Causal Laws - 200 now but may expand to 450 if we improve the model by adding the third possible switch position. Impossibility Propositions - 100 now but again may expand to 150 Static Causal Laws - 138 Definition Propositions - ~845 if we only consider "important" open_path and path_to_leak propositions, ~3300 otherwise. Total - ~1300 without some irrelevant grounding. ~3650 with all groundings. Question: > 2. In Section 4.4 you write that approximately 20 actions might be > needed to ready the shuttle for a maneuver. Does the order of actions > matter in a plan like this? If we are allowed to perform actions > concurrently, how many time intervals will we need? Theoretically > speaking, can all 20 actions be performed at the same time, or do we > need to perform some of them first to ensure preconditions for the > others? As far as order is concerned, the answer is yes and no. That is, while I believe there is a prefered (safer) order for opening valve, etc, in this case it seems that any plan that achieves the goal can be reordered into this prefered order without invalidating the resulting plan. The same seems to be true with concurrency. It seems that, for this domain, you could create a plan with only one large concurrent action to achieve the plan and that any linear, non-concurrent ordering of the actions, including the aforementioned preferred one, would also be a valid plan. =================== Date: Mon, 21 Dec 1998 From: Vladimir Lifschitz To: Richard Watson Your comments about the size of the domain description from your paper and about the possibility of executing, in principle, all actions concurrently, make me believe that planning problems for your domain can be solved very quickly, within minutes if not seconds. The following suggestions are based on the discussion of your paper that we had here in Austin a week ago. One of several things that our "causal calculator" ("ccalc") can do is planning in domains described in an action language with both dynamic and static laws. The experiments with ccalc that we conducted so far differ from what is required in your case in two ways. First, ccalc understands Action Language C, but not B that you are using (see [2.7] in the TAG bibliography). My impression is that this difference is not very essential in this case--your dynamic and static laws are understood in both languages in the same way. (As an aside, I'd like to note that C has two advantages that may be relevant. It is capable of expressing the closed world assumption, which is related to the semantics of "definitions" in your dialect of B. And it is capable of expressing concurrency, which is important for fast planning.) Second, ccalc generates large domain descriptions by grounding relatively small "schematic descriptions" whose schematic variables range over finite domains. Your method for generating a domain description is more sophisticated--it uses a Prolog program. What we'll need is using Prolog's findall to generate the input for ccalc. We have never tried this, but it doesn't strike me as something very difficult. It seems to me that planning with less than 4000 causal laws after grounding and with a plan of length 1 (all actions are performed concurrently) is peanuts in comparison with the blocks world experiments that Norm McCain and Hudson Turner have conducted. (Information about those experiments is included in their KR-98 paper, accessible through their web pages--see the TAG membership list). =================== Date: Mon, 18 Jan 1999 From: Norm McCain To: Vladimir Lifschitz We can do planning in the shuttle domain. We don't get minimal plans of course. I have had to make various assumptions about the sorts of variables that were not properly restricted in the domain description. I am not sure that these assumptions are right. I hope that Richard will examine the input file when he returns from PADL'99. I don't understand the domain in detail, but I've checked in a few cases that the plans produced work in queries -- using their query answering program and my modified domain description. I've extended ccalc to handle causal theories specified by Prolog programs, and I've written a translator from the language L_0 into causal theories. The ground theory with maxtime 1 is generated with these statistics. % 5302 atoms, 13798 rules, 37378 clauses (4748 new atoms), 21760 msec. Planning takes about .3 seconds typically, using rel_sat. The input file is in '/u/mccain/tag/shuttle/myrcs.pl'. Here's an example. | ?- compile(myrcs). {compiling /v/hank/v38/mccain/tag/shuttle/myrcs.pl...} {Warning: [V] - singleton variables in valve_path/4 in lines 527-551} {Warning: [V] - singleton variables in valve_path/4 in lines 551-553} {Warning: [G] - singleton variables in non_fluent/1 in lines 909-910} {Warning: [A] - singleton variables in impossible/1 in lines 1430-1435} {/v/hank/v38/mccain/tag/shuttle/myrcs.pl compiled, 2090 msec 167464 bytes} yes | ?- translate. % 5302 atoms, 13798 rules, 37378 clauses (4748 new atoms), 22980 msec. yes | ?- plan. enter facts (then ctrl-d) |: enter goal |: h(ready_for_maneuver(plus_pitch),1). calling rel_sat... 0. position(f1dr,off) position(f2dr,off) ... ACTIONS: flip(f1dr,on) flip(f2dr,on) flip(f4dr,on) flip(l2r2d,on) flip(l3r3d,on) flip(l4r4d,on) flip(vd,on) flip(f1lo,on) flip(f2lo,on) flip(l2r2l,on) flip(l4r4l,on) flip(fha,open) flip(fi12,open) flip(fm1,open) flip(fm2,open) flip(fm3,open) flip(fm4,open) flip(fm5,open) flip(lha,open) flip(li12,open) flip(li345a,open) flip(li345b,open) flip(lm4,open) flip(lx12,open) flip(rhb,open) flip(ri345a,open) flip(ri345b,open) flip(rm2,open) flip(rx12,open) flip(rx345,open) 1. position(f1dr,on) position(f2dr,on) ... Elapsed Time (cpu sec): 0.52 Verify plan? (y/n) y verifying. The plan is verified! yes | ?- q(ready_for_maneuver(plus_pitch),[ flip(f1dr,on),flip(f2dr,on),flip(f4dr,on),flip(l2r2d,on), flip(l3r3d,on),flip(l4r4d,on),flip(vd,on),flip(f1lo,on),flip(f2lo,on), flip(l2r2l,on),flip(l4r4l,on),flip(fha,open),flip(fi12,open), flip(fm1,open),flip(fm2,open),flip(fm3,open),flip(fm4,open), flip(fm5,open),flip(lha,open),flip(li12,open),flip(li345a,open), flip(li345b,open),flip(lm4,open),flip(lx12,open),flip(rhb,open), flip(ri345a,open),flip(ri345b,open),flip(rm2,open),flip(rx12,open), flip(rx345,open)]). yes | ?- q/2 is their query/2. The query takes a lot longer than the planning.