UNIT I

INTRODUCTION
Introduction to Artificial Intelligence-Search-Heuristic Search-A* algorithm-Game Playing- Alpha-
Beta Pruning-Expert systems-Inference - Rules-Forward Chaining and Backward Chaining- Genetic
Algorithms.

Introduction to AI

Artificial Intelligence:
Artificial Intelligence is the ability of a computer to act like a human being.
• Artificial intelligence systems consist of people, procedures, hardware, software, data, and
knowledge needed to develop computer systems and machines that demonstrate the
characteristics of intelligence
Concept of Rationality
A system is rational if it does the “right thing”. Given what it knows.
– System that think like human
– System that think rationally
– System that act like human
– System that act rationally
Types of AI Tasks
(i) Mundane Tasks
• Perception
• Speech
• Natural Language understanding, generation and translation
• Common-sense Reasoning
• Robot Control
(ii) Formal Tasks
• Games
• Mathematics
(iii) Expert Tasks
• Engineering
• Medical Diagnosis
• Rule based systems - if (conditions) then action

Agents and environments

An agent is anything that can be viewed as perceiving its environment through sensors and acting
upon that environment through actuators
Human Sensors: eyes, ears, and other organs for sensors.
Human Actuators: hands, legs, mouth, and other body parts.
Robotic Sensors: Mic, cameras and infrared range finders for sensors
Robotic Actuators: Motors, Display, speakers etc

PEAS: Performance, Measure, Environment, Actuators, Sensors

Consider, e.g., the task of designing an automated taxi driver:
– Performance measure - Safe, fast, legal, comfortable trip, maximize profits
– Environment - Roads, other traffic, pedestrians, customers
– Actuators - Steering wheel, accelerator, brake, signal, horn
– Sensors - Cameras, sonar, speedometer, GPS, odometer, engine sensors, keyboard

1
 Search Algorithms

• Uninformed or blind search strategies uses only the information available in the problem
definition
• Informed or heuristic search strategies use additional information. Heuristic tells us
approximately how far the state is from the goal state. Heuristics might underestimate or
overestimate the merit of a state.
Generate and test

The generate and test is the simplest form of all heuristic search methods
Algorithm
1. Generate a possible solution. For some problems, this means generating a particular point in
the problem space. For others, it means generating a path from a start state.
2. Test to see if this is actually a solution by comparing the chosen point or the endpoint of the
chosen path to the set of acceptable goal states.
3. If a solution has been found, quit. Otherwise, return to step 1.
Example - Traveling Salesman Problem (TSP)
• Traveler needs to visit n cities.
• Know the distance between each pair of cities.
• Want to know the shortest route that visits all the cities once.

• TSP - generation of possible solutions is done in lexicographical order of cities:

2
 1. A - B - C - D
2. A - B - D - C
3. A - C - B - D
4. A - C - D - B
5. A - D - C - B
6. A - D - B - C
• n=80 will take millions of years to solve exhaustively!

Best-First Search
Best first search combines the advantages of Breadth-First and Depth-First searches.
– DFS: follows a single path, don’t need to generate all competing paths.
– BFS: doesn’t get caught in loops or dead-end-paths.
• Best First Search: explore the most promising path seen so far. Nodes are ordered and
expanded using evaluation function. The best evaluation function is expanded first.
• Two types of evaluation function
– Greedy Best First Search
– A* search

(i) Greedy Best First Search

Greedy best first search minimize the estimated cost to reach the goal. It always expand the node that
appears to be closed to the goal.
Evaluation function
f(n)=h(n)
• h(n) = estimated cost of the cheapest path from the state at node n to a goal state

A-S-F-B 140+99+211=450

3
Algorithm
1. Start with OPEN containing just the initial state.
2. Until a goal is found or there are no nodes left on OPEN do
(a) Pick the best node on OPEN
(b) Generate its successors
(c) For each successor do
(i) If it has not been generated before, evaluate it, add it to OPEN, and record its
parent.
(ii) If it has been generated before, change the parent if this new path is better than
the previous one. In that case, update the cost of getting to this node and to any
successors that this node may already have.
Performance Analysis
• Time and space complexity – O(bm)
• Optimality – no
• Completeness - no

(ii) A* search Algorithm

Evaluation function
f(n) = h(n)+g(n)
• f(n) = cost of the cheapest solution through n
• g(n) = actual path cost from the start node to node n
Algorithm
1. Create a priority queue of search nodes (initially the start state). Priority is determined by
the function f )
2. While queue not empty and goal not found:
(a) Get best state x from the queue.
(b) If x is not goal state:
(i) generate all possible children of x (and save path information with each node).
(ii) Apply f to each new node and add to queue.
(iii) Remove duplicates from queue (using f to pick the best).

A-S-R-P-B 140+80+97+101=418
Performance Analysis
• Time complexity – depends on heuristic function and admissible heuristic value
• space complexity – O(bm)
• Optimality – yes (locally finite graphs)
• Completeness – yes (locally finite graphs)

Hill Climbing
In computer science, hill climbing is an iterative local search algorithm that starts with an arbitrary
solution to a problem, then attempts to find a better solution by incrementally changing a single
element of the solution.

4
Algorithm
1. Evaluate the initial state.
2. Loop until a solution is found or there are no new operators left to be applied:
- Select and apply a new operator
- Evaluate the new state:
goal  quit
better than current state  new current state
Example: 8 puzzle problem
Here, h(n) = the number of misplaced tiles (not including the blank), the Manhattan Distance
heuristic helps us quickly find a solution to the 8-puzzle.

