A* Search

Implementing single-pair shortest path search.¹

Learning Goals

• Apply the graph solver design pattern.

  Graph algorithms are typically implemented as separate graph solver classes. This allows the graph solver to maintain its own state (such as distTo and edgeTo maps) without interfering with or modifying the graph data. In this assignment, we act as a client of a graph data type by using the AStarGraph API to solve any problem that can be reduced to A* search.

• Debug a graph algorithm involving multiple data structures.

  A* search relies on maintaining a priority queue and multiple maps to determine which vertex to visit next. Implementing and, moreover, debugging this algorithm gives us experience working with more complex systems that have multiple interacting components, each of which maintain a small slice of information about the overall computational process.

Table of contents

1. Overview
2. Getting the Assignment
3. AStarGraph
4. Memory-Optimizing A* Search
5. AStarPathFinder
   1. Testing
6. Puzzles
7. Submission

Overview

This assignment focuses writing your own implementation of the A* algorithm. We’ll use this later to do the routing in HuskyMaps, and again to intelligently shrink images in the last homework assignment.

Before you begin the assignment, you might find these resources helpful in addition to the lecture slides. Make sure to properly cite any third-party code that you end up incorporating into your submission:

• A* Insertion Demo Slides
• Josh Hug’s Shortest Paths lecture recording
• Pathfinding Algorithms Visual Comparison (build a complex maze and compare Dijkstra vs A*!)

Getting the Assignment

Task

Pull the skeleton repository to get the astar assignment.

If IntelliJ doesn’t properly recognize the new files or complains about failing to resolve ExtrinsicMinPQ, refresh Gradle manually through the Gradle tool window (on the right by default):

AStarGraph

Background

Read through the graph interface that you will be working with.

Problems to be solved by your algorithm will be provided in the form of a graph. More specifically, they will be given as a class that implements the AStarGraph interface, which is an API for the single-pair shortest path problem.

The interface has only two methods:

Notably, this simple interface lacks any methods for enumerating all vertices; but surprisingly, it captures a huge swath of real-world problems, including various puzzles that we’ll explore in this homework, as well as the route navigation directions for HuskyMaps.

Memory-Optimizing A* Search

Task

Understand the memory optimization described.

Recall that the A* algorithm requires that we start with a priority queue that contains every possible vertex. In practice, this seemingly innocuous requirement can be difficult to achieve due to the memory limits of real computers. For even a simple problem, like the 15 puzzle, there are trillions of possible configurations—far more than we could ever fit into a regular computer’s memory. (For reference, 1 gigabyte is only 1 billion bytes; you’d need tens of terabytes just to store all these configurations.)

To save memory, we will implement a different version of A* search with one fundamental difference. Instead of starting with all vertices in the priority queue, we’ll start with only the start vertex in the priority queue.

This necessitates that we also change our relaxation operation. In the version from lecture, a successful relaxation operation updated the priority of the target vertex, but never added anything new. Now that the priority queue starts off mostly empty, a successful relaxation must add the target vertex if it is not already in the priority queue.

Explore the Memory Optimizing A* Demo² below to see the algorithm in action.

Or compared side-by-side in A* vs. Memory Optimized A* Demo³. This example is also run on a more interesting graph than the earlier example.

Even with this optimization, some A* problems are so hard that they can take billions of years and terabytes of memory to solve. If the algorithm takes longer than some timeout value to find the goal vertex, the algorithm should stop running and report that a solution was unable to be found.

AStarPathFinder

Task

Implement an AStarPathFinder class that implements the ShortestPathFinder interface with the above optimization.

Tips

• An example solver is given in the LazySolver class. This solver simply tries the first edge it sees, and if that edge doesn’t lead to the solution, it (incorrectly) claims that the puzzle is unsolvable.
  • This is a good place to look for examples of how to handle the timeout and how to construct ShortestPathResult objects.
  • As with other reference code, do not blindly copy and paste code! This is likely only going to make you miserable later when you try to debug something that you didn’t write yourself and don’t understand.
• Since AStarGraph<Vertex> uses a generic type for vertices, the input graph’s vertices may be a reference type. Thus, make sure to use the equals method whenever you want to compare two vertices for equality.
• You’ll need to use an ExtrinsicMinPQ; for this assignment, you have access to two:
  1. Your heap from HW4: if you want to use this, you’ll need to go back and change it to support any generic types by changing the generic type declaration in the class from <T extends Comparable<T>> to simply <T> and changing any TreeMaps you used into HashMaps. (If IntelliJ doesn’t let you import the heap, try reimporting the Gradle project)
  2. The new priorityqueues.DoubleMapMinPQ provided with this assignment. While DoubleMapMinPQ is slower and more memory-hungry than ArrayHeapMinPQ, its operations still take $\mathcal{O}(\log N)$ time, which is good enough for this assignment.

