Biomedical Department, Nit Raipur

1

LECTURE:03

Biomedical Department, NIT Raipur

10/11/09

PRODUCTION SYSTEM 2

A PS is a computer

program typically used to provide some form of AI, which consists a set of rules about behavior.

A PS provides the mechanism necessary to execute

productions in order to achieve some goal for the system.

Biomedical Department, NIT Raipur

10/11/09

PRODUCTION SYSTEM 3

A production system consists of four basic components: 1. A set of rules of the form

Ci ® Ai or C1, C2, … Cn => A1 A2 …Am Left hand side (LHS) Conditions/antecedents

Right hand side (RHS) Conclusion/consequence

where Ci is the condition part and Ai is the action part. The condition determines when a given rule is applied, and the action determines what happens when it is applied.

Biomedical Department, NIT Raipur

10/11/09

4

2. knowledge databases / working memory : Contains whatever information is relevant for the given problem & also maintains data about current state or knowledge. Some parts of the database may be permanent, while others may temporary and only exist during the solution of the current problem. The information in the databases may be structured in any appropriate manner.

Biomedical Department, NIT Raipur

10/11/09

5

3. A control strategy : that determines the order in which the rules are applied to the database, and provides a way of resolving any conflicts that can arise when several rules match at once. 4. A rule applier : which is the computational system that implements the control strategy and applies the rules.

Biomedical Department, NIT Raipur

10/11/09

Production rule for water jug problem 6 1.

(x, y)  (4, y),

If x < 4 fill the 4-gallon jug.

2.

(x, y)  (x,3),

If y < 3 fill the 3-gallon jug.

3.

(x, y)  (x- d , y),

If x > 0 pour some water out of the 4-gallon jug

4.

(x, y)  (x, y - d), If y > 0 pour some water out of the 4-gallon jug

5.

(x, y)  (0, y)

6.

(x, y)  (x, 0),

If x > 0 empty the 4-gallon jug. If y > 0 empty the 3-gallon jug.

7.

(x, y)  (4, y – (4 – x) ), if x + y >= 4 & y > 0 pour water from the 3-gallon jug into the 4-gallon jug until the 4-gallon jug is full.

8.

(x, y)  (x – (3 – y), 3 ), if x + y >= 4 & y > 0 pour water from the 4-gallon jug into the 3-gallon jug until 3-gallon jug is full.

Biomedical Department, NIT Raipur

the

10/11/09

7

9. (x, y)  (x + y, 0 ), if x + y <= 4 & y > 0 pour all the water from the 3-gallon jug into the 4gallon jug. 10. (x, y)  (0, x + y), if x + y <= 3 & x > 0 pour all the water from the 4-gallon jug into the 3-gallon jug. 11. (0, 2)  (2, 0), pour 2-g from 3-g to 4-g 12. (2, y)  (0, y) , empty the 2-g in to 4-g on the ground

Biomedical Department, NIT Raipur

10/11/09

Problem of Conflict Resolution 8

When there are more then one rule that can be fired in a

situation and the rule interpreter can not be decide which is to be fired, what is the order of triggering and whether to apply it .

Some Resolution Strategies: 1) Perform the first. 2)Sequencing techniques. 3)Perform the most specific. 4)Most recent policy.

Biomedical Department, NIT Raipur

10/11/09

CONTROL STRATEGIES 9

Requirements of control strategies: 1. It should cause motion. 2. It should be systematic.

Biomedical Department, NIT Raipur

10/11/09

Two types 10

Forward chaining:- starts with the data available and uses the inference rules to conclude more data until a desired goal is reached.  An inference engine using forward chaining searches the inference rules until it finds one in which the if-clause is known to be true.  It then concludes the then-clause and adds this information to its data.  It would continue to do this until a goal is reached. Because the data available determines which inference rules are used.  this method is also called data driven Biomedical Department, NIT Raipur

10/11/09

A Simple Example R1: IF hot AND smoky THEN fire R2: IF alarm_beeps THEN smoky R3: If fire THEN switch_on_sprinklers F1: alarm_beeps F2: hot

