Multi-threaded BLAO* Algorithm

All Papers

We present a heuristic search algorithmfor solving goal based Markov decision processes (MDPs) named Multi-threaded BLAO* (MBLAO*). Hansen and Zilberstein proposed a heuristic search MDP solver named LAO*. Bhuma and Goldsmith extended LAO* to the bidirectional case and named their solver BLAO*. Recent experiments on BLAO* discovered that BLAO* outperforms LAO* by restricting the number of Bellman backups. MBLAO* is based on this observation. MBLAO* further restricts the number of backups by searching backward from the goal state, and also from some middle states (states along the most probable path from the start state to the goal state). Our experiments show that MBLAO* is more efficient than BLAO* and other state-of-the-art heuristic search MDP planners.