Before describing our implementation of propose-and-revise, we briefly present EXPECT's approach to representing knowledge. We will concentrate on presenting background that is directly relevant to the work presented here. More details about the architecture and knowledge acquisition tools can be found in [Gil, 1994, Swartout and Gil, 1995, Gil and Paris, 1994].
In EXPECT, both factual knowledge and problem-solving knowledge about a task are represented explicitly. This means that the system can access and reason about the representations of factual and problem-solving knowledge and about their interactions. Factual knowledge is represented in LOOM [MacGregor, 1991, MacGregor, 1988], a state-of-the-art knowledge representation system based on description logic. Every concept or class can have a definition that intensionally describes the set of objects that belong to that class. Concept descriptions can include type and number restrictions of the fillers for relations to other concepts. Relations can also have definitions. LOOM uses the definitions to produce a subsumption hierarchy that organizes all the concepts according to their class/subclass relationship. Factual knowledge includes the concept base, the instance base, and the relations among them.
Problem-solving knowledge is represented in a procedural-style language that is tightly integrated with the LOOM representations. Subgoals that arise during problem solving are solved by methods. Each method description specifies: 1) the goal that the method can achieve, 2) the type of result that the method returns, and 3) the method body containing the procedure that must be followed in order to achieve the method's goal. A method body can contain nested expressions, including subgoal expressions that need to be resolved by other methods; control expressions such as conditional statements and some forms of iteration; and relational expressions to retrieve the fillers of a relation over a concept. Some method bodies are calls to Lisp functions that are executed without further subgoaling.
We will give examples of EXPECT's representations using propose-and-revise as a strategy for solving the following type of problems in the U-Haul domain: Given the total volume that the client needs to move, the system recommends which piece of equipment (e.g., a truck, a trailer, etc.) the client should rent.
Figure 1 graphically shows parts of the factual domain model for propose-and-revise and for the U-Haul domain. The upper part of the picture shows factual knowledge that is domain independent and can be reused for any domain. Constraint satisfaction (CS) problems are specified with a set of constraints and a state. The state is described with a set of variables. Constraints can have fixes. In a configuration problem, the state is a configuration. Some of the state variables denote components, i.e., pieces of equipment that together form a configuration. A component may have an upgrade, e.g., a more powerful model of that kind of equipment.
The lower part of the picture shows factual knowledge that is relevant only to the U-Haul domain. One of the state variables denotes the equipment that the client can rent, which can be a trailer, a rooftop, or a truck. There are several kinds of trucks, ranging from the smallest EasyMover to the largest HeftyMover.
There is a continuum between the representation of domain-dependent and domain-independent factual knowledge in EXPECT. They are represented in the same language, yet they can be defined and maintained separately. Once a U-Haul problem is specified as a kind of configuration problem, it inherits the fact that it has constraints and fixes. Trucks are not defined as having upgrades, since having upgrades is a way to look at components from the point of view of configuration problems. Instead, they are defined as configuration components, which have upgrades.
Figure 1: EXPECT's representation of some of the factual knowledge needed for propose-and-revise problems, for configuration problems, and for the U-Haul domain. Notice that the relations across these subdomains are naturally captured in the subsumption hierarchy.
Figure 2 shows three different problem-solving methods. REVISE-CS-STATE is one of the methods that specifies how propose-and-revise works. To revise a CS state, we apply the fixes that are found for the constraints violated in the state. The other two specify a constraint and a fix in the U-Haul domain respectively. CHECK-CAPACITY-CONSTRAINT specifies that the capacity of the equipment rented cannot exceed the volume that the client needs to move. APPLY-UPGRADE-EQUIPMENT-FIX applies the fix of upgrading the equipment being rented.
The representation of knowledge about constraints and fixes illustrates EXPECT's separate representations for procedural and factual knowledge. UpgradeEquipmentFix is a fix for the CapacityConstraint regardless of how the constraint is checked or how the fix is applied. Thus, this is represented as factual knowledge as a relation between an instance of constraint and an instance of fix, as shown in Figure 1. The procedures to check the constraint and to apply the fix are part of the problem-solving knowledge base, and are executed as part of the process to revise configurations. Factual knowledge and problem-solving knowledge about constraints and fixes are related because the methods refer to the instances CapacityConstraint and UpgradeEquipmentFix in their arguments. This separation of different kinds of knowledge is key in supporting knowledge acquisition in EXPECT, as will be shown in Section 5.
Notice that, like factual knowledge, problem-solving knowledge can be domain dependent or domain independent. EXPECT uses the same language to represent both.
Figure 2: Problem-solving knowledge in EXPECT.