Alex Golden
Richard Golden
CSC 242 Term Project
Planning with UCPOP, Graphplan and Sensory Graphplan
Background:
Both Richard and Alexander greatly enjoyed working with UCPOP during the
planning assignment. They each came up with different, interesting domains to
solve, Rich's being "Dungeon Master" where a man must find a way out
of a dungeon. Alex chose to represent the world of Boxxle
in UCPOP to see if it could solve the puzzles.
They were both disappointed to find that UCPOP failed to find
solutions to many of their problems, even though they were relatively simple
(had few operators, only took a few steps to get to a solution).
Both Rich and Alex are very interested in finding out why
UCPOP didn't work on those certain problems and domains. Our goal for the Term
Project was to determine what went wrong during the UCPOP assignment. Were our
domains and problems too complicated for UCPOP to solve, or could we simplify
them to the point of being solvable in UCPOP? Would other planners be able to
solve the problems that UCPOP can't? Would a problem solver have better luck
than the planners? We set out to answer all of these questions and more in this
project.
Note: When using graphplan to solve “Dungeon
Master” problems it solved all of Rich’s test cases from the UCPOP
project. It fared so well on them that
Rich believed that with “Dungeon Master” domain it would be difficult to
produce a problem hard for graphplan to solve, except for a stress test. As such, our group project tends to focus
mainly on the Boxxle domain, a far more interesting domain than “Dungeon
Master.” For all inquiries into the “Dungeon
Master” domain, please see Rich’s UCPOP project.
About the planners / problem solvers:
Name 
Type 
Web page 
Info 
BoxxleSolver 
Problem solver 
n/a 
Written by us in Java. 
UCPOP 
Planner (Lisp) 
A planner written in Lisp. 

Sensory Graphplanner (SGP) 
Planner (Lisp) 
A Lisp planner based on Graphplanner. 

Graphplan 
Planner (Written in C) 
A compiled planner written in C. 
Directory Structure:
docs/ 
Contains document files. 
graphplan/ 
Contains the Graphplan executable and more. 
ourplanner/ 
Contains Java source code to our incomplete planner to solve Boxxle problems. 
problemsolver/ 
Contains Java source code to our Boxxle problem solver. 
sgp/ 
Sensory Graphplanner (SGP). 
testcases/ 
Contains ASCII files of Boxxle maps and Java programs to convert those to useable files. 
UCPOP/ 
Contains UCPOP and Boxxle domain definitions. This is a slightly more efficient version of Alex's UCPOP project. 
About the testcases:
Creating the input for four different programs would prove be
a time consuming task. In order to simplify the process Rich and I wrote four
different programs:
AsciiToProdigy 
Java application to convert an ASCII Boxxle map to a facts
file readable by graphplan. 
AsciiToSgp 
Java application to convert an ASCII Boxxle map to Lisp
code usable by Sensory Graphplanner. 
MapToJava 
Java application to convert an ASCII Boxxle to a character array definition useable by Java. 
MapToHtml 
Java application to convert an ASCII Boxxle to a HTML code
to display a graphical representation of the map. 
Each of these programs is capable of converting one ASCII map
at a time. Perl scripts were written to convert all of the current test cases
at once, put them into their appropriate files (i.e. BoxxleSolver.java for the
problem solver, or domains.lisp for UCPOP or SGP).
About our planner:
Our original task was to write a planner to solve Boxxle levels. However,
after many hours of work the planner was not close to being able to solve
Boxxle levels. After that we searched the web and found additional planners we
could use instead of UCPOP. These are without a doubt more efficient than our
planner would have been, and are more than capable of showing UCPOP's
weaknesses.
Boxxle is a puzzle game for the Nintendo Game Boy released in 1989. The idea of
the game is simple: You are a guy, and you meet a girl who you would love to
show a night on the town. Unfortunately you don't have any cash, and you need
to get a job. You weren't smart enough to be a computer science major so you
take a job moving boxes around in a warehouse. For what the game lacks in an
interesting story it more than makes up for with challenging puzzles. The game puts on you different levels, and
on each level your job is to push all of the boxes to goal squares on the map.
Once you've done this, you go on to the next level, until you beat the game,
get to go out on your date.
Rules Of The Domain:
1: There is a map that consists of the player, boxes,
goal squares, empty squares, and walls.
2: The goal for each map is to push all of the boxes
onto goal squares.
3: There are an equal number of goal squares and boxes
for each map.
4: The player may move up, down, left, and right so
long as there is an adjacent, empty square in that direction.
5: The player may only move boxes by pushing them. The
player may only push a box into an empty square.
Key:
The Player = Where the player starts
A Box = A Box
Goal State = Where you want the boxes to be
Box On Goal = A box on a goal
Wall = A wall
Space = An empty space on the map
A Simple Map & Solution:
Our Test Maps: Here are our tests maps for Boxxle. Each map is also accompanied
by a table that shows how our problem solver, UCPOP, Graphplan, and Sensory
Graphplan fared on them. Enjoy!
test1: 

