Special Issue on Selected Papers from the 17th Annual IEEE International Conference (ICTAI-2005); Guest Editors: Fan Wang and Andrew LimNo Access

REACHABILITY ANALYSIS FOR UNCERTAIN SSPs

OLIVIER BUFFET

OLIVIER BUFFET

Statistical Machine Learning program, National ICT Australia, RSISE, The Australian National University, Canberra, Australia

Search for more papers by this author

https://doi.org/10.1142/S0218213007003527Cited by:0 (Source: Crossref)

Abstract

Stochastic Shortest Path problems (SSPs) can be efficiently dealt with by the Real-Time Dynamic Programming algorithm (RTDP). Yet, RTDP requires that a goal state is always reachable. This article presents an algorithm checking for goal reachability, especially in the complex case of an uncertain SSP where only a possible interval is known for each transition probability. This gives an analysis method for determining if SSP algorithms such as RTDP are applicable, even if the exact model is not known. As this is a time-consuming algorithm, we also present a simple process that often speeds it up dramatically. Yet, the main improvement still needed is to turn to a symbolic analysis in order to avoid a complete state-space enumeration.

Keywords:

Remember to check out the Most Cited Articles!
Check out Notable Titles in Artificial Intelligence.

References

D. P. Bertsekas and J. N. Tsitsiklis , Neurodynamic Programming ( Athena Scientific , 1996 ) . Google Scholar
R. Munos , Advances in Neural Information Processing Systems (NIPS'01) 13 ( 2001 ) . Google Scholar
J. A. Bagnell, A. Y. Ng, and J. Schneider. Solving uncertain Markov decision problems. Technical Report CMU-RI-TR-01-25, Robotics Institute, Carnegie Mellon University, Pittsburgh, PA, August 2001 . Google Scholar
A. Nilim and L. El Ghaoui , Advances in Neural Information Processing Systems (NIPS'03) 16 ( 2004 ) . Google Scholar
R. Givan, S. Leach and T. Dean, Artificial Intelligence 122(1–2), 71 (2000), DOI: 10.1016/S0004-3702(00)00047-3. Crossref, Web of Science, Google Scholar
M. Hosaka, M. Horiguchi and M. Kurano, Applied Mathematics and Computation 120(1–3), 195 (2001), DOI: 10.1016/S0096-3003(99)00241-6. Crossref, Web of Science, Google Scholar
A. L. Strehl and M. L. Littman , An empirical evaluation of interval estimation for Markov decision processes , Proceedings of the Sixteenth International Conference on Tools with Artificial Intelligence (ICTAI'04) ( 2004 ) . Google Scholar
A. G. Barto, S. Bradtke and S. Singh, Artificial Intelligence 72, (1995), DOI: 10.1016/0004-3702(94)00011-O. Google Scholar
O. Buffet and D. Aberdeen , Robust planning with (L)RTDP , Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI'05) ( 2005 ) . Google Scholar
C. Boutilier , R. I. Brafman and C. Geib , Structured reachability analysis for Markov decision processes , Proceedings of the Fourteenth Conference on Uncertainty in Artificial Intelligence (UAI-98) ( 1998 ) . Google Scholar
R. Bellman , Dynamic Programming ( Princeton University Press , Princeton, New-Jersey , 1957 ) . Google Scholar
R. Sutton and G. Barto , Reinforcement Learning: an introduction ( Bradford Book, MIT Press , Cambridge, MA , 1998 ) . Google Scholar
O. Buffet and D. Aberdeen. Planning with robust (L)RTDP. Technical report, National ICT Australia, november 2004 . Google Scholar
B. Bonet and H. Geffner , Faster heuristic search algorithms for planning with uncertainty and full feedback , Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI'03) ( 2003 ) . Google Scholar
Robert J. Vanderbei. Optimal sailing strategies, statistics and operations research program, 1996. University of Princeton, http://www.sor.princeton.edu/~rvdb/sail/sail.html . Google Scholar
L. Peret and F. Garcia , On-line search for solving Markov decision processes via heuristic sampling , Proceedings of the Sixteenth European Conference on Artificial Intelligence (ECAI'04) ( 2004 ) . Google Scholar
O. Coudert , J.-C. Madre and C. Berthet , Verifying temporal properties of sequential machines without building their state diagrams , Proceedings of the Workshop on Computer-Aided Verification ( 1990 ) . Google Scholar
R. E. Bryant, ACM/IEEE Design Automation 688 (1985). Google Scholar

Vol. 16, No. 04

Metrics

Downloaded 13 times

History

Keywords

PDF download

System Upgrade on Tue, May 28th, 2024 at 2am (EDT)

REACHABILITY ANALYSIS FOR UNCERTAIN SSPs

Abstract

Recommended