Course Branch Subject Subject Name Semester NOTES

Name Code

B. Tech CS CS-305 ARTIFICIAL INTELLIGENCE 4TH UNIT 1

Course Branch Subject Subject Name Semester NOTES
Name Code

[Link] CS CS-305 ARTIFICIAL INTELLIGENCE 4TH UNIT 1

Introduction:

➢ Artificial Intelligence is concerned with the design of intelligence in an artificial

device. The term was coined by John McCarthy in 1956.
➢ Intelligence is the ability to acquire, understand and apply the knowledge to
achieve goals in the world.
➢ AI is the study of the mental faculties through the use of computational models

➢ AI is the study of intellectual/mental processes as computational processes.

➢ AI program will demonstrate a high level of intelligence to a degree that
equals or exceeds the intelligence required of a human in performing some task.
➢ AI is unique, sharing borders with Mathematics, Computer
Science, Philosophy, Psychology, Biology, Cognitive Science and many
others.
➢ Although there is no clear definition of AI or even Intelligence, it can be described as
an attempt to build machines that like humans can think and act, able to learn and use
knowledge to solve problems on their own.

Topic:History of Artificial Intelligence:

Artificial Intelligence is not a new word and not a new technology for researchers. This technology
is much older than you would imagine.
Maturation of Artificial Intelligence (1943-1952)

o Year 1943: The first work which is now recognized as AI was done by Warren
McCulloch and Walter pits in 1943. They proposed a model of artificial
neurons.
o Year 1949: Donald Hebb demonstrated an updating rule for modifying the
connection strength between neurons. His rule is now called Hebbian
learning.
o Year 1950: The Alan Turing who was an English mathematician and pioneered
Machine learning in 1950. Alan Turing publishes "Computing Machinery
and Intelligence" in which he proposed a test. The test can check the
machine's ability to exhibit intelligent behavior equivalent to human
intelligence, called a Turing test.

The birth of Artificial Intelligence (1952-1956)

o Year 1955: An Allen Newell and Herbert A. Simon created the "first artificial
intelligence program"Which was named as "Logic Theorist". This program
had proved 38 of 52 Mathematics theorems, and find new and more elegant
proofs for some theorems.
o Year 1956: The word "Artificial Intelligence" first adopted by American
Computer scientist John McCarthy at the Dartmouth Conference. For the first
time, AI coined as an academic field.

At that time high-level computer languages such as FORTRAN, LISP, or COBOL were invented.
And the enthusiasm for AI was very high at that time.
The golden years-Early enthusiasm (1956-1974)

o Year 1966: The researchers emphasized developing algorithms which can

solve mathematical problems. Joseph Weizenbaum created the first chatbot in
1966, which was named as ELIZA.
o Year 1972: The first intelligent humanoid robot was built in Japan which was
named as WABOT-1.

The first AI winter (1974-1980)

o The duration between years 1974 to 1980 was the first AI winter duration. AI
winter refers to the time period where computer scientist dealt with a severe
shortage of funding from government for AI researches.
o During AI winters, an interest of publicity on artificial intelligence was
decreased.

A boom of AI (1980-1987)

o Year 1980: After AI winter duration, AI came back with "Expert System".
Expert systems were programmed that emulate the decision-making ability of a
human expert.
o In the Year 1980, the first national conference of the American Association of
Artificial Intelligence was held at Stanford University.

The second AI winter (1987-1993)

o The duration between the years 1987 to 1993 was the second AI Winter
duration.
 o Again Investors and government stopped in funding for AI research as due to
high cost but not efficient result. The expert system such as XCON was very
cost effective.

The emergence of intelligent agents (1993-2011)

o Year 1997: In the year 1997, IBM Deep Blue beats world chess champion,
Gary Kasparov, and became the first computer to beat a world chess champion.
o Year 2002: for the first time, AI entered the home in the form of Roomba, a
vacuum cleaner.
o Year 2006: AI came in the Business world till the year 2006. Companies like
Facebook, Twitter, and Netflix also started using AI.

Deep learning, big data and artificial general intelligence (2011-present)

o Year 2011: In the year 2011, IBM's Watson won jeopardy, a quiz show, where
it had to solve the complex questions as well as riddles. Watson had proved that
it could understand natural language and can solve tricky questions quickly.
o Year 2012: Google has launched an Android app feature "Google now", which
was able to provide information to the user as a prediction.
o Year 2014: In the year 2014, Chatbot "Eugene Goostman" won a competition
in the infamous "Turing test."
 o Year 2018: The "Project Debater" from IBM debated on complex topics with
two master debaters and also performed extremely well.
o Google has demonstrated an AI program "Duplex" which was a virtual assistant
and which had taken hairdresser appointment on call, and lady on other side
didn't notice that she was talking with the machine.

Sub Areas of AI:

1) Game Playing

Deep Blue Chess program beat world champion Gary Kasparov

2) Speech Recognition

PEGASUS spoken language interface to American Airlines' EAASY SABRE reservation

system, which allows users to obtain flight information and make reservations over the

telephone. The 1990s has seen significant advances in speech recognition so that limited
systems are now successful.
3) Computer Vision

Face recognition programs in use by banks, government, etc. The ALVINN system
from CMU autonomously drove a van from Washington, D.C. to San Diego (all but 52 of
2,849 miles), averaging 63 mph day and night, and in all weather conditions. Handwriting
recognition, electronics and manufacturing inspection, photo interpretation, baggage
inspection, reverse engineering to automatically construct a 3D geometric model.
4) Expert Systems

Application-specific systems that rely on obtaining the knowledge of human experts in an