Advantages of Hill Climbing

• Estimates how far away the goal is.
• Is neither optimal nor complete.
• Can be very fast.

Steepest-Ascent Hill Climbing (Gradient Search)

The steepest ascent hill climbing technique considers all the moves from the current state. It
selects the best one as the next state.

Algorithm
1. Evaluate the initial state.
2. Loop until a solution is found or a complete iteration produces no change to current state:
- SUCC = a state such that any possible successor of the
current state will be better than SUCC (the worst state).
- For each operator that applies to the current state, evaluate
the new state:
goal  quit
better than SUCC  set SUCC to this state
- SUCC is better than the current state  set the current state to SUCC.

Disadvantages
• Local maximum
A state that is better than all of its neighbours, but not better than some other states far away.

5
 • Plateau
A flat area of the search space in which all neighbouring states have the same value.

• Ridge
The orientation of the high region, compared to the set of available moves, makes it impossible to
climb up. However, two moves executed serially may increase the height.

There are some ways of dealing with these problems.

• Backtrack to some earlier node and try going in a different direction. This is a good way of
dealing with local maxima.
• Make a big jump to try to get in a new section of the search space. This is particularly a good
way of dealing with plateaus.
• Apply two or more rules before doing a test. This corresponds to moving in several directions
at once. This is particularly a good strategy for dealing with ridges.

Constraint Satisfaction Problem (CSP) – search

• Search procedure that operates in a space of constraint sets.
• Initial state - contains the constraints that are originally given in the problem description.
• Goal State - any state that has been constrained "enough," where "enough" must be defined
for each problem
• Example: Crypt arithmetic, graph coloring
CSP – Example - Crypt arithmetic
Statement: the aim is to find a substitution of digits for letters such that the resulting sum is
arithmetically correct, each letter stand for a different digit.
• Given : FORTY+ TEN+ TEN=SIXTY
• 29786 + 850+ 850 = 31486
• F=2, O=9, R=7, T=8, Y=6, E=5, N=0
Constraint satisfaction is a two-step process
• Constraints are discovered and propagated as far as possible throughout the system.
Then, if there is still not a solution, search begins.
• A guess about something is made and added as a new constraint. Propagation can
then occur with this new constraint, and so forth
Algorithm
1. Propagate available constraints. To do this, first set OPEN to the set of all objects that must
have values assigned to them in complete solution. Then do until an inconsistency is detected
or until OPEN is empty:
(a) Select an object OB from OPEN. Strengthen as much as possible the set of
constraints that apply to OB.
(b) If this set is different from the set that was assigned the last time OB was
examined or if this is the first time OB has been examined, then add to OPEN all
objects that share any constraints with OB.
(c) Remove OB from OPEN.
2. If the union of the constraints discovered above defines a solution, then quit and report the solution.
3. If the union of the constraints discovered above defines a contradiction, then return failure.
4. If neither of the above occurs, then is necessary to make a guess at something inorder to proceed.
To do this, loop until a solution is found or all possible solutions have been eliminated.

6
 (a) Select an object whose value is not yet determined and select a way of
strengthening the constraints on the object.
(b) Recursively invoke constraint satisfaction with the current set of constraints augmented by
the strengthening constraint just selected.
Example
Given : CROSS + ROADS = DANGER
Goal state: The digits to the letter should be assigned in such a manner that the sum is satisfied.

Graph Coloring
Given the task of coloring each region either red, green, or blue in such a way that no
neighboring regions have the same color. To formulate this as a CSP, we define the variables to be the
regions: WA, NT, Q, NSW , V , SA, and T.
The domain of each variable is the set {red, green, blue}. The constraints require neighboring
regions to have distinct colors; for example, the allowable combinations for WA and NT are the pairs
{(red, green),(red, blue),(green, red),(green, blue),(blue, red),(blue, green)} . (The constraint can also
be represented more succinctly as the inequality WA 6= NT, provided the constraint satisfaction
algorithm has some way to evaluate such expressions).

7
 There are many possible solutions, such as {WA = red, NT = green, Q = red, NSW = green, V
= red, SA = blue, T = green}. CONSTRAINT GRAPH. The nodes of the graph correspond to
variables of the problem and the arcs correspond to constraints. Treating a problem as a CSP confers
several important benefits. Because the representation of states in a CSP conforms to a standard
pattern—that is, a set of variables with assigned values—the successor function and goal test can
written in a generic way that applies to all CSPs. Furthermore, we can develop effective, generic
heuristics that require no additional, domain-specific expertise. Finally, the structure of the constraint
graph can be used to simplify the solution process, in some cases giving an exponential reduction in
complexity.
Problem Reduction
 Each sub-problem is solved and final solution is obtained by combining solutions of each sub-
problem.
 Decomposition generates arcs that we will call AND arc.

8
 OR graph
An OR graph consists entirely of OR nodes, and in order to solve the problem represented by
it, you only need to solve the problem represented by one of his children
(Eight Puzzle Tree example).

AND GRAPH
An AND graph consists entirely of AND nodes, and in order to solve a problem represented by it,
you need to solve the problems represented by all of his children (Hanoi towers example).

AND/OR Graphs
AND-OR graph is useful for certain problems where
• The solution involves decomposing the problem into smaller problems. We then solve these
smaller problems
• An AND/OR graph consists of both AND nodes and OR nodes.
Acquire TV

Steal TV Earn Money Buy TV

