Incremental Inference: Getting Multiple Agents to Agree on What to Do Next

Gary C. BorchardtAAAI 1987

Abstract

In mixed-initiative systems, humans and AI agents must maintain a shared understanding of goals and plans. Traditional Truth Maintenance Systems (TMS) often prove too brittle for these dynamic environments, retracting plans the moment their logical justifications are altered. This paper introduces Incremental Inference, a symbolic reasoning algorithm that utilizes a recency-based heuristic to provide stable, default assumptions. By prioritizing newer information during logical stabilization, the system allows for fluid hand-offs and persistent goal-tracking in complex domains like geological data interpretation.

Introduction

The coordination of multiple expert systems and human operators requires a reasoning engine capable of handling shifting priorities without constant state resets. In the late 1980s, the challenge was to build collaborative systems for tasks such as space robot control or geological analysis. The primary friction point identified was the rigidity of logic-based Truth Maintenance Systems.

The Problem: Brittle Justifications

In a standard TMS, every proposition must be supported by a logical justification. If the underlying reason for a plan is removed, the system immediately retracts the plan. In a collaborative setting, this behavior is often counter-intuitive. For example, if a robot pauses a specific sub-task, a human operator likely expects the overarching goal to remain active as a "default" until a specific reason to switch is established. The goal of Incremental Inference is to move from "brittle" logic to "fluid" consensus tracking.

The Incremental Inference Algorithm

The core of the algorithm is a restructuring of the TMS model to prioritize temporal relevance over logical derivation.

Data Representation

Propositions are represented in Conjunctive Normal Form (CNF). Unlike traditional systems, each proposition is associated with a tuple: (truth value, timestamp). The truth value can be true, false, or retracted.

Figure 1: Example of propositions represented as (value, timestamp) pairs.

Stabilization and Recency

When an agent updates a proposition, the global clock increments. The system then "stabilizes" the logic by evaluating clauses. If a conflict arises (an unsatisfied clause), the system modifies the propositions with the oldest timestamps first. This "recency heuristic" assumes that newer information is a better proxy for the current intended state of the system.

Refreshing and Retraction

Agents can "refresh" a proposition, updating its timestamp to the current time without changing its value. This effectively "protects" a state from being overwritten by the inference engine's stabilization process. If a conflict cannot be resolved through recency, the system marks propositions as "retracted," signaling a contradiction that requires higher-level intervention or backtracking.

Application: The SPECTRUM System

The algorithm was evaluated using SPECTRUM, a system developed at JPL for interpreting imaging spectrometer data. The demonstration focused on the Isodata clustering tool, which involves several states: initialize, cluster, extract, and merge.

Figure 5: The state of the SPECTRUM control loop at time 16, showing active plans and agent interests.

In this domain, the system manages "handshakes" between the human user and the AI. For instance, if the AI suggests a "cluster" operation but the user "refreshes" their interest in "merge," the system respects the user's recent input and maintains the merge plan as the stable state. This prevents the system from dropping a goal simply because a temporary logical support was removed.

Key Insights

  1. Inference as Heuristic: In human-machine collaboration, temporal recency often outperforms strict logical proof as a mechanism for maintaining context.
  2. Stability over Completeness: The algorithm trades full logical case analysis for the ability to track a changing environment fluidly.
  3. Meta-Reasoning: By treating an agent's "interest" as a proposition, the system can reason about the collaboration process itself, allowing one agent to block another from relinquishing interest in a critical task.

Conclusion

Incremental Inference provides a robust framework for multi-agent coordination. By ensuring that the stabilization process always converges and prioritizing recent inputs, it creates a "fluid" reasoning environment suitable for real-time, mixed-initiative tasks. Future work remains to address logical incompleteness and scaling to larger proposition sets.

Summary updated

BibTeX
@inproceedings{borchardt1987incremental,
  author = {Gary C. Borchardt},
  title = {{Incremental Inference: Getting Multiple Agents to Agree on What to Do Next}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1987},
}
Figure