area and programming that knowledge into a system.
a. Diagnostic Systems: MYCIN system for diagnosing bacterial infections of the blood
and suggesting treatments. Intellipath pathology diagnosis system (AMA approved).
Pathfinder medical diagnosis system, which suggests tests and makes diagnoses. Whirlpool
customer assistance center.
b. System Configuration
DEC's XCON system for custom hardware configuration. Radiotherapy treatment planning.
c. Financial Decision Making
Credit card companies, mortgage companies, banks, and the U.S. government employ
AI systems to detect fraud and expedite financial transactions. For example, AMEX
credit check.
d. Classification Systems
Put information into one of a fixed set of categories using several sources of information.
E.g., financial decision making systems. NASA developed a system for classifying very
faint areas in astronomical images into either stars or galaxies with very high accuracy by
learning from human experts' classifications.
5) Mathematical Theorem Proving

Use inference methods to prove new theorems.

6) Natural Language Understanding

AltaVista's translation of web pages. Translation of Catepillar Truck manuals into 20 languages
7) Scheduling and Planning
Automatic scheduling for manufacturing. DARPA's DART system used in Desert Storm and
Desert Shield operations to plan logistics of people and supplies. American Airlines rerouting
contingency planner. European space agency planning and scheduling of spacecraft
assembly, integration and verification.
8) Artificial Neural Networks:

9) Machine Learning
 Building AI Systems:

1) Perception

Intelligent biological systems are physically embodied in the world and experience the world
through their sensors (senses). For an autonomous vehicle, input might be images from a
camera and range information from a rangefinder. For a medical diagnosis system,
perception is the set of symptoms and test results that have been obtained and input to the
system manually.
2) Reasoning

Inference, decision-making, classification from what is sensed and what the internal "model"
is ofthe world. Might be a neural network, logical deduction system, Hidden Markov Model
induction,heuristic searching a problem space, Bayes Network inference, genetic algorithms,
etc.
Includes areas of knowledge representation, problem solving, decision theory, planning, game
theory, machine learning, uncertainty reasoning, etc.
3) Action

Biological systems interact within their environment by actuation, speech, etc. All behavior
iscentered around actions in the world. Examples include controlling the steering of a Mars rover
or autonomous vehicle, or suggesting tests and making diagnoses for a medical diagnosis
.
system. Includes areas of robot actuation, natural language generation, and speech synthesis.
The definitions of AI:

a) "The exciting new effort to make b) "The study of mental faculties

computers think . . . machines with through the use of computational
minds,in the full and literal sense" models" (Charniak and
(Haugeland, 1985) McDermott, 1985)

"The automation of] activities that we "The study of the computations

associate with human thinking, activities that make it possible to perceive,
such as decision-making, problem solving, reason, and act" (Winston, 1992)
learning..."(Bellman, 1978)

c) "The art of creating machines that d) "A field of study that seeks to
perform functions that require explain and emulate intelligent
intelligence when performed by behavior in terms of computational
people" (Kurzweil, 1990) processes"
(Schalkoff, 1 990)
"The study of how to make "The branch of computer science
computersdo things at which, at the that is concerned with the
moment, people are better" (Rich automation of intelligent
and Knight, 1 behavior"
99 1 ) (Luger and Stubblefield, 1993)

The definitions on the top, (a) and (b) are concerned with reasoning, whereas those on the
bottom, (c) and (d) address behavior. The definitions on the left, (a) and (c) measure
success interms of human performance, and those on the right, (b) and (d) measure the
ideal concept of intelligence called rationality
Intelligent Systems:
In order to design intelligent systems, it is important to categorize them into four
categories (Luger and Stubberfield 1993), (Russell and Norvig, 2003)
1. Systems that think like humans

2. Systems that think rationally

3. Systems that behave like humans
4. Systems that behave rationally
 Human-Like Rationally

Cognitive Science Approach Laws of thought Approach

Thin
k: “Machines that think like humans” “ Machines that think Rationally”

Turing Test Approach Rational Agent Approach

Act:
“Machines that behave like “Machines that behave
humans” Rationally”

Cognitive Science: Think Human-Like

a. Requires a model for human cognition. Precise enough models allow

simulation by computers.

b. Focus is not just on behavior and I/O, but looks like reasoning process.

c. Goal is not just to produce human-like behavior but to produce a sequence of steps of
thereasoning process, similar to the steps followed by a human in solving the same task.

Laws of thought: Think Rationally

a. The study of mental faculties through the use of computational models; that it is,
thestudy of computations that make it possible to perceive reason and act.

Focus is on inference mechanisms that are probably correct and guarantee an optimal solution.

b. Goal is to formalize the reasoning process as a system of logical rules and procedures
of inference.

c. Develop systems of representation to allow inferences to be like

―Socrates is a man. All men are mortal. Therefore Socrates is mortal”

Turing Test: Act Human-Like

a. The art of creating machines that perform functions requiring intelligence when performed
by people; that it is the study of, how to make computers do things which, at the moment, people
do better.
b. Focus is on action, and not intelligent behavior centered around the representation of the world
c. Example: Turing Test
3 rooms contain: a person, a computer and an interrogator.

o The interrogator can communicate with the other 2 by teletype (to avoidthe machine
imitate the appearance of voice of the person)

o The interrogator tries to determine which the person is and which themachine is.

o The machine tries to fool the interrogator to believe that it is the human, and the
person also tries to convince the interrogator that it is the human.

o If the machine succeeds in fooling the interrogator, then conclude that themachine is
intelligent.

Rational agent: Act Rationally

a. Tries to explain and emulate intelligent behavior in terms of computational process;

thatit is concerned with the automation of the intelligence.

b. Focus is on systems that act sufficiently if not optimally in all situations.

c. Goal is to develop systems that are rational and sufficient

Agents and Environments:

Fig 2.1: Agents and Environments

