Abstract
This paper introduces a versatile, model-theoretic framework for combining heterogeneous knowledge bases into a single "Modular System" that respects complex preferences. By utilizing partial structures and three-valued logic, the framework ensures robustness under standard algebraic operations—such as composition and feedback—and unifies existing formalisms like CP-nets and preference-based planning.
Introduction
In modern Artificial Intelligence, solving complex problems often requires the integration of multiple "specialist" modules. For instance, a logistics system might employ Integer Linear Programming (ILP) to solve a Knapsack problem for truck packing while using Answer Set Programming (ASP) to solve a Traveling Salesman Problem (TSP) for routing.
The primary challenge lies in expressing global preferences across these heterogeneous modules. Defining a "best" solution is difficult when modules use different logic languages, have internal constraints, and interact through complex feedback loops where the output of one module affects the input of another. This paper addresses these challenges by proposing a language-agnostic framework for preference-based modular systems.
The P-MS Framework
The authors build upon the Model Expansion (MX) framework, where a problem is viewed as expanding an input structure with new relations and functions that satisfy a logical specification. The proposed Preference-based Modular System (P-MS) introduces several key innovations:
- Algebraic Operators: Modules are combined using operators like composition (piping), union (choice), and feedback (loops).
- Partial Structures: Preferences are defined over partial structures using three-valued logic (true, false, unknown). This allows the system to express preferences even when some information is missing or irrelevant to a specific module, facilitating a "ceteris paribus" (all else being equal) interpretation.
- Meta-Preferences: A formal mechanism to rank preferences themselves, allowing the system to resolve conflicts between different criteria.
Illustrative Example: Logistics Service Provider
To demonstrate the framework, the authors use a conceptual "Logistics Service Provider" (LSP) example. This system combines packing and routing tasks into a single modular architecture.
As shown in the figure, the system $M_{LSP}$ integrates a Knapsack module ($M_K$) and a TSP module ($M_{TSP}$). The feedback loop ($B$ to $B'$) illustrates how the framework handles cyclic dependencies, ensuring that preferences remain consistent even when sub-components interact dynamically.
Key Theoretical Results
The paper provides a rigorous mathematical foundation for P-MS through several core theorems:
- Robustness (Theorem 1): The authors prove that the operations of composition, union, feedback, and projection preserve the properties of a preference-based modular system. This ensures that complex systems can be built incrementally without breaking the underlying preference logic.
- Unification (Theorems 2 & 3): The framework acts as a "universal translator," formally demonstrating that existing frameworks like CP-nets (conditional preferences) and Preference-based Planning (basic desires) are special cases of the P-MS formalism.
Discussion and Future Work
While the P-MS framework is mathematically robust and language-agnostic, it currently focuses on semantics rather than algorithmic implementation. Solving these systems is likely to be computationally expensive (NP-complete or higher).
Future research will focus on developing efficient solvers and exploring the "sweet spot" between preference expressivity and computational efficiency. Additionally, the authors aim to apply this framework to large-scale, human-centric systems, such as complex business processes where diverse stakeholders provide preferences in varying formats.
Summary updated