AI planning based quasi-montecarlo simulation method for probabilistic planning

• US 8,473,447 B2
• Filed: 03/29/2010
• Issued: 06/25/2013
• Est. Priority Date: 03/29/2010
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Yoon, Sungwook, Ruml, Wheeler, Do, Minh Binh, Benton, J. Daniel
• Primary Examiner(s): Gaffin, Jeffrey A
• Assistant Examiner(s): Sugent, James F
• Application Number:
  US12/748,686
• Publication Number:
  US 20110238614A1
• Time in Patent Office: 1,184 Days
• Field of Search: 706/52, 700/93, 702/181, 705/7.11, 705/7.36, 705/7.37
• US Class Current: 706/52
• CPC Class Codes: G06N 20/00 Machine learning
• CPC Class Codes: G06N 5/045 Explanation of inference; Explainable artificial intelligence [XAI]; Interpretable artificial intelligence

Abstract

A computer-based method and system for AI planning based quasi-Monte Carlo simulation for probabilistic planning are provided. The method includes generating a set of possible actions for an initial state, generating a set of sample future outcomes, generating solutions for each of the sample future outcomes, using an AI planner, generating a set of future outcome solutions that are low probability and high-impact, combining the solutions generated from each of the sample future outcomes with the future outcome solutions generated by the AI Planner into an aggregated set of future outcome solutions, analyzing the aggregated set of future outcome solutions, selecting a best action based at least partially on the analysis of the aggregated set of future outcome solutions, and outputting the selected best action to computer memory.

Claims

1. A computer-implemented method for artificial intelligence (AI) planning based quasi-Monte Carlo simulation for probabilistic planning, comprising:

using a computer processor, storing into a computer memory an initial state of a system and a description of a target domain;

generating a set of possible actions for the initial state;

for each action in the set of the possible actions, performing a sequence of actions, comprising;

generating by an AI planner a set of sample future outcomes for the initial state;

generating by a quasi-Monte Carlo simulation module probabilities of solutions for each of the sample future outcomes;

evaluating future outcome solutions that are either highest probability, or lowest probability and highest-impact, relative to the solutions generated by the AI planner, wherein the AI planner searches a probabilistic planning tree for harmful sequences of actions which are either highest probability, or lowest probability and highest-impact, relative to the solutions generated by the AI planner for focused evaluation thereof;

aggregating the evaluated solutions with future outcome solutions generated by the quasi-Monte Carlo simulation module, each of the aggregated solutions indicating a state of the system after a corresponding outcome occurs; and

analyzing the aggregated set of future outcome solutions;

automatically selecting a best action based at least partially on the analysis of the aggregated set of future outcome solutions; and

outputting the selected best action to computer memory for probabilistic planning.

2. The method of claim 1, where the set of possible actions for the initial state contains all of the possible actions for the initial state.

3. The method of claim 1, wherein the description of a target domain comprises:

a description of a desired goal state,

known probabilities of future events, and

a set of possible actions for the initial state.

4. The method of claim 1, wherein the generating a set of sample future outcomes is performed by a uniform sampling algorithm that includes a Monte Carlo sampling method.

5. The method of claim 4, wherein the uniform sampling algorithm comprises generating a sequence of fixed length random numbers.

6. The method of claim 1, wherein the AI planner is an automated planning engine that takes general problem description language that includes planning domain definition language (PDDL) as its input.

7. The method of claim 1, wherein:

the action of analyzing the aggregated set of future outcome solutions creates an index based at least partially on the analysis of the aggregated set of future outcome solutions; and

the action of selecting a best action is based at least partially on the created index.

8. The method of claim 7, wherein the index is created through a weighted averaging of the future outcomes in the aggregated set of future outcome solutions.

9. The method of claim 7, further comprising comparing an aggregated set of future outcome solutions for a given action with the aggregated set of future outcome solutions for a different action.

10. The method of claim 1, wherein the selected best action is output to at least one of the following:

a computer monitor, and

a file system.

11. A non-transitory computer readable medium encoding instructions which, when executed by a computer, performs the method of claim 1.

12. The method of claim 1, wherein the aggregated set of future outcome solutions is relative to the initial state.

13. The method of claim 1, wherein the probabilistic planning tree includes a plurality of states of the system and a plurality of actions, the plurality of states including the initial state and the aggregated solutions, and the plurality of actions including the set of possible actions and probabilistic outcomes of the set of possible actions represented as actions, and wherein the plurality of actions connect pairs of the plurality of states.

14. A computer-based system for artificial intelligence (AI) planning based quasi-Monte Carlo simulation for probabilistic planning, comprising:

an AI planner; and

a quasi-Monte Carlo simulation module adapted to;

store an initial state of a system and a description of a target domain into a computer memory;

generate a set of possible actions for the initial state for a desired initial state;

for each action in the set of the possible actions, perform a sequence of actions, comprising;

generating by the AI planner a set of sample future outcomes for the initial state;

generating probabilities of solutions for each of the sample future outcomes;

evaluating a set of future outcome solutions that are either highest probability, or lowest probability and highest-impact, relative to the solutions generated by the AI planner, wherein the AI planner searches a probabilistic planning tree for harmful sequences of actions which are either highest probability, or lowest probability and highest-impact, relative to the solutions generated by the AI planner for focused evaluation thereof;

combining the evaluated solutions with future outcome solutions generated by the quasi-Monte Carlo simulation module into an aggregated set of future outcome solutions, each of the aggregated solutions indicating a state of the system after a corresponding outcome occurs; and

analyzing the aggregated set of future outcome solutions;

automatically selecting a best action based at least partially on the analysis of the aggregated set of future outcome solutions; and

outputting the selected best action to computer memory for probabilistic planning.

15. The system of claim 14, wherein the set of possible actions for the initial state contains all of the possible actions for the initial state.

16. The system of claim 14, wherein the description of a target domain comprises:

a description of a desired goal state,

known probabilities of future events, and

a set of possible actions for the initial state.

17. The system of claim 14, wherein the generating a set of sample future outcomes is performed by a sampling algorithm compatible with a Monte Carlo sampling method;

wherein the sampling algorithm is one of;

a uniform sampling algorithm,

stratified sampling algorithm, and

a residual sampling algorithm.

18. The system of claim 14, wherein the AI planner is an automated planning engine that takes general problem description language including planning domain definition language (PDDL) as its input.

19. The system of claim 14, wherein:

the action of analyzing the aggregated set of future outcome solutions creates an index based at least partially on the analysis of the aggregated set of future outcome solutions; and

the action of selecting a best action is based at least partially on the created index.

20. The system of claim 19, wherein the index is created through a weighted averaging of the future outcomes in the aggregated set of future outcome solutions.

21. The system of claim 14, wherein the selected best action is output to at least one of the following:

a computer monitor, and

a file system.

22. The system of claim 14, wherein the computer memory additionally receives as input at least one of the following:

a threshold value to identify a low probability solution; and

a threshold value to identify a high-impact solution.

23. The system of claim 14, wherein the probabilistic planning tree includes a plurality of states of the system and a plurality of actions, the plurality of states including the initial state and the aggregated solutions, and the plurality of actions including the set of possible actions and probabilistic outcomes of the set of possible actions represented as actions, and wherein the plurality of actions connect pairs of the plurality of states.