PRODIGY is a nonlinear AI planner that searches for a sequence of actions that transform an initial state into a final state (goal state). The following sections include some of the basic terminology involved in problem solving with PRODIGY.

The domain specification constitutes of all those legal actions that can be performed by operators and legal inferences that can be made by inference rules. The operators and inference rules have a precondition expression that must be satisfied before they can be applied. The effects list summarizes how the application of the operator brings a change in that relevant world. An operator that has its parameters specified is called an instantiated operator.

The problem solving in PRODIGY is done by means end analysis in which a goal is picked that is not yet true and an attempt is made to find an operator to make it true. The preconditions of this operator become a goal and the process is repeated until all goals are attached to operators or are true.

The problem specification involves the initial state and the goal state that has to be achieved at the end of the plan. The initial state consists of a list of objects and their types with a set of instantiated predicates. The goal specification is an expression that must be satisfied at any goal state.

PRODIGY 's decision cycle includes the following steps.

1. Given a list of pending goals, the system decides which goal to pursue next.

2. Given a goal, it decides which operator it will try to achieve the goal.

3. Given an operator, it decides what variable-bindings it will use to instantiate the operator.

4. Given instantiated operators with no open preconditions and a list of pending goals, it decides whether to apply an operator and hence change the current state or whether to choose a pending goal to solve. When PRODIGY applies an instantiated operator in decision number four above, an action's effected are projected. Although this decision may be backtracked over, a final plan will consist of a sequence of these operator applications. For more information on PRODIGY refer to the PRODIGY manual.