Agent:
An Agent is anything that can be viewed as perceiving its environment through sensors
andacting upon that environment through actuators.
✓ A human agent has eyes, ears, and other organs for sensors and hands, legs, mouth,
and other body parts for actuators.
✓ A robotic agent might have cameras and infrared range finders for sensors and
various motors foractuators.
✓ A software agent receives keystrokes, file contents, and network packets as sensory
inputs and acts on the environment by displaying on the screen, writing files, and sending
network packets.

Percept:
We use the term percept to refer to the agent's perceptual inputs at any given instant.

Percept Sequence:
An agent's percept sequence is the complete history of everything the agent has ever perceived.

Agent function:
Mathematically speaking, we say that an agent's behavior is described by the agent
functionthat maps any given percept sequence to an action.
Agent program
Internally, the agent function for an artificial agent will be implemented by an agentprogram.
It is important to keep these two ideas distinct. The agent function is an abstract
mathematical description; the agent program is a concrete implementation, running on the
agent architecture.
To illustrate these ideas, we will use a very simple example-the vacuum-cleaner world shown
in Fig 2.1.5. This particular world has just two locations: squares A and B. The vacuum agent
perceives which square it is in and whether there is dirt in the square. It can choose to move
left, move right, suck up the dirt, or do nothing. One very simple agent function is the
following: if the current square is dirty, then suck, otherwise move to the other square. A partial
tabulation of this agent function is shown in Fig 2.1.6.

Fig 2.1.5: A vacuum-cleaner world with just two locations.

Agent function

Percept Sequence Action

[A, Clean] Right

[A, Dirty] Suck

[B, Clean] Left

[B, Dirty] Suck

[A, Clean], [A, Clean] Right

[A, Clean], [A, Dirty] Suck

Fig 2.1.6: Partial tabulation of a simple agent function for the example: vacuum-cleaner world shown
in the Fig2.1.5

Function REFLEX-VACCUM-AGENT ([location, status]) returns an

action If status=Dirty then return Suck

else if location = A then return Right

else if location = B then return Left

Fig 2.1.6(i): The REFLEX-VACCUM-AGENT program is invoked for each new percept
(location, status) and returns an action each time

• A Rational agent is one that does the right thing. we say that the right action is the one that
will cause the agent to be most successful. That leaves us with the problem of deciding how
and when to evaluate the agent's success.
We use the term performance measure for the how—the criteria that determine how
successful an agent is.
✓ Ex-Agent cleaning the dirty floor
✓ Performance Measure-Amount of dirt collected
✓ When to measure-Weekly for better results
What is rational at any given time depends on four things:
• The performance measure defining the criterion of success
• The agent‘s prior knowledge of the environment
• The actions that the agent can perform
• The agent‘s percept sequence up to now.

Omniscience ,Learning and Autonomy:

➢ We need to distinguish between rationality and omniscience. An Omniscient agent knows
the actual outcome of its actions and can act accordingly but omniscience is impossible in
reality.
➢ Rational agent not only gathers information but also learns as much as possible
from what itperceives.
➢ If an agent just relies on the prior knowledge of its designer rather than its own
percepts thenthe agent lacks autonomy.
➢ A system is autonomous to the extent that its behavior is determined its own experience.
➢ A rational agent should be autonomous.

E.g., a clock(lacks autonomy)

➢ No input (percepts)
➢ Run only but its own algorithm (prior knowledge)
➢ No learning, no experience, etc.

ENVIRONMENTS:
The Performance measure, the environment and the agents actuators and sensors comes under

the heading task environment. We also call this as

PEAS(Performance,Environment,Actuators,Sensors)
Environment-Types:

1. Accessible vs. inaccessible or Fully observable vs Partially Observable:

If an agent sensor can sense or access the complete state of an environment at each point
of time then it is a fully observable environment, else it is partially observable.
2. Deterministic vs. Stochastic:
If the next state of the environment is completely determined by the current state and the
actionsselected by the agents, then we say the environment is deterministic
3. Episodic vs. nonepisodic:
➢ The agent's experience is divided into "episodes." Each episode consists of the agent
perceiving and then acting. The quality of its action depends just on the episode itself,
becausesubsequent episodes do not depend on what actions occur in previous episodes.
➢ Episodic environments are much simpler because the agent does not need to think ahead.

4. Static vs. dynamic.

If the environment can change while an agent is deliberating, then we say the
environment isdynamic for that agent; otherwise it is static.
5. Discrete vs. continuous:
If there are a limited number of distinct, clearly defined percepts and actions we saythat
the environment is discrete. Otherwise, it is continuous.
STRUCTURE OF INTELLIGENT AGENTS

➢ The job of AI is to design the agent program: a function that implements the agent
mapping from percepts to actions. We assume this program will run on some sort of
ARCHITECTURE computing device, which we will call the architecture.
➢ The architecture might be a plain computer, or it might include special-purpose
hardware for certain tasks, such as processing camera images or filtering audio input. It
might also include software that provides a degree of insulation between the raw computer
and the agent program, so that we can program at a higher level. In general, the architecture
makes the percepts from the sensors available to the program, runs the program, and feeds
the program's action choicesto the effectors as they are generated.
➢ The relationship among agents, architectures, and programs can be summed up as

follows: agent = architecture + program

 Agent programs:
➢ Intelligent agents accept percepts from an environment and generates actions. The
earlyversions of agent programs will have a very simple form (Figure 2.4)
➢ Each will use some internal data structures that will be updated as new percepts arrive.
➢ These data structures are operated on by the agent's decision-making procedures to
generate anaction choice, which is then passed to the architecture to be executed

Types of agents:
Agents can be grouped into four classes based on their degree of perceived intelligence and capability :
➢ Simple Reflex Agents
➢ Model-Based Reflex Agents
➢ Goal-Based Agents
➢ Utility-Based Agents

