Knowledge Evolution : Knowledge Evolution Up to now we have not considered evolution of the knowledge
In real situations knowledge evolves by:
completing it with new information
changing it according to the changes in the world itself
Simply adding the new knowledge possibly leads to contradiction
In many cases a process for restoring consistency is desired
Revision and Updates : Revision and Updates In real situations knowledge evolves by:
completing it with new information (Revision)
changing it according to the changes in the world itself (Updates)
These forms of evolution require a differentiated treatment. Example:
I know that I have a flight booked for London (either for Heathrow or for Gatwick).
Revision: I learn that it is not for Heathrow
I conclude my flight is for Gatwick
Update: I learn that flights for Heathrow were canceled
Either I have a flight for Gatwick or no flight at all
Reasoning about changes : Reasoning about changes Dealing with changes in the world, rather than in the belief (Updates rather than revision) requires:
Methodology for representing knowledge about the chang es, actions, etc, using existing languages
or
New languages and semantics for dealing with a changing world
Possibly with translation to the existing languages
Situation calculus : Situation calculus Initially developed for representing knowledge that changes using 1st order logics [McCarthy and Hayes 1969]
Several problems of the approach triggered research in nonmotonic logics
Main ingredients
Fluent predicates: predicates that may change their truth value
Situations: in which the fluents are true or false
A special initial situation
Other situations are characterized by the actions that were performed from the initial situation up to the situation
Situation Calculus - Basis : Situation Calculus - Basis (Meta)-predicate holds/2 for describing which fluents hold in which situations
Situations are represented by:
constant s0, representing the initial situation
terms of the form result(Action,Situation), representing the situation that results from performing the Action in the previous situation
Yale shooting : Yale shooting There is a turkey, initially alive:
holds(alive(turkey),s0).
Whenever you shoot with a loaded gun, the turkey at which you shoots dies, and the gun becomes unloaded
¬holds(alive(turkey),result(shoot,S)) ← holds(loaded,S).
¬holds(loaded,result(shoot,S)).
Loading a gun results in a loaded gun
holds(loaded,result(load,S)).
What happens to the turkey if I load the gun, and then shoot at the turkey?
holds(alive(turkey), result(shoot, result(load,s0)))?
Frame Problem : Frame Problem In general only the axioms for describing what changes are not enough
Knowledge is also needed about what doesn’t change.
Suppose that there is an extra action of waiting:
holds(alive(turkey), result(shoot, result(wait,result(load,s0)))) is not true.
By default, fluents should remain with the truth value they had before, unless there is evidence for their change (commonsense law of inertia)
In 1st order logic it is difficult to express this
With a nonmonotonic logics this should be easy
Frame Axioms in Logic Programming : Frame Axioms in Logic Programming The truth value of fluents in two consecutive situations is, by default, the same:
holds(F,result(A,S)) :- holds(F,S), not ¬holds(F,result(A,S)), not nonInertial(F,A,S).
¬holds(F,result(A,S)) :- ¬holds(F,S), not holds(F,result(A,S)), not nonInertial(F,A,S)
This allows for establishing the law of inertia.
Representing Knowledge with the situation calculus : Representing Knowledge with the situation calculus Write rules for predicate holds/2 describing the effects of actions.
Write rules (partially) describing the initial situation, and possibly also some other states
Add the frame axioms
Care must be taken, especially in the case of Stable Models, because models are infinite
Look at the models of the program (be it SM or WF) to get the consequences
Yale shooting results : Yale shooting results The WFM of the program contains, e.g.
holds(alive,result(load,s0))
¬holds(alive,result(shoot,result(wait,result(load,s0))))
¬holds(loaded,result(shoot,result(wait,result(load,s0))))
Queries of the form
?- holds(X,)
return what holds in the given situation.
Queries of the form
?- holds(,X)
return linear plans for obtaining the property from the initial situation.
More on the rules of inertia : More on the rules of inertia The rules allow for, given information about the past, reasoning about possible futures.
Reasoning about the past given information in the future is also possible, but requires additional axioms:
holds(F,S) :- holds(F,result(A,S)), not ¬holds(F,S), not nonInertial(F,A,S).
¬holds(F,S) :- ¬holds(F,result(A,S)), not holds(F,S), not nonInertial(F,A,S).
Care must be taken when using these rules, since they may create infinite chains of derivation”
On the other hand, it is difficult with this representation to deal with simultaneous actions
Fluent Calculus : Fluent Calculus Extends by introducing a notion of state [Thielscher 1998]
Situation are representations of states
State(S) denotes the state of the world in situation S
Operator o is used for composing fluents that are true in the same state.
Example:
State(result(shoot,Soalive(turkey)oloaded) = S
State(result(load,S)) = Soloaded
Axioms are needed for guaranteeing that o is commutative and associative, and for equality
This allows inferring non-effects of action without the need for extra frame axioms
Event Calculus : Event Calculus It is another methodology developed for representing knowledge that changes over time [Kowalski and Sergot 1986]
Solves the frame problem in a different (simpler) way, also without frame axioms.
It is adequate for determining what holds after a series of action being performed
It does not directly help for planning and for general reasoning about the knowledge that is changing
Event Calculus - Basis : Event Calculus - Basis Fluents are represented as terms, as in situation calculus
Instead of situations, there is a notion of discrete time:
constants for representing time points
predicate
Event Calculus – Basis (cont) : Event Calculus – Basis (cont) Events initiate (the truth) of some fluents and terminate (the truth) of other fluents.
This is represented using predicates initiates/3 and terminates/3
Effects of action are described by the properties initiated and terminated by the event associated to the action occurrence.
There is a special event, that initiates all fluents at the beginning
Yale shooting again : Yale shooting again There is a turkey, initially alive:
initiates(alive(turkey),start,T). occurs(start,t0).
Whenever you shoot with a loaded gun, the turkey at which you shoots dies, and the gun becomes unloaded
terminates(alive(turkey),shoot,T) ← holds_at(loaded,T).
terminates(loaded,shoot,T).
Loading a gun results in a loaded gun
initiates(loaded,load,T).
The gun was loaded at time t10, and shoot at time t20:
occurs(load,t10). occurs(shoot,t20).
Is the turkey alive at time t21?
holds_at(alive(turkey), t21)?
General axioms for event calculus : General axioms for event calculus Rules are needed to describe what holds, based on the events that occurred:
holds_at(P,S) :- occurs(E,S1), initiates(P,E,S1), S1 < S, not clipped(P,S1,S).
clipped(P,S1,S2) :- occurs(E,S), S1 ≤ S < S2, terminates(P,E,S).
There is no need for frame axioms. By default thing will remain true until terminated
Event calculus application : Event calculus application Appropriate when it is known which events occurred, and the reasoning task is to know what holds in each moment. E.g.
reasoning about changing databases
reasoning about legislation knowledge bases, for determining what applies after a series of events
Reasoning with parallel actions.
Not directly applicable when one wants to know which action lead to an effect (planning), or for reasoning about possible alternative courses of actions
No way of inferring occurrences of action
No way of representing various courses of actions
No way of reasoning from the future to the past
Event calculus and abduction : Event calculus and abduction With abduction it is possible to perform planning using the event calculus methodology
Declare the occurrences of event as abducible
Declare also as abducible the order among the time events occurred
Abductive solutions for holds_at(,