Example: Water Jug Problem

You are given two jugs, a 4-gallon one and a 3-litre one. Neither have any measuring
markers on it. There is a pump that can be used to fill the jugs with water. How can you get exactly 2
gallons of water into 4-gallon jug. Let x and y be the amounts of water in 4-gallon and 3-gallon Jugs
respectively. (x,y) refers to water available at any time in 4-gallon, 3-gallon jugs.
o The start state is (0,0)
o The goal state is (2,n)

9
 Gallons in the Gallons in the Description
4-gallon jug 3-gallon jug

0 0 Initial State
0 3 Fill the 3-gallon jug
3 0 Transfer all water from 3-gallon jug in to 4-gallon jug
3 3 Fill the 3-gallon jug
4 2 Transfer water from 3-gallon jug in to 4-gallon jug until the 4
gallon jug is full
0 2 Empty the 4-gallon jug
2 0 Transfer 2-gallon water from the 3-gallon jug in to 4-gallon jug

Uninformed Search Algorithm

Breadth First Search
Breadth-First Search algorithm is a graph traversing technique, where you select a random initial node
(source or root node) and start traversing the graph layer-wise in such a way that all the nodes and
their respective children nodes are visited and explored.

Algorithm:
1. Create a variable called NODE-LIST and set it to initial state
2. Until a goal state is found or NODE-LIST is empty do
a. Remove the first element from NODE-LIST and call it E. If NODE-LIST
was empty, quit
b. For each way that each rule can match the state described in E do:
i. Apply the rule to generate a new state
ii. If the new state is a goal state, quit and return this state
iii. Otherwise, add the new state to the end of NODE-LIST
Advantages of BFS
• BFS will not get trapped exploring a blind alley. This contrasts with DFS, which may follow
a single unfruitful path for a very long time, perhaps forever, before the path actually
terminates in a state that has no successors.
• If there is a solution, BFS is guaranteed to find it.
• If there are multiple solutions, then a minimal solution will be found.

Depth First Search

Depth First Search (DFS) algorithm traverses a graph in a depth-ward motion and uses a stack to
remember to get the next vertex to start a search, when a dead end occurs in any iteration.
1. If the initial state is a goal state, quit and return success
10
 2. Otherwise, do the following until success or failure is signaled:
a. Generate a successor, E, of initial state. If there are no more successors, signal failure.
b. Call Depth-First Search, with E as the initial state
c. If success is returned, signal success. Otherwise continue in this loop.

Advantages of Depth-First Search

• DFS requires less memory since only the nodes on the current path are stored.
• By chance, DFS may find a solution without examining much of the search space at all.

ITERATIVE DEEPENING

Depth first search was efficient in terms of space but required some cutoff depth in order to
force backtracking when a solution was not found. Breadth first search was guaranteed to find the
shortest solution path but required inordinate amount of space because all leaf nodes had to be kept in
memory. An algorithm called depth first iterative deepening (DFID) combines the best aspects of
depth-first and breadth-first search.

To avoid the infinite depth problem of DFS, we can decide to only search until depth L, i.e.
we don’t expand beyond depth L. This is called Depth-Limited Search. Suppose if the solution is
deeper than L, then increase L iteratively. This is known as Iterative Deepening Search. This iterative
deepening search inherits the memory advantage of Depth-First search.

Iterative deepening search L=1

Iterative deepening search L=2

11
Iterative deepening search L=3

Algorithm
1. Set SEARCH-DEPTH=1.
2. Conduct a depth-first search to a depth of SEARCH-DEPTH. If a solution path is found, then return
it.
3. Otherwise, increment SEARCH-DEPTH by 1 and go to step2.

Disadvantage
Iterative deepening looks inefficient because so many states are expanded multiple times. In
practice this is not that bad, because by far most of the nodes are at the bottom level.
 For a branching factor b of 2, this might double the search time.
 For a branching factor b of 10, this might add 10% to the search time.
Advantage
 Avoids the problem of choosing cutoffs without sacrificing efficiency.
 DFID is the optimal algorithm for uniformed search.
Performance Analysis
Completeness - Yes
Time Complexity- (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd)
Space Complexity - O(bd)
Optimality - Yes, if step cost = 1 or increasing function of depth.

ITERATIVE DEEPENING A*
1. Set THRESHOLD=the heuristic evaluation of the start state.
2. Conduct a depth-first search, pruning any branch when its total cost function (g+h) exceeds a
THRESHOLD. If a solution path is found during the search, return it.
3. Otherwise, Increment THRESHOLD by the minimum amount. It was exceeded during the previous
step, and the go to step 2.
Iterative Deepening A* is guaranteed to find optimal solution, provided that h is a n
admissible heuristic. Because of its depth-first search technique, IDA* is very efficient with respect to
space. IDA* is the first heuristic search algorithm to find optimal paths within reasonable time and
space constraints.

UNIFORM COST SEARCH

Uniform Cost Search is the best algorithm for a search problem, which does not involve the
use of heuristics. It can solve any general graph for optimal cost. Uniform Cost Search as it
sounds searches in branches which are more or less the same in cost.

