This problem set is simplicity itself: write a function

which takes a goal as input, generates a solution plan that solves the goal, and executes that plan in the Truckworld. You can define a goal however you want, though there will be some suggestions below. What’s more, we will be operating in a very simple Truckworld environment, consisting of only three locations and only a few objects:

Here is more detail about the world:

1. The truck begins at location A, half full with fuel.
2. Every trip consumes a half tank of fuel.
3. The cargo bays and the box can hold an arbitrary number of objects.
4. Carrying the glass in a cargo bay and moving the truck will break the glass unless it is contained in a box.
5. You can put any item inside the recycler, and it disappears.
6. You do not need money to get full fuel drums, but you can only vend one fuel drum at a time.

Another nice thing about this world is that the objects always appear at prespecified locations and positions:

• The garbage is at location A position 6.
• The rock is at location C position 7.
• The glass is at location A position 8.
• The box is at location B position 9.
• The recycler is at location A position 11.
• The fuel drum dispenser is at location B position 12.
• Fuel drums will be dispensed location B position 13.
• The fuel drum consumer is at location B position 14.

Solve the problem in several steps:

1. Parse the goal and, along with the other information about the world given above, forumulate a search problem.
2. Use the search code to solve the problem. This produces a sequence of operators as output.
3. Start the Truckworld and execute the solution operators.

1. Formulating the problem

The tricky part of the first step is to decide how to represent the problem (state, operators, goals). It is probably best to begin by defining a goal. You need not use the following representation exactly, but your solution must solve all of the following goals:

(defvar *goal-1* '((GLASS A) (GLASS UNBROKEN)))

(defvar *goal-2* '((GARBAGE RECYCLED)))

(defvar *goal-3* '((GLASS BROKEN)))

(defvar *goal-4* '((ROCK RECYCLED)))

(defvar *goal-5* '((GLASS RECYCLED)))

(defvar *goal-6* '((GLASS C) (GLASS UNBROKEN)))

(defvar *goal-7* '((ROCK RECYCLED) (GLASS RECYCLED)))

(defvar *goal-8* '((GARBAGE B) (GLASS B) (GLASS UNBROKEN)))

(defvar *goal-9* '((ROCK RECYCLED) (GLASS C) (GARBAGE IN-BOX)))

(defvar *goal-10* '((ROCK RECYCLED) (GLASS A)

(GLASS UNBROKEN) (FUEL FULL)))

(defvar *goal-11* '((ROCK RECYCLED) (GLASS C) (GLASS UNBROKEN)

(GARBAGE IN-BOX) (FUEL FULL)))

Another big part of an effective solution will be to limit how long plans get. As you discovered in Problem Sets 0 and 1, even a simple pickup action in Truckworld consists of several primitives; more complex actions like refueling the truck consist of many primitives. It is probably infeasible to generate plans in a space where the operators are Truckworld primitives, as the plans will be too long and thus will take too long to generate. You should therefore use the concept of "macro-operators" from Problem Set 1: your search operators will be macrops instead of primitives.

In the PS2 directory, you will find macrops that correspond to many of the search operators you will need. For PS2, one extra feature has been added to the macrop expansion code which lets you use the name of an object in place of its location, i.e.,

(pick-up !glass)

You will also have to come up with a heuristic ranking function for the search. (Hint: concentrate on detecting repeated states and eliminating "nonsense" move sequences, e.g. picking up an object then immediately putting it down.)

2. Generating the solution

3. Executing the solution

Your search will supply you with a list of macro-operators that will move the world into a goal state. Now all that is left is to execute that solution in the Truckworld. You can use the truckworld interface and macrop code from Problem Set 1, including the following functions:

Suppose the agent knew the location of objects, but not their exact positions. It could then generate an abstract plan, but could not plan down to the level of primitives.

But the agent could compensate for this lack of information by using its sensors to find out where an object was at plan-execution time.

The behaviors we developed in Problem Set 1 implement this sort of abstract operator. For example, the pickup-recyclable behavior can be viewed as an abstract search operator with a precondition that there is a piece of recyclable material somewhere at the truck’s current location, and a postcondition that the recyclable object is no longer at that location and is being held by the truck.

Rewrite your search problem so that

• the initial state information tells the agent about objects’ locations but not their exact position
• the search does not rely on objects being vended or placed in pre-designated positions
• the search operators correspond to behaviors
• to execute a solution, you repeatedly initiate behaviors rather than execute macrops.