RAO*: An Algorithm for Chance-Constrained POMDP's
Abstract
Autonomous agents operating in partially observable stochastic environments often face the problem of optimizing expected performance while bounding the risk of violating safety constraints. Such problems can be modeled as chance-constrained POMDP's (CC-POMDP's). Our first contribution is a systematic derivation of execution risk in POMDP domains, which improves upon how chance constraints are handled in the constrained POMDP literature. Second, we present RAO*, a heuristic forward search algorithm producing optimal, deterministic, finite-horizon policies for CC-POMDP's. In addition to the utility heuristic, RAO* leverages an admissible execution risk heuristic to quickly detect and prune overly-risky policy branches. Third, we demonstrate the usefulness of RAO* in two challenging domains of practical interest: power supply restoration and autonomous science agents.
Cite
Text
de Rodrigues Quemel e Assis Santana et al. "RAO*: An Algorithm for Chance-Constrained POMDP's." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10423Markdown
[de Rodrigues Quemel e Assis Santana et al. "RAO*: An Algorithm for Chance-Constrained POMDP's." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/derodriguesquemeleassissantana2016aaai-rao/) doi:10.1609/AAAI.V30I1.10423BibTeX
@inproceedings{derodriguesquemeleassissantana2016aaai-rao,
title = {{RAO*: An Algorithm for Chance-Constrained POMDP's}},
author = {de Rodrigues Quemel e Assis Santana, Pedro Henrique and Thiébaux, Sylvie and Williams, Brian Charles},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2016},
pages = {3308-3314},
doi = {10.1609/AAAI.V30I1.10423},
url = {https://mlanthology.org/aaai/2016/derodriguesquemeleassissantana2016aaai-rao/}
}