Robust Shortest Path with Incremental Information Revelation

In this paper, we consider the problem of finding the shortest path in a graph when there is aleatoric uncertainty about the presence and/or cost of certain edges. We investigate hybrid path planning, in which an agent observes the uncertain information as it traverses the graph and may adapt to the new information. We model this problem as a robust partially observable Markov decision process (robust POMDP) and identify an information state for dynamic programming decomposition. We propose a series of pruning steps, which truncate the state space based on the relationship between the cost and the uncertainty. We then show how to adapt the Neural Monte Carlo Tree Search (Neural MCTS) algorithm to obtain an approximate solution. Finally, we present a numerical study to illustrate the effectiveness of the proposed approach.