Steps
to goal: 1
Spaces: 3
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





test2: 

Steps to goal: 2
Spaces: 4
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test3: 

Steps to
goal: 1
Spaces: 4
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test4: 

Steps to
goal: 3
Spaces: 6
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 5: 

Steps to
goal: 3
Spaces: 7
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 6: 

Steps to
goal: 3
Spaces: 5
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 7: 

Steps to
goal: 4
Spaces: 6
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 8: 

Steps to goal: 6 Spaces: 7
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 9: 

Steps to goal: 6
Spaces: 8
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 10: 

Steps to goal: 6
Spaces: 9
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 11: 

Steps to
goal: 7
Spaces: 10
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 12: 

Steps to
goal: 9
Spaces: 11
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 21: 

Steps to
goal: 2
Spaces: 10
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 22: 

Steps to
goal: 4
Spaces: 10
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 23: 

Steps to goal: 4
Spaces: 15
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 24: 

Steps to goal: 8
Spaces: 15
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 25: 

Steps to goal: 10
Spaces: 15
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 26: 

Steps to goal: 14
Spaces: 15
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 27: 

Steps to goal: 21
Spaces: 22
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Test 28: 

Steps to goal: 21
Spaces: 36
Our Problem Solver 
UCPOP 
Graphplan 
Sensory Graphplan 





Conclusion: All programs were relatively close in speed at solving
simple Boxxle problems. However, UCPOP began to take significantly longer than
the others with map test7 when it took over 18 seconds to solve the problem
while the others took less than one second. It should be noted that SGP, which
very similar Lisp code to UCPOP, was able to solve the problem.
Sensory Graphplanner proved itself to be much faster and able to solve Boxxle
problems than UCPOP. It is our recommendation that you look into changing the
project from using UCPOP to Sensory Graphplanner next year. They take nearly
identical input, while Sensory Graphplanner can solve problems that UCPOP cannot
and may prevent the same frustration that Rich and I faced during the UCPOP
project. We were relieved to know that our code was all right, but UCPOP just
couldn't handle certain kinds of problems.
We would also like to point out how simple graphplan was to
use. While learning UCPOP, it seemed as though learning how to load it in Lisp
was half the battle. Graphplan simply reads two text files at runtime (the
domain definition and the problem definition) and then proceeds to solve the
problem. It was faster than both the Lisp planners and much easier to use. If
working with a Lisp planner isn't a requirement for the class than I would
suggest looking into changing the project from UCPOP to Graphplan. Graphplan
not only outperformed both UCPOP and SGP but it's low learning curve would
allow students to concentrate more on creating intricate domains and detailed
documentation than fighting with Lisp to get results that they want.
As expected, our problem solver which was designed to
specifically solve Boxxle problems had the best performance. However, it took
many hours of man work to produce this fine tuned program. The only problem we
tested that Graphplan did not keep up with our planner was test27, which
graphplan could not solve but our problem solver figured out in 38 seconds. Our
problem solver used techniques such as never searching a state we had visited
before and not searching down certain paths that it knew a goal could not be
reached on.
In conclusion, every option we tried (besides our Boxxle
planner which was not completed) outperformed UCPOP in solving Boxxle problems.
Our problem solver took the most time to produce, which is understandable
seeing as it is an entire program instead of a problem definition in another
program. Graphplan outperformed SGP, although in most cases the difference was
only by a few seconds. Test26 was the only case that Graphplan could solve but
SGP could not.