|
Hyung Joon Kook Department of Computer Science King Sejong University 98 Kunja, Sungdong Seoul, Korea 133-747 |
Gordon S. Novak Jr.
Department of Computer Sciences University of Texas at Austin Austin, TX 78712 |
Copyright © 1990 by IEEE.
Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
This article appears in Proceedings of The Sixth Conference on Artificial Intelligence Applications, Santa Barbara, CA, March 1990 (IEEE Computer Society Press), pp. 274-280.
This research was supported by the U.S. Army Research Office under contract DAAG29-84-K-0060. Computer equipment used in this research was donated by Xerox Corporation.
Expertise in solving real-world physics problems is characterized by the ability to adequately set up (or represent) a problem. An expert's representation is distinguished from a novice's by employing idealized, formal models (such as a point mass or the principle of uniform circular motion) for modeling objects and relationships in the initial problem. A computer program, APEX (A Physics Expert), has been developed to investigate the nature and contents of such models. As the representational primitives of the domain, two types of models are defined: canonical physical objects and physical models. During problem solving, the problem is represented in the form of a data connection network, which is progressively augmented by these models in the form of additional network elements. APEX's representational framework supports multiple representations (e.g., viewing many objects as a single canonical physical object) and handling of incompletely specified problems. The proposed representational methodology may be applied to similar domains in which representations of domain knowledge are based mainly on models.
Real-world physics problems are often presented in terms of informal, real-world objects and the relationships among them. An important task of a problem solver is to obtain a formal representation of the problem by interpreting each of these objects and relationships into formal, often abstract, models of physics. Therefore, competence in solving a physics problem derives mainly from the skill of setting up the problem in terms of these models, rather than from mere mathematical skill [larkin:lmss]. An expert in physics is believed to possess a finite number of such models that may be applied to solve a number of complex problems.
We have been investigating a machine problem solver in physics with its representational aspects as the primary research issue [kook:diss]. The primary goal of this research has been to develop a problem-solving model that realizes the model-building aspect of expert physics problem solving. The resulting system, APEX (A Physics Expert), is a computer program built in an object-oriented programming environment [novak:glisp] for solving physics problems in a model-based representational framework. There are two types of models employed in APEX: canonical physical objects and physical models. Canonical physical objects are those idealized objects in physics that are only meaningful in physics, such as a point mass, a circle or an ideal rope. Physical models are a group of data structures for representing the laws and principles of physics.
APEX extends the work in ISAAC [novak:isaac,novak:ijcai], a program that solves physics problems stated in English, with the main research issue shifted from natural language understanding to representational aspects of physics problem solving. Many underlying ideas in the development of APEX are supported by the results of psychological study by [chi], which made a comparison between experts and novices in categorizing a given set of problems. Other studies of the nature of performance differences between experts and novices [larkin:etal,larkin] suggest the importance of model-building behavior of experts, which comprises one of APEX's main research issues. [addanki] and [murthy] describe the use of graphs that relate physical models, with edges of a graph representing differences in the assumptions of the models. [lowry] describes abstraction models in the domain of programming. [bobrow] includes descriptions of several approaches to qualitiative reasoning about physical systems, including qualitative process theory [forbus], confluences [dekleer-brown], and qualitative simulation [kuipers].
The overall organization of the program and its data elements is shown in Figure 1. In the diagram, programs are represented by boxes with double lines, and data structures and rules by plain boxes, while links between boxes represent the data flow.
Fig. 1: Overall Program Organization.
A physics problem is presented to the system in the form of a semantic network describing features of a group of objects and their relationships with other objects. In the current implementation of APEX, the initial representation of a problem is formulated by hand-simulating the output from an English parser similar to the ones in [novak:isaac,bulko,bulko:diss].
Given an initial representation of a problem, the process of solving a physics problem occurs in several distinct steps. First, aided by an inference system that reasons about the objects and their relationships, APEX transforms the initial problem representation into a representation in terms of canonical physical objects such as a point mass. This is achieved by interpreting each object in the initial representation into a canonical physical object selected from a library of canonical physical objects based on the object's features and interactions with other objects. Transformation of an object into a canonical object is performed by constructing a data connection network between the two objects which provides a computational facility for viewing an object as another (canonical physical) object. Therefore, the problem representation resulting from this stage (labeled canonical representation in the diagram) actually consists of a group of views that inherit all the properties of corresponding canonical physical objects.
Then, the canonical representation is again used as input for reasoning by the inference system, which aids APEX in building a physical representation of the problem in which the underlying physical principles and laws involved in the problem are explicitly represented. APEX's physical models can be divided into two subgroups based on their operational goals: those specialized for making inferences about implicit forces, and those specialized for writing equations. Accordingly, this stage of problem solving is performed in two distinct steps; the first step is to select and instantiate physical models involving forces, and the second step is to select and instantiate physical models involving equations.
The next stage of problem solving involves formulating a set of equations by collecting equations from the physical model instances in the physical representation in order to obtain a mathematical representation of the problem. Finally, the equations, which may contain symbolic constants as well as numbers (with units) and variables, are sent to a symbolic manipulation package designed to solve simultaneous equations for the desired quantities of the problem.
As outlined above, APEX solves a physics problem by a series of stepwise re-representation processes involving invocations of models to the initial problem representation. This stepwise re-representation process is performed in a way that augments the previous problem representation rather than replacing it. Therefore, the final problem representation may be considered a representation of the problem with full specification of its underlying structures that were initially implicit. At each stage of re-representation, APEX is guided by an inference system specialized for selecting proper canonical objects or physical models. A user-friendly interface is installed in APEX for assisting a human to mimic a physics expert in the selection process. MISA (Mini Inference System for APEX) is an inference system that has been developed to demonstrate APEX in a limited number of problem-solving sessions without human intervention. MISA comprises of a set of inference rules that a human physics expert might consider when selecting proper models.
Canonical objects such as a point mass, a lever, or an ideal rope serve as the vocabulary for physics. Most real-world physics problem solving involves the process of interpreting the objects in the initial problem into ideal, canonical objects that are only meaningful in physics. A group of canonical objects has been predefined in APEX's permanent knowledge base; each canonical object is an object class in an object-oriented programming environment. A canonical object class is defined with its intrinsic attributes and methods for computing those properties that are computable from the attributes. Figure 2 shows the definitions for some example canonical object classes.
| class: | PtMass |
| attributes: | mass |
| superclass: | CanonicalObj |
| class: | Rope |
| attributes: | rotation |
| tension | |
| superclass: | CanonicalObj |
| class: | Circle |
| attributes: | radius |
| properties: | diameter <- 2 * radius |
| area <- pi * radius2 | |
| perimeter <- pi * diameter | |
| superclass: | CanonicalObj |
Fig. 2: Example Canonical Object Classes.
We regard the process of abstracting an initial object as a canonical physical object as a data conversion process between the two different representations. APEX employs the notion of view to accomplish the data conversion between the initial and canonical representations of the objects. A view serves as a hybrid data structure facilitating bidirectional mapping of the features of the objects in the two representations. During APEX's problem solving, viewing an input object as a canonical object is achieved by dynamically constructing a collection of network elements within the object-oriented programming environment of APEX. The network consists of five kinds of data elements described below:
A car is moving on a circular racetrack with a curvature-radius of 60m. If the banking of the racetrack is 30 degrees from the horizontal, what is the uniform speed of the car to keep it moving in the circle without friction?In the course of solving the problem, MISA (Mini Inference System for APEX) would suggest a circle view of the track, among other views. Figure 3 shows the view network constructed by APEX for that effect. In the diagram, a real-world object instance, Racetrack1, is abstracted as a canonical object class, Circle. A new view class, CircleView1, is constructed with an originalobj attribute and a radius property. The mapping instruction for deriving the feature of the target canonical object, i.e., radius, is given by MISA as (GETV Racetrack1 curvature-radius). [(GETV < obj> < slot>) retrieves the value of < slot> from < obj>.] This mapping instruction is then stored, in a more general form, i.e., (GETV originalobj curvature-radius), in the CircleView1 class as the method for computing its radius property. The internal data structure for CircleView1 class is shown in Figure 4. [View descriptions will be discussed in a later section.] Finally, an instance of the view class, CircleView1.1, is created with its originalobj attribute defined as Racetrack1.
Fig. 3: An Example View Network Structure.
| class: | CircleView1 |
| attributes: | originalobj |
| viewdescription | |
| properties: | radius <- (GETV originalobj curvature-radius) |
| superclass: | Circle |
| View | |
Fig. 4: Data Structure for CircleView1.
The resulting view instance, once constructed, enables APEX to treat it as if it were a `real' Circle, i.e., properties of a Circle (e.g., area, perimeter) are directly accessible to the view instance thanks to the property inheritance mechanism of the object-oriented programming environment. In APEX, the final physical representation of a problem is obtained in terms of a collection of such view instances.
In the physics problem-solving domain, problems are often presented incompletely specified. Such under-specification is effectively dealt with by the proposed representational framework. APEX's process of building a canonical representation of a problem is concerned with construction of a bidirectional data conversion scheme between the initial and canonical representations of a problem. In the forward direction (from initial to canonical, and to physical representation), the derivation methods are stored only in symbolic forms specifying where and how to derive data. Actual values are not retrieved until after building the final physical representation of the problem, at which point values are retrieved by evaluating these forms in order to write equations involving only constants and variables. In the backward direction, intermediate results obtained from the canonical (or physical) representation are transmitted into the missing slots of original representation, eventually resulting in full specification of the problem. An example of backward data propagation would be when external forces acting on the car (viewed as a point mass) in the previous example are considered. In order to derive the gravitational force exerted on the car, it is necessary to consider the kind of gravitational field the car resides in. For this, APEX decides to create a field instance with default gravitational constant, in which case the newly created instance is attached to the car in the initial representation[ A field is an environment of an object. In APEX, there are four kinds of environments: field, contact, motion and external force.]. In an analogous way to specifying an object's implicit environment, backward data propagations are also effectively used for specifying an object's structural attributes (e.g., the tension of a rope), or even attributes of an environment (e.g., the acceleration of a motion).
[novak:mult] suggested the importance of multiple representations in solving physics problems. In the previous section, we were mainly interested in the discussions on viewing a single object as a single canonical object. As the level of a problem's complexity increases, however, there are occasions when a mere application of one-to-one view strategy is not adequate for modeling the problem. This occurs when a problem involves an object which plays multiple roles in the problem context; e.g., in the racetrack problem, the track's two-dimensional geometry has to be abstracted as a canonical circle, and a vertical snapshot of the car on the track suggests that the track be viewed as a canonical incline as well. This type of multiple view (one-to-many view) is handled in APEX without any difficulty, since once a canonical views representation is constructed, its internal data connections to initial objects are transparent to the problem solver.
Another type of multiple view is viewing many objects as a single canonical object. Representation of this type (many-to-one view) needs some elements in addition to the view framework we have presented. We will describe the extensions to the proposed view framework by considering the following problem (ref. [larkin]).
What constant horizontal force F must be applied to the large cart in Figure 5 (of mass M) so that the smaller carts (masses m1 and m2) do not move relative to the large cart? Neglect friction.
Fig. 5: Sample Problem.
In the course of solving this problem, it is required that the problem solver take a single point mass view of all objects in motion (three carts, pulley and string) as a preliminary step to writing a force equation about the total mass with respect to the external force (F). When advised by the inference system to view these objects as a point mass, APEX's canonical representation builder first recognizes this as advice to build a many-to-one view network and makes an instance of CompositeObj class in the current context. CompositeObj is a special object class that is designed to bridge between a target canonical view and multiple objects in the initial representation. An instance of CompositeObj class is essentially an encapsulation of multiple objects, with pointers to those objects involved in the view. Once such an instance is set up, it is treated by APEX as a single object instance for the later stages of problem solving. Figure 6 shows the problem representation after a multiple view is taken (the initial problem representation is shown in the dashed box). Figure 7 shows the data structures for the added nodes.
Fig. 6: Multiple View.
| instance: | PtMassView1.2 |
| attributes: | originalobj <- CompositeObj1 |
| viewdescription <- ViewDesc1 | |
| properties: | mass <- (GETV originalobj mass) |
| superclass: | PtMass |
| View |
| instance: | CompositeObj1 |
| attributes: | fromobjs <- (S-cart1 S-cart2 L-cart Pulley String) |
| properties: | mass <- M + m1 + m2 |
Fig. 7: Data structures for the elements of multiple view.
A physics textbook presents a set of physical principles. Expertise in physics problem solving is best described by the ability to apply a proper set of physical principles to solve real-world problems, in order to obtain a set of equations relevant to the problem context. APEX employs the notion of physical models as the data structures for modeling principles of physics. A physical model is essentially an encapsulation of a single principle or law of physics, stored in a permanent knowledge base of APEX. Whereas a canonical physical object is an abstraction of (one or more) objects, a physical model is a physical interpretation of a situation involving (one or more) objects and their relationships. Each physical model is designed to contain a chunk of physical principle such as:
Like canonical physical objects, physical models are implemented as a set of object classes in an object-oriented programming environment. The following is the description of the contents of a physical model.
When the inference system (e.g., MISA) examines the canonical representation of a problem for selecting physical models to be used for solving the problem, the components of physical models are tested for match with a certain group of views and their environments. If a physical model involving a sysvar (e.g., a coordinate system) is selected, the inference system first computes it by invoking a library procedure specialized for this task.
After matching contexts (and sysvar, if any) are passed to a group of programs for instantiating the selected physical model, these programs first construct an object class called a model class. A model class is constructed by copying from the attributes of the selected physical model with an additional attribute for model description. [Model descriptions will be discussed in a later section.] After making the new model class a subclass of the selected physical model, the model-building programs undergo a process of instantiating it in the given context. The locals of the physical model (which is now a super class of the model class) are computed in a predefined order using the methods given in the locals property definitions. The computation of a locals property may involve inference of unspecified data. Suppose, for instance, that the physical model in Figure 8 has been selected for instantiation, and that the obj in question is in contact (Contact1) with the incline in question. If the normal force acting at Contact1 is initially unknown, the effect of computing (GETV contact normalforce (CREATE Vector WITH dir = (normalto incline))) is to create a vector as prescribed by (CREATE ) procedure (i.e., with direction = (normalto incline) and magnitude = a symbolic constant), and to store it as the value of the normalforce property of Contact1.
| class: | NormalforceModel |
| components: | obj |
| incline | |
| property: | contact <- (CONTACTBETWEEN obj incline) |
| loc <- (LOCATIONOF obj contact) | |
| force.vect <- (GETV contact normalforce (CREATE Vector WITH dir = (normalto incline))) | |
| force.env <-
(CREATE ExtForce WITH force = force.vect obj = obj loc = loc agent = incline) | |
| OUT <- (ENVADD obj force.env) | |
| superclass: | PhysicalModel |
Fig. 8: Physical Model Class NormalforceModel.
The last property of a physical model is always an OUT property. Computation of an OUT property results in generating either a set of equations (through an EQNADD operation) or a new environment for an object (through an ENVADD operation). When the OUT property is an EQNADD operation, the equations are stored in a global storage space. An example use of an ENVADD operation is given in Figure pmex1; i.e., instantiation of this model will result in attaching the force (an environment) to the obj.
The main design theme of the research in APEX is to provide a separation of representation from the inference aspect of problem solving, i.e., the process of selecting proper models. We have developed an interface to APEX which facilitates human-guided selection of models. In addition, the interface is designed to present the progressive stages of problem representation in the form of a graph, in which a graph node may be further inspected in a menu-driven way. Figure p5:mview is a segment of such a graph.
Besides APEX's facility for human-guided inference, a small rule base, MISA (Mini Inference System for APEX), has been constructed to be used for testing APEX on a selected set of problems with machine-guided inference. The rule base is written in ARL (APEX Rule Language), a rule language designed specially for this purpose. MISA works in a forward-chaining manner; i.e., it reasons about a situation involving objects and relationships, then makes suggestions on what models to use.
As APEX solves a problem with augmentations to the initial problem representation, the various stages of representation do not explicitly reflect the system's previous reasoning behaviors (or inference history) that brought about the present state of problem representation. In order to facilitate a capability for recording this information within the framework of APEX, it employs the notion of view descriptions and model descriptions as data structures for keeping track of the system's inference history. View and model descriptions are defined as object classes, which are instantiated for specific viewing or modeling operations and attached to the resulting view or physical model. They are effectively used as the template for recording what rule has been applied to what kind of situations, and what initially-unspecified quantities have been derived and how. During or after solving a problem, they provide the basis for APEX to answer some of the questions about the system's reasoning behavior. For instance, a user might want to ask the system why a specific view has been taken. The user interacts with the system through the menu-driven graphic interface, to obtain the answer in the form of a rule, instantiated in its matching context and translated into English.
The main content of solving real-world physics problems is the process of representing the problems in terms of formal domain models. A computer model for solving physics problems cannot rely merely on the linguistic aspects of the problems, since these would constrain the basis for the problem-solving decisions to literal (i.e., superficial) features of the problems. We also believe a purely goal-driven approach (e.g., equation-driven as in [bundy:ai]) to physics problem solving to be a weak strategy, since such an approach seems to ignore the data-driven representational aspect of expert problem solving.
The major advantages of employing the notion of models for representing a scientific domain such as physics are:
We believe the representational methodology developed in APEX may be applied to similar domains to provide a language for dealing with the conceptual entities [greeno] of the domains. Potential applications include engineering analysis and computer-aided instruction in physics.
[addanki] S. Addanki, R. Cremoni, and J. S. Penberthy, ``Reasoning About Assumptions in Graphs of Models,'' Proc. IJCAI-89, pp. 1432-1438.
[bobrow] Bobrow, D., ed., Qualitative Reasoning about Physical Systems, M.I.T. Press, 1985.
[bulko] W. Bulko. ``Understanding Text With an Accompanying Diagram'', Proc. First International Conference on Industrial and Engineering Applications of AI and Expert Systems, Tullahoma, TN, 1988, pp. 894-898.
[bulko:diss] William Bulko. Understanding Coreference in a System for Solving Physics Word Problems, Ph.D. dissertation, available as AI-89-102, CS Dept., Univ. of Texas at Austin, 1989.
[bundy:ai] A. Bundy. ``Will It Reach the Top? Prediction in the Mechanics World'', Artificial Intelligence, 10, 1978, pp. 129-146.
[chi] M. Chi, P. Feltovich and R. Glaser. ``Categorization and Representation of Physics Problems by Expert and Novices'', Cognitive Science, 5, 1981, pp. 121-152.
[dekleer-brown] J. de Kleer and J. S. Brown, ``A Qualitative Physics Based on Confluences'', in [bobrow], pp. 7-84.
[forbus] K. Forbus, ``Qualitative Process Theory'', in [bobrow], pp. 85-168.
[gentner] D. Gentner. and A. Stevens. (eds.) Mental Models. Hillsdale, NJ: Lawrence Erlbaum Associates, 1983.
[greeno] J. Greeno. ``Conceptual Entities'', in [Gentner and Stevens 83].
[kook:diss] H. J. Kook. A Model-Based Representational Framework for Expert Physics Problem Solving. Ph. D. dissertation. Available as AI-89-103, CS Dept., Univ. of Texas at Austin, 1989.
[kuipers] B. Kuipers, ``Commonsense Reasoning about Causality: Deriving Behavior from Structure'', in [bobrow], pp. 169-204.
[larkin:lmss] J. Larkin, J. McDermott, D. Simon and H. Simon. ``Expert and Novice Performance in Solving Physics Problems'', Science, 208, 20 June 1980, pp. 1335-1342.
[larkin:etal] J. Larkin, J. McDermott, D. Simon and H. Simon. ``Models of Competence in Solving Physics Problems'', Cognitive Science, 4, 1980, pp. 317-345.
[larkin] J. Larkin. ``The Role of Problem Representation in Physics'', In [Gentner and Stevens 83].
[lowry] M. Lowry, ``The Abstraction/Implementation Model of Problem Reformulation'', Proc. IJCAI-87, pp. 1004-1010.
[murthy] S. Murthy and S. Addanki, ``PROMPT: An Innovative Design Tool'', Proc. AAAI-87, pp. 637-642.
[novak:isaac] G. Novak. ``Computer Understanding of Physics Problems Stated in Natural Language'', American Journal of Computational Linguistics, Microfiche 53, 1976. Also available as TR-NL-30, CS Dept., Univ. of Texas at Austin, 1976.
[novak:ijcai] G. Novak. ``Representations of Knowledge in a Program for Solving Physics Problems'', Proc. IJCAI-77, 1977, pp. 286-291.
[novak:mult] G. Novak and A. Araya. ``Physics Problem Solving Using Multiple Views'', TR-173, CS Dept., Univ. of Texas at Austin, 1981.
[novak:glisp] G. Novak. ``GLISP: A LISP-Based Programming System With Data Abstraction'', AI Magazine, Fall, 1983, pp. 37-47.