Interactions between tree search and task simplification in planning
[paper]
Humans can flexibly solve novel, complex problems by planning—that is, by forming an internal model of a task, reasoning about possibilities in that model, and selecting effective actions. However, these cognitive operations are costly and humans have limited cognitive resources, necessitating the use of resource rational planning strategies. In this project, we analyze the interaction of two broad strategies: heuristic tree search and task simplification. We present an algorithmic framework for interleaving tree search with task simplification—iteratively refining a simplified construal of a task, and reusing plans made under simpler construals to seed planning in richer ones—and prove it is guaranteed to find the optimal policy in problems composed of discrete objects where the task is to reach a goal configuration in as few steps as possible.
Construals of a Rush Hour puzzle form a lattice, from the empty construal at the bottom to the full task at the top. The highlighted path shows a sequence of iteratively refined construals.
Results
When applied to tasks such as Rush Hour and Sokoban, our approach significantly decreases the total amount of computation required to find a solution. These results reveal how the interaction of resource rational strategies can lead to efficiencies above and beyond the individual strategies.
Rollout models of human planning with exact action probabilities
[preprint]
One proposed mechanism for human planning is the mental simulation, or “rollout,” of potential action sequences to evaluate future outcomes. While rollout-based models have seen great success in artificial intelligence, cognitive models that describe how people use rollouts remain scarce, in part because they are difficult to fit to behavioral data: existing methods rely on computationally intensive simulations that result in approximate, noisy estimates of latent planning parameters. Together with Wei Ji Ma, we introduce ROSETTE (Rollouts with Stochastic Early Termination and Tractable Estimation), a rollout-based model for finite goal-directed tasks with absorbing goals that provides analytically tractable, simulation-free model fitting. ROSETTE treats planning as a sequence of mental simulations formalized as an absorbing Markov chain: the model deterministically accumulates analytically computed expected rollout evidence and performs a variable number of policy-update cycles.
The model: circular nodes are states, square nodes are stopping states, and diamonds are decision points. Transitions in blue areas are mental simulations; transitions in brown areas are executed actions.
Results
We fit ROSETTE to data from human participants in two multi-step planning tasks (Rush Hour and Tower of London) and found that it well accounted for a rich set of summary statistics of behavior—for example, both humans and the model increasingly took actions that reduced the distance to the goal as they approached it, a trend that alternative models could not capture. By making this class of absorbing-goal rollout models tractable, our framework provides a testable account of how people may simulate and evaluate possible futures.
A computational model of backward reasoning in human problem solving
[preprint]
Human life is filled with problem solving. From something as simple as crossing the road, to complex problems such as chess, any situation where an agent desires change can be framed as a problem. Many problems are too complex to tackle directly, and instead can be broken down into subgoals which are more easily solved. The process of starting at the main goal of the problem and breaking it down into subgoals recursively is called backward reasoning. Under the supervision of Wei Ji Ma, we proposed that AND-OR trees that chain together subgoals and actions to attain them provide a useful representation to study this process.
Results
AND-OR trees provide a representation predictive of human actions
Closer to the goal, the predictive power increases
The trees get smaller the closer to the goal a person is
People make fewer mistakes the closer to the goal they are
A simple process model built on AND-OR trees can capture these trends, while alternative models cannot
Strongly solving the Royal Game of Ur
Royal Game of Ur is one of the oldest board games in the world. Excavated at the Royal Cemetery at Ur, five boards were found dating back to around 2,600–2,400 BC. It is a predecessor of many race games like backgammon. The game has received increased attention after Tom Scott’s interview and the launch of https://royalur.net/.
In this project, I collaborated with the creator of RoyalUr.net, Padraig Lamont, to (strongly) solve the game and analyze strategic and tactical gameplay.
One of the boards excavated at the Royal Cemetery at Ur (British Museum), and the board schematic with each player’s route.
Results
We strongly solved three conjectured rule sets for the game: Finkel, Blitz, and Masters. For every reachable state, we computed the game-theoretic value, the first player’s probability of winning under optimal play, and an optimal move. From the initial position, the first player wins 51.54% of games under the Finkel rules (50.41% for Blitz, 50.48% for Masters), implying a small first-player advantage in each variant. We obtained the solution maps using value iteration and verified them through convergence analysis and large-scale simulations. The resulting maps are deployed on RoyalUr.net for optimal play, game review, and player feedback. We are now comparing the solution to human gameplay data to analyze in which situations people behave optimally.
Performance of the optimal agent against an ε-greedy opponent. Even against an opponent who plays randomly only half the time, the optimal agent wins 96.32% of games.
Past research
Neural and behavioral signatures of online learning in probabilistic models
The statistics of the world are constantly in flux, so the brain must be able to adapt its internal model in real time to make sense of this evolving environment. This problem is further complicated by the fact that sensory information is itself dynamic and ambiguous, so neural circuits have to disambiguate meaningful changes from noise through a dynamic inference process. Together with Camille Rullán and Cristina Savin, we proposed a framework for online learning in probabilistic models that can infer model parameters from the stochastic, continuous-time dynamical systems underlying inference over time. Our sampling-based approach allows for unified learning solutions for different internal models. The learning process is temporally local and does not require an evaluation of gradients, both computational prerequisites for biological learning.
Results
The phenomenological effects of our learning framework can be mapped into neural responses and behavior via a spiking recurrent network encoding process allowing us to directly compare its properties to experimental data. We found evidence in nonhuman primate data on smooth pursuit that supports our theory.
Representational dissimilarity metric spaces for stochastic neural networks
[paper]
How do you find the distance between two neural networks (biological or artificial) when their output is stochastic? Measures of deterministic representational similarity ignore the scale and geometric structure of noise, both of which play important roles in neural computation. In collaboration with researchers at the Flatiron Institute, we extended Alex Williams’s theory of Generalized Shape Metrics to apply to stochastic neural networks.
Results
We applied our theory to both biological and artificial neural network data and found that the stochastic geometries of neurobiological representations of oriented visual gratings and naturalistic scenes respectively resemble untrained and trained deep network representations. We were also able to more accurately predict certain network attributes (e.g. training hyperparameters) from their position in stochastic (versus deterministic) shape space.
Active sensing in landmark-based localisation
[abstract]
Localising objects is a task plagued by uncertainty, such as when looking for an object in a cluttered scene. While eye movements in visual search have been shown to optimally reduce uncertainty about target location called active sensing, they have mostly been studied using scenes devoid of landmarks. Conversely, landmarks are central to the study of navigation, but the role of uncertainty, and its reduction by active sensing, remain unclear. Instead, various heuristic strategies, using landmarks proximal or distal to the goal, have been described. With the help of Yul Kang and under the supervision of Máté Lengyel and Daniel Wolpert, we ran a psychophysics experiment to test whether people use optimal or heuristic strategies when localising objects in the presence of landmarks.
Results
We found diverse strategies, with some participants close to optimal active sensing, while others heavily biased towards using the proximal landmark, with a significant anticorrelation between these two strategies. Each participant’s active sensing strategy was adapted to their idiosyncratic patterns of errors, underscoring the importance of subjective uncertainty. Our study reveals active sensing in localisation, by systematically separating it from a proximity-based heuristic, and suggests a landmark-specific representation of subjective uncertainty, thus placing stringent constraints on candidate neural mechanisms of localisation and, more generally, of navigation.
