Ai Chap 1

191AIC403T - ARTIFICIAL INTELLIGENCEUnit-I
INTRODUCTION TO AI
Introduction to AI-Problem formulation, Problem Definition -Production systems, Control
strategies, Search strategies. Problem characteristics - Problem solving methods -Hill
Climbing-Depth first and Breadth first, Constraints satisfaction – Related algorithms,
Measure of performance and analysis of search Algorithms-Genetic Algorithms.
1.1 Introduction to AI:
What is artificial intelligence?
 Artificial Intelligence is the branch of computer science concerned with making

computers behave like humans.
 Major AI textbooks define artificial intelligence as "the study and design of
intelligent agents," where an intelligent agent is a system that perceives its
environment and takes actions which maximize its chances of success.
 John McCarthy, who coined the term in 1956, defines it as "the science
and engineering of making intelligent machines, especially intelligent
computer programs."
 The definitions of AI according to some text books are categorized into
four approaches and are summarized in the table below :
Systems that think like humans Systems that think rationally

"The exciting new effort to make computers "The study of mental faculties through the use
think … machines with minds, in the full and of computer models."
literal sense."(Haugeland,1985) (Charniak and McDermont,1985)
Systems that act like humans Systems that act rationally

The art of creating machines that performs "Computational intelligence is the study of the
functions that require intelligence when design of intelligent agents."(Poole et al.,1998)
performed by people."(Kurzweil,1990)
Philosophy of AI
While exploiting the power of the computer systems, the curiosity of human, lead him to
wonder, “Can a machine think and behave like humans do?”
Thus, the development of AI started with the intention of creating similar intelligence in
machines that we find and regard high in humans.
Goals of AI
 To Create Expert Systems − The systems which exhibit intelligent behavior, learn,
demonstrate, explain, and advice its users.
1
 To Implement Human Intelligence in Machines − Creating systems that

understand, think, learn, and behave like humans.
What Contributes to AI?
Artificial intelligence is a science and technology based on disciplines such as Computer
Science, Biology, Psychology, Linguistics, Mathematics, and Engineering. A major thrust of
AI is in the development of computer functions associated with human intelligence, such as
reasoning, learning, and problem solving.
Out of the following areas, one or multiple areas can contribute to build an intelligent
system.
Programming Without and With AI

The programming without and with AI is different in following ways −
Programming Without AI Programming With AI
A computer program without AI can answer A computer program with AI can answer
the specific questions it is meant to solve. the generic questions it is meant to solve.
AI programs can absorb new modifications by

putting highly independent pieces of information
Modification in the program leads to change
together. Hence you can modify even a minute
in its structure.
piece of information of program without affecting
its structure.
Modification is not quick and easy. It may

Quick and Easy program modification.
lead to affecting the program adversely.
What is AI Technique?
In the real world, the knowledge has some unwelcomed properties −
2
 Its volume is huge, next to unimaginable.

 It is not well-organized or well-formatted.
 It keeps changing constantly.
AI Technique is a manner to organize and use the knowledge efficiently in such a way that −
 It should be perceivable by the people who provide it.

 It should be easily modifiable to correct errors.
 It should be useful in many situations though it is incomplete or inaccurate.
AI techniques elevate the speed of execution of the complex program it is equipped with.
Applications of AI
AI has been dominant in various fields such as −
 Gaming − AI plays crucial role in strategic games such as chess, poker, tic-tac-toe,
etc., where machine can think of large number of possible positions based on
heuristic knowledge.
 Natural Language Processing − It is possible to interact with the computer that
understands natural language spoken by humans.
 Expert Systems − There are some applications which integrate machine, software,
and special information to impart reasoning and advising. They provide explanation
and advice to the users.
 Vision Systems − These systems understand, interpret, and comprehend visual input
on the computer. For example,
o A spying aeroplane takes photographs, which are used to figure out spatial
information or map of the areas.
o Doctors use clinical expert system to diagnose the patient.
o Police use computer software that can recognize the face of criminal with the
stored portrait made by forensic artist.
 Speech Recognition − Some intelligent systems are capable of hearing and
comprehending the language in terms of sentences and their meanings while a
human talks to it. It can handle different accents, slang words, noise in the
background, change in human’s noise due to cold, etc.
 Handwriting Recognition − The handwriting recognition software reads the text
written on paper by a pen or on screen by a stylus. It can recognize the shapes of the
letters and convert it into editable text.
 Intelligent Robots − Robots are able to perform the tasks given by a human. They
have sensors to detect physical data from the real world such as light, heat,
temperature, movement, sound, bump, and pressure. They have efficient processors,
multiple sensors and huge memory, to exhibit intelligence. In addition, they are
capable of learning from their mistakes and they can adapt to the new
environment.
3
Types of Artificial Intelligence:
Artificial Intelligence can be divided in various types, there are mainly two types of main
categorization which are based on capabilities and based on functionally of AI. Following is
flow diagram which explain the types of AI.
AI type-1: Based on Capabilities

1. Weak AI or Narrow AI:
o Narrow AI is a type of AI which is able to perform a dedicated task with
intelligence.The most common and currently available AI is Narrow AI in the world
of Artificial Intelligence.
o Narrow AI cannot perform beyond its field or limitations, as it is only trained for one
specific task. Hence it is also termed as weak AI. Narrow AI can fail in unpredictable
ways if it goes beyond its limits.
o Apple Siriis a good example of Narrow AI, but it operates with a limited pre-defined
range of functions.
o IBM's Watson supercomputer also comes under Narrow AI, as it uses an Expert
system approach combined with Machine learning and natural language processing.
o Some Examples of Narrow AI are playing chess, purchasing suggestions on e-
commerce site, self-driving cars, speech recognition, and image recognition.
2. General AI:
o General AI is a type of intelligence which could perform any intellectual task with
efficiency like a human.
o The idea behind the general AI to make such a system which could be smarter and
think like a human by its own.
4
o Currently, there is no such system exist which could come under general AI and can
perform any task as perfect as a human.
o The worldwide researchers are now focused on developing machines with General AI.
o As systems with general AI are still under research, and it will take lots of efforts and
time to develop such systems.
3. Super AI:
o Super AI is a level of Intelligence of Systems at which machines could surpass human
intelligence, and can perform any task better than human with cognitive properties. It
is an outcome of general AI.
o Some key characteristics of strong AI include capability include the ability to think, to
reason,solve the puzzle, make judgments, plan, learn, and communicate by its own.
o Super AI is still a hypothetical concept of Artificial Intelligence. Development of such
systems in real is still world changing task.
Artificial Intelligence type-2: Based on functionality

1. Reactive Machines
o Purely reactive machines are the most basic types of Artificial Intelligence.
o Such AI systems do not store memories or past experiences for future actions.
o These machines only focus on current scenarios and react on it as per possible best
action.
o IBM's Deep Blue system is an example of reactive machines.
o Google's AlphaGo is also an example of reactive machines.
2. Limited Memory
o Limited memory machines can store past experiences or some data for a short period
of time.
o These machines can use stored data for a limited time period only.
5
o Self-driving cars are one of the best examples of Limited Memory systems. These
cars can store recent speed of nearby cars, the distance of other cars, speed limit, and
other information to navigate the road.
3. Theory of Mind
o Theory of Mind AI should understand the human emotions, people, beliefs, and be
able to interact socially like humans.
o This type of AI machines are still not developed, but researchers are making lots of
efforts and improvement for developing such AI machines.
4. Self-Awareness
o Self-awareness AI is the future of Artificial Intelligence. These machines will be
super intelligent, and will have their own consciousness, sentiments, and self-
awareness.
o These machines will be smarter than human mind.
o Self-Awareness AI does not exist in reality still and it is a hypothetical concept.
AGENTS:
An agent is anything that can perceive its environment through sensors and acts upon that
environment through effectors.
 A human agent has sensory organs such as eyes, ears, nose, tongue and skin parallel
to the sensors, and other organs such as hands, legs, mouth, for effectors.
 A robotic agent replaces cameras and infrared range finders for the sensors, and
various motors and actuators for effectors.
 A software agent has encoded bit strings as its programs and actions.
Agent Terminology
 Performance Measure of Agent − It is the criteria, which determines how
successful an agent is.
 Behaviour of Agent − It is the action that agent performs after any given sequence of
percepts.
 Percept − It is agent’s perceptual inputs at a given instance.
 Percept Sequence − It is the history of all that an agent has perceived till date.
 Agent Function − It is a map from the precept sequence to an action.
6
Intelligent Agents:
An intelligent agent is an autonomous entity which act upon an environment using sensors
and actuators for achieving goals. An intelligent agent may learn from the environment to
achieve their goals. A thermostat is an example of an intelligent agent.
Following are the main four rules for an AI agent:
o Rule 1: An AI agent must have the ability to perceive the environment.

o Rule 2: The observation must be used to make decisions.
o Rule 3: Decision should result in an action.
o Rule 4: The action taken by an AI agent must be a rational action.
Rational Agent:
A rational agent is an agent which has clear preference, models uncertainty, and acts in a way
to maximize its performance measure with all possible actions.
A rational agent is said to perform the right things. AI is about creating rational agents to use
for game theory and decision theory for various real-world scenarios.
For an AI agent, the rational action is most important because in AI reinforcement learning
algorithm, for each best possible action, agent gets the positive reward and for each wrong
action, an agent gets a negative reward.
Rationality:
The rationality of an agent is measured by its performance measure. Rationality can be

judged on the basis of following points:
o Performance measure which defines the success criterion.

