COSC 3402 Artificial Intelligence

<<< Planing

Situation Calculus

It is an extension of predicate logic.

• Individual variables: x,y,z,...
• Situation variables: S0, S1, S2,...
• Among function symbols we have names of actions: move(r,block,from,to)

  do(action,situation)
  
  [situation] ----------------> [do(action,situation)]
                   action
  

• Predicates:
  • fluents: predicates with situation argument e.g. on(b,a,S1)
  • non-fluents e.g. robot(r2d2)

Example: Goal: Save the princess from the dragon, or
dead(dragon,s) ^ ~dead(princess,s)
Goals:

• take(h,gun)
• load(h,gun)
• aim(h,gun,At)
• shoot(h,gun,At)

Situations in Situation Calculus are sets of formulas.
S0 = {~dead(princess,S0), ~dead(dragon,S0),...}

Actions in Situation Calculus: poss(action,S) = α(S)

• poss(take(H,O),S) = close_to(H,O,S) ^ ~heavy(O)
• poss(load(H,G),S) = has(H,G,S)
• poss(aim(H,G,At),S) = has(H,G,S)
• poss(shoot(H,G,At),S) = has(H,G,S) ^ loaded(G,S)

Effects in Situation Calculus: poss(action,S) --> α(do(action,S)

     poss.  do action     α
     (   )  --------->  (   )
       S                  S' = do(action,S)

• poss(take(H,O),S) --> has(H,O,do(take(H,O),S))
• poss(load(H,G),S) --> loaed(G,do(load(H,G),S))
• poss(aim(H,G,At),S) --> aimed_at(H,G,At), do(aim(H,G,At),S))
• poss(shoot(H,G,At),S) --> (At = head v At = heart) ^ dead(At,do(shoot(H,G,At),S))

S0 = {~dead(princess,S0), ~dead(dragon,S0),~heavy(gun),close_to(h,gun,S0)}
Find a plan to satisfy: dead(dragon,S)

• Step1. Try to execute take(h,gun) in S0
  Since preconditions ~heavy(gun) and close_to(h,gun,S0) are true in S0 these actions can be executed resulting in the state
  S1 = do(take(h,gun),S0)
  In S1 has(h,gun,S1) is true.
• Step2. Try to execute load(h,load) in S1
  Since has(h,gun,S1) is true, we can execute "load" which results in situation
  S2 = do(load(h,gun),S1)
  By effect axiom from load,
  loaded(gun,S2) is true
• Step3. Try to execute aim(h,gun,head) in S2.
  Check preconditions has(h,gun,S2) - Unknown!

Note: Effect axioms specify the(some) change in the environment after the execution of an action. However they do not specify what must remain unchanged.
We need special axioms called Frame Axioms to specify relationships that must not change.

Frame axioms for load and has
poss(load(H,G),S) --> has(H,G,do(load(H,G,S)))

• Back to Step2:
  has(h,gun,S) is true. By the frame axiom for load and has:
  has(h,gun,S2) is true.
• Return to Step3, now we know the precondition is true
  So, we can execute: aim(h,gun,head)
  By the effect axiom we know: aimed_at(h,gun,head,S3)
  where S3 = do(aim(h,gun,head),S2)
• Step4. Try to execute shoot(h,gun,head) in S3
  Are has(h,gun,S3) and loaded(gun,S3) true?
  To get has(h,gun,S3) true, we need a new frame axiom for aim and has:
  poss(aim(h,G,head),S) --> has(H,G,do(aim(H,G,At),S))
  By this axiom has(h,gun) is true in S3
  To have loaded(gun,S3) we need a frame axiom for aim and loaded:
  poss(aim(H,G,At),S) ^ loaded(G,S) --> loaded(G, do(aim(H,G,At),S))
  By this axiom and the fact that loaded(gun,S3) is true,
  loaded(gun,S3) is true.
• Step4. To conclude all the preconditions for shoot(h,gun,head) are true in S3.
  The Resulting situation:
  S4 = do(shoot(h,gun,head),S3)
  So by the effect axiom for shoot:
  dead(dragon,S4) is true.

How about ~dead(princess,S4)?
Add frame axioms:
prec(take(H,O),S) ^ ~dead(princess,S) --> ~dead(princess,do(take(H,O),S))

	        take           load           aim           shoot
	( S0 )  ---->  ( S1 )  ---->  ( S2 )  --->  ( S3 )  ----->  ( S4 )

Frame Axioms: poss(action,S) ^ l(S) ---> l(do(action,S))

Frame Problem: too many of these axioms are needed if there are n actions and m elements, then we need <= n.m frame axioms.

A possible solution

A a ( poss(a, S) ^ ~dead(princess, S) ^ 
a /= shoot(h,gun,princess) ^ a /= eat(dragon, princess)  
                                  --->  ~dead(princess,do(a,S)) )

Goals in Situation Calculus: arbitrary formulas of S.C.

E.g. E s (dead(dragon,s) ^ ~dead(princess,s))
E s ( dead(dragon,s) ^ A s1 (acc(s,s1)) --> dead(dragon, s1))
A s acc(s,s1):

            a             acc(sx,s)
 (   ) ----------> (    ) --->...---> (    )
   s                 sx                 s1

As ( E sx acc(sx,s1) ^ E a (sx = do(a,s))  --->  acc(s,s1))

Planing Problem in Situation Calculus

     _   _
    |A| |B|
---|---|---|---
     1   2   3
     
E s ( acc(s,s0) ^ on(B,1,s) ^ on(A,B,s) )
     _
    |A|
    |B| 
---|---|---|---
     1   2   3

Given: initial situation s0 
	goal α (typically E s α(s))

AI agent's KB:
	KB = actions U s0 U info_about_past_state
	                |               |
	         e.g. on(A,B,s0)      clear(A,spost)

Planing Task:
	KB |-- E s α(s)
	
To answer the goal:   E s α(s)
	We can use an automated reasoning system for S.C. (e.g. GOLOG)
	(Visit the Cognitive Robotics web page at UofT)

An answer is given in the form:
	s = do(an, do(a(n-1), do(...,do(a1,s0)...)))
	
	s0 --a1--> s1 --> ... --> s(n-2) --a(n-1)--> s(n-1) --an--> sn
	
	Plan = a1, ..., a(n-1), an

Possible extensions of basic S.C.

                           \C1 /   \   /
             R              \_/     \_/
---|---|---|---|---|---|---|---|---|---|---
    d1  d2      d3

Clean the office:

Es Ad (dirt(d) ---> Al (location(l) ---> ~on(d,l,s)))

π d take(robot,d) (No-deterministicly select d)
To make it more complete: π d (dirt(d) ---> take(robot,d))

We'll more into extension in future courses.

Neural Networks >>>