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. |
|
our-planner/ |
Contains Java source code to our incomplete planner to solve Boxxle problems. |
|
problem-solver/ |
Contains Java source code to our Boxxle problem solver. |
|
sgp/ |
Sensory Graphplanner (SGP). |
|
test-cases/ |
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 test-cases:
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 |