Apparatus and method for data processing and/or for control

• US 5,812,994 A
• Filed: 05/20/1994
• Issued: 09/22/1998
• Est. Priority Date: 05/20/1993
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Imlah, William George
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Shah, Sanjiv
• Application Number:
  US08/246,702
• Time in Patent Office: 1,586 Days
• Field of Search: 395/50, 395/54, 706/45, 706/50
• US Class Current: 706/45
• CPC Class Codes: G05B 19/0428 Safety, monitoring G05B19/0423 takes precedence
• CPC Class Codes: G06N 5/04 Inference or reasoning models
• CPC Class Codes: G06N 5/041 Abduction

Abstract

A computer implemented abductive reasoner checks for contradictions in the reasoning operations during processing and determines subsequent processing dependent upon the results of the checking. Constraints on variables may be imposed to permit proofs to be pursued which otherwise would involve contradictions. Different types of abductive reasoning step may be assigned different costs and proofs or future processing steps selected dependent upon the costing. Alternatively or in addition, reasoning operations and the resulting proofs, if any, may be grouped according to the types of reasoning steps involved and provision may be included for pursuing operations involving less costly reasoning steps in preference or prior to operations which may be more costly. Where successive goals are to be proved, the proof of each successive goal may be performed by reference to hypotheses established in proofs of previous goals. In applications involving the production of control signals, commands defining required control signals may be provided in the form of premises in rules contained in a knowledge base with which the abducer operates and means may be provided for outputting said commands and converting them to the required control signals.

Claims

1. Data processing apparatus comprising means for storing a knowledge base containing data defining a plurality of facts and/or rules;

and an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, said abducer being operable to define in said record facts or other statements whose presence in the knowledge base has been relied upon in said reasoning operations and to prohibit hypothesized or actual removal from said knowledge base of said defined facts or other statements during subsequent processing.

2. Apparatus according to claim 1, wherein said hypothesised changes comprise adding facts to said knowledge base.

3. Apparatus according to claim 1, wherein said record defines said facts added to said knowledge base.

4. Apparatus according to claim 1, wherein said hypothesised changes include removal of facts from said knowledge base.

5. Apparatus according to claim 4, wherein said record defines said facts removed from said knowledge base.

6. Apparatus according to claim 1, wherein said hypothesised changes include removal of rules from said knowledge base.

7. Apparatus according to claim 6, wherein said record defines said rules removed from said knowledge base.

8. Apparatus according to claim 1, wherein said abducer is operable to process goals in the form of negative conjunctions.

9. Apparatus according to claim 8, wherein said hypothesised changes include deleting conjunctions and said record defines said deleted conjunctions.

10. Apparatus according to claim 1, wherein said abducer is operable to perform said testing for contradictions after the completion of all of the first and second reasoning steps in the reasoning operation.

11. Apparatus according to claim 1, wherein said abducer is operable to perform said testing at least some of said second reasoning steps.

12. Apparatus according claim 11, wherein said abducer is operable to perform said testing at each of said second reasoning steps.

13. Apparatus according to claim 1, wherein said abducer is operable to perform some of said tests for contradiction at said second reasoning steps and at least one further test for contradiction after completion of all of said first and second reasoning steps.

14. Apparatus according to claim 1, wherein said abducer is operable to process goals in the form of positive and negative literals and positive and negative conjunctions;

wherein said hypothesised changes comprise adding facts to the knowledge base, removing facts from the knowledge base, removing rules from the knowledge base, and deleting conjunctions;

wherein said record defines facts whose presence in the knowledge base is relied on in said first reasoning steps, defines facts whose unprovability has been relied on in said first reasoning steps, defines said facts added to said knowledge base, defines said facts removed from said knowledge base, defines said rules removed from said knowledge base and defines said deleted conjunctions;

wherein said abducer is operable to perform at said second reasoning steps tests for contradiction with said defined facts whose presence is relied upon, said defined facts whose unprovability is relied upon, said defined facts added, said defined facts removed, and said defined rules removed; and

wherein said abducer is operable to perform tests for contradiction with said defined deleted conjunctions after completion of all of said first and second reasoning steps.

15. Apparatus according to claim 1, wherein, upon detection of a contradiction in a partially completed reasoning operation, processing of said partially completed reasoning operation is terminated or suspended.

