Project: 15 Puzzle, $A^{*}$, and Coordinated Motion Planning · Optimal Coordinated Motion Planning with $A^{*}$

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

Let $m$ be the number of free cells. The number of possible configurations is at most \[m(m-1)\dotsm(m-k+1)\le m^{k},\] and every configuration has at most $5^{k}$ candidate moves. This is far too much when $k$ is large!

The $A^{*}$ algorithm searches over the same graph, but assigns every discovered configuration $P$ the priority \[f(P)=g(P)+h(P),\] where $g(P)$ is the number of steps already made and $h(P)$ is a lower bound on the number of remaining steps. The better this lower bound is, the fewer unpromising configurations the algorithm has to process.