University of Washington
Department of Computer Science and Engineering
CSE473–Introduction to Artificial Intelligence
Winter 1998
Problem Set #3
Assigned February 9, 1998
Due February 23, 1998
Planning: UCPOP and Graphplan
Here's the Truckworld scenario for this assignment, much like the one for Problem Set 2:
Here is more detail about the world:
- There is no refueling to worry about in this assignment.
- The cargo bays and the box can hold an unlimited number of objects.
- Carrying the glass in a cargo bay and moving the truck will break the glass unless it is contained in a box.
- Exploding a bomb at a location breaks everything at that location. Exploding a bomb in the truck breaks everything in the truck (unless it is in a box in the truck). Exploding in a bomb that is in a box breaks everything in that box. The truck cannot be broken, and being broken does not affect a box's ability to hold items.
Keep in mind that in this assignment we are just planning, and not executing. Therefore the positions of objects don't matter.
Part I: UCPOP
First transform the following goals into UCPOP axioms. I have annotated each one with how much luck I had trying to solve it (in UCPOP). I don't expect you to get them all, especially the ones I couldn't! You should define these goals in the file common.lsp.
;;; Trivial
Glass-2 is at A
;;; Almost trivial
Garbage-1 has been recycled
;;; Easy
Glass-1 is broken
;;; Almost trvial
Glass-1 and garbage-1 have both been recycled
;;; Can be nasty if you're not careful, but easy if you are
Glass-2 and garbage-1 have both been recycled
;;; Pretty easy
Glass-1 and glass-2 are both broken
;;; Easy if you order things right!
Glass-2 has been recycled
;;; Ditto
Glass-1, glass-2, and rock-1 have been recycled
;;; Surprisingly easy
The bomb (bomb-1) has been exploded, but glass-2 is not broken
;;; Pretty easy
Glass-1 and rock-1 are broken, but glass-2 is not
;;; Easy
All the glass is at B
;;; Solve these in sequence....
- The truck is at C
- The truck is at C, and glass-1 is in the truck
- The truck is at C and so is glass-1
- Glass-1 is in the box (box-1)
;;; I couldn't solve this one, but I kept thinking I could...
Glass-1 and rock-1 are both in the box
;;; Forget about it! Laughably hard!
Glass-1 is at B and is unbroken
Next, write UCPOP axioms for the operators (e.g. travel, load into truck, put into box, explode bomb), and build the initial conditions. Then try to use UCPOP to solve the goals.
Here are some tips on how to approach the problem.
- Start with really really (really really) easy problems.
- Test your operators fully. For every operator you write, concoct a test problem that tests only that operator.
- Now that you have your operators working, try some of the harder problems. It's probably a good idea to set the number of search iterations, *search-limit* kind of low at first, just to see how things are going. UCPOP will terminate with failure, but not with NIL, rather with an incomplete plan.
- On the one hand, you can learn something from analyzing this plan. What causal links is it adding? In what order? What stupid things is it doing? How can you fix them?
- On the other hand, it is important to realize that the plan that you get when UCPOP fails is fairly arbitrary. It is just the plan that it was considering when its iteration count was exceeded, so it's not necessarily a good plan.
- Now you have to worry about heuristic control (the ranking function). Apart from gross cheating (see below), the most important thing that determines how things go is the order of the goal conjuncts and the action preconditions. First analyze a UCPOP trace to see what goals are being addressed in what order (it's not always the same order that you defined them, and it's not always the opposite order either!) Manipulate the ordering to see if that improves performance. (Hint: you generally want the system to work on the "truck location" goal last, otherwise it will get in nasty "travel" loops.)
- When you discover that precondition ordering will get you only so far, and not very far at that, you have to think about how to cheat. Here is how I cheated. (You're welcome to use my cheats, which are in "truck-rank-func" and the functions it calls in hints.lsp, and/or come up with good ones of your own):
- For each goal I figured out how many travel actions there need to be, and I penalized the plan massively for every travel action in excess of that amount. (I said it was cheating!)
- I identified certain nonsense pairs: you should never pick up an object and put down the same object in the same location. (That's not really a valid rule, but I used it anyway.) You should never box an object then unbox that same object at the same location. (Ditto, but ditto.)
- With those rules you should be able to solve the same problems that I could; feel free to get more down and dirty, and go after the rest.
A framework to get you started and some hints on how to build the cheats are in the file my_ucpop.lsp in the ps3 directory. Also note the ucpop\domains subdirectory, which will give you plenty of examples on how to define operators, problems, and domains.
PART II: GraphPlan
Now convert the domain and problems to GraphPlan. A framework for your GraphPlan domain is in my_gplan.lsp in the ps3 directory. Try it on a number of problems, including the UCPOP ones. Comment on the following, or on anything else you found interesting in the process of converting and testing.
- Can GraphPlan handle problems of the same size as UCPOP? If so, how big can they be, if not, how small must they be?
- Is GraphPlan as sensitive to goal/precondition ordering?
- Are there certain problems that seem to take much longer than others (like UCPOP), or is the performance relatively even over the domain?
- How does GraphPlan's performance degrade as the size of the domain, number of actions, and length of solution plan increase? Which of these is it most sensitive to? (In other words, I want you to figure out what makes GraphPlan break, and tell me why.)
Final note:
Look in the file "readme.txt" in the ps3 directory to get started. It should help explain what's going on.