12
Initialization: { [ S , 0 ] }
Iteration1: { [ S->A , 1 ] , [ S->G , 12 ] }
Iteration2: { [ S->A->C , 2 ] , [ S->A->B , 4 ] , [ S->G , 12] }
Iteration3: { [ S->A->C->D , 3 ] , [ S->A->B , 4 ] , [ S->A->C->G , 4 ] , [ S->G , 12 ] }
Iteration4: { [ S->A->B , 4 ] , [ S->A->C->G , 4 ] , [ S->A->C->D->G , 6 ] , [ S->G , 12 ] }
Iteration5: { [ S->A->C->G , 4 ] , [ S->A->C->D->G , 6 ] , [ S->A->B->D , 7 ] , [ S->G , 12 ] }
Iteration6 gives the final output as S->A->C->G.

Algorithm
1. Insert the root into the queue
2. While the queue is not empty
a) Dequeue the maximum priority element from the queue
(If priorities are same, alphabetically smaller path is chosen)
b) If the path is ending in the goal state, print the path and exit
Else
c) Insert all the children of the dequeued element, with the cumulative costs as priority

Advantages:
o Uniform cost search is optimal because at every state the path with the least cost is chosen.
Disadvantages:
o It does not care about the number of steps involve in searching and only concerned about path
cost. Due to which this algorithm may be stuck in an infinite loop.

GAME PLAYING
Early work on AI focused on formal tasks such as game playing and theorem proving. In
game playing to select the next state, search technique is used. There were two reasons that games
appeared to be a good domain in which to explore machine intelligence.

(i) Games provide a structured task in which it is easy to measure success or failure
(ii) They did not require large amount of knowledge. They apply a straight forward search
and provide a solution from the starting state to a winning state

MINIMAX SEARCH ALGORITHM

It is a depth first, depth limited search procedure. The idea is to start at the current
position and uses a plausible move generator to generate the set of possible successor positions. Apply
static evaluation function to those positions and simply choose the best one. After doing so, we can
back that value up to the starting position to represent the evaluation of it. We assume that the static
evaluation function returns large values to indicate good situation so our goal is to maximize the value
of the static function for the next board position
Principle of Minimax
Given two players(x,y)- the chance of one person winning the game is possible at the
expense of other person losing the game.

13
Two ply search

The alternation of maximizing and minimizing at alternate ply when evaluations being pushed back
up correspond to the opposing strategies of two plays and gives this method a name minimax
procedure.

The computer is Max.

The opponent is Min.

ALPHA BETA CUT OFF

MINIMAX searches the entire tree, even if in some cases the rest can be ignored. But,
this alpha beta cutoff returns appropriate minimax decision without exploring entire tree. The
minimax search procedure is slightly modified by including branch and bound strategy one for each
players. This modified strategy is known as alpha beta pruning. It requires maintenance of two
threshold values, one representing a lower bound on the value that a maximizing node may ultimately
be assigned (alpha) and another representing upper bound on the value that a minimizing node may be
assigned (beta).
Here is an example of Alpha-Beta search:

14
Another example

Algorithm: MINIMAX-A-B(position, depth, player, Use-Thresh, Pass-Thresh)

1. If DEEP-ENOUGH (position, depth), then return structure.
VALUE=STATIC (position, player)
PATH=Nil
This indicates that there is no path from this node.
2. Otherwise generate one more ply of the tree by calling the function MOVE-GEN (position, player)
and setting SUCCESSORS to the list it returns.
3. If SUCCESSORS is empty, then there are no moves to be done, so return the same structure that
would have been returned by DEEP_ENOUGH.
4. If SUCCESSORS is not empty, then examine each element in turn and keep track of the best one.
This is done as follows.
For each element SUCC of SUCCESSORS do the following
(a) Set RESULT-SUCC to MINIMAX-A-B (SUCC, Depth+1, OPPOSITE (player), Pass-
Thresh, Use-Thresh)
(b) Set NEW-VALUE to VALUE (RSULT-SUCC)
(c) If NEW-VALUE > Pass-Thresh, then we have found a successor that is better than
any that have been examined so far. Record this by doing the following.
(i) Set Pass-Thresh to NEW VALUE.
(ii) The best known path is now from CURRENT to SUCC and then on the appropriate
path down from SUCC as determined by the recursive call to MINIMAX-A-B. So set BEST-PATH to
the result of attaching SUCC to the front of PATH (RESULT-SUCC).
5. If Pass-Thresh is not better than Use-Thresh, then we should stop examining this branch. But, both
thresholds and values have been inverted. So, if Pass-Thresh>=Use-Thresh, then return immediately
with the value.
VALUE = Path-Thresh
15
 PATH = BEST-PATH
5. So return the structure.
VALUE = Path-Thresh
PATH = BEST-PATH
Performance analysis
o Guaranteed to compute the same root value as MINIMAX.
o If we choose a best successor first, the need to examine O(bm/2) nodes.
o If we choose a random successor, the need to examine O(b3m/4) nodes.

PRODUCTION BASED SYSTEM

Production systems are also known as rule based system.
A system whose knowledge base is represented as a set of rules and facts is called rule based
system. A rule based system consists of a collection of IF-THEN rules, a collection of facts, and some
interpreter controlling the application of the rules given the facts.
Production rules
– IF-THEN expressions
– IF some condition(s) exists THEN perform some action(s)
Condition-action pair
– Condition: pattern that determines when a rule may be applied to problem instance
– Action: defines associated problem solving step
Antecedent – Consequent
– IF <antecedent> THEN <consequent>
When the antecedent part is NULL, the rule becomes fact.
Rule can have multiple antecedents
Conjunction AND
IF <antecedent0> AND <ante cedent1> … AND <antecedentn>
THEN <consequent>
Disjunction OR
IF <antecedent0> OR <antecedent1> … OR <antecedentn>
THEN <consequent>
Combination of both
IF <antecedent0> AND <antecedent1> … AND <antecedentn>
OR <antecedent0> OR <antecedent1> … OR <antecedentn>
THEN <consequent>
Consequents can also have multiple clauses
IF <antecedent> THEN <consequent0>, <consequent1>,
…<consequentn-1>, <consequentn>
Triggered and fired rules
A rule is triggered when all the antecedents evaluate to true.
A rule is fired when the action stated in the consequent part or the inference related to the
consequent part is inferred or taken.

