Problem Solving as Probabilistic Inference with Subgoaling: Explaining Human Successes and Pitfalls in the Tower of Hanoi
Open accessThe DOI matches its Crossref record; 31 of the 31 references it cites were found in a registry or an index.
Abstract
How do humans and other animals face novel problems for which predefined solutions are not available? Human problem solving links to flexible reasoning and inference rather than to slow trial-and-error learning. It has received considerable attention since the early days of cognitive science, giving rise to well known cognitive architectures such as SOAR and ACT-R, but its computational and brain mechanisms remain incompletely known. Furthermore, it is still unclear whether problem solving is a "specialized" domain or module of cognition, in the sense that it requires computations that are fundamentally different from those supporting perception and action systems. Here we advance a novel view of human problem solving as probabilistic inference with subgoaling. In this perspective, key insights from cognitive architectures are retained such as the importance of using subgoals to split problems into subproblems. However, here the underlying computations use probabilistic inference methods analogous to those that are increasingly popular in the study of perception and action systems. To test our model we focus on the widely used Tower of Hanoi (ToH) task, and show that our proposed method can reproduce characteristic idiosyncrasies of human problem solvers: their sensitivity to the "community structure" of the ToH and their difficulties in executing so-called "counterintuitive" movements. Our analysis reveals that subgoals have two key roles in probabilistic inference and problem solving. First, prior beliefs on (likely) useful subgoals carve the problem space and define an implicit metric for the problem at hand-a metric to which humans are sensitive. Second, subgoals are used as waypoints in the probabilistic problem solving inference and permit to find effective solutions that, when unavailable, lead to problem solving deficits. Our study thus suggests that a probabilistic inference scheme enhanced with subgoals provides a comprehensive framework to study problem solving and its deficits.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The free-energy principle: a unified brain theory?
Friston, K. (2010) · Nature Reviews Neuroscience · doi:10.1038/nrn2787 · Cited by 8,120 · cited 2×
“We use probabilistic inference methods that are increasingly adopted to study multiple cognitive domains, such as perception, action and learning [17, 18], supporting the idea that the computations underlying problem solving might share common principles with them.”
BackgroundMethodBetween MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning
Sutton, R. S., Precup, D., & Singh, S. (1999) · Artificial Intelligence · doi:10.1016/s0004-3702(99)00052-1 · Cited by 3,119
The information bottleneck method
Tishby, N., Pereira, F. C., & Bialek, W. (2000) · arXiv · doi:10.48550/arxiv.physics/0004057 · Cited by 2,626
Memory, navigation and theta rhythm in the hippocampal-entorhinal system
Buzsáki, G., & Moser, E. I. (2013) · Nature Neuroscience · doi:10.1038/nn.3304 · Cited by 1,847 · cited 1×
“First, researchers have focused on how individual brain areas or circuits solve problems in specific domains; for example, the hippocampus is considered to be implied in solving navigation problems [4 – 6] and parieto-frontal regions are considered to be implied in mathematical problem solving [7].”
BackgroundHow to grow a mind: Statistics, structure, and abstraction
Tenenbaum, J. B., Kemp, C., Griffiths, T. L., & Goodman, N. D. (2011) · Science · doi:10.1126/science.1192788 · Cited by 1,815
A formal theory of inductive inference. Part II
Solomonoff, R. J. (1964) · Information and Control · doi:10.1016/s0019-9958(64)90131-7 · Cited by 1,758
Bayesian inference with probabilistic population codes
Ma, W. J., Beck, J. M., Latham, P. E., & Pouget, A. (2006) · Nature Neuroscience · doi:10.1038/nn1790 · Cited by 1,457
Hippocampal place-cell sequences depict future paths to remembered goals
Pfeiffer, B. E., & Foster, D. J. (2013) · Nature · doi:10.1038/nature12112 · Cited by 1,216
A formal theory of inductive inference. Part I
Solomonoff, R. J. (1964) · Information and Control · doi:10.1016/s0019-9958(64)90223-2 · Cited by 1,192
Decision making and the avoidance of cognitive demand
Kool, W., McGuire, J. T., Rosen, Z. B., & Botvinick, M. M. (2010) · Journal of Experimental Psychology: General · doi:10.1037/a0020198 · Cited by 1,141
Neural ensembles in CA3 transiently encode paths forward of the animal at a decision point
Johnson, A., & Redish, A. D. (2007) · The Journal of Neuroscience · doi:10.1523/jneurosci.3761-07.2007 · Cited by 1,003 · cited 1×
“The importance of feedforward mechanisms emerges from psychological experiments [49, 50] as well as neurophysiological studies on rodents [51 – 53], monkeys, [54, 55] and humans [56].”
BackgroundTheory-based Bayesian models of inductive learning and reasoning
Tenenbaum, J. B., Griffiths, T. L., & Kemp, C. (2006) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2006.05.009 · Cited by 880 · cited 1×
“…used across multiple domains (sensorimotor [21, 22], decision-making and planning [23 – 25], human-level reasoning [26 – 28] and learning [29]) and levels of description (higher / computational and lower / neuronal [17, 18, 30 – 33]), supporting the idea that problem solving does not…”
BackgroundVision as Bayesian inference: analysis by synthesis?
Yuille, A., & Kersten, D. (2006) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2006.05.002 · Cited by 849
Memory for goals: an activation‐based model
Altmann, E. M., & Trafton, J. G. (2002) · Cognitive Science · doi:10.1207/s15516709cog2601_2 · Cited by 795 · cited 1×
“…on the well-studied Tower of Hanoi (ToH) task, which has been modeled using several computational frameworks such as the cognitive architecture ACT-R [88] and various symbolic [81, 89] and subsymbolic systems [90], none of which however use the principles of probabilistic inference proposed here.”
MethodSimulation as an engine of physical scene understanding
Battaglia, P. W., Hamrick, J. B., & Tenenbaum, J. B. (2013) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1306572110 · Cited by 681
Active Inference, homeostatic regulation and adaptive behavioural control
Pezzulo, G., Rigoli, F., & Friston, K. (2015) · Progress in Neurobiology · doi:10.1016/j.pneurobio.2015.09.001 · Cited by 650
Self-citationNeural representations of events arise from temporal community structure
Schapiro, A. C., Rogers, T. T., Cordova, N. I., Turk-Browne, N. B., & Botvinick, M. M. (2013) · Nature Neuroscience · doi:10.1038/nn.3331 · Cited by 556 · cited 5×
“The way we calculate algorithmic priors P ( SG ) shares some similarities, but also differences, with alternative ways that have been proposed in the literature that are based on graph theory [74, 75, 84] and information theory [43 – 45, 85, 86].”
BackgroundMethodResultInfluentialHierarchical models of behavior and prefrontal function
Botvinick, M. M. (2008) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2008.02.009 · Cited by 532
Are the frontal lobes implicated in “planning” functions? Interpreting data from the Tower of Hanoi
Goel, V., & Grafman, J. (1995) · Neuropsychologia · doi:10.1016/0028-3932(95)90866-p · Cited by 510
Reinforcement learning or active inference?
Friston, K. J., Daunizeau, J., & Kiebel, S. J. (2009) · PLoS ONE · doi:10.1371/journal.pone.0006421 · Cited by 443
Thoughts, behaviour, and brain dynamics during navigation in the real world
Spiers, H. J., & Maguire, E. A. (2006) · NeuroImage · doi:10.1016/j.neuroimage.2006.01.037 · Cited by 371
Otto (2013) · doi:10.1177/0956797612463080 · Cited by 352
Speed/accuracy trade-off between the habitual and the goal-directed processes
Keramati, M., Dezfouli, A., & Piray, P. (2011) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1002055 · Cited by 346
Information Theory of Decisions and Actions
Tishby, N., & Polani, D. (2011) · Perception-Action Cycle · doi:10.1007/978-1-4419-1452-1_19 · Cited by 267
Activity in the lateral prefrontal cortex reflects multiple steps of future events in action plans
Mushiake, H., Saito, N., Sakamoto, K., Itoyama, Y., & Tanji, J. (2006) · Neuron · doi:10.1016/j.neuron.2006.03.045 · Cited by 249 · cited 1×
“The importance of feedforward mechanisms emerges from psychological experiments [49, 50] as well as neurophysiological studies on rodents [51– 53], monkeys, [54, 55] and humans [56].”
BackgroundInternally generated sequences in learning and executing goal-directed behavior
Pezzulo, G., van der Meer, M. A. A., Lansink, C. S., & Pennartz, C. M. A. (2014) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2014.06.011 · Cited by 217
Self-citationEmbodied choice: how action influences perceptual decision making
Lepora, N. F., & Pezzulo, G. (2015) · PLOS Computational Biology · doi:10.1371/journal.pcbi.1004110 · Cited by 209 · cited 1×
“Specifically, we use a variant of the widely adopted drift-diffusion model [72] that casts choice as a Bayesian sequential analysis over multiple alternatives [63, 64, 73].”
MethodSelf-citationInterplay of approximate planning strategies
Huys, Q. J. M., Lally, N., Faulkner, P., Eshel, N., Seifritz, E., Gershman, S. J., Dayan, P., & Roiser, J. P. (2015) · Proceedings of the National Academy of Sciences · doi:10.1073/pnas.1414219112 · Cited by 207
Pezzulo, G., Rigoli, F., & Chersi, F. (2013) · Frontiers in Psychology · doi:10.3389/fpsyg.2013.00092 · Cited by 163
Self-citationThe why, what, where, when and how of goal-directed choice: neuronal and computational principles
Verschure, P. F. M. J., Pennartz, C. M. A., & Pezzulo, G. (2014) · Philosophical Transactions of the Royal Society B Biological Sciences · doi:10.1098/rstb.2013.0483 · Cited by 131
Prefrontal Goal Codes Emerge as Latent States in Probabilistic Value Learning
Stoianov, I., Genovesio, A., & Pezzulo, G. (2016) · Journal of Cognitive Neuroscience · doi:10.1162/jocn_a_00886 · Cited by 44 · cited 1×
“Probabilistic inference methods are increasingly used to explain a variety of cognitive, perceptual and motor tasks, including goal-directed decisions and planning [17, 23, 30, 34, 37, 38, 87].”
BackgroundSelf-citation
Cited by
Hierarchical active inference: A theory of motivated control
Pezzulo, G., Rigoli, F., & Friston, K. J. (2018) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2018.01.009 · Cited by 334
Self-citationPlanning and navigation as active inference
Kaplan, R., & Friston, K. J. (2018) · Biological Cybernetics · doi:10.1007/s00422-018-0753-2 · Cited by 203
Petzschner, F. H., Weber, L. A. E., Gard, T., & Stephan, K. E. (2017) · Biological Psychiatry · doi:10.1016/j.biopsych.2017.05.012 · Cited by 181
Action perception as hypothesis testing
Donnarumma, F., Costantini, M., Ambrosini, E., Friston, K., & Pezzulo, G. (2017) · Cortex · doi:10.1016/j.cortex.2017.01.016 · Cited by 90
Self-citation
Metadata
- Authors
- Donnarumma, F., Maisto, D., & Pezzulo, G.
- Venue
- PLOS Computational Biology
- Publisher
- Public Library of Science (PLoS)
- Published
- 2016-04-13
- Volume
- 12
- Issue
- 4
- Pages
- e1004864
- ISSN
- 1553-734X (ISSN-L)
- 1553-7358
- OpenAlex
- W2339047734
- Cited by
- 60
- References
- 31
- FWCI
- 7.47
- Type
- journal article
- Language
- en
- Open access
- gold
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.