Reachability analysis for uncertain SSPs

Olivier Buffet

doi:10.1109/ICTAI.2005.106

Reachability analysis for uncertain SSPs

Olivier Buffet^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

4 Citations (Scopus)

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 paper 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. We aim at a symbolic analysis in order to avoid a complete state-space enumeration.

Original language	English
Title of host publication	ICTAI 2005
Subtitle of host publication	17th IEEE International Conference on Tools with Artificial Intelligence, ICTAI'05
Pages	515-522
Number of pages	8
DOIs	https://doi.org/10.1109/ICTAI.2005.106
Publication status	Published - 2005
Event	ICTAI 2005: 17th IEEE International Conference on Tools with Artificial Intelligence, ICTAI'05 - Hong Kong, China Duration: 14 Nov 2005 → 16 Nov 2005

Publication series

Name	Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI
Volume	2005
ISSN (Print)	1082-3409

Conference

Conference	ICTAI 2005: 17th IEEE International Conference on Tools with Artificial Intelligence, ICTAI'05
Country/Territory	China
City	Hong Kong
Period	14/11/05 → 16/11/05

Access to Document

10.1109/ICTAI.2005.106

Cite this

@inproceedings{09954b9ebf9e46c39e13b980e9313faf,

title = "Reachability analysis for uncertain SSPs",

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 paper 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. We aim at a symbolic analysis in order to avoid a complete state-space enumeration.",

author = "Olivier Buffet",

year = "2005",

doi = "10.1109/ICTAI.2005.106",

language = "English",

isbn = "0769524885",

series = "Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI",

pages = "515--522",

booktitle = "ICTAI 2005",

note = "ICTAI 2005: 17th IEEE International Conference on Tools with Artificial Intelligence, ICTAI'05 ; Conference date: 14-11-2005 Through 16-11-2005",

}

Buffet, O 2005, Reachability analysis for uncertain SSPs. in ICTAI 2005: 17th IEEE International Conference on Tools with Artificial Intelligence, ICTAI'05., 1562987, Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI, vol. 2005, pp. 515-522, ICTAI 2005: 17th IEEE International Conference on Tools with Artificial Intelligence, ICTAI'05, Hong Kong, China, 14/11/05. https://doi.org/10.1109/ICTAI.2005.106

Reachability analysis for uncertain SSPs. / Buffet, Olivier.
ICTAI 2005: 17th IEEE International Conference on Tools with Artificial Intelligence, ICTAI'05. 2005. p. 515-522 1562987 (Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI; Vol. 2005).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Reachability analysis for uncertain SSPs

AU - Buffet, Olivier

PY - 2005

Y1 - 2005

N2 - 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 paper 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. We aim at a symbolic analysis in order to avoid a complete state-space enumeration.

AB - 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 paper 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. We aim at a symbolic analysis in order to avoid a complete state-space enumeration.

UR - http://www.scopus.com/inward/record.url?scp=33845909258&partnerID=8YFLogxK

U2 - 10.1109/ICTAI.2005.106

DO - 10.1109/ICTAI.2005.106

M3 - Conference contribution

SN - 0769524885

SN - 9780769524887

T3 - Proceedings - International Conference on Tools with Artificial Intelligence, ICTAI

SP - 515

EP - 522

BT - ICTAI 2005

T2 - ICTAI 2005: 17th IEEE International Conference on Tools with Artificial Intelligence, ICTAI'05

Y2 - 14 November 2005 through 16 November 2005

ER -

Reachability analysis for uncertain SSPs

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this