Description of the PRODIGY Architecture

PRODIGY is a system designed for unifying problem solving, planning and multiple learning methods in an integrated architecture. The PRODIGY architecture takes the form of a general problem solver to which six learning modules are tightly coupled. The PRODIGY architecture is best represented graphically: Click here to see a representation of the PRODIGY modules. The discussion here is based primarily on the architectural design of the problem solver and the learning modules are described individually elsewhere in this document.

The problem solver is a search engine that searches over a problem space defined by the current domain and operators. As it searches, it makes a problem-solving trace, incorporating each step of the search (including paths that were later dropped) and its own reasoning at the time about the current state of the search. This trace can be used by the learning modules.

In the absence of control rules, the search defaults to depth-first, means-end analysis. Nodes in the problem space are defined as the set of goals and the state of the world, both expressed in first-order predicate logic. The search proceeds through the problem space until a node is found that satisfies the top-level goal, using the following algorithm:

Decision Phase.
- Determine node to expand next (by either control rules or DFS).
- Determine new goal from this node.
- Select operator to achieve goal.
- Bind operator parameters.
Expansion Phase
- If operator can be applied, apply it.
- Otherwise, subgoal on unmatched preconditions.

Control Rules

Control rules are are used for the following three purposes:

improving the search efficiency;
improving the solution quality; and/or
directing the problem solver along normally-unexplored paths.

For search, PRODIGY assumes that search will be guided by explicit control knowledge for important decisions. This assumption is called the casual commitment strategy and implies that the problem solver will not attempt sophisticated behavior in the absence of sophisticated control knowledge.

Control rules are divided into a left-hand side which conditionally matches variables against the current state axioms and a right-hand side action which indicates whether to SELECT, REJECT or PREFER a particular candidate rule. A control decision is made based on these indications and a new candidate node is determined.

To return, press HOME. To go to the next document, press NEXT.