Trial-based Heuristic Tree Search for MDPs with Factored Action Spaces

Geißer, Florian and Speck, David and Keller, Thomas. (2020) Trial-based Heuristic Tree Search for MDPs with Factored Action Spaces. In: Proceedings of the 13th Annual Symposium on Combinatorial Search (SoCS 2020). pp. 38-47.

[img] PDF - Accepted Version

Official URL: https://edoc.unibas.ch/78709/

Downloads: Statistics Overview


MDPs with factored action spaces, i.e. where actions are described as assignments to a set of action variables, allow reasoning over action variables instead of action states, yet most algorithms only consider a grounded action representation. This includes algorithms that are instantiations of the trial-based heuristic tree search (THTS) framework, such as AO* or UCT. To be able to reason over factored action spaces, we propose a generalisation of THTS where nodes that branch over all applicable actions are replaced with subtrees that consist of nodes that represent the decision for a single action variable. We show that many THTS algorithms retain their theoretical properties under the generalised framework, and show how to approximate any state-action heuristic to a heuristic for partial action assignments. This allows to guide a UCT variant that is able to create exponentially fewer nodes than the same algorithm that considers ground actions. An empirical evaluation on the benchmark set of the probabilistic track of the latest International Planning Competition validates the benefits of the approach.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Keller, Thomas
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:29 Sep 2020 08:25
Deposited On:29 Sep 2020 08:25

Repository Staff Only: item control page