When is Psychology Research Useful in Artificial Intelligence? A Case for Reducing Computational Complexity in Problem Solving

Abstract

A problem is a situation in which an agent seeks to attain a given goal without knowing how to achieve it. Human problem solving is typically studied as a search in a problem space composed of states (information about the environment) and operators (to move between states). A problem such as playing a game of chess has ${10}^{120}$ possible states, and a traveling salesperson problem with as little as 82 cities already has more than ${10}^{120}$ different tours (similar to chess). Biological neurons are slower than the digital switches in computers. An exhaustive search of the problem space exceeds the capacity of current computers for most interesting problems, and it is fairly clear that humans cannot in their lifetime exhaustively search even small fractions of these problem spaces. Yet, humans play chess and solve logistical problems of similar complexity on a daily basis. Even for simple problems humans do not typically engage in exploring even a small fraction of the problem space. This begs the question: How do humans solve problems on a daily basis in a fast and efficient way? Recent work suggests that humans build a problem representation and solve the represented problem-not the problem that is out there. The problem representation that is built and the process used to solve it are constrained by limits of cognitive capacity and a cost-benefit analysis discounting effort and reward. In this article, we argue that better understanding the way humans represent and solve problems using heuristics can help inform how simpler algorithms and representations can be used in artificial intelligence to lower computational complexity, reduce computation time, and facilitate real-time computation in complex problem solving.

Keywords: Artificial intelligence; Heuristics; Problem representation; Problem solving; Reinforcement learning.