16. Apparatus according to claim 1, wherein, upon detection of a contradiction in a partially completed reasoning operation, said abducer is operable to determine whether processing of said partially completed reasoning operation may continue without contradiction by constraining variables in said data and/or in said goals, and to continue said processing with constraints on said variables to avoid said contradictions.

17. Apparatus according to claim 16, wherein processing of said partially completed reasoning operation is terminated or suspended when said abducer determines that said contradiction cannot be avoided by effecting said constraining.

18. Apparatus according to claim 1, wherein said abducer is operable to assign a cost to said reasoning steps and to determine on the basis of said assigned cost, a total cost for a reasoning operation.

19. Apparatus according to claim 18, wherein said abducer is operable to calculate the cumulative cost of the reasoning operation at intervals during said reasoning operation.

20. Apparatus according to claim 19, wherein said intervals are such that said abducer calculates the cumulative cost of the reasoning operation at each said second reasoning step.

21. Apparatus according to claim 19, wherein said abducer is operable at each said interval to compare the cumulative cost of the partially completed reasoning operation currently being processed to the cumulative cost of the least costly of any previously completed reasoning operations, and to terminate or suspend said partially completed reasoning operation if its cumulative cost has reached the cumulative cost of said least costly of said previously completed reasoning operations.

22. Apparatus according to claim 21, wherein said abducer is operable to select, from different reasoning operations proving the same goal, that operation having total cost indicating that it is likely to provide the best solution.

23. Apparatus according to claim 1, wherein said abducer is operable to group solutions to the same goal according to the nature of the reasoning steps performed in the reasoning operation.

24. Apparatus according to claim 23, wherein said hypothesised changes comprise adding facts to said knowledge base;

said hypothesised changes include removal of facts from said knowledge base; and

said grouping comprises placing in a first group reasoning operations in which only said first reasoning steps are performed, placing in a second group reasoning operations relying upon facts hypothetically added to the knowledge base and placing in a third group reasoning operations relying upon data hypothetically removed from the knowledge base.

25. Apparatus according to claim 24, wherein said groups are numbered according to a predetermined criterion, and wherein said abducer is operable to select solutions in a lower-numbered said group in preference to solutions in a higher-numbered said group.

26. Apparatus according to claim 23, wherein said hypothesised changes comprise adding facts to said knowledge base;

said hypothesised changes include removal of facts from said knowledge base;

said hypothesised changes include removal of rules from said knowledge base; and

said grouping comprises placing in a first group reasoning operations in which only said first reasoning steps are performed, placing in a second group reasoning operations in which data representing hypothesised addition of facts to the knowledge base is relied upon, placing in a third group reasoning operations in which data representing hypothesised removal of facts from the knowledge base is relied upon, and placing in a fourth group reasoning operations in which data representing hypothesised removal of rules from the knowledge base is relied upon.

27. Apparatus according to claim 23, wherein said grouping of said reasoning operations is performed during the performance of said reasoning steps.

28. Apparatus according to claim 23, wherein the grouping of said reasoning operations is performed after completion of the reasoning operation.

29. Apparatus according to claim 1, wherein said abducer is operable to seek said proof of a goal by pursuing reasoning operations involving only said first reasoning steps before seeking a said proof of a goal by pursuing reasoning operations involving said second reasoning steps.

30. Apparatus according to claim 29, wherein said abducer is operable, when pursuing said proof of a goal by reasoning operations involving said second reasoning steps, to pursue reasoning operations involving a predetermined type or types of said second reasoning steps before pursuing reasoning operations involving a different type or types of said second reasoning steps.

31. Apparatus according to claim 30, wherein said hypothesised changes comprise adding facts to said knowledge base;

said hypothesised changes include removal of facts from said knowledge base;

said hypothesised changes include removal of rules from said knowledge base; and

said abducer is operable, when performing reasoning operations involving said second reasoning steps;

(a) to pursue in a first phase reasoning operations wherein hypothesised changes consisting of adding facts are permitted but hypothesised changes consisting of removing facts or rules are not permitted;

(b) thereafter to pursue in a second phase reasoning operations wherein hypothesised changes consisting of adding facts and removing facts are permitted but hypothesised changes consisting of removing rules are not permitted; and

(c) subsequently to pursue in a third phase reasoning operations wherein hypothesised changes consisting of adding and removing facts and removing rules are permitted.

