17. – 22. August 2014, Dagstuhl Seminar 14341
Resource-bounded Problem Solving
1 / 2 >
Auskunft zu diesem Dagstuhl Seminar erteilt
(Zum Einloggen bitte Seminarnummer und Zugangscode verwenden)
This Dagstuhl Seminar on 'Resource-bounded Problem Solving' was a successor to Dagstuhl Seminar 11351: 'Computer Science & Problem Solving: New Foundations', held in August 2011, which was the first Dagstuhl event to bring together computer scientists and psychologists to exchange perspectives on problem solving in general. Before summarizing the content of the seminar itself, we describe the theoretical motivations for the topic of `Resource-bounded Problem Solving', and the choice for the interdisciplinary composition of participants, ranging complexity theory, cognitive psychology, artificial intelligence and cognitive neuroscience.
Background and Motivation
Problem solving, whether by humans or machines, is bounded by the resources at hand. For machines, these resources fundamentally include hardware and processing speed. For humans, important resources also include mental representations, memory capacities, inferential capacities, and time to name a few. 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. After all, many cognitive models may be able to match human performance on really easy problems, but only a few can for really hard problems. Hence, if one finds even one cognitive model that can solve a hard problem as well as humans one can be much more confident that it 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. Computational complexity theory studies the intrinsic resource demands of various computational problems. It allows us to assess when resource demands are low, reasonable, high, or impractically high. Though the importance of computational complexity has been recognized in computer science for decades, it has been underutilized to date by cognitive scientists. This is not for want of opportunities, as cases are known where cognitive scientists have studied principles of resource-bounded problem solving in apparent ignorance of relevant computational complexity results. The following example illustrates such a situation.
- Solving constrained Traveling Salesman problems: MacGregor and Ormerod (1996,Attention, Perception & Psychophysics) hypothesized that the difficulty of solving Euclidean versions of the Traveling Salesperson problem (E-TSP) may be more a function of the number of inner points (i.e., the points not lying on the convex hull of the point set) than of the total number of points. This hypothesis was tested and confirmed for human subjects solving pen-and-paper instances of E-TSP. Independently, it was shown that E-TSP is fixed-parameter tractable when the number of inner points is the parameter (Deineko et al.COCOON 2004). In other words, it is possible to solve E-TSP in time f(k)n^c, where fs is a non-polynomial function of the number k of inner points, n is the total number of points, and c is a constant. This result is relevant for explaining the findings of MacGregor and Ormerod (1996) as it gives a computational formalization of their hypothesis.
There may be many other such opportunities waiting to be noticed. There is also evidence that when such opportunities are exploited and cognitive scientists and complexity theorists establish collaborations, these collaborations can yield novel perspectives and approaches. Below are two examples of such ongoing collaborations and their products.
- Analyzing resource demands of cognitive models: Using computational complexity concepts and techniques, psychologists can systematically study how human problem solving proceeds under various resource demands. Also, complexity theory can predict how resource demands scale as a function of a problem's parameters. Psychologists can then in turn use these predictions to test the models being studied. This approach has been successfully implemented by Iris van Rooij, Todd Wareham, and others in a wide variety of domains, including decision-making (2005, Journal of Mathematical Psychology) and analogical problem solving (2011, Journal of Problem Solving). This program has also led to the development of a theory of structure approximability which has produced new results within both computer science (2007, Proceedings of Dagstuhl seminar 07281) and psychology (2012, Journal of Mathematical Psychology).
- Pyramid data structures and efficient search: Humans and animals are able to delineate, detect and recognize objects in complex scenes at a blink of an eye. Tsotsos (1990, Behavioral and Brain Sciences) performed a complexity analysis and showed that hierarchical representation of visual information and hierarchical processing of this information is one of the best, if not the best, way for brains to solve visual problems. Pyramid data structures provide an effective model for efficient hierarchical search of the problem space. This perspective has led to fruitful collaborations between Yll Haxhimusa, Zygmunt Pizlo, Walter Kropatsch and others, yielding new algorithmic techniques in computer vision (2005, Pattern Recognition Letters; 2009, Vision & Computing),as well as inspiring new cognitive models of visual problem solving in psychology (2006 and 2011, Journal of Problem Solving).
With this seminar we aimed to actively stimulate the exchange of ideas and results between computational complexity theorists, psychologists, cognitive neuroscientists, and AI-researchers studying problem solving. In particular, we wanted to ensure that this exchange would be of use to each (and not just one) of these communities. We believe that such n-way productivity is crucial to fruitful long-term interdisciplinary collaboration, in that it encourages the continued interest of members of all communities in collaborating.
Organization of seminar
On Day 1 of the seminar, Iris van Rooij opened the seminar by explaining its history, motivation and aims. This was following by a round of introductions, in which each participant introduced themselves, who they are, what their home disciplines were, what their relevant research interests were, and what they hoped to both bring to the seminar and get out off it.
Given the interdisciplinary nature of the questions of interest and the wide range of expertise of the seminar participants, it was crucial that a common understanding of the different goals and assumptions of the disciplines involved at the meeting be established early in the meeting. To this end, the first full day of the seminar was devoted to primers on basic terminology, assumptions, and goals of four major sub disciplines represented at the seminar (namely, computational complexity theory, artificial intelligence, psychology, and cognitive neuroscience).
The four introductory keynote speakers, Zygmunt Pizlo (Cognitive Psychology), Todd Wareham (Computational Complexity Theory), Rineke Verbrugge (Artificial Intelligence), and David Noelle (Cognitive Neuroscience), all addressed each of the following questions for their own respective fields.
- What are the goals of that discipline?
- What are the techniques used in that discipline?
- What do the terms "problem solving" and "resource bounds" mean in that discipline?
- What does that discipline have to offer to other disciplines in the context of this seminar?
- What does that discipline want from the other disciplines in the context of this seminar?
- What are some tentative research questions and collaboration opportunities?
Following these introductory key notes there was a panel discussion. Day 1 closed with a Town Hall meeting, in which the set-up and organization for the next days was discussed with all participants and a preliminary schedule was established (later on, as needed, this schedule was updated). At the Town Hall meeting the concept of Birds-of-a-Feather (B.O.F.) sessions was also explained (see Section 5), which turned out to be a very successful format for self-organized working groups.
Days 2, 3 and 4 involved a mix of talks, posters, B.O.F. sessions, and Town Hall sessions. Pairs or triplets of talks were followed by panel discussions to stimulate cross talk connections. Poster sessions allowed for more in-depth discussion in an informal setting, and B.O.F. sessions allowed people to gather and discuss more specific topics of common interest. At Town Hall sessions, a plenary report on the insights gained from each B.O.F. session was given, so that all participants were kept up to date of the outcome of such events. All in all, this set-up worked very well, stimulating active exchange and discussion between participants that crossed disciplinary boundaries.
On the morning of Day 5 we closed with reflections on the overall organization and content of the seminar. It was a shared perspective among participants that the seminar had been exceptionally successful in bringing together the different fields involved in the seminar, initiating many first-time theoretical exchanges and conceptualizations of possible common research questions. Many participants indicated that following this seminar, they would be interested in more focused seminars specializing in subtopics within the domain of problem solving or specializing in specific modeling techniques.
Creative Commons BY 3.0 Unported license
Yll Haxhimusa, Iris van Rooij, Sashank Varma, and Todd Wareham
Related Dagstuhl Seminar
- 11351: "Computer Science and Problem Solving: New Foundations" (2011)
- Artificial Intelligence / Robotics
- Data Structures / Algorithms / Complexity
- Society / Human-computer Interaction
- Complexity theory
- Problem solving
- Cognitive psychology
- Computational trade-offs