Computational architecture for reasoning involving extensible graphical representations

• US 5,999,182 A
• Filed: 05/11/1998
• Issued: 12/07/1999
• Est. Priority Date: 05/11/1998
• Status: Expired due to Fees

• Current Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Original Assignee: Board of Trustees of the Leland Stanford Junior University (Stanford Management Co.)
• Inventors: Etchemendy, John W., Barwise, K. Jon
• Primary Examiner(s): Huynh, Ba
• Application Number:
  US09/075,372
• Time in Patent Office: 575 Days
• Field of Search: 706/45, 706/46, 706/53, 706/54, 706/55, 706/56, 706/57, 706/58, 706/59, 706/60, 706/61-67, 345/326, 345/348, 345/349
• US Class Current: 715/853
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound

Abstract

A computer architecture supports reasoning tasks involving information represented in graphical form. The architecture supports the creation, storing, display, and editing of a partially ordered set of nodes representing the steps in a reasoning process, as well as representations of information associated with the nodes. Modifications are constrained by rules that support the creation of valid reasoning. In particular, special rules of inheritance place constraints upon what information is available for display and modification at any given point in the reasoning process. The present architecture supports reasoning about any type of graphical representation and about multiple representations within a single reasoning process. In addition, the present architecture supports extensible representations, i.e., representations that may be edited at later points in a proof to extend the range of possible values which may be assigned to their attributes, or to add or delete objects or attributes. The architecture can simultaneously support and integrate the structured reasoning involving both sentential and graphical representations of information. The techniques provided by the invention have application to a wide variety of engineering and scientific practices by improving the processes through which designs and problem solutions are created, assessed, and communicated. It has particular importance and value for complex collaborative projects.

Claims

1. A computer implemented method for assisting a user engaged in a reasoning task, the method comprising:

a) storing in a memory a data structure comprising;

i) a partially ordered set of nodes comprising a set of nodes N and a partial ordering of N,

ii) a set R of representations, wherein at least one representation r in R is a graphical representation comprising a set of edits d₀, . . . , d_L, wherein L≧

0, and

iii) a function f;

r→

N assigning to each edit d_i in r an associated node f(d_i) in N, wherein f(d_i)≧

f(d₀) for all i;

b) displaying to the user an instance r[n] of the representation r at a user-selected node n, wherein the instance r[n]={d_i in r such that n≧

f(d_i)≧

f(d₀)};

c) receiving from the user an instruction to introduce at the node n in N an edit d_L+1 to the graphical representation r; and

d) modifying the data structure to introduce at n the edit d_L+1 to r, provided;

i) n≧

f(d₀); and

ii) r is extensible, or n=f(d₀), or the edit d_L+1 at n does not extend r.

2. The method of claim 1 wherein the edit d₀ of the graphical representation r comprises a set of graphical objects, wherein each graphical object comprises a set of attributes, wherein each attribute comprises an attribute value range, and wherein condition d) ii) fails ifr is defined to be a non-extensible representation, andn≠

f(d₀), and

3) one or more of the following propositions is true;

a) the edit d_L+1 adds an object to r;

b) the edit d_L+1 deletes an object of r;

c) the edit d_L+1 adds an attribute to an object of r;

d) the edit d_L+1 deletes an attribute of an object of r; and

e) the edit d_L+1 extends an attribute value range of an attribute of an object of r.

3. The method of claim 1 wherein the set R of representations is a heterogeneous set of representations comprising at least two distinct representational forms selected from the group consisting of a spreadsheet, a CAD drawing, a chemical structure diagram, a topological diagram, a Feynman diagram, an electrical schematic, an architectural drawing, an artistic drawing, a 3D model, an animation, a motion picture, a table, a Venn diagram, a Euler diagram, a blocks world diagram, a position diagram, a Boolean truth table, a binary decision diagram, a graph, a flowchart, a mathematical sentence, a computer program, a logical sentence, and a linguistic expression.

4. The method of claim 1 wherein the edit d_L+1 of r comprises an edit selected from the group consisting of:

a) an addition of an object to r;

b) a deletion of an object from r;

c) an addition of an attribute to an object of r;

d) a deletion of an attribute of an object of r;

e) an extension of an attribute value range of an attribute of an object of r;

f) a partial restriction of an attribute value range of an attribute of an object of r;

g) a complete restriction of an attribute value range of an attribute of an object of r; and

h) a specification of an attribute value within an attribute value range of an attribute of an object of r.

5. The method of claim 1 wherein the method further comprises the step of determining if the data structure satisfies a condition of the reasoning task.

6. The method of claim 1 wherein the condition of the reasoning task is selected from the group consisting of a logical inference rule, a goal of the reasoning task.

7. The method of claim 1 further comprising the step of modifying the partially ordered set of nodes by a structural edit, wherein the structural edit is chosen from the group consisting of a deletion of a node in the set N, an addition of a node to the set N, and a change in partial ordering on the set N.