OGA-UCT: On-the-Go Abstractions in UCT. Anand, A., Noothigattu, R., Mausam, & Singla, P. In
OGA-UCT: On-the-Go Abstractions in UCT [link]Paper  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.
@inproceedings {icaps16-225,
    track    = {​Main Track},
    title    = {OGA-UCT: On-the-Go Abstractions in UCT},
    url      = {http://www.aaai.org/ocs/index.php/ICAPS/ICAPS16/paper/view/13060},
    author   = {Ankit Anand and  Ritesh Noothigattu and   Mausam and  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