Problem Solving in Human Beings and Computers (formerly: Heuristic Problem Solving)
Zygmunt Pizlo, Anupam Joshi, Scott Graham · Purdue e-Pubs (Purdue University System) · 1994
The process of solving a problem has been traditionally represented as that of searching a graph, describing the problem space, to find a path from the start to the goal state.Prior research on human problem solving has shown that human beings do not perform an exhaustive search of the problem space.Instead, they attempt to identify and use intrinsic properties of the problem.This process involves insight, concept formation, establishing subgoals and invariant features.Such results from psychological research have been used by computer scientists in formalizing the concept of heuristic and applying it in Artificial Intelligence (AI) systems.It has been shown that, in the general case, heuristics allow restriding the search space which speeds up the search process.We first show that if the cosLs of edges in the search graph satisfy metric axioms an algorithm based on the evaluation fundion r develops only one (optimal) path.Second, we show that if a problem can be represented in a metric space, the solution of the problem can be determined by decomposing the problem into local regions and combining the local solutions into a global one.The implications of these analyses were tested in two experiments where human subjects were asked to solve the Traveling Salesman Problem (TSP).Our results show that the subjects are very efficient in metric (Euclidean) TSP, but not in non-metric TSP (where triangle inequality is violated).In the Euclidean TSP, the solution is nearly optimal and time is a linear function of the number of cities.These results suggest that human beings solve problems by building only a single path, rather than by performing a constrained search.We conclude by comparing the human performance to the performance of several conventional Al algorithms.This comparison shows that human beings solve problems by using heuristics that are quite different from existing AI heuristics.progress in AI has been relatively modest and, as a result, existing AI systems fall far behind NI.In this paper, we analyze how human beings solve some "difficult" problems, and propose a new approach that can be used in designing efficient algorithms to solve such problems using computers.We will begin by reviewing prior research from computer science and psychology.We will then critically analyze and discuss these approaches, and formulate a new approach based on the use of metric constraints in problem space.Then we will present results of psychological experiments and computer simulations that support our theoretical formulations.These experimental results also point to possible directions for future investigations.