lOMoARcPSD|19189123

AI - Notes

btech (Guru Gobind Singh Indraprastha University)

Studocu is not sponsored or endorsed by any college or university

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)
 lOMoARcPSD|19189123

Artificial Intelligence
Unit – III
Games
Natural Language Processing
Vision and Speech Processing
Robotics
Exepert Systems
Theorem Proving
AI techniques – Search Knowledge, Abstraction

Games in Artificial Intelligence :

• Game Playing is an important domain of artificial intelligence.

• Games don’t require much knowledge; the only knowledge we need to provide is the
rules, legal moves and the conditions of winning or losing the game.
• Both players try to win the game.
• So, both of them try to make the best move possible at each turn.
• Searching techniques like BFS(Breadth First Search) are not accurate for this as the
branching factor is very high, so searching will take a lot of time. So, we need another
search procedures that improve –
• Generate procedure so that only good moves are generated.
• Test procedure so that the best move can be explored first.
• The most common search technique in game playing is Minimax search procedure. It is
depth-first depth-limited search procedure. It is used for games like chess and tic-tac-toe.

Adversarial Search :

• Adversarial search is a search, where we examine the problem which arises when we
try to plan ahead of the world and other agents are planning against us.

• There might be some situations where more than one agent is searching for the
solution in the same search space, and this situation usually occurs in game playing.

• The environment with more than one agent is termed as multi-agent environment,
in which each agent is an opponent of other agent and playing against each other.
Each agent needs to consider the action of other agent and effect of that action on
their performance.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

• Searches in which two or more players with conflicting goals are trying to explore
the same search space for the solution, are called adversarial searches, often known
as Games.

• Games are modeled as a Search problem and heuristic evaluation function, and these
are the two main factors which help to model and solve games in AI.

Types of Games in AI :

Deterministic Chance Moves

Perfect Information Chess, Checkers, Go, Backgammon, Monopoly

Othello

Imoerfect Information Battleships, Blind, Bridge, Poker, Scrabble,

Tic-Tac-Toe Nuclear War

Perfect Information

A game with the perfect information is that in which agents can look into the complete
board. Agents have all the information about the game, and they can see each other moves
also. Examples are Chess, Checkers, Go, etc.

Imperfect Information

If in a game agents do not have all information about the game and not aware with what's
going on, such type of games are called the game with imperfect information, such as tic-
tac-toe, Battleship, blind, Bridge, etc.

Deterministic Games

Deterministic games are those games which follow a strict pattern and set of rules for the
games, and there is no randomness associated with them. Examples are chess, Checkers,
Go, tic-tac-toe, etc

Non – Deterministic Games

Non-deterministic are those games which have various unpredictable events and has a factor
of chance or luck. This factor of chance or luck is introduced by either dice or cards. These
are random, and each action response is not fixed. Such games are also called as stochastic
games. Example: Backgammon, Monopoly, Poker, etc.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

Zero-Sum Game :
• Zero-sum games are adversarial search which involves pure competition.

• In Zero-sum game each agent's gain or loss of utility is exactly balanced by the losses or
gains of utility of another agent.

• One player of the game try to maximize one single value, while other player tries to
minimize it.

• Each move by one player in the game is called as ply.

• Chess and tic-tac-toe are examples of a Zero-sum game.

Zero-sum game: Embedded thinking :

The Zero-sum game involved embedded thinking in which one agent or player is trying to figure
out:
• What to do.
• How to decide the move
• Needs to think about his opponent as well
• The opponent also thinks what to do
Each of the players is trying to find out the response of his opponent to their actions. This requires
embedded thinking or backward reasoning to solve the game problems in AI.

Formalization of the problem :

A game can be defined as a type of search in AI which can be formalized of the following elements:
• Initial state: It specifies how the game is set up at the start.

• Player(s): It specifies which player has moved in the state space.

• Action(s): It returns the set of legal moves in state space.

• Result(s, a): It is the transition model, which specifies the result of moves in the state space.

• Terminal-Test(s): Terminal test is true if the game is over, else it is false at any case. The
state where the game ends is called terminal states.

• Utility(s, p): A utility function gives the final numeric value for a game that ends in terminal
states s for player p. It is also called payoff function. For Chess, the outcomes are a win,
loss, or draw and its payoff values are +1, 0, ½.

