Multi-threaded BLAO* algorithm

We present a heuristic search algorithm for solving goal based Markov decision processes (MDPs) named Multi-threaded BLAO* (MBLAO*). Hansen and Zilberstein proposed a heuristic search MDP solver named LAO* (Hansen & Zilberstein 2001). Bhuma and Goldsmith extended LAO* to the bidirectional case (Bhuma & Goldsmith 2003) and named their solver BLAO*. Recent experiments on BLAO* (Dai & Goldsmith 2006) 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.