Reachability analysis for uncertain SSPs

作     者：Buffet, Olivier 

作者机构：Australian Natl Univ Natl ICT Australia RSISE Stat Machine Learning Program Canberra ACT Australia 

出 版 物：《INTERNATIONAL JOURNAL ON ARTIFICIAL INTELLIGENCE TOOLS》 (国际人工智能工具杂志)

年 卷 期：2007年第16卷第4期

页      面：725-749页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主　　题：stochastic shortest-path problems uncertain model reachability analysis 

摘      要：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.