A* Algorithm in Artificial Intelligence

Original article was published on Artificial Intelligence on Medium

A* Algorithm in Artificial Intelligence

The environment we face everyday sends us an indefinite amount of information through our senses. It is a problem of cognition to be able to select the relevant information. If we want an artificially intelligent agent it must require the ability to guide itself through and find the relevant information. In A.I this is referred to as a heuristic.

“A heuristic function maps a state onto an estimate of the cost to the goal.”

In formalizing the heuristic search problem we arrive at:

If h(n1)<h(n2)

We guess that it is cheaper to get to the goal from n1 than from n2.

Where:

  • h represents a heuristic
  • We require that h(n)=0 for every node n whose terminal state satisfies the goal.
  • Zero cost of achieving the goal from node that already satisfies the goal

Before we get into A*, let us review a motivating heuristic that inspires A*..

Best First Search

Take a path from Arad to Bucharest by calculating the shortest path between nodes:

Best First Search

We plan our trip by picking cities at each time point that minimize the distance to our goal using euclidean distance.

This path hits the least amount of nodes, however, there is an issue…

…This is not the absolute shortest path from Arad to Bucharest

A * Search

We need to change our search cost of getting to the node and our estimate of the cost of getting to the goal state.

f(n) = g(n) + h(n)

Where:

g(n) — the cost of a path to the node

h(n) — the estimate of the heuristic cost achieving the goal from n

Node — All potential position states

Starting Node — Frontier, are where you start searching, also current node

Goal Node — The target to stop searching.

Search Space — A collection of nodes, like all board positions of a board game

Cost — Value for the path from a node to another node.

**Always expand the node with lowest f-value on the frontier where the f-value is an estimate of the cost of getting to the goal

A* Algorithm

A * shoots toward the goal until the goal is removed from the frontier.

If A* discovers a lower cost path through as it searches through state, it updates the order of that state on the current state, based on the lower path cost.

Properties of A*:

The properties of A* algorithm depend on the condition of the heuristic function.

To achieve optimality (shortest path), completeness (always arrives to the goal state) and a preferable time and space complexity we require conditions to be place on the heuristic function.

To condition A* we have a h*(n) that represents the cost of an optimal path from n to the goal. We want to have our conditioned heuristic function to be such that h(n) ≤ h*(n). Thus it never over estimates the cost to reach the goal.

In such a case A star is complete as it finds a path, it is optimal as it finds the shortest path and has good time and space complexity.

Conclusion

A* algorithm is among the best and most popular path finding algorithms and can be easily modified to approach many search related issues. I hope this tutorial was a fruitful explanation of this algorithm.

Citation:

Heuristic Search Lectures, https://www.teach.cs.toronto.edu//~csc384h/winter/lectures.html