o Agent prior knowledge of its environment.
o Best possible actions that an agent can perform.
o The sequence of percepts.
7
Types of AI Agents
Agents can be grouped into five classes based on their degree of perceived intelligence and
capability. All these agents can improve their performance and generate better action over the
time. These are given below:
o Simple Reflex Agent

o Model-based reflex agent
o Goal-based agents
o Utility-based agent
o Learning agent
1. Simple Reflex agent:

o The Simple reflex agents are the simplest agents. These agents take decisions on the
basis of the current percepts and ignore the rest of the percept history.
o These agents only succeed in the fully observable environment.
o The Simple reflex agent does not consider any part of percepts history during their
decision and action process.
o The Simple reflex agent works on Condition-action rule, which means it maps the
current state to action. Such as a Room Cleaner agent, it works only if there is dirt in
the room.
o Problems for the simple reflex agent design approach:
o They have very limited intelligence
o They do not have knowledge of non-perceptual parts of the current state
o Mostly too big to generate and to store.
o Not adaptive to changes in the environment.
8
2. Model-based reflex agent

o The Model-based agent can work in a partially observable environment, and track the
situation.
o A model-based agent has two important factors:
o Model: It is knowledge about "how things happen in the world," so it is called
a Model-based agent.
o Internal State: It is a representation of the current state based on percept
history.
o These agents have the model, "which is knowledge of the world" and based on the
model they perform actions.
o Updating the agent state requires information about:
a. How the world evolves

b. How the agent's action affects the world.
9
3. Goal-based agents
o The knowledge of the current state environment is not always sufficient to decide for
an agent to what to do.
o The agent needs to know its goal which describes desirable situations.
o Goal-based agents expand the capabilities of the model-based agent by having the
"goal" information.
o They choose an action, so that they can achieve the goal.
o These agents may have to consider a long sequence of possible actions before
deciding whether the goal is achieved or not. Such considerations of different scenario
are called searching and planning, which makes an agent proactive.
10
4. Utility-based agents
o These agents are similar to the goal-based agent but provide an extra component of
utility measurement which makes them different by providing a measure of success at
a given state.
o Utility-based agent act based not only goals but also the best way to achieve the goal.
o The Utility-based agent is useful when there are multiple possible alternatives, and an
agent has to choose in order to perform the best action.
o The utility function maps each state to a real number to check how efficiently each
action achieves the goals.
11
5. Learning Agents
o A learning agent in AI is the type of agent which can learn from its past experiences,
or it has learning capabilities.
o It starts to act with basic knowledge and then able to act and adapt automatically
through learning.
o A learning agent has mainly four conceptual components, which are:
a. Learning element: It is responsible for making improvements by learning

from environment
b. Critic: Learning element takes feedback from critic which describes that how
well the agent is doing with respect to a fixed performance standard.
c. Performance element: It is responsible for selecting external action
d. Problem generator: This component is responsible for suggesting actions
that will lead to new and informative experiences.
o Hence, learning agents are able to learn, analyze performance, and look for new ways
to improve the performance.
12
PEAS Representation
PEAS is a type of model on which an AI agent works upon. When we define an AI agent or
rational agent, then we can group its properties under PEAS representation model. It is made
up of four words:
o P: Performance measure
o E: Environment
o A: Actuators
o S: Sensors
Here performance measure is the objective for the success of an agent's behavior.
PEAS for self-driving cars:
Let's suppose a self-driving car then PEAS representation will be:
Performance: Safety, time, legal drive, comfort
Environment: Roads, other vehicles, road signs, pedestrian
Actuators: Steering, accelerator, brake, signal, horn
Sensors: Camera, GPS, speedometer, odometer, accelerometer, sonar.
Example of Agents with their PEAS representation

13
Agent Performance Environment Actuators Sensors

measure
1. Medical Keyboard
o Healthy patient o Patient o Tests (Entry of symptoms)
Diagnose
o Minimized o Hospital o Treatments
cost o Staff
2. Vacuum
o Cleanness o Room o Wheels o Camera
Cleaner
o Efficiency o Table o Brushes o Dirt detection
o Battery life o Wood floor o Vacuum sensor
o Security o Carpet Extractor o Cliff sensor
o Various o Bump Sensor

obstacles o Infrared Wall
Sensor
3. Part -
picking
o Percentage of o Conveyor o Jointed o Camera
Robot parts in correct belt with Arms o Joint angle
bins. parts, o Hand sensors.
o Bins
Turing Test in AI
In 1950, Alan Turing introduced a test to check whether a machine can think like a human or
not, this test is known as the Turing Test. In this test, Turing proposed that the computer can
be said to be an intelligent if it can mimic human response under specific conditions.
Turing Test was introduced by Turing in his 1950 paper, "Computing Machinery and
Intelligence," which considered the question, "Can Machine think?"
14
The Turing test is based on a party game "Imitation game," with some modifications. This
game involves three players in which one player is Computer, another player is human
responder, and the third player is a human Interrogator, who is isolated from other two
players and his job is to find that which player is machine among two of them.
Consider, Player A is a computer, Player B is human, and Player C is an interrogator.

Interrogator is aware that one of them is machine, but he needs to identify this on the basis of
questions and their responses.
The conversation between all players is via keyboard and screen so the result would not
depend on the machine's ability to convert words as speech.
The test result does not depend on each correct answer, but only how closely its responses
like a human answer. The computer is permitted to do everything possible to force a wrong
identification by the interrogator.
The questions and answers can be like:
Interrogator: Are you a computer?
PlayerA (Computer): No
Interrogator: Multiply two large numbers such as (256896489*456725896)
Player A: Long pause and give the wrong answer.
In this game, if an interrogator would not be able to identify which is a machine and which is
human, then the computer passes the test successfully, and the machine is said to be
intelligent and can think like a human.
"In 1991, the New York businessman Hugh Loebner announces the prize competition,
offering a $100,000 prize for the first computer to pass the Turing test. However, no AI
program to till date, come close to passing an undiluted Turing test".
15
Chatbots to attempt the Turing test:
ELIZA: ELIZA was a Natural language processing computer program created by Joseph
Weizenbaum. It was created to demonstrate the ability of communication between machine
and humans. It was one of the first chatterbots, which has attempted the Turing Test.
Parry: Parry was a chatterbot created by Kenneth Colby in 1972. Parry was designed to
simulate a person with Paranoid schizophrenia(most common chronic mental disorder).
Parry was described as "ELIZA with attitude." Parry was tested using a variation of the
Turing Test in the early 1970s.
Eugene Goostman: Eugene Goostman was a chatbot developed in Saint Petersburg in 2001.
This bot has competed in the various number of Turing Test. In June 2012, at an event,
Goostman won the competition promoted as largest-ever Turing test content, in which it has
convinced 29% of judges that it was a human.Goostman resembled as a 13-year old virtual
boy.
The Chinese Room Argument:
There were many philosophers who really disagreed with the complete concept of Artificial
Intelligence. The most famous argument in this list was "Chinese Room."
In the year 1980, John Searle presented "Chinese Room" thought experiment, in his paper
"Mind, Brains, and Program," which was against the validity of Turing's Test. According
to his argument, "Programming a computer may make it to understand a language, but
it will not produce a real understanding of language or consciousness in a computer."
He argued that Machine such as ELIZA and Parry could easily pass the Turing test by
manipulating keywords and symbol, but they had no real understanding of language. So it
cannot be described as "thinking" capability of a machine such as a human.
Features required for a machine to pass the Turing test:

o Natural language processing: NLP is required to communicate with Interrogator in
general human language like English.
o Knowledge representation: To store and retrieve information during the test.
o Automated reasoning: To use the previously stored information for answering the
questions.
o Machine learning: To adapt new changes and can detect generalized patterns.
o Vision (For total Turing test): To recognize the interrogator actions and other
objects during a test.
o Motor Control (For total Turing test): To act upon objects if requested.
16
Problem formulation:
It is one of the core steps of problem-solving which decides what action should be taken to
achieve the formulated goal. In AI this core part is dependent upon software agent which
consisted of the following components to formulate the associated problem.
To build a system to solve a problem
1. Define the problem precisely
2. Analyse the problem
3. Isolate and represent the task knowledge that is necessary to solve the problem
4. Choose the best problem-solving techniques and apply it to the particular problem.
Mouse Path Problem
 Problem Statement
 Problem Definition: Mouse is hungry, mouse is in a puzzle where there are some
cheese. Mouse will only be satisfied if mouse eat cheese
 Problem Limitation: Some paths are close i-e dead end, mouse can only travel
through open paths
 Problem Solution: Reach location where is cheese and eat minimum one cheese. There
are possible solutions (cheese pieces)
 Solution Space: To reach cheese there are multiple paths possible
 Operators: Mouse can move in four possible directions, these directions are operators or
