Page 122 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes Varying: These are variables that are not to be taken into account at all in the course of
minimization.

Fixed: These are variables considered fixed while doing a minimization; in other words,
minimization can be done only by comparing models with the same values of these variables.
The difference is the value of the varying conditions is simply assumed not to matter. The fixed
conditions instead characterize a possible situation, so that comparing two situations where
these conditions have different value makes no sense.

Formally, the extension of circumscription that incorporate varying and fixed variables is as
follows, where P is the set of variables to minimize, Z the fixed variables, and the varying
variables are those not in P U Z:
CIRC(T; P, Z)= {M|M T and ∃N such that N T, N I P ⊂ M I P and N I Z = M I Z}
In words, minimization of the variables assigned to true is only done for the variables in P;
moreover, models are only compared if the assign the same values on the variables of Z. All
other variables are not taken into account while comparing models. The solution to the frame
problem proposed by McCarthy is based on circumscription with no fixed conditions. In the
propositional case, this solution can be described as follows: in addition to the formulae directly
encoding what is known, one also define new variables representing changes in the values of
the conditions; these new variables are then minimized.
For example, of the domain in which there is a door that is closed at time 0 and in which the
action of opening the door is executed at time 2, what is explicitly known is represented by the
two formulae:
¬open
0
true → open
2
The frame problem shows in this example as the problem that ¬open is not a consequence of
1
the above formulae, while the door is supposed to stay closed until the action of opening it is
performed. Circumscription can be used to this aim by defining new variables change_open to
t
model changes and then minimizing them:
changeopen ≡ (open ≡ open )
0 /
0
1
changeopen ≡ (open ≡ open )
1 /
1 2
…
As shown by the Yale shooting problem, this kind of solution does not work. For example,
¬open is not yet entailed by the circumscription of the formulae above: the model in which
1
change open is true and change open is false is incomparable with the model with the opposite
0 1
values. Therefore, the situation in which the door becomes open at time 1 and then remains open
as a consequence of the action is not excluded by circumscription.
Several other formalizations of dynamical domains not suffering from such problems have
been developed. Many use circumscription but in a different way.
6.9.3 Predicate Circumscription

The original definition of circumscription proposed by McCarthy is about first-order logic. The
role of variables in propositional logic (something that can be true or false) is played in first-order
logic by predicates. Namely, a propositional formula can be expressed in first-order logic by
replacing each propositional variable with a predicate of zero arity (i.e., a predicate with no

116 LOVELY PROFESSIONAL UNIVERSITY