Depth-limited search for real-time problem solving
Tóm tắt
We propose depth-limited heuristic search as a general paradigm for real-time problem solving in a dynamic environment. When combined with iterative-deepening, it provides the ability to commit to an action almost instantaneously, but allows the quality of that decision to improve as long as time is available. Once a deadline is reached, the best decision arrived at is executed. We illustrate the paradigm in three different settings, corresponding to single-agent search, two-player games, and multi-agent problem solving. First we review two-player minimax search with alpha-beta pruning. Minimax can be extended to themaxn algorithm for more than two players, which admits a much weaker form of alpha-beta pruning. Finally, we explore real-time search algorithms for single-agent problems. Minimax is specialized tominimin, which allows a very powerfulalpha pruning algorithm. In addition,real-time-A
* allows backtracking while still guaranteeing a solution and making locally optimal decisions.
Tài liệu tham khảo
Newell, A., H.A. Simon, and J.C. Shaw. 1963. Empirical explorations with the logic theory machine: A case study in heuristics. InComputers and Thought, E. Feigenbaum and J. Feldman (Eds.), New York: McGraw-Hill.
Samuel, A.L. 1963. Some studies in machine learning using the game of checkers. InComputers and Thought, E. Feigenbaum and J. Feldman (Eds.), New York: McGraw-Hill.
Berliner, H. 1989. Deep-Thought wins Fredkin Intermediate Prize.AI Magazine, 0, 2, (Summer).
Korf, R.E. 1985. Depth-first iterative-deepening: An optimal admissible tree search.Artificial Intelligence, 27, 1:97–109.
Korf, R.E. 1988. Search in AI: A survey of recent results. InExploring Artificial Intelligence. Los Altos, CA: Morgan-Kaufmann.
Korf, R.E. 1990. Mult-player alpha-beta pruning.Artificial Intelligence (to appear).
Korf, R.E. 1990. Real-time heuristic search.Artificial Intelligence (to appear).
Shannon, C.E. 1980. Programming a Computer for Playing Chess.Philosophical Magazine, 41:256–275.
Pearl, J. 1984.Heuristics. Reading, MA: Addison-Wesley.
Hart, T.P., and D.J. Edwards. 1963. The alpha-beta heuristic. M.I.T. Artificial Intelligence Project Memo, Massachusetts Institute of Technology, Cambridge, MA, October.
Knuth, D.E., and R.E. Moore. 1975. An analysis of Alpha-beta pruning.Artificial Intelligence, 6,4: 293–326.
Pearl, J. 1982. The solution for the branching factor of the Alpha-Beta pruning algorithm and its optimality.Communications of the Association of Computing Machinery 25, 8:559–564.
Luckhardt, C.A., and K.B. Irani. 1986. An algorithmic solution of N-person games.Proceedings of the National Conference on Artificial Intelligence (AAAI-86), Philadelphia, PA, (Aug):158–162.
Hart, P.E., N.J. Nilsson, and B. Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths.IEEE Transactions on Systems Science and Cybernetics, SSC-4, 2:100–107.
Rosenberg, R.S., and J. Kestner. 1972. Look-ahead and one-person games.Journal of Cybernetics, 2, 4: 27–42.
Horvitz, E.J., G.F. Cooper, and D.E. Heckerman. 1989. Reflection and action under scarce resources: Theoretical principles and empirical study. InProceedings of the International Conference on Artificial Intelligence (IJCAI-89), Detroit, Michigan, (Aug):1121–1127.
Boddy, M., and T. Dean. 1989. Solving time-dependent planning problems. InProceedings of the International Conference on Artificial Intelligence (IJCAI-89), Detroit, Michigan, (Aug): 979–984.
Russell, S., and E. Wefald. 1989. On optimal game-tree search using rational meta-reasoning. InProceedings of the International Conference on Artificial Intelligence (IJCAI-89), Detroit, Michigan, (Aug):334–340.