COSC 3402 Artificial Intelligence

<<< Predicate Logic

Applications of Resolution Theory - Logic Programming

Planing

	                /----------------\
	Program ------->|                |
	                |   Resolution   |
	Goal ---------->|                |--------> YES
	                \----------------/
			         |
				 |
				 V
				 e=e1.e2...en

Program: f(x)=x.11 :-
Goal: y=f(2)
Program |--         e(Goal(2.y))

C1. f(x)=x.11
c2. ¬(f(2)=y)	e = [x/2,y/2.11]
C3. empty clause

Horn Clauses are clauses with at most 1 positive literal.
E.g. p, ¬p, pv¬qv¬r are H.C. (but pv¬qvr is not)

From disjunctions to horn clauses

1: ~q v p v ~r v ~s
-- Move positives to left
2: p v ~q v ~r v ~s
-- 
3: p v ~ (q ^ r ^ s)
--
4: p <-- (q ^ r ^ s)
-- In prolog notation (almost)
5: p :- q ^ r ^ s
-- More like prolog (horn clause)
6: p:- q,r,s     --> This is a horn clause

:- a,b,c         --> This is a goal (query)

p :-             --> This is a fact

Goal-Oriented Behaviour

1. Theory of Actions
2. Planning

KB =    State      U     Action_Information
     (May change)           (Wont change)

Actions

1. Action Name - action(arg1, ..., argk)
   e.g. move(R,X,From,To) - R should move X from From to To
2. Pre-condition - must satisfy before executing
   e.g. close_to(R,X), clear(X), clear(To), on(X,From)
3. Effects - true after action executed
   e.g. (Some effects are) on(X,To), clear(From) will be true and clear(To), on(X,From) will become false.

Strips Planner

• State - list of possible atomic formulas
  In our example, the current state (of environment) is: [on(r,1), on(x,from), clear(to), clear(x)]
• Actions in Strips
  1. Preconditions list (PREC)
  2. Positive effects list (Ef+)
  3. Negative effects list (Ef-)
  Let S be the current situation. To execute an action:
  1. PREC C S (sub-list)
  2. Execute Action
  3. Compute the new state:
     S_new = (S - (Ef-)) U (Ef+)

Example:
1. PREC C S
2. execute move(r,x,from,to)
3. Snew =  [on(r,1), clear(x), on(x,to), clear(from)]

Notation: If a is an action and S is a state, then a(S) is the state obtained from S by executing a.

In strips: a(S) = (S - Eff-) U Eff+

Situation Calculus >>>