Peng Dai, Judy Goldsmith
In 2003, Bhuma and Goldsmith introduced a bidirectional variant of Hansen and Zilberstein's LAO* algorithm called BLAO* for solving goal-based MDPs. BLAO* consistently ran faster than LAO* on the race-track examples used in Hansen and Zilberstein's paper. In this paper, we analyze the performance of BLAO* in comparison with both LAO* and our newly proposed algorithm, RLAO*, the reverse LAO* search, to understand what makes the bidirectional search work well.
Subjects: 1.11 Planning; 15.7 Search
Submitted: Jun 5, 2006