Biomedical Department, NIT Raipur

[Given] [Given]

10/11/09

A Simple Example R1: IF hot AND smoky THEN ADD fire R2: IF alarm_beeps THEN ADD smoky R3: If fire THEN ADD switch_on_sprinklers F1: alarm_beeps F2: hot

[Given] [Given]

F3: smoky F4: fire F5: switch_on_sprinklers

[from F1 by R2] [from F2, F4 by R1] [from F4 by R3]

A typical Forward Chaining example

Biomedical Department, NIT Raipur

12

10/11/09

Forward Chaining In a forward chaining system: Facts are held in a working memory Condition-action rules represent actions to take when specified facts occur in working memory. Typically the actions involve adding or deleting facts from working memory. facts Inference Engine

Working Memory facts

rules

facts User Biomedical Department, NIT Raipur

Rule Base 13

10/11/09

Forward Chaining Algorithm (I) Collect the rule whose condition matches a fact in WM. Do actions indicated by the rule (add facts to WM or delete facts from WM) Until problem is solved or no condition match

Biomedical Department, NIT Raipur

14

10/11/09

15

Backward chaining:starts with a list of goals and works backwards to see if there is data which will allow it to conclude any of these goals.  An inference engine using backward chaining

would search the inference rules until it finds one which has a then-clause that matches a desired goal. If the if-clause of that inference rule is not known to be true, then it is added to the list of goals. Biomedical Department, NIT Raipur

10/11/09

Backward Chaining Same rules/facts may be processed differently, using backward chaining interpreter Backward chaining means reasoning from goals back to facts. The idea is that this focuses the search. Checking hypothesis Should I switch the sprinklers on?

Biomedical Department, NIT Raipur

16

10/11/09

Backward Chaining Algorithm To prove goal G: If G is in the initial facts, it is proven. Otherwise, find a rule which can be used to conclude G, and try to prove each of that rule's conditions.

Biomedical Department, NIT Raipur

17

10/11/09

Example Rules: R1: IF hot AND smoky THEN fire

alarm_beeps

R2: IF alarm_beeps THEN smoky R3: If fire THEN switch_on_sprinklers Facts: hot

smoky

F1: hot F2: alarm_beeps Goal: Should I switch sprinklers on?

fire

switch_on_sprinklers Biomedical Department, NIT Raipur

18

10/11/09

Forward vs Backward Chaining Depends on problem, and on properties of rule set. If you have clear hypotheses, backward chaining is likely to be better. Goal driven Diagnostic problems or classification problems Medical expert systems Forward chaining may be better if you have less clear hypothesis and want to see what can be concluded from current situation. Data driven Synthesis systems Design / configuration

Biomedical Department, NIT Raipur

19

10/11/09

Forward-chaining Example (A,B,E, and D are 20given)  If Y and D then Z  If X and B and E then Y  If A then X  If C then L  If L and M then N A

X

B C

Y L

Z

D E Biomedical Department, NIT Raipur

10/11/09

Backward Chaining Example 21

 If Y and D then Z  If X and B and E then Y  If A then X  If C then L  If L and M then N A B C

X B

Y

Z

E

D E Department, NIT Raipur Biomedical

D 10/11/09

22

LECTURE 4

Biomedical Department, NIT Raipur

10/11/09

One Systematic Control Strategy for Water Jug Problem : Breadth First Search Technique 23

Construct a tree with initial state as root & then

generate all the offspring of the root by applying each of the applicable rules to initial state. (0,0)

(4,0)

Biomedical Department, NIT Raipur

(0,3)

10/11/09

Similarly………………. 24

For each leaf node , generate all its successors by

applying all the rules that are appropriate. (0,0)

(4,0)

(4,3)

(0,0)

(0,3)

(1,3)

(4,3)

(0,0)

(3,0)

Continue this to reach goal state. Biomedical Department, NIT Raipur

10/11/09

DEPTH FIRST SEARCH 25

(0,0)

(4,0)

(4,3)

Biomedical Department, NIT Raipur

10/11/09