×

LAO*: A heuristic search algorithm that finds solutions with loops. (English) Zbl 0971.68036

Summary: Classic heuristic search algorithms can find solutions that take the form of a simple path (A*), a tree, or an acyclic graph (AO*). In this paper, we describe a novel generalization of heuristic search, called LAO*, that can find solutions with loops. We show that LAO* can be used to solve Markov decision problems and that it shares the advantage heuristic search has over dynamic programming for other classes of problems. Given a start state, it can find an optimal solution without evaluating the entire state space.

MSC:

68P10 Searching and sorting
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barto, A. G.; Bradtke, S. J.; Singh, S. P., Learning to act using real-time dynamic programming, Artificial Intelligence, 72, 81-138 (1995)
[2] Bertsekas, D., Dynamic Programming and Optimal Control (1995), Athena Scientific: Athena Scientific Belmont, MA
[3] Chakrabarti, P. P.; Ghose, S.; DeSarkar, S. C., Admissibility of AO∗ when heuristics overestimate, Artificial Intelligence, 34, 97-113 (1988) · Zbl 0643.68153
[4] Davis, H. W.; Bramanti-Gregor, A.; Wang, J., The advantages of using depth and breadth components in heuristic search, (Ras, Z. W.; Saitta, L., Methodologies for Intelligent Systems Vol. 3 (1989), North-Holland: North-Holland Amsterdam), 19-28
[5] Dean, T.; Kaelbling, L. P.; Kirman, J.; Nicholson, A., Planning under time constraints in stochastic domains, Artificial Intelligence, 76, 35-74 (1995)
[6] Dearden, R.; Boutilier, C., Integrating planning and execution in stochastic domains, (Proc. Tenth Conference on Uncertainty in Artificial Intelligence (1994), Washington, DC), 162-169
[7] Dechter, R.; Pearl, J., Generalized best-first search strategies and the optimality of A∗, J. ACM, 32, 505-536 (1985) · Zbl 0631.68075
[8] Hansen, E. A.; Zilberstein, S., Heuristic search in cyclic AND/OR graphs, (Proc. AAAI-98, Madison, WI (1998)), 412-418
[9] Ishida, T.; Shimbo, M., Improving the learning efficiencies of realtime search, (Proc. AAAI-96, Portland, OR (1996)), 305-310
[10] Jiménez, P.; Torras, C., An efficient algorithm for searching implicit AND/OR graphs with cycles, Artificial Intelligence, 124, 1-30 (2000) · Zbl 0957.68034
[11] Korf, R., Real-time heuristic search, Artificial Intelligence, 42, 189-211 (1990) · Zbl 0718.68082
[12] Lian, Z.; Deshmukh, A.; Wang, J., Optimal frozen period in a periodic review inventory model with updateable demand forecasts, (Proc. 15th International Conference on Production Research (1999))
[13] Martelli, A.; Montanari, U., Additive AND/OR graphs, (Proc. IJCAI-73, Stanford, CA (1973)), 1-11
[14] Martelli, A.; Montanari, U., Optimizing decision trees through heuristically guided search, Comm. ACM, 21, 12, 1025-1039 (1978) · Zbl 0395.90079
[15] Mérõ, L., A heuristic search algorithm with modifiable estimate, Artificial Intelligence, 23, 1, 13-27 (1984) · Zbl 0537.68063
[16] Nilsson, N. J., Search problem-solving and game-playing trees for minimal cost solutions, (Morrell, A., Information Processing 68, Vol. 2 (1969), North-Holland: North-Holland Amsterdam), 1556-1562
[17] Nilsson, N. J., Problem Solving Methods in Artificial Intelligence (1971), McGraw-Hill: McGraw-Hill New York
[18] Nilsson, N. J., Principles of Artificial Intelligence (1980), Tioga Publishing: Tioga Publishing Palo Alto, CA · Zbl 0422.68039
[19] Pattipati, K. R.; Alexandridis, M. G., Application of heuristic search and information theory to sequential fault diagnosis, IEEE Trans. Systems Man Cybernet., 20, 4, 872-887 (1990) · Zbl 0709.68006
[20] Pohl, I., First results on the effect of error in heuristic search, Machine Intelligence, 5, 219-236 (1973) · Zbl 0221.68058
[21] Tash, J.; Russell, S. J., Control strategies for a stochastic planner, (Proc. AAAI-94, Seattle, WA (1994)), 1079-1085
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.