Production based system

16
Inference machine is a machine that implements strategies to utilize the knowledge base and derive
new conclusions from it.
Match
Inference machine is comparing the fact base and the rule base and find some rules are matching.
These set of rules are passed to the next phase, conflict resolution.
Conflict resolution phase
 Rule 1:IF the ‘traffic light’ is green THEN the action is go
 Rule 2:IF the ‘traffic light’ is red THEN the action is stop
 Rule 3:IF the traffic light’ is red THEN the action is go
We have two rules, Rule 2 and Rule 3, with the same IF part. Thus both of them can be set to fire
when the condition part is satisfied. These rules represent a conflict set. The inference engine must
determine which rule to fire from such a set. A method for choosing a rule to fire when more than one
rule can be fired in a given cycle is called conflict resolution.
The conflict resolution mechanisms are
– Rule Ordering
– Recency
– Specificity
– Refraction
i) Recency
 Rules which use more recent facts are preferred.
 Working memory elements are time tagged indicating at what cycle each fact was added to
working memory.
 Focuses on single line of reasoning
ii) Specificity
 Rules which have greater number of conditions are therefore more difficult to satisfy, are
preferred to more general rules with fewer conditions.
 More specific rules are better because they take more of the data in to account.
iii) Refraction
 A rule should not be allowed to fire more than once on the same data.
 The executed rules are discarded from the conflict set.
 Prevents undesired loops
iv) Rule ordering
 Choose the first rule in the text ordered top to bottom
Alternative to conflict resolution
Meta rules reason about which rules should be considered for firing. They direct reasoning rather than
actually performing reasoning. Meta knowledge is knowledge about knowledge to guide search.
If conflict set contains any rule (c,a) such that c=”animal is mammal” THEN fire(c,a). This
example says meta knowledge encodes knowledge about how to guide search for solution.

Execute phase
The selected rule is fired in this phase. This phase also checks whether the goal is reached.
After every execution new fact will be added to the fact base.

17
Limitations of Rule-Based Representations

• Can be difficult to create

– the “knowledge engineering” problem
• Can be difficult to maintain
– in large rule-bases, adding a rule can cause many unforeseen interactions and effects
=> difficult to debug
• Many types of knowledge are not easily represented by rules
– uncertain knowledge: “if it is cold it will probably rain”
– information which changes over time
– procedural information (e.g. a sequence of tests to diagnose a disease)

INFERENCE MECHANISM
An inference is an idea or conclusion that's drawn from evidence and reasoning.
An Inference Engine is a tool from artificial intelligence.
Given a set of rules, there are essentially two ways to generate new knowledge
 Forward chaining
 Backward chaining

FORWARD CHAINING
Forward chaining is one of the two main methods of reasoning when using an inference engine and
can be described logically as repeated application of modus ponens. Forward chaining is a popular
implementation strategy for expert systems, business and production rule systems. Forward chaining
is also known as data driven approach. Forward chaining starts with the facts and see what rules apply.

Facts are held in the working memory (ie., contains the current state of the world). Rules represent the
action to be taken when specified facts occur in the working memory. The actions involve adding or
deleting facts from the working memory.

Algorithm: Forward chaining

i) Collect the rules whose conditions match facts in working memory.

ii) If more than one rule matches then
(a) Use conflict resolution strategy to select the rules.
iii) Do the actions indicated by the rules. ie add facts to working memory or delete facts from working
memory.
iv) Repeat these steps until the goal is reached or no condition match found.\

Example
Rule R1: IF hot and smoky THEN fire
Rule R2: IF alarm_beeps THEN smoky
Rule R3: IF fire THEN switch_on_sprinklers

Fact F1: alarm_beeps (Given)

Fact F2: hot (Given)

Inference
Rule R1: IF hot and smoky THEN fire
Rule R2: IF alarm_beeps THEN smoky
Rule R3: IF fire THEN switch_on_sprinklers

18
Fact F1: alarm_beeps (Given)
Fact F2: hot (Given)

Fact F3: smoky (Added)

Fact F4: fire (Added)
Fact F5: switch_on_sprinklers (Added)

Suppose that we know the facts A, B, C, D, E and the rules shown in the knowledge base to the left
What facts can we infer from this?

After inferring facts X, L, Y and Z there are no more rules that can be fired.
Properties of forward chaining
 All rules which can fire do fire.
 Can be inefficient, which lead to spurious rule firing, unfocussed problem solving.
 Set of rules that can fire known as conflict set.
 Decision about which rule to fire is conflict resolution.

19
 BACKWARD CHAINING

This is also called goal driven approach. A desired goal is placed in working memory,
inference cycle attempts to find evidence to prove it.
The knowledge base (rule base) is searched for rules that might lead to goal. If condition of such rule
matches fact in working memory then rule is fired and goal is proved.
Backward chaining means reasoning from goals to facts. Rules and facts are processed using
backward chaining interpreter.
Algorithm: Backward Chaining
i) Prove goal G.
ii) if G is the initial fact, it is proven.
iii) Otherwise, find a rule which can be used to conclude G, and try to prove each of the rules
conditions.
Example 1
Rule R1: IF hot and smoky THEN fire
Rule R2: IF alarm_beeps THEN smoky
Rule R3: IF fire THEN switch_on_sprinklers

