Dagstuhl-Seminar 14341
Resource-bounded Problem Solving
( 17. Aug – 22. Aug, 2014 )
(zum Vergrößern in der Bildmitte klicken)
Permalink
Bitte benutzen Sie folgende Kurz-Url zum Verlinken dieser Seite:
https://www.dagstuhl.de/14341
Organisatoren
- Yll Haxhimusa (TU Wien, AT)
- Iris van Rooij (Radboud University Nijmegen, NL)
- Sashank Varma (University of Minnesota - Minneapolis, US)
- Todd Wareham (Memorial University of Newfoundland, CA)
Kontakt
- Andreas Dolzmann (für wissenschaftliche Fragen)
- Annette Beyer (für administrative Fragen)
Dagstuhl Seminar Wiki
- Dagstuhl Seminar Wiki (Use personal credentials as created in DOOR to log in)
Gemeinsame Dokumente
- Dagstuhl Materials Page (Use personal credentials as created in DOOR to log in)
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 confident 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/).
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
- Burcu Arslan (University of Groningen, NL)
- Tarek Richard Besold (Universität Osnabrück, DE) [dblp]
- Mark Blokpoel (Radboud University Nijmegen, NL)
- Sarah Carruthers (University of Victoria, CA) [dblp]
- Christopher Cherniak (University of Maryland - College Park, US) [dblp]
- Nicole Cruz de Echeverria Loebell (University of London, GB)
- Harmen de Weerd (University of Groningen, NL) [dblp]
- Michael R. Fellows (Charles Darwin University - Darwin, AU) [dblp]
- Nadine Fleischhut (MPI für Bildungsforschung, DE)
- Liane Gabora (University of British Columbia - Vancouver, CA) [dblp]
- Emmanuel Genot (Lund University, SE)
- Nina Gierasimczuk (University of Amsterdam, NL) [dblp]
- Vinod Goel (York University - Toronto, CA) [dblp]
- Yll Haxhimusa (TU Wien, AT) [dblp]
- Justine Jacot (Lund University, SE) [dblp]
- Frank Jäkel (Universität Osnabrück, DE) [dblp]
- Brendan Juba (Harvard University - Cambridge, US) [dblp]
- Alexandra Kirsch (Universität Tübingen, DE) [dblp]
- Etienne Koechlin (ENP - Paris, FR) [dblp]
- Antonina Kolokolova (Memorial University of Newfoundland, CA) [dblp]
- Johan Kwisthout (Radboud University Nijmegen, NL) [dblp]
- Falk Lieder (University of California - Berkeley, US) [dblp]
- Wolfgang Maass (TU Graz, AT) [dblp]
- Matthias Mnich (Universität Bonn, DE) [dblp]
- Martin Möhrmann (Universität Osnabrück, DE) [dblp]
- David Noelle (University of California - Merced, US) [dblp]
- Stellan Ohlsson (University of Illinois - Chicago, US) [dblp]
- Maria Otworowska (Radboud University Nijmegen, NL)
- Zygmunt Pizlo (Purdue University - West Lafayette, US) [dblp]
- Frances A. Rosamond (Charles Darwin University - Darwin, AU) [dblp]
- Constantin Rothkopf (TU Darmstadt, DE) [dblp]
- Zahra Sajedinia (Memorial University of Newfoundland, CA) [dblp]
- Ulrike Stege (University of Victoria, CA) [dblp]
- Marieke Sweers (Radboud University Nijmegen, NL)
- Niels A. Taatgen (University of Groningen, NL) [dblp]
- John K. Tsotsos (York University - Toronto, CA) [dblp]
- Iris van Rooij (Radboud University Nijmegen, NL) [dblp]
- Sashank Varma (University of Minnesota - Minneapolis, US) [dblp]
- Rineke Verbrugge (University of Groningen, NL) [dblp]
- Todd Wareham (Memorial University of Newfoundland, CA) [dblp]
- Scott Watson (Memorial University of Newfoundland, CA) [dblp]
Verwandte Seminare
- Dagstuhl-Seminar 11351: Computer Science and Problem Solving: New Foundations (2011-08-28 - 2011-09-02) (Details)
Klassifikation
- artificial intelligence / robotics
- data structures / algorithms / complexity
- society / human-computer interaction
Schlagworte
- complexity theory
- problem solving
- cognitive psychology
- computational trade-offs