Game tree :
A game tree is a tree where nodes of the tree are the game states and Edges of the tree are the moves
by players. Game tree involves initial state, actions function, and result Function.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

Min-Max Algorithm :
• Mini-max algorithm is a recursive or backtracking algorithm which is used in
decision-making and game theory.
• It provides an optimal move for the player assuming that opponent is also playing
optimally. Mini-Max algorithm uses recursion to search through the game-tree.
• Min-Max algorithm is mostly used for game playing in AI. Such as Chess, Checkers,
tic-tac-toe, go, and various tow-players game.
• This Algorithm computes the minimax decision for the current state.
• In this algorithm two players play the game, one is called MAX and other is called
MIN.
• Both Players of the game are opponent of each other, where MAX will select the
maximized value and MIN will select the minimized value.
• The minimax algorithm performs a depth-first search algorithm for the exploration of
the complete game tree.
• The minimax algorithm proceeds all the way down to the terminal node of the tree,
then backtrack the tree as the recursion.

Working

• The working of the minimax algorithm can be easily described using an example.
• Below we have taken an example of game-tree which is representing the two-player
game.
• In this example, there are two players one is called Maximizer and other is called
Minimizer.
• Maximizer will try to get the Maximum possible score, and Minimizer will try to get
the minimum possible score.
• This algorithm applies DFS, so in this game-tree, we have to go all the way through
the leaves to reach the terminal nodes.
• At the terminal node, the terminal values are given so we will compare those value
and backtrack the tree until the initial state occurs.
• Following are the main steps involved in solving the two-player game tree:

Step-1: In the first step, the algorithm generates the entire game-tree and apply the utility
function to get the utility values for the terminal states. In the below tree diagram, let's take
A is the initial state of the tree. Suppose maximizer takes first turn which has worst-case

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

initial value =- infinity, and minimizer will take next turn which has worst-case initial value
=+ infinity.

Step 2: Now, first we find the utilities value for the Maximizer, its initial value is -∞, so we
will compare each value in terminal state with initial value of Maximizer and determines the
higher nodes values. It will find the maximum among the all.
• For node D max(-1,- -∞) => max(-1,4)= 4
• For Node E max(2, -∞) => max(2, 6)= 6
• For Node F max(-3, -∞) => max(-3,-5) = -3
• For node G max(0, -∞) = max(0, 7) = 7

Step 3: In the next step, it's a turn for minimizer, so it will compare all nodes value with +∞,
and will find the 3rd layer node values.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

• For node B= min(4,6) = 4

• For node C= min (-3, 7) = -3

Step 4: Now it's a turn for Maximizer, and it will again choose the maximum of all nodes
value and find the maximum value for the root node. In this game tree, there are only 4
layers, hence we reach immediately to the root node, but in real games, there will be more
than 4 layers.
• For node A max(4, -3)= 4

That was the complete workflow of the minimax two player game.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

Properties of Mini-Max algorithm

• Complete- Min-Max algorithm is Complete. It will definitely find a solution (if exist), in the
finite search tree.

• Optimal- Min-Max algorithm is optimal if both opponents are playing optimally.

• Time complexity- As it performs DFS for the game-tree, so the time complexity of Min-
Max algorithm is O(bm), where b is branching factor of the game-tree, and m is the
maximum depth of the tree.

• Space Complexity- Space complexity of Mini-max algorithm is also similar to DFS which
is O(bm).

Limitation of the minimax Algorithm

• The main drawback of the minimax algorithm is that it gets really slow for complex games
such as Chess, go, etc.
• This type of games has a huge branching factor, and the player has lots of choices to decide.
• This limitation of the minimax algorithm can be improved from alpha-beta pruning.