actions which are UP, DOWN, LEFT and RIGHT
17
Water Jug Problem
o You are given two jugs, a 4-gallon one and a 3-litre one.
o Neither have any measuring markers on it.
o There is a pump that can be used to fill the jugs with water.
o How can you get exactly 2 gallons of water into 4-gallon jug.
o Let x and y be the amounts of water in 4-gallon and 3-gallon Jugs respectively
o (x,y) refers to water available at any time in 4-gallon, 3-gallon jugs.
o (x,y)  (x-d,y+dd) means drop some unknown amount d of water from 4-
gallon jug and add dd onto 3-gallon jug.
The state space for this problem can be described as the set of ordered pairs of integers (x,y)
such that x = 0, 1,2, 3 or 4 and y = 0,1,2 or 3; x represents the number of gallons of water in
the 4-gallon jug and y represents the quantity of water in 3-gallon jug
o The start state is (0,0)
o The goal state is (2,n)
Production rules for Water Jug Problem
Sl No Current state Next State Description
1 (x,y) if x < 4 (4,y) Fill the 4 gallon jug
2 (x,y) if y <3 (x,3) Fill the 3 gallon jug
3 (x,y) if x > 0 (x-d, y) Pour some water out of the 4 gallon jug
4 (x,y) if y > 0 (x, y-d) Pour some water out of the 3-gallon jug
5 (x,y) if x>0 (0, y) Empty the 4 gallon jug
6 (x,y) if y >0 (x,0) Empty the 3 gallon jug on the ground
7 (x,y) if x+y >= 4 and y (4, y-(4-x)) Pour water from the 3 –gallon jug into
>0 the 4 –gallon jug until the 4-gallon jug
is full
8 (x, y) if x+y >= 3 and (x-(3-y), 3) Pour water from the 4-gallon jug into
x>0 the 3-gallon jug until the 3-gallon jug is
full
9 (x, y) if x+y <=4 and (x+y, 0) Pour all the water from the 3-gallon jug
y>0 into the 4-gallon jug
10 (x, y) if x+y <= 3 and (0, x+y) Pour all the water from the 4-gallon jug
x>0 into the 3-gallon jug
11 (0,2) (2,0) Pour the 2 gallons from 3-gallon jug

into the 4-gallon jug
12 (2,y) (0,y) Empty the 2 gallons in the 4-gallon jug

on the ground
18
Gallons in Gallons in Rule applied

the 4-gallon the 3-gallon
jug jug
0 0 2
0 3 9
3 0 2
3 3 7
4 2 5 or 12
0 2 9 0r 11
2 0
Required a control structure that loops through a simple cycle in which some rule
whose left side matches the current state is chosen, the appropriate change to the state is
made as described in the corresponding right side, and the resulting state is checked to see if
it corresponds to goal state. One solution to the water jug problem shortest such sequence will
have a impact on the choice of appropriate mechanism to guide the search for solution.
Path Finding Problem
 Definition: Going from Arad to Bucharest in given map
 Limitation: Must travel from location to other if there is path
 Problem Solution: Reach Bucharest
 Solution Space: There are multiple paths to reach Bucharest.
 Operators: Move to other locations
The reflex agents are known as the simplest agents because they directly map states
into actions. Unfortunately, these agents fail to operate in an environment where the
mapping is too large to store and learn. Goal-based agent, on the other hand,
considers future actions and the desired outcomes.
Here, we will discuss one type of goal-based agent known as a problem-solving
agent, which uses atomic representation with no internal states visible to the problem-
solving algorithms.
19
Problem-solving in Artificial Intelligence:

The reflex agents are known as the simplest agents because they directly map states into
actions. Unfortunately, these agents fail to operate in an environment where the mapping is
too large to store and learn. Goal-based agent, on the other hand, considers future actions and
the desired outcomes.
Here, we will discuss one type of goal-based agent known as a problem-solving agent, which
uses atomic representation with no internal states visible to the problem-solving algorithms.
Problem-solving agent
The problem-solving agent perfoms precisely by defining problems and its several solutions.
According to psychology, “a problem-solving refers to a state where we wish to reach to a
definite goal from a present state or condition.”
According to computer science, a problem-solving is a part of artificial intelligence which
encompasses a number of techniques such as algorithms, heuristics to solve a problem.
Therefore, a problem-solving agent is a goal-driven agent and focuses on satisfying the goal.
Steps performed by Problem-solving agent
 Goal Formulation: It is the first and simplest step in problem-solving. It organizes

the steps/sequence required to formulate one goal out of multiple goals as well as
actions to achieve that goal. Goal formulation is based on the current situation and the
agent's performance measure (discussed below).
 Problem Formulation: It is the most important step of problem-solving which
decides what actions should be taken to achieve the formulated goal. There are
following five components involved in problem formulation:
 Initial State: It is the starting state or initial step of the agent towards its goal.
 Actions: It is the description of the possible actions available to the agent.
 Transition Model: It describes what each action does.
 Goal Test: It determines if the given state is a goal state.
 Path cost: It assigns a numeric cost to each path that follows the goal. The problem-
solving agent selects a cost function, which reflects its performance measure.
Remember, an optimal solution has the lowest path cost among all the solutions.
20
Note: Initial state, actions, and transition model together define the state-space of the
problem implicitly. State-space of a problem is a set of all states which can be reached from
the initial state followed by any sequence of actions. The state-space forms a directed map or
graph where nodes are the states, links between the nodes are actions, and the path is a
sequence of states connected by the sequence of actions.
 Search: It identifies all the best possible sequence of actions to reach the goal state
from the current state. It takes a problem as an input and returns solution as its output.
 Solution: It finds the best algorithm out of various algorithms, which may be proven
as the best optimal solution.
 Execution: It executes the best optimal solution from the searching algorithms to
reach the goal state from the current state.
Example Problems
Basically, there are two types of problem approaches:
 Toy Problem: It is a concise and exact description of the problem which is used by
the researchers to compare the performance of algorithms.
 Real-world Problem: It is real-world based problems which require solutions. Unlike
a toy problem, it does not depend on descriptions, but we can have a general
formulation of the problem.
Some Toy Problems
 8 Puzzle Problem: Here, we have a 3x3 matrix with movable tiles numbered from 1
to 8 with a blank space. The tile adjacent to the blank space can slide into that space.
The objective is to reach a specified goal state similar to the goal state, as shown in
the below figure.
 In the figure, our task is to convert the current state into goal state by sliding digits
into the blank space.
In the above figure, our task is to convert the current(Start) state into goal state by sliding
digits into the blank space.
The problem formulation is as follows:
 States: It describes the location of each numbered tiles and the blank tile.
 Initial State: We can start from any state as the initial state.
21
 Actions: Here, actions of the blank space is defined, i.e., either left, right, up or
down
 Transition Model: It returns the resulting state as per the given state and actions.
 Goal test: It identifies whether we have reached the correct goal-state.
 Path cost: The path cost is the number of steps in the path where the cost of each step
is 1.
Note: The 8-puzzle problem is a type of sliding-block problem which is used for testing
new search algorithms in artificial intelligence.
 8-queens problem: The aim of this problem is to place eight queens on a chessboard
in an order where no queen may attack another. A queen can attack other queens
either diagonally or in same row and column.
From the following figure, we can understand the problem as well as its correct solution.
It is noticed from the above figure that each queen is set into the chessboard in a position
where no other queen is placed diagonally, in same row or column. Therefore, it is one right
approach to the 8-queens problem.
For this problem, there are two main kinds of formulation:
 Incremental formulation: It starts from an empty state where the operator augments
a queen at each step.
Following steps are involved in this formulation:
 States: Arrangement of any 0 to 8 queens on the chessboard.

 Initial State: An empty chessboard
 Actions: Add a queen to any empty box.
 Transition model: Returns the chessboard with the queen added in a box.
 Goal test: Checks whether 8-queens are placed on the chessboard without any attack.
 Path cost: There is no need for path cost because only final states are counted.
In this formulation, there is approximately 1.8 x 1014 possible sequence to investigate.
 Complete-state formulation: It starts with all the 8-queens on the chessboard and
moves them around, saving from the attacks.
22
Following steps are involved in this formulation
 States: Arrangement of all the 8 queens one per column with no queen attacking the
other queen.
 Actions: Move the queen at the location where it is safe from the attacks.
This formulation is better than the incremental formulation as it reduces the state space
from 1.8 x 1014 to 2057, and it is easy to find the solutions.
Some Real-world problems
 Traveling salesperson problem(TSP): It is a touring problem where the salesman

can visit each city only once. The objective is to find the shortest tour and sell-out the
stuff in each city.
 VLSI Layout problem: In this problem, millions of components and connections are
positioned on a chip in order to minimize the area, circuit-delays, stray-capacitances,
and maximizing the manufacturing yield.
The layout problem is split into two parts:
 Cell layout: Here, the primitive components of the circuit are grouped into cells, each
performing its specific function. Each cell has a fixed shape and size. The task is to
place the cells on the chip without overlapping each other.
 Channel routing: It finds a specific route for each wire through the gaps between the
cells.
 Protein Design: The objective is to find a sequence of amino acids which will fold
into 3D protein having a property to cure some disease.
Searching for solutions

We have seen many problems. Now, there is a need to search for solutions to solve them.
In this section, we will understand how searching can be used by the agent to solve a
problem.
For solving different kinds of problem, an agent makes use of different strategies to reach the
goal by searching the best possible algorithms. This process of searching is known as search
strategy.
Measuring problem-solving performance
Before discussing different search strategies, the performance measure of an algorithm
should be measured. Consequently, There are four ways to measure the performance of an
algorithm:
Completeness: It measures if the algorithm guarantees to find a solution (if any solution
exist).
Optimality: It measures if the strategy searches for an optimal solution.
Time Complexity: The time taken by the algorithm to find a solution.
Space Complexity: Amount of memory required to perform a search.
The complexity of an algorithm depends on branching factor or maximum number of
successors, depth of the shallowest goal node (i.e., number of steps from root to the path)
and the maximum length of any path in a state space.
Production System in AI
23
A production system (popularly known as a production rule system) is a kind of cognitive

architecture that is used to implement search algorithms and replicate human problem-solving
skills. This problem-solving knowledge is encoded in the system in the form of little quanta
popularly known as productions. It consists of two components: rule and action.
Rules recognize the condition, and the actions part has the knowledge of how to deal with the
condition. In simpler words, the production system in AI contains a set of rules which are
defined by the left side and right side of the system. The left side contains a set of things to
watch for (condition), and the right side contains the things to do (action).
What are the Elements of a Production System?
An AI production system has three main elements which are as follows:
 Global Database: The primary database which contains all the information necessary to
