State Space Search for Risk-averse Agents

Patrice Perny, Olivier Spanjaard, Louis-Xavier Storme

We investigate search problems under risk in state-space graphs, with the aim of finding optimal paths for risk-averse agents. We consider problems where uncertainty is due to the existence of different scenarios of known probabilities, with different impacts on costs of solution-paths. We consider various non-linear decision criteria (EU, RDU, Yaari) to express risk averse preferences; then we provide a general optimization procedure for such criteria, based on a path-ranking algorithm applied on a scalarized valuation of the graph. We also consider partial preference models like second order stochastic dominance (SSD) and propose a multiobjective search algorithm to determine SSD-optimal paths. Finally, the numerical performance of our algorithms are presented and discussed.

Subjects: 15.7 Search; 15.5 Decision Theory

Submitted: Oct 15, 2006

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.