Introduction
In artificial intelligence and automated reasoning, maintaining the consistency of a knowledge base ($\Delta$) is a fundamental challenge. When a knowledge base becomes inconsistent—often due to the arrival of new, conflicting information—researchers typically seek a Maximal Satisfiable Subset (MSS). An MSS is a subset of the original clauses that is internally consistent and cannot be expanded without introducing a contradiction.
However, real-world scenarios often involve reasoning under multiple, potentially mutually exclusive, future scenarios or "assumptive contexts" ($\Gamma$). This paper addresses the problem of computing an Assumptive Context MSS (AC-MSS): a subset of $\Delta$ that remains satisfiable when paired with any individual context in $\Gamma$, even if the contexts themselves are mutually contradictory.
The AC-MSS Problem
Traditional approaches to this problem rely on brute-force enumeration. To find an AC-MSS, one would typically compute all MSSes for each individual context and then find a common subset that satisfies the maximality criteria across all contexts. This approach is prone to "combinatorial explosion," as the number of possible subsets grows exponentially with the size of the knowledge base and the number of contexts.
Consider a robot navigating a dynamic environment. It may have a core map ($\Delta$) and receive two conflicting sensor updates ($\Gamma$): one suggesting a path is blocked and another suggesting it is clear. The robot needs to identify the largest portion of its core map that is robust enough to be valid regardless of which sensor update proves correct.
The Transformational Method
To overcome the limitations of brute-force methods, this paper introduces a novel Transformational Method. This approach reformulates the AC-MSS problem into a single optimization task that can be solved by standard SAT-based solvers (such as Partial-Max-SAT solvers).
Core Mechanisms
- Selectors ($\epsilon$): For every clause in the original knowledge base $\Delta$, a unique "selector" variable is introduced. A clause $C$ is transformed into $(\neg \epsilon \lor C)$, meaning the clause is only active if its selector is true.
- Contextual Renaming: To handle multiple contexts simultaneously without them interfering with one another, the method creates a copy of the weakened knowledge base for each context in $\Gamma$. In each copy, all variables are renamed except for the selectors.
- Single-Call Optimization: By linking these renamed copies through the shared selector variables, the problem is reduced to finding a truth assignment that satisfies the maximum number of selectors. This ensures that the chosen subset of $\Delta$ is compatible with every individual context copy.
Experimental Evaluation
The researchers evaluated the Transformational Method against a brute-force baseline using 225 instances from standard AI planning benchmarks, including Blocks World, Logistics (Bomb), and Robot Navigation (Empty-room, UTS). Assumptive contexts were generated using a 3-SAT generator to ensure complex, non-trivial constraints.
Key Results and Discussion
As shown in Table 1, the performance difference between the brute-force approach and the Transformational Method is stark. The brute-force method frequently encountered Memory-Out (MO) errors, successfully completing only 81 out of 900 test runs. In contrast, the Transformational Method for inclusion-maximal subsets (AC-MSS$_{\subseteq}$) achieved a 100% success rate, solving all 900 instances.
Furthermore, the computational efficiency of the new method is remarkable. The average time (T) to compute an AC-MSS$_{\subseteq}$ was approximately 0.05 seconds, making it suitable for real-time applications. Even the more computationally demanding task of finding a cardinality-maximal subset (AC-MSS$_{\#}$)—the absolute largest possible subset—showed significant improvement, succeeding in 415/900 cases where brute force failed entirely.
Conclusion
The Transformational Method represents a significant advancement in robust reasoning. By bypassing the need for explicit subset enumeration and leveraging the efficiency of modern SAT solvers, it allows for the rapid identification of maximal knowledge subsets compatible with multiple conflicting contexts. Future research will focus on approximating cardinality-maximal solutions and applying these techniques to the enumeration of Minimal Unsatisfiable Subsets (MUSes) for system debugging.
Summary updated