Alpha-Beta Pruning :
• It is an optimization technique for the minimax algorithm.
• Tere is a technique by which without checking each node of the game tree we can
compute the correct minimax decision, and this technique is called pruning.
• This involves two threshold parameter Alpha and beta for future expansion, so it is
called alpha-beta pruning. It is also called as Alpha-Beta Algorithm.
• Alpha-beta pruning can be applied at any depth of a tree, and sometimes it not only
prune the tree leaves but also entire sub-tree.
• The two-parameter can be defined as:
▪ Alpha: The best (highest-value) choice we have found so far at any point
along the path of Maximizer. The initial value of alpha is -∞.
▪ Beta: The best (lowest-value) choice we have found so far at any point along
the path of Minimizer. The initial value of beta is +∞.
• The Alpha-beta pruning to a standard minimax algorithm returns the same move as
the standard algorithm does, but it removes all the nodes which are not really
affecting the final decision but making algorithm slow. Hence by pruning these
nodes, it makes the algorithm fast.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

Condition for Alpha-Beta Pruning

The main condition which required for alpha-beta pruning is:
α>=β

Key points about alpha-beta pruning

• The Max player will only update the value of alpha.

• The Min player will only update the value of beta.

• While backtracking the tree, the node values will be passed to upper nodes instead of values
of alpha and beta.

• We will only pass the alpha, beta values to the child nodes.

Working of Apha-Beta Pruning

Let's take an example of two-player search tree to understand the working of Alpha-beta
pruning
Step 1: At the first step the, Max player will start first move from node A where α= -∞ and β= +∞,
these value of alpha and beta passed down to node B where again α= -∞ and β= +∞, and Node B
passes the same value to its child D.

Step 2: At Node D, the value of α will be calculated as its turn for Max. The value of α is compared
with firstly 2 and then 3, and the max (2, 3) = 3 will be the value of α at node D and node value will
also 3.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

Step 3: Now algorithm backtrack to node B, where the value of β will change as this is a turn of
Min, Now β= +∞, will compare with the available subsequent nodes value, i.e. min (∞, 3) = 3,
hence at node B now α= -∞, and β= 3.

In the next step, algorithm traverse the next successor of Node B which is node E, and the values of
α= -∞, and β= 3 will also be passed.
Step 4: At node E, Max will take its turn, and the value of alpha will change. The current value of
alpha will be compared with 5, so max (-∞, 5) = 5, hence at node E α= 5 and β= 3, where α>=β, so
the right successor of E will be pruned, and algorithm will not traverse it, and the value at node E
will be 5.

Step 5: At next step, algorithm again backtrack the tree, from node B to node A. At node A, the
value of alpha will be changed the maximum available value is 3 as max (-∞, 3)= 3, and β= +∞,
these two values now passes to right successor of A which is Node C.
At node C, α=3 and β= +∞, and the same values will be passed on to node F.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

Step 6: At node F, again the value of α will be compared with left child which is 0, and max(3,0)=
3, and then compared with right child which is 1, and max(3,1)= 3 still α remains 3, but the node
value of F will become 1.

Step 7: Node F returns the node value 1 to node C, at C α= 3 and β= +∞, here the value of beta will
be changed, it will compare with 1 so min (∞, 1) = 1. Now at C, α=3 and β= 1, and again it satisfies
the condition α>=β, so the next child of C which is G will be pruned, and the algorithm will not
compute the entire sub-tree G.

Step 8: C now returns the value of 1 to A here the best value for A is max (3, 1) = 3. Following is
the final game tree which is the showing the nodes which are computed and nodes which has never
computed. Hence the optimal value for the maximizer is 3 for this example.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

Move Ordering in Alpha-Beta pruning:

The effectiveness of alpha-beta pruning is highly dependent on the order in which each node
is examined. Move order is an important aspect of alpha-beta pruning.
It can be of two types:
• Worst ordering: In some cases, alpha-beta pruning algorithm does not prune any of
the leaves of the tree, and works exactly as minimax algorithm. In this case, it also
consumes more time because of alpha-beta factors, such a move of pruning is called
worst ordering. In this case, the best move occurs on the right side of the tree. The
time complexity for such an order is O(bm).

• Ideal ordering: The ideal ordering for alpha-beta pruning occurs when lots of
pruning happens in the tree, and best moves occur at the left side of the tree. We
apply DFS hence it first search left of the tree and go deep twice as minimax
algorithm in the same amount of time. Complexity in ideal ordering is O(bm/2).

Rules to find good ordering:

