-
Notifications
You must be signed in to change notification settings - Fork 3
Example: Creating An State Space Search Problem For A*
This is an example of creating a state space search problem that will be used by the A* search framework. There are two main steps, create a class that represents the problem(which is a search node in the state space) and a heuristic function used while searching.
For this example we will use the problem of navigating a maze. Given a maze layout, a start point, and an endpoint find the optimal path from the start to the end. The maze layout will be represented by a two dimensional integer array, where 0s are walls and 1s are pathways. The start and endpoints will be represented by two integers, one to represent the row and the second to represent the column.
Here is an example maze and start/end points:
int[][] maze = {
{1, 0, 0, 1, 0, 1},
{1 ,0, 1, 1, 0, 1},
{1, 0, 1, 0, 0, 1},
{1, 0, 1, 0, 0, 1},
{1, 1, 1, 1, 1, 1}};
int startRow = 0; // Top Left
int startCol = 0;
int goalRow = 0; // Top Right
int goalCol = 5;All problems must be represented by class that extends AbstractAStarNode. Here is the boilerplate for the Maze class:
public class Maze extends AbstractAStarNode<int[]> {
@Override
public List<AbstractAStarNode> getSuccessors() {
return null;
}
@Override
public double distFromParent() {
return 0;
}
@Override
public int hashCode() {
return 0;
}
@Override
public boolean equals(Object otherMaze) {
return false;
}
}Next, each state/node must be represented by the current position in the maze. The state in this problem will be the current row position and the current column position. Although the maze layout doesn't change(only the position in the maze changes) each node will need access to the maze layout. We will have the Maze class take all three of these items in a constructor and the constructor will call setState() giving it the current position as an array. Also we will create a secondary constructor taking in the three parameters discussed above along with a parent node to help make the getSuccessors() methods cleaner. Another small addition we will make is we will store the number of rows in the maze and the number of columns as well as create getters for them.
private int currentRow;
private int currentCol;
private int[][] maze;
private int numberOfRows;
private int numberOfCols;
public Maze(int[][] maze, int currentRow, int currentCol) {
this.maze = maze;
this.currentRow = currentRow;
this.currentCol = currentCol;
this.setState(new int[]{currentRow, currentCol});
this.numberOfRows = maze.length;
this.numberOfCols = maze[0].length; // Assuming No Jagged Arrays
}
public Maze(int[][] maze, int currentRow, int currentCol, Maze parentMaze) {
this(maze, currentRow, currentCol);
this.setParent(parentMaze);
}
public int[][] getMaze() {
return this.maze;
}
public int getNumberOfRows() {
return this.numberOfRows;
}
public int getNumberOfCols() {
return this.numberOfCols;
}Next we will implement the getSuccessors() method which returns a list of the next possible states/nodes. Due to the discrete nature of the mazes we are using there are only four directions you can attempt to move in: up, down, left, and right. We will attempt to move each direction and if it is possible to move that direction we will create a new Maze whose parent will be the current and its state will be the row and column after moving. All we check is that we do not move into a wall and that we are still inside the maze(we don't get an arrays out of bounds).
@Override
public List<AbstractAStarNode> getSuccessors() {
List<AbstractAStarNode> possibleMoves = new ArrayList<>();
// Move Up
if(this.currentRow - 1 >= 0 && this.maze[this.currentRow - 1][this.currentCol] != 0)
possibleMoves.add(new Maze(this.maze, this.currentRow - 1, this.currentCol, this));
// Move Down
if(this.currentRow + 1 < numberOfRows && this.maze[this.currentRow + 1][this.currentCol] != 0)
possibleMoves.add(new Maze(this.maze, this.currentRow + 1, this.currentCol, this));
// Move Left
if(this.currentCol - 1 >= 0 && this.maze[this.currentRow][this.currentCol - 1] != 0)
possibleMoves.add(new Maze(this.maze, this.currentRow, this.currentCol -1, this))
//Move Right
if(this.currentCol + 1 < numberOfCols && this.maze[this.currentRow][this.currentCol + 1] != 0)
possibleMoves.add(new Maze(this.maze, this.currentRow, this.currentCol + 1, this));
return possibleMoves;
}The distFromParent() method represents how far away a node is from its parent node. In the context of Maze, going from a node to its parent only took one step, so there will always be a distance of 1 from a node to its parent.
@Override
public double distFromParent() {
return 1;
}Finally, we need to implement hashCode() and equals()(note: hashCode and equals must be consistent with one another). In the A* framework both of these methods need to be based off a node's state and ignore all values such as f, g, and h. Since our state is an integer array we are just going to use methods from the Arrays package to generate hash codes and compare states.
@Override
public int hashCode() {
return Arrays.hashCode(getState());
}
@Override
public boolean equals(Object otherMaze) {
if(otherMaze instanceof Maze) {
return Arrays.equals(((Maze) otherMaze).getState(), this.getState());
}
return false;
}A heuristic function is a function that estimates how far away a state/node is from the goal state/node. Heuristic functions must be admissible, meaning they must underestimate or estimate the exact distance from the goal(NEVER overestimate). To create a heuristic function it is common to relax the rules of the problem being addressed. In Maze we will relax the problem by ignoring walls, to get to the goal we will just walk the horizontal distance and then the vertical distance to reach the goal. This is often referred to as Manhattan or City Block distance. The value of the heuristic function will simply be the absolute value of the differences of rows plus the absolute difference of columns.
In the A* framework a heuristic function must implement IHeuristicFunction. Here is the complete code for our problem.
public class NavigationManhattanDist implements IHeuristicFunction {
private Maze goalNode;
public NavigationManhattanDist(Maze goalNode) {
this.goalNode = goalNode;
}
@Override
public double calculateHeuristic(AbstractAStarNode searchNode) {
int diffOfCols = Math.abs(this.goalNode.getState()[0] - ((Maze) searchNode).getState()[0]);
int diffOfRows = Math.abs(this.goalNode.getState()[1] - ((Maze) searchNode).getState()[1]);
return diffOfCols + diffOfRows;
}
}After you are done creating your classes, it is time to use them.
Here is solving a maze using normal A* search(we could easily change to IDA* by changing AStarSearch to IDAStarSearch):
int[][] maze = {
{1, 0, 0, 0, 1},
{1 ,0, 1, 0, 1},
{1, 0, 1, 0, 1},
{1, 0, 1, 0, 1},
{1, 1, 1, 1, 1}};
int startRow = 0;
int startCol = 0;
int goalRow = 0;
int goalCol = 4;
Maze initial = new Maze(maze, startRow, startCol);
Maze goal = new Maze(maze, goalRow, goalCol);
IHeuristicFunction heuristicFunction = new NavigationManhattanDist(goal);
IDAStarSearch searcher = new IDAStarSearch(initial, goal, heuristicFunction);
AbstractAStarNode finalSearchNode = searcher.search();
System.out.println("Initial State");
System.out.println(initial);
System.out.println("Goal State");
System.out.println(goal);
List<AbstractAStarNode> path = searcher.getPath(finalSearchNode);
int step = 1;
for (AbstractAStarNode node : path) {
System.out.println("Step " + step);
System.out.println(node + "\n");
step++;
}We can use the Maze class to address a new problem easily. The new problem will be navigating terrain, which is very similar to navigating a maze. In terrain navigation we add in the concept that certain terrains are harder to move through than others. For instance, instead of walking down a path you might need to swim which is a harder task than walking. Or maybe walking up hill takes more effort than walking on flat land. To change the problem we simply allow the array that represents the maze to contain values besides 0s and 1s. We will still define 0s as being obstacles that block a path, but now valid paths are weighted by value in the maze. For instance a path with 1 is easier to navigate through than a path with a value of 2.
Now instead of finding the shortest path, it will find the path that results in the smallest sum of values in the terrain array. The represents the least difficult path to traverse.
We begin by extending Maze. Then, we create constructors that will simply call Maze's constructors. next we override getSuccessors(), most the code will be 100% the same as Maze.getSuccessors() but we must make it create NavigateTerrain objects instead of Maze. Also we now must use super to access the maze(terrain data) and position data. Finally, the step that makes the biggest difference, we must override distFromParent(). Since we want the values in the terrain array to represent how hard it is to navigate, we use the values in the terrain array as the distance from the parent state/node.
Here is the complete code:
public class NavigateTerrain extends Maze {
public NavigateTerrain(int[][] terrain, int currentRow, int currentCol) {
super(terrain, currentRow, currentCol);
}
public NavigateTerrain(int[][] terrain, int currentRow, int currentCol, NavigateTerrain parentMaze) {
super(terrain, currentRow, currentCol, parentMaze);
}
@Override
public double distFromParent() {
return super.getMaze()[this.getState()[0]][this.getState()[1]];
}
@Override
public List<AbstractAStarNode> getSuccessors() {
List<AbstractAStarNode> possibleMoves = new ArrayList<>();
// Move Up
if(this.getState()[0] - 1 >= 0 && super.getMaze()[this.getState()[0] - 1][this.getState()[1]] != 0)
possibleMoves.add(new NavigateTerrain(super.getMaze(), this.getState()[0] - 1, this.getState()[1], this));
// Move Down
if(this.getState()[0] + 1 < super.getNumberOfRows() && super.getMaze()[this.getState()[0] + 1][this.getState()[1]] != 0)
possibleMoves.add(new NavigateTerrain(super.getMaze(), this.getState()[0] + 1, this.getState()[1], this));
// Move Left
if(this.getState()[1] - 1 >= 0 && super.getMaze()[this.getState()[0]][this.getState()[1] - 1] != 0)
possibleMoves.add(new NavigateTerrain(super.getMaze(), this.getState()[0], this.getState()[1] - 1, this));
//Move Right
if(this.getState()[1] + 1 < super.getNumberOfCols() && super.getMaze()[this.getState()[0]][this.getState()[1] + 1] != 0)
possibleMoves.add(new NavigateTerrain(super.getMaze(), this.getState()[0], this.getState()[1] + 1, this));
return possibleMoves;
}
}Now we can use this class to navigate terrain.
In the example below we introduce "water" by assigning it a value of 4. If we simply wanted the shortest path we could swim across the top row to get to the goal; however, if we want the path easiest to travel we walk around the water.
// 0 = Wall
// 1 = Path
// 4 = Water
int[][] terrain = {
{1, 4, 4, 4, 4, 4, 4, 4, 4, 1},
{1, 0, 4, 4, 4, 4, 4, 4, 0, 1},
{1, 0, 4, 4, 4, 4, 4, 4, 0, 1},
{1, 0, 4, 4, 4, 4, 4, 4, 0, 1},
{1, 0, 4, 4, 4, 4, 4, 4, 0, 1},
{1, 0, 4, 4, 4, 4, 4, 4, 0, 1},
{1, 0, 4, 4, 4, 4, 4, 4, 0, 1},
{1, 0, 0, 0, 0, 0, 0, 0, 0, 1},
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
};
int startRow = 0;
int startCol = 0;
int goalRow = 0;
int goalCol = 9;
NavigateTerrain initial = new NavigateTerrain(terrain, startRow, startCol);
NavigateTerrain goal = new NavigateTerrain(terrain, goalRow, goalCol);
IHeuristicFunction heuristicFunction = new NavigationManhattanDist(goal);
IDAStarSearch searcher = new IDAStarSearch(initial, goal, heuristicFunction);
AbstractAStarNode finalSearchNode = searcher.search();
System.out.println("Initial State");
System.out.println(initial);
System.out.println("Goal State");
System.out.println(goal);
List<AbstractAStarNode> path = searcher.getPath(finalSearchNode);
int step = 1;
for (AbstractAStarNode node : path) {
System.out.println("Step " + step);
System.out.println(node + "\n");
step++;
}Here are links to gists of the files created in this write up:
If you have any questions feel free to contact me!