Depth-First Search For Target Value Problems

• US 20110004581A1
• Filed: 07/02/2009
• Published: 01/06/2011
• Est. Priority Date: 07/02/2009
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Kleer, Johan de, Schmidt, Tim, Price, Robert, Zhou, Rong, Kuhn, Lukas D.
• Granted Patent: US 8,364,629 B2
• Time in Patent Office: Days
• US Class Current: 706/55
• CPC Class Codes: G06F 17/11 for solving equations , e.g. nonlinear equations, general mathematical optimization problems optimization specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

A method for determining a target path for a model-based control system. The model-based control system includes a directed acyclic graph, where the directed acyclic graph includes a plurality of vertices interconnected by a plurality of edges. The method includes the steps of performing a depth-first search of the directed acyclic graph for the target path. The depth-first search is operative to return an explicit solution or an implicit solution, wherein the implicit solution is determined using a heuristic. The method further includes determining if the depth-first search returned an explicit solution or an implicit solution, and if the depth-first search returned an implicit solution, constructing the target path from the implicit solution. The method may further include constructing a pattern database.

Claims

1. A method for generating a pattern database for a model-based control system which employs target value searching, wherein said model-based control system includes a directed acyclic graph, wherein the directed acyclic graph includes a plurality of vertices interconnected by a plurality of edges, said method comprising the steps of:

(a) selecting one or more of the plurality of vertices which are ready for processing in an inverse topological order;

(b) processing the selected one or more of the plurality of vertices, wherein processing includes assigning a range bound to each of the selected one or more of the plurality of vertices; and

,

(c) repeating steps (a) to (b) until each of the plurality of vertices is processed, wherein the pattern database is computed in time linear to the number of vertices plus edges of the graph.

2. The method of claim 1, wherein said plurality of vertices include an initial vertex, a goal vertex, and one or more intermediate vertices, wherein said one or more intermediate vertices are both descendants of the initial vertex and ancestors of the goal vertex.

3. The method of claim 2, wherein the goal vertex is processed first.

4. The method of claim 1, wherein the range bound for each of the selected one or more of the plurality of vertices is determined by combining the range bound for each descendant.

5. The method of claim 1, wherein the range bound for each of the selected one or more of the plurality of vertices includes a lower bound and an upper bound of path lengths from the each of the selected one or more of the plurality of vertices to a goal vertex.

6. The method of claim 1, wherein the selected one or more of the plurality of vertices are not processed.

7. The method of claim 1, wherein the selected one or more of the plurality of vertices are ready for processing when all successors of the selected one or more of the plurality of vertices are processed.

8. A method for determining a target path for a model-based control system which employs target value searching, wherein said model-based control system includes a directed acyclic graph, wherein the directed acyclic graph includes a plurality of vertices interconnected by a plurality of edges, said method comprising the steps of:

(a) performing a depth-first search of the directed acyclic graph for the target path, wherein the depth-first search is operative to return an explicit solution or an implicit solution, wherein the implicit solution is determined using a heuristic;

(b) constructing the target path from the implicit solution or the explicit solution, wherein the target value search is a heuristic target-value search that has a memory requirement linear in the target value.

9. The method of claim 8, further comprising the step of creating a pattern database.

10. The method of claim 8, wherein the heuristic uses a pattern database.

11. The method of claim 8, wherein the depth-first search is bounded by the heuristic.

12. The method of claim 8, wherein said depth-first search includes a current search prefix and a lead vertex, wherein said current search prefix includes one or more connected vertices from the plurality of vertices, wherein said lead vertex is a deepest vertex in the current search prefix.

13. The method of claim 12, said depth-first search performing the steps of:

(i) determining whether the current search prefix is an explicit solution; and

,

(ii) if it is determined that the current search prefix is an explicit solution, returning the current search prefix as the target path and ending the depth-first search.

14. The method of claim 12, said depth-first search performing the steps of:

(i) determining whether the current search prefix is better than previous current search prefixes; and

,

(ii) if it is determined that the current search prefix is better than the previous current search prefixes, saving the current search prefix.

15. The method of claim 14, wherein the saved current search prefix is the implicit solution.

16. The method of claim 12, wherein said plurality of vertices include an initial vertex, a goal vertex, and one more intermediate vertices, wherein said one or more intermediate vertices are both descendants of the initial vertex and ancestors of the goal vertex.

17. The method of claim 16, wherein the explicit solution exists if the lead vertex is the goal vertex and the current search prefix includes a path length equal to a target value of the target path.

18. A model-based control system for controlling a production system, wherein said production system provides jobs and objectives to the model-based control system, said production system comprising a plant, said system comprising:

a planner operative to provide the production system with a plan, wherein said planner generates the plan using a depth-first target value search, wherein the depth-first target value search generates the plan with a failure probability most closely approximating a target value;

a system model operative to model the behavior of the plant; and

,

a diagnosis engine operative to estimate failure probabilities for plans and provide diagnostic guidance to the planner.

19. The model-based control system of claim 18, wherein the target value corresponds to the optimal amount of uncertainty in a plan outcome.

20. The model-based control system of claim 18, wherein the depth-first target value search generates a pattern database.