초록 ▼

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 i

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.

대표청구항 ▼

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

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; andperforming 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 connection graph is constructed as the intersection 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; andpropagating backward from the goal node to the start node, determining an upper bound value USm and a lower bound value LSm along incoming edges to each given node n in the connection graph from the given node's predecessor nodes m according to the equations: LSm=minSn∈SUC⁡(Sm)⁢[v⁡(aSm,Sn)+LSn]USm=maxSn∈SUC⁡(Sm)⁢[v⁡(aSm,Sn)+USn] where v(aSM,SN) is the at least one directional weight value of the edge from the predecessor node m to the given node n. 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′PI→Sn=T−v(pI→Sn), where v(pI→Sn) 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 USm and a lower bound value LSm of the successor node as follows: F⁡(pI→Sn)={0⁢:Δ⁢⁢TpI→Sn′⁢in⁢⁢a⁢⁢range⁢[L⁡(Sn),U⁡(Sn)]min⁢(TpI→Sn′-L⁡(Sn),TpI→Sn′-U⁡(Sn))⁢:otherwise,where ΔT′PI→Sn=[T′PI→Sn, T′PI→Sn]; (4) retaining all evaluated successor nodes in a list where all nodes are sorted by their outcome of function F; and(5) selecting one node with a minimal function F value and continuing with step (1) until the selected node is a goal node 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 based at least partially on the successor node sets. 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; andpropagating backward from the goal node to the start node, determining an upper bound value USm and a lower bound value LSm along incoming edges to each given node n in the connection graph from the given node's predecessor nodes m according to the equations: LSm=minSn∈SUC⁡(Sm)⁢[v⁡(aSm,Sn)+LSn]USm=maxSn∈SUC⁡(Sm)⁢[v⁡(aSm,Sn)+USn] where v(aSM,SN) is the at least one directional weight value of the edge from the predecessor node m to the given node n. 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′PI→Sn=T−v(pI→Sn), where v(pI→Sn) 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 USm and a lower bound value LSm of the successor node as follows: F⁡(pI→Sn)={0⁢:Δ⁢⁢TpI→Sn′⁢in⁢⁢a⁢⁢range⁢[L⁡(Sn),U⁡(Sn)]min⁢(TpI→Sn′-L⁡(Sn),TpI→Sn′-U⁡(Sn))⁢:otherwise,where ΔT′PI→Sn=[T′PI→Sn, T′PI→Sn]; (4) retaining all evaluated successor nodes in a list where all nodes are sorted by their outcome of function F; and(5) selecting one node with the minimal function F value and continuing with step (1) until the selected node is a goal node 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 based at least partially on the successor node sets. 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′PI→Sn=T−v(pI→Sn), where v(pI→Sn) 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 USm and a lower bound value LSm of the successor node as follows: F⁡(pI→Sn)={0⁢:Δ⁢⁢TpI→Sn′⁢in⁢⁢a⁢⁢range⁢[L⁡(Sn),U⁡(Sn)]min⁢(TpI→Sn′-L⁡(Sn),TpI→Sn′-U⁡(Sn))⁢:otherwise,where ΔT′PI→Sn=[T′PI→Sn, T′PI→Sn]; (4) retaining all evaluated successor nodes in a list where all nodes are sorted by their outcome of function F; and(5) selecting one node with the minimal function F value and continuing with step (1) until the selected node is a goal node 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 based at least partially on the successor node sets. 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: at least one processor: anda target value search component implemented using the at least one processor, comprising: a graph construction component implemented using the at least one processor, and 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 implemented using the at least one processor, and 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; anda search component implemented using the at least one processor, and 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 intersection 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 USm and a lower bound value LSm along incoming edges to each given node n in the connection graph from the given node's predecessor nodes m according to the equations: LSm=minSn∈SUC⁡(Sm)⁢[v⁡(aSm,Sn)+LSn]USm=maxSn∈SUC⁡(Sm)⁢[v⁡(aSm,Sn)+USn] where v(aSM,SN) is the at least one directional weight value of the edge from the predecessor node m to the given node n. 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′PI→Sn=T−v(pI→Sn), where v(pI→Sn) 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 USm and a lower bound LSm of the successor node as follows: F⁡(pI→Sn)={0⁢:Δ⁢⁢TpI→Sn′⁢in⁢⁢a⁢⁢range⁢[L⁡(Sn),U⁡(Sn)]min⁢(TpI→Sn′-L⁡(Sn),TpI→Sn′-U⁡(Sn))⁢:otherwise, where ΔT′PI→Sn=[T′PI→Sn, T′PI→Sn], (4) retaining all evaluated successor nodes in a list where all nodes are sorted by their outcome of function F, and(5) selecting one node with the minimal function F value and continuing with step (1) until the selected node is a goal node 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. 13. The system of claim 12, wherein the search component comprises a pruning component implemented using the at least one processor, and 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′PI→Sn=T−v(pI→Sn), where v(pI→Sn) 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 USm and a lower bound LSm of the successor node as follows: F⁡(pI→Sn)={0⁢:Δ⁢⁢TpI→Sn′⁢in⁢⁢a⁢⁢range⁢[L⁡(Sn),U⁡(Sn)]min⁢(TpI→Sn′-L⁡(Sn),TpI→Sn′-U⁡(Sn))⁢:otherwise, where ΔT′PI→Sn=[T′PI→Sn, T′PI→Sn], (4) retaining all evaluated successor nodes in a list where all nodes are sorted by their outcome of function F, and(5) selecting one node with the minimal function F value and continuing with step (1) until the selected node is a goal node 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. 15. The system of claim 14, wherein the search component comprises a pruning component implemented using the at least one processor, and 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.