Method and system for rapid evaluation of logical expressions

• US 7,636,697 B1
• Filed: 01/29/2007
• Issued: 12/22/2009
• Est. Priority Date: 01/29/2007
• Status: Expired due to Fees

• Current Assignee: Wei Yen
• Original Assignee: AiLive, Inc.
• Inventors: Reynolds, Stuart, Tu, Xiaoyuan, Funge, John, Wright, Ian, Yen, Wei, Dobson, Daniel, Musick, Charles
• Primary Examiner(s): Holmes; Michael B
• Application Number:
  US11/699,201
• Time in Patent Office: 1,058 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 perform operations of;

obtaining a set of logical expressions, at least some of the logical expressions associated with a time sequence, each of the logical expressions associated with one or more primitives that at any time have one or more possible values, wherein the logical expressions are expressed in one or more directed acyclic graphs, each including at least one root node, at least one leaf node, and at least one association between a non-leaf node and a leaf node, node is associated with a set of the logical expressions that are presumed true, a subset of true logical expressions being a possibly empty subset the logical expressions, and each non-leaf node is further associated with one of the primitives associated with one of these logical expressions; and

each edge between any two nodes is associated with one of the primitive associated with a node at a tail of the edge, and at any time, a path through each of the directed acyclic graphs from a root node is determined by recursively following the edge that corresponds to the value of the primitive at a given non-leaf node; and

taking a union of the logical expressions expressed in the directed acyclic graphs and traversing the directed acyclic graphs to yields the subset of the true logical expressions.

2. A computing device as in claim 1, further comprising a cache of the value of at least one primitive, the value having been determined at a node visited as part of traversing through at least some of the acyclic graphs and made available to determine the edge to follow for a subsequent node visited and associated with the primitive.

3. A computing device as in claim 2, further comprising a cache of the value of at least one primitive that is retained even after the subset of true logical expressions has been determined so that the value of at least one primitive facilitates a calculation of a different subset of true logical expressions later.

4. A computing device as in claims 1, 2 or 3, wherein the subset of true logical expressions is determined with a maximum number of times the primitives are evaluated, the maximum number is less than or equal to a total number of the directed acyclic graphs.

5. A computing device as in claim 4, wherein the subset of true logical expressions is determined in real time or near real-time.

6. A computing device as in claim 4, wherein the subset of true logical expressions is determined with any primitive being evaluated at most once.

7. A computing device as in claim 4, wherein the subset of true logical expressions is determined in time that is typically logarithmic, but at least sub-linear, in the number of logical expressions.

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

9. A computing device as in claim 8, wherein the computing device facilitates real-time or near real-time learning in accordance with the logical expressions.

10. A computing device as in claim 9, 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.

11. A computing device as in claim 10, wherein the logical expressions are about a member of the group comprising:

a portion of a real world;

all or a portion of an abstraction of the real world;

a portion of a virtual world; and

all or a portion of an abstraction of the virtual world.

12. A computing device as in claim 1, further comprising converting each of the logical expressions a disjunctive normal form (DNF).

13. A computing device as in claim 12, 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.

14. A computing device as in claim 11, wherein at least one of those 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 a state 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.

15. A computing device as in claim 14, wherein

the computing device facilitates decision making and/or learning in robotics applications.

16. A computing device as in claim 14, wherein the computing device facilitates decision making and/or learning in OLAP applications.

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

maintaining data in a memory space representing a set of logical expressions, at least some of the logical expressions associated with a time sequence, each of the logical expressions associated with one or more primitives that at any time have one of one or more values; and

operating a computing device to read one or more directed acyclic graphs, each including at least one root node, at least one leaf node, and at least one association between a non-leaf node and a leaf node, wherein each node is associated with a set of the logical expressions that are presumed true, the set of true logical expressions being a possibly empty subset of the logical expressions, and each non-leaf node is further associated with one of the primitives associated with one of the logical expressions, each edge between any two nodes is associated with one of values of the primitives associated with the node at a tail of an edge, at any time, a path through each of the directed acyclic graphs from a root node is determined by recursively following the edge that corresponds to one of the values of the primitives at a given non-leaf node; and

taking a union of the logical expressions expressed in the directed acyclic graphs and traversing the directed acyclic graphs to yield the subset of the true logical expressions.

18. A method as in claim 17, further comprising caching a value of at least one primitive, the value having been determined at a node visited as part of traversing the path through at least one of the acyclic graphs and made available to determine the edge to follow for a subsequent node visited and associated with the same primitive.

19. A method as in claim 18, further comprising retaining a cache of at least one primitive even after the subset of true logical expressions has been determined.

20. A method as in claim 17, further comprising determining the subset of true logical expressions, with a maximum number of times a primitive is evaluated, the maximum number being less than or equal to a number of the directed acyclic graphs.

21. A method as in claim 20, further comprising determining the subset of true logical expressions in real time or near real-time.

22. A method as in claim 20, further comprising determining the subset of true logical expressions with a primitive being evaluated at most once.

23. A method as in claim 20, further comprising determining the subset of true logical expressions in an amount of time that is logarithmic in a number of the logical expressions.

24. A method as in claim 20, further comprising determining the subset of true logical expressions in an amount of time that is sub-linear in the number of logical expressions.

25. A method as in claim 21, further comprising decision making in real-time or near real-time.

26. A method as in claim 21, further comprising learning in real-time or near real-time.

27. A method as in claim 21, further comprising setting the set of logical expressions be a set of tests from a collection of specialists and a subset of true tests determined 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.

28. A method as in claim 17, wherein the logical expressions are about a member of a group comprising:

a portion of a real world;

all or a portion of an abstraction of the real world;

all or a portion of a virtual world; and

all or a portion of an abstraction of the virtual world.

29. A method as in claim 28, wherein at least one of the logical expressions is a member of the group comprising:

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

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

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

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

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

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

a statement about some 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 some relationship between a first object represented within the world abstraction, or a portion thereof, and a second object represented within the world abstraction, or a portion thereof; and

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

30. A method as in claim 29, further comprising decision making and/or learning in robotics applications.

31. A method as in claim 29, further comprising decision making and/or learning in OLAP applications.

32. A method as in claim 29, further comprising decision making and/or learning in video game applications.

33. A software product in a computer readable medium for rapidly evaluating logical expressions, the software product comprising:

program code for obtaining a set of logical expressions to facilitate making a decision in a video game, at least some of the logical expressions associated with a time sequence, each of the logical expressions associated with one or more primitives that at any time have one or more possible values, wherein the logical expressions are expressed in one or more directed acyclic graphs, each including at least one root node, at least one leaf node, and at least an association between a non-leaf node and a leaf node, each node is associated with a set of the logical expressions that are presumed true, a subset of true logical expressions being an empty subset the logical expressions, and each non-leaf node is further associated with one of the primitives associated with one of the logical expressions; and

each edge between any two nodes is associated with one of the primitives associated with a node at a tail of the edge, and at any time, a path through each of the directed acyclic graphs from a root node is determined by recursively following the edge that corresponds to a value of one of the primitives at a given non-leaf node; and

program code for taking a union of the logical expressions expressed in the directed acyclic graphs and traversing the directed acyclic graphs to yield the subset of the true logical expressions.

34. The software product as recited in claim 33, wherein the decision making includes context learning used to learn a play style of a human player.

35. The software product as recited in claim 34, wherein one or more of the logical expressions define a set of input features to a machine learning algorithm, the each of the logical expression is constructed from logical connectives, relational operators, parentheses and the primitives, where truth or falsity of each of the logical expressions is determined by current values of the primitives and standard rules of mathematical logic, the primitive values change over time.