Computation and comparison of nonmonotonic skeptical inference relations induced by sets of ranking models for the realization of intelligent agents

摘要

Skeptical inference of an intelligent agent in the context of a knowledge base R containing conditionals of the form If A then usually B can be defined with respect to a set of models of R. For the semantics of ranking functions that assign a degree of surprise to each possible world, we develop a method for comparing the inference relations induced by different sets of ranking models. Using this method, we address the problem of ensuring the correctness of approximating skeptical c-inference for R by constraint satisfaction problems (CSPs) over finite domains. Skeptical c-inference is defined by taking the set of all c-representations into account, where c-representations are ranking functions induced by impact vectors encoding the conditional impact on each possible world. By setting a bound for the maximal impact value, c-inference can be approximated by a resource-bounded inference operation. We investigate the concepts of regular and sufficient upper bounds for conditional impacts and how they can be employed for implementing c-inference as a finite domain constraint solving problem. While in general, determining a sufficient upper bound for these CSPs is an open problem, for a sequence of simple knowledge bases investigated only experimentally before, we prove that using the number of conditionals in R as an upper bound correctly captures skeptical c-inference. The ideas presented in this paper are implemented in a software platform that realizes the core reasoning component of an intelligent agent.