Anytime optimal MDP planning with trial-based heuristic tree search

Hochschulschrift

Zusammenfassung: Planning and acting in a dynamic environment is a challenging task for an autonomous agent, especially in the presence of uncertain and exogenous effects, a large number of states, and a long-term planning horizon. In this thesis, we approach the problem by considering algorithms that interleave planning for the current state and execution of the taken decision. The main challenge of the agent is to use its tight deliberation time wisely.One solution are determinizations, which simplify the Markov Decision Process that describes the uncertain environment to a deterministic planning problem. We introduce an all-outcomes determinization where, unlike in comparable methods, the number of deterministic actions is not exponentially but polynomially bounded in the number of parallel probabilistic effects. We discuss three algorithms that base their decision solely on the solution to a determinization, and show that they have fundamental limitations that prevent optimal behavior even if provided with unlimited resources.The main contribution of this thesis, the Trial-based Heuristic Tree Search (THTS) framework, allows the description of algorithms in terms of only six ingredients that can be mixed and matched at will. We present a selection of ingredients and analyze theoretically which combinations yield asymptotically optimal behavior.

Object Details

• Location: Deutsche Nationalbibliothek Frankfurt am Main
• Extent: Online-Ressource
• Language: Englisch
• Notes: Albert-Ludwigs-Universität Freiburg, Dissertation, 2015

Classification and Topics

• Classification: Informatik

Contributors, Places and Time

• Event: Veröffentlichung
• (where): Freiburg
• (who): Universität
• (when): 2015
• Creator: Keller, Thomas
• Contributor: Nebel, Bernhard

Further information

• DOI: 10.6094/UNIFR/11034
• URN: urn:nbn:de:bsz:25-freidok-110346
• Rights: Der Zugriff auf das Objekt ist unbeschränkt möglich.
• Last update: 25.03.2025, 1:42 PM CET