Simple reflex agents:

➢ Simple reflex agents ignore the rest of the percept history and act only on the
basis ofthe current percept.
➢ The agent function is based on the condition-action rule.

➢ If the condition is true, then the action is taken, else not. This agent function only succeeds
whenthe environment is fully observable.
Model-based reflex agents:

The Model-based agent can work in a partially observable environment, and track the
situation.
➢ A model-based agent has two important factors:
➢ Model: It is knowledge about "how things happen in the world," so it is called a Model-based agent.

➢ Internal State: It is a representation of the current state based on percept history.

Goal-based agents:
➢ A goal-based agent has an agenda.

➢ It operates based on a goal in front of it and makes decisions based on how best to reach that goal.
➢ A goal-based agent operates as a search and planning function, meaning it targets the goal
ahead andfinds the right action in order to reach it.
➢ Expansion of model-based agent.

Utility-based agents:
➢ utility-based agent is an agent that acts based not only on what the goal is, but the best way to
reach thatgoal.
➢ The Utility-based agent is useful when there are multiple possible alternatives, and an
agent has tochoose in order to perform the best action.
➢ The term utility can be used to describe how "happy" the agent is.

Problem Solving Agents:

➢ Problem solving agent is a goal-based agent.
➢ Problem solving agents decide what to do by finding sequence of actions that lead to desirable states.
Goal Formulation:
It organizes the steps required to formulate/ prepare one goal out of multiple goals available.
Problem Formulation:
It is a process of deciding what actions and states to consider to follow goal
formulation. The process of looking for a best sequence to achieve a goal is called
Search.
A search algorithm takes a problem as input and returns a solution in the form of action sequences.
Once the solution is found the action it recommends can be carried out. This is called Execution
[Link] Defined problems and solutions:
A problem can be defined formally by 4 components:
➢ The initial state of the agent is the state where the agent starts in. In this case, the initial state can be
described as In: Arad
➢ The possible actions available to the agent, corresponding to each of the state the agent
residesin.
For example, ACTIONS(In: Arad) = {Go: Sibiu, Go: Timisoara, Go:
Zerind}.Actions are also known as operations.
➢ A description of what each action [Link] formal name for this is Transition model,Specified
by thefunction Result(s,a) that returns the state that results from the action a in state s.
We also use the term Successor to refer to any state reachable from a given state by a single
[Link] EX:Result(In(Arad),GO(Zerind))=In(Zerind)

Together the initial state,actions and transition model implicitly defines the state space of the
problem State space: set of all states reachable from the initial state by any sequence of actions
➢ The goal test, determining whether the current state is a goal state. Here, the goal state is
{In:Bucharest}
➢ The path cost function, which determine the cost of each path, which is reflecting
in theperformance measure.
we define the cost function as c(s, a, s‘), where s is the current state and a is the action
performed by theagent to reach state s‘.
Example –
8 puzzle problem

Initial State

Goal State

➢ States: a state description specifies the location of each of the eight tiles in one of the
ninesquares. For efficiency, it is useful to include the location of the blank.
➢ Actions: blank moves left, right, up, or down.

➢ Transition Model: Given a state and action, this returns the resulting state. For example
if weapply left to the start state the resulting state has the 5 and the blank switched.
➢ Goal test: state matches the goal configuration shown in fig.

➢ Path cost: each step costs 1, so the path cost is just the length of the path.

State Space Search/Problem Space Search:

The state space representation forms the basis of most of the AI methods.
• Formulate a problem as a state space search by showing the legal problem states, the legal
operators, and the initial and goal states.
• A state is defined by the specification of the values of all attributes of interest in the world

• An operator changes one state into the other; it has a precondition which is the value
of certain attributes prior to the application of the operator, and a set of effects, which arethe
attributes altered by the operator
• The initial state is where you start

• The goal state is the partial description of the solution

Formal Description of the problem:

1. Define a state space that contains all the possible configurations of the relevant objects.
2. Specify one or more states within that space that describe possible situations from
whichthe problem solving process may start ( initial state)
3. Specify one or more states that would be acceptable as solutions to the problem. ( goal states)
Specify a set of rules that describe the actions (operations) available

State-Space Problem Formulation:

Example: A problem is defined by four items:

1. initial state e.g., "at Arad―
2. actions or successor function : S(x) = set of action–
state pairse.g., S(Arad) = {<Arad → Zerind, Zerind>, … }
3. goal test (or set of goal states)
e.g., x = "at Bucharest‖, Checkmate(x)

4. path cost (additive)

e.g., sum of distances, number of actions executed, etc.
c(x,a,y) is the step cost, assumed to be ≥ 0
A solution is a sequence of actions leading from the initial state to a goal state

Example: 8-queens problem

Initial State: Any arrangement of 0 to 8 queens on board.
1. Operators: add a queen to any square.
2. Goal Test: 8 queens on board, none attacked.
3. Path cost: not applicable or Zero (because only the final state counts, search cost might
be of interest).
Search strategies:

Search: Searching is a step by step procedure to solve a search-problem in a given search

space. Asearch problem can have three main factors:
Search Space: Search space represents a set of possible solutions, which a system may
[Link] State: It is a state from where agent begins the search.
Goal test: It is a function which observe the current state and returns whether the goal state is
achievedor not.
Properties of Search Algorithms

Which search algorithm one should use will generally depend on the
problemdomain. There are four important factors to consider:
1. Completeness – Is a solution guaranteed to be found if at least one solution exists?

2. Optimality – Is the solution found guaranteed to be the best (or lowest cost) solution
if thereexists more than one solution?
3. Time Complexity – The upper bound on the time required to find a solution, as a
function ofthe complexity of the problem.
4. Space Complexity – The upper bound on the storage space (memory) required at any
pointduring the search, as a function of the complexity of the problem.

