Circumscribing Circumscription: A Guide to Relevance and Incompleteness

Intelligent agents in the physical world must work from incomplete information due to partial knowledge and limited resources. An agent copes with these limitations by applying rules of conjecture to make reasonable assumptions about what is known. Circumscription, proposed by McCarthy, is the formalization of a particularly important rule of conjecture likened to Occam's razor. That is, the set of all objects satisfying a certain property is the smallest set of objects that is consistent with what is known. This paper examines closely the properties and the semantics underlying circumscription, considering both its expressive power and limitations. In addition we study circumscription's relationship to several related formalisms, such as negation by failure, the closed world assumption, default reasoning and Planner's THNOT. In the discussion a number of extensions to circumscription are proposed, allowing one to tightly focus its scope of applicability. In addition, several new rules of conjecture are proposed based on the notions of relevance and minimality. Finally a synthesis between the approaches of McCarthy and Konolige is used to extend circumscription, as well as several other rules of conjecture, to account for resource limitations