RAPID: A Reachable Anytime Planner for Imprecisely-sensed Domains

Emma Brunskill, Stuart Russell
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:91-100, 2010.

Abstract

Despite the intractability of generic optimal par- tially observable Markov decision process plan- ning, there exist important problems that have highly structured models. Previous researchers have used this insight to construct more effi- cient algorithms for factored domains, and for domains with topological structure in the flat state dynamics model. In our work, motivated by findings from the education community rele- vant to automated tutoring, we consider problems that exhibit a form of topological structure in the factored dynamics model. Our Reachable Any- time Planner for Imprecisely-sensed Domains (RAPID) leverages this structure to efficiently compute a good initial envelope of reachable states under the optimal MDP policy in time lin- ear in the number of state variables. RAPID per- forms partially-observable planning over the lim- ited envelope of states, and slowly expands the state space considered as time allows. RAPID performs well on a large tutoring-inspired prob- lem simulation with 122 state variables, corre- sponding to a flat state space of over 1030 states.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-brunskill10a, title = {{RAPID}: A Reachable Anytime Planner for Imprecisely-sensed Domains}, author = {Brunskill, Emma and Russell, Stuart}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {91--100}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/brunskill10a/brunskill10a.pdf}, url = {https://proceedings.mlr.press/r8/brunskill10a.html}, abstract = {Despite the intractability of generic optimal par- tially observable Markov decision process plan- ning, there exist important problems that have highly structured models. Previous researchers have used this insight to construct more effi- cient algorithms for factored domains, and for domains with topological structure in the flat state dynamics model. In our work, motivated by findings from the education community rele- vant to automated tutoring, we consider problems that exhibit a form of topological structure in the factored dynamics model. Our Reachable Any- time Planner for Imprecisely-sensed Domains (RAPID) leverages this structure to efficiently compute a good initial envelope of reachable states under the optimal MDP policy in time lin- ear in the number of state variables. RAPID per- forms partially-observable planning over the lim- ited envelope of states, and slowly expands the state space considered as time allows. RAPID performs well on a large tutoring-inspired prob- lem simulation with 122 state variables, corre- sponding to a flat state space of over 1030 states.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T RAPID: A Reachable Anytime Planner for Imprecisely-sensed Domains %A Emma Brunskill %A Stuart Russell %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-brunskill10a %I PMLR %P 91--100 %U https://proceedings.mlr.press/r8/brunskill10a.html %V R8 %X Despite the intractability of generic optimal par- tially observable Markov decision process plan- ning, there exist important problems that have highly structured models. Previous researchers have used this insight to construct more effi- cient algorithms for factored domains, and for domains with topological structure in the flat state dynamics model. In our work, motivated by findings from the education community rele- vant to automated tutoring, we consider problems that exhibit a form of topological structure in the factored dynamics model. Our Reachable Any- time Planner for Imprecisely-sensed Domains (RAPID) leverages this structure to efficiently compute a good initial envelope of reachable states under the optimal MDP policy in time lin- ear in the number of state variables. RAPID per- forms partially-observable planning over the lim- ited envelope of states, and slowly expands the state space considered as time allows. RAPID performs well on a large tutoring-inspired prob- lem simulation with 122 state variables, corre- sponding to a flat state space of over 1030 states. %Z Reissued by PMLR on 04 October 2026.
APA
Brunskill, E. & Russell, S.. (2010). RAPID: A Reachable Anytime Planner for Imprecisely-sensed Domains. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:91-100 Available from https://proceedings.mlr.press/r8/brunskill10a.html. Reissued by PMLR on 04 October 2026.

Related Material