Abschlussarbeit

The domain of belief change examines how a rational agent can adjust its beliefs when new and potentially contradictory information arises. To address inconsistencies in belief systems, there are two main approaches: computing minimal inconsistent subsets, called kernels, and computing maximal consistent subsets, called residuals. The search for these kernels and residuals plays an important role in incorporating new information while maintaining basic beliefs. Several belief change algorithms for computing kernels and residues have been proposed in the literature. These computed kernels and residuals can be used to span a search tree that contains all potential solutions for belief base contraction and make them consistent. A major challenge remains to find the optimal solution out of all possible solutions.

In this paper, an innovative approach is presented that builds on established rank- based methods but complements them with a unique strategy for weight computation. Rather than relying solely on ranks, this approach assigns specific values to formulas within a belief base, including values based on inconsistency measures. These values not only enable the ranking of possible solutions to determine the optimal solution, but also facilitate the implementation of a branch-and-bound strategy used to explore the search tree more efficiently. The branch-and-bound implementation in this thesis includes three different pruning approaches that enable the computation of an optimal solution that yields the maximum value, the minimum value, or a combination of both, using different measures for the maximum and minimum values.

Consequently, this work provides an implementation that finds optimal solutions for both maximality and minimality problems. A maximality problem seeks to maximize a given value within the belief base, while a minimality problem aims to minimize a given value. Our approach shows significant advances over exist- ing algorithms, offering an average time saving of 50% in computing kernels and finding optimal solutions in less than half the time required by conventional methods. The implemented branch-and-bound algorithm outperforms known strategies by efficiently pruning the search space and utilizing innovative techniques such as divide-and-conquer and sliding window methods. This work establishes a robust framework for belief base contraction and shows outstanding performance in both maximization and minimization problem solving scenarios.