Information Technology Reference
In-Depth Information
Of course, for this to work, the programmer must be able to estimate how far a
state is from a goal. The estimate does not have to be exact, since it is just a guide to
what state should be explored next.
In the case of the 15-puzzle, there is a natural estimate of how far a state is from
the goal. In the initial state in figure 9.10, tiles 1 and 3 are in their correct position,
but tile 6 has to be moved down one position. Tile 4 has to go up two and right one.
The horizontal or vertical distance is known as a
Manhattan distance
(by analogy with
the grid of streets in Manhattan). So tile 1 has a Manhattan distance of 0 from its
home, tile 6 has a Manhattan distance of 1 from its home, and tile 4 has a Manhattan
distance of 2
3 from its home. In general, one can estimate how far a state is
from the goal by summing the Manhattan distances of every tile from its home. So
the goal state in figure 9.10 has a distance of 0 from the goal (since every tile is at its
home), and the initial state in figure 9.10 has a distance of
+
=
1
+
+
+
+
+
+
+
+
+
+
+
+
+
+
=
17
from the goal. Note that this estimate has the nice property that it is a
lower bound
on
the number of moves required to get to a goal state: at the very least, each tile has
to do that number of horizontal or vertical moves to get it to its home. The actual
number of moves to get to a goal state will typically be much larger, since the tiles get
in each other's way.
0
1
0
1
2
1
0
3
1
2
3
1
0
1
1
9.4 Scaling up: The representation problem
For planning problems like the three small puzzles considered up to now, the method
of representing a state worked just fine. A state was represented as a list whose
elements were the various aspects of the problem, such as the visible side of a coin,
the location of the monkey, or the position of a tile in a rectangular frame. But for
more realistic domains, it becomes very awkward to deal with lists that include
all
the relevant aspects of that domain.
For example, imagine a world with 1,000 boxes that can be moved independently.
Representing this state requires a list like
. Then 1,000
clauses would be needed to describe the
legal_move
predicate, one for each box
in the list. The clause would change the location of that box and leave the values of
all the others unchanged, using 999 Prolog variables.
This is not just a problem with locations. In general, even in domains with many
aspects, each action will change only a few of them. Pushing a box under the bananas
will change the location of the monkey and the box, but it will
not
affect the location
[
loc
1
,
loc
2
,
loc
3
,
...
,
loc
1000
]
