Grid Expectations
Consider a uniform grid that extends infinitely in all directions, as in the earlier exercise about pruning.
We start out at the grid point marked S. Assume the goal is far away and not shown in the figures.
In the grid on the left, each state has four child states (movement on the grid is limited to up, down, left, and right). In the one on the right, each state has eight children (diagonal moves are allowed).
n this problem, we will consider uniform-cost search in this domain. Assume that the cost of traversing a path is the Euclidean distance of the path, and that the distance between points in the vertical and horizontal directions is 1 meter.
Searching
Answer the following questions about uniform-cost search without dynamic programming in the eight-action grid (the grid on the right). Enter your answers as decimal numbers accurate to within 10^{-1}
Heuristics
The "Manhattan distance" between two states (x_0,y_0) and (x_1,y_1) on the grid is defined as:
Assume that we are using A* search and we use this distance an a heuristic.