AI planning based quasimontecarlo simulation method for probabilistic planning

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
7Forward
Citations 
0
Petitions 
2
Assignments
First Claim
1. A computerimplemented method for artificial intelligence (AI) planning based quasiMonte 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 quasiMonte 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 highestimpact, 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 highestimpact, relative to the solutions generated by the AI planner for focused evaluation thereof;
aggregating the evaluated solutions with future outcome solutions generated by the quasiMonte 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 Assignments
0 Petitions
Accused Products
Abstract
A computerbased method and system for AI planning based quasiMonte 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 highimpact, 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.
23 Citations
View as Search Results
SYSTEMS AND METHODS FOR SCHEDULING MULTISKILLED STAFF  
Patent #
US 20150356514A1
Filed 06/10/2014

Current Assignee
Infrared Integrated Systems Ltd.

Sponsoring Entity
Infrared Integrated Systems Ltd.

PREDICTING A STATUS OF A TRANSACTION  
Patent #
US 20160217513A1
Filed 05/29/2015

Current Assignee
eBay Inc.

Sponsoring Entity
eBay Inc.

System and method for controlling autonomous or semiautonomous vehicle  
Patent #
US 9,568,915 B1
Filed 02/11/2016

Current Assignee
Mitsubishi Electric Research Laboratories

Sponsoring Entity
Mitsubishi Electric Research Laboratories

Trajectory generation using temporal logic and tree search  
Patent #
US 10,133,275 B1
Filed 06/23/2017

Current Assignee
Zoox Inc.

Sponsoring Entity
Zoox Inc.

Predicting a status of a transaction  
Patent #
US 10,217,148 B2
Filed 05/29/2015

Current Assignee
eBay Inc.

Sponsoring Entity
eBay Inc.

Trajectory generation and execution architecture  
Patent #
US 10,353,390 B2
Filed 06/23/2017

Current Assignee
Zoox Inc.

Sponsoring Entity
Zoox Inc.

Featurebased prediction  
Patent #
US 10,414,395 B1
Filed 04/06/2018

Current Assignee
Zoox Inc.

Sponsoring Entity
Zoox Inc.

DECISION SUPPORT METHODS UNDER UNCERTAINTY  
Patent #
US 20110125702A1
Filed 07/09/2009

Current Assignee
International Institute Of Information Technology

Sponsoring Entity
International Institute Of Information Technology

COMPUTER IMPLEMENTED DECISION SUPPORT METHOD & SYSTEM  
Patent #
US 20110270646A1
Filed 07/13/2009

Current Assignee
Prasanna Gorur Narayana Srinivasa, Kumar Dileep, Aswal Abhilasha, Joy Mabel Mary, Chandra Babu Anushka, Jain Piyushkumar

Sponsoring Entity
Prasanna Gorur Narayana Srinivasa, Kumar Dileep, Aswal Abhilasha, Joy Mabel Mary, Chandra Babu Anushka, Jain Piyushkumar

TRUSTED DECISION SUPPORT SYSTEM AND METHOD  
Patent #
US 20090210378A1
Filed 04/28/2009

Current Assignee
Gregory P. Benson

Sponsoring Entity
Gregory P. Benson

Portfolio rebalancing by means of resampled efficient frontiers with forecast confidence level  
Patent #
US 7,412,414 B2
Filed 06/21/2005

Current Assignee
Michaud Partners LLP

Sponsoring Entity
Michaud Partners LLP

Trusted decision support system and method  
Patent #
US 20070022057A1
Filed 05/03/2006

Current Assignee
Gregory P. Benson

Sponsoring Entity
Gregory P. Benson

Trusted decision support system and method  
Patent #
US 20070011107A1
Filed 05/03/2006

Current Assignee
Gregory P. Benson

Sponsoring Entity
Gregory P. Benson

Method and apparatus for customer scheduling to reduce wait times and increase throughput  
Patent #
US 20070136118A1
Filed 12/09/2005

Current Assignee
Perrin Brian, Gerlach Brett

Sponsoring Entity
Perrin Brian, Gerlach Brett

