Friday, June 26, 2009

A* / HPA* links and scribblings shared

There just was a question on the AiGameDev forums asking about A* (Astar), I remembered I had my own old links and scribblings somewhere so I shared them, so here they are if anybody needs them:

A* / HPA* links, references, implementation considerations:
http://docs.google.com/View?id=dcm3hb4r_30mjc2cj4j

A* basic theory scribblings:
http://jadnohra.net/release/AStar_Basic_Theory.pdf


If you have been following the blog you will see that I recently got into Reinforcement Learning and Dynamic Programming (see previous post), this gave me a much better overview about the 'essence' A* is and how it came to be, really just a case of applying dynamic programming.

The essence:
"Principle of Optimality: An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision." (written in 1957 by Bellman, a genius)

.

1 comment:

Scott Edwards said...

Hi this stuff is so interesting. Not sure i understand the Principle of Optimality though. Any suggestions on how to more fully grok it?