Clause counter map inference engine

• US 5,230,061 A
• Filed: 01/02/1992
• Issued: 07/20/1993
• Est. Priority Date: 01/02/1992
• Status: Expired due to Fees

• Current Assignee: University of Akron
• Original Assignee: University of Akron
• Inventors: Welch, John T.
• Primary Examiner(s): MacDonald, Allen R.
• Application Number:
  US07/815,968
• Time in Patent Office: 565 Days
• Field of Search: 395/51, 395/61, 395/903, 395/904, 395/906, 364/148
• US Class Current: 706/46
• CPC Class Codes: G05B 19/052 Linking several PLC's
• CPC Class Codes: G06N 5/046 Forward inferencing; Production systems
• CPC Class Codes: Y10S 706/903 Control
• CPC Class Codes: Y10S 706/904 Manufacturing or machine, e.g. agricultural machinery, machine tool
• CPC Class Codes: Y10S 706/906 Process plant

Abstract

The invention describes a clause counter map inference engine which is an interpreter method based upon the Boolean form, in which Boolean inference is directly assisted by a programmable data structure. The system provides a translation of a series of Boolean logic functions into a compact map representation, which may then be used for Boolean inference by means of an interpreter algorithm or inference engine adapted to update function values based upon any changed input value. The invention provides a rule-based model for logical control systems having an imbeddable, event-chaining inference engine which is independent of the rule-based model. The time to complete a scan cycle of the system depends directly upon the number of inferences in an up-date interval between input and output variable changes, and the lengths of inference chains of events in the logic. The clause counter map inference engine generally provides a method of implementing logical functions where inferencing is at an optimum, thereby reducing inference processing time and providing a system which may take the place of other on-line control methods for implementation of a PLC, and also may be applied to expert and knowledge-based decision systems which utilize logic programming and rule search methods.

Claims

1. A clause counter map inference engine for implementation of logical control systems, comprising:

a map of logical rules defining a logical control system stored in computer memory, wherein said map represents a series of rules, each logical rule comprising a rule type code and main clause record, and at least one additional clause record, wherein adjacency of said clause records in said map indicates that the clause further from said rule type code is a member of the clause nearer said rule type code, except where said clause records are separated by a skip marker, wherein a set of clauses separated by skip markers are represented to be members of the clause adjacent to the said set of clauses in the direction of said rule type code,

said clause records comprising a clause connective denoting the logical nature of the clause, and at least one count field representing the number of members of the clause that are currently in a logical state determined by the conventions of said map,

said interference engine including a use list associated with at least one input or logical rule of said logical control system, which identifies in said map within computer memory said clauses containing said input or logical rule, and indicates the application of a logical negation to the use of said input or logical rule within said clause in which it is contained, said inference engine including storage means to store the current logical value of each input or logical rule of the application,

said interference engine associating each logical rule of said map with said current logical value by means of an identifying index number, said index number either being placed in said map adjacent to the rule type code, or a copy of said index number being present within a use list entry in the use lists associated with other of said logical rules, such entry representing the use of a rule in said other logical rules,

an inferencing algorithm adapted to compute all changes in said clause counts and said associated rule values resulting from a change of an input or logical rule value, said algorithm being directed to each effected clause by means of said use list associated with said changed input or rule value, and said algorithm using the old value and new value of said changed input or rule value to adjust said clause counts, and said algorithm determining whether said adjusted value of said clause counts represents a change of clause value, and if said change of clause value is indicated, said algorithm then moving to said clause record of said clause containing said adjusted clause, and said algorithm continuing in the described manner until a containing clause value is not affected or until the rule type code is reached within said map, and said algorithm determining by means of said index number, and said current value, if said logical rule represented by said map is changed, and said algorithm adapted to record each such change on a list of changes for processing and computation of changes in said clause counts and said associated rule values,

said list of changes comprising entries including an old logical value, a new logical value, and said identifying index number of said logical rule, and

said algorithm processing each of said input changes and resulting changes in said logical rules so as to produce output signals representative of adjustments made to clauses within said map.

2. The clause counter map inference engine of claim 1, wherein,

said rule type codes associated with said main clause and said at least one clause within said map are provided as a symbol representing a logical implication on the rule value, wherein permitted meanings of said rule type codes representing the rule types including "IF", wherein a true main cause implies a true rule value, while a false main clause makes no implication;

and "NOTIF", wherein a true main clause implies a false rule value; and

"IFF", wherein a true main clause implies a true rule value and a false main clause implies a false rule value.

3. The clause counter map inference engine of claim 1, wherein,

said clause connectives forming a part of said clauses include the Boolean binary operators "AND", "OR", "NAND", "NOR", and "EXOR", as conventionally defined.

5. The clause counter map inference engine of claim 1, wherein

said logical rules are 3-valued Boolean functions, and said inputs to said inference engine are 3-valued input variables, each 3-valued clause record having two counts associated therewith representing the clause states in 3-valued Boolean logic.

6. The clause counter map inference engine of claim 1, wherein,

said inferencing algorithm uses a queue, or first-in, first-out (FIFO) organization for said list of changes, processing the oldest change entries first, and said inferencing algorithm places a uniquely coded entry on the queue as a marker to represent the end of a cycle, and said inferencing algorithm, upon encountering said cycle marker entry as output of the queue, then records new input changes on the queue, immediately followed by a new cycle marker, to thereby affect synchronous operation of an on-line control model.

7. The clause counter map inference engine of claim 6, wherein, said inference engine also includes a pointer into said queue corresponding to each logical rule, and said inference algorithm includes the examination of this pointer before adding an entry to said queue for a change in the corresponding logical rule, whereupon said pointer being set, said algorithm uses said pointer to locate a prior recorded queue entry and transitively combines the new change with the previous change, leaving any net change in the queue, or removing any canceled change from the queue and clearing said pointer, or if said examined pointer is not set, but contains a null value meaning that no previous change of a corresponding logical rule is currently on the queue, then said algorithm sets the pointer to the location of the new queue entry, said algorithm also clearing all said pointer entries when a cycle marker is encountered, and said inference engine maintains the queue of changes in such a way that locations of queue entries in memory does not change, and said pointers remain accurate, as the queue advances.

8. The clause counter map inference engine of claim 1, wherein,

said inference engine further includes a table associated with each of said clause records, wherein said inference engine can apply a current change code and said clause count to look up both a modified count to be stored in said clause record, and a new change code to be applied to said containing clause or rule value, and a table wherein said inference engine can apply said current change code obtained from said clause record to look up said rule change code.

4. The clause counter map inference engine of claim wherein,

said logical rules are 2-valued Boolean functions, and said inputs to said inference engine are 2-valued input variables, each 2-valued clause record having one count associated therewith representing the clause state in 2-valued Boolean logic.