State Spaces versus Search Trees:

• State Space
o Set of valid states for a problem
o Linked by operators
o e.g., 20 valid states (cities) in the Romanian travel problem
• Search Tree
– Root node = initial state
– Child nodes = states that can be visited from parent
– Note that the depth of the tree can be infinite
• E.g., via repeated states
– Partial search tree
• Portion of tree that has been expanded so far
– Fringe
• Leaves of partial search tree, candidates for expansion
Search trees = data structure to search state-space
Searching
Many traditional search algorithms are used in AI applications. For complex problems, the
traditional algorithms are unable to find the solution within some practical time and space
limits. Consequently, many special techniques are developed; using heuristic functions. The
algorithms that use heuristic functions are called heuristic algorithms. Heuristic algorithms
are not really intelligent; they appear to be intelligent because they achieve better
performance.

Heuristic algorithms are more efficient because they take advantage of feedback from the data t o direct
the search path.
Uninformed search
Also called blind, exhaustive or brute-force search, uses no information about the problem to
guide thesearch and therefore may not be very efficient.

Informed Search:

Also called heuristic or intelligent search, uses information about the problem to guide the
search, usuallyguesses the distance to a goal state and therefore efficient, but the search may not
be always possible.
Uninformed Search (Blind searches
Breadth First Search:
➢ One simple search strategy is a breadth-first search. In this strategy, the root node is
expanded first, then all the nodes generated by the root node are expanded next, and thentheir
successors, and so on.
➢ In general, all the nodes at depth d in the search tree are expanded before the nodes at depth d

+ FS illustrated:
Step 1: Initially frontier contains only one node corresponding to the source state A.

Figure 1
Frontier: A

Step 2: A is removed from fringe. The node is expanded, and its children B and C are
[Link] are placed at the back of fringe.

Figure 2
Frontier: B
C

Step 3: Node B is removed from fringe and is expanded. Its children D, E are generated

and putat the back of fringe.

Figure 3
Frontier: C D E

Step 4: Node C is removed from fringe and is expanded. Its children D and G are added
to theback of fringe.
Figure 4
Frontier: D E D G

Step 5: Node D is removed from fringe. Its children C and F are generated and added to the
backof fringe.

Figure 5
Frontier: E D G C F

Step 6: Node E is removed from fringe. It has no children.

Figure 6
Frontier: D G C F

Step 7: D is expanded; B and F are put in OPEN.

Figure 7
Frontier: G C F B F
Step 8: G is selected for expansion. It is found to be a goal node. So the algorithm returns the
path A C G by following the parent pointers of the node corresponding to G. The algorithm
terminates.

Breadth first search is:

One of the simplest search strategies

• Complete. If there is a solution, BFS is guaranteed to find it.
• If there are multiple solutions, then a minimal solution will be found
• The algorithm is optimal (i.e., admissible) if all operators have the same
[Link], breadth first search finds a solution with the shortest path
length.
• Time complexity : O(bd )
• Space complexity : O(bd )
• Optimality :Yes

b - branching factor(maximum no of successors of

any node), d – Depth of the shallowest goal node
Maximum length of any path (m) in search space
Advantages

➢ BFS will provide a solution if any solution exists.

➢ If there are more than one solutions for a given problem, then BFS will provide the minimal
solutionwhich requires the least number of steps.

Disadvantages:
➢ Requires the generation and storage of a tree whose size is exponential the depth of
theshallowest goal node.
➢ The breadth first search algorithm cannot be effectively used unless the search space
isquite small.
Applications Of Breadth-First Search Algorithm
GPS Navigation systems: Breadth-First Search is one of the best algorithms used to find
neighboringlocations by using the GPS system.
Broadcasting: Networking makes use of what we call as packets for communication. These
packets follow a traversal method to reach various networking nodes. One of the most commonly
used traversal
methods is Breadth-First Search. It is being used as an algorithm that is used to communicate
broadcastedpackets across all the nodes in a network.
Depth- First- Search.
We may sometimes search the goal along the largest depth of the tree, and move up only
when further traversal along the depth is not possible. We then attempt to find alternative
offspring of the parent of the node (state) last visited. If we visit the nodes of a tree using the
above principlesto search the goal, the traversal made is called depth first traversal and
consequently the search strategy is called depth first search.

DFS illustrated:

A State Space Graph Step 1: Initially fringe contains

only the node for A.

Figure 1
FRINGE: A

Step 2: A is removed from fringe. A is expanded and its children B and C are put in front
offringe.

Figure 2
FRINGE: B C

Step 3: Node B is removed from fringe, and its children D and E are pushed in front of fringe.

Figure 3
FRINGE: D E

Step 4: Node D is removed from fringe. C and F are pushed in front of fringe.
Figure 4
FRINGE: C F E C

Step 5: Node C is removed from fringe. Its child G is pushed in front of fringe.
Figure 5

Figure 5

FRINGE: G F E C
Step 6: Node G is expanded and found to be a goal node.

Figure 6
FRINGE: G F E C

The solution path A-B-D-C-G is returned and the algorithm terminates.

Depth first search

1. takes exponential time.

2. If N is the maximum depth of a node in the search space, in the worst case the algorithm will
d
take time O(b ).
3. The space taken is linear in the depth of the search tree, O(bN).

Note that the time taken by the algorithm is related to the maximum depth of the search tree. If
the search tree has infinite depth, the algorithm may not terminate. This can happen if the
search space is infinite. It can also happen if the search space contains cycles. The latter case can
be handled by checking for cycles in the algorithm. Thus Depth First Search is not complete.

Iterative Deeping DFS

➢ 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 limituntil a goal is found.
➢ This algorithm performs depth-first search up to a certain "depth limit", and it keeps
increasingthe depth limit after each iteration until the goal node is found.

Advantages:
➢ It combines the benefits of BFS and DFS search algorithm in terms of fast search and
memoryefficiency.

Disadvantages:
➢ The main drawback of IDDFS is that it repeats all the work of the previous phase.

Iterative deepening search L=0

Iterative
deepening search L=1

Iterative deepening search L=2

IterativeDeepeningSea
rchL=3

M is the goal node. So we stop there.

Compl
ete:
Yes
Time:
O(bd)
Space:
O(bd)
Optimal: Yes, if step cost = 1 or increasing function of depth.

Conclusion:
We can conclude that IDS is a hybrid search strategy between BFS and DFS inheriting
their advantages.
IDS is faster than BFS and DFS.
Itissaidthat ―IDSisthepreferreduniformedsearchmethodwhen thereisalargesearchspace and the depthof
the solution is not know
Informed search/Heuristic search

A heuristic is a method that

• might not always find the best solution but is guaranteed to find a good solution in
reasonable time. By sacrificing completeness it increases efficiency.
• Useful in solving tough problems which
o could not be solved any other way.
o solutions take an infinite time or very long time to compute.

Calculating Heuristic Value:

• 1. Euclidian distance- used to calculate straight line distance.

• [Link] distance-If we want to calculate vertical or horizontal distanceFor ex:
8 puzzle problem
Source state

1 3 2
6 5 4
8 7
destination state

1 2 3
4 5 6
7 8

Then the Manhattan distance would be sum of the no of moves required to move each
number from source state to destination state.

Number 2 3 4 5 6 7 8
in 8
puzzle
No. of 2 1 2 0 2 2 0
moves to
reach
destinati
on
1. No. of misplaced tiles for 8 puzzle problem

Source state

1 3 2
6 5 4
8 7

Destination state

1 2 3
4 5 6
7 8
Here just calculate the number of tiles that have to be changed to reach
goal stateHere 1,5,8 need not be changed
2,3,4,6,7 should be changed, so the heuristic value will be 5(because 5 tiles have to be changed)

Hill Climbing Algorithm

✓ 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 tothe
problem. It terminates when it reaches a peak value where no neighbor has a higher value.
✓ It is also called greedy local search as it only looks to its good immediate neighbor state
and not beyond that.
✓ Hill Climbing is mostly used when a good heuristic is available.
✓ In this algorithm, we don't need to maintain and handle the search tree or graph as it only
keeps a single current state.

The idea behind hill climbing is as follows.

1. Pick a random point in the search space.

2. Consider all the neighbors of the current state.
3. Choose the neighbor with the best quality and move to that state.
4. Repeat 2 thru 4 until all the neighboring states are of lower quality.
5. Return the current state as the solution state.
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 ishigher than it.

Global Maximum: Global maximum is the best possible state of state space landscape. It has the
highest value of objectivefunction.

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.

Algorithm for Hill Climbing

Problems in Hill Climbing Algorithm:

Simulated annealing search
A hill-climbing algorithm that never makes ―downhill‖ moves towards states with lower
value (or higher cost) is guaranteed to be incomplete, because it can stuck on a local maximum.
In contrast, a purely random walk –that is, moving to a successor chosen uniformly at random
from the set of successors – is complete, but extremely inefficient. Simulated annealing is an
algorithm that combines hill-climbing with a random walk in some way that yields both
efficiencyand completeness.
simulated annealing algorithm is quite similar to hill climbing. Instead of picking the best
move,however, it picks the random move. If the move improves the situation, it is always
accepted. Otherwise, the algorithm accepts the move with some probability less than 1.
The probability decreases exponentially with the ―badness‖ of the move – the amount E
by which the evaluation is worsened. The probability also decreases as the "temperature" T
goes down: "bad movesare more likely to be allowed at the start when temperature is high,
and they become more unlikelyas T decreases. One can prove that if the schedule lowers T
slowly enough, the algorithm will find a globaloptimum with probability approaching 1.
Simulated annealing was first used extensively to solve VLSI layout problems. It has been
applied widelyto factory scheduling and other large-scale optimization tasks.

Best First Search:

• A combination of depth first and breadth first searches.

• Depth first is good because a solution can be found without computing all nodes and
breadth first is good because it does not get trapped in dead ends.
• The best first search allows us to switch between paths thus gaining the benefit of both
approaches. At each step the most promising node is chosen. If one of the nodes chosen
generates nodes that are less promising it is possible to choose another at the same level and
in effect the search changes from depth to breadth. If on analysis these are no better than this
previously unexpanded node and branch is not forgotten and the search method reverts to
the

OPEN is a priority queue of nodes that have been evaluated by the heuristic function but which
have not yet been expanded into successors. The most promising nodes are at the front.

CLOSED are nodes that have already been generated and these nodes must be stored
because agraph is being used in preference to a tree.
Algorithm:
1. Start with OPEN holding the initial state

Until a goal is found or there are no nodes left on open do.

• Pick the best node on OPEN

• Generate its successors
• For each successor Do
• If it has not been generated before ,evaluate it ,add it to OPEN and record its
parent

• If it has been generated before change the parent if this new path is betterand in that
case update the cost of getting to any successor nodes.

2. If a goal is found or no more nodes left in OPEN, quit, else return to 2.

Example:

1. It is not optimal.
2. It is incomplete because it can start down an infinite path and never return to try
otherpossibilities.
3. The worst-case time complexity for greedy search is O (bm), where m is the maximum
depth of the search space.
4. Because greedy search retains all nodes in memory, its space complexity is the same
asitstime complexity
A* Algorithm

The Best First algorithm is a simplified form of the A* algorithm.

The A* search algorithm (pronounced "Ay-star") is a tree search algorithm that finds a path
from a given initial node to a given goal node (or one passing a given goal test). It employs a
"heuristic estimate" which ranks each node by an estimate of the best route that goes through
thatnode. It visits the nodes in order of this heuristic estimate.

Similar to greedy best-first search but is more accurate because A* takes into account the
nodes that have already been traversed.

From A* we note that f = g + h where

g is a measure of the distance/cost to go from the initial node to the current node

his an estimate of the distance/cost to solution from the current node.

Thus fis an estimate of how long it takes to go from the initial node to the solution

Algorithm:

1. Initialize : Set OPEN = (S); CLOSED

= ( ) g(s)= 0, f(s)=h(s)
2. Fail : If OPEN = ( ), Terminate and fail.

3. Select : select the minimum cost state, n,

from OPEN,save n in CLOSED
4. Terminate : If n €G, Terminate with success and return f(n)

5. Expand : for each successor, m, of n

a) If m € [OPEN U CLOSED] Set g(m) = g(n) + c(n , m)

