Year of Publication
Master of Science (MS)
Dr. Judy Goldsmith
Uncertainty is a feature of many AI applications. While there are polynomial-time algorithms for planning in stochastic systems, planning is still slow, in part because most algorithms plan for all eventualities. Algorithms such as LAO* are able to find good or optimal policies more quickly when the starting state of the system is known.
In this thesis we present an extension to LAO*, called BLAO*. BLAO* is an extension of the LAO* algorithm to a bidirectional search. We show that BLAO* finds optimal or E-optimal solutions for goal-directed MDPs without necessarily evaluating the entire state space. BLAO* converges much faster than LAO* or RTDP on our benchmarks.
Bhuma, Venkata Deepti Kiran, "Bidirectional LAO* Algorithm (A Faster Approach to Solve Goal-directed MDPs)" (2004). University of Kentucky Master's Theses. 225.