Pushpak Bhattacharyya

CS344: Introduction to Artificial Intelligence

Intelligence

(associated lab: CS386)

Pushpak Bhattacharyya

CSE Dept., IIT Bombay

Lecture–4: Fuzzy Control of Inverted

P d l P i i l C l l b d

Pendulum + Propositional Calculus based puzzles

Lukasiewitz formula for Fuzzy Implication

„

t(P) = truth value of a proposition/predicate In

„

t(P) truth value of a proposition/predicate. In fuzzy logic t(P) = [0,1]

t(

) = min[1 1 t(P)+t(Q)]

„

t( ) = min[1,1 -t(P)+t(Q)]

Use Lukasiewitz definition Use Lukasiewitz definition

„ t(pÆq) = min[1,1 -t(p)+t(q)]

W h ( ) [1 1 ( ) ( )]

„ We have t(p->q)=c, i.e., min[1,1 -t(p)+t(q)]=c

„ Case 1:

1 i 1 t( )+t( )> 1 i t( )>

„ c=1 gives 1 -t(p)+t(q)>=1, i.e., t(q)>=a

„ Otherwise, 1 -t(p)+t(q)=c, i.e., t(q)>=c+a-1 Combining t(q)=max(0 a+c 1)

„ Combining, t(q)=max(0,a+c-1)

„ This is the amount of truth transferred over the channel pÆq

channel pÆq

ANDING of Clauses on the LHS of implication

Eg: If Pressure is high AND Volume is low then make Temperature

)) (

), (

min(

)

( P Q t P t Q

t ∧ =

Eg: If Pressure is high AND Volume is low then make Temperature Low

High Pressure Low

Volume Volume

Low Temperature

P /V l /T

P₀ T₀ V₀

Mu(P₀)<Mu(V₀) Pressure/Volume/Temp ( ₀) ( ₀)

Hence Mu(T₀)=Mu(P₀)

Fuzzy Inferencing

Core

The Lukasiewitz rule

t( ) = min[1,1 + t(P) – t(Q)]

An example Q P →

An example

Controlling an inverted pendulum

θ

θ

= d θ / dt

Motor i=current

The goal: To keep the pendulum in vertical position (θ=0)

i d i ilib i Wh h d l d

in dynamic equilibrium. Whenever the pendulum departs from vertical, a torque is produced by sending a current ‘i’

Controlling factors for appropriate current

A l θ A l l it θ^.

Angle θ, Angular velocity θ Some intuitive rules

If θ is +ve small and θ^. is –ve small then current is zero

then current is zero

If θ is +ve small and θ^. is +ve small then current is –ve medium

-ve ve +ve +ve

Control Matrix θ

ve

ve

med -ve

small Zero +ve small

+ve

θ^. θ med -ve med

-ve +ve +ve Region of

small Zero

+ve med

+ve small +ve Z -ve

Zero Region of

interest e o

+ve

ve small -ve -ve

+ve

small Zero ve Z

small +ve

ve ve med

small Zero

med

Each cell is a rule of the form If θ i d θ^. i

If θ is <> and θ is <>

then i is <>

4 “Centre rules”

1 if θ Z d θ^. Z th i Z

1. if θ = = Zero and θ = = Zero then i = Zero

2. if θ is +ve small and θ^. = = Zero then i is –ve small 3. if θ is –ve small and θ^.= = Zero then i is +ve small 4 if θ = = Zero and θ^. is +ve small then i is ve small 4. if θ = = Zero and θ is +ve small then i is –ve small 5. if θ = = Zero and θ^. is –ve small then i is +ve small

Linguistic variables 1 Zero

1. Zero

2. +ve small 3. -ve small

Profiles

zero 1

+ve small -ve small

1

ε ε

-ε +ε ε₂

-ε₂

-ε₃ ε₃

Quantity (θ, θ^., i)

Inference procedure

1. Read actual numerical values of ^{θ and θ.}

2 Get the corresponding μ values μ_Z μ_{(+ ll)}

2. Get the corresponding μ values μ_Zero, μ(+ve small), μ(-ve small). This is called FUZZIFICATION

3. For different rules, get the fuzzy i values from

3. For different rules, get the fuzzy i values from the R.H.S of the rules.

4. “Collate” by some method and get ONE current y g value. This is called DEFUZZIFICATION

5. Result is one numerical value of i.

Rules Involved

if θ is Zero and dθ/dt is Zero then i is Zero

if θ is Zero and dθ/dt is +ve small then i is ve small if θ is Zero and dθ/dt is +ve small then i is –ve small if θ is +ve small and dθ/dt is Zero then i is –ve small

if θ +ve small and dθ/dt is +ve small then i is -ve medium

zero 1

+ve small -ve small

1

ε ε

-ε +ε ε₂

-ε₂

-ε₃ ε₃

Quantity (θ, θ^., i)

Fuzzification

Suppose θ is 1 radian and dθ/dt is 1 rad/sec μ (θ =1)=0 8 (say)

μ_zero(θ =1)=0.8 (say)

μ _+ve-small(θ =1)=0.4 (say) μ_zero(dθ/dt =1)=0.3 (say)

μ_+ve-small(dθ/dt =1)=0.7 (say)

μ_{+ve small}( ) ( y)

zero 1

+ve small -ve small

1

ε ^{1 rad/sec} ε

-ε +ε ε₂

-ε₂

-ε₃ ε₃

Quantity (θ, θ^., i) 1rad

Fuzzification

Suppose θ is 1 radian and dθ/dt is 1 rad/sec μ_zero(θ =1)=0.8 (say)

μ _{+ve small}(θ =1)=0.4 (say) μ _+ve-small(θ 1) 0.4 (say) μ_zero(dθ/dt =1)=0.3 (say)

μ_+ve-small(dθ/dt =1)=0.7 (say)

if θ is Zero and dθ/dt is Zero then i is Zero min(0.8, 0.3)=0.3

hence μ _{e o}(i)=0.3 hence μ_zero(i) 0.3

if θ is Zero and dθ/dt is +ve small then i is –ve small min(0.8, 0.7)=0.7

hence μ_-ve-small(i)=0.7

if θ i ll d dθ/dt i Z th i i ll

if θ is +ve small and dθ/dt is Zero then i is –ve small min(0.4, 0.3)=0.3

hence μ-ve-small(i)=0.3

if θ +ve small and dθ/dt is +ve small then i is -ve medium/ min(0.4, 0.7)=0.4

hence μ_-ve-medium(i)=0.4

Finding i

di

-ve small

zero 1

-ve small -ve medium

ve small

0.4 0.7

-ε +ε

-ε₂ -ε₃

-4.1 -2.5 ε ε

0.3 Possible candidates:

i=0.5 and -0.5 from the “zero” profile and μ=0.3

i 0 1 and 2 5 f om the “ e small” p ofile and 0 3 i=-0.1 and -2.5 from the “-ve-small” profile and μ=0.3 i=-1.7 and -4.1 from the “-ve-small” profile and μ=0.3

Defuzzification: Finding i

by the centroid method

Required i value Centroid of three

-ve small -ve medium

trapezoids

-ε +ε

zero

-4.1 -2.5 ε ε

Possible candidates:

i is the x-coord of the centroid of the areas given by the bl e t ape i m the g een t ape i ms and the black t ape i m blue trapezium, the green trapeziums and the black trapezium

Propositional Calculus and Puzzles

Propositions

− Stand for facts/assertions

− Declarative statements

− As opposed to interrogative statements (questions) or imperative statements (request, order)

Operatorsp

) ( (~),

), ( ),

(∧ OR ∨ NOT IMPLICATION ⇒ AND

=> and ¬ form a minimal set (can express other operations) - Prove it.

Tautologies are formulae whose truth value is always T, whatever the assignment is

Model

In propositional calculus any formula with n propositions has 2ⁿ models (assignments)

- Tautologies evaluate to T in all models.

Examples:

1) ⁾

P ∨ P

2)

