H

ICS 361, Artificial Intelligence Programming

Assignment 7

Due Sun 4/22 on or before 11:59:59 pm

In Prolog, write a means-ends analysis planner. Your program will implement the plan functor:

% plan(Start,     % the start state
%      Goal,	  % the goal state
%      Been_list, % a list of visited states to avoid infinite loops
%      Plan,      % the resulting plan, a series of moves
%      End_state  % the final state after executing the Plan

/* sample moves */
move(pickup2(X), [handempty, ontable(X), clear(X)],
		 [del(handempty), del(clear(X)), del(ontable(X)),
				  add(holding(X))]).

move(pickup(X), [handempty, on(X, Y), clear(X)],
		[del(handempty), del(clear(X)), del(on(X, Y)),
				 add(clear(Y)),	add(holding(X))]).

move(putdown(X), [holding(X)],
		 [del(holding(X)), add(on(X, table)), add(clear(X)),
				   add(handempty)]).

move(stack(X, Y), [holding(X), clear(Y)],
		  [del(holding(X)), del(clear(Y)), add(handempty),
                                    add(on(X, Y)), add(clear(X))]).

go(S, G, P) :- plan(S, G, [S], P, _).
test0(P) :-
	go([holding(a), ontable(c), on(b, c), clear(b)],
	   [on(a,b), on(b, c)], P).
test1(P) :-
	go([handempty, ontable(a), ontable(c), on(b, c), clear(a),
clear(b)],
	   [on(a,b), on(b, c)], P).
test2(P) :-
	go([handempty, ontable(b), ontable(c), on(a, b), clear(c),
clear(a)],
	   [handempty, ontable(c), on(a,b), on(b, c), clear(a)], P).
test3(P) :-
	go([handempty, ontable(a), ontable(b), on(c, a), clear(b),
clear(c)],
	   [on(a, b), on(b, c)], P).

Include a test run of your program with the above test inputs.

Hints

You should look at the textbook's Simple Prolog Planner. This is a depth-first search planner as opposed to a means-ends analysis planner. However some of the functors defined in the textbook's planner should be useful for your implementation. In particular, change_state, conditions_met, and member_state are used in my solution. Note that this planner includes the adts.pl code, a collection of abstract data type functors for stacks, queues, sets, and priority queues. Some of these definitions are already part of SWI Prolog's built-in libraries, so you should comment out the definitions for member, union, and intersection to avoid error messages when loading adts.pl. Note that there are a couple of important differences in the specification of the textbook's plan functor versus this assignment. First, our plan functor has an extra End_state argument. This is useful so that you don't have to recompute the end state of a recursive call to plan by applying all of the plan operators to the start state. The second less obvious difference is our plan functor returns the actual Plan in the 4th argument whereas the Moves argument in the textbook's plan functor is really an input parameter that holds the plan that has been generated up to the current call to plan. At the end of the plan call, Moves will not hold the full plan. This is why the textbook's code prints out the plan, because otherwise, the plan would be lost as it is not "returned" by the plan functor.

Note that the solution to this assignment should be very short. My solution (code only, not including comments or the above move and test functors) is only 22 lines and includes only one distinct functor and 2 rules, not including the code taken from the textbook's website.

Start by writing the plan functor code assuming that the selected operator's preconditions are satisfied. Here's the pseudo-code for means-ends analysis:

  1. find a predicate that is in Goal, but not in Start; call it Diff (adts.pl's set_diff functor is useful for this)
  2. then find an operator Name that has an add postcondition matching Diff
  3. unify Name's Preconditions with Start (the intersection functor can be used for this -- you don't care about the result, just that there is an intersection)
  4. check if the Preconditions are satisfied in Start (the textbook's conditions_met functor)
  5. if so:

The resulting Plan is just Name followed by the plan from the recursive call. Test this with test0(R).

Once you get the above to work, add another plan rule for the case when Preconditions are not met, in which case the plan functor should (after doing all of the same preliminary stuff before conditions_met):

  1. recursively plan from Start to new goal state Preconditions
  2. if successful, then apply Name to the End_state of the recursive call to get the new state, call it Child_state
  3. add Child_state to the Been_list
  4. append the recursive call's Plan to [Name] to get Pre_moves
  5. recursively plan from new start state Child_state to Goal
  6. finally append Pre_moves to the 2nd recursive call's Plan (Post_moves) to produce the final Plan

test3(P) will end up with an inefficient Plan that is too long to be printed by SWI Prolog. To see the entire plan, add the following code to your a7.pl file (or type the set_prolog_flag line without the :- directly to the Prolog interpreter):

% change the max print depth so we can see the entire plan (no ...)
:- set_prolog_flag(toplevel_print_options,[max_depth(0)]).

To save a log of your Prolog session to a file, use the protocol('mylog.txt'). predicate followed by noprotocol.

Submitting

Submit by zipping together your source code file (e.g., a7.pl) and your typescript file (e.g., typescript.txt) into a7.zip and then upload a7.zip to Assignment 7 on Laulima.


David N. Chin / Chin@Hawaii.Edu