Agent-Centered Search: Situated Search with Small Look-Ahead

Sven KoenigAAAI 1996 · OpenReview

Abstract

Traditional search algorithms often assume a static, fully known environment where planning occurs entirely in memory before any action is taken. However, for physical agents in dynamic or uncertain worlds, this "search-in-memory" approach is often impractical. This paper explores agent-centered search, a paradigm where search is restricted to a small look-ahead around the agent's current state and interleaved with action execution. By treating search as a situated process, we can better account for movement costs, irreversibility, and environmental uncertainty. This research establishes a theoretical and experimental framework to analyze the performance of these methods and extends their application to probabilistic domains with complex reward structures.

In traditional artificial intelligence, search is typically viewed as a "mental" exercise. Algorithms like A* operate on a model of the world, expanding nodes and jumping between distant states in a state-space graph at zero cost. This "search-in-memory" assumes that the agent has a complete, deterministic map of the environment and can execute a pre-planned sequence of actions (an open-loop plan) without surprises.

In contrast, situated search is the process of achieving a goal within the actual world. For a physical agent—whether a robot in a warehouse or a software agent in a changing network—the assumptions of search-in-memory rarely hold. Agent-centered search methods are a subset of situated search that restrict their internal simulations to a small area centered on the agent's current location. By performing only a "small look-ahead" before committing to an action, these agents can adapt to new information and environmental changes in real-time.

The Realities of Physical Agency

The shift from memory-based search to agent-centered search is driven by three fundamental realities of situated environments:

  1. The Cost of Movement: In a mental model, evaluating a state 100 steps away is as cheap as evaluating the next state. In the real world, an agent must physically traverse the distance to explore or reach that state. The further a state is from the current position, the more expensive it is to access.
  2. Asymmetry and Irreversibility: Traditional search assumes that "undoing" an edge in a graph is trivial. In physical space, backtracking can be significantly more expensive than moving forward, or even impossible. An agent might not yet know how to reverse an action, making every move a high-stakes decision.
  3. Uncertainty and Non-determinism: Real-world domains are often partially known or non-stationary. Planning for every possible contingency in an open-loop fashion is computationally explosive. Agent-centered search avoids this by only planning for the situations that actually arise from the execution of actions.

The research focuses on the systematic analysis of methods that interleave search and action. These include real-time heuristic search, online reinforcement learning, and various exploration strategies. Unlike previous studies that were largely empirical, this work seeks to identify the underlying factors that influence performance.

Key Methodological Components:

  • Interleaved Execution: The agent plans a few steps, moves, observes the new state, and repeats. This allows the agent to gather information and resolve uncertainty incrementally.
  • Local Heuristics: Because the agent cannot see the entire state space, it relies on local information and heuristic estimates to guide its immediate actions.
  • Learning on the Fly: As the agent moves, it updates its internal model of the world, effectively learning the "map" and the costs of actions through experience.

Beyond Traditional Benchmarks

A significant portion of this research involves critiquing and improving how we evaluate search algorithms. Standard AI benchmarks—such as the sliding tile puzzle or simple grid worlds—often fail to capture the complexities of situated search. These "toy" problems frequently lack the asymmetric costs or non-deterministic elements found in real-world applications.

The research advocates for more adequate testbeds that distinguish between "easy" and "hard" search problems. By analyzing how different state-space topologies affect agent-centered search, we can better predict which algorithms will succeed in complex, situated contexts.

Advanced Applications: Probabilistic Domains and Risk

The second phase of this research extends agent-centered search to more complex scenarios, specifically those involving:

  • Probabilistic Domains: Handling environments where actions have stochastic outcomes.
  • Non-linear Reward Structures: Real-world goals often involve deadlines or specific risk tolerances. For example, an agent might prioritize a "safe" path with a guaranteed arrival time over a "fast" path that has a high probability of failure. Agent-centered search must be adapted to handle these non-linear utilities, where the value of an outcome is not just a simple sum of costs.

Conclusion

Agent-centered search represents a move toward more realistic AI agents that can function in the "here and now." By acknowledging the constraints of being situated in a physical or dynamic environment, this research provides the tools to design agents that are not just efficient in theory, but robust in practice. The transition from search-in-memory to situated search with small look-ahead is essential for developing autonomous systems capable of navigating the uncertainty of the real world.

Summary updated

Abstract

Situated search is the process of achieving a goal in the world. Traditional single-agent search algorithms (such as the A* algorithm) usually assume completely known, stationary domains with deterministic actions. These assumptions favor search approaches that first determine open-loop plans (sequences of actions) that can then be executed blindly in the world. Consequently, single-agent search in AI is often performed in a mental model of the world (state space): states are represented as memory images and search is a process inside the computer (search-in-memory). Situated search can interleave or overlap searchin-memory with action execution. This approach has advantages over traditional approaches in nondeterministic, non-stationary, or only partially known domains. It allows one, for example, to gather information by executing actions. This information can be used to resolve uncertainty caused by missing knowledge of the domain, inaccurate world models, or actions with non-deterministic effects. For instance, one does not need to plan for every contingency in nondeterministic domains; planning is necessary only for those situations that actually result from the execution of actions. My research focuses on the design and analysis of agent-centered search methods. Agent-centered search methods are situated search methods that restrict the search-in-memory to a small part of the state space that is centered around the current state of the agent before committing to the execution of the next action. Since agent-centered search methods perform a small amount of search-in-memory around the current state of the agent, they can be characterized as “situated search with small look-ahead.” Examples of agentcentered search methods include real-time heuristic search methods (they search forward from the current state of the agent), many on-line reinforcement learning algorithms, and exploration approaches. A major difference .between search-in-memory and agent-centered search is that search-in-memory methods can “jump around in the state space.” If, after they have expanded a state, a state in a different part of the state space looks promising, they can expand this state next. In contrast, in situated search, if an agent wanted to explore a state, it would have to execute actions that get it there. The further the state is from the current state of the agent, the more expensive it is to get to that state. Furthermore, backtracking to a previous state might not be easy: it can be very expensive in state spaces with asymmetric costs and the agent might not even have learned how to “undo” an action execution. Thus, one can expect situated (agentcentered) search methods to have different properties than search-in-memory methods. To date, agent-centered search methods have mostly been studied in the context of specific applications. The few existing results are mostly of empirical nature and no systematic or comparative studies have yet been conducted. It is therefore unclear when (and why) agent-centered search algorithms perform well. My research explores, both theoretically and experimentally, how agent-centered search methods behave. This includes an analysis of the factors that influence their performance. Such an analysis is helpful, for example, for predicting their performance in nondeterministic domains, for distinguishing easy from hard search problems, for representing situated search problems in a way that allows them to be solved efficiently, and for developing more adequate testbeds for agent-centered search methods than sliding tile puzzles, blocks worlds, and grid worlds. The second step then is to use these results to extend the functionality of agent-centered search algorithms to better fit typically encountered situated search situations. This includes probabilistic domains with non-linear reward structures, which can be caused, for instance, by the presence of dead-lines or risk attitudes. For more details and references to the literature, see (Koenig SC Simmons 1996).
BibTeX
@inproceedings{koenig1996agent,
  author = {Sven Koenig},
  title = {{Agent-Centered Search: Situated Search with Small Look-Ahead}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
  url = {https://openreview.net/forum?id=SJZXUl-dbH},
}
Figure