successfully complete a task. It is further broken down into two parts: temporary and
permanent. The temporary part contains information relevant to the current situation only
whereas the permanent part contains information about the fixed actions.
 A set of Production Rules: A set of rules that operates on the global database. Each rule
consists of a precondition and postcondition that the global database either meets or not. For
example, if a condition is met by the global database, then the production rule is applied
successfully.
 Control System: A control system that acts as the decision-maker, decides which
production rule should be applied. The Control system stops computation or processing when
a termination condition is met on the database.
A production system has the following features:
1. Simplicity: Due to the use of the IF-THEN structure, each sentence is unique in the
production system. This uniqueness makes the knowledge representation simple to enhance
the readability of the production rules.
2. Modularity: The knowledge available is coded in discrete pieces by the production system,
which makes it easy to add, modify, or delete the information without any side effects.
3. Modifiability: This feature allows for the modification of the production rules. The rules are
first defined in the skeletal form and then modified to suit an application.
4. Knowledge-intensive: As the name suggests, the system only stores knowledge. All the rules
are written in the English language. This type of representation solves the semantics problem.
A production system is classified into four main classes which are:
 Monotonic Production System: In a monotonic production system, the use of one rule
never prevents the involvement of another rule when both the rules are selected at the same
time. Hence, it enables the system to apply rules simultaneously.
 Partially Commutative Production System: In this production system if a set of rules is
used to change state A to state B then any allowable combination of these rules will also
produce the same results (convert state A to state B).
 Non-Monotonic Production System: This production system increases the problem-
solving efficiency of the machine by not keeping a record of the changes made in the
previous search process. These types of production systems are useful from an
24
implementation point of view as they do not backtrack to the previous state when it is found
that an incorrect path was followed.
 Commutative Production System: These type of production systems is used when the
order of operation is not important, and the changes are reversible.
Join the Machine Learning Course online from the World’s top Universities – Masters,
Executive Post Graduate Programs, and Advanced Certificate Program in ML & AI to fast-
track your career.
Advantages of using a Production System:
Offers modularity as all the rules can be added, deleted, or modified individually.
 Separate control system and knowledge base.
 An excellent and feasible model that imitates human problem-solving skills.
 Beneficial in real-time applications and environment.
 Offers language independence.
Control strategies:
• Control Strategy in Artificial Intelligence scenario is a technique or strategy, tells us about which
rule has to be applied next while searching for the solution of a problem within problem space. It
helps us to decide which rule has to apply next without getting stuck at any point. These rules
decide the way we approach the problem and how quickly it is solved and even whether a problem
is finally solved.
• Control Strategy helps to find the solution when there is more than one rule or fewer rules for
finding the solution at each point in problem space.
• Requirements for a good Control Strategy
– It should cause motion
In water jug problem, if we apply a simple control strategy of starting each time from the top
of rule list and choose the first applicable one, then we will never move towards solution.
– It should explore the solution space in a systematic manner
If we choose another control strategy, say, choose a rule randomly from the applicable rules
then definitely it causes motion and eventually will lead to a solution. But one may arrive to same
state several times. This is because control strategy is not systematic.
Examples:
Breadth First Search
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
25
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.
26
• If there are multiple solutions, then a minimal solution will be found.
Depth First Search

1. If the initial state is a goal state, quit and return success
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.
27
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.
Travelling Salesman Problem

A travelling salesman has to visit all the cities atleast once at a minimum cost and return back to the
starting position.
 If there are N cities, then number of different paths among them is (N-1)!
 So the total time required to perform this search is proportional to N!
 For 10 cities, 9! = 3,628,800
 This phenomenon is called combinatorial explosion.
Search strategies:
Searching is a process to find the solution for a given set of problems. This in artificial
intelligence can be done by using either uninformed searching strategies of either informed
searching strategies.
Search Algorithm Terminologies:

o Search: Searching is a step by step procedure to solve a search-problem in a given
search space. A search problem can have three main factors:
a. Search Space: Search space represents a set of possible solutions, which a

system may have.
b. Start State: It is a state from where agent begins the search.
c. Goal test: It is a function which observe the current state and returns whether
the goal state is achieved or not.
o Search tree: A tree representation of search problem is called Search tree. The root of
the search tree is the root node which is corresponding to the initial state.
o Actions: It gives the description of all the available actions to the agent.
o Transition model: A description of what each action do, can be represented as a
transition model.
o Path Cost: It is a function which assigns a numeric cost to each path.
o Solution: It is an action sequence which leads from the start node to the goal node.
o Optimal Solution: If a solution has the lowest cost among all solutions.
Properties of Search Algorithms:
Following are the four essential properties of search algorithms to compare the efficiency of
these algorithms:
28
Completeness: A search algorithm is said to be complete if it guarantees to return a solution

if at least any solution exists for any random input.
175.2K
Tesla announces plans for humanoid robot
Optimality: If a solution found for an algorithm is guaranteed to be the best solution (lowest
path cost) among all other solutions, then such a solution for is said to be an optimal solution.
Time Complexity: Time complexity is a measure of time for an algorithm to complete its
task.
Space Complexity: It is the maximum storage space required at any point during the search,
as the complexity of the problem.
Types of search algorithms
Based on the search problems we can classify the search algorithms into uninformed
(Blind search) search and informed search (Heuristic search) algorithms.
Uninformed/Blind Search:
The uninformed search does not contain any domain knowledge such as closeness, the
location of the goal. It operates in a brute-force way as it only includes information about
how to traverse the tree and how to identify leaf and goal nodes. Uninformed search applies a
way in which search tree is searched without any information about the search space like
initial state operators and test for the goal, so it is also called blind search. It examines each
node of the tree until it achieves the goal node.
29
It can be divided into five main types:
o Breadth-first search
o Uniform cost search
o Depth-first search
o Iterative deepening depth-first search
o Bidirectional Search
Informed Search
Informed search algorithms use domain knowledge. In an informed search, problem

information is available which can guide the search. Informed search strategies can find a
solution more efficiently than an uninformed search strategy. Informed search is also called a
Heuristic search.
A heuristic is a way which might not always be guaranteed for best solutions but guaranteed
to find a good solution in reasonable time.
Informed search can solve much complex problem which could not be solved in another way.
An example of informed search algorithms is a traveling salesman problem.
1. Greedy Search
2. A* Search
Uninformed Search Algorithms
Uninformed search is a class of general-purpose search algorithms which operates in brute

force-way. Uninformed search algorithms do not have additional information about state or
search space other than how to traverse the tree, so it is also called blind search.
Following are the various types of uninformed search algorithms:
1. Breadth-first Search
2. Depth-first Search
3. Depth-limited Search
4. Iterative deepening depth-first search
5. Uniform cost search
6. Bidirectional Search
1. Breadth-first Search:
30
o Breadth-first search is the most common search strategy for traversing a tree or graph.
This algorithm searches breadthwise in a tree or graph, so it is called breadth-first
search.
o BFS algorithm starts searching from the root node of the tree and expands all
successor node at the current level before moving to nodes of next level.
o The breadth-first search algorithm is an example of a general-graph search algorithm.
o Breadth-first search implemented using FIFO queue data structure.
Advantages:
o BFS will provide a solution if any solution exists.

o If there are more than one solutions for a given problem, then BFS will provide the
minimal solution which requires the least number of steps.
Disadvantages:
Nested Structure in C
Keep Watching
o It requires lots of memory since each level of the tree must be saved into memory to
expand the next level.
o BFS needs lots of time if the solution is far away from the root node.
Example:
In the below tree structure, we have shown the traversing of the tree using BFS algorithm
from the root node S to goal node K. BFS search algorithm traverse in layers, so it will follow
the path which is shown by the dotted arrow, and the traversed path will be:
S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
31
Time Complexity: Time Complexity of BFS algorithm can be obtained by the number of
nodes traversed in BFS until the shallowest Node. Where the d= depth of shallowest solution
and b is a node at every state.
T (b) = 1+b2+b3+.......+ bd= O (bd)
Space Complexity: Space complexity of BFS algorithm is given by the Memory size of
frontier which is O(bd).
Completeness: BFS is complete, which means if the shallowest goal node is at some finite
depth, then BFS will find a solution.
Optimality: BFS is optimal if path cost is a non-decreasing function of the depth of the node.
2. Depth-first Search
o Depth-first search isa recursive algorithm for traversing a tree or graph data structure.
o It is called the depth-first search because it starts from the root node and follows each
path to its greatest depth node before moving to the next path.
o DFS uses a stack data structure for its implementation.
o The process of the DFS algorithm is similar to the BFS algorithm.
Note: Backtracking is an algorithm technique for finding all possible solutions using
recursion.
Advantage:
o DFS requires very less memory as it only needs to store a stack of the nodes on the
path from root node to the current node.
o It takes less time to reach to the goal node than BFS algorithm (if it traverses in the
right path).
Disadvantage:
o There is the possibility that many states keep re-occurring, and there is no guarantee
of finding the solution.
o DFS algorithm goes for deep down searching and sometime it may go to the infinite
loop.
Example:
In the below search tree, we have shown the flow of depth-first search, and it will follow the
order as:
32
Root node--->Left node ----> right node.
It will start searching from root node S, and traverse A, then B, then D and E, after traversing
E, it will backtrack the tree as E has no other successor and still goal node is not found. After
backtracking it will traverse node C and then G, and here it will terminate as it found goal
node.
Completeness: DFS search algorithm is complete within finite state space as it will expand
every node within a limited search tree.
Time Complexity: Time complexity of DFS will be equivalent to the node traversed by the
algorithm. It is given by:
T(n)= 1+ n2+ n3 +.........+ nm=O(nm)
Where, m= maximum depth of any node and this can be much larger than d (Shallowest
solution depth)
Space Complexity: DFS algorithm needs to store only single path from the root node, hence
Optimal: DFS search algorithm is non-optimal, as it may generate a large number of steps or
high cost to reach to the goal node.
3. Depth-Limited Search Algorithm:
A depth-limited search algorithm is similar to depth-first search with a predetermined limit.