Fact F1: alarm_beeps (Given)

Fact F2: hot (Given)

Goal: Should I switch_on_sprinklers

Suppose that we know the facts A, B, C, D, E and the rules shown in the knowledge base to
the left. Can we infer the fact Z?

Backward chaining inferred Z from the facts and rules that were available.
Advantages
 Most efficient to infer one particular fact.
 User may be asked to input additional facts

EXPERT SYSTEM-BASIC CONCEPTS

Expert System (ES) is a computer program that uses knowledge and inference procedures to solve
problems that are difficult enough to require human expertise for their solutions. Expert System
(ES) is an information system that is capable of mimicking human thinking and making
considerations during the process of decision-making

Need of Expert System

 An Expert System is built because of two factors: either to replace or to help an expert.
20
  Reducing operational costs. To hire an expert is costly.
 To replace a retiring or a leaving employee who is an expert.
 Help experts in their routine to improve productivity.
 Help experts in their more complex and difficult tasks
 An expert to obtain information needed by other experts who have forgotten about it or who
are too busy to search for it.
 Characteristics of knowledge and inference engines used by domain experts
 Time and money spent on the project.
Few Applications of Expert system
 ES in Remote sensing applications
 ES in management applications
 ES in Research & Development
 ES for business (Marketing)
 ES for Biologist
Advantages
• Increased productivity (find solutions much faster than humans).
• Availability of expertise (human experts can be at one place at a time).
• Can be used in dangerous environments (e.g. in space).
• Reuse of User Interface and Inference modules
• Level of programming skill needed is low.
• Faster and cheaper completion of project
Limitations
• Difficulty in engineering, especially acquiring the expertise.
• Mistrust by the users.
• Effective only in specific areas (areas of expertise)
The main areas of application of ES are (Waterman, 1986)
Interpretation — drawing high–level conclusions based on data.
Prediction — projecting probable outcomes.
Diagnosis — determining the cause of malfunctions, disease, etc.
Design — finding best configuration based on criteria.
Planning — proposing a series of actions to achieve a goal.
Monitoring — comparing observed behaviour to the expected behaviour.
Debugging and Repair — prescribing and implementing remedies.

Steps to Develop an Expert Systems

The process of ES development is iterative. Steps in developing the ES include −
Identify Problem Domain
 The problem must be suitable for an expert system to solve it.
 Find the experts in task domain for the ES project.
 Establish cost-effectiveness of the system.
Design the System
 Identify the ES Technology
 Know and establish the degree of integration with the other systems and databases.
 Realize how the concepts can represent the domain knowledge best.
Develop the Prototype
From Knowledge Base: The knowledge engineer works to −
 Acquire domain knowledge from the expert.
 Represent it in the form of If-THEN-ELSE rules.
Test and Refine the Prototype
 The knowledge engineer uses sample cases to test the prototype for any deficiencies in
performance.
 End users test the prototypes of the ES.
Develop and Complete the ES
 Test and ensure the interaction of the ES with all elements of its environment, including end
users, databases, and other information systems.
 Document the ES project well
 Train the user to use ES.

21
 ARCHITECTURE OF EXPERT SYSTEM

Expert System
..
Inference Engine
Special
Interfaces
Inference & Control

Human Case History

Expert Knowledge Acquisition
& Learning Module
Knowledge Base

Static database
User User Interface

Dynamic database
(working memory)

Explanation Module

Knowledge Base:
 Knowledge about problem domain in the form of static and dynamic databases.
 Static knowledge consists of rules and facts which is complied as a part of the system and
does not change during execution of the system.
 Dynamic knowledge consists of facts related to a particular consultation of the system.
− At the beginning of the consultation, the dynamic knowledge base often called
working memory is empty.
− As a consultation progresses, dynamic knowledge base grows and is used along with
static knowledge in decision making.
 Working memory is deleted at the end of consultation of the system.

Components of Knowledge Base

The knowledge base of an ES is a store of both, factual and heuristic knowledge.
 Factual Knowledge − It is the information widely accepted by the Knowledge Engineers and
scholars in the task domain.
 Heuristic Knowledge − It is about practice, accurate judgement, one’s ability of evaluation,
and guessing.

Inference Engine:
 It consists of inference mechanism and control strategy.
 Inference means search through knowledge base and derive new knowledge.
 It involve formal reasoning involving matching and unification similar to the one performed
by human expert to solve problems in a specific area of knowledge.
 Inference operates by using modus ponen rule.
 Control strategy determines the order in which rules are applied.
 There are mainly two types of control mechanism viz., forward chaining and backward
chaining.
To recommend a solution, the interface engine uses the following strategies −
 Forward Chaining
 Backward Chaining
Forward Chaining
22
 It is a strategy of an expert system to answer the question, “What can happen next?” Here,
the interface engine follows the chain of conditions and derivations and finally deduces the outcome.
It considers all the facts and rules, and sorts them before concluding to a solution. This strategy is
followed for working on conclusion, result, or effect. For example, prediction of share market status
as an effect of changes in interest rates.

Backward Chaining
With this strategy, an expert system finds out the answer to the question, “Why this
happened?” On the basis of what has already happened, the interface engine tries to find out which
conditions could have happened in the past for this result. This strategy is followed for finding out
cause or reason. For example, diagnosis of blood cancer in humans.