Set f(m) = g(m) + h(m)
Insert m in OPEN

b) If m € [OPEN U CLOSED]

Set g(m) = min { g(m) , g(n) + c(n

, m)} Set f(m) = g(m) + h(m)
If f(m) has decreased and m € CLOSED

Move m to OPEN.
Description:
• A* begins at a selected node. Applied to this node is the "cost" of entering this node (usually
zero for the initial node). A* then estimates the distance to the goal node fromthe current node.
This estimate and the cost added together are the heuristic which is assigned to the path
leading to this node. The node is then added to a priority queue, oftencalled "open".
• The algorithm then removes the next node from the priority queue (because of the way a
priority queue works, the node removed will have the lowest heuristic). If the queue is empty,
there is no path from the initial node to the goal node and the algorithm stops. If the node is the
goal node, A* constructs and outputs the successful path and stops.
• If the node is not the goal node, new nodes are created for all admissible adjoining nodes;
the exact way of doing this depends on the problem at hand. For each successive node, A*
calculates the "cost" of entering the node and saves it with the node. This cost is calculated from
the cumulative sum of costs stored with its ancestors, plus the cost of the operation which reached
this new node.
• The algorithm also maintains a 'closed' list of nodes whose adjoining nodes have been
checked. If a newly generated node is already in this list with an equal or lower cost, no
further processing is done on that node or with the path associated with it. If a node in the
closed list matches the new one, but has been stored with a higher cost, it is removed from the
closed list, and processing continues on the new node.