32. Apparatus according to claim 31, wherein:

(a) said first phase comprises a plurality of sub-phases in each of which reasoning operations involving only said first reasoning steps are first permitted and thereafter hypothesised changes consisting of adding facts are permitted but removing facts and rules is not permitted;

(b) said second phase comprises a plurality of sub-phases in each of which, firstly, reasoning operations involving only said first reasoning steps are permitted, then, hypothesised changes consisting of adding facts are permitted but removing facts and rules is not permitted, and thereafter hypothesised changes consisting of adding facts and removing facts are permitted but removing rules is not permitted; and

(c) said third phase comprises a plurality of sub-phases in each of which, firstly, reasoning operations involving only said first reasoning steps are permitted, then hypothesised changes involving the addition of facts are permitted but removing facts and rules is not permitted, thereafter hypothesised changes involving the addition or removal of facts are permitted but the removal of rules is not permitted, and subsequently hypothesised changes involving adding and removing facts and removing rules are permitted.

33. Apparatus according to claim 1, wherein said abducer is operable for performing successive said reasoning operations for obtaining proofs of successive goals, said abducer further being operable in each said successive reasoning operation to test for contradictions in the reasoning operation utilising both said record provided in the current reasoning operation and said record or records provided in the previous reasoning operation or operations in said succession.

34. Apparatus according to claim 1, including means for deductively checking proofs obtained by said abductive reasoning operations.

35. Apparatus according to claim 1, including means for hypothesising rules and recording said hypothesised rules, said abducer being further operable to perform said abductive reasoning operations relying upon said hypothesised rules.

36. Apparatus according to claim 1, wherein said abducer is operable to refer to data identifying non-abduceable facts and in response thereto to avoid providing proofs relying upon said non-abduceable facts.

37. Data processing apparatus comprising means for storing a knowledge base containing data defining a plurality of facts and/or rules;

and an abducer operable to perform deductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide in said memory means a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, said abducer being operable to define in said record facts whose unprovability has been relied upon in said reasoning operations and to prohibit abductive addition to said knowledge base of said defined unprovable facts during subsequent processing.

38. Data processing apparatus comprising means for storing a knowledge base containing data defining a plurality of facts and/or rules;

and an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing,

wherein, upon detection of a contradiction in a partially completed reasoning operation, processing of said partially completed reasoning operation is terminated or suspended, and

wherein said abducer is operable to perform said abductive reasoning operations by a process which includes a plurality of choice points from each of which processing may continue along any of a number of processing paths, and wherein upon a said termination or suspension of a reasoning operation, processing backtracks to a previous choice point and continues from said choice point along a processing path not previously used in said reasoning operation.

39. Data processing apparatus comprising means for storing a knowledge base containing data defining a plurality of facts and/or rules;

and an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesised changes in the knowledge base, wherein said abducer is operable to test for predetermined contradictions during said reasoning operation and, upon detection of a said predetermined contradiction in a partially completed reasoning operation, to determine whether processing of said partially completed reasoning operation may continue without contradiction by constraining variables in said data and/or in said goals, and to continue said processing with constraints on said variables to avoid said contradictions.

40. Apparatus according to claim 39, wherein processing of said partially completed reasoning operation is terminated or suspended when said abducer determines that said contradiction cannot be avoided by effecting said constraining.

41. Data processing apparatus comprising means for storing a knowledge base containing data defining a plurality of facts and/or rules;

and an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, wherein said abducer is operable to assign a cost to said reasoning steps and to determine on the basis of said assigned cost, a total cost for a reasoning operation,

wherein said abducer is operable to calculate the cumulative cost of the reasoning operation at intervals during said reasoning operation, and

wherein said abducer is operable at each said interval to compare the cumulative cost of the partially completed reasoning operation currently being processed to the cumulative cost of the least costly of any previously completed reasoning operations, and to terminate or suspend said partially completed reasoning operation if its cumulative cost has reached the cumulative cost of said least costly of said previously completed reasoning operations.

42. Apparatus according to claim 41, wherein said intervals are such that said abducer calculates the cumulative cost of the reasoning operation at each said second reasoning step.

43. Apparatus according to claim 41, wherein said abducer is operable to select, from different reasoning operations proving the same goal, that operation having total cost indicating that it is likely to provide the best solution.

44. Data processing apparatus comprising means for storing a knowledge base containing data defining a plurality of facts and/or rules;