Knowledge Acquisition:
● Knowledge acquisition module allows system to acquire knowledge about the problem
domain.
● Sources of Knowledge for ES
− Text books, reports, case studies,
− Empirical data and
− Domain expert experience.
● Updating of Knowledge can be done using knowledge acquisition module of the system.
− Insertion,
− Deletion and
− Updation of existing knowledge

Steps in knowledge acquisition

1. Collect: (elicitation)
- Getting the knowledge out of the expert
- Most difficult step
- Lots of strategies
2. Interpret: Review collected knowledge, organize, and filter
3. Analyze:
- Determining types of knowledge, conceptual relationships
- Determining appropriate knowledge representations & inference structure
4. Design: Extracting more knowledge after using above principles

Experts involved in the knowledge acquisition process are domain expert, knowledge engineer
and system editor

 Domain Expert

Anyone can be considered a domain expert if he or she has deep knowledge and strong practical
experience in a particular domain. The area of the domain may be limited. In general, an expert
is a skilful person who can do things other people cannot.Eg: Doctor. Provides knowledge and
processes needed to solve problem. Domain expert must be available for hundreds of hours.

23
 Knowledge in the expert system ends up being the knowledge engineer’s understanding of the
domain, not the domain expert’s knowledge
 Knowledge Engineer

Knowledge engineers are involved with validation and verification.

Validation is the process of ensuring that something is correct or conforms to a certain
standard. A knowledge engineer is required to carry out data collection and data entry, but they
must use validation in order to ensure that the data they collect, and then enter into their systems,
fall within the accepted boundaries of the application collecting the data.
It is important that a knowledge engineer incorporates validation procedures into their
systems within the program code. After the knowledge-based system is constructed, it can be
maintained by the domain expert
 System Editor

Knowledge base editor which help the expert or knowledge engineer to easily update and
check the knowledge base .

Case History
● Case History stores the file created by inference engine using the dynamic database created at
the time of consultation.
● Useful for learning module to enrich its knowledge base.
● Different cases with solutions are stored in Case Base system.
● These cases are used for solving problem using Case Base Reasoning (CBR).
Explanation Module
● Most expert systems have explanation facilities that allow the user to ask the system why it
asked some question, and how it reached to conclusion.
● It contains 'How' and 'Why' modules attached to it.
− The sub-module ‘How’ tells the user about the process through which system has
reached to a particular solution
− ‘Why' sub-module tells that why is that particular solution offered.
● It explains user about the reasoning behind any particular problem solution.
● Questions are answered by referring to the system goals, the rules being used, and any
existing problem data.
User Interfaces:

Allows user to communicate with system in interactive mode and helps system to create working
knowledge for the problem to be solved. The explanation may appear in the following forms −
 Natural language displayed on screen.
 Verbal narrations in natural language.
 Listing of rule numbers displayed on the screen.
Dialogue Module (User Interface)

System Do you have fever?

User Yes
System Do you have bad throat?
User No
System Do you have cough?
User Yes
System Are you suffering from running nose?
User Yes
System Are you suffering from headache?
User No

Special Interfaces:
● It may be used for specialized activities such as handling uncertainty in knowledge.
● This is a major area of expert systems research that involves methods for reasoning with
uncertain data and uncertain knowledge.
● Knowledge is generally incomplete and uncertain.
● To deal with uncertain knowledge, a rule may have associated with it a confidence factor or a
weight.
24
 ● The set of methods for using uncertain knowledge in combination with uncertain data in the
reasoning process is called reasoning with uncertainty.

GENETIC ALGORITHM

A genetic algorithm is a search heuristic that is inspired by Charles Darwin’s theory of natural
evolution based on ‘survival of the fittest’. It is a global search method for finding the global optimal
solution from a complicated search spaces. According to this mechanism, the species with optimal
fitness will survive to leave ancestors and continues to populate the world.

1. Initialization of Population
Population is the set of solutions called individuals. The individual is built out of
chromosomes. A chromosome contains genes. Each gene contains a parameter of problem represented
by the whole chromosome.
In genetic representation and initialization of population, instead of starting from a single
solution within the search space, genetic algorithms are initialized with a population of solution. They
are usually random and will be spread throughout the search space. In genetic algorithm, each
possible solution is represented by an individual of population called chromosome.

Initialize the population

Assign fitness to each individual

Selection Operation

Crossover Operation

Mutation Operation

Assign fitness to offspring

Add offspring into
the population pool
Yes
Fitness of offspring is
greater Elitism

No
Discard the offspring

No Termination
Condition reached?

Yes

Stop

25
2. Fitness Function
Fitness function accurately reflects the suitability of a solution. The fitness function
assigns a score to the possible solution. The score is a numerical value that represents, how well the
particular solution solves the problem. The task of the GA is to discover solutions that have high
fitness values among the set of all possible solutions.
Genetic algorithms are usually suitable for solving maximization problems. Minimization
problems are transformed in to maximization problem by some suitable transformation. In general,
fitness functions F(x) is first derived from the objective function and is used in successive genetic
operations.
Consider the following transformations
F(x) = f(x) for maximization problem
F(x) = 1/f(x) for minimization problem, if f(x) ≠ 0