Depth-limited search can solve the drawback of the infinite path in the Depth-first search. In
this algorithm, the node at the depth limit will treat as it has no successor nodes further.
Depth-limited search can be terminated with two Conditions of failure:
o Standard failure value: It indicates that problem does not have any solution.
o Cutoff failure value: It defines no solution for the problem within a given depth limit.
33
Advantages:
Depth-limited search is Memory efficient.
Disadvantages:
o Depth-limited search also has a disadvantage of incompleteness.

o It may not be optimal if the problem has more than one solution.
Example:
Completeness: DLS search algorithm is complete if the solution is above the depth-limit.
Time Complexity: Time complexity of DLS algorithm is O(bℓ).
Space Complexity: Space complexity of DLS algorithm is O(b×ℓ).
Optimal: Depth-limited search can be viewed as a special case of DFS, and it is also not
optimal even if ℓ>d.
4. Uniform-cost Search Algorithm:
Uniform-cost search is a searching algorithm used for traversing a weighted tree or graph.
This algorithm comes into play when a different cost is available for each edge. The primary
goal of the uniform-cost search is to find a path to the goal node which has the lowest
cumulative cost. Uniform-cost search expands nodes according to their path costs form the
root node. It can be used to solve any graph/tree where the optimal cost is in demand. A
uniform-cost search algorithm is implemented by the priority queue. It gives maximum
priority to the lowest cumulative cost. Uniform cost search is equivalent to BFS algorithm if
the path cost of all edges is the same.
Advantages:
34
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.
Example:
Completeness:
Uniform-cost search is complete, such as if there is a solution, UCS will find it.
Time Complexity:
Let C* is Cost of the optimal solution, and ε is each step to get closer to the goal node. Then
the number of steps is = C*/ε+1. Here we have taken +1, as we start from state 0 and end to
C*/ε.
Hence, the worst-case time complexity of Uniform-cost search isO(b1 + [C*/ε])/.
Space Complexity:
The same logic is for space complexity so, the worst-case space complexity of Uniform-cost
search is O(b1 + [C*/ε]).
Optimal:
Uniform-cost search is always optimal as it only selects a path with the lowest path cost.
5. Iterative deepening depth-first Search:
35
The iterative deepening algorithm is a combination of DFS and BFS algorithms. This search
algorithm finds out the best depth limit and does it by gradually increasing the limit until a
goal is found.
This algorithm performs depth-first search up to a certain "depth limit", and it keeps
increasing the depth limit after each iteration until the goal node is found.
This Search algorithm combines the benefits of Breadth-first search's fast search and depth-
first search's memory efficiency.
The iterative search algorithm is useful uninformed search when search space is large, and
depth of goal node is unknown.
Advantages:
o Itcombines the benefits of BFS and DFS search algorithm in terms of fast search and
memory efficiency.
Disadvantages:
o The main drawback of IDDFS is that it repeats all the work of the previous phase.
Example:
Following tree structure is showing the iterative deepening depth-first search. IDDFS
algorithm performs various iterations until it does not find the goal node. The iteration
performed by the algorithm is given as:
1'st Iteration-----> A
2'nd Iteration----> A, B, C
3'rd Iteration------>A, B, D, E, C, F, G
4'th Iteration------>A, B, D, H, I, E, C, F, K, G
In the fourth iteration, the algorithm will find the goal node.
36
Completeness:
This algorithm is complete is ifthe branching factor is finite.
Time Complexity:
Let's suppose b is the branching factor and depth is d then the worst-case time complexity
is O(bd).
Space Complexity:
The space complexity of IDDFS will be O(bd).
Optimal:
IDDFS algorithm is optimal if path cost is a non- decreasing function of the depth of the
node.
6. Bidirectional Search Algorithm:
Bidirectional search algorithm runs two simultaneous searches, one form initial state
called as forward-search and other from goal node called as backward-search, to find
the goal node. Bidirectional search replaces one single search graph with two small
subgraphs in which one starts the search from an initial vertex and other starts from
goal vertex. The search stops when these two graphs intersect each other.
Bidirectional search can use search techniques such as BFS, DFS, DLS, etc.
Advantages:
o Bidirectional search is fast.

o Bidirectional search requires less memory
Disadvantages:
o Implementation of the bidirectional search tree is difficult.

o In bidirectional search, one should know the goal state in advance.
Example:
In the below search tree, bidirectional search algorithm is applied. This algorithm divides one
graph/tree into two sub-graphs. It starts traversing from node 1 in the forward direction and
starts from goal node 16 in the backward direction.
The algorithm terminates at node 9 where two searches meet.
37
Completeness: Bidirectional Search is complete if we use BFS in both searches.
Time Complexity: Time complexity of bidirectional search using BFS is O(bd).
Space Complexity: Space complexity of bidirectional search is O(bd).
Optimal: Bidirectional search is Optimal.
Informed Search Algorithms
So far we have talked about the uninformed search algorithms which looked through search
space for all possible solutions of the problem without having any additional knowledge
about search space. But informed search algorithm contains an array of knowledge such as
how far we are from the goal, path cost, how to reach to goal node, etc. This knowledge help
agents to explore less to the search space and find more efficiently the goal node.
The informed search algorithm is more useful for large search space. Informed search
algorithm uses the idea of heuristic, so it is also called Heuristic search.
Heuristics function: Heuristic is a function which is used in Informed Search, and it finds
the most promising path. It takes the current state of the agent as its input and produces the
estimation of how close agent is from the goal. The heuristic method, however, might not
always give the best solution, but it guaranteed to find a good solution in reasonable time.
Heuristic function estimates how close a state is to the goal. It is represented by h(n), and it
calculates the cost of an optimal path between the pair of states. The value of the heuristic
function is always positive.
Admissibility of the heuristic function is given as:
1. h(n) <= h*(n)
Here h(n) is heuristic cost, and h*(n) is the estimated cost. Hence heuristic cost should
be less than or equal to the estimated cost.
Pure Heuristic Search:

38
Pure heuristic search is the simplest form of heuristic search algorithms. It expands nodes
based on their heuristic value h(n). It maintains two lists, OPEN and CLOSED list. In the
CLOSED list, it places those nodes which have already expanded and in the OPEN list, it
places nodes which have yet not been expanded.
On each iteration, each node n with the lowest heuristic value is expanded and generates all
its successors and n is placed to the closed list. The algorithm continues unit a goal state is
found.
In the informed search we will discuss two main algorithms which are given below:
o Best First Search Algorithm(Greedy search)

o A* Search Algorithm
1.) Best-first Search Algorithm (Greedy Search):
Greedy best-first search algorithm always selects the path which appears best at that moment.
It is the combination of depth-first search and breadth-first search algorithms. It uses the
heuristic function and search. Best-first search allows us to take the advantages of both
algorithms. With the help of best-first search, at each step, we can choose the most promising
node. In the best first search algorithm, we expand the node which is closest to the goal node
and the closest cost is estimated by heuristic function, i.e.
1. f(n)= g(n).
Were, h(n)= estimated cost from node n to the goal.
The greedy best first algorithm is implemented by the priority queue.
Best first search algorithm:

o Step 1: Place the starting node into the OPEN list.
o Step 2: If the OPEN list is empty, Stop and return failure.
o Step 3: Remove the node n, from the OPEN list which has the lowest value of h(n),
and places it in the CLOSED list.
o Step 4: Expand the node n, and generate the successors of node n.
o Step 5: Check each successor of node n, and find whether any node is a goal node or
not. If any successor node is goal node, then return success and terminate the search,
else proceed to Step 6.
o Step 6: For each successor node, algorithm checks for evaluation function f(n), and
then check if the node has been in either OPEN or CLOSED list. If the node has not
been in both list, then add it to the OPEN list.
39
o Step 7: Return to Step 2.
Advantages:
o Best first search can switch between BFS and DFS by gaining the advantages of both
the algorithms.
o This algorithm is more efficient than BFS and DFS algorithms.
Disadvantages:
o It can behave as an unguided depth-first search in the worst case scenario.
o It can get stuck in a loop as DFS.
o This algorithm is not optimal.
Example:
Consider the below search problem, and we will traverse it using greedy best-first search. At
each iteration, each node is expanded using evaluation function f(n)=h(n) , which is given in
the below table.
In this search example, we are using two lists which are OPEN and CLOSED Lists.
Following are the iteration for traversing the above example.
40
Expand the nodes of S and put in the CLOSED list
Initialization: Open [A, B], Closed [S]
Iteration 1: Open [A], Closed [S, B]
Iteration 2: Open [E, F, A], Closed [S, B]

: Open [E, A], Closed [S, B, F]
Iteration 3: Open [I, G, E, A], Closed [S, B, F]

