First-Order Logical Filtering

Abstract

Logical filtering is the process of updating a belief state (set of possible world states) after a sequence of executed actions and perceived observations. In general, it is intractable in dynamic domains that include many objects and relationships. Still, potential applications for such domains (e.g., semantic web, autonomous agents, and partial-knowledge games) encourage research beyond immediate intractability results. In this paper we present polynomial-time algorithms for filtering belief states that are encoded as First-Order Logic (FOL) formulae. We sidestep previous discouraging results, and show that our algorithms are exact in many cases of interest. These algorithms accept belief states in full FOL, which allows natural representation with explicit references to unidentified objects, and partially known relationships. Our algorithms keep the encoding compact for important classes of actions, such as STRIPS actions. These results apply to most expressive modeling languages, such as partial databases and belief revision in FOL.