AI PLANNING BASED QUASI-MONTECARLO SIMULATION METHOD FOR PROBABILISTIC PLANNING

• US 20110238614A1
• Filed: 03/29/2010
• Published: 09/29/2011
• 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, Do, Minh Binh, Ruml, Wheeler
• Granted Patent: US 8,473,447 B2
• Time in Patent Office: Days
• 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 AI planning based quasi-Monte Carlo simulation for probabilistic planning, comprising:

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

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 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;

aggregating the solutions generated by the AI planner with the sample future outcomes; and

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.

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, such as that used in a Monte Carlo sampling method.

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

6. 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.

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

8. 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.

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

10. The method of claim 1, 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.

11. A computer program product encoding instructions which, when executed by a computer, performs the method of claim 1.

12. A computer-based system for AI planning based quasi-Monte Carlo simulation for probabilistic planning, comprising:

an AI planner; and

a quasi-Monte Carlo simulation module adapted to;

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

generate a set of possible actions for the initial state;

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

generating a set of sample future outcomes;

using the AI planner, generating a set of future outcome solutions that are low probability and high-impact for each of the sample future outcomes;

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; and

analyzing the aggregated set of future outcome solutions;

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

output the selected best action to computer memory.

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

14. The system of claim 12, 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.

15. The system of claim 12, 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.

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

17. The system of claim 12, 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.

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

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

a computer monitor, and

a file system.

20. The system of claim 12, 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.