|
Published Articles >> Table of Contents >> Abstract
September 1988 (Vol. 10, No. 5)
pp. 676-686
A Methodology for Solving Problems: Problem Modeling and Heuristic Generation
K.B. Irani
S.I. Yoo
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/34.6776
Send link to a friend
| Abstract |
|
A methodology is given for modeling a problem and solving it using the A* algorithm. The heuristic used for A* is mechanically generated from the simplified problem, which is derived by relaxing each of the predicate formulas describing the rules and the goal state of the problem. The generated heuristic satisfies the conditions of admissibility and monotonicity. The methodology is applicable for solving general problems. The overall procedure for this methodology is illustrated by four well-known problems, namely, the eight-puzzle problem, the traveling salesman problem, the robot planning problem, and the consistent labeling problem. The values of the heuristics generated by this procedure are compared to the corresponding values of problem-oriented heuristics reported in the literature.
|
 References
|
[1] J. Gaschnig, "Exactly how good are heuristics?: Towards a real predictive theory of best first search," inProc. IJCAI, Aug. 1977, pp. 434-441.
[2] J. Gaschnig, "A problem similarity approach to devising heuristics: First results," inProc. IJCAI, 1979.
[3] G. Guida and M. Somalvico, "A method for computing heuristics in problem solving,"Inform. Sci., vol. 19, pp. 251-259, 1979.
[4] L. Harris, "The heuristic search under conditions of error,"Artif Intell., vol. 5, 1974.
[5] P. Hart, N. Nilsson, and B. Raphael, "A formal basis for the heuristic determination of minimum cost paths,"IEEE Trans. Syst. Sci. Cybernet., vol. 4, no. 2, 1968.
[6] R. Haralick and L. Daviosenfeld, "Reduction operations for constraint satisfaction,"Inform. Sci., vol. 14, pp. 199-219, 1978.
[7] R. Haralick and L. Shapiro, "The consistent labeling problem: Part I,"IEEE Trans. Pattern Anal. Mach. Intell., vol. PAMI-1, Apr. 1979.
[8] M. Held and R. Karp, "The traveling salesman problem and minimum spanning tree,"Oper. Res., vol. 19, 1971.
[9] A. K. Mackworth, "Consistency in networks of relations,"Artif. Intell., vol. 8, pp. 99-118, 1977.
[10] N. Nilsson,Principles of Artificial Intelligence. Palo Alto, CA: Tioga, 1980.
[11] J. Pearl, "On the discovery and generation of certain heuristics,"AI Mag., vol. 4, no. 1, winter-spring 1983.
[12] J. Pearl,Heuristics: Intelligent Search Strategies for Computer Problem Solving. Reading, Mass: Addison-Wesley, 1984.
[13] I. Pohl, "The avoidance of (relative) catastrophe, heuristic competence, genuine dynamic weighting and computational issues in heuristic problem-solving," inProc. IJCAI, 1973.
[14] L. Rendell, "A new basis for state-space learning systems and a successful implementation,"Artif Intell., vol. 21, 1983.
[15] S. Yoo, "A methodology for solving problems in artificial intelligence," Ph.D. dissertation, Dep. Elec. Eng. Comput. Sci., Univ. Mich., Ann Arbor, MI, July 1985.
|
 Additional Information
|
Index Terms- problem solving; methodology; problem modeling; heuristic generation; traveling salesman problem; robot planning problem; labeling problem; problem solving
Citation:
K.B. Irani, S.I. Yoo,
"A Methodology for Solving Problems: Problem Modeling and Heuristic Generation,"
IEEE Transactions on Pattern Analysis and Machine Intelligence,
vol. 10,
no. 5,
pp. 676-686,
Sept.,
1988
|
|
RSS Feed