Next, an estimate of the new node's distance to the goal is added to the cost to form the heuristic for that
node. This is then added to the 'open' priority queue, unless an identical node is found there.
• Once the above three steps have been repeated for each new adjoining node, the original node
taken from the priority queue is added to the 'closed' list. The next node is then popped from the
priority queue and the process is repeatedThe heuristic costs from each city to Bucharest:
 A* search properties:

▪ The algorithm A* is admissible. This means that provided a solution exists, the first
solution found by A* is an optimal solution. A* is admissible under the following
conditions:

▪ Heuristic function: for every node n , h(n) ≤ h*(n) .

▪ A* is also complete.

▪ A* is optimally efficient for a given heuristic.

▪ A* is much more efficient that uninformed search.

Game Playing
Adversarial search, or game-tree search, is a technique for analyzing an adversarial game in order
to try to determine who can win the game and what moves the players should make in order to
win. Adversarial search is one of the oldest topics in Artificial Intelligence. The original ideas
for adversarial search were developed by Shannon in 1950 and independently by Turing in 1951,
in the context of the game of chess—and their ideas still form the basis for the techniques used
today.
2- Person Games:

o Players: We call them Max and Min.

o Initial State: Includes board position and whose turn it is.
o Operators: These correspond to legal moves.
o Terminal Test: A test applied to a board position which determines whether the game is over.
In chess, for example, this would be a checkmate or stalemate situation.
o Utility Function: A function which assigns a numeric value to a terminalstate. For example,
in chess the outcome is win (+1), lose (-1) or draw (0). Note that by convention,we always
measure utility relative to Max.

Mini Max Algorithm:

1. Generate the whole game tree.
2. Apply the utility function to leaf nodes to get their values.
3. Use the utility of nodes at level n to derive the utility of nodes at level n-1.
4. Continue backing up values towards the root (one layer at a time).
5. Eventually the backed up values reach the top of the tree, at which point Max chooses the
move that yields the highest value. This is called the minimax decision because it maximises the
utility for Max on the assumption that Min will play perfectly to minimise it.
Example:

Example:
Properties of minimax:

▪ Complete : Yes (if tree is finite)

▪ Optimal : Yes (against an optimal opponent)
▪ Time complexity : O(bm)
▪ Space complexity : O(bm) (depth-first exploration)
▪ For chess, b ≈ 35, m ≈100 for "reasonable" games

→ exact solution completely infeasible.

Limitations
– Not always feasible to traverse entire tree
– Time limitations

Alpha-Beta pruning algorithm:

• Pruning: eliminating a branch of the search tree from consideration without exhaustive
examination of each node
• - Pruning: the basic idea is to prune portions of the search tree that cannot
improvetheutility value of the max or min node, by just considering the values of nodes
seen sofar.
• Alpha-beta pruning is used on top of minimax search to detect paths that do not need tobe
explored. The intuition is:
• The MAX player is always trying to maximize the score. Call this .
• The MIN player is always trying to minimize the score. Call this .
• Alpha cutoff: Given a Max node n, cutoff the search below n (i.e., don't generate
orexamine any more of n's children) if alpha(n) >= beta(n)
(alpha increases and passes beta from below)
• Beta cutoff.: Given a Min node n, cutoff the search below n (i.e., don't generate
orexamine any more of n's children) if beta(n) <= alpha(n)
(beta decreases and passes alpha from above)
• Carry alpha and beta values down during search Pruning occurs whenever alpha >= beta

Algorithm:
Example:

1) Setup phase: Assign to each left-most (or right-most) internal node of

the tree,variables: alpha = -infinity, beta = +infinity

2) Look at first computed final configuration value. It’s a 3. Parent is a min