Anticipatory Mobile System Service Brokering and Resource Planning from Multiple Providers  
Patent #
US 20070288138A1
Filed 08/23/2007

Current Assignee
Bodin William, Kwok Albert, Del Pizzo John, Thorson Derral, Stryjewski Wojciech, Huff David, Clark Bryan, Karasick Michael

Sponsoring Entity
Bodin William, Kwok Albert, Del Pizzo John, Thorson Derral, Stryjewski Wojciech, Huff David, Clark Bryan, Karasick Michael

Anticipatory optimization with composite folding  
Patent #
US 6,745,384 B1
Filed 09/21/2000

Current Assignee
Microsoft Technology Licensing LLC

Sponsoring Entity
Microsoft Corporation

Business enterprise risk model and method  
Patent #
US 20050027645A1
Filed 01/31/2003

Current Assignee
SEBURY ANALYTIC LLC

Sponsoring Entity
SEBURY ANALYTIC LLC

Objectoriented pseudorandom number generator interface  
Patent #
US 20050050122A1
Filed 12/18/2003

Current Assignee
SAP SE

Sponsoring Entity
SAP SE

Method and system for automatic service composition  
Patent #
US 20050097224A1
Filed 03/30/2004

Current Assignee
Industrial Technology Research Institute

Sponsoring Entity
Industrial Technology Research Institute

System and method for incorporating mortality risk in an investment planning model  
Patent #
US 6,947,904 B1
Filed 07/25/2000

Current Assignee
MACEYHOLLAND CO. LLC

Sponsoring Entity
MACEYHOLLAND CO. LLC

Digital cockpit  
Patent #
US 20040015381A1
Filed 01/09/2003

Current Assignee
General Electric Company

Sponsoring Entity
General Electric Company

System and method for modeling and analyzing strategic business decisions  
Patent #
US 20020169658A1
Filed 03/06/2002

Current Assignee
Adler Richard M.

Sponsoring Entity
Adler Richard M.

Monte Carlo based treatment planning for neutron capture therapy  
Patent #
US 5,341,292 A
Filed 06/04/1992

Current Assignee
NEW ENGLAND MEDICAL CENTER HOSPITALS INC. A CORP. OF MA

Sponsoring Entity
NEW ENGLAND MEDICAL CENTER HOSPITALS INC. A CORP. OF MA

23 Claims
 1. A computerimplemented method for artificial intelligence (AI) planning based quasiMonte 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 quasiMonte 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 highestimpact, 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 highestimpact, relative to the solutions generated by the AI planner for focused evaluation thereof;
aggregating the evaluated solutions with future outcome solutions generated by the quasiMonte 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.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
 using a computer processor, storing into a computer memory an initial state of a system and a description of a target domain;
 11. A nontransitory computer readable medium encoding instructions which, when executed by a computer, performs the method of claim 1.
 14. A computerbased system for artificial intelligence (AI) planning based quasiMonte Carlo simulation for probabilistic planning, comprising:
 an AI planner; and
a quasiMonte 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 highestimpact, 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 highestimpact, relative to the solutions generated by the AI planner for focused evaluation thereof;
combining the evaluated solutions with future outcome solutions generated by the quasiMonte 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.  View Dependent Claims (15, 16, 17, 18, 19, 20, 21, 22, 23)
 an AI planner; and
