Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

With the help of a model for discrete optimization problems, we show that a large number of heuristic search procedures (for searching state-space graphs, AND/OR graphs, game trees, etc.) of artificial intelligence (AI), and dynamic programming (DP) and branch-and-bound (B&B) procedures of operations research use problem-specific knowledge in a framework based upon context-free grammar. The model reveals the true nature of these procedures, and aids in synthesizing new variations as well as generalizations and parallel implementations of these procedures. The paper concludes by commenting upon how this model may be generalized and made more powerful to encompass a greater variety of problems, and to help synthesize more efficient search procedures.

REFERENCES

• 1: Avron Barr , Edward A. Feigenbaum, Handbook of AI, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 2: Richard Ernest Bellman, Dynamic Programming, Dover Publications, Incorporated, 2003
• 3: H. Berliner, The B Tree Search Algorithm: A Best-First Proof Procedure, Artificial Intelligence 12, pp. 23-40, 1979.
• 4: M. Bruynooghe, Intelligent Backtracking for an Interpreter of Horn Clause Logic Programs, Report CW 16, Applied Math and Programming Division, Katholieke Univ., Leuven, Belgium, 1978.
• 5: P. R. Cohen and E. A. Feigenbaum, The Handbook of Artificial Intelligence, Vol III, William Kaufman, Inc., Los Altos, CA, 1982.
• 6: E. W. Dijkstra, A Note on Two Problems in Connection with Graphs, Numer. Math. 1, pp. 269-271, 1959.
• 7: Stuart E. Dreyfus , Averill M. Law, Art and Theory of Dynamic Programming, Academic Press, Inc., Orlando, FL, 1977
• 8: G. W. Ernst and R. B. Banerji, On the Relationship Between Strong and Weak problem Solvers, The AI Magazine, pp. 25-30, summer 1983.
• 9: Eugene C. Freuder, A Sufficient Condition for Backtrack-Free Search, Journal of the ACM (JACM), v.29 n.1, p.24-32, Jan. 1982 [doi>10.1145/322290.322292]
• 10: Patrick A. V. Hall, Equivalence between AND/OR graphs and context-free grammars, Communications of the ACM, v.16 n.7, p.444-445, July 1973 [doi>10.1145/362280.362302]
• 11: Ellis Horowitz , Sartaj Sahni, Fundamentals of Computer Alori, W. H. Freeman & Co., New York, NY, 1978
• 12: T. Ibaraki, Branch-and-Bound Procedure and State-Space Representation of Combinatorial Optimization Problems, Inform and Control 36, pp. 1-27, 1978.
• 13: R. M. Karp and M. H. Held, Finite-State Processes and Dynamic Programming, SIAM J. Appl. Math 15, pp. 693-718, 1967.
• 14: D. E. Knuth, A Generalization of Dijkstra's Algorithm, Information Processing Letters 6, pp. 1-6, 1977.
• 15: D. E. Knuth and R. W. Moore; An Analysis of Alpha-Beta Pruning, Artificial Intelligence 6, pp. 293-326, 1975.
• 16: M. Kohli and J. Minker, Intelligent Control Using Integrity Constraints, Proc. of the National Conf. on Artificial Intelligence (AAAI-83), pp. 202-205, 1983.
• 17: Vipin Kumar, A unified approach to problem solving search procedures, 1982
• 18: V. Kumar, A General Bottom-up Procedure for Searching And/Or Graphs., Proc. National Conference on Artificial Intelligence (AAAI-84), Austin, Texas, 1984.
• 19: V. Kumar and L. Kaual, A General Branch and Bound Formulation for Understanding and Synthesizing And/Or Tree Search Procedures, Artificial Intelligence 21, 1, pp. 179-198, 1983.
• 20: V. Kumar and L. N. Kanal, The Composite Decision Process: A Unifying Formulation for Heuristic Search, Dynamic Programming and Branch & Bound Procedures, 1983 National Conference on Artificial Intelligence (AAAI-83), Washington, D.C., pp. 220-224, August 1983.
• 21: V. Kumar and L. N. Kanal, Parallel Branch and Bound Formulations for And/Or Tree Search, IEEE Trans. on Pattern Analysis and Machine Intelligence (to appear), 1984.
• 22: E. L. Lawler and D. E. Wood, Branch-and-Bound Methods: A Survey, Operations Research 14, pp. 699-719, 1966.
• 23: A. Martelli and U. Montanari, Additive AND/OR Graphs, Proc. Third Internat. Joint Conf. on Artif. Intell., pp. 1-11, 1973.
• 24: Alberto Martelli , Ugo Montanari, Optimizing decision trees through heuristically guided search, Communications of the ACM, v.21 n.12, p.1025-1039, Dec. 1978 [doi>10.1145/359657.359664]
• 25: Dana S. Nau , Vipin Kumar , Laveen Kanal, General branch and bound, and its relation to A* and AO*, Artificial Intelligence, v.23 n.1, p.29-58, May 1984 [doi>10.1016/0004-3702(84)90004-3]
• 26: N. J. Nilsson, Principles of artificial intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1980
• 27: L. M. Pereira and A. Porto, Selective Backtracking, pp. 107-114 in Logic Programming, ed. S. Tarnlund, Academic Press, 1982.
• 28: P. W. Purdom, C. A. Brown, and E. L. Robertson, Backtracking with Multi-level Dynamic Search Rearrangement, Acta Inform. 15, pp. 99-113, 1981.
• 29: M. O. Rabin, Theoretical Impediments to Artificial Intelligence, Proc. of IFIP congress, pp. 615-619, 1974.
• 30: G. C. Stockman, A Minimax Algorithm Better than Alpha-Beta?, Artificial Intelligence 12, pp. 179-196, 1979.
• 31: G. J. Sussman and D. V. McDermott, From Planner to Conniver: A Genetic Approach, AFIPS, pp. 1171-1180, 1972.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Theory