Testing

Recommended

Run our unit tests and read about our randomized tests.

We’ve provided all the unit tests we’ll use during grading, but much of the grading will also be based on additional randomized tests that you won’t have access to.

First, for your convenience, here are diagrams of some of the graphs used in the unit tests:

Unfortunately, if you find yourself passing our unit tests, but failing some randomized tests on the grader, your best course of action will be to carefully review your code until you figure out where your code deviates from the A* algorithm.

Some of our randomized tests will also check your code’s runtime; one will time your code on random WeightedDirectedGraphs with many vertices and edges (so the shortest paths end up being only several edges in length), whereas another will test your runtime with very long paths. Again, if you fail these tests, make sure that you’re following the A* pseudocode correctly.

As always, if you find yourself debugging for over an hour, definitely post on Piazza or come to drop-in times for assistance—we’re here to help you learn, and struggling on your own through multiple hours of debugging is not an efficient way to learn. (Additionally, by bringing our attention to bugs that our unit tests don’t catch, you help us write better tests for future quarters.)

Puzzles

Optional

Run our puzzle solvers that use your AStarPathFinder to solve puzzles.

Included in the assignment code are some example applications that use your code to solve non-trivial puzzles; these are provided mostly for fun, but you can also use them as an informal benchmark or stress test for your code.

Word Ladder

In a word ladder puzzle, we try to convert one word in English to another by either changing, adding, or removing individual letters such that every transition results in a valid English word. Suppose we start with the word “horse” and we want to turn it into “nurse”.

Total states explored in 0.874s: 190
Search was successful.
Solution was of length 9, and had total weight 8.0:
horse->hose->hole->cole->core->cure->pure->purse->nurse

Obviously, the time taken will vary based on your computer, but the number of states explored and even the final solution may vary based on how your priority queue breaks ties. The only thing guaranteed to be consistent between different A* implementations is the total weight of the solution found (although for the provided puzzles, all edges have weights of 1, which means that the solution length (number of vertices) will also be consistent).

Sliding Puzzle

The 15 puzzle is a puzzle invented and popularized by Noyes Palmer Chapman in the 1870’s. The original version is played on a 4-by-4 grid with 15 square tiles labeled 1 through 15 and a blank square, though there are also 2-by-2 and 3-by-3 variants. The goal of this puzzle is to rearrange the tiles so that they are in order using as few moves as possible. The player is permitted to slide tiles horizontally or vertically into the blank square.

As an example of a solution, the following shows a sequence of legal moves from an initial board (left) to the goal board (right) on the 3-by-3 version.

   1  3        1     3        1  2  3        1  2  3        1  2  3
4  2  5   =>   4  2  5   =>   4     5   =>   4  5      =>   4  5  6
7  8  6        7  8  6        7  8  6        7  8  6        7  8

initial        1 left          2 up          5 left          goal

This is also just a graph, where each vertex—a possible state of the board—has up to 4 neighbors corresponding to sliding the left, top, right, or bottom neighbor of the blank into the blank. As with word ladders, every edge has weight equal to 1.

We’ve provided 11 example puzzles with the assignment, each specified by a text file in the astar/data subdirectory. (We use 0 to represent the blank tile.) The puzzles are ranked by difficulty, and their files also include their expected solution length, and most files include the number of states explored by a staff solution with and without the heuristic (A* with Manhattan distance heuristic, versus just Dijkstra’s algorithm).

Again, based on the tie-breaking in your priority queue, you will likely see different values for the numbers of states explored, but your solution weights and lengths should match the ones given in the puzzle files.

Note that hard- and elite-difficulty puzzles may time out on your computer with the default timeouts, so you may need to adjust the timeout to see results. We expect the basic puzzles to take under a second to run, and the hard puzzles may take up to a minute; the elite puzzles are truly difficult to solve, though, and may take several minutes or longer to solve—if the program doesn’t exceed Java’s default memory limit first, that is.

If you find that your code is many times slower than expected on the basic or hard puzzles, it’s likely that your code will be too slow to run correctly on the autograder for this assignment (and future assignments); so you might want to review your code to check for any implementation errors or inefficiencies.

Submission

Commit and push your changes to GitLab before submitting your homework to Gradescope.