AI : A-Star (A*) Search Algorithm in Java

Search algorithms are used in artificial intelligence (AI) to find the best solution to a problem. They work by exploring a set of possible solutions, also known as a search space.

Below are the types of search algorithms uses in AI

We are going to explore the A* search algorithm in this article.

Informed search algorithms in AI are equipped with information about the goal state. This information is used by a function to estimate the proximity of a state to its goal within the system. Informed search is more efficient and accurate. It is less lengthy while implemented and the speed of finding solutions is quick.

The A* algorithm was created in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael. The A* algorithm works by maintaining two sets of nodes: the open set and the closed set. The open set contains nodes that have been discovered but not yet explored. The closed set contains nodes that have already been explored.

The cost of a node is calculated as the sum of the cost of moving from the starting node to the node and the estimated cost of moving from the node to the goal node. The estimated cost is calculated using a heuristic function. The heuristic function is a function that estimates the cost of moving from a node to the goal node. The heuristic function must be admissible, which means that it must never overestimate the cost of moving from a node to the goal node.

The A* algorithm is guaranteed to find the shortest path between the starting node and the goal node if the heuristic function is admissible. However, the algorithm is not guaranteed to be efficient. The efficiency of the algorithm depends on the quality of the heuristic function.

There are generally three approximation heuristic function.

1. Manhattan Distance : It is nothing but the sum of absolute values of differences in the goal’s x and y coordinates and the current cell’s x and y coordinates respectively. When we are only allowed to move only in four directions only (right, left, top, bottom), we can use this function.
2. Diagonal Distance : It is nothing but the maximum of absolute values of differences in the goal’s x and y coordinates and the current cell’s x and y coordinates respectively. When we are allowed to move in eight directions only (similar to a move of a King in Chess), we can use this function.
3. Euclidean Distance : When we are allowed to move in any directions we can use this function which is nothing but the distance between the current cell and the goal cell using the distance formula.

Let’s try to understand this algorithm though a intelligent robot agent. This robot can move up, down, left and right. This robot needs to move to destination through the shortest path. The floor has impassable walls which the robot needs to ignore.

Below is the A* algorithm written in Java.

private void AStar() {

  Position selfPosition = env.getRobotPosition(this);
  Position targetPosition = env.getTarget();

  // if starting and end position is the same - meaning target is reached
  if (selfPosition.equals(targetPosition)) {
   foundActions.add(Action.DO_NOTHING);
  }

  // Open list containing the nodes which are not explored
  PriorityQueue<Node> openList = new PriorityQueue<>();

  // creating the node from the starting position , 
  //converting the starting position to the node, 
  //cost is 0 because we are starting here - no direction
  Node start = new Node(selfPosition, 0, "");

 //Adding the start node, pick up the first node at the top of the priority
  // queue
  openList.add(start);

  // store the nodes which are explored.
  Map<Position, Integer> closeList = new HashMap<>();

  // starting node is already visited so put in the bucket of nodes
  // already visited
  cameFrom.put(start, null);

  // the cost of the starting node is 0
  closeList.put(selfPosition, 0);

 //while more nodes to be visited meaning the open bucket has more
  // more nodes to be visited
  while (!openList.isEmpty()) {
  // pick up the top node to be explored (where the priority is smaller
  // - meaning the path cost is smaller)
  Node current = openList.poll();

  //if the current node that we just explored the target then we are done
  if (current.getPosition().equals(targetPosition)) {
   reconstructPath(current); // find the path
   break;
  }

  // get the neighboring positions of the current position
  Map<String, Position> neighboringPositions = 
        env.getNeighborPositions(current.getPosition());
  // traverse through the neighboring four positions
for(Map.Entry<String, Position> entry : neighboringPositions.entrySet()) {

   // Calculating the cost for the path from the starting point to
   // the current positions's neighbor node
   // step cost is 1
   int new_cost = closeList.get(current.getPosition()) + 1; 

   // extract the position object
   Position nextPosition = entry.getValue();

// position picked up is not boundary and the position is not impassable
  // and the position was never visited
   if (nextPosition != null && 
    env.getPositionTile(nextPosition).getStatus() != TileStatus.IMPASSABLE
     && closeList.containsKey(nextPosition) == false) {

    // put the position in the visited bucket
    closeList.put(nextPosition, new_cost);
   // calculating the total cost which is f(n) = g(n) + h(n).
   int priority = new_cost + manhattan_distance_heuristic(nextPosition,
       targetPosition);
 //create the node object which would contain new neighboring position
 //the total cost, and the direction involved
   Node neighborNode = new Node(nextPosition, priority, entry.getKey());
 //add the node object to frontier bucket it sit in the priorityqueue
   openList.add(neighborNode);
 //so add that node into the visited nodes bucket to track the direction
   cameFrom.put(neighborNode, current);

     }

    }
  }

 }

AStar Search Algorithm 1

AStar Search Algorithm 2

AStar Search Algorithm 3

AStar Search Algorithm 4

AStar Search Algorithm 5

For the complete source code, check out the repository on GitHub.