17.08.14 - 22.08.14, Seminar 14341

Resource-bounded Problem Solving

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.


Problem solving, whether by humans or machines, is bounded by the resources at hand. For machines, important resources are hardware and processing speed; additional resources for humans include mental representations, memory capacities, and inferential capacities. All these resources can be severely limited, by constraints imposed by both the implementing hardware (current technology in the case of machines, the organization of our brains in the case of humans) and the physical and social operating environments.

The study of resource-bounded problem solving has a long and productive history within computer science, which has resulted in a number of efficient exact-solution algorithms and algorithm design techniques as well as, where such algorithms are not possible, various widely-applicable approximate-solution heuristics. Given that brains have evolved to solve problems under severe resource constraints, resource-bounded problem solving may also provide one of the best windows on the organization of cognitive brain function. Trying to model exactly how humans solve really hard - that is, resource demanding - problems efficiently seems a good strategy from the perspective of deriving predictive and explanatory cognitive models. Cognitive models that match human performance on really easy problems are easy to find, but if one can find even one model that can solve a hard problem as well as humans, one can be much more confi dent that this model captures fundamental principles of human cognition.

What makes tasks resource demanding? Here computational complexity theory is a key source of information for the study of human and machine problem solving, as it allows us to assess when the intrinsic resource demands of computational problems are low, reasonable, high, or impractically high. Computational complexity has been underutilized to date in psychology. This is not for want of opportunities, as cases are known where psychologists have studied principles of resource-bounded problem solving in apparent ignorance of relevant computational complexity results (e.g. the independent psychological proposal (MacGregor and Ormerod, 1996) and computational confirmation (Deineko et al., 2004) that the difficulty of solving Euclidean versions of the Traveling Salesperson problem is a function of the number of inner points). There is also evidence that when such opportunities are exploited and psychologists and complexity theorists establish long-term ongoing collaborations (as has been done by Iris van Rooij, Todd Wareham, Johan Kwisthout and others with respect to analyzing resource demands of cognitive models and Yll Haxhimusa, Zygmunt Pizlo, Walter Kropatsch and others with respect to pyramid data structures as models of efficient search in humans and machines), such collaborations can yield novel perspectives and approaches.

With this seminar we aim to stimulate the exchange of ideas and results between complexity theorists and psychologists studying problem solving. Invitees will be split evenly between those whose primary expertise is in complexity theory, psychology, artificial intelligence, and cognitive neuroscience. The intent is to balance theoretical with implementation-level perspectives on resources required for problem solving in machines and humans. Questions that the seminar aims to address include (but are not limited to) the following:

  • Why are some problems that are difficult for machines very easy for humans, and vice versa? Could this be explained by humans and machines making different use of resources?
  • Are human brains optimized to use their resources in particular ways which may support some types of problem solving but not others? How can we achieve similar ways of optimizing resource usage in machines?
  • Can new computational complexity theory be developed relative to resources other than time and space that are also relevant for studying resource-bounded human problem solving?
  • How can computational complexity theoretic predictions for cognitive models of resource-bounded problem solving be empirically tested?
  • How can cognitive models of resource-bounded problem solving interface with neural models of brain organization?

Participants will be invited to publish their ideas in one or more peer reviewed special issues of The Journal of Problem Solving (see http://docs.lib.purdue.edu/jps/).