and an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesised changes in the knowledge base, wherein said abducer is operable, when performing reasoning operations involving said second reasoning steps;

(a) to pursue in a first phase reasoning operations wherein hypothesised changes consisting of adding facts are permitted but hypothesised changes consisting of removing facts or rules are not permitted, said first phase comprising a plurality of sub-phases in each of which reasoning operations involving only said first reasoning steps are first permitted and thereafter hypothesised changes consisting of adding facts are permitted but removing facts and rules is not permitted;

(b) thereafter to pursue in a second phase reasoning operations wherein hypothesised changes consisting of adding facts and removing facts are permitted but hypothesised changes consisting of removing rules are not permitted, said second phase comprising a plurality of sub-phases in each of which, firstly, reasoning operations involving only said first reasoning steps are permitted, then, hypothesised changes consisting of adding facts are permitted but removing facts and rules is not permitted, and thereafter hypothesised changes consisting of adding facts and removing facts are permitted but removing rules is not permitted; and

(c) subsequently to pursue in a third phase reasoning operations wherein hypothesised changes consisting of adding and removing facts and removing rules are permitted, said third phase comprising a plurality of sub-phases in each of which, firstly, reasoning operations involving only said first reasoning steps are permitted, then hypothesised changes involving the addition of facts are permitted but removing facts and rules is not permitted, thereafter hypothesised changes involving the addition or removal of facts are permitted but the removal of rules is not permitted, and subsequently hypothesised changes involving adding and removing facts and removing rules are permitted.

45. Apparatus for producing control signals relating to a predetermined process or system, comprising:

(a) input means for receiving input signals from said process or system and for converting said signals into goals;

(b) data processing apparatus comprising means for storing a knowledge base containing data defining a plurality of facts and rules relating to said process or system, and an abducer operable to perform abductive reasoning operations for providing a proof of a said goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said rules containing premises in the form of commands defining control signals to be produced and said abducer being operable to provide said commands in output data dependent upon proof of a said goal; and

(c) output means arranged to receive from said data processing apparatus said output data and operable to convert said commands to said control signals,

wherein said input means comprises a look-up table containing a list of goals which may be supplied to the data processing apparatus, said input means being operable to apply said input signals to said look-up table to obtain therefrom a corresponding goal.

46. Apparatus according to claim 45, wherein said commands are made available for output as a consequence of a said second reasoning step in which data representing said command is relied upon in a hypothesized change in the knowledge base.

47. Apparatus according to claim 45, wherein said commands are made available as hypothesized addition of facts corresponding to said commands to the knowledge base.

48. Apparatus according to claim 45, including means for changing the data in the knowledge base in response to signals received by said input means and output data from said data processing apparatus.

49. Apparatus for producing control signals relating to a predetermined process or system, comprising:

(a) input means for receiving input signals from said process or system and for converting said signals into goals;

(b) data processing apparatus comprising means for storing a knowledge base containing data defining a plurality of facts and rules relating to said process or system, and an abducer operable to perform abductive reasoning operations for providing a proof of a said goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said rules containing premises in the form of commands defining control signals to be produced and said abducer being operable to provide said commands in output data dependent upon proof of a said goal; and

(c) output means arranged to receive from said data processing apparatus said output data and operable to convert said commands to said control signals,

wherein said output means comprises a look-up table defining control signals to be output dependent upon the output data from said data processing apparatus, said output means being operable to apply said output data to said look-up table for obtaining said control signals.

50. Apparatus for producing control signals relating to a predetermined process or system, in combination with a machine controlled thereby, said apparatus comprising:

(a) input means for receiving input signals from said process or system and for converting said signals into goals;

(b) data processing apparatus comprising means for storing a knowledge base containing base defining a plurality of facts and rules relating to said process or system, and an abducer operable to perform abductive reasoning operations for providing a proof of a said goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said rules containing premises in the form of commands defining control signals to be produced and said abducer being operable to provide said commands in output data dependent upon proof of a said goal; and

(c) output means arranged to receive from said data processing apparatus said output data and operable to convert said commands to said control signals,

and said machine including means for generating signals indicative of the status of at least a part or parts thereof and supplying said signals to said input means for conversion to goals, and control means arranged to receive said control signals from said control signal generating apparatus and operable to control said machine in accordance with said control signals.

