# US 5,706,406 A · Architecture for an artificial agent that reasons defeasibly > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 5,706,406 A - Document ID: US5706406A - Status: Granted - Kind: A - Application number: 08/445,995 - Filed: 1995-05-22 - Granted: 1998-01-06 - Earliest claimed: 1995-05-22 - Inventors: John L. Pollock - Web page: https://patentgrep.com/patent/US5706406A ## CPC - G06N 5/04: Inference or reasoning models - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS ## Abstract A method for defeasible reasoning including a method for analyzing data input, reasoning to conclusions on the basis of that data and adopting and executing plans on the basis of those conclusions. The processes are defeasible in the sense that, as reasoning proceeds or new data is input to the system, both conclusions and plans may be retracted and replaced by new conclusions and plans that are better supported by the new data and reasoning. The methods of the invention are useful as controlling mechanisms for a variety of applications, including robotics, operational assembly lines, and as on-line "assistants" for computer work. The methods can also be used as an advisor in many applications, including medical diagnosis, fault diagnosis in manufacturing and transportation scheduling. Additionally, submethods that draw conclusions on the basis of defeasible reasoning can be used as an inference-engine for automated data analysis. ## Claims ### Claim 1 A computer implemented method for defeasible reasoning, comprising the steps of: (a) generating a list of conclusions by monotonic reasoning and recording said conclusions in a selected one of a simple inference-graph and an and/or inference-graph each having nodes corresponding to said conclusions; (b) computing defeat-status for said nodes of said inference-graph, using a method comprising the steps of: (i) computing a list of status-assignments; (ii) computing the defeat-status of a selected node by one of the following: (A) a method for computing the defeat-status of a selected node wherein said inference-graph is an and/or inference-graph and said node is judged undefeated only if every status-assignment assigns a nonzero defeat-status to said node; and (B) a method for computing the defeat-status of a selected node wherein said inference-graph is an and/or inference-graph and said node is judged undefeated if said inference-graph contains nodes that constitute an argument for said node and all of said nodes in said argument are assigned an undefeated defeat-status by every status-assignment. ### Claim 2 (depends on 1) The method of claim 1, in which said monotonic reasoning proceeds by a method comprising the steps of: (a) selecting a set of sequents in a list input, and a set of sequents in a list ultimate-epistemic-interests; (b) categorizing said sequents in said list input as conclusions and inserting said sequents into an ordered list inference-queue, (c) categorizing said sequents in said list ultimate-epistemic-interests as interests and inserting said interests into said list inference-queue; (d) retrieving in order said conclusions and said interests of said list inference-queue; (e) for each said conclusion retrieved, performing forwards reasoning to produce new conclusions and storing said new conclusions in a data structure inference-graph and also placing said new conclusions on said list inference-queue; (f) for each said interest retrieved performing, backwards reasoning to produce new interests and storing said new interests in a data structure interest-graph and also placing said new interests list on said list inference-queue; (g) comparing each said new conclusion with said interests recorded in said interest-graph and discharging from said inference graph each said new conclusion that is the same as an interest recorded in said interest graph; and (h) comparing each said new interest with said conclusions recorded in the inference-graph, and discharging from said interest graph each said new interest that is the same as a conclusion recorded in said inference graph. ### Claim 3 (depends on 2) A method as defined in claim 2 comprising repeating indefinitely, steps (a) through (h) whereby the reasoning never terminates. ### Claim 4 (depends on 2) A method as defined in claim 2 comprising repeating steps (a) through (h) until said inference-graph is empty. ### Claim 5 (depends on 1) The method of claim 1, wherein one node of the inference-graph defeats a second node only if the maximal-degree-of-support of the first node is at least as great as the maximal degree-of-support of the second node. ### Claim 6 (depends on 1) The method of claim 1, wherein maximal-degrees of support for members of the inference-graph are computed in accordance with the weakest-link principle. ### Claim 7 (depends on 1) The method of claim 1, as exemplified by the operation make-inference-from-link, wherein a new conclusion is drawn in accordance with an interest-link only when the maximal-degree-of-support for said new conclusion is at least as great as the degree-of-interest of the link-interest for said interest-link. ### Claim 8 (depends on 1) The method of claim 1, as exemplified by the operation discharge-interest-in, wherein interest in a conclusion is discharged only when the maximal-degree-of-support for said conclusion is at least as great as the degree-of-interest for some interest that said conclusion discharges. ### Claim 9 (depends on 1) The method of claim 1, wherein undefeated-degrees-of support and degrees-of-interest are used in prioritizing the inference-queue. ### Claim 10 (depends on 1) The method of claim 1 wherein said list of conclusions is maintained and forward reasoning makes inference only from elements of that list, whereby the method avoids duplicating reasoning in connection with inference-rules and reason schemes having multiple premises. ### Claim 11 (depends on 1) The method of claim 1, wherein: (a) conclusions and interests are stored in c-lists and i-lists; (b) for each c-list, the list of corresponding-i-lists is maintained; (c) for each i-list, the list of corresponding-c-lists is maintained; and (d) searches for appropriately related interests and inference-nodes are performed by searching the corresponding-c-lists of their i-lists and corresponding-i-lists of their c-lists, as exemplified by the operations discharge-interest-in, discharge-link, make-inference-from-link, and replicate-discharges, thereby avoiding replicating searches when matching or unifying conclusions and interests. ### Claim 12 (depends on 1) The method of claim 1, wherein interest-schemes are used to direct the portion of backward-reasoning that results from instantiating backward-reasoning by instantiating the conclusion of said reasons with an interest. ### Claim 13 (depends on 1) The method of claim 1, wherein interest-links are used to direct the portion of backward-reasoning that results from instantiating interest-schemes by instantiating the forward premises of said interest-schemes with conclusions. ### Claim 14 (depends on 1) The method of claim 1, as exemplified by the operation replicate-discharges, wherein the list of discharged-right-links for an interest is maintained, and searched when new conclusions are drawn, whereby the effect of interest-discharge is repeated when said new conclusions are drawn. ### Claim 15 (depends on 1) The method of claim 1, exemplified by the operations discharge-link and discharge-interest-in, wherein backward reasoning cancels interest in inference-nodes and interests that are no longer of use, whereby said inference-nodes and interests do not occupy the resources of the reasoning. ### Claim 16 (depends on 1) The method of claim 1, wherein the list of status assignments is computed by compute-assignments. ### Claim 17 (depends on 1) The method of claim 1, as exemplified by the operation compute-assignment-tree, wherein the list of status-assignments is computed by building the assignment-tree and taking said list of status-assignments to be the list of tree-assignments for all subtrees of said assignment-tree. ### Claim 18 (depends on 1) The method of claim 1, as exemplified by the operation update-assignment-tree, wherein the list of status-assignments is updated by recomputing only those parts of the assignment-tree containing inference/defeat-descendants of newly added support-links. ### Claim 19 A computer-implemented method of directing plan adoption, comprising the use of defeasible reasons governing terms comprising suitable-goals, adoptable plans, and disjunctively-adoptable-plans, wherein said terms can be taken as place-holders irrespective of whether said terms are contentful expressions. ### Claim 20 A computer-implemented method of directing plan-execution, comprising the use of defeasible reasoning relating terms comprising adoptable-plans, disjunctively-adoptable-plans, and executable-operations, where said terms can be taken as place-holders in the reasoning irrespective of whether said terms are contentful expressions. ### Claim 21 A computer implemented method for defeasible reasoning, comprising the steps of: (a) generating a list of conclusions by monotonic reasoning and recording said conclusions in a selected one of a simple inference-graph and an and/or inference graph each having nodes corresponding to said conclusions: (b) computing defeat-statuses for said nodes of said inference-graph, using a method comprising the steps of: (i) computing a list of status-assignments; (ii) computing the defeat-status of a selected node by employing a method selected from the group consisting of: (A) a method for computing the defeat-status of a selected node wherein said inference-graph is an and/or inference-graph and said node is judged undefeated only if every status-assignment assigns a nonzero defeat status to said node; and (B) a method for computing the defeat-status of a selected node wherein said inference-graph is an and/or inference-graph and said node is judged undefeated if said inference-graph contains nodes that constitute an argument for said node and all of said nodes in said argument are assigned an undefeated defeat-status by every status-assignment; (c) through the use of monotonic reasoning, selecting a set of sequents in a list input, and a set of sequents in a list ultimate-epistemic-interests; (d) categorizing said sequents in said list input as conclusions and inserting sequents into an ordered list inference-queue; (e) categorizing said sequents in said list ultimate-epistemic-interests as interests and inserting said interests into said list inference-queue; (f) retrieving in order said conclusions and said interests of said list inference-queue; (g) for each said conclusion retrieved, performing forward reasoning to produce new conclusions and storing said new conclusions in a data structure inference-graph and also placing said new conclusions on said list inference-queue; (h) for each said interest retrieved performing, backward reasoning to produce new interests and storing said new interests in a data structure interest-graph and also placing said new interests list on said list inference-queue; (i) comparing each said new conclusion with said interests recorded in said interest-graph and discharging from said inference graph each said new conclusion that is the same as an interest recorded in said interest graph; and (j) comparing each said new interest with said conclusions recorded in the inference-graph, and discharging from said interest graph each said new interest that is the same as a conclusion recorded in said inference graph. ### Claim 22 (depends on 21) The method of claim 21, wherein one node of the inference-graph defeats a second node only if the maximal-degree-of-support of the first node is at least as great as the maximal degree-of-support of the second node. ### Claim 23 (depends on 22) The method of claim 22, wherein maximal-degrees of support for members of the inference-graph are computed in accordance with the weakest-link principle. ### Claim 24 (depends on 23) The method of claim 23, as exemplified by the operation make-inference-from-link, wherein a new conclusion is drawn in accordance with an interest-link only when the maximal-degree-of-support for said new conclusion is at least as great as the degree-of-interest of the link-interest for said interest-link. ### Claim 25 (depends on 24) The method of claim 24, as exemplified by the operation discharge-interest-in, wherein interest in a conclusion is discharged only when the maximal-degree-of-support for said conclusion is at least as great as the degree-of-interest for some interest that said conclusion discharges. ### Claim 26 (depends on 25) The method of claim 25, wherein interest-links are used to direct the portion of backward-reasoning that results from instantiating interest-schemes by instantiating the forwards premises of said interest-schemes with conclusions. ### Claim 27 A computer-implemented method of directing plan adoption and plan-execution comprising the steps of: (a) directing plan adoption using defeasible reasons governing terms comprising suitable-goals, adoptable plans, and disjunctively-adoptable-plans, wherein said terms can be taken as place-holders irrespective of whether said terms are contentful expressions; and (b) directing plan-execution using defeasible reasons relating adoptable-plans, disjunctively-adoptable-plans, and executable-operations, where said terms can be taken as place-holders in the reasoning irrespective of whether said terms are contentful expressions. ### Claim 28 A computer implemented method for reasoning, comprising the steps of: (a) using forward-inference rules EI and UI and backward-logical reasons EG and UG to skolemize interest-formulas and conclusion formulas; (b) using unification to compute common instances of forwards-reasons and the node-formulas in inference-nodes, and using unification to compute conclusions to be inferred from said inference-nodes in accordance with said forwards-reasons; (c) when a supposition is generated by an interest, the interest-variables of the interest are made the node-variables of the inference-node recording the supposition; and (d) discharging interests by unifying the node-formula of an inference-node and the interest-formula of an interest to produce a unifier, applying said unifier to their suppositions, and then unifying the resulting node-supposition into the resulting interest-supposition. ### Claim 29 A computer implemented method for reasoning, comprising the steps of: (a) using procedure adopt-reductio-interest to create reductio-interests having schematic supposition; and (b) using procedures discharge reductios and discharge-retrospective-reductios to discharge reductio-interests having schematic suppositions.