OGA-UCT: On the Go Abstractions in UCT. Ankit Anand, R. N. & Mausam, P. S. .
abstract   bibtex   
Recent work has begun exploring the value of domain abstractions in Monte-Carlo Tree Search (MCTS) algo- rithms for probabilistic planning. These algorithms au- tomatically aggregate symmetric search nodes (states or state-action pairs) saving valuable planning time. Exis- ting algorithms alternate between two phases: (1) ab- straction computation for computing node aggregations, and (2) modified MCTS that use aggregate nodes. We believe that these algorithms do not achieve the full po- tential of abstractions because of disjoint phases � e.g., recovery from erroneous abstractions can be slow. In response, we propose On the Go Abstractions (OGA), a novel approach in which abstraction compu- tation is tightly integrated into the MCTS algorithm. We implement these on top of UCT and name the resulting algorithm OGA-UCT. It has several desirable proper- ties, including (1) rapid use of new information in mod- ifying existing abstractions, (2) elimination of the ex- pensive batch abstraction computation phase, and (3) focusing abstraction computation on important part of the sampled search space,. We experimentally compare OGA-UCT against ASAP-UCT, a recent state-of-the- art MDP algorithm as well as vanilla UCT algorithm. We find that across a suite of planning competition and other MDP domains, OGA-UCT performs better or at par with the best technique on each domain obtaining up to 18 % quality improvements.
@inproceeduings {icaps16-225,
  track    = {Main Track},
  title    = {OGA-UCT: On the Go Abstractions in UCT},
  author   = {Ankit Anand, Ritesh Noothigattu,  Mausam, Parag Singla},
  abstract = {Recent work has begun exploring the value of domain
abstractions in Monte-Carlo Tree Search (MCTS) algo-
rithms for probabilistic planning. These algorithms au-
tomatically aggregate symmetric search nodes (states or
state-action pairs) saving valuable planning time. Exis-
ting algorithms alternate between two phases: (1) ab-
straction computation for computing node aggregations,
and (2) modified MCTS that use aggregate nodes. We
believe that these algorithms do not achieve the full po-
tential of abstractions because of disjoint phases � e.g.,
recovery from erroneous abstractions can be slow.

In response, we propose On the Go Abstractions
(OGA), a novel approach in which abstraction compu-
tation is tightly integrated into the MCTS algorithm. We
implement these on top of UCT and name the resulting
algorithm OGA-UCT. It has several desirable proper-
ties, including (1) rapid use of new information in mod-
ifying existing abstractions, (2) elimination of the ex-
pensive batch abstraction computation phase, and (3)
focusing abstraction computation on important part of
the sampled search space,. We experimentally compare
OGA-UCT against ASAP-UCT, a recent state-of-the-
art MDP algorithm as well as vanilla UCT algorithm.
We find that across a suite of planning competition and
other MDP domains, OGA-UCT performs better or at
par with the best technique on each domain obtaining
up to 18 % quality improvements.},
  keywords = {Probabilistic planning; MDPs and POMDPs}
}

Downloads: 0