Methods and systems for target value path identification
IPC분류정보
국가/구분
United States(US) Patent
등록
국제특허분류(IPC7판)
G06F-017/00
G06N-007/00
G06N-007/08
출원번호
US-0409235
(2009-03-23)
등록번호
US-8266092
(2012-09-11)
발명자
/ 주소
Kuhn, Lukas D.
Schmidt, Tim
Price, Robert
de Kleer, Johan
Zhou, Rong
Do, Minh Binh
출원인 / 주소
Palo Alto Research Center Incorporated
대리인 / 주소
Fay Sharpe LLP
인용정보
피인용 횟수 :
8인용 특허 :
64
초록▼
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′inarange[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′inarange[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′inarange[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′inarange[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′inarange[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.
연구과제 타임라인
LOADING...
LOADING...
LOADING...
LOADING...
LOADING...
이 특허에 인용된 특허 (64)
Zuo,Lei; Slotine,Jean Jacques E., Active control vibration isolation using dynamic manifold.
Skaanning, Claus; Jensen, Finn V.; Kjærulff, Uffe; Pelletier, Paul A.; Jensen, Lasse Rostrup; Parker, Marilyn A.; Bogorad, Janice L., Automated diagnosis of printer systems using bayesian networks.
Alvarez,Bruce H.; Bergeron,Steven R.; Cavanaugh,William J.; McClintock,Michael S., Automated knowledge system for equipment repair based on component failure history.
Ruml,Wheeler; Lofthus,Robert M.; Root,Ronald J.; Fromherz,Markus P J.; Webster,Marc W., Exception handling in manufacturing systems combining on-line planning and predetermined rules.
Takeuchi Kenji (Murrysville PA) Gagnon Andre F. (Monroeville PA) Cheung Augustine C. (Murrysville PA) Meyer Philip E. (Penn Hills PA), Expert system for surveillance, diagnosis and prognosis of plant operation.
Chester,Daniel L.; Daniel,Stephen L.; Fickelscherer,Richard J.; Lenz,Douglas H., Method and system of monitoring, sensor validation and predictive fault analysis.
Pechtl,Peter Anton; Posch,Martin; Davari,Bijan; Dieleman,Marco Robert, Methods and apparatus for optimizing combined cycle/combined process facilities.
Teran Conrad K. (Puerto La Cruz-Edo Anzoatequi TX VEX) Grotewold Delbert (The Woodlands TX), Process optimization and control system that plots inter-relationships between variables to meet an objective.
Huelsman, David L.; Love, Sharon E.; Mair, Douglas M., Rule processing methods for automating a decision and assessing satisfiability of rule-based decision diagrams.
Bonissone Piero Patrone ; Chen Yu-To, System and method for providing raw mix proportioning control in a cement plant with a fuzzy logic supervisory controller.
Hayashi, Yoshiharu; Fujimura, Hidekazu; Furukawa, Masao; Shimizu, Katsuhito; Hayasaka, Yasushi, System for aiding the preparation of operation and maintenance plans for a power generation installation.
Hayashi, Yoshiharu; Fujimura, Hidekazu; Furukawa, Masao; Shimizu, Katsuhito; Hayasaka, Yasushi, System for aiding the preparation of operation and maintenance plans for a power-generation installation.
Krist Johannes H. A. (Terneuzen NLX) Lapre Martine R. (Knokke-Heist BEX) Wassink Steven G. (Axel NLX) Koolen Johannes L. A. (Terneuzen NLX), System for real time optimization.
Krist Johannes H. A.,NLX ; Lapere Martine R.,BEX ; Wassink Steven Groot,NLX ; Koolen Johannes L. A.,NLX ; Sprenkels Jacobus C. M.,NLX, System for real-time economic optimizing of manufacturing process control.
Cooper, Jared Klineman; Golden, Samuel William; Noffsinger, Joseph Forrest; Kumar, Ajith Kuttannair; Plotnikov, Yuri Alexeyevich; Fries, Jeffrey Michael; Ehret, Steven Joseph; Nagrodsky, Nicholas David, Route examination system and method.
Otsubo, Tom; Daum, Wolfgang; Stull, Craig Alan; Hann, Gregory; Danner, Phillip, System, method and computer software code for determining a mission plan for a powered system using signal aspect information.
Kapp, Kevin L; Eldredge, David Allen; Foy, Robert James; Wakeman, Joseph Daniel; Brand, John William, Systems and methods for operating a vehicle system in response to a plan deviation.
Kumar, Ajith Kuttannair; Shaffer, Glenn Robert; Houpt, Paul Kenneth; Movsichoff, Bernardo Adrian; Chan, David So Keung; Eker, Sukru Alper, Trip optimization system and method for a train.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.