: Open [I, E, A], Closed [S, B, F, G]
Hence the final solution path will be: S----> B----->F----> G
Time Complexity: The worst case time complexity of Greedy best first search is O(bm).
Space Complexity: The worst case space complexity of Greedy best first search is O(bm).
Where, m is the maximum depth of the search space.
Complete: Greedy best-first search is also incomplete, even if the given state space is finite.
Optimal: Greedy best first search algorithm is not optimal.
2.) A* Search Algorithm:
A* search is the most commonly known form of best-first search. It uses heuristic function
h(n), and cost to reach the node n from the start state g(n). It has combined features of UCS
and greedy best-first search, by which it solve the problem efficiently. A* search algorithm
finds the shortest path through the search space using the heuristic function. This search
algorithm expands less search tree and provides optimal result faster. A* algorithm is similar
to UCS except that it uses g(n)+h(n) instead of g(n).
In A* search algorithm, we use search heuristic as well as the cost to reach the node. Hence
we can combine both costs as following, and this sum is called as a fitness number.
41
At each point in the search space, only those node is expanded which have the lowest value
of f(n), and the algorithm terminates when the goal node is found.
Algorithm of A* search:
Step1: Place the starting node in the OPEN list.
Step 2: Check if the OPEN list is empty or not, if the list is empty then return failure and
stops.
Step 3: Select the node from the OPEN list which has the smallest value of evaluation
function (g+h), if node n is goal node then return success and stop, otherwise
Step 4: Expand node n and generate all of its successors, and put n into the closed list. For
each successor n', check whether n' is already in the OPEN or CLOSED list, if not then
compute evaluation function for n' and place into Open list.
Step 5: Else if node n' is already in OPEN and CLOSED, then it should be attached to the
back pointer which reflects the lowest g(n') value.
Step 6: Return to Step 2.
Advantages:
o A* search algorithm is the best algorithm than other search algorithms.
o A* search algorithm is optimal and complete.
o This algorithm can solve very complex problems.
Disadvantages:
o It does not always produce the shortest path as it mostly based on heuristics and
approximation.
o A* search algorithm has some complexity issues.
o The main drawback of A* is memory requirement as it keeps all generated nodes in
the memory, so it is not practical for various large-scale problems.
Example:
42
In this example, we will traverse the given graph using the A* algorithm. The heuristic value
of all states is given in the below table so we will calculate the f(n) of each state using the
formula f(n)= g(n) + h(n), where g(n) is the cost to reach any node from start state.
Here we will use OPEN and CLOSED list.
Solution:
Initialization: {(S, 5)}
Iteration1: {(S--> A, 4), (S-->G, 10)}
Iteration2: {(S--> A-->C, 4), (S--> A-->B, 7), (S-->G, 10)}
Iteration3: {(S--> A-->C--->G, 6), (S--> A-->C--->D, 11), (S--> A-->B, 7), (S-->G, 10)}
Iteration 4 will give the final result, as S--->A--->C--->G it provides the optimal path with
cost 6.
Points to remember:
43
o A* algorithm returns the path which occurred first, and it does not search for all
remaining paths.
o The efficiency of A* algorithm depends on the quality of heuristic.
o A* algorithm expands all nodes which satisfy the condition f(n)<="" li="">
Complete: A* algorithm is complete as long as:
o Branching factor is finite.

o Cost at every action is fixed.
Optimal: A* search algorithm is optimal if it follows below two conditions:
o Admissible: the first condition requires for optimality is that h(n) should be an
admissible heuristic for A* tree search. An admissible heuristic is optimistic in nature.
o Consistency: Second required condition is consistency for only A* graph-search.
If the heuristic function is admissible, then A* tree search will always find the least cost path.
Time Complexity: The time complexity of A* search algorithm depends on heuristic

function, and the number of nodes expanded is exponential to the depth of solution d. So the
time complexity is O(b^d), where b is the branching factor.
Space Complexity: The space complexity of A* search algorithm is O(b^d)
Problem Characteristics
In order to choose the most appropriate method(s) for a particular problem must analyse the problem
along several dimensions.
1. Is the problem decomposable into a set of independent smaller sub problems?
Example: Decomposable Problem
Decomposable problems can be solved by the divide-and-conquer technique. In divide and
conquer technique, divide the problem in to sub-problems, find the solutions for the sub-
problems. Finally, integrate the solutions for the sub-problems, we will get the solution for the
original problem. Suppose we want to solve the problem of computing the integral of the following
expression
∫(x2+ 3x + sin2x * cos2x) dx
44
Example: Non-Decomposable problem

There are non-decomposable problems. For example, Block world problem is non-decomposable.
2. Can Solution Steps be ignored or atleast undone if they prove to be unwise?

In real life, there are three important types of problems:
◦ Ignorable ( theorem proving)
◦ Recoverable ( 8-puzzle)
◦ Irrecoverable ( Chess)
Ignorable ( theorem proving)
Suppose we have proved some lemma in order to prove a theorem and eventually realized that
lemma is no help at all, then ignore it and prove another lemma.
• It can be solved by using simple control strategy?
Recoverable ( 8-puzzle)
Objective of 8 puzzle game is to rearrange a given initial configuration of eight numbered
tiles on 3 X 3 board (one place is empty) into a given final configuration (goal state).
Rearrangement is done by sliding one of the tiles into empty square.
2 8 3 1 2 3
1 6 4 8 4
7 5
45
\ 7 6 5
Initial state Goal state
 Solved by backtracking
Irrecoverable ( Chess)
• A stupid move cannot be undone.
• Can be solved by planning process.
3. Is the universe predictable?
There are two types of problems. Certain outcome and uncertain outcome.
Certain outcome (8-puzzle problem)

Able to plan the entire sequence of moves.
Uncertain outcome (Bridge game)

It is not possible to plan the entire sequence of actions. We do not know exactly where all the
cards are or what the other players will do on their turns. To overcome this, investigate several plans
and use probabilities of the various outcomes to choose a plan that has the highest estimated
probability of leading to a good score on the hand.
4. Is a good solution absolute or relative?

There are two types of problems
• Any path problem
• Best path problem
Any path problem
• Any path problems can often be solved in a reasonable amount of time by using heuristics
that suggest good paths to explore.
• Consider a problem of answering questions based on the database of simple facts.
1. Marcus was a man.
2. Marcus was a Pompeian.
3. Marcus was born in 40AD.
4. All men are mortal.
5. All Pompeian died in 79 AD.
6. No mortal lives longer than 150 years.
7. It is now 1991 AD.
Suppose we ask a question ,”Is Marcus is alive?”. From the facts given we can easily derive an
answer to the question.
1. Marcus was a man. 1
4. All men are mortal. 4
8. Marcus was a mortal. 1, 4
3. Marcus was born in 40AD. 3
7. It is now 1991 AD. 7
9. Marcus age is 1951 years. 3, 7
6. No mortal lives longer than 150 years. 6
10. Marcus was dead 6.8.9
OR
7. It is now 1991 AD. 7

5. All Pompeian died in 79 AD. 5
11. All Pompeian are dead now. 7, 5
2. Marcus was a Pompeian. 2
10. Marcus was dead 11, 2
46
Either of two reasoning paths will lead to the answer. We need to find only the answer to the question.
No need to go back and see if some other path might also lead to a solution.
Best path problem
In travelling salesman problem, our goal is to find the shortest route that visits each city
exactly once.
This path is not a best solution for the salesman problem.
Best path problems are computationally harder than any path problem.
5. Is the solution a state or path?
State
Finding a consistent interpretation for the sentence “The bank president ate a dish of pasta
salad with the fork”. We need to find the interpretation but not the record of the processing.
Path
In water jug problem, it is not sufficient to report that the problem is solved and the goal is
reached, it is (2,0). For this problem, we need the path from the initial state to the goal state.
6. What is the role of knowledge?

For eg, Chess playing
Knowledge about the legal moves of the problem is needed. Without the knowledge, we
cannot able to solve the problem.
7. Does the task require Interaction with a person?
Solitary in which the computer is given a problem description and produces an answer with no
intermediate communication and no demand for an explanation of the reasoning process.
Conversational in which there is intermediate communication between a person and the computer,
either to provide additional assistance to the computer or to provide additional information to the user,
or both.
47
Problem solving methods

In artificial intelligence, problems can be solved by using searching algorithms, evolutionary
computations, knowledge representations, etc. In general, searching is referred to as finding
information one needs.
The process of problem-solving using searching consists of the following steps.
 Define the problem
 Analyze the problem
 Identification of possible solutions
 Choosing the optimal solution
 Implementation
Hill Climbing Algorithm in Artificial Intelligence

o Hill climbing algorithm is a local search algorithm which continuously moves in the
direction of increasing elevation/value to find the peak of the mountain or best
solution to the problem. It terminates when it reaches a peak value where no neighbor
has a higher value.
o Hill climbing algorithm is a technique which is used for optimizing the mathematical
problems. One of the widely discussed examples of Hill climbing algorithm is
Traveling-salesman Problem in which we need to minimize the distance traveled by
the salesman.
o It is also called greedy local search as it only looks to its good immediate neighbor
state and not beyond that.
o A node of hill climbing algorithm has two components which are state and value.
o Hill Climbing is mostly used when a good heuristic is available.
o In this algorithm, we don't need to maintain and handle the search tree or graph as it
only keeps a single current state.
Features of Hill Climbing:
Following are some main features of Hill Climbing Algorithm:
o Generate and Test variant: Hill Climbing is the variant of Generate and Test
method. The Generate and Test method produce feedback which helps to decide
which direction to move in the search space.
o Greedy approach: Hill-climbing algorithm search moves in the direction which
optimizes the cost.
48
o No backtracking: It does not backtrack the search space, as it does not remember the
previous states.
State-space Diagram for Hill Climbing:
The state-space landscape is a graphical representation of the hill-climbing algorithm which

is showing a graph between various states of algorithm and Objective function/Cost.
On Y-axis we have taken the function which can be an objective function or cost function,
and state-space on the x-axis. If the function on Y-axis is cost then, the goal of search is to
find the global minimum and local minimum. If the function of Y-axis is Objective function,
then the goal of the search is to find the global maximum and local maximum.
Different regions in the state space landscape:
Local Maximum: Local maximum is a state which is better than its neighbor states, but there
is also another state which is higher than it.
Global Maximum: Global maximum is the best possible state of state space landscape. It has
the highest value of objective function.
Current state: It is a state in a landscape diagram where an agent is currently present.
Flat local maximum: It is a flat space in the landscape where all the neighbor states of
current states have the same value.
Shoulder: It is a plateau region which has an uphill edge.
Types of Hill Climbing Algorithm:

o Simple hill Climbing:
o Steepest-Ascent hill-climbing:
o Stochastic hill Climbing:
49
1. Simple Hill Climbing:
Simple hill climbing is the simplest way to implement a hill climbing algorithm. It only
evaluates the neighbor node state at a time and selects the first one which optimizes
current cost and set it as a current state. It only checks it's one successor state, and if it
finds better than the current state, then move else be in the same state. This algorithm has the
following features:
o Less time consuming

o Less optimal solution and the solution is not guaranteed
Algorithm for Simple Hill Climbing:

o Step 1: Evaluate the initial state, if it is goal state then return success and Stop.
o Step 2: Loop Until a solution is found or there is no new operator left to apply.
o Step 3: Select and apply an operator to the current state.
o Step 4: Check new state:
a. If it is goal state, then return success and quit.

b. Else if it is better than the current state then assign new state as a current state.
c. Else if not better than the current state, then return to step2.
o Step 5: Exit.
2. Steepest-Ascent hill climbing:
The steepest-Ascent algorithm is a variation of simple hill climbing algorithm. This algorithm
examines all the neighboring nodes of the current state and selects one neighbor node which
is closest to the goal state. This algorithm consumes more time as it searches for multiple
neighbors
Algorithm for Steepest-Ascent hill climbing:

o Step 1: Evaluate the initial state, if it is goal state then return success and stop, else
make current state as initial state.
o Step 2: Loop until a solution is found or the current state does not change.
a. Let SUCC be a state such that any successor of the current state will be better
than it.
b. For each operator that applies to the current state:
a. Apply the new operator and generate a new state.
50
b. Evaluate the new state.

c. If it is goal state, then return it and quit, else compare it to the SUCC.
d. If it is better than SUCC, then set new state as SUCC.
e. If the SUCC is better than the current state, then set current state to
SUCC.
o Step 5: Exit.
3. Stochastic hill climbing:
Stochastic hill climbing does not examine for all its neighbor before moving. Rather, this
search algorithm selects one neighbor node at random and decides whether to choose it as a
current state or examine another state.
Problems in Hill Climbing Algorithm:
1. Local Maximum: A local maximum is a peak state in the landscape which is better than
each of its neighboring states, but there is another state also present which is higher than the
local maximum.
Solution: Backtracking technique can be a solution of the local maximum in state space
landscape. Create a list of the promising path so that the algorithm can backtrack the search
space and explore other paths as well.
2. Plateau: A plateau is the flat area of the search space in which all the neighbor states of
the current state contains the same value, because of this algorithm does not find any best
direction to move. A hill-climbing search might be lost in the plateau area.
Solution: The solution for the plateau is to take big steps or very little steps while searching,
to solve the problem. Randomly select a state which is far away from the current state so it is
possible that the algorithm could find non-plateau region.
51
3. Ridges: A ridge is a special form of the local maximum. It has an area which is higher than
its surrounding areas, but itself has a slope, and cannot be reached in a single move.
Solution: With the use of bidirectional search, or by moving in different directions, we can
improve this problem.
Simulated Annealing:
A hill-climbing algorithm which never makes a move towards a lower value guaranteed to be
incomplete because it can get stuck on a local maximum. And if algorithm applies a random
walk, by moving a successor, then it may complete but not efficient. Simulated Annealing is
an algorithm which yields both efficiency and completeness.
In mechanical term Annealing is a process of hardening a metal or glass to a high

temperature then cooling gradually, so this allows the metal to reach a low-energy crystalline
state. The same process is used in simulated annealing in which the algorithm picks a random
move, instead of picking the best move. If the random move improves the state, then it
follows the same path. Otherwise, the algorithm follows the path which has a probability of
less than 1 or it moves downhill and chooses another path.
Constraints satisfaction
A constraint satisfaction problem (CSP) consists of
 a set of variables,
 a domain for each variable, and
 a set of constraints.
The aim is to choose a value for each variable so that the resulting possible world satisfies the
constraints; we want a model of the constraints.
A finite CSP has a finite set of variables and a finite domain for each variable. Many of the
methods considered in this chapter only work for finite CSPs, although some are designed for
infinite, even continuous, domains.
The multidimensional aspect of these problems, where each variable can be seen as a separate
dimension, makes them difficult to solve but also provides structure that can be exploited.
Given a CSP, there are a number of tasks that can be performed:
 Determine whether or not there is a model.
 Find a model.
 Find all of the models or enumerate the models.
 Count the number of models.
 Determine whether some statement holds in all models.
Solving Constraint Satisfaction Problems
The requirements to solve a constraint satisfaction problem (CSP) is:
52
 A state-space
 The notion of the solution.
A state in state-space is defined by assigning values to some or all variables such as

{X1=v1, X2=v2, and so on…}.
An assignment of values to a variable can be done in three ways:
 Consistent or Legal Assignment: An assignment which does not violate any

constraint or rule is called Consistent or legal assignment.
 Complete Assignment: An assignment where every variable is assigned with a value,
and the solution to the CSP remains consistent. Such assignment is known as
Complete assignment.
 Partial Assignment: An assignment which assigns values to some of the variables
only. Such type of assignments are called Partial assignments.
Types of Domains in CSP

There are following two types of domains which are used by the variables :
 Discrete Domain: It is an infinite domain which can have one state for multiple
variables. For example, a start state can be allocated infinite times for each variable.
 Finite Domain: It is a finite domain which can have continuous states describing one
domain for one specific variable. It is also called a continuous domain.
Constraint Types in CSP

With respect to the variables, basically there are following types of constraints:
 Unary Constraints: It is the simplest type of constraints that restricts the value of a
single variable.
 Binary Constraints: It is the constraint type which relates two variables. A
value x2 will contain a value which lies between x1 and x3.
 Global Constraints: It is the constraint type which involves an arbitrary number of
variables.
Some special types of solution algorithms are used to solve the following types of
constraints:
 Linear Constraints: These type of constraints are commonly used in linear

programming where each variable containing an integer value exists in linear form
only.
 Non-linear Constraints: These type of constraints are used in non-linear
programming where each variable (an integer value) exists in a non-linear form.
Note: A special constraint which works in real-world is known as Preference constraint.

Constraint Propagation
In local state-spaces, the choice is only one, i.e., to search for a solution. But in CSP, we have
two choices either:
 We can search for a solution or
53
 We can perform a special type of inference called constraint propagation.
Constraint propagation is a special type of inference which helps in reducing the legal
number of values for the variables. The idea behind constraint propagation is local
consistency.
In local consistency, variables are treated as nodes, and each binary constraint is treated as
an arc in the given problem. There are following local consistencies which are discussed
below:
 Node Consistency: A single variable is said to be node consistent if all the values in
the variable’s domain satisfy the unary constraints on the variables.
 Arc Consistency: A variable is arc consistent if every value in its domain satisfies the
binary constraints of the variables.
 Path Consistency: When the evaluation of a set of two variable with respect to a
third variable can be extended over another variable, satisfying all the binary
constraints. It is similar to arc consistency.
 k-consistency: This type of consistency is used to define the notion of stronger forms
of propagation. Here, we examine the k-consistency of the variables.
CSP Problems
Constraint satisfaction includes those problems which contains some constraints while
solving the problem. CSP includes the following problems:
 Graph Coloring: The problem where the constraint is that no adjacent sides can have
the same color.
 Sudoku Playing: The gameplay where the constraint is that no number from 0-9 can
be repeated in the same row or column.
54
 n-queen problem: In n-queen problem, the constraint is that no queen should be

placed either diagonally, in the same row or column.
Note: The n-queen problem is already discussed in Problem-solving in AI section.
 Crossword: In crossword problem, the constraint is that there should be the correct
formation of the words, and it should be meaningful.
 Latin square Problem: In this game, the task is to search the pattern which is
occurring several times in the game. They may be shuffled but will contain the same
digits.
55
 Cryptarithmetic Problem: This problem has one most important constraint that is,
we cannot assign a different digit to the same character. All digits should contain a
unique alphabet.
Measure of performance and analysis of search algorithms:

The performance measure of an algorithm should be measured. Consequently, There are four
ways to measure the performance of an algorithm:
Completeness: It measures if the algorithm guarantees to find a solution (if any solution
exist).
Optimality: It measures if the strategy searches for an optimal solution.
Time Complexity: The time taken by the algorithm to find a solution.
Space Complexity: Amount of memory required to perform a search.
The complexity of an algorithm depends on branching factor or maximum number of
successors, depth of the shallowest goal node (i.e., number of steps from root to the path) and
the maximum length of any path in a state space.
Means-Ends Analysis in Artificial Intelligence

o We have studied the strategies which can reason either in forward or backward, but a
mixture of the two directions is appropriate for solving a complex and large problem.
Such a mixed strategy, make it possible that first to solve the major part of a problem
and then go back and solve the small problems arise during combining the big parts of
the problem. Such a technique is called Means-Ends Analysis.
o Means-Ends Analysis is problem-solving techniques used in Artificial intelligence for
limiting search in AI programs.
o It is a mixture of Backward and forward search technique.
o The MEA technique was first introduced in 1961 by Allen Newell, and Herbert A.
Simon in their problem-solving computer program, which was named as General
Problem Solver (GPS).
56
o The MEA analysis process centered on the evaluation of the difference between the
current state and goal state.
How means-ends analysis Works:
The means-ends analysis process can be applied recursively for a problem. It is a strategy to
control search in problem-solving. Following are the main Steps which describes the working
of MEA technique for solving a problem.
a. First, evaluate the difference between Initial State and final State.
b. Select the various operators which can be applied for each difference.
c. Apply the operator at each difference, which reduces the difference between the
current state and goal state.
Operator Subgoaling
In the MEA process, we detect the differences between the current state and goal state. Once
these differences occur, then we can apply an operator to reduce the differences. But
sometimes it is possible that an operator cannot be applied to the current state. So we create
the subproblem of the current state, in which operator can be applied, such type of backward
chaining in which operators are selected, and then sub goals are set up to establish the
preconditions of the operator is called Operator Subgoaling.
Algorithm for Means-Ends Analysis:
Let's we take Current state as CURRENT and Goal State as GOAL, then following are the
steps for the MEA algorithm.
o Step 1: Compare CURRENT to GOAL, if there are no differences between both then
return Success and Exit.
o Step 2: Else, select the most significant difference and reduce it by doing the
following steps until the success or failure occurs.
a. Select a new operator O which is applicable for the current difference, and if there is
no such operator, then signal failure.
b. Attempt to apply operator O to CURRENT. Make a description of two states.
i) O-Start, a state in which O?s preconditions are satisfied.
ii) O-Result, the state that would result if O were applied In O-start.
c. If
(First-Part <------ MEA (CURRENT, O-START)
57
And
(LAST-Part <----- MEA (O-Result, GOAL), are successful, then signal
Success and return the result of combining FIRST-PART, O, and LAST-
PART.
The above-discussed algorithm is more suitable for a simple problem and not adequate for
solving complex problems.
Example of Mean-Ends Analysis:
Let's take an example where we know the initial state and goal state as given below. In this
problem, we need to get the goal state by finding differences between the initial state and
goal state and applying operators.
Solution:
To solve the above problem, we will first find the differences between initial states and goal
states, and for each difference, we will generate a new state and will apply the operators. The
operators we have for this problem are:
o Move
o Delete
o Expand
1. Evaluating the initial state: In the first step, we will evaluate the initial state and will
compare the initial and Goal state to find the differences between both states.
2. Applying Delete operator: As we can check the first difference is that in goal state there
is no dot symbol which is present in the initial state, so, first we will apply the Delete
operator to remove this dot.
58
3. Applying Move Operator: After applying the Delete operator, the new state occurs which
we will again compare with goal state. After comparing these states, there is another
difference that is the square is outside the circle, so, we will apply the Move Operator.
4. Applying Expand Operator: Now a new state is generated in the third step, and we will
compare this state with the goal state. After comparing the states there is still one difference
which is the size of the square, so, we will apply Expand operator, and finally, it will
generate the goal state.
Genetic Algorithm
Genetic Algorithm is a part of Evolutionary Algorithms, specifically to generate high-quality
solutions to optimization and search problems by relying on biologically inspired operators
such as mutation, crossover, and selection.
Genetic algorithm is majorly used for 2 purposes-
1. Search
2. Optimisation
Genetic algorithms use an iterative process to arrive at the best solution. Finding the best
solution out of multiple best solutions (best of best). Compared with Natural selection, it
is natural for the fittest to survive in comparison with others.
Now let’s try to grab some pointers from the evolution side to clearly correlate with
genetic algorithms.
59
 Evolution usually starts from a population of randomly generated individuals in

the form of iteration. (Iteration will lead to a new generation).
 In every iteration or generation, the fitness of each individual is determined to
select the fittest.
 Genome fittest individuals selected are mutated or altered to form a new
generation, and the process continues until the best solution has reached.
The process terminates under 2 scenarios-
1. When maximum number of generations have been created

2. Fitness level reached is sufficient.
Relating it to the Optimisation scenario, we need to identify the Genetic
Representation of our solution domain or business problem we need to solve. Evaluation
criteria i.e., Fitness Function to decide the worth of a solution.
Also Read: React JS Tutorial
For example:
 We need to maximize the profit (Fitness Function) by increasing sales (Genetic

representation) of the product.
 We need to find the best model hyperparameters (Fitness function) for the
classification algorithms i.e., Fine-tuning to yield the best prediction
 Optimum number of feature (fitness function) selection for building the
machine learning model (Genetic representation).
The process can be broadly divided as following:
1. Initialisation:
Randomly generate a population with multiple chromosomes. Gene is the smallest unit
and can be referred to as a set of characteristics (variables). We aim to join the Genes to
obtain the Chromosomes(solution). The chromosome itself represents one candidate
solution abstractly. The generation of Chromosome is user-defined (combination of
numbers between 0 and 5 or only binary numbers).
2. Defining the fit function:
Now we need to define the evaluation criteria for best chromosomes(solution). Each
chromosome is assigned with a fitness score by the fitness function, which represents the
goodness of the solution. Let’s say the fitness function is the sum of all the genes. Hence,
60
the chromosome with the maximum sum is the fittest. In our case, the chromosome has a
sum of 12.
3. Selection:
Selecting the top 2 fittest chromosomes for creating the next generation. These will act as
parents to generate offspring for the next generation which will naturally inherit the
strong features. Two pairs of individuals (parents) are selected based on their fitness
scores. Other chromosomes are dropped. Here are some of the methods of parent
selection-
1. Roulette Wheel Selection

2. Rank Selection
3. Steady State Selection
4. Tournament Selection
5. Elitism Selection
4. Crossover:
Crossover is the equivalent of two parents having a child. Each chromosome contributes a
certain number of genes to the new individual. Offspring are created by exchanging the
genes of parents among themselves until the crossover point is reached.
1. Single point crossover.

2. k-point crossover (k ≥ 1)
3. Uniform crossover.
5. Mutation:
To avoid the duplicity(crossover generates offspring similar to parents) and to enhance

the diversity in offspring we perform mutation. The mutation operator solves this problem
by changing the value of some features in the offspring at random.
These steps are repeated until the termination criteria is met.
When to apply Genetic Algorithm:
 There are multiple local optima

 The objective function is not smooth (so derivative methods cannot be applied)
 Number of parameters is very large
61
 Objective function is noisy or stochastic
Advantages of Genetic Algorithm:
 Concept is easy to understand

 Modular, separate from application
 Answer gets better with time
 Inherently parallel; easily distributed
 Genetic algorithms work on the Chromosome, which is an encoded version of
potential solutions’ parameters, rather the parameters themselves.
 Genetic algorithms use fitness score, which is obtained from objective
functions, without other derivative or auxiliary information
Disadvantages:
 Genetic Algorithms might be costly in computational terms since the evaluation

of each individual requires the training of a model.
 These algorithms can take a long time to converge since they have a stochastic
nature.
62

Ai Chap 1

Uploaded by

Copyright:

Available Formats

Ai Chap 1

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ai Chap 1

Uploaded by

Copyright:

Available Formats

191AIC403T - ARTIFICIAL INTELLIGENCEUnit-I

1.1 Introduction to AI:

What is artificial intelligence?

 Artificial Intelligence is the branch of computer science concerned with making

Systems that think like humans Systems that think rationally

Systems that act like humans Systems that act rationally

 To Implement Human Intelligence in Machines − Creating systems that

Programming Without and With AI

Programming Without AI Programming With AI

AI programs can absorb new modifications by

Modification is not quick and easy. It may

 Its volume is huge, next to unimaginable.

 It should be perceivable by the people who provide it.

Types of Artificial Intelligence:

AI type-1: Based on Capabilities

Artificial Intelligence type-2: Based on functionality

Following are the main four rules for an AI agent:

o Rule 1: An AI agent must have the ability to perceive the environment.

The rationality of an agent is measured by its performance measure. Rationality can be

o Performance measure which defines the success criterion.

o Simple Reflex Agent

1. Simple Reflex agent:

2. Model-based reflex agent

a. How the world evolves

a. Learning element: It is responsible for making improvements by learning

PEAS for self-driving cars:

Let's suppose a self-driving car then PEAS representation will be:

Performance: Safety, time, legal drive, comfort

Environment: Roads, other vehicles, road signs, pedestrian

Actuators: Steering, accelerator, brake, signal, horn

Sensors: Camera, GPS, speedometer, odometer, accelerometer, sonar.

Example of Agents with their PEAS representation

Agent Performance Environment Actuators Sensors

o Security o Carpet Extractor o Cliff sensor

o Various o Bump Sensor

Consider, Player A is a computer, Player B is human, and Player C is an interrogator.

The questions and answers can be like:

Interrogator: Are you a computer?

Interrogator: Multiply two large numbers such as (256896489*456725896)

Player A: Long pause and give the wrong answer.

Chatbots to attempt the Turing test:

The Chinese Room Argument:

Features required for a machine to pass the Turing test:

To build a system to solve a problem

1. Define the problem precisely

2. Analyse the problem

Mouse Path Problem

Water Jug Problem

11 (0,2) (2,0) Pour the 2 gallons from 3-gallon jug

12 (2,y) (0,y) Empty the 2 gallons in the 4-gallon jug

Gallons in Gallons in Rule applied

Path Finding Problem

Problem-solving in Artificial Intelligence:

 Goal Formulation: It is the first and simplest step in problem-solving. It organizes

Some Toy Problems

Following steps are involved in this formulation:

 States: Arrangement of any 0 to 8 queens on the chessboard.

In this formulation, there is approximately 1.8 x 1014 possible sequence to investigate.

Following steps are involved in this formulation