node, soset the beta (min) value to 3.
3) Look at next value, 5. Since parent is a min node, we want the minimum of 3
and 5 which is 3. Parent min node is done – fill alpha (max) value of its parent max node. Always
set alpha for max nodes and beta for min nodes. Copy the state of the max parent node into the
second unevaluated min child.

4) Look at next value, 2. Since parent node is min with b=+inf, 2 is smaller, change b.
5) Now, the min parent node has a max value of 3 and min value of 2. The value of the 2nd
child does not matter. If it is >2, 2 will be selected for min node. If it is <2, it will be
selected for min node, but since it is <3 it will not get selected for the parent max node. Thus,
we prune the right subtree of the min node. Propagate max value up the tree.

6) Max node is now done and we can set the beta value of its parent and
propagate nodestate to sibling subtree’s left-most path.

7) The next node is 10. 10 is not smaller than 3, so state of parent does not change.
We stillhave to look at the 2nd child since alpha is still –inf.
8) The next node is 4. Smallest value goes to the parent min node. Min subtree is done,
so the parent max node gets the alpha (max) value from the child. Note that if the max
node had a2nd subtree, we can prune it since a>b.
9) Continue propagating value up the tree, modifying the corresponding alpha/beta
values. Also propagate the state of root node down the left-most path of the right
subtree.

10) Next value is a 2. We set the beta (min) value of the min parent to 2. Since no
otherchildren exist, we propagate the value up the tree.
11) We have a value for the 3rd level max node, now we can modify the beta (min) value
of the min parent to 2. Now, we have a situation that a>b and thus the value of the
rightmost subtree of the min node does not matter, so we prune the whole subtree.

12) Finally, no more nodes remain, we propagate values up the tree. The root has a
value of 3 that comes from the left-most child. Thus, the player should choose the left-
most child’s move in order to maximize his/her winnings. As you can see, the result is
the same as with the mini-max example, but we did not visit all nodes of the tree.
AO* Search: (And-Or) Graph:

• AO* is informed search algorithm ,work based on heuristic. We already know about the divide
and conquer strategy, a solution to a problem can be obtained by decomposing it into smaller sub-
problems.
• Each of this sub-problem can then be solved to get its sub solution. These sub solutions can
then recombined to get a solution as a whole. That is called is Problem Reduction. AND- OR
graphs or AND –OR trees are used for representing the solution.
• This method generates arc which is called as AND-OR arcs. One AND arc may point to any
number of successor nodes, all of which must be solved in order for an arc to point to a solution.
AND-OR graph is used to represent various kind of complex problem solutions.
• AO* search algo. is based on AND-OR graph so ,it is called AO* search algo.
• Example: In Following figure , we have taken example of Goal: Acquire TV Set. This goal or
problem is subdivided into two subproblems or sub goals like 1) STEAL TV SET 2) Earn some
money, Buy TV SET. SO to solve this problem if we select second alternative of earn some Money,
then along with that Buy TV SET also need to select as it is part of and graph.
• Whereas First alternative :Steal Tv Set is forming OR Graph

AO * Search Algorithm In Artificial Intelligence

• Justas in an OR graph, several arcs may emerge from a single node, indicating a variety of ways
in which theoriginal problem might be solved.
• This is why the structure is called not simply an OR-graph but rather an AND-OR graph (which also
happens to bean AND-OR tree)

AO * Search Algorithm In Artificial Intelligence With Example

AO * Search Algorithm In Artificial Intelligence

• An algorithm to find a solution in an AND – OR graph must handle AND area appropriately.
• A* algorithm can not search AND – OR graphs efficiently.
• This can be understand from the give figure
• In figure (a) the top node A has been expanded producing two area one leading to B and leading to
C-D
. the numbers at each node represent the value of f ‗ at that node (cost of getting to the goal state from
current state). For simplicity, it is assumed that every operation(i.e. applying a rule) has unit cost, i.e.,
eachare with single successor will have a cost of 1 and each of its components.

• With the available information till now , it appears that C is the most promising node to
expand since itsf ‗ = 3 , the lowest but going through B would be better since to use C we must
also use D‘ and the cost would be 9(3+4+1+1). Through B it would be 6(5+1).
• Thus the choice of the next node to expand depends not only on a value but also on whether
that node is part of the current best path form the initial mode. Figure (b) makes this clearer. In
figure the node G appearsto be the most promising node, with the least f ‗ value. But G is not on
the current beat path, since to use G we must use GH with a cost of 9 and again this demands that
arcs be used (with a cost of 27).

The path from A through B, E-F is better with a total cost of (17+1=18). Thus we can see
that tosearch an AND-OR graph, the following three things must be done.

1. traverse the graph starting at the initial node and following the current best path, and
accumulate the setof nodes that are on the path and have not yet been expanded.
2. Pick one of these best unexpanded nodes and expand it. Add its successors to the graph and
compute f ‗(cost of the remaining distance) for each of them.

3. Change the f ‗ estimate of the newly expanded node to reflect the new information produced
by itssuccessors. Propagate this change backward through the graph. Decide which of the
current best path.

The propagation of revised cost estimation backward is in the tree is not necessary in A*
algorithm. This is because in AO* algorithm expanded nodes are re-examined so that the
current best path canbe selected.

Advantages of AO*:

• It is Complete
• Will not go in infinite loop
• Less Memory Required
Disadvantages of AO*:

It is not optimal as it does not explore all the path once it find a solution.