Multi-Cycle Query Caching in Agent Programming

Natasha Alechina, Tristan M. Behrens, Mehdi Dastani, Koen V. Hindriks, Jomi Fred Hübner, Brian Logan, Hai H. Nguyen, Marc van ZeeAAAI 2013 · OpenReview

Introduction

Logic-based Belief-Desire-Intention (BDI) agents are central to autonomous systems, enabling rational behavior through a continuous 'sense-plan-act' cycle. However, these agents often face a significant computational bottleneck: the 'inference tax.' Re-evaluating complex logical queries against a knowledge base every cycle consumes substantial resources. This paper introduces a multi-cycle caching approach that persists query results across deliberation cycles, utilizing intelligent invalidation to achieve dramatic speedups in agent reasoning.

The Challenge of Dynamic Beliefs

In complex environments, BDI agents frequently repeat logical queries—such as pathfinding or goal verification—hundreds of times per second. While standard software engineering employs memoization to optimize such repetitions, BDI agents present a unique difficulty: their beliefs change every cycle. A query result valid in Cycle 1 might be false in Cycle 2 if the agent moves or the environment state shifts.

Historically, most platforms have opted for safety by clearing the cache at the end of every cycle. This 'single-cycle' approach, while correct, discards valuable computational work that remains valid across state transitions.

Methodology: Intelligent Multi-Cycle Caching

The proposed multi-cycle caching system moves beyond simple cycle-based clearing. The core innovation lies in a sophisticated Update Phase composed of two main mechanisms:

  1. Dependency Tracking: Instead of merely storing query results, the system records the 'ground facts' (dependencies) used to derive each answer.
  2. Intelligent Invalidation: When an agent's beliefs are updated, an invalidate operation checks if any changed facts were dependencies for cached queries. Only the affected entries are purged, allowing the majority of the cache to persist into the next cycle.

This methodology was implemented and tested across three major agent programming platforms: Jason, 2APL, and GOAL, using techniques ranging from dependency graphs to meta-interpreters.

Experimental Evaluation

The researchers benchmarked the system across five diverse AI environments:

  • Blocks World: Gripper-based block manipulation.
  • Grid World: Bomb disposal in a discrete grid.
  • Wumpus World: A logic-heavy navigation puzzle with hazards.
  • Elevator Sim: Dynamic multi-elevator control in a high-rise.
  • MAPC: Real-time scenarios from the Multi-Agent Programming Contest.

Key Results and Discussion

Empirical data demonstrates that multi-cycle caching provides substantial performance gains, particularly in platforms that rely heavily on external logic engines like GOAL and 2APL.

Performance comparison in GOAL platform showing significant query time reduction in Elevator tasks.

As shown in the GOAL platform results, the Elevator 10 task saw a normalized average query time ($c_{qry}$) drop from 6.67 (no cache) to 1.00 with multi-cycle caching. The hit rate ($h$) in this scenario reached a remarkable 90%, indicating that the vast majority of logical reasoning was successfully reused across cycles.

Performance comparison in 2APL platform highlighting high hit rates in Wumpus World.

In the 2APL platform, the benefits were similarly pronounced in the Wumpus World benchmarks. For the 'Wumpus Large' scenario, the multi-cycle hit rate reached 84%, significantly outperforming single-cycle caching (57%). This confirms that a high percentage of logical inferences remain valid even as the agent navigates a partially observable environment.

Scaling and Overhead

The 'inference tax' is most apparent as problem complexity grows. In Blocks World, as the number of blocks increased, the relative benefit of caching scaled positively because the underlying logical queries became exponentially more expensive to compute from scratch.

However, multi-cycle caching is not free. The system must pay a 'maintenance tax' for dependency tracking. In some implementations, such as the GOAL meta-interpreter, individual queries were 1.5x to 2x slower due to tracking overhead. Nevertheless, the high hit rates consistently outweighed these costs, leading to net performance improvements.

Conclusion

Multi-cycle query caching represents a significant step forward in optimizing BDI agent architectures. By intelligently tracking dependencies and selectively invalidating cache entries, agents can maintain high-speed reasoning even in dynamic environments. Future work will explore deeper integration into the deliberation cycle, potentially caching higher-level plan-selection decisions and accommodating agents with dynamic, self-modifying rule sets.

Summary updated

Abstract

In many logic-based BDI agent programming languages, plan selection involves inferencing over some underlying knowledge representation. While context-sensitive plan selection facilitates the development of flexible, declarative programs, the overhead of evaluating repeated queries to the agent's beliefs and goals can result in poor run time performance. In this paper we present an approach to multi-cycle query caching for logic-based BDI agent programming languages. We extend the abstract performance model presented in (Alechina et al. 2012) to quantify the costs and benefits of caching query results over multiple deliberation cycles. We also present results of experiments with prototype implementations of both single- and multi-cycle caching in three logic-based BDI agent platforms, which demonstrate that significant performance improvements are achievable in practice.
BibTeX
@inproceedings{alechina2013multi,
  author = {Natasha Alechina and Tristan M. Behrens and Mehdi Dastani and Koen V. Hindriks and Jomi Fred Hübner and Brian Logan and Hai H. Nguyen and Marc van Zee},
  title = {{Multi-Cycle Query Caching in Agent Programming}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2013},
  url = {https://openreview.net/forum?id=HyVy8y-uZr},
}
Figure