51. Data processing apparatus comprising means for storing a knowledge base containing data defining a plurality of facts and/or rules;

and an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, wherein, upon detection of a contradiction in a partially completed reasoning operation, processing of said partially completed reasoning operation is terminated or suspended.

52. Data processing apparatus comprising means for storing a knowledge base containing data defining a plurality of facts and/or rules;

and an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, wherein, upon detection of a contradiction in a partially completed reasoning operation, said abducer is operable to determine whether processing of said partially completed reasoning operation may continue without contradiction by constraining variables in said data and/or in said goals, and to continue said processing with constraints on said variables to avoid said contradictions.

53. Data processing apparatus comprising means for storing a knowledge base containing data defining a plurality of facts and/or rules;

and an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, wherein said abducer is operable to assign a cost to said reasoning steps and to determine on the basis of said assigned cost, a total cost for a reasoning operation, wherein said abducer is operable to calculate the cumulative cost of the reasoning operation at intervals during said reasoning operation, and

wherein said abducer is operable at each said interval to compare the cumulative cost of the partially completed reasoning operation currently being processed to the cumulative cost of the least costly of any previously completed reasoning operations, and to terminate or suspend said partially completed reasoning operation if its cumulative cost has reached the cumulative cost of said least costly of said previously completed reasoning operations.

54. Data processing apparatus comprising means for storing a knowledge base containing data defining a plurality of facts and/or rules;

and an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, wherein said abducer is operable to seek said proof of a goal by pursuing reasoning operations involving only said first reasoning steps before seeking a said proof of a goal by pursuing reasoning operations involving said second reasoning steps.

55. Data processing apparatus comprising means for storing a knowledge base containing data defining a plurality of facts and/or rules;

and an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, wherein said abducer is operable to refer to data identifying non-abduceable facts and in response thereto to avoid providing proofs relying upon said non-abduceable facts.

56. A computer-readable memory medium storing instructions for causing a programmable apparatus to store a knowledge base containing data defining a plurality of facts and/or rules;

and to act as an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, said abducer being operable to define in said record facts or other statements whose presence in the knowledge base has been relied upon in said reasoning operations and to prohibit hypothesized or actual removal from said knowledge base of said defined facts or other statements during subsequent processing.

57. A computer-readable memory medium storing instructions for causing a programmable apparatus to store a knowledge base containing data defining a plurality of facts and/or rules;

and to act as an abducer operable to perform deductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide in said memory means a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, said abducer being operable to define in said record facts whose unprovability has been relied upon in said reasoning operations and to prohibit abductive addition to said knowledge base of said defined unprovable facts during subsequent processing.

58. A computer-readable memory medium storing instructions for causing a programmable apparatus to store a knowledge base containing data defining a plurality of facts and/or rules;

and to act as an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing,

wherein, upon detection of a contradiction in a partially completed reasoning operation, processing of said partially contemplated reasoning operation is terminated or suspended, and

wherein said abducer is operable to perform said abductive reasoning operations by a process which includes a plurality of choice points from each of which processing may continue along any of a number of processing paths, and wherein upon a said termination or suspension of a reasoning operation, processing backtracks to a previous choice point and continues from said choice point along a processing path not previously used in said reasoning operation.

59. A computer-readable member memory medium storing instructions for causing a programmable apparatus to store a knowledge base containing data defining a plurality of facts and/or rules;

and an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, wherein said abducer is operable to assign a cost to said reasoning steps and to determine on the basis of said assigned cost, a total cost for a reasoning operation,

wherein said abducer is operable to calculate the cumulative cost of the reasoning operation at intervals during said reasoning operation, and

wherein said abducer is operable at each said interval to compare the cumulative cost of the partially completed reasoning operation currently being processed to the cumulative cost of the least costly of any previously completed reasoning operations, and to terminate or suspend said partially completed reasoning operation if its cumulative cost has reached the cumulative cost of said least costly of said previously completed reasoning operations.

60. A computer-readable memory medium storing instructions for causing a programmable apparatus to produce control signals relating to a predetermined process or system, by performing a method comprising the steps of:

(a) receiving input signals from said process or system and for converting said signals into goals by referring to a look-up table containing a list of goals;

