University of Washington
Department of Computer Science and Engineering

CSE573–Artificial Intelligence I

Autumn 1997

Problem Set #2

Assigned October 22, 1997

Due November 3, 1997

State Space Search, and a Truckworld Agent

This problem set is simplicity itself: write a function

(solve-problem goal)

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.

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 at position 13.
• The fuel drum consumer is at location B position 14.

Consider the problem in several steps:

1. Parse the goal and, along with the other information about the world, generate a search problem
2. Use the search code to solve the search problem
3. Start the Truckworld and execute the solution.

1. Formulating the problem

The tricky part of the first step is to decide what formulation you will use to represent the problem. It will probably help to know what form the goals might take. 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 will see, even a simple pickup action in Truckworld consists of several primitives; more complex actions like refueling the truck consist of many primitives. If your search space comprises the set of all sequences of Truckworld primitives, you will have

serious problems solving even the smallest problems. (See "macro-operators" below.)

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

Use two methods to perform the search: iterative deepening search, and heuristic search based on your own ranking function. To do the former, you will have to extend the algorithm in search.lsp to do iterative deepening search.

3. Macro-Operators

As mentioned above, you will probably want to search using abstract (macro) operators, then expand the solution into primitive Truckworld actions. The file macrop-function.lsp

contains some code that will help you do so. It implements a function

(expand-macrop form)

which takes an expression representing a macro-operator, and expands it into a list of primitives. An example might be:

(expand-macrop ’(pickup glass)) =>

( (arm-move arm-1 outside)

(arm-move arm-1 8)

(arm-grasp arm-1)

(arm-move arm-1 folded)

(arm-move arm-1 inside)

(arm-move arm-1 bay-1)

(arm-move arm-1 0)

(arm-ungrasp arm-1 0)

(arm-move arm-1 folded)

)

This expansion takes advantage of several assumptions and design decisions, for example

• arm-1 will always be used to pick up objects
• arm-1 will always start in the folded position and not carrying anything
• the glass is at position 8
• position 0 of bay-1 will always be used for transporting glass.

You can write as many macro-operators as you want, and make as many assumptions as you want about what resources to use for what tasks (e.g. you can use one arm for picking up objects and the other arm for refueling). You will also have to take good advantage of the information about the three-node world provided above.

4. Implementing the solution

Your search will supply you with a list of macro-actions that will move the world into a goal state. Now all that is left is to execute that solution in the Truckworld. The code in truckworld-interface.lsp provides some handy functions to do so:

• (defun ti-start-simulator ())
• simulator must be loaded; load the three-node world and start the simulation using the functional command processor
• (defun ti-stop-simulator ())
• terminate the simulation and close the window
• (defun ti-redraw-simulator ())
• refresh the simulator’s display in case things get messy
• (defun ti-restart-simulator ())
• restart the simulation at the beginning. Equivalent to start then stop, but quicker.
• (defun ti-execute-macrop (command))
• Expand the command (a macrop) into primitives, then execute each primitive in the Truckworld.