Homework 2 — Designing heuristics
UWL CS452/552 Articial Intelligence
Fall 2019
For your second homework, please experiment with heuristics to optimize the A* search for
solutions to congurations of my son’s game Rushhour. Rushhour is a children’s puzzle based on
sliding blocks back-and-forth on a grid. One of the blocks represents the family car, which is
stuck in trac: one or more blocks sit in between the family car and an exit the end of the family
car’s row of the grid. My son solves the puzzle by moving cars within their row or column so that
the path from the family car to the exit becomes clear; you and I will solve the puzzle by tuning
a heuristic search algorithm to nd a series of moves which are as optimal as we can manage.
Stuck in trac. Driving free!
Only the family car is allowed to exit; the other vehicles must remain in the frame.
You will receive a substantial amount of working code for your experiments: the Java code
you will produce for this homework will include little more than implementating your ideas for
heuristic functions1
. There are links to the code and its Javadoc on Canvas; some starting points
for exploring the code are:
• Package uwlcs452552.h2.model is an implementation of the game mechanics — the Rushhour
board, cars, possible moves, etc.
– Class uwlcs452552.h2.model.Boards has some sample initial board congurations.
• Package uwlcs452552.search.graph is a generic implementation of several of the graph search
algorithms we have discussed.
– The heart of this implementation is class GraphSearcher, which implements the GraphSearch algorithm of Russell and Norvig in its general form. The specic behaviors of
the frontier, the explored set, checking for goal nodes, etc. are provided through the
generic type arguments, and through the behaviors passed as constructor arguments.
1But there is also written work; keep reading.
– You will make particular (if indirect) use of class AStarSearcher, which specializes GraphSearcher with the priority queue details of A* search.
• Package uwlcs452552.h2 links the generic search implementations with the Rushhour model.
– Class uwlcs452552.h2.BreadthFirstFinder solves Rushhour puzzles using breadth-rst search.
This class is your frenemy: On the one hand, this class gives you a working example
of how we specialize the general search algorithms to a particular problem. But on the
other hand this class is your rival, since the entire point of designing good heuristics
with A* is to beat blind search algorithms like BFS. – For each heuristic function you implement, you will write one class extending uwlcs452552
.h2.MovesFinder. Note that the constructor for MovesFinder takes only one argument —
the heuristic function. Your subclasses should provide that constructor argument, and
nothing more: do not otherwise override any methods inherited from MovesFinder. – Finally, you will extend class uwlcs452552.h2.AbstractSolution to wrap up all of your
work on one bundle (see the Deliverables section below).
Deliverables and submitting them
There are three deliverables for this homework:
1. Contributions to uwlcs452552.h2.model.Boards. As I write this document, there are a
small number of example boards in that class, but we will all nd it useful if there are
more. Therefore this weekend or early next week I will scan some Rushhour cards, and will
ask each of you to encode two for inclusion in that class, and then email me the revised
Boards.java. Later in the week, I will update that class with all of your contributions.
Follow the naming convention of the board which are already in that le, make sure it
compiles and runs under BFS, and email me your updated Boards.java le. This portion of
the homework is due by Thursday, October 3.2
2. Heuristic function implementations. Using the approaches we studied for designing heuristics, I expect you to try at least three distinct ideas for heuristics for Rushhour, implementing
each one as a separate class extending MovesFinder. Your heuristics should be independent
of board size: although the physical toy does use a 6 × 6 board, the BoardState class which
represents one conguration of the board can have a dierent size set at its creation.
In addition, you should provide one additional MovesFinder extension which combines your
individual ideas using pointwise maximization.
When you are debugging your code, it may be helpful to use the setDebug method to generate
debugging information from running your code. However, the versions of your MovesFinder
extensions which you submit should not set this ag, or otherwise print output messages.
Finally you should write one additional class Solution in the h2 package (not uwlcs452552.h2,
just plain old h2) extending uwlcs452552.h2.AbstractSolution. This class simply allows me to
run all of your code at once. Your Solution class should look something like:
If you signed out your board sheet the week aer, then this portion is due Thursday, October 10.
package h2;
public class Solution extends uwlcs452552.h2.AbstractSolution {
public Solution() {
super(new MyFinder1(), new MyFinder2(),
// ...
new MyFinderNminusOne(), new MyFinderN(),
new MyComboFinder());
}
// Use *exactly* this main method
public static void main(String[] args) { new Solution().run(); }
}
where the MyFinderN’s implement your individual heuristic ideas, and MyComboFinder performs the pointwise maximization across them.3
Submit your code to Canvas as a zip or tgz le which expands to a src directory containing
your Java source at the top-level. I will expand your archive and then run commands like
javac -cp codeIGaveYou.jar src/*.java
This portion of the homework is due on Monday, October 21.
3. Written report. Analyze each of your heuristics, discussing
• How you derived them.
• Their properties, especially admissibility, consistency, and complexity. Do not spend
time on heuristics which are not admissibile and consistent, and do not duplicate solving
the problem in the heurisitic.
• Their performance, including consideration for each heuristic of
– Its eective branching factor on each board relative to both the theoretical branching factor for that board, and the eective branching factor by the provided BFS
implementation for that board.
– How stable its eective branching factor is across dierent boards.
Gather many numbers!
Discuss the factors behind each heuristic’s advantages, and draw conclusions as to which of
your heuristics are better or worse. Submit this report to Canvas as a PDF as discussed in
the syllabus.
This portion of the homework is due on Monday, October 21.
Things that will change
For the sake of giving you this assignment as soon as possible, I am opening it before I have
nished all of the code I plan to give you. In particular,
3Note that except for Solution, I do not care what you actually name these classes — so long as I can compile them
and run Solution. 3
• Much of the library does not yet have Javadoc comments.
• The run method of the AbstractSolution class does not yet do anything; this will simply be
a method which runs A* with all of your heuristics on the same boards.
You should nonethess be able to make substantial progress under the current state of this code. I
will update or remove items from the above list as I complete them.
Bug bounty
I wrote the code distributed with this assignment with haste. Although I have run it successfully,
I have not thoroughly tested it, and you are as likely as not to nd bugs in it. I will award a small
amount of extra credit for the rst accurate emailed report of each bug in the code. A report must
contain a minimal example which triggers the bug; reports which also identify suspected details
of the bug will be assessed as more valuable.