Following are some rules to find good ordering in alpha-beta pruning:
• Occur the best move from the shallowest node.
• Order the nodes in the tree such that the best nodes are checked first.
• Use domain knowledge while finding the best move. Ex: for Chess, try order: captures first,
then threats, then forward moves, backward moves.
• We can bookkeep the states, as there is a possibility that states may repeat.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

Natural Language Processing :

• Natural Language Processing (NLP) refers to AI method of communicating with an
intelligent systems using a natural language such as English.
• Processing of Natural Language is required when you want an intelligent system like robot
to perform as per your instructions, when you want to hear decision from a dialogue based
clinical expert system, etc.
• The field of NLP involves making computers to perform useful tasks with the natural
languages humans use. The input and output of an NLP system can be −
▪ Speech
▪ Written Text
Components of NLP
There are two components :-
1. Natural Language Understading (NLU)
Understanding involves the following tasks −
• Mapping the given input in natural language into useful representations.
• Analyzing different aspects of the language.

2. Natural Language Generation (NLG)

It is the process of producing meaningful phrases and sentences in the form of natural
language from some internal representation.
It involves −
• Text planning − It includes retrieving the relevant content from knowledge base.
• Sentence planning − It includes choosing required words, forming meaningful
phrases, setting tone of the sentence.
• Text Realization − It is mapping sentence plan into sentence structure.
The NLU is harder than NLG.

Difficulties in NLU
NL has an extremely rich form and structure.
It is very ambiguous. There can be different levels of ambiguity −
• Lexical ambiguity − It is at very primitive level such as word-level.
• Syntax Level ambiguity − A sentence can be parsed in different ways.
• Referential ambiguity − Referring to something using pronouns. For example, Rima went
to Gauri. She said, “I am tired.” − Exactly who is tired?
• One input can mean different meanings.
• Many inputs can mean the same thing.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

NLP Terminology
• Phonology − It is study of organizing sound systematically.
• Morphology − It is a study of construction of words from primitive meaningful units.
• Morpheme − It is primitive unit of meaning in a language.
• Syntax − It refers to arranging words to make a sentence. It also involves determining the
structural role of words in the sentence and in phrases.
• Semantics − It is concerned with the meaning of words and how to combine words into
meaningful phrases and sentences.
• Pragmatics − It deals with using and understanding sentences in different situations and
how the interpretation of the sentence is affected.
• Discourse − It deals with how the immediately preceding sentence can affect the
interpretation of the next sentence.
• World Knowledge − It includes the general knowledge about the world.

Steps in NLP
There are general five steps −
• Lexical Analysis −
• It involves identifying and analyzing the structure of words.
• Lexicon of a language means the collection of words and phrases in a
language.
• Lexical analysis is dividing the whole chunk of text into paragraphs,
sentences, and words.
• Syntactic Analysis (Parsing) −
• It involves analysis of words in the sentence for grammar and
arranging words in a manner that shows the relationship among the
words.
• The sentence such as “The school goes to boy” is rejected by English
syntactic analyzer.

• Semantic Analysis −
• It draws the exact meaning or the dictionary meaning from the text.
• The text is checked for meaningfulness.
• It is done by mapping syntactic structures and objects in the task
domain.
• The semantic analyzer disregards sentence such as “hot ice-cream”.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

• Discourse Integration −
• The meaning of any sentence depends upon the meaning of the
sentence just before it.
• In addition, it also brings about the meaning of immediately
succeeding sentence.
• Pragmatic Analysis −
• During this, what was said is re-interpreted on what it actually meant.
• It involves deriving those aspects of language which require real
world knowledge.

Implementation Aspects of Syntactic Analysis

There are a number of algorithms researchers have developed for syntactic analysis, but we
consider only the following simple methods −
• Context-Free Grammar
• Top-Down Parser

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

1. Context-Free Grammar
It is the grammar that consists rules with a single symbol on the left-hand side of the rewrite rules.
Merit − The simplest style of grammar, therefore widely used one.
Demerits −
• They are not highly precise. For example, “The grains peck the bird”, is a syntactically
correct according to parser, but even if it makes no sense, parser takes it as a correct
sentence.
• To bring out high precision, multiple sets of grammar need to be prepared. It may require a
completely different sets of rules for parsing singular and plural variations, passive
sentences, etc., which can lead to creation of huge set of rules that are unmanageable.

