Algoritmo de Monte Carlo Tree Search para SSPs sob o critério GUBS

Em planejamento probabilístico, um problema comum é o de caminho estocastico mais curto (SSP), no qual se deseja encontrar políticas que chegam a uma meta com o menor custo acumulado esperado. A presença de estados a partir dos quais não é possível alcançar uma meta, os dead-ends, torna esse critério indefinido nesses estados. Por isso, existem extensões e novas formulações para esse caso particular, como o critério GUBS. Embora existam algoritmos para solucionar esse critério, todos eles necessitam iterar pelo espaço completo de estados. Tendo isso em vista, no presente trabalho é proposto o UCT-GUBS, um algoritmo online de planejamento baseado no UCT para resolver SSPs sob o criterio GUBS. Os resultados dos experimentos realizados mostram empiricamente que o algoritmo demonstra um compromisso entre custo e probabilidade para a meta conforme a variação dos seus parâmetros, podendo tomar uma decisão em um tempo menor ou maior dependendo do tempo limite passado para o algoritmo, que é uma característica importante do UCT.