Methods and systems for active diagnosis through logic-based planning

• US 8,145,334 B2
• Filed: 02/02/2009
• Issued: 03/27/2012
• 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: Do, Minh Binh, Verdes, Hector Luis Palacios, Zhou, Rong, Kuhn, Lukas Daniel, de Kleer, Johan
• Primary Examiner(s): Chaki, Kakali
• Assistant Examiner(s): Booker, Kelvin
• Application Number:
  US12/364,006
• Publication Number:
  US 20100010657A1
• Time in Patent Office: 1,149 Days
• Field of Search: 700/103, 700/80, 700/79, 700/99, 700/97, 700/9, 700/29, 700/30, 700/109, 706/62, 716/106, 702/84, 702/182
• US Class Current: 700/103
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: Y02P 90/80 Management or planning
• CPC Class Codes: Y10S 706/906 Process plant
• CPC Class Codes: Y10S 706/912 Manufacturing or machine, e.g. agricultural machinery, machine tool
• CPC Class Codes: Y10S 706/914 Process plant

Abstract

A control systems and methods are presented for controlling a production system, in which a model-based planner includes a formulation, such as a SAT formulation representing possible actions in the production, with a solver being used to provide a solution to the formulation based at least partially on production and diagnostic goals and the current plant condition, and a translation component translates the solution into a plan for execution in the plant.

Claims

1. A control system for controlling operation of a production system with a plant that can achieve one or more production goals by execution of plans using one or more plant resources, the control system comprising:

at least one processor;

a plant model including a model of the plant;

a diagnosis component implemented using the at least one processor and operatively coupled with the plant to determine a current plant condition based at least partially on a previously executed plan, at least one corresponding observation from the plant, and the plant model; and

a planner operative to receive at least one diagnostic goal from the diagnosis component and at least one production goal, the planner comprising;

a formulation representing possible actions in the plant including;

constraints and variables for each action to transition the plant from a starting state to a goal state defined by at least one production goal, and

an objective function evaluating the number of plant resources suspected of being fault that are used in a given solution,

a solver implemented using the at least one processor and operative to provide at least one solution to the formulation based at least partially on the at least one production goal, at least one diagnostic goal, and the current plant condition, and

a translation component operative to translate the solution into a plan and to provide the plan to the plant for execution;

wherein the planner is operative to select at least one solution for which the number of suspected resources used in the solution is closest to half of the suspected plant resources.

2. The control system of claim 1, wherein the solver is a SAT solver.

3. The control system of claim 2:

wherein the constraints and variables for each plant state are Boolean;

wherein the current plant condition includes an indication of which plant resources are suspected of being faulty;

wherein the formulation further includes an objective function evaluating the number of plant resources suspected of being faulty that are used in a given solution.

4. The control system of claim 2, wherein the formulation is one of a conjunctive normal form (CNF) formulation, a decomposable disjunctive negation form (DNNF) formulation, a binary decision diagram (BDD) formulation, a programmed instruction (PI) formulation, a negation normal form (NNF) formulation, and a hybrid truth maintenance system (HTMS) formulation.

5. The control system of claim 2, wherein the formulation is one of a conjunctive normal form (CNF) formulation and a decomposable disjunctive negation form (DNNF) formulation.

6. The control system of claim 1, wherein the formulation is a constraint satisfaction problem (CSP) formulation.

7. The control system of claim 6, wherein the formulation is a constraint satisfaction optimization problem (CSOP) formulation.

8. The control system of claim 1, wherein the formulation is a linear programming (LP) formulation.

9. The control system of claim 1, wherein the formulation is an integer linear programming (ILP) formulation.

10. The control system of claim 1, wherein the formulation further includes an objective function evaluating fault probabilities of plant resources, and wherein the planner is operative to select at least one solution based at least partially on the fault probabilities.

11. A method of generating plans for execution in a production system with a plant to achieve one or more production goals, the method comprising:

determining a current plant condition based at least partially on a previously executed plan, at least one corresponding observation from the plant, and a plant model;

providing a formulation representing possible actions in the plant including constraints and variables for each action to transition the plant from a starting state to a goal state defined by at least one production goal;

solving the formulation to provide at least one solution to the formulation based at least partially on the at least one production goal, the at least one diagnostic goal, and the current plant condition, wherein solving the formulation comprises evaluating an objective function based on the number of plant resources suspected of being faulty that are used in a given solution, and selecting at least one solution for which number of suspected resources used in the solution is closest to half of the suspected plant resources;

translating the solution into a plan; and

providing the plan to the plant for execution.

12. The method of claim 11, wherein solving the formulation further comprises:

evaluating an objective function with respect to fault probabilities of plant resources; and

selecting at least one solution based at least partially on the fault probabilities.

13. A non-transitory computer readable medium having computer executable instructions for performing the steps of:

determining a current plant condition based at least partially on a previously executed plan, at least one corresponding observation from the plant, and a plant model;

providing a formulation representing possible actions in the plant including constraints and variables for each action to transition the plant from a starting state to a goal state defined by at least one production goal;

solving the formulation to provide at least one solution to the formulation based at least partially on the at least one production goal, the at least one diagnostic goal, and the current plant condition, wherein the computer executable instructions for solving the formulation comprise;

computer executable instructions for evaluating an objective function based on the number of plant resources suspected of being faulty that are used in a given solution, and

computer executable instructions for selecting at least one solution for which number of suspected resources used in the solution is closest to half of the suspected plant resources;

translating the solution into a plan; and

providing the plan to the plant for execution.

14. The computer readable medium of claim 13, wherein the computer executable instructions for solving the formulation comprise computer executable instructions for:

evaluating an objective function fault with respect to probabilities of plant resources; and

selecting at least one solution based at least partially on the fault probabilities.

15. A control system for controlling operation of a production system with a plant that can achieve one or more production goals by execution of plans using one or more plant resources, the control system comprising:

at least one processor;

a plant model including a model of the plant;

a diagnosis component implemented using the at least one processor and operatively coupled with the plant to determine a current plant condition based at least partially on a previously executed plan, at least one corresponding observation from the plant, and the plant model, the current plant condition indicating fault status of the one or more plant resources; and

a planner operative to receive at least one diagnostic goal from the diagnosis component and at least one production goal, the planner comprising;

a formulation representing possible actions in the plant including constraints and variables for each action to transition the plant from a starting state to a goal state defined by at least one production goal,

a solver implemented using the at least one processor and operative to provide at least one solution to the formulation based at least partially on the at least one production goal, at least one diagnostic goal, and the current plant condition, and

a translation component operative to translate the solution into a plan and to provide the plan to the plant for execution.

16. The control system of claim 15, wherein the solver is a SAT solver.

17. The control system of claim 15, wherein the formulation is a constraint satisfaction problem (CSP) formulation.

18. The control system of claim 17, wherein the formulation is a constraint satisfaction optimization problem (CSOP) formulation.

19. The control system of claim 15, wherein the formulation is a constraint satisfaction optimization problem (CSOP) formulation.

20. The control system of claim 15, wherein the formulation further includes an objective function evaluating fault probabilities of plant resources, and wherein the planner is operative to select at least one solution based at least partially on the fault probabilities.