PRODIGY4.0 creates a plan for its unsolved goals by selecting operators whose effects achieve those goals. It continues adding operators to the incomplete plan until a solution to the problem is found. In Figure 4 we show a simple incomplete plan.
Figure 4: Representation of a plan. G is the top-level
goal, and Op1 is the operator that achieves it. G1 and G2 are two
preconditions of Op1 that are not true in the current state, and are
achieved by O1 and O2 respectively.
The plan is built by a backward-chaining algorithm, which starts from the list of goals, G, and adds operators, one by one, to achieve its pending goals, i.e., to achieve preconditions of other operators that are not satisfied in the current state.
When all the preconditions of an operator are satisfied in the current state, PRODIGY4.0 simulates the effects of the action by applying the operator. Each time an operator is applied, the current state is updated with the effects of the action. PRODIGY4.0 terminates planning when each of the goals are true in the state.
The planning cycle involves several decision points, including which goal to select from the set of pending goals, and which applicable operator to apply. Table 2 shows the decisions made while creating the plans. Back-Chainer shows the decisions made while back-chaining on the plan, Operator-Application shows how an operator is applied, and Prodigy4.0 shows the top-level procedure.
Table 2: PRODIGY4.0 decision points, adapted from [Veloso et al.
1995].
Planning involves specifying a task model including operators, search control rules and domain description.