2. Top-Down Parser
Here, the parser starts with the S symbol and attempts to rewrite it into a sequence of terminal
symbols that matches the classes of the words in the input sentence until it consists entirely of
terminal symbols.
These are then checked with the input sentence to see if it matched. If not, the process is started
over again with a different set of rules. This is repeated until a specific rule is found which describes
the structure of the sentence.
Merit − It is simple to implement.
Demerits −
• It is inefficient, as the search process has to be repeated if an error occurs.
• Slow speed of working.

Speech and Voice Recognition :

These both terms are common in robotics, expert systems and natural language processing.
Though these terms are used interchangeably, their objectives are different.

Speech Recognition Voice Recognition

The speech recognition aims at understanding and

The objective of voice recognition is to
comprehending WHAT was spoken.
recognize WHO is speaking.
It is used in hand-free computing, map, or menu
It is used to identify a person by analysing its
navigation.
tone, voice pitch, and accent, etc.
Machine does not need training for Speech
This recognition system needs training as it is
Recognition as it is not speaker dependent.
person oriented.
Speaker independent Speech Recognition systems Speaker dependent Speech Recognition systems
are difficult to develop. are comparatively easy to develop.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

Robotics :
Robotics is a domain in artificial intelligence that deals with the study of creating intelligent
and efficient robots.

What are Robots?

Robots are the artificial agents acting in real world environment.

Objective
Robots are aimed at manipulating the objects by perceiving, picking, moving, modifying the
physical properties of object, destroying it, or to have an effect thereby freeing manpower
from doing repetitive functions without getting bored, distracted, or exhausted.

What is Robotics?
Robotics is a branch of AI, which is composed of Electrical Engineering, Mechanical
Engineering, and Computer Science for designing, construction, and application of robots.

Aspects of Robotics
• The robots have mechanical construction, form, or shape designed to accomplish a
particular task.
• They have electrical components which power and control the machinery.
• They contain some level of computer program that determines what, when and how
a robot does something.

Difference in Robot System and Other AI Program

Here is the difference between the two −
AI Programs Robots
They usually operate in computer-
They operate in real physical world
stimulated worlds.
The input to an AI program is in Inputs to robots is analog signal in the form of
symbols and rules. speech waveform or images
They need general purpose computers They need special hardware with sensors and
to operate on. effectors.

Robot Locomotion
Locomotion is the mechanism that makes a robot capable of moving in its environment.
There are various types of locomotions −
• Legged
• Wheeled
• Combination of Legged and Wheeled Locomotion
• Tracked slip/skid

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

Legged Locomotion
• This type of locomotion consumes more power while demonstrating walk, jump, trot,
hop, climb up or down, etc.
• It requires more number of motors to accomplish a movement. It is suited for rough
as well as smooth terrain where irregular or too smooth surface makes it consume
more power for a wheeled locomotion. It is little difficult to implement because of
stability issues.
• If a robot has multiple legs then leg coordination is necessary for locomotion.
The total number of possible gaits (a periodic sequence of lift and release events for each of
the total legs) a robot can travel depends upon the number of its legs.
If a robot has k legs, then the number of possible events N = (2k-1)!.
In case of a two-legged robot (k=2), the number of possible events is N = (2k-1)! = (2*2-1)!
= 3! = 6.
Hence there are six possible different events −
• Lifting the Left leg
• Releasing the Left leg
• Lifting the Right leg
• Releasing the Right leg
• Lifting both the legs together
• Releasing both the legs together

Wheeled Locomotion
It requires fewer number of motors to accomplish a movement. It is little easy to implement
as there are less stability issues in case of more number of wheels. It is power efficient as
compared to legged locomotion.
• Standard wheel − Rotates around the wheel axle and around the contact
• Castor wheel − Rotates around the wheel axle and the offset steering joint.

• Swedish 45o and Swedish 90o wheels − Omni-wheel, rotates around the contact
point, around the wheel axle, and around the rollers.
• Ball or spherical wheel − Omnidirectional wheel, technically difficult to implement.

Slip/Skid Locomotion
In this type, the vehicles use tracks as in a tank. The robot is steered by moving the tracks
with different speeds in the same or opposite direction. It offers stability because of large
contact area of track and ground.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

