Method and system for rapid evaluation of logical expressions

• US 7,917,455 B1
• Filed: 11/20/2009
• Issued: 03/29/2011
• Est. Priority Date: 01/29/2007
• Status: Active Grant

• Current Assignee: AiLive, Inc.
• Original Assignee: AiLive, Inc.
• Inventors: Reynolds, Stuart, Tu, Xiaoyuan, Funge, John, Wright, Ian, Yen, Wei, Dobson, Daniel, Musick, JR., Charles
• Primary Examiner(s): HOLMES, MICHAEL B
• Application Number:
  US12/622,907
• Time in Patent Office: 494 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G06N 20/00 Machine learning

Abstract

Methods and systems capable of determining which subset of a set of logical expressions are true with relatively few evaluations of the primitives that together with any standard logical connectives, make up the logical expressions. A plurality of directed acyclic graphs, each graph including at least one root node, at least one leaf node, and at least one non-leaf node associated with a leaf node. Each node is associated with a, possibly empty, subset of presumed to be true logical expressions. Each non-leaf node is associated with one of the primitives mentioned in any of the logical expressions. Edges are defined between two of the nodes, each edge being associated with a possible value, or range of possible values, of the primitive associated with the node at the tail of the edge. Paths are defined through each of the directed acyclic graphs from a root node to a leaf node by recursively following each edge corresponding to the current value of the primitive at a selected non-leaf node. Lastly, subsets of logical expressions associated with the nodes on the defined paths are collated to yield a subset of logical expressions that are true.

Claims

1. A computing device for rapidly evaluating logical expressions, the computing device comprising:

a memory space for storing code;

a processor, coupled to the memory space, executing the code to cause the computing device to repeatedly perform operations of;

determining a set of primitives defining some or all of a current state of a model of a virtual or real world;

accessing a set of logical expressions including the primitives, each of the logical expressions being either a true or false statement about the current state of the model, wherein a union of the logical expressions is expressed in one or more directed acyclic graphs; and

computing which of the logical expressions are true statements about the current state of the model by traversing the one or more directed acyclic graphs once exactly in one path from a root node to a leaf node in the one or more directed acyclic graphs.

2. The computing device as recited in claim 1, wherein the one or more directed acyclic graphs include at least one node associated with one of the primitives used in at least one of the logical expressions, a value of the one of the primitives being evaluated to reflect the current state of the model when the node is visited in traversing the one or more directed acyclic graphs.

3. The computing device as recited in claim 2, further comprising a memory space to cache the value of each of the primitives that has been evaluated so that within a computational cycle, traversals of additional directed acyclic graphs need not re-compute the value of the previously evaluated primitives.

4. The computing device as recited in claim 2, wherein a subset of the logical expressions that are true is determined with computational effort proportional to a number of times the primitives are evaluated.

5. The computing device as recited in claim 4, wherein the subset of the true logical expressions is determined in real time.

6. The computing device as in claim 4, wherein computing of the subset of the true logical expressions requires evaluating any one of the primitives at most once.

7. The computing device as recited in claim 1, wherein the model includes a plurality of characters described by one or more of the logical expressions, actions of the characters being contingent upon which of the logical expressions being true.

8. The computing device as recited in claim 1, wherein the computing device is executing a video game and is configured to facilitate real-time or near real-time decision making in accordance with a subset of the logical expressions that are true.

9. The computing device as recited in claim 8, wherein the computing device facilitates real-time learning in response to the logical expressions.

10. The computing device as recited in claim 9, wherein the set of the logical expressions is a set of tests from a collection of specialists, a set of true tests is a subset of the tests that determine a set of active experts, wherein each of the specialists is an expert paired with one of the tests such that whenever the one of the tests is determined to be true, the expert is said to be active, wherein the expert is a subroutine to be queried to suggest a particular action, behavior or course of action in video game.

11. The computing device as in claim 10, wherein the primitives are used in a video game to indicate a set of surrounding parameters or a status of an object, the set of surrounding parameters includes, what other objects are near the object, and the status includes at least a health level of the object.

