METHODS AND SYSTEMS FOR TARGET VALUE PATH IDENTIFICATION

• US 20100010952A1
• Filed: 03/23/2009
• Published: 01/14/2010
• Est. Priority Date: 07/10/2008
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Schmidt, Tim, Price, Robert, Do, Minh Binh, Zhou, Rong, Kuhn, Lukas D., de Kleer, Johan
• Granted Patent: US 8,266,092 B2
• Time in Patent Office: Days
• US Class Current: 706/47
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

Target value search methods and systems are presented for solving a target value path problem to identify a path or paths in a graph in which a connection graph is created and upper and lower bound values are determined for each node in the connection graph, and a first best search is performed to identify a path or paths from a starting node to a goal node having a path value closest to the target value.

Claims

1. A method for identifying at least one path having a value closest to a target value, the method comprising:

providing a starting graph with a plurality of nodes and a plurality of edges between pairs of nodes, each edge having at least one positive directional weight value, the nodes individually comprising at least one property value and representing a physical location or an operational state of a machine or system;

constructing a successor graph based at least partially on the starting graph and a start node;

constructing a predecessor graph based at least partially on the starting graph and at least one goal node;

constructing a connection graph based at least partially on the successor and predecessor graphs;

determining upper and lower bound values for each given node of the connection graph based at least partially on the weight values of all remaining paths from the given node to the at least one goal node; and

performing a best first search using the upper and lower bound values to identify at least one path from the start node to the goal node having a path value closest to a non-zero target value.

2. The method of claim 1, wherein the construction graph is constructed as the union of the successor and predecessor graphs.

3. The method of claim 2, wherein determining upper and lower bounds values for each given node of the connection graph comprises:

initializing the upper and lower bound values of the at least one goal node to zero; and

propagating backward from the goal node to the start node, determining an upper bound value U_Sm and a lower bound value L_Sm along incoming edges to each given node n in the connection graph from the given node'"'"'s predecessor nodes m according to the equations;

4. The method of claim 3, wherein performing the best first search comprises:

searching forward from the start node to the goal node, performing a node evaluation for each given node n according to the following node evaluation;

(1) generating a set of successor nodes for each given node n;

(2) for each successor node of a given set, determining the successor node value T′

<sub>pI→

sn</sub>=T−

v(p<sub>I→

Sn</sub>), where v(p<sub>I→

Sn</sub>) is the weight value of the edge from the given node n to the given successor node and T is the target value;

(3) for each successor node of a given set, evaluating a function F using an upper bound value U_Sm and a lower bound value L_Sm of the successor node as follows;

5. The method of claim 1, wherein determining upper and lower bounds values for each given node of the connection graph comprises:

initializing the upper and lower bound values of the at least one goal node to zero; and

propagating backward from the goal node to the start node, determining an upper bound value U_Sm and a lower bound value L_Sm along incoming edges to each given node n in the connection graph from the given node'"'"'s predecessor nodes m according to the equations;

6. The method of claim 5, wherein performing the best first search comprises:

propagating forward from the start node to the goal node, performing a node evaluation for each given node n according to the following node evaluation;

(1) generating a set of successor nodes for each given node n;

(2) for each successor node of a given set, determining the successor node value T′

<sub>pI→

sn</sub>=T−

v(p<sub>I→

Sn</sub>), where v(p<sub>I→

Sn</sub>) is the weight value of the edge from the given node n to the given successor node and T is the target value;

(3) for each successor node of a given set, evaluating a function F using an upper bound value U_Sm and a lower bound value L_Sm of the successor node as follows;

7. The method of claim 1, wherein performing the best first search comprises:

propagating forward from the start node to the goal node, performing a node evaluation for each given node n according to the following node evaluation;

(1) generating a set of successor nodes for each given node n,

(2) for each successor node of a given set, determining the successor node value T′

<sub>pI→

sn</sub>=T−

v(p<sub>I→

Sn</sub>), where v(p<sub>I→

Sn</sub>) is the weight value of the edge from the given node n to the given successor node and T is the target value,

(3) for each successor node of a given set, evaluating a function F using an upper bound value U_Sm and a lower bound value L_Sm of the successor node as follows;

8. The method of claim 7, wherein performing a node evaluation for each given node n further comprises selectively pruning the set of successor nodes to speed up the best first search.

9. A system for identifying at least one path having a value closest to a target value in a starting graph that includes a plurality of nodes representing a physical location or an operational state of a machine or system and having at least one property value, and a plurality of edges between pairs of nodes, each edge having at least one positive directional weight value, the system comprising:

a target value search component, comprising;

a graph construction component operative to construct a connection graph based at least partially on the starting graph, a start node, and at least one goal node,

a computation component operative to determine upper and lower bound values for each given node of the connection graph based at least partially on the weight values of all paths from the given node to the at least one goal node; and

a search component operative to perform a best first search using the upper and lower bound values to identify at least one path from the start node to the goal node having a path value closest to a non-zero target value.

10. The system of claim 9, wherein the graph construction component is operative to construct a successor graph based at least partially on the starting graph and the start node, to construct a predecessor graph based at least partially on the starting graph and the at least one goal node, and to construct the connection graph as the union of the successor and predecessor graphs.

11. The system of claim 9, wherein the computation component is operative to initialize the upper and lower bound values of the at least one goal node to zero, and propagating backward from the goal node to the start node, to determine an upper bound value U_Sm and a lower bound value L_Sm along incoming edges to each given node n in the connection graph from the given node'"'"'s predecessor nodes m according to the equations:

12. The system of claim 11, wherein the search component is operative to perform a node evaluation for each given node n propagating forward from the start node to the goal node, according to the following node evaluation by

(1) generating a set of successor nodes for each given node n,

(2) for each successor node of a given set, determining the successor node value T′

<sub>pI→

sn</sub>=T−

v(p<sub>I→

sn</sub>), where v(p<sub>I→

Sn</sub>) is the weight value of the edge from the given node n to the given successor node and T is the target value,

(3) for each successor node of a given set, evaluating a function F using an upper bound U_Sm and a lower bound L_Sm of the successor node as follows;

13. The system of claim 12, wherein the search component comprises a pruning component operative to selectively prune the set of successor nodes to speed up the best first search.

14. The system of claim 9, wherein the search component is operative to perform a node evaluation for each given node n propagating forward from the start node to the goal node, according to the following node evaluation by

(1) generating a set of successor nodes for each given node n,

(2) for each successor node of a given set, determining the successor node value T′

<sub>pI→

sn</sub>=T−

v(p<sub>I→

Sn</sub>), where v(p<sub>I→

Sn</sub>) is the weight value of the edge from the given node n to the given successor node and T is the target value,

(3) for each successor node of a given set, evaluating a function F using an upper bound U_Sm and a lower bound L_Sm of the successor node as follows;

15. The system of claim 14, wherein the search component comprises a pruning component operative to selectively prune the set of successor nodes to speed up the best first search.

16. The system of claim 9:

wherein the starting graph is a belief model of a diagnosis engine of a model-based control system for constructing plans for operating a production plant to achieve one or more production goals, the starting graph including a plurality of nodes representing a state of the production plant and a plurality of edges representing actions by one or more plant resources to transition the plant state from one graph node to another, each edge having at least one positive directional weight value defining a failure probability associated with the action having a value between 0 and 1 inclusive;

wherein the target value search component is incorporated into the diagnosis engine and the search component performs a best first search to identify at least one production plan to achieve a given production goal that has a failure probability value closest to a non-zero target value.

17. The system of claim 16, wherein the target value is 0.5.

18. The system of claim 9, wherein the system is a consumer search system.