Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/172576 
Erscheinungsjahr: 
2017
Quellenangabe: 
[Journal:] Journal of Industrial Engineering International [ISSN:] 2251-712X [Volume:] 13 [Issue:] 4 [Publisher:] Springer [Place:] Heidelberg [Year:] 2017 [Pages:] 417-426
Verlag: 
Springer, Heidelberg
Zusammenfassung: 
Many hierarchical techniques to solve large Markov decision processes (MDPs) are based on the partition of the state space into strongly connected components (SCCs) that can be classified into some levels. In each level, smaller problems named restricted MDPs are solved, and then these partial solutions are combined to obtain the global solution. In this paper, we first propose a novel algorithm, which is a variant of Tarjan's algorithm that simultaneously finds the SCCs and their belonging levels. Second, a new definition of the restricted MDPs is presented to ameliorate some hierarchical solutions in discounted MDPs using value iteration (VI) algorithm based on a list of state-action successors. Finally, a robotic motion-planning example and the experiment results are presented to illustrate the benefit of the proposed decomposition algorithms.
Schlagwörter: 
Markov decision process
Graph theory
Tarjan's algorithm
Strongly connected components
Decomposition
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.