AStar.md (649B)
1 # A* 2 3 **Source:** Probabilistic Robotics Video 253 4 5 **Definition:** Uses a **heuristic function** (H) that gives a value, used to improve search efficiency. 6 7 --- 8 9 ## Steps 10 11 Assume we are in an unweighted grid world. 12 13 - Define heuristic function 14 - $H(x,y) = \sqrt{(x - x_t)^2 - (y - y_t)^2}$ where $(x_t,y_t)$ are the coordinates of the target 15 - This defines the heuristic function to be the distance from the target. 16 - This heuristic is basically an optimal grid assuming no obstacles 17 - Search the minimal reachable state where our cost function is: 18 - $f = g + h(x,y)$ where the g value is the minimum # of steps to get to the state