P P ∨ ¬

) (

)

(P ∧ Q ⇔ P ∨ Q

2)

e Morgan with AND

) (

)

(P ∧ Q ⇔ ¬P ∨ ¬Q

¬

-e Morgan with AND

Semantic Tree/Tableau method of proving tautology

Start with the negation of the formula

α-formula

)]

( )

(

[¬ P∧Q ⇒ ¬P∨¬Q

¬ ^{- α - formula}

β-formula α-formula

- α - formula - β - formula

)

( P ∧ Q

¬

)

( P Q

p q

α formula

) (¬P ∨¬Q

¬

q

¬q

¬ p

Example 2:

(α - formula) X )]

( ) (

) (

[ A ∧ B ∨ C ⇒ A ∧ B ∨ A ∧ C

¬

α-formula ^{¬A ¬C}

(α - formulae) )

( B C

A ∧ ∨

)) (

)

(( A ∧ B ∨ A ∧ C

¬

¬A ¬B ¬A ¬B

)

( A ∧ B

¬

A (β - formulae)

)) ( A ∧ C

¬

A B C

A

B C A

B C

A B C

B C B C

Contradictions in all paths

A puzzle A puzzle

(Zohar Manna, Mathematical Theory of Computation 1974)

Computation, 1974)

From Propositional Calculus

Tourist in a country of truth- sayers and liers

„ Facts and Rules: In a certain country, people either always speak the truth or always

lie A tourist T comes to a junction in the lie. A tourist T comes to a junction in the country and finds an inhabitant S of the

country standing there. One of the roads at the junction leads to the capital of the

the junction leads to the capital of the

country and the other does not. S can be asked only yes/no questions.

Q i Wh i l / i T

„ Question: What single yes/no question can T ask of S, so that the direction of the capital is revealed?

Diagrammatic representation

Capital Capital

S (either always says the truth Or always lies)

Or always lies) T (tourist)

Deciding the Propositions: a very difficult Deciding the Propositions: a very difficult step- needs human intelligence

„

P: Left road leads to capital

„

Q: S always speaks the truth

„

Q: S always speaks the truth

Meta Question: What question should the tourist ask

„

The form of the question

„

Very difficult: needs human intelligence

„

Very difficult: needs human intelligence

„

The tourist should ask

„

Is R true?

„

Is R true?

„

The answer is “yes” if and only if the left road leads to the capital p

„

The structure of R to be found as a

function of P and Q

A more mechanical part: use of truth table

P Q S’s

Answer R

T T Yes T

T F Yes F

F T N F

F T No F

F F No T

F F No T

Get form of R: quite mechanical

„

From the truth table

„

R is of the form (P x-nor Q) or (P

Q)

„

R is of the form (P x nor Q) or (P

Q)

Get R in

English/Hindi/Hebrew…

„ Natural Language Generation: non-trivial

„ The question the tourist will ask isq

„ Is it true that the left road leads to the capital if and only if you speak the truth?

„ Exercise: A more well known form of this

question asked by the tourist uses the X-OR t i t d f th X N Wh t h

operator instead of the X-Nor. What changes do you have to incorporate to the solution, to get that answer?

get that answer?