1 Specification
The present exemplary embodiments relate to a system and method for Artificial Intelligence (AI) planning based quasiMonte Carlo simulation for probabilistic planning. As observed in the financial markets and other uncertain environments, it is difficult to make rational decisions when the future is unknown. Although there are many ways to create models based on an environment containing an uncertain future, the models need to be solved correctly and completely in order to make optimal decisions with respect to the environment such that losses are prevented or mitigated and gains are maximized. However, the problem of finding optimal solutions within an uncertain environment is normally intractable and at best only approximates solutions with great computation complexity. Thus, the goal is to find an approach that balances between computational complexity and a good quality solution.
A computerimplemented system and method for AI planning based quasiMonte Carlo simulation for probabilistic planning is provided. The system and method includes receiving an initial state and a description of a target domain into computer memory; generating a set of possible actions that can be executed for the initial state; for each action in the set of the possible actions: 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 having a low probability but having a high impact; combining the automated AI planner produced solutions generated from each of 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.
Aspects of the present exemplary embodiment relate to a system and method for decision making with regard to uncertain future problems using sampling. Specifically, the exemplary embodiment samples possible future outcomes based on the known probabilities of future events and then solves deterministic problems represented by the sampled future outcomes. The exemplary embodiment utilizes the fact that deterministic versions of the intractable problem are much easier to solve. The solutions from many of the deterministic problems are then combined, which allows for accurate decision making when the sampled future outcome set is representative of the problem.
With reference to
Previous approaches to planning and scheduling in uncertain environments have traditionally been formulated as Markov Decision Processes (MDP) and solved by finding the optimal policy over many iterations of a Bellman update. In practice, it turns out that naïve application of MDP is not conducive to realworld applications due to poor running time and performance.
Other approaches to decision making with regard to an uncertain future, such as the Monte Carlo approach, sample the futures based on the probability that each future event may occur but do not take into account the “importance” or “significance” of different future events. Thus, this type of approach often omits highimpact future outcomes from the set of sample futures. Highimpact future outcomes are outcomes that, regardless of their probability of happening, would have a significant impact (whether positive or negative) on the solution for a deterministic problem.
The exemplary embodiments of the present application incorporate very unlikely but critical/highimpact future outcomes, such as financial defaults in banking or landmine explosions, when generating sample futures. Rather than naively sampling from some distribution, the exemplary embodiment utilizes AI (artificial intelligence) planning to automatically find unlikely but critical sequences of events. The described systems and methods can be viewed as a quasiMonte Carlo approach, since rather than sampling based on raw probabilities, a particular sample set is found through a known reasoning process such as AI planning as used in this implementation.
Regular Monte Carlo sampling works by simulating multiple “whatif” scenarios and combining the “whatif” simulation results to evaluate various input plans. The quasiMonte Carlo approach works like the regular Monte Carlo approach, where a different set of “whatif” scenarios are chosen to simulate. The present exemplary Monte Carlo simulation embodiment performs computed sampling like quasiMonte Carlo, but the composition of the sampling is done through AI planning. The use of AI planning provides for autonomous or nearautonomous sampling, whereas existing quasiMonte Carlo style sampling relies on a human interaction. Through the combination of AI planning based quasiMonte Carlo and normal Monte Carlo sampling, significant computational gains are achieved with increased autonomy.
As shown in standard probabilistic planning benchmarks, AI (i.e., deterministic) planning can be used very effectively in uncertain environments by considering all the probabilistic outcomes as separate deterministic outcomes while finding solutions for extreme cases. Preliminary results show that this approach can capture unlikely but critical uncertain outcomes and the whole decision making can be made much better and more stable.
The exemplary embodiments describe an approach of effective decision making in the presence of uncertainty by using an “anticipatory” technique. This technique is applicable to a broad area of decision making, scheduling and planning in uncertain situations. These situations happen naturally in many environments and situations. For example, in warfare situations, an Army moving into enemy area may have no clear idea of where the enemy is hiding and will want to maximize its chance of finding the enemy with some sort of planning technique. In the financial sector, banks routinely make decisions on whether to lend money based on a borrower's past credit, but the process of decision making is uncertain, since banks do not know what will happen in the future. On a larger scale, financial crises may be averted if optimal or nearoptimal decisions can be made by the parties involved in the market. In an environment such as a production system, this technique is useful as better decisions can be made as to what actions to take relative to unknown future costs.
Probabilistic planning, scheduling and decision making algorithms have been developed to cope with uncertain futures such as those scenarios described above, and the present exemplary embodiment improves the performance of those techniques. There are many ways to model the uncertain nature of the environment and if the models are solved correctly and completely, optimal decisions can be made. However, the problem of finding optimal solutions is normally intractable and at best only approximates solutions with great computational complexity. Thus, the goal is to find an approach that balances between computational complexity and a good quality solution.
With regard to
This probabilistic planning tree 300 can be mapped out apriori based on known probabilities. However, one of the key problems in simulating future “whatif” scenarios is the size of the future sample set when the method simulates far into the future with a long horizon. As one can see in
However, there is one big caveat with Monte Carlo sampling methods: the sampled points need to be well correlated with the bottomline actual distribution multiplied by the implied risk/reward. This situation can be illustrated by the concept of “default” within the banking industry. Typically, a default (a failure to meet financial obligations) is a rare event. Consequently, this rare event is not usually sampled with normal uniform sampling, such as that used in the Monte Carlo sampling method. Additional sampling algorithms such as stratified or residual sampling algorithms may also fail to sample rare events. However, the cost of such a default, despite being a rare event, is high enough that the sampling method needs to sample such occasion and evaluate it in order to create a viable set of future samples.
With respect to
One way to do this rareevent simulation is by modifying the sampling function to be able to sample unlikely samples associated with high risk or reward values more frequently than they could have been and readjust the weights to reflect the modified sampling. This method has been known as importance sampling and is widely used in many of the current software packages. One such method of importance sampling is quasiMonte Carlo simulation. This technique attempts to solve the problem by predesigning the sampling pattern. So, in fact, it is not actual sampling but rather finding where to sample with meticulously designed Meshstyle points.
The benefit of this technique is potential robustness compared to normal sampling, which is typically very unstable, whereas predesigned quasiMonte Carlo points provide robustness and reduced variance. The cost of an approach such as quasiMonte Carlo sampling is that it is not known apriori what samples constitute rare/high value occasion. Another cost is having too many sample points that deteriorate the overall efficiency significantly compared to existing Monte Carlo Simulation.
With respect to
With respect to
An advantage of using AI planning is the ability to construct causally related action sequences that achieve a desired effect. The present exemplary embodiment utilizes this particular property of AI planning as a sampling source for the quasiMonte Carlo simulation. Particularly, in place of actions, the modified quasiMonte Carlo simulation views random outcomes that are handled by simulation as actions in AI planning. Then the whole problem of identifying potentially harmful random sequence events (or outcomes) is cast as a planning problem by putting the outcomes as actions and potentially harmful results as “desired effects” or “goals”. This view fits nicely with the problem of making decisions in an uncertain environment.
With respect to
The system 600 includes data memory 608 for use during the processing of the initial state 604 and description of the target domain 606. Main memory 610 of the system 600 stores a quasiMonte Carlo simulation module 612 containing a Monte Carlo sampling module 614, an AI Planner 616, and a solution aggregation module 618. The quasiMonte Carlo simulation module 612 works in conjunction with modules 614, 616 and 618 to calculate the best action to take at a given state. In particular, the Monte Carlo sampling module 614 is adapted to generate all the possible actions for a given state and generates a set of sample futures for a given starting (initial) state. The futures represent the possible outcomes for each state that are realized if a particular action is selected. For example,
The quasiMonte Carlo simulation module 612, Monte Carlo sampling module 614, AI Planner 616 and solution aggregation module 618 may be implemented as hardware or software or a combination thereof. In the exemplary embodiment, components 612, 614 and 616 comprise software instructions stored in main memory 610, which are executed by a computer processor 619. The processor 619, such as a computer's CPU, may control the overall operation of the computer system by execution of processing instructions stored in memory 610. Components 608, 610 and 619 of the computer system 600 may be connected by a data control bus 620.
The system 600 includes an output device 622, which outputs processed data, such as a selected best action 24. The exemplary output device 622 is linked by a wired or wireless link to a storage system 626, which may store a selected best action 624. Alternatively, the output device 622 may store processed data, such as a selected best action 624 into internal memory 608 of the computing device 600.
As will be appreciated, the AI Planning based quasiMonte Carlo simulation system 600 may comprise one or more computing devices, such as a personal computer, PDA, laptop computer, server computer, or combination thereof. Memories 608 and 610 may be integral or separate and may represent any type of computer readable medium such as random access memory and read only memory. In some embodiments, the processor 619 and memory 608 and/or 610 may be combined in a single chip.
With reference to
At step 701, the input device 602 of the simulation system 600 receives an initial state 604 and a description of the target domain 606 and imports them into data memory 608. The method then proceeds to step 702.
At step 702, all possible actions (such as Action1 and Action 2 of
At step 704, steps 706, 708, 710 and 712 are performed for each action generated above in step 702. Control is then passed to the solution aggregation module 618 at step 714.
At step 706, the Monte Carlo sampling module 614 generates a set of sample futures according to any sampling algorithm known in the art, including, but not limited to, uniform sampling algorithms traditionally used for Monte Carlo simulation. The number of sample futures generated will be statistically sufficient to enable a near optimal simulation while keeping processing costs low. With respect to the stock exchange transaction example above, the Monte Carlo sampling module 614 may determine with 90% confidence that if the second action is performed, there is a 99% chance of the stock increasing in value by 20%, and a 1% chance of the stock decreasing in value by 80%. With respect to
At step 708, solutions are generated for each of the sample futures produced by step 706. That is, for each sample future, the Monte Carlo sampling module 614 determines the state that will exist if the sample future actually materializes. With respect to the stock exchange transaction example, step 706 generated two sample futures (potential outcomes) out of many that could have been sampled in step 706. The resulting outcome for the first sample future where the stock increases in value by 20% is a “selling” of stock that has just increased 20% in value (represented by state F in
At step 710, the AI Planner 616 generates solutions starting at the initial state 604 using alloutcome determination domain representation. All outcome determination treats each probabilistic outcome of actions as a separate deterministic action. For example, in the stock example presented above, two actions are generated, one that increases the stock and the other that decreases the stock. The AI Planner 616, or its equivalent, uses the determined set of actions (all the possible outcomes) and given the initial state 604 and an input description of a target domain 606, finds any low probability highimpact future outcomes automatically. As described above, the description of the target domain 606 includes a description of the desired goal (i.e, the properties of a desirable end state solution), known probabilities of future events, and a set of possible actions for the initial state 604. The description of the target domain may be encoded in any formal language (such as PDDL—planning domain definition language) suitable to convey such information, such as the languages found in the Stanford Research Institute Problem Solver (STRIPS) domain. The thresholds for whether an outcome is considered low probability and/or highimpact may be set by an outside entity (such as an end user) or may be set as default values. For example, a parameter may be set in the AI Planner to classify an outcome as low probability if the probability is less than 0.5%, or to classify an outcome as highimpact if it results in a state that causes a change from the initial state 604 of at least 500%. With respect to
The solution aggregation module 618 then combines the low probability, highimpact solutions generated by the AI Planner 616 with the sample solution set generated in step 708. The combined set of sample future solutions are then processed by the solution aggregation module 618 at step 712.
At step 712, the solution aggregation module 618 processes the combined set of sample future solutions through aggregation. The aggregation process comprises performing a mathematical or statistical algorithm on the combined set of sample future solutions to produce meaningful information for the purpose of decision making. This is basically a summary value for each action available from the initial state (generated by step 702). In the present exemplary embodiment, the aggregation process comprises performing a weighted summation or averaging of all the solutions in the set to produce an index value. The index value can then be used to determine the relative importance of the combined set of sample solutions compared to a combined set of sample solutions associated with a different action. After step 712 is performed, control is passed to step 714.
At step 714, the quasiMonte Carlo simulation module 612 has aggregated a set of solutions for each action relative to the initial state 604. The simulation module 712 then chooses the best action for the initial state 604 based at least partially on the aggregation performed in step 712. In the exemplary embodiment, the best action is determined by comparing the index values created in step 712.
At step 716, the selected best action determined in step 714 is output by the output device 622 to either memory 608 or an external device such as a storage system 626, or a monitor.
The method ends at step 718.
It will be appreciated that various of the abovedisclosed and other features and functions, or alternatives thereof, may be desirably combined into many other different systems or applications. Also that various presently unforeseen or unanticipated alternatives, modifications, variations or improvements therein may be subsequently made by those skilled in the art which are also intended to be encompassed by the following claims.