A methodology for solving problems in artificial intelligence (automated reasoning, heuristics, a-star algorithm, model problem)

Abstract

For the development of a general and efficient approach for solving problems, a metholodogy for deriving a heuristic for the A* algorithm is discussed. A systematic approach for modeling a problem using the knowledge in the problem domain is first presented in which a set of elementary units and a set of attributes of the problem are defined. Algorithms to derive a heuristic for A* are then developed for this problem model. The procedure for modeling a problem and deriving the heuristic for the problem is illustrated by several examples, namely, the 8-puzzle problem, the traveling salesman problem, the robot planning problem, the consistent labeling problem, and the theorem proving problem. For problems such as the 8-puzzle problem, the traveling salesman problem, the robot planning problem, and the consistent labeling problem in which the goal is completely defined, our problem solving approach results in good efficiency. For problems such as the theorem proving problem in which the goal is partially defined, our approach results in poor efficiency. For deriving the heuristic for A* which results in better problem solving efficiency, various other versions of the basic problem model are suggested. The versions are given by partitioning the set of elementary units and the set of attributes of the problem. Some of these models are compared against each other for complexity for deriving the heuristic and for tightness of the derived heuristic.