Many real-world planning problems occur in environments where there may be incomplete information or where actions may not always lead to the same results. Examples include planning for retirement, where the state of the economy in the future is uncertain, and planning in logistics, where the duration of travel between two cities is uncertain due to potential congestion.
A Markov decision process (MDP) is a popular framework for modeling decision making in these kinds of problems, where an agent needs to plan a sequence of actions that maximizes its chances of reaching its goal. A partially observable MDP (POMDP) is an extension where the world that the agent is operating in is only partially observable, and a decentralized (PO)MDP is an extension where a team of agents needs to collectively plan their joint actions.
We proposed the risk-sensitive MDP and POMDP models, where the objective is to find a policy that maximizes the probability of reaching a goal state. Such a model and its accompanying algorithms are useful in high-risk applications, where a single failure can be catastrophic.
Partially Observable Markov Decision Processes (POMDPs) are often used to model planning problems under uncertainty. The goal in Risk-Sensitive POMDPs (RS-POMDPs) is to find a policy that maximizes the probability that the cumulative cost is within some user-defined cost threshold. In this paper, unlike existing POMDP literature, we distinguish between the two cases of whether costs can or cannot be observed and show the empirical impact of cost observations. We also introduce a new search-based algorithm to solve RS-POMDPs and show that it is faster and more scalable than existing approaches in two synthetic domains and a taxi domain generated with real-world data.
@inproceedings{conf/aaai/Hou0V16,author={Hou, Ping and Yeoh, William and Varakantham, Pradeep},title={Solving Risk-Sensitive POMDPs With and Without Cost Observations},booktitle={{AAAI} Conference on Artificial Intelligence},pages={3138--3144},year={2016},}
ICAPS
Revisiting Risk-Sensitive MDPs: New Algorithms and Results
Ping Hou, William Yeoh, and Pradeep Varakantham
In International Conference on Automated Planning and Scheduling, 2014
While Markov Decision Processes (MDPs) have been shown to be effective models for planning under uncertainty, the objective to minimize the expected cumulative cost is inappropriate for high-stake planning problems. As such, Yu, Lin, and Yan (1998) introduced the Risk-Sensitive MDP (RSMDP) model, where the objective is to find a policy that maximizes the probability that the cumulative cost is within some user-defined cost threshold. In this paper, we revisit this problem and introduce new algorithms that are based on classical techniques, such as depth-first search and dynamic programming, and a recently introduced technique called Topological Value Iteration (TVI). We demonstrate the applicability of our approach on randomly generated MDPs as well as domains from the ICAPS 2011 International Probabilistic Planning Competition (IPPC).
@inproceedings{conf/icaps/Hou0V14,author={Hou, Ping and Yeoh, William and Varakantham, Pradeep},title={Revisiting Risk-Sensitive {MDP}s: New Algorithms and Results},booktitle={International Conference on Automated Planning and Scheduling},year={2014},}