Information Technology Reference
In-Depth Information
It would then be up to the programmer of each individual planning problem to spec-
ify which actions are acceptable for the goal in question and which should be filtered.
If it so happens that absolutely nothing is known about how to plan for the goal, the
clause
acceptable(_,_).
% No filter, so anything goes.
can be included in the problem specification, and the resulting planning behavior is
the same as before.
For the 15-puzzle, imagine that in a current state tiles 1, 2, 3, and 4 are in their
correct positions in the first row, and that the empty space is below tile 2 (in position
6). While it is perfectly legal to move tile 2 down next, experience says that this is
not a good idea: once the first row is in place, it should not be disturbed. A simple
first step toward using this knowledge in planning would be to filter that action in a
program for the 15-puzzle, as follows:
acceptable(down(X),S) :- \+ row1_done(X,S).
row1_done(X,S) :- member(X,[1,2,3,4]), S=[1,2,3,4|_].
This would prevent the program from wasting its time considering plans that disturb
the first row once it is in place.
Decomposing a problem
This idea of not disturbing some parts of a goal that have been solved is a general one.
Many planning problems have the following property: they are made of subproblems
that can be solved
independently
and then combined.
How does this help? Imagine there is a problem that can be solved using twenty-
five moves. Assume there are three legal moves at each state; this means that there
might be
3
25
, or about
10
12
, paths to a goal state.
But suppose that this problem can be broken down into two independent pieces,
A and B, where the A part can be solved in ten steps, and the B part can be solved
in the remaining fifteen steps. To solve A, there might be as many as
3
10
paths, and
to solve B,
3
15
, or about
10
7
, paths
to a goal state. But this is much less than
10
12
paths. Similarly, if the problem can
be broken down into five independent pieces, each requiring five steps (for a total
of twenty-five), there might be only
5
3
10
3
15
paths, so that in total, there might be
(
+
)
3
5
, or about
10
3
, paths. In general, solving
a problem that can be broken down into independent subproblems requires dealing
with the
sum
of their search spaces, not the
product
, an enormous difference.
Many natural problems have this decomposition structure allowing them to be
handled effectively. Consider the 15-puzzle again. The goal of getting all the tiles in
ยท