12. The computing device as in claim 10, wherein at least one of the logical expressions is a member of a group comprising:

a statement about a state of a real world, or a portion thereof;

a statement about some of an abstraction of the real world, or a portion thereof;

a statement about a state of a virtual world, or a portion thereof;

a statement about a state of an abstraction of some virtual world, or a portion thereof;

a statement about a state of an object represented within the real world, or a portion thereof;

a statement about a state of the object represented within the abstraction of the real word, or a portion thereof;

a statement about a relationship between a first object represented within the real world, or a portion thereof, and a second object represented within the real world, or a portion thereof;

a statement about a relationship between the first object represented within the abstraction of the real world, or a portion thereof, and a second object represented within the abstraction of the real world, or a portion thereof;

or

a statement asserted to be a combination, conjunction, or disjunction of one or more of the above.

13. A method for rapidly evaluating logical expressions, the method comprising:

maintaining data in a memory space representing a model of a virtual or a real world, and a set of logical expressions including primitives, each of the logical expressions being either true or false about a current state of the model, wherein a union of the logical expressions is expressed in one or more directed acyclic graphs;

computing which of the logical expressions are true statements about the current state of the model by traversing the one or more directed acyclic graphs once exactly in one path from a root node to a leaf node in the one or more directed acyclic graphs.

14. The method as recited in claim 13, wherein the one or more directed acyclic graphs include at least one node associated with one of the primitives used in at least one of the logical expressions, a value of the one of the primitives being evaluated to reflect the current state of the model when the node is visited in traversing the one or more directed acyclic graphs.

15. The method device as recited in claim 14, further caching in a memory space the value of each of the primitives that has been evaluated so that within a computational cycle, traversals of additional directed acyclic graphs need not re-compute the value of the previously evaluated primitives.

16. The method as recited in claim 14, wherein a subset of the logical expressions that are true is determined with computational effort proportional to a number of times the primitives are evaluated.

17. The method as recited in claim 16, wherein the subset of the true logical expressions is determined in real time.

18. The method as in claim 16, wherein any one of the primitives is evaluated at most once.

19. The method as recited in claim 13, wherein the model includes a plurality of characters described by one or more of the logical expressions in a subset of the logical expressions that are true, actions of the characters being contingent upon which of the logical expressions being true.

20. The method as recited in claim 13, wherein a computing device is executing a video game and configured to facilitate real-time or near real-time decision making in accordance with the subset of true logical expressions.

21. The method as recited in claim 20, wherein the computing device facilitates real-time learning in response to the logical expressions.

22. The method as recited in claim 21, wherein the set of logical expressions is a set of tests from a collection of specialists, a set of true tests is a subset of the tests that determine a set of active experts, wherein each of the specialists is an expert paired with one of the tests such that whenever the one of the tests is determined to be true, the expert is said to be active, wherein the expert is a subroutine to be queried to suggest a particular action, behavior or course of action in video game.

23. The method as in claim 22, wherein the primitives are used in a video game to indicate a set of surrounding parameters or a status of an object, the set of surrounding parameters includes, what other objects are near the object, and the status includes at least a health level of the object.

24. The method as in claim 22, wherein at least one of the logical expressions is a member of a group comprising:

a statement about a state of a real world, or a portion thereof;

a statement about some of an abstraction of the real world, or a portion thereof;

a statement about a state of a virtual world, or a portion thereof;

a statement about a state of an abstraction of some virtual world, or a portion thereof;

a statement about a state of an object represented within the real world, or a portion thereof;

a statement about a state of the object represented within the abstraction of the real word, or a portion thereof;

a statement about a relationship between a first object represented within the real world, or a portion thereof, and a second object represented within the real world, or a portion thereof;

a statement about a relationship between the first object represented within the abstraction of the real world, or a portion thereof, and a second object represented within the abstraction of the real world, or a portion thereof;

or

a statement asserted to be a combination, conjunction, or disjunction of one or more of the above.