The A* algorithm in Clojure

http://clj-me.cgrand.net/2010/09/04/a-in-clojure/

by limist • 16 years ago

26 4 16 years ago

clj-me.cgrand.net

miguelpais• 16 years ago

As this snippet doesn't really help a lot to know what A* search actually is, here is the explanation from Artificial Intelligence: A Modern Approach (from Russel and Norvig):

The most widely-known form of best-first search is called A-start search (pronounced "A-star search"). It evaluates nodes by combining g(n) - the cost to reach the node, and h(n) - the cost to get from the node to the goal:

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

Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated cost of the cheapest path from n to the goal, we have

  f(n) = estimated cost of the cheapest solution through n*

Thus, if we are trying to find the cheapest solution, a reasonable thing to try first is the node with the lowest value of g(n) + h(n). It turns out that this strategy is more than just reasonable: provided that the heuristic function h(n) satisfies certain conditions, K search is both complete and optimal.

So, for the following graph (tree actually):

  +---A---+
  |       |
  B h:1   E h:4
  |
  C h:2
  |
  D h:3

Where the function g(x) is the depth of the node in the tree, and the heuristic function h(x) is presented next to the node (random values), A-star will search for a solution first in the nodes with smaller values of f(n). So a traversal starting at node A will visit nodes in the following order: {A, B, C, E, D}

  f(B) = h(B) + g(B) = 1 + 1 = 2
  f(C) = 2 + 2 = 4
  f(E) = 4 + 1 = 5
  f(D) = 3 + 3 = 6

If there's anything wrong with my explanation please correct me.

P.S.: I know my heuristic function is probably not admissible.

omnigoat• 16 years ago

And for those wondering when you'd use this algorithm (as even academics don't seem to know!) - it is the go-to algorithm for implementing pathfinding in video games, and robotics.

glenra• 16 years ago

Yup. The algorithm was first used in planning paths for Shakey The Robot back in the late 1960s, which seems like ancient history in computer terms. (I only know of it because my dad "invented" A-star. :-) )

ramanujan• 16 years ago

10 second explanation of A star: you have a graph + matrix of node-node distances. You want to find shortest path from origin to destination. Standard Dijsktra only allows lookahead of one node at a time. A star allows you to incorporate a long range heuristic, like Euclidean distance from current node to destination. This gives a lower bound on current candidate path length and allows you to discard bad paths more rapidly.

Note that in all cases you need some basis for this heuristic (eg lat/lng of each node). Also, while 2D maps/nodes as cities is a great way to build your intuition for the algorithm, you can generalize it to arbitrary node types as long as heuristic function gives a good lower bound.

The A* algorithm in Clojure

Related Stories