Multi-threaded BLAO* Algorithm

Peng Dai, Judy Goldsmith

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.

Subjects: 1.11 Planning

Submitted: Feb 8, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.