Methods and systems for target value path identification
AssigneePalo Alto Research Center Incorporated
InventorsLukas D. Kuhn, Tim Schmidt, Robert Price, Johan de Kleer, Rong Zhou, Minh Binh Do
Life of this patent
Estimating the term…
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.
Claims18
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.
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:
- and
- a 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;
- and
- a 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.
Dependencies are inferred from the claim text.