Components of a Robot
Robots are constructed with the following −
• Power Supply − The robots are powered by batteries, solar power, hydraulic, or
pneumatic power sources.
• Actuators − They convert energy into movement.
• Electric motors (AC/DC) − They are required for rotational movement.
• Pneumatic Air Muscles − They contract almost 40% when air is sucked in them.
• Muscle Wires − They contract by 5% when electric current is passed through them.
• Piezo Motors and Ultrasonic Motors − Best for industrial robots.
• Sensors − They provide knowledge of real time information on the task environment.

Computer Vision
This is a technology of AI with which the robots can see. Computer vision automatically
extracts, analyzes, and comprehends useful information from a single image or an array of
images. This process involves development of algorithms to accomplish automatic visual
comprehension.

Hardware of Computer Vision System

This involves −
• Power supply
• Image acquisition device such as camera
• A processor
• A software
• A display device for monitoring the system
• Accessories such as camera stands, cables, and connectors

Tasks of Computer Vision

• OCR − In the domain of computers, Optical Character Reader, a software to convert
scanned documents into editable text, which accompanies a scanner.
• Face Detection − Many state-of-the-art cameras come with this feature, which
enables to read the face and take the picture of that perfect expression. It is used to let
a user access the software on correct match.
• Object Recognition − They are installed in supermarkets, cameras, high-end cars
such as BMW, GM, and Volvo.
• Estimating Position − It is estimating position of an object with respect to camera as
in position of tumor in human’s body.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

Expert Systems :
Expert systems (ES) are one of the prominent research domains of AI. It is introduced by the
researchers at Stanford University, Computer Science Department.

What are Expert Systems?

The expert systems are the computer applications developed to solve complex problems in a
particular domain, at the level of extra-ordinary human intelligence and expertise.

Characteristics of Expert Systems

• High performance
• Understandable
• Reliable
• Highly responsive

Capabilities of Expert Systems

The expert systems are capable of −
• Advising
• Instructing and assisting human in decision making
• Demonstrating
• Deriving a solution
• Diagnosing
• Explaining
• Interpreting input
• Predicting results
• Justifying the conclusion
• Suggesting alternative options to a problem
They are incapable of −
• Substituting human decision makers
• Possessing human capabilities
• Producing accurate output for inadequate knowledge base
• Refining their own knowledge

Components of Expert Systems

The components of ES include −
• Knowledge Base
• Inference Engine
• User Interface
Let us see them one by one briefly −

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

Knowledge Base
It contains domain-specific and high-quality knowledge.
Knowledge is required to exhibit intelligence. The success of any ES majorly depends upon
the collection of highly accurate and precise knowledge.

What is Knowledge?
The data is collection of facts. The information is organized as data and facts about the task
domain. Data, information, and past experience combined together are termed as
knowledge.

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.

Knowledge representation
It is the method used to organize and formalize the knowledge in the knowledge base. It is
in the form of IF-THEN-ELSE rules.

Knowledge Acquisition
The success of any expert system majorly depends on the quality, completeness, and
accuracy of the information stored in the knowledge base.
The knowledge base is formed by readings from various experts, scholars, and the
Knowledge Engineers. The knowledge engineer is a person with the qualities of empathy,
quick learning, and case analyzing skills.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

He acquires information from subject expert by recording, interviewing, and observing him
at work, etc.
He then categorizes and organizes the information in a meaningful way, in the form of IF-
THEN-ELSE rules, to be used by interference machine.
The knowledge engineer also monitors the development of the ES.

Inference Engine
Use of efficient procedures and rules by the Inference Engine is essential in deducting a
correct, flawless solution.
The Inference Engine acquires and manipulates the knowledge from the knowledge base to
arrive at a particular solution.
In case of rule based ES, it −
• Applies rules repeatedly to the facts, which are obtained from earlier rule application.
• Adds new knowledge into the knowledge base if required.
• Resolves rules conflict when multiple rules are applicable to a particular case.
To recommend a solution, the Inference Engine uses the following strategies −
• Forward Chaining
• Backward Chaining

Forward Chaining
It is a strategy of an expert system to answer the question, “What can happen next?”
Here, the Inference 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.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

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 Inference 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.

