Project "Planning under Uncertainty with Realistic Preference Models"
Preference models determine which one of several plans to prefer. It is important that planners use the same preference models as human decision makers because planners should make the same decisions as their human users, otherwise the planners are not of much use. Artificial intelligence planners usually either maximize the probability of goal achievement or minimize the expected execution cost until the goal is achieved. However, many people have more complex preference models. We therefore investigate how to build planners that fit the preference models of human decision makers in nondeterministic decision situations better than current planners, by combining constructive methods from artificial intelligence with more descriptive methods from utility theory in order to extend the applicability of planners from artificial intelligence. We study optimal versus satisficing planning with a variety of preference models, and explore how to exploit the structure of complex sequential planning tasks to solve them efficiently for realistic preference models, with an emphasis on risk-averse decision-making in high-stakes decision situations. (For example, when human decision makers can choose between getting $2,000,000 for sure or $5,000,000 with 50 percent probability, they often pick the safe alternative.) To this end, we develop representation changes that make use of existing planners from artificial intelligence by transforming planning tasks with nonlinear utility functions to planning tasks that these planners can solve. We have demonstrated that these representation changes allow one to make use of existing probabilistic planning methods to create efficient planners for high-stakes decision situations, for example, in the context of sensor planning.
A large part of our research is done in the context of Markov decision process models, popular representations of probabilistic planning tasks. In this context, artificial intelligence researchers have concentrated on how to plan efficiently with more realistic (and thus larger) world models. We, on the other hand, concentrate on how to plan efficiently with more realistic preference models to model the preferences of human decision makers adequately. We have studied planning techniques for totally and partially observable Markov decision process models that maximize the worst-case reward, the expected utility for non-linear utility functions, or the expected total reward under given restrictions. For example, we have used Markov decision process models for route planning in the presence of traps such as steep slopes for outdoor robots (where the primary objective is to reach the target and only the secondary objective is to minimize the travel distance). In this context, we have shown that some reward structures do not guarantee that the plan that maximizes the expected (discounted) reward also reaches the goal from the start (even if it is possible to reach the goal from the start). We have shown when this trapping phenomenon occurs, using a novel interpretation of discounting, and how to eliminate it. We have also used Markov decision process models for sensor planning (that is, when an agent should sense) and for planning with nonlinear utility functions (that is, planning in the presence of deadlines or with risk-attitudes in high-stakes domains).
In conjunction with researchers from IBM T.J. Watson Research Lab, we have applied some of our insights to help supply-chain management systems decide when to participate in auctions and how much to bid. In particular, we derived a closed form of the optimal bidding function for auction agents that maximize the expected utility of the profit for concave exponential utility functions in the symmetric independent private values (SIPV) model and showed how to integrate them into production-planning systems to derive the valuation of items automatically for them. In conjunction with researchers from Emory's School of Medicine, we have also studied how to acquire complex preference models from decision makers, for example how individual clinicians trade-off between the complexity of executing radiosurgery plans and the conformity with which they deliver the radiation to brain lesions.
Representative Publications on High-Stake Planning
Representative Publications on Multi-Attribute Planning
Representative Publications on Hard or Soft Deadlines
Some of this material is based upon work supported by the National Science Foundation under Grant No. 9984827 and an IBM Faculty Fellowship. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation or the other sponsoring organizations.
Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.
This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.