Structurally Guided Task Decomposition in Spatial Navigation Tasks (Student Abstract)

Ruiqi He, Carlos G. Correa, Tom Griffiths, Mark K. HoAAAI 2024 · OpenReview

Introduction

Human planning is not merely a search for the shortest physical path; it is a search for the path that is most computationally efficient to conceptualize. While traditional models of navigation focus on minimizing physical distance, this research explores how humans decompose complex tasks into subtasks to minimize the combined cost of physical movement and mental "search" effort. By incorporating spatial heuristics, such as Manhattan distance, the authors demonstrate that visual structure significantly influences how individuals plan their routes.

Computational Framework

The researchers propose a three-level task decomposition framework to model human navigation:

  1. Task Decomposition: The primary goal (reaching the maze exit) is divided into subtasks, such as choosing between two distinct halves of a maze.
  2. Subtask-level Planning: This layer selects a subtask by maximizing a reward function that balances expected utility against computational cost.
  3. Action-level Planning: To simulate human spatial reasoning, the model employs the A* search algorithm with a Manhattan distance heuristic.

In this framework, "mental effort" is quantified as the planning cost, defined by the number of states (cells) the A* algorithm visits. A path with numerous branching points or dead ends incurs a higher planning cost than a more direct route, even if the total physical distance is identical.

Experimental Design

To test this model, a behavioral experiment was conducted with 41 participants recruited via Prolific. Participants navigated 12 unique mazes, each designed with two possible paths to the goal. Crucially, both paths had the same optimal step cost, but one was engineered to have a significantly higher planning cost due to increased branching.

Example of a maze with two paths of equal length but different planning costs.

Results

The study revealed that humans treat cognitive effort as a finite resource. Key findings include:

  • Preference for Simplicity: As participants gained experience, they increasingly favored the path with the lower planning cost.
  • The Learning Effect: In the initial trial, only 42.5% of participants chose the computationally simpler path. By the 12th trial, this proportion rose to 67.5%.
  • Statistical Significance: Logistic regression analysis showed a significant positive slope for trial number (coefficient = 0.063, p = 0.021), confirming that participants learned to identify and prefer mentally easier routes.
Proportion of participants choosing the computationally simpler path across 12 trials.

The model successfully predicted navigation strategies for the majority of participants by accounting for the hidden costs associated with complex branching paths.

Discussion and Future Work

While the model provides a strong fit for human behavior, it did not account for all participants; 32.5% still chose the more complex path in the final trial. This suggests individual variability in how planning costs are estimated or how heuristics are applied.

Future research should focus on refining these heuristics to better capture the diversity of human navigation strategies and investigating the dynamic learning process by which individuals estimate mental effort on the fly. Such insights could bridge the gap between cognitive psychology and the development of more human-like artificial intelligence.

Summary updated

BibTeX
@inproceedings{he2024structurally,
  author = {Ruiqi He and Carlos G. Correa and Tom Griffiths and Mark K. Ho},
  title = {{Structurally Guided Task Decomposition in Spatial Navigation Tasks (Student Abstract)}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=z0Z8fgorfh},
}
Figure