Are Many Reactive Agents Better Than a Few Deliberative Ones?

Kevin Knight

Abstract Traditional AI search algorithms face an exponential trade-off between deliberation depth and computational cost. This paper proposes an alternative: using multiple "reactive" agents with minimal lookahead to find high-quality solutions. By leveraging the variance in stochastic search paths, a "crowd" of fast agents can match the performance of a single deep-searching agent at a fraction of the temporal cost. Experiments on the 8-puzzle and 15-puzzle demonstrate that this multi-agent approach can achieve superlinear speedups, offering a scalable path for real-time search in complex domains.

Introduction

In artificial intelligence, a fundamental trade-off exists between search time and solution quality. Traditional algorithms like A strive for optimality but often become prohibitively slow as search spaces expand. Real-Time A (RTA*) was developed to mitigate this by interleaving planning and execution, allowing an agent to look ahead a few steps, move, and then re-plan.

Conventionally, to improve the efficiency of the resulting path, one increases the "lookahead horizon" ($h$). However, because search trees grow exponentially, even modest increases in deliberation depth can lead to orders-of-magnitude increases in computation time. Kevin Knight's 1993 paper challenges this "think harder" paradigm, suggesting that it is often more efficient to "think fast" with many agents simultaneously.

The Cost of Deliberation

The primary bottleneck in making an agent more "deliberative" is the computational explosion of the search space. As the lookahead horizon increases, the number of states the agent must evaluate grows exponentially.

Search time per step grows exponentially as the lookahead horizon increases.

Knight argues that this exponential cost makes deep lookahead a poor investment for real-time systems. Instead, he proposes a Multiple Agent Search strategy. By running $n$ independent reactive agents (with minimal lookahead, $h=1$) in parallel or via dovetailing on a single processor, the computational cost scales only linearly with the number of agents, rather than exponentially with depth.

Exploiting Search Variance

The success of the multi-agent approach relies on the inherent variance of search paths. While a single reactive agent is erratic and may take a long, rambling path to the goal, the distribution of possible path lengths is broad.

Distribution of solution lengths for reactive agents, highlighting the high variance that multiple agents can exploit.

By introducing Stochastic RTA*—which uses probabilistic tie-breaking for equally good moves—Knight ensures that different agents explore different trajectories. In a "crowd" of such agents, the probability that at least one will stumble upon a near-optimal path increases significantly. This "luck of the crowd" allows the system to sample the minimum of the distribution shown above, which drops much faster than the average solution length.

Key Results and Insights

The paper evaluates these strategies using classic benchmarks like the 8-puzzle and Blocks World. The results were striking:

  • Efficiency Gains: In the 8-puzzle, a group of 8 reactive agents matched the solution quality of a single deliberative agent with a lookahead of 10. Crucially, the 8 agents were 27 times faster on a sequential machine and 225 times faster in a parallel environment.
  • Superlinear Speedup: The research demonstrated that $n$ agents can sometimes find a solution more than $n$ times faster than a single agent. This occurs because agents are sampling the distribution of solution times; the first agent to finish effectively "wins" for the whole group.
  • Communication: When agents shared a memory of visited states (a shared hash table), solution quality improved by an additional 10%, suggesting that even minimal coordination further enhances the "wisdom of the crowd."

Conclusion

Knight’s work suggests that for many search problems, the "Cortes strategy"—getting started immediately rather than over-planning—is superior. By shifting the focus from deep individual deliberation to the collective power of many fast, reactive agents, AI systems can navigate complex spaces with greater temporal efficiency. While future work is needed to ensure agent dispersal in continuous domains, the principle of leveraging search variance remains a powerful tool for modern distributed AI.

Summary updated

BibTeX
@inproceedings{knight1993are,
  author = {Kevin Knight},
  title = {{Are Many Reactive Agents Better Than a Few Deliberative Ones?}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1993},
}
Figure