Concept
- Heuristic h(q): Estimated length of the path from the node q to the goal node.
- Exact cost g(q): Length of the actual path from the start node to the node q.
- Total cost for node q: f (q) = h(q) + g(q)
Admissible Heuristic
To find an optimal (least-cost) path from start to goal, the heuristic used by A* should be admissible, i.e. it should never overestimate the actual cost of getting to goal node from the current node.
- For a continuous environment (e.g., outdoor feature maps): Euclidean distance, spherical distance, etc.
- For a discrete environment (e.g., indoor occupancy grid maps): Manhattan distance.
Pseudocode
