Information Technology Reference
In-Depth Information
9.2 Generating plans
To solve a planning problem using Prolog, the general idea is this:
Represent the initial state, the goal state(s), and the operators of the problem.
The Prolog program will then find a way of getting from the initial state to a goal
state using those operators.
How will it do this? By
thinking
about the problem, of course! The thoughts will be
like this:
If I am in state
S
andIdomove
M
, that will take me to state
S
.
From
S
if I now do move
M
,
that will take me to
S
. ...
The programmer tells Prolog where to start (that is, the initial state) and where it
should end (the goal state). Along the way, the program will need to keep track of all
the moves it is considering and assemble them into a working plan at the end.
9.2.1 A general planning program
A plan is a sequence of moves from an initial state to a goal state. So the main thing in
planning is knowing how to go from one state
S
1
to another state
S
2
using a sequence
of legal moves
L
. (Bigger planning problems will present much more to think about.)
The state
S
2
is said to be
reachable
from
S
1
using
L
, which is written this way:
L
−→
S
2
There are only two principles to know about this reachability:
S
is reachable from
S
(trivially) using no moves:
S
S
1
−→
S
.
If there is a legal move
M
0
that goes from state
S
1
to state
S
2
, and
S
3
is reachable
from
S
2
using moves
M
1
,
...
,
M
n
, then
S
3
is also reachable from
S
1
using moves
M
0
,
M
1
,
...
,
M
n
. This is represented as follows:
and
S
2
M
1
,
...
,
M
n
then
S
1
M
0
,
M
1
,
...
,
M
n
If
S
1
M
0
−→
→
→
→
→
S
2
...
S
3
,
...
S
3
A planner can be defined in Prolog by encoding these two reachability principles
directly, as shown in figure 9.3. To solve a planning problem, the
plan
predicate is
used to generate a list of moves
L
such that a goal state
G
is reachable from the initial
state
I
using
L
.