3. Selection Operation
Selection or reproduction operation is usually the first operator applied on population.
Selection operation chooses two individuals from an existing population, according to the definition
of fitness. Individuals which are selected from the population pool are to be parents. According to
Darwin’s theory of survival of the fittest, the best one should survive and create new offspring. A
selection operation in genetic algorithm is a process that helps to select better individuals in the
population for the mating pool.
The various methods for selecting the individual from the population pool for cross-over are
i.Roulette wheel selection
ii.Truncation selection
iii.Tournament selection
iv.Rank selection
i. Roulette wheel selection
The commonly used selection operator is the proportionate operator, where, an individual
is selected from the population pool with a probability proportional to the fitness. This selection
procedure is easy to implement. However, it does not guarantee that all selected individuals are better
than the rejected individuals. Also, premature convergence of the search takes place.
ii. Truncation selection
In truncation selection, the candidate solutions are ordered by fitness and some proportion
p, (e.g. p=1/2, 1/3, etc.,) of the fittest individuals are selected and reproduced 1/p times. Truncation
selection will eliminate a fixed percentage of the weakest candidates.
iii. Tournament selection
The tournament selection strategy provides selection pressure by holding a tournament
competition among two individuals. The best individual (winner) from the tournament is the one with
highest fitness. The winner is then inserted in to the mating pool. The tournament competition is
repeated, until the mating pool for generating new offspring is filled. The mating pool comprising of
tournament winner has higher average population fitness. The steps for selection operation using
tournament selection are:
i. Select two random individuals p1 and p2.
ii. If the fitness value of p1>p2, assign parent = p1, else parent = p2.
iii. Repeat step 2, until the second parent is selected.
iv. Check if the two parents are equal. If equal, repeat step2 until the parents are not
equal.
iv. Rank selection
In ranking selection, first the individuals are ranked according to the fitness values. Those
with high fitness values will be ranked high and those with low fitness values will eventually have
lower ranks. Then, the individuals are selected with a probability that is proportional to the rank of the
individuals in the population. The steps for rank based selection are:
i. The individuals are sorted according to their fitness values.
ii. The individuals with best fitness are taken as the parents.
4. Cross-over operation
Cross-over operator is applied to the mating pool to create a better individual than the
individual in the population pool. The various types of cross-over operations are
i.Single point cross-over
ii.Multi-point cross-over
iii.Uniform cross-over

26
i. Single point cross-over
In single point cross-over, the cross-over point is selected randomly along the length of
the mated strings, and the bits next to the cross-over points are exchanged as shown in the Figure.
Parent1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 0 0
Parent2 0 0 0 1 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1

Child1 1 0 1 1 0 1 1 0 1 0 0 1 0 1 1 0 0 0 1 1
Child2 0 0 0 1 1 1 1 1 1 0 1 1 0 1 0 0 1 1 0 0
An example illustrating single point cross-over
ii. Multi-point cross-over
In multi-point cross-over, multiple cross-over points are chosen and the information
between the alternate pair of cross-over points is interchanged as shown in the Figure 4.7.
Parent1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 0 0
Parent2 0 0 0 1 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1

Child1 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 0 0 0 1 1
Child2 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0 0 1 1 0 0
An example illustrating multi-point cross-over
iii. Uniform cross-over
An extreme case of multi-point cross-over is the uniform cross-over operator. In a
uniform cross-over operator, each bit from either parent is selected with a probability of 0.5 and then
interchanged as shown in the Figure. The offspring produced contains a mixture of genes from each
parent. The number of effective cross-over point is not fixed, but averages to half the length of
chromosome.

Parent1 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 0 1 1 0 0
Parent2 0 0 0 1 1 1 1 1 1 0 0 1 0 1 1 0 0 0 1 1

Child1 1 0 0 1 0 1 1 1 1 0 0 1 0 1 1 0 0 0 0 1
Child2 0 0 1 1 1 1 1 0 1 0 1 1 0 1 0 0 1 1 1 0
An example illustrating uniform cross-over
5. Mutation Operation
Mutation alters one or more gene values in a chromosome from its initial state. In
mutation, the solution may change entirely from the previous solution. This method can lead to new
individuals in the problem space. Sometimes, this can lead to new and better results. The following
are the three types of mutation operations: (i) Flip Bit: randomly chooses the genome and inverts the
bits; (ii) Boundary: replaces the genome with either lower or upper bound randomly; and (iii) Uniform:
replaces the value of the chosen gene with a uniform random value selected between the user-
specified upper and lower bounds for that gene.
6. Elitism
The cross-over and mutation operation will destroy the best solution of the population
pool. Thus, elitism concept is used while adding/discarding an individual in to/from the population,
because it preserves few best solutions in the population pool. The elitism concept will allow some of
the better individuals from the current generation (without altering) to carry over to the next
generation while constructing a new population
7. Adding/Discarding the individual
This module in GA is used to check whether the offspring (child) produced is added in to
the population pool or discarded from the population pool. The fitness value of the child is compared
with the fitness value of the individuals in the population pool. The steps involved are:
i. Check if the fitness value of the child is greater than the fitness value of the individuals in
the population pool. If the condition is satisfied, go to step (ii); otherwise, discard the
child.
ii. Check whether the child is already in the population pool.

27
 a) If the child is not in the pool, remove the individual which has minimum fitness
value from the population pool and add the child in to the population pool.
b) If the child is already in the pool, discard the child.
iii. Repeat steps (i) to (ii) for the next child.
8. Convergence of genetic algorithm
Convergence criterion for the genetic algorithm is set based on the maximum number of
generations or elapsed time, predefined fitness value etc.

28