The Stochastic Arrival Problem

Thomas Webster

doi:10.1007/978-3-031-19135-0

The Stochastic Arrival Problem

Thomas Webster

School of Informatics

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

Abstract

We study a new modification of the Arrival problem, which allows for nodes that exhibit random as well as controlled behaviour, in addition to switching nodes. We study the computational complexity of these extensions, building on existing work on Reachability Switching Games. In particular, we show for versions of the arrival problem involving just switching and random nodes it is PP-hard to decide if their value is greater than a half and we give a PSPACE decision algorithm.

Original language	English
Title of host publication	Proceedings of the 16th International Conference on Reachability Problems
Editors	Anthony W. Lin, Georg Zetzsche, Igor Potapov
Publisher	Springer, Cham
Pages	93-107
Number of pages	15
ISBN (Electronic)	978-3-031-19135-0
ISBN (Print)	978-3-031-19134-3
DOIs	https://doi.org/10.1007/978-3-031-19135-0
Publication status	Published - 12 Oct 2022
Event	The 16th International Conference on Reachability Problems, 2022 - Kaiserslautern, Germany Duration: 17 Oct 2022 → 19 Oct 2022 Conference number: 16 https://rp2022.mpi-sws.org/submission.html

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Cham
Volume	13608
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	The 16th International Conference on Reachability Problems, 2022
Abbreviated title	RP 2022
Country/Territory	Germany
City	Kaiserslautern
Period	17/10/22 → 19/10/22
Internet address	https://rp2022.mpi-sws.org/submission.html

Keywords

Arrival
Markov Chains
Reachability Switching Games
MDPs
Simple Stochastic Games

Access to Document

10.1007/978-3-031-19135-0Licence: All Rights Reserved

The Stochastic_WEBSTER_DOA18082022_AFVAccepted author manuscript, 1.41 MBLicence: Creative Commons: Attribution (CC-BY)

https://link.springer.com/book/10.1007/978-3-031-19135-0Licence: All Rights Reserved

Cite this

@inproceedings{6da0d1383dde46aaa344210467883ad4,

title = "The Stochastic Arrival Problem",

abstract = "We study a new modification of the Arrival problem, which allows for nodes that exhibit random as well as controlled behaviour, in addition to switching nodes. We study the computational complexity of these extensions, building on existing work on Reachability Switching Games. In particular, we show for versions of the arrival problem involving just switching and random nodes it is PP-hard to decide if their value is greater than a half and we give a PSPACE decision algorithm.",

keywords = "Arrival, Markov Chains, Reachability Switching Games, MDPs, Simple Stochastic Games",

author = "Thomas Webster",

year = "2022",

month = oct,

day = "12",

doi = "10.1007/978-3-031-19135-0",

language = "English",

isbn = "978-3-031-19134-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Cham",

pages = "93--107",

editor = "Lin, {Anthony W.} and Georg Zetzsche and Igor Potapov",

booktitle = "Proceedings of the 16th International Conference on Reachability Problems",

note = "The 16th International Conference on Reachability Problems, 2022, RP 2022 ; Conference date: 17-10-2022 Through 19-10-2022",

url = "https://rp2022.mpi-sws.org/submission.html",

}

Webster, T 2022, The Stochastic Arrival Problem. in AW Lin, G Zetzsche & I Potapov (eds), Proceedings of the 16th International Conference on Reachability Problems. Lecture Notes in Computer Science, vol. 13608, Springer, Cham, pp. 93-107, The 16th International Conference on Reachability Problems, 2022, Kaiserslautern, Germany, 17/10/22. https://doi.org/10.1007/978-3-031-19135-0

TY - GEN

T1 - The Stochastic Arrival Problem

AU - Webster, Thomas

N1 - Conference code: 16

PY - 2022/10/12

Y1 - 2022/10/12

N2 - We study a new modification of the Arrival problem, which allows for nodes that exhibit random as well as controlled behaviour, in addition to switching nodes. We study the computational complexity of these extensions, building on existing work on Reachability Switching Games. In particular, we show for versions of the arrival problem involving just switching and random nodes it is PP-hard to decide if their value is greater than a half and we give a PSPACE decision algorithm.

AB - We study a new modification of the Arrival problem, which allows for nodes that exhibit random as well as controlled behaviour, in addition to switching nodes. We study the computational complexity of these extensions, building on existing work on Reachability Switching Games. In particular, we show for versions of the arrival problem involving just switching and random nodes it is PP-hard to decide if their value is greater than a half and we give a PSPACE decision algorithm.

KW - Arrival

KW - Markov Chains

KW - Reachability Switching Games

KW - MDPs

KW - Simple Stochastic Games

U2 - 10.1007/978-3-031-19135-0

DO - 10.1007/978-3-031-19135-0

M3 - Conference contribution

SN - 978-3-031-19134-3

T3 - Lecture Notes in Computer Science

SP - 93

EP - 107

BT - Proceedings of the 16th International Conference on Reachability Problems

A2 - Lin, Anthony W.

A2 - Zetzsche, Georg

A2 - Potapov, Igor

PB - Springer, Cham

T2 - The 16th International Conference on Reachability Problems, 2022

Y2 - 17 October 2022 through 19 October 2022

ER -

The Stochastic Arrival Problem

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this