reasoning about results of actions is central to a knowledge-based agent. propositional logic gave us an example of the wumpus world that describes how actions affect the environment. the problem with propositional logic is the need to have different copies of the action description for each time the action might be executed. this section uses first-order logic to avoid that problem
one way to avoid multiple copies of axioms is to simply quantify over time, to say:
“for all time t, such-and-such is the result at time t+1 of doing action at time t”
this approach is called situation calculus and involves the following ontology:
§ situations – are logical terms consisting of the initial situation (S0) and all situations that are generated by applying an action to a situation.
§ the function Result(a,s) gives the resulting situation when action a is applied to situation s
§ fluents – are functions and predicates that vary from one situation to the next, such as the location of the agent or the aliveness of the wumpus
§ atemporal/eternal predicate and functions are also allowed (e.g. predicate Gold(G1) and function LeftLegof(Wumpus))
frame problem – representing all things that stay the same. finding an efficient solution to the frame problem is a must
frame axioms – say what stays the same. if there are F fluent axioms and A actions, then we will need O(AF) frame axioms. On the other hand if each action has at most E effects (where E is typically much less than F) then we should be able to represent what happens with a much smaller knowledge base of size O(AE). this is the representational frame problem.
inferential frame problem – projects the results of a t-step sequence of actions in time O(Et), rather than O(At) or O(AEt)
qualification problem – ensuring all necessary conditions for an action’s success have been specified. there is no complete solution
Solving the Representational Frame Problem
axioms are called successor-state axioms of form
| SUCCESSOR-STATE AXIOM:Action is possible -> (fluent is true in result state <-> (Action’s effect made it true) v (It was true before and action left it alone)) |
TODO page 332 of AI: A Modern Approach 2nd Edition
Solving the Inferential Frame Problem
TODO page 333 of AI: A Modern Approach 2nd Edition
Time and Event Calculus
situation calculus works well on a single agent performing instantaneous, discrete actions. However, when actions have duration and overlaps with each other, event calculus should be used.
event calculus
· is based on points in time rather than situations
· in event calculus, fluents (functions or predicates that vary from one situation or time to the next) hold at points in time rather than at situations
· designed to reason over intervals of time
· an event calculus axiom says that a fluent is true at a point in time if the fluent was initiated by an event at some time in the past and was not terminated by an intervening event
· the INITIATES and TERMINATES relations plays a similar role to the RESULT relation in situation calculus
· INITIATES(e,f,t) means that event e at time t cause fluent f to be true
· TERMINATES(w,f,t) means that event w at time t causes fluent f to be false
· HAPPENS(e,t) means event e happens at time t
· CLIPPED(f,t1,t2) means fluent f is terminated at sometime between time t1 and t2
· this gives us functionality similar to situational calculus but with ability to talk about time points and intervals (e.g. HAPPENS(turn_off(light_switch_1), 1:00) meaning “light switch was turned off at 1:00”)
· extensions of event calculus to address problems of indirect effects, events with duration, concurrent events, continuously changing events, nondeterministic effects, causal constraints, etc
Generalized Events
generalized event – is composed from aspects of some “space-time chunk”
for example WWII is an event that took place at various points in space-time. it can be broken down into subevents:
| subevent(battle_of_britian, world_war_ii)subevent(world_war_ii, twentieth_century) |
intervals – are chunks of space-time that include all of space between 2 time points
Period(e) – denotes the smallest interval enclosing the event e
Duration(i) – the length of time occupied by an interval
then we can say
| Duration(Period(world_war_ii)) > Years(5) |
Like any other sort of object, generalized events can be grouped into categories (e.g. World War II belongs to the categories of Wars
To say civil war occured in England in the 1640s:
| ∃w w∈CivilWars ʌ SubEvent(w,1640s) ʌ In(Location(w) England) |
Processes
discrete events – events that have definite structure
liquid events or process categories – any subinterval of a process is also a member of the same process category – processes of continuous non-change
| // Marcus was flying at some time yesterdayE(Flying(Marcus), Yesterday) // Stuart was working today during lunch hourT(Working(Stuart), TodayLunchHour) |
temporal substances – liquid events
spatial substances – things like butter
Time Intervals
2 kinds of time intervals: moments and extended intervals (only moments have zero duration)
| Partition({Moments, ExtendedIntervals}, Intervals)i ∈ Moments ⇔ Duration(i) = Seconds(0) |
Next we invent a time scale and associate points on that scale with moments, giving us ab- solute times. The time scale is arbitrary; we measure it in seconds and say that the moment at midnight (GMT) on January 1, 1900, has time 0. The functions Begin and End pick out the earliest and latest moments in an interval, and the function Time delivers the point on the time scale for a moment. The function Duration gives the difference between the end time and the start time.
| Interval(i) ⇒ Duration(i)=(Time(End(i)) − Time(Begin(i)))Time(Begin(AD1900)) = Seconds(0)Time(Begin(AD2001)) = Seconds(3187324800)Time(End(AD2001))= Seconds(3218860800)Duration(AD2001) = Seconds(31536000) |
To make these numbers easier to read, we also introduce a function Date, which takes six arguments (hours, minutes, seconds, day, month, and year) and returns a time point:
| Time(Begin(AD2001)) = Date(0, 0, 0, 1, Jan, 2001)Date(0, 20, 21, 24, 1, 1995) = Seconds(3000000000) |
Two intervals Meet if the end time of the first equals the start time of the second. The com- plete set of interval relations, as proposed by Allen (1983), is shown graphically in Figure 12.2 and logically below:
| Meet(i,j) ⇔ End(i) = Begin(j)Before(i,j) ⇔ End(i) < Begin(j)After(j,i) ⇔ Before(i,j)During(i,j) ⇔ Begin(j) < Begin(i) < End(i) < End(j)Overlap(i,j) ⇔ Begin(i) < Begin(j) < End(i) < End(j)Begins(i,j) ⇔ Begin(i) = Begin(j)Finishes(i,j) ⇔ End(i) = End(j)Equals(i,j) ⇔ Begin(i) = Begin(j) ∧ End(i) = End(j) |
These all have their intuitive meaning, with the exception of Overlap: we tend to think of overlap as symmetric (if i overlaps j then j overlaps i), but in this definition, Overlap(i,j) only holds if i begins before j. To say that the reign of Elizabeth II immediately followed that of George VI, and the reign of Elvis overlapped with the 1950s, we can write the following:
| Meets(ReignOf(GeorgeVI), ReignOf(ElizabethII))Overlap (Fifties, ReignOf(Elvis))Begin(Fifties) = Begin(AD1950)End(Fifties) = End(AD1959) |
Fluents and Objects
physical objects can be viewed as generalized events, that a physical object is a chunk of space-time.
For example, USA can be thought of as an event that began in 1776 as a union of 13 states and is still in progress today as a union of 50 states. To describe changing properties of USA we use fluents (e.g. Population(USA)).
President(USA) denotes a single object that consist of different people at different times.
To say that George Washington was president throughout 1790:
| T(Equals(President(USA), GeorgeWashington), AD1790) |
We use the function symbol Equals rather than the standard logical predicate =, because we cannot have a predicate as an argument to T, and because the interpretation is not that GeorgeWashington and President(USA) are logically identical in 1790; logical identity is not something that can change over time. The identity is between the subevents of each object that are defined by the period 1790.