(b) storing a knowledge base containing data defining a plurality of facts and rules relating to said process or system, and acting as an abducer operable to perform abductive reasoning operations for providing a proof of a said goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said rules containing premises in the form of commands defining control signals to be produced and said abducer being operable to provide said commands in output data dependent upon proof of a said goal; and

(c) receiving said output data and converting said commands to said control signals.

61. A computer-readable memory medium storing instructions for causing a programmable apparatus to produce control signals relating to a predetermined process or system, and to perform a method comprising the steps of:

(a) receiving input signals from said process or system and for converting said signals into goals;

(b) storing a knowledge base containing data defining a plurality of facts and rules relating to said process or system, and acting as an abducer operable to perform abductive reasoning operations for providing a proof of a said goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said rules containing premises in the form of commands defining control signals to be produced and said abducer being operable to provide said commands in output data dependent upon proof of a said goal; and

(c) receiving said output data and operable to convert said commands to said control signals, by applying said output data to a look-up table defining control signals to be output dependent upon the output data.

62. A computer-readable memory medium storing instructions for causing a programmable apparatus to produce control signals relating to a predetermined process or system, and to perform, in combination with a machine controlled thereby, a method comprising the steps of:

(a) receiving input signals from said process or system and for converting said signals into goals;

(b) storing a knowledge base containing data defining a plurality of facts and rules relating to said process or system, and acting as an abducer operable to perform abductive reasoning operations for providing a proof of a said goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said rules containing premises in the form of commands defining control signals to be produced and said abducer being operable to provide said commands in output data dependent upon proof of a said goal; and

(c) receiving said output data and converting said commands to said control signals, and said machine including means for generating signals indicative of the status of at least a part or parts thereof and supplying said signals for conversion to goals, and control means arranged to receive said control signals and operable to control said machine in accordance with said control signals.

63. A computer-readable memory medium storing instructions for causing a programmable apparatus to perform a method comprising the steps of:

storing a knowledge base containing data defining a plurality of facts and/or rules; and

acting as an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, wherein, upon detection of a contradiction in a partially completed reasoning operation, processing of said partially completed reasoning operation is terminated or suspended.

64. A computer-readable memory medium storing instructions for causing a programmable apparatus to perform a method comprising the steps of:

storing a knowledge base containing data defining a plurality of facts and/or rules; and

acting as an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, wherein, upon detection of a contradiction in a partially completed reasoning operation, said abducer is operable to determine whether processing of said partially completed reasoning operation may continue without contradiction by constraining variables in said data and/or in said goals, and to continue said processing with constraints on said variables to avoid said contradictions.

65. A computer-readable memory medium storing instructions for causing a programmable apparatus to perform a method comprising the steps of:

storing a knowledge base containing data defining a plurality of facts and/or rules; and

acting as an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, wherein said abducer is operable to assign a cost to said reasoning steps and to determine on the basis of said assigned cost, a total cost for a reasoning operation, wherein said abducer is operable to calculate the cumulative cost of the reasoning operation at intervals during said reasoning operation, and

wherein said abducer is operable at each said interval to compare the cumulative cost of the partially completed reasoning operation currently being processed to the cumulative cost of the least costly of any previously completed reasoning operations, and to terminate or suspend said partially completed reasoning operation if its cumulative cost has reached the cumulative cost of said least costly of said previously completed reasoning operations.

66. A computer-readable memory medium storing instructions for causing a programmable apparatus to perform a method comprising the steps of:

storing a knowledge base containing data defining a plurality of facts and/or rules; and

acting as an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, wherein said abducer is operable to seek said proof of a goal by pursuing reasoning operations involving only said first reasoning steps before seeking a said proof of a goal by pursuing reasoning operations involving said second reasoning steps.

67. A computer-readable memory medium storing instructions for causing a programmable apparatus to perform a method comprising the steps of:

storing a knowledge base containing data defining a plurality of facts and/or rules; and

acting as an abducer operable to perform abductive reasoning operations for providing a proof of a goal, said reasoning operations including first reasoning steps relying upon the data in the knowledge base and second reasoning steps relying upon data representing hypothesized changes in the knowledge base, said abducer being operable to provide a record defining the data relied on in the reasoning steps, to test for contradictions in said reasoning operation utilizing said record, and to determine subsequent processing dependent on the result of the testing, wherein said abducer is operable to refer to data identifying non-abduceable facts and in response thereto to avoid providing proofs relying upon said non-abduceable facts.