Information Technology Reference
In-Depth Information
In the search for a path from an initial state to a goal state, only the moves that are
legal in each state need to be considered. Nonetheless it is not hard to see that the
number of paths is
exponential
in the length of the path.
For example, consider the 15-puzzle. Suppose there are exactly three legal moves
possible from any state. (Some states have four legal moves, and when the empty
space is in a corner, there are only two legal moves.) This means that from a starting
state there are three paths that have just one move; from each of these final states
(not necessarily distinct), there are three new states, meaning there are nine paths
that contain two moves; similarly, there are twenty-seven paths with three moves. In
general, there are
3
n
paths with
n
moves.
This means that to find a path with twenty moves in the 15-puzzle, there might be
as many as
10
9
paths. This is perhaps manageable, but twenty moves are not very
many. For thirty moves, there might be
10
14
paths, and for forty moves, as many as
10
19
paths. Even with something as simple as the 15-puzzle, finding a plan with one
hundred moves will be well outside the reach of a simple planner.
This is similar to the exponential growth that occurred in solving constraint satis-
faction problems (see section 5.2.3). As with constraint satisfaction problems, to deal
with this issue, the planning must be more sophisticated.
9.3.1 Knowledge-based planning
For many planning problems, thinking (that is, using what is known about the prob-
lem) focuses on those actions that actively contribute to achieving a goal. To get to
a grocery store to buy food, for example, one would usually not spend any time
contemplating actions like packing a suitcase. It might be perfectly legal to pack a
suitcase on a Saturday morning, but we have knowledge from experience that this
legal action is not part of an effective plan to achieve the grocery store goal.
Considerations like these suggest that planning should go beyond merely looking
for a sequence of legal moves from a start to a goal state. Perhaps the simplest way
to accommodate more knowledge into the process is to assume that each planning
problem will come with an additional predicate
acceptable(
a
,
s
)
that tells the gen-
eral planner when a legal action
a
should be considered in a state
s
as part of a plan
to achieve the current goal. Instead of
reachable(S1,[M|L],S3) :- legal_move(S1,M,S2), reachable(S2,L,S3).
the general planner would now say
reachable(S1,[M|L],S3) :-
legal_move(S1,M,S2), acceptable(M,S1), reachable(S2,L,S3).
