Abstract
In multi-agent systems, updating knowledge bases often leads to logical conflicts. Traditional approaches typically force an agent to either reject new information or entirely overwrite existing beliefs. This paper proposes a novel framework based on "forgetting"—a process where an agent resolves conflicts by strategically removing specific atoms from its logic program. By defining Strong and Weak Forgetting, the authors provide a mathematically rigorous method for maintaining consistency while preserving the essential consequences of the original knowledge base. The framework is shown to be computationally viable and capable of simulating existing update models.
Introduction
Artificial intelligence agents frequently encounter new information that contradicts their internal logic programs. When a conflict arises, the standard binary choice—accepting the new data at the cost of the old, or rejecting the new data to preserve the old—is often too blunt. This paper introduces "forgetting" as a nuanced middle ground.
Consider a scenario where Agent A requires Agent B's assistance, but Agent B refuses to help if Agent A allows a third party, Agent C, to copy their work. If Agent A learns that Agent B dislikes Agent C, a traditional update might force Agent A to adopt Agent B's personal dislike into its own knowledge base. Through the mechanism of forgetting, Agent A can instead choose to "forget" the possibility of letting Agent C copy the work. This resolves the conflict and satisfies Agent B's constraints without requiring Agent A to adopt irrelevant external beliefs.
The Mechanics of Forgetting
The authors define two primary mechanisms for forgetting a set of atoms $P$ from a logic program $\Pi$. Both methods rely on a preliminary step called Program Reduction (or unfolding). In this step, if an atom $a$ depends on an atom $p$ (where $p \in P$), the rules defining $p$ are substituted directly into the body of the rules for $a$. This ensures that the logical consequences of $p$ are maintained even after $p$ itself is removed.
Following reduction, the paper distinguishes between two approaches to handling "negation as failure" (the not operator):
- Strong Forgetting ($SForgetLP$): A skeptical approach. If an atom $p$ is forgotten, any rule relying on the absence of $p$ (i.e.,
not p) is discarded. The rationale is that if $p$ is no longer part of the language, the agent can no longer safely rely on its absence to derive other facts. - Weak Forgetting ($WForgetLP$): A credulous approach. If $p$ is forgotten, the term
not pis simply removed from the rules. This effectively treats the absence of $p$ as a default truth, allowing the agent to continue deriving facts that depended on $p$ being false.
Multi-Agent Conflict Resolution
To apply these concepts to real-world AI interactions, the authors introduce Logic Program Contexts $\Sigma = (\Phi_1, \dots, \Phi_n)$. In this framework, each agent possesses a knowledge base, a set of immutable constraints, and a "forgetting set"—a collection of atoms the agent is willing to relinquish to achieve consensus. This unified framework is powerful enough to simulate other major logic update approaches, positioning forgetting as a foundational primitive for knowledge evolution.
Theoretical Insights and Complexity
The paper establishes a significant bridge between logic programming and classical propositional logic. Theorem 1 demonstrates a symmetry where Strong Forgetting corresponds to the "strongest consequence" in classical logic, while Weak Forgetting corresponds to the "weakest premiss."
From a computational standpoint, the authors address the "Linear-Time Paradox." While the physical size of a program may grow exponentially during the unfolding process, Theorem 2 proves that the stable models of the forgotten program can be computed in linear time relative to the original program. This suggests that while the explicit rule set becomes complex, the underlying meaning remains computationally accessible.
Key complexity results include:
- Entailment: Deciding if a fact remains true after forgetting is coNP-complete, matching the complexity of standard stable model reasoning.
- Irrelevance: Determining if forgetting a set $P$ actually changes the truth value of an atom $a$ is coDP-complete.
Conclusion and Future Work
This research provides a robust formalization of forgetting as a tool for conflict resolution in logic programs. By allowing agents to selectively prune their knowledge bases, the framework facilitates consensus without the need for total information adoption.
However, challenges remain regarding "representation explosion," as the reduction process can significantly increase the number of rules. Future research directions include developing more compact representations for forgotten programs, exploring dynamic preferences where agents decide what to forget based on the context of the conflict, and investigating the impact of circular dependencies and complex recursive structures on the forgetting process.
Summary updated