The Monkey and the Trainer: Discussion, Part 1 Date: Sat, 24 Apr 1999 From: Hudson Turner To: Vladimir Lifschitz I spent an hour adding a rather odd trainer to the monkey and banana domain -- this trainer can only walk after being prompted by the monkey! (Otherwise, he can "voluntarily" help the monkey grasp the banana -- the monkey need never scream. Or we may imagine he can interfere with the monkey's plan, by walking off with the monkey on his back, for instance. (What is planning with an opponent like -- esp. if the opponent can act concurrently?)) As it should I guess, the scenario raises questions... I chose easy answers first, without considering them carefully. =========================================================== Domain description is included as an attachment. Here are excerpts: (prompted is a defaultFalseFluent) scream causes prompted. caused false if at(monkey,L) && -at(trainer,L) after prompted. nonexecutable walk(trainer,L) if -prompted. climbTrainer causes onTrainer. nonexecutable climbTrainer if onTrainer. nonexecutable climbTrainer if onBox. nonexecutable climbTrainer if at(monkey,L) && -at(trainer,L). graspBanana causes hasBanana. nonexecutable graspBanana if -onBox && -onTrainer. nonexecutable graspBanana if at(monkey,L) && -at(banana,L). Here's a planning problem that seems to require a scream and climbTrainer: :- plan facts :: init -prompted, init at(monkey,l1), init at(banana,l2), init at(box,l3), init at(trainer,l4); goal :: last hasBanana, last at(box,l3). Here's a plan: | ?- loadf('monkey-trainer.c'). % loading file /home/vola/14/hudson/plan/ccalc/monkey-trainer.c % loading file /home/vola/14/hudson/plan/ccalc/C % loading file /home/vola/14/hudson/plan/ccalc/monkey-trainer.p % 216 atoms, 2392 rules, 2280 clauses, 3110 msec. yes | ?- plan(0). calling sato... 0. at(banana,l2) at(box,l3) at(monkey,l1) at(trainer,l4) ACTIONS: walk(monkey,l2) 1. at(banana,l2) at(box,l3) at(monkey,l2) at(trainer,l4) ACTIONS: scream 2. prompted at(banana,l2) at(box,l3) at(monkey,l2) at(trainer,l4) ACTIONS: walk(trainer,l2) 3. at(banana,l2) at(box,l3) at(monkey,l2) at(trainer,l2) ACTIONS: climbTrainer 4. onTrainer at(banana,l2) at(box,l3) at(monkey,l2) at(trainer,l2) ACTIONS: graspBanana 5. hasBanana onTrainer at(banana,l2) at(box,l3) at(monkey,l2) at(trainer,l2) run time (seconds) 0.03 Verify plan? (y/n) y verifying..... The plan is verified! yes | ?- ================================================================= :- macros maxtime -> 5. :- include 'C'; 'monkey-trainer.p'. :- sorts object >> agent; location. :- variables G :: agent; O :: object; L, L1 :: location; A, A1 :: action. :- constants monkey, trainer :: agent; box, banana :: object; l1, l2, l3, l4 :: location; at(object,location) :: inertialTrueFluent; onBox, hasBanana, onTrainer :: inertialFluent; prompted :: defaultFalseFluent; walk(agent,location), pushBox(location), climbBox, graspBanana, scream, climbTrainer :: action. nonexecutable A && A1 if -(A=A1). walk(G,L) causes at(G,L). nonexecutable walk(G,L) if at(G,L). nonexecutable walk(monkey,L) if onBox. nonexecutable walk(monkey,L) if onTrainer. pushBox(L) causes at(monkey,L). pushBox(L) causes at(box,L). nonexecutable pushBox(L) if at(monkey,L). nonexecutable pushBox(L) if onBox. nonexecutable pushBox(L) if onTrainer. nonexecutable pushBox(L) if at(monkey,L1) && -at(box,L1). climbBox causes onBox. nonexecutable climbBox if onBox. nonexecutable climbBox if onTrainer. nonexecutable climbBox if at(monkey,L) && -at(box,L). climbTrainer causes onTrainer. nonexecutable climbTrainer if onTrainer. nonexecutable climbTrainer if onBox. nonexecutable climbTrainer if at(monkey,L) && -at(trainer,L). scream causes prompted. caused false if at(monkey,L) && -at(trainer,L) after prompted. nonexecutable walk(trainer,L) if -prompted. graspBanana causes hasBanana. nonexecutable graspBanana if -onBox && -onTrainer. nonexecutable graspBanana if at(monkey,L) && -at(banana,L). caused -at(O,L1) if at(O,L) && -(L=L1). caused at(banana,L) if at(monkey,L) && hasBanana. always at(O,l1) ++ at(O,l2) ++ at(O,l3) ++ at(O,l4). always at(monkey,L) && onBox ->> at(box,L). caused at(monkey,L) if onTrainer && at(trainer,L). ============== Date: Fri, 30 Apr 1999 From: Vladimir Lifschitz To: Hudson Turner Your formalization is certainly a step in the right direction, although a trainer who never walks on his own accord is, indeed, an odd creature. About your question, "What is planning with an opponent like": The answer is, I think, that this is planning how to play a game! I never noticed before receiving your message that the plan fails if the trainer keeps walking after responding to the monkey's call, and consequently the success of the plan depends on the trainer's cooperation. We'll have to assume that the trainer is friendly and doesn't walk while the monkey is climbing up his back or is on his back. ============== Date: Mon, 17 May 99 From: UTEP KR Group To: TAG Here is a solution for the monkey with trainer problem, written in Language B with the addition of defaults. First it didn't include default statement: default(neg(prompted(trainer)), []). (see below) The main idea was to express the trigger, i.e. a statement of the form "if prompted then trainer must approach the monkey," by : impossible(B,[prompted(trainer),at(monkey,L)]) :- location(L), action(B), diff_actions(B,walk(trainer,L)) which says that any other action is impossible in a state in which prompted is true. (It is easy to modify this to allow concurrent actions by replacing "diff_actions(B,walk(trainer,L))" by "not member(walk(trainer,L), B)"). This worked fine, but we noticed that the trainer would stay prompted afterwards. To remedy this problem we introduced the default statement: default(neg(prompted(trainer)), []). (Note that the translation to Smodels defines prompted as non-inertial and generates rule: nprompted(trainer,T) :- time(T), not prompted(trainer,T). ) The semantics of B with defaults is easily defined (we can give a definition if someone is interested). We are sending the resulting domain description as an attachment: monkey.pl. This domain description is passed as input parameter to Son's translator program (tentatively called b2s.pl, suggestions for a name are welcome), which generates the two input files for Smodels: 1. the domain description file, (attachment: monkey_domain) and 2. the problem file including the initial conditions and goal (attachment: monkey_problem) Smodels generates 84 plans, which seem to be fine, for the goal: has_banana(monkey,lasttime), where lasttime=5. Below we show some of those plans: Plan1: MONKEY USES BOX walk(monkey,l3,0) push_box(monkey,l2,1) climb_on(monkey,box,2) grab_banana(monkey,3) Achieves goal: has_banana(monkey,4) Plan2: TRAINER VOLUNTARILY COOPERATES WITH MONKEY walk(trainer,l2,0) walk(monkey,l2,1) climb_on(monkey,trainer,2) grab_banana(monkey,3) Achieves goal: has_banana(monkey,4) Plan3: ANOTHER POSSIBILITY FOR PLAN2 walk(monkey,l2,0) walk(trainer,l2,1) climb_on(monkey,trainer,2) grab_banana(monkey,3) Achieves goal: has_banana(monkey,4) Plan4: MONKEY REQUESTS TRAINER'S HELP walk(monkey,l2,0) scream_monkey(1) walk(trainer,l2,2) climb_on(monkey,trainer,3) grab_banana(monkey,4) Achieves goal: has_banana(monkey,5) Plan5: ANOTHER POSSIBILITY FOR PLAN4 - MONKEY GOES TO THE BANANA'S LOCATION SITTING ON TRAINER'S SHOULDER scream(monkey,0) walk(trainer,l1,1) climb_on(monkey,trainer,2) walk(trainer,l2,3) grab_banana(monkey,4) Achieves goal: has_banana(monkey,5) Smodels generated 56 plans to the goal used by Hudson: has_banana(monkey,lasttime) and at(box,l3,lasttime), where lasttime=5. We also got 2 plans (plan4 and plan5 above) that included action scream(monkey) for this goal. ----- After our program was written, we looked at Hudson's solution. It is very similar to what we did. There are some differences though, we would like to point the following: 1. Hudson's solution uses fluent "prompted" in the following laws scream causes prompted. caused false if at(monkey,L) && -at(trainer,L) after prompted. (*) nonexecutable walk(trainer,L) if -prompted. The first rule is as ours. The last one doesn't allow trainer to move freely (which we can of course do too.) We are not sure about the second rule though. It seems to say that, if prompted is true in S then in any successor of S the trainer and the monkey are in the same position. Are we right? If so this seems to allow the monkey to go to the trainer instead of trainer going to the monkey. We are not sure if it was intended. Our solution uses: default(neg(prompted(trainer)), []). impossible(B,[prompted(trainer), at(monkey,L)]) :- action(B), location(L), diff_actions(walk(trainer,L),B). which says that if trainer is prompted the only action that can be executed is: walk(trainer,L). But the trainer can move around freely when not prompted. This solution can be viewed as written in C as well as in B plus. The conjecture is that both interpretations are equivalent. Hudson also uses the following: always at(O,l1) ++ at(O,l2) ++ at(O,l3) ++ at(O,l4). (**) always at(monkey,L) && onBox ->> at(box,L). (***) Do we really need (**)? We represent (***) as a dynamic causal law. Hudson's solution is better here, but we didn't change our original version. ---------- X-Sun-Data-Type: default X-Sun-Data-Name: monkey.pl X-Sun-Content-Lines: 197 %%------------------------------------------------------------- %% Monkey with Trainer Example %% as proposed to TAG by V. Lifschitz %% %% Version written in Language B plus defaults %% %% Last modified: 4/27/99 %%------------------------------------------------------------- object(box). object(banana). agent(monkey). agent(trainer). location(l1). location(l2). location(l3). location(l4). climbing_point(box). climbing_point(trainer). element(X) :- object(X); agent(X). %%------------------------------------------------------------- %% ACTIONS %%------------------------------------------------------------- action(climb_on(monkey,Y)) :- climbing_point(Y). action(push_box(monkey,L)) :- location(L). action(walk(X,L)) :- agent(X), location(L). action(grab_banana(monkey)). action(scream(monkey)). %%------------------------------------------------------------- %% FLUENTS %%------------------------------------------------------------- fluent(at(X,L)) :- element(X), location(L). % monkey is sitting on the trainer's shoulder or the box fluent(on(monkey,P)) :- climbing_point(P). % trainer is prompted to approach the monkey fluent(prompted(trainer)). fluent(has_banana(monkey)). %%------------------------------------------------------------- %% DEFAULTS %% %% default(l,H) - normally l holds in any state %% which satisfies H. %%------------------------------------------------------------- % Normally prompted is false. default(neg(prompted(trainer)), []). %%------------------------------------------------------------- %% DYNAMIC CAUSAL LAWS %% %% causes(A,F,P) iff action A causes fluent literal F %% to be true if preconditions P hold. %%------------------------------------------------------------- causes(climb_on(monkey,P), on(monkey,P), []) :- climbing_point(P). causes(push_box(monkey,L), at(box,L), []) :- location(L). causes(push_box(monkey,L), at(monkey,L), []) :- location(L). causes(walk(X,L), at(X,L), []) :- agent(X), location(L). causes(walk(trainer,L), at(monkey,L), [on(monkey,trainer)]) :- location(L). causes(grab_banana(monkey), has_banana(monkey), []). causes(scream(monkey), prompted(trainer), []). %%-------------------------------------------------------------- %% STATIC CAUSAL LAWS %% %% caused(G,F) iff set of fluents F causes fluent literal G %% to be true. %%-------------------------------------------------------------- caused(neg(at(X,L1)), [at(X,L2)]) :- element(X), location(L1), location(L2), diff(L1,L2). caused(at(banana,L), [has_banana(monkey), at(monkey,L)]) :- location(L). %%-------------------------------------------------------------- %% EXECUTABILITY CONDITIONS %% %% impossible(A,F) iff it is not possible to execute action A %% if set of fluents F hold. %%-------------------------------------------------------------- impossible(B,[prompted(trainer), at(monkey,L)]) :- action(B), location(L), diff_actions(walk(trainer,L),B). impossible(climb_on(monkey,P), [on(monkey,P)]) :- climbing_point(P). impossible(climb_on(monkey,P), [at(monkey,L1), at(P,L2)]) :- climbing_point(P), location(L1), location(L2), diff(L1,L2). impossible(push_box(monkey,L), [on(monkey,P)]) :- location(L), climbing_point(P). impossible(push_box(monkey,L), [at(box,L)]) :- location(L). impossible(push_box(monkey,L), [at(monkey,L1), at(box,L2)]) :- location(L), location(L1), location(L2), diff(L1,L2). impossible(walk(monkey,L), [on(monkey,P)]) :- location(L), climbing_point(P). impossible(walk(A,L), [at(A,L)]) :- agent(A), location(L). impossible(grab_banana(monkey), [has_banana(monkey)]). impossible(grab_banana(monkey), [at(monkey,L1), at(banana,L2)]) :- location(L1), location(L2), diff(L1,L2). impossible(grab_banana(monkey), [neg(on(monkey,box)), neg(on(monkey,trainer))]). impossible(scream(monkey), [on(monkey,P)]) :- climbing_point(P). impossible(scream(monkey), [at(monkey,L), at(trainer,L)]) :- location(L). %%-------------------------------------------------------------- %% INITIAL SITUATION %%-------------------------------------------------------------- initially(neg(on(monkey,box))). initially(neg(on(monkey,trainer))). initially(neg(has_banana(monkey))). initially(at(monkey,l1)). initially(at(banana,l2)). initially(at(box,l3)). initially(at(trainer,l4)). initially(neg(prompted(trainer))). %%-------------------------------------------------------------- %% GOAL %%-------------------------------------------------------------- goal(has_banana(monkey)). %%-------------------------------------------------------------- %% AUXILIARY PREDICATES %%-------------------------------------------------------------- eq(X,X). diff(L1,L2) :- location(L1), location(L2), \+ eq(L1,L2). diff_actions(A,B) :- action(A), action(B), \+ eq(A,B). ======== Date: Wed, 26 May 1999 From: Hudson Turner To: TAG I haven't finished studying the UTEP KRGROUP description and implementation of the monkey trainer problem, but I can respond to some of the helpful comments and questions that introduced it. > After our program was written, we looked at Hudson's solution. It is > very similar to what we did. There are some differences though, we > would like to point the following: > 1. Hudson's solution uses fluent "prompted" in the following laws > scream causes prompted. > caused false if at(monkey,L) && -at(trainer,L) after prompted. (*) > nonexecutable walk(trainer,L) if -prompted. > > The first rule is as ours. > The last one doesn't allow trainer to move freely (which we > can of course do too.) Yes. My worry was that, intuitively, the possibility of a plan may otherwise depend on the cooperation of the trainer. It seems to me that if the trainer can move freely, the trainer can foil the monkey's plans (at least the ones that involve the trainer). The trainer may walk away from the monkey when the monkey wants to climb the trainer. Or the trainer may walk away from the banana when the monkey wants to grasp it. One possibility is to assume that the trainer cooperates in the monkey's plan, which is a typical assumption in multi-agent planning, as far as I know. But if we assume that the trainer will cooperate, and still allow the trainer to move freely, then there are (shorter) plans in which the monkey doesn't scream -- the trainer just walks over to the banana without prompting. Your Plan 2 is an example of this kind. > Plan2: TRAINER VOLUNTARILY COOPERATES WITH MONKEY > walk(trainer,l2,0) > walk(monkey,l2,1) > climb_on(monkey,trainer,2) > grab_banana(monkey,3) > > Achieves goal: has_banana(monkey,4) I was looking for any easy way to obtain Vladimir's suggested plan as an optimal one. (Hence, for instance, my additional stipulation that the box end up where it starts.) > We are not sure about the second rule though. It seems to say > that, if prompted is true in S then in any successor of S the > trainer and the monkey are in the same position. Are we right? > If so this seems to allow the monkey to go to the trainer > instead of trainer going to the monkey. We are not sure if it > was intended. The idea is to "oblige" the trainer, when prompted, to end up at the same place as the monkey. I don't say *how* this is to happen. > The main idea was to express the trigger, i.e. a statement of the > form "if prompted then trainer must approach the monkey," by : > > impossible(B,[prompted(trainer),at(monkey,L)]) :- > location(L), action(B), diff_actions(B,walk(trainer,L)) > > which says that any other action is impossible in a state in which > prompted is true. (It is easy to modify this to allow concurrent > actions by replacing "diff_actions(B,walk(trainer,L))" by > "not member(walk(trainer,L), B)"). This formulation requires that the trainer, when prompted, walk to where the monkey was when it screamed. If we allow concurrent actions, and the monkey moves, the trainer ends up where the monkey used to be. Also, it is impossible for the monkey to scream when the trainer and monkey are in the same place, since that would force the trainer to walk to where the trainer already is. > impossible(walk(A,L), [at(A,L)]) :- > agent(A), location(L). It's not clear to me why the monkey should be unable to scream in such a case. In contrast, you wrote this "explicitly": > impossible(scream(monkey), [at(monkey,L), at(trainer,L)]) :- > location(L). Another action precondition for scream, which puzzles me. > impossible(scream(monkey), [on(monkey,P)]) :- > climbing_point(P). (More generally, according to both our descriptions, it seems the monkey cannot scream if the trainer cannot later reach the required location -- I would have thought that maybe the monkey can scream anyway, but fruitlessly.) About your use of prompted you say... > This worked fine, but we noticed that the trainer would stay prompted > afterwards. > To remedy this problem we introduced the default statement: > default(neg(prompted(trainer)), []). In C the corresponding assumption was expressed in the constant declaration: prompted :: defaultFalseFluent; > Hudson also uses the following: > > always at(O,l1) ++ at(O,l2) ++ at(O,l3) ++ at(O,l4). (**) > always at(monkey,L) && onBox ->> at(box,L). (***) > > Do we really need (**)? I think I understand the question -- if we assume that reasoning is always in the context of a complete initial state, then the constraint (**) will hold initially, and will be maintained (I believe). For other kinds of reasoning, it seems (**) is needed. Again intuitively, it seems that the monkey trainer problem raises issues we probably don't know how to resolve. Are the trainer and monkey working together? If so, what is the use of "scream"? If not, should a plan here consist only of the actions of the monkey, with the trainer free to act as he will? I guess there are many complications and elaborations possible. Vladimir suggests that we might understand this as game playing -- in which case, I suppose it will typically be a mistake to look for valid plans, even conditional ones. And what to do about a "game" in which the opponents can perform actions concurrently? I doubt I know how to start thinking about this. A question that occurs to me: does the monkey's determination to perform an action "trump" the inclinations of the trainer -- can the monkey always do what it wants if the trainer has otherwise performable actions that cannot be performed concurrently? (Or the other way around?) ==================== Date: Fri, 4 Jun 99 From: Michael Gelfond and Monica Nogueira To: TAG First, thanks very much to Hudson for the prompt comments. The discussion is very useful to us. Here is some response. Hudson: > One possibility is to assume that the trainer cooperates in the monkey's > plan, which is a typical assumption in multi-agent planning, as far as I > know. This was our assumption. > But if we assume that the trainer will cooperate, and still allow the > trainer to move freely, then there are (shorter) plans in which the monkey > doesn't scream -- the trainer just walks over to the banana without > prompting. True. > I was looking for any easy way to obtain Vladimir's suggested plan as an > optimal one. (Hence, for instance, my additional stipulation that the box > end up where it starts.) We obtain the plans where action "scream " appears by adding a new rule that says action scream "must" occur at some moment of time, as scream(monkey,0) or scream(monkey,1) or... or scream(monkey,T) <- next(T,lasttime). (The disjunction of course is written then as rules of the form scream(monkey,0) <- not scream(monkey,1), ..., not scream(monkey,T). ... scream(monkey,T) <- not scream(monkey,0), not scream(monkey,1), ... ) Hudson also pointed about our solution that: > This formulation requires that the trainer, when prompted, walk to where > the monkey was when it screamed. If we allow concurrent actions, and the > monkey moves, the trainer ends up where the monkey used to be. Also, it > is impossible for the monkey to scream when the trainer and monkey are in > the same place, since that would force the trainer to walk to where the > trainer already is. >> impossible(walk(A,L), [at(A,L)]) :- >> agent(A), location(L). > It's not clear to me why the monkey should be unable to scream in such a > case. In contrast, you wrote this "explicitly": >> impossible(scream(monkey), [at(monkey,L), at(trainer,L)]) :- >> location(L). We assumed that when monkey screams, it is CALLING the trainer for help. Thus, the monkey would stay and wait for the trainer to come to it. Probably, in our interpretation the monkey is too rational but we are trying to model rational agents. This assumption also explains the last axiom. We can of course remove this axiom and make trainer to walk to the monkey only if it is not already there. > Another action precondition for scream, which puzzles me. >> impossible(scream(monkey), [on(monkey,P)]) :- >> climbing_point(P). Similar case, if monkey is on trainer already, they are at the same place and monkey doesn't need to CALL trainer for help anymore. > (More generally, according to both our descriptions, it seems the monkey > cannot scream if the trainer cannot later reach the required location -- > I would have thought that maybe the monkey can scream anyway, but > fruitlessly.) We believe the explanations above cover this too. We decided to experiment with Hudson's solution and use Ccalc. Esra and Norm answered some of Monica's questions for which we thank them. Trying to understand how the trainer and monkey interact in that solution, we presented the following problem: :- plan facts :: init -prompted, init at(monkey,l1), init at(banana,l2), init at(box,l3), init at(trainer,l4); goal :: last at(trainer,l3), last at(monkey,l3). and got the following interesting plan: | ?- plan(0). calling sato... 0. at(banana,l2) at(box,l3) at(monkey,l1) at(trainer,l4) ACTIONS: walk(monkey,l4) 1. at(banana,l2) at(box,l3) at(monkey,l4) at(trainer,l4) ACTIONS: climbTrainer 2. onTrainer at(banana,l2) at(box,l3) at(monkey,l4) at(trainer,l4) ACTIONS: scream 3. onTrainer prompted at(banana,l2) at(box,l3) at(monkey,l4) at(trainer,l4) ACTIONS: walk(trainer,l3) 4. onTrainer at(banana,l2) at(box,l3) at(monkey,l3) at(trainer,l3) run time (seconds) 0.01 Verify plan? (y/n) y verifying.... The plan is verified! yes This is counterintuitive w.r.t. our understanding of the problem. The problem is we do not see any way for the monkey to communicate his intention of going to location l3 to the trainer. In Hudson's solution the action scream seems to have this power. Is it intentional? We realized lately that our first solution would only work correctly if we included in the initial situation the following axioms: initially(neg(on(monkey,box))). initially(neg(on(monkey,trainer))). initially(neg(has_banana(monkey))). They were necessary to maintain consistency of the initial situation, since the translator b2s.pl introduced axioms of the form: initially(F) or initially(neg(F)) <- for each fluent F, and we didn't have any static causal laws (or constraints) to avoid impossible situations like the monkey and the box being initially in different locations AND the monkey being on top of the box at the same time. We fix this problem by introducing the following static causal laws to our program: caused(neg(has_banana(monkey)), [at(monkey,L1), at(banana,L2)]) :- location(L1), location(L2), diff(L1,L2). caused(neg(on(monkey,P)), [at(monkey,L1), at(P,L2)]) :- climbing_point(P), location(L1), location(L2), diff(L1,L2). We have been working on finding a better (more efficient) solution to the monkey-trainer problem. To reduce finding a plan to computing an answer set of a program P2 which has fewer answer sets than that of P1. (Here P1 is the program used in our first solution). Here is the first attempt: Our new domain description D2 is almost the same as the old description D1. We added the above rules and removed the rule: impossible(B,[prompted(trainer), at(monkey,L)]) :- action(B), location(L), diff_actions(walk(trainer,L),B). There is nothing wrong with it but it is not really needed for planning. (It is needed for temporal prediction though.) Our translator b2s used to translate D1 into a program P1. The new translator translates D2 into a program P obtained from P1 by removing rules of the type: 1. a(T) or neg(a(T)) <- which says that an action can occur or not occur at time T. 2. <- a(lasttime). which says that no action can be performed at lasttime. 3. <- a1(T), a2(T). which says that no two actions a1 and a2 can be performed in parallel. We decided to separate P from the module which controls the program search for a plan. We can use different control modules in conjunction with P. Here we use the following module, say C. 1. a1(T) or a2(T) or ... or an(T) <- not has_banana(monkey,T), not prompted(trainer,T). This rule requests to look for sequential plans, such that, until the goal is reached, the monkey performs at least one action at each moment of time except those in which it must wait for the trainer. 2. walk(trainer,L,T) <- prompted(trainer,T), at(monkey,L,T). This rule requires trainer to walk to the monkey. Notice that we are only interested in plans where role of the trainer is limited to walking to the monkey when prompted. It excludes, for instance, a plan: scream(monkey,0) walk(trainer,l1,1) climb_on(monkey,trainer,2) walk(trainer,l2,3) grab_banana(monkey,4) This plan was found by our program P1 but it is in a sense contrary to our reading of the story. It presupposes that the trainer knows that monkey wants to get the banana and actively tries to help. 3. scream(monkey,0) or scream(monkey,1) or... or scream(monkey,T) <- next(T,lasttime). This rule says that we are only interested in plans in which the monkey screams. 4. <- a(T), neg(a(T)). This rule guarantees consistency. These rules can be viewed as a declarative description of control. We are looking only for the sequential plans. (Maybe in the next message we remove this restriction and allow some actions to be performed concurrently). Now the problem of finding a plan (containing scream) is reduced to finding an answer set of program P2 = P + C. The number of answer sets to be computed is substantially decreased which, we believe, leads to an increase in efficiency. We also get better plans, e.g., limiting the search to the point where the goal is reached, eliminates only uninteresting plans where the agent keep acting "without need". We timed some experiments using Smodels to compare efficiency of programs P1 and P2. The results were as follow: -------------------------------------------------------------------------- program lasttime #plans time(secs) About plans obtained -------------------------------------------------------------------------- P1 5 84 1 2 plans have action scream, because we allow trainer to walk with monkey on his shoulders P' 5 6 0 one plan contains scream. P2 5 1 0 -------------------------------------------------------------------------- P1 8 2,214 650 P' 8 770 5 P2 8 227 3 -------------------------------------------------------------------------- where P' is P2 minus axiom 3. It looks for plans with and without scream as P1 does. There are many questions associated with this example but we probably should send it in right now and wait for your comments. ==================== Date: Fri, 4 Jun 1999 From: Hudson Turner To: Michael Gelfond and Monica Nogueira Monica and Michael, What fun! On Fri, 4 Jun 1999 monica@cs.utep.edu wrote: > > Dear TAG, > > First, thanks very much to Hudson for the prompt comments. > The discussion is very useful to us. Here is some response. > > Hudson: > > > This is counterintuitive w.r.t. our understanding of the problem. > The problem is we do not see any way for the monkey to communicate his > intention of going to location l3 to the trainer. > > In Hudson's solution the action scream seems to have this power. > Is it intentional? I can't say I anticipated this. I guess it makes sense, given that I was already willing to allow, with concurrency, that the trainer might have to meet the monkey somewhere. (Or maybe the story could have been that the trainer can see where the monkey is going, and meet it there.) I guess it is probably closer to the spirit of Vladimir's scenario to have the scream oblige the trainer to go where the scream came from, much as you did. Then again, it is entertaining to imagine the monkey driving the trainer around the room. > > caused(neg(has_banana(monkey)), [at(monkey,L1), at(banana,L2)]) :- > location(L1), location(L2), diff(L1,L2). > > caused(neg(on(monkey,P)), [at(monkey,L1), at(P,L2)]) :- > climbing_point(P), location(L1), location(L2), diff(L1,L2). These seem like maybe they should be "state constraints." > > We have been working on finding a better (more efficient) solution > to the monkey-trainer problem. To reduce finding a plan to computing an > answer set of a program P2 which has fewer answer sets than that of > P1. (Here P1 is the program used in our first solution). > > Our translator b2s used to translate D1 into a program P1. > The new translator translates D2 into a program P obtained from P1 > by removing rules of the type: > 1. a(T) or neg(a(T)) <- > which says that an action can occur or not occur at time T. > > 2. <- a(lasttime). > which says that no action can be performed at lasttime. > > 3. <- a1(T), a2(T). > which says that no two actions a1 and a2 can be performed in > parallel. > > > We decided to separate P from the module which controls the program > search for a plan. We can use different control modules in conjunction > with P. Here we use the following module, say C. > > 1. a1(T) or a2(T) or ... or an(T) <- not has_banana(monkey,T), > not prompted(trainer,T). > This rule requests to look for sequential plans, such that, until the > goal is reached, the monkey performs at least one action at each > moment of time except those in which it must wait for the trainer. > > 2. walk(trainer,L,T) <- prompted(trainer,T), at(monkey,L,T). > This rule requires trainer to walk to the monkey. > > Notice that we are only interested in plans where role of the trainer > is limited to walking to the monkey when prompted. It excludes, for > instance, a plan: > > scream(monkey,0) > walk(trainer,l1,1) > climb_on(monkey,trainer,2) > walk(trainer,l2,3) > grab_banana(monkey,4) > > This plan was found by our program P1 but it is in a sense contrary to > our reading of the story. It presupposes that the trainer knows that > monkey wants to get the banana and actively tries to help. > > 3. scream(monkey,0) or scream(monkey,1) or... or scream(monkey,T) <- > next(T,lasttime). > This rule says that we are only interested in plans in which the > monkey screams. > > 4. <- a(T), neg(a(T)). > This rule guarantees consistency. > > These rules can be viewed as a declarative description of control. Interesting. I wonder if you get similar improvement in performance by adding to P1 constraints (as necessary) corresponding to your "control" rules. The requirement that an action occur at each time step can be understood as a planning heuristic -- and I imagine all optimal plans in this domain will have this property. In classical planning anyway, I suppose this is a heuristic that is not "domain-specific" *and* never rules out any optimal plans. Other heuristics, including domain-specific heuristics, and even heuristics that depend on details of the initial state and goal, might also be expressed. But as I understand common practice, heuristics should not rule out all optimal plans -- which suggests that your 3, for instance, may be best understood as something other than a planning heuristic. The requirement that a scream occur may be best understood as an aspect of the goal. Perhaps the requirement that the trainer act only when prompted can be understood in the same way. (But this still leaves open the question of why we are interested in such a plan. It seems a plan like this can be sure to succeed only if the trainer cooperates. Perhaps the story is that the trainer has agreed to behave this way -- I guess we don't need to worry about why -- perhaps he wishes to make himself available for the monkey's use, but doesn't know what the monkey wants unless the monkey tells him -- and the monkey can only scream for his presence.)