Integrating knowledge in problem solving search procedures

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. 1.A. Barr and E. A. Feigenbaum, The Handbook of Artificial Intelligence Vol I, William Kaufman, Inc., Los Altos, CA, 1981.
2. 2.R. E. Bellman, Dynamic Programming, Princeton University Press, Princeton, NJ, 1957.
3. 3.H. Berliner, The B Tree Search Algorithm: A Best-First Proof Procedure, Artificial Intelligence 12, pp. 23-40, 1979.
4. 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. 5.P. R. Cohen and E. A. Feigenbaum, The Handbook of Artificial Intelligence, Vol III, William Kaufman, Inc., Los Altos, CA, 1982.
6. 6.E. W. Dijkstra, A Note on Two Problems in Connection with Graphs, Numer. Math. 1, pp. 269-271, 1959.
7. 7.S. E. Dreyfus and A. M. Law, The Art and Theory of Dynamic Programming, Academic Press, New York, 1977.
8. 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. 9.E. C. Freuder, A Sufficient Condition for Backtrack-Free Search, JACM 29, 1, pp. 24-32, Jan. 1982.
10. 10.P. A. V. Hall, Equivalence between AND/OR Graphs and Context-Free Grammars, Comm. ACM 16, pp. 444-445, 1973.
11. 11.E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms, Computer Science Press, Potomac, MD, 1978.
12. 12.T. Ibaraki, Branch-and-Bound Procedure and State-Space Representation of Combinatorial Optimization Problems, Inform and Control 36, pp. 1-27, 1978.
13. 13.R. M. Karp and M. H. Held, Finite-State Processes and Dynamic Programming, SIAM J. Appl. Math 15, pp. 693-718, 1967.
14. 14.D. E. Knuth, A Generalization of Dijkstra's Algorithm, Information Processing Letters 6, pp. 1-6, 1977.
15. 15.D. E. Knuth and R. W. Moore; An Analysis of Alpha-Beta Pruning, Artificial Intelligence 6, pp. 293-326, 1975.
16. 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. 17.V. Kumar, A Unified Approach to Problem Solving Search Procedures, Ph.D. thesis, Dept. of Computer Science, University of Maryland, College Park, December, 1982.
18. 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. 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. 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. 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. 22.E. L. Lawler and D. E. Wood, Branch-and-Bound Methods: A Survey, Operations Research 14, pp. 699-719, 1966.
23. 23.A. Martelli and U. Montanari, Additive AND/OR Graphs, Proc. Third Internat. Joint Conf. on Artif. Intell., pp. 1-11, 1973.
24. 24.A. Martelli and U. Montanari, Optimizing Decision Trees Through Heuristically Guided Search, Comm. ACM 21, pp. 1025-1039, 1978.
25. 25.D. S. Nau, V. Kumar, and L. N. Kanal, General Branch-and-Bound and its Relation to A and AO, Artificial Intelligence, 1984.
26. 26.N. Nilsson, Principles of Artificial Intelligence, Tioga Publ. Co., Palo Alto. CA, 1980.
27. 27.L. M. Pereira and A. Porto, Selective Backtracking, pp. 107-114 in Logic Programming, ed. S. Tarnlund, Academic Press, 1982.
28. 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. 29.M. O. Rabin, Theoretical Impediments to Artificial Intelligence, Proc. of IFIP congress, pp. 615-619, 1974.
30. 30.G. C. Stockman, A Minimax Algorithm Better than Alpha-Beta?, Artificial Intelligence 12, pp. 179-196, 1979.
31. 31.G. J. Sussman and D. V. McDermott, From Planner to Conniver: A Genetic Approach, AFIPS, pp. 1171-1180, 1972.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Control methods

    • Search methodologies

• Theory of computation

  • Design and analysis of algorithms

    • Algorithm design techniques

      • Dynamic programming

  • Randomness, geometry and discrete structures