User Interface
User interface provides interaction between user of the ES and the ES itself. It is generally
Natural Language Processing so as to be used by the user who is well-versed in the task
domain. The user of the ES need not be necessarily an expert in Artificial Intelligence.
It explains how the ES has arrived at a particular recommendation. 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.
The user interface makes it easy to trace the credibility of the deductions.

Requirements of Efficient ES User Interface

• It should help users to accomplish their goals in shortest possible way.
• It should be designed to work for user’s existing or desired work practices.
• Its technology should be adaptable to user’s requirements; not the other way round.
• It should make efficient use of user input.

Expert Systems Limitations

No technology can offer easy and complete solution. Large systems are costly, require
significant development time, and computer resources. ESs have their limitations which
include −

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

• Limitations of the technology

• Difficult knowledge acquisition
• ES are difficult to maintain
• High development costs

Applications of Expert System

The following table shows where ES can be applied.
Application Description
Design Domain Camera lens design, automobile design.
Diagnosis Systems to deduce cause of disease from observed data,
Medical Domain
conduction medical operations on humans.
Monitoring Comparing data continuously with observed system or with prescribed
Systems behavior such as leakage monitoring in long petroleum pipeline.
Process Control
Controlling a physical process based on monitoring.
Systems
Knowledge
Finding out faults in vehicles, computers.
Domain
Finance/ Detection of possible fraud, suspicious transactions, stock market
Commerce trading, Airline scheduling, cargo scheduling.

Development of Expert Systems: General Steps

The process of ES development is iterative. Steps in developing the ES include −

1. 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.

2. 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.

3. 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.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

4. 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.

5. 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.

6. Maintain the System

• Keep the knowledge base up-to-date by regular review and update.
• Cater for new interfaces with other information systems, as those systems evolve.

Benefits of Expert Systems

• Availability − They are easily available due to mass production of software.
• Less Production Cost − Production cost is reasonable. This makes them affordable.
• Speed − They offer great speed. They reduce the amount of work an individual puts
in.
• Less Error Rate − Error rate is low as compared to human errors.
• Reducing Risk − They can work in the environment dangerous to humans.
• Steady response − They work steadily without getting motional, tensed or fatigued.

Theorem Proving :
Reasoning by theorem proving is a weak method, compared to experts systems, because it
does not make use of domain knowledge. This, on the other hand, may be a strength, if no
domain heuristics are available (reasoning from first principles). Theorem proving is usually
limited to sound reasoning.
Differentiate between
• theorem provers: fully automatic
• proof assistants: require steps as input, take care of bookkeeping and sometimes 'easy'
proofs.
Theorem proving requires
• a logic (syntax)
• a set of axioms and inference rules

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)

 lOMoARcPSD|19189123

• a strategy on when how to search through the possible applications of the axioms and rules
Strategies
Forwards - start from axioms, apply rules
Backwards - start from the theorem (in general: a set of goals), work backwards to the
axioms

AI techniques – Search Knowlegde

• Large amounts of knowledge and some mechanisms to manipulate the knowledge is
needed to create solutions for complex problems encountered in AI.
• We have to search the goal in that knowledge
• To search a knowledge base efficiently, it is necessary to represent the knowledge
base in a systematic way so that it can be searched easily.
• The knowledge can be represented either in the form of facts or in some formalism.
• When there are many possible paths of reasoning, it is clear that fruitless ones not be
pursued.
• Knowledge about path most likely to lead quickly to a goal state is often called
search control knowledge.

Abstraction :
• Abstraction a mental facility that permits humans to view real-world problems with
varying degrees of details depending on the current context of the problem.

• Abstraction means to hide the details of something.

• For example, if we want to compute the square root of a number then we simply call
the function sqrt in C. We do not need to know the implementation details of this
function.

• Early attempts to do this involved the use of macro-operators, in which large

operators we built from smaller one’s. But in this approach, no details were
eliminated from actual description of the operators.

• A better approach was developed in the ABSTRIPS system, which actually planned
in a hierarchy of abstraction spaces, in each of which preconditions at a lower level
of abstraction, was ignored.

Downloaded by Crazy Leader (billionairecrazyleader@gmail.com)