1

SSM COLLEGE OF ARTS & SCIENCE

DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

UNIT - I
INTRODUCTION

Intelligence is so important Intelligence to us. For thousands of years, we have tried to

understand how we think and act—that is, how our brain, a mere handful of matter, can perceive,
understand, predict, and manipulate a world far larger and more complicated than itself. The field
of artificial intelligence, or AI, Artificial intelligence is concerned with not just understanding but
also building intelligent entities—machines that can compute how to act effectively and safely in a
wide variety of novel situations.

1.1 What Is AI?

AI is interesting, but we have not said what it is. Historically, researchers have pursued
several different versions of AI. Some have defined intelligence in terms of fidelity to human
performance, while others prefer an abstract, formal definition of intelligence called rationality—
loosely speaking, doing the “right thing”

The subject matter Rationality itself also varies: some consider intelligence to be a property
of internal thought processes and reasoning, while others focus on intelligent behavior, an external
characterization. From these two dimensions

1. human vs. rational

2. thought vs. behaviour

There are four possible combinations, and there have been adherents and research programs for all
four.

The methods used are necessarily different: the pursuit of human-like intelligence must be
in part an empirical science related to psychology, involving observations and hypotheses about
actual human behaviour and thought processes; a rationalist approach, on the other hand, involves a
combination of mathematics and engineering, and connects to statistics, control theory, and
economics. The various groups have both disparaged and helped each other. Let us look at the four
approaches in more detail.

1.1.1 Acting humanly: The Turing test approach

The Turing test, proposed by Alan Turing (1950), was designed as a thought Turing test
experiment that would sidestep the philosophical vagueness of the question “Can a machine think?”
A computer passes the test if a human interrogator, after posing some written questions, cannot tell
whether the written responses come from a person or from a computer

The computer would need the following capabilities:

 Natural language processing to communicate successfully in a human language;

 Knowledge representation to store what it knows or hears;
 Automated reasoning to answer questions and to draw new conclusions;
 2
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

 Machine learning to adapt to new circumstances and to detect and extrapolate patterns.
Turing viewed the physical simulation of a person as unnecessary to demonstrate
intelligence. However, other researchers have proposed a total Turing test, which requires
interaction with objects and people in the real world. To pass the total Turing test, a robot will need

 Computer vision and speech recognition to perceive the world;

 Robotics to manipulate objects and move about

1.1.2 Thinking humanly: The cognitive modelling approach

To say that a program thinks like a human, we must know how humans think. We can learn
about human thought in three ways:

 introspection—trying to catch our own thoughts as they go by

 psychological experiments—observing a person in action
 brain imaging—observing the brain in action.

Once we have a sufficiently precise theory of the mind, it becomes possible to express the
theory as a computer program. If the program’s input–output behaviour matches corresponding
human behaviour, that is evidence that some of the program’s mechanisms could also be operating
in humans.
 3
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

CHAPTER 2
INTELLIGENT AGENTS
2.1 AGENTS AND ENVIRONMENTS
Intelligent agents in AI are autonomous entries that act an environment using sensors and
actuators to achieve their goals.. In addition, intelligent agents may learn from the environment to
achieve those goals. Driverless cars.

In artificial intelligence, an agent is a computer program or system that is designed to

perceive its environment, make decisions and take actions to achieve a specific goal or set of
goals. The agent operates autonomously, meaning it is not directly controlled by a human
operator.

An agent is anything that can be viewed as perceiving its environment through sensors and
acting upon that environment through actuators. This simple idea is illustrated in Figure 2.1.

Actuator A human agent has eyes, ears, and other organs for sensors and hands, legs, vocal
tract, and so on for actuators.

 A robotic agent might have cameras and infrared range finders for sensors and various
motors for actuators.

 A software agent receives file contents, network packets, and human input
keyboard/mouse/touch screen/voice) as sensory inputs and acts on the environment by
writing files, sending network packets, and displaying information or generating sounds.

The environment could be everything—the entire universe! In practice it is just that part of
the universe whose state we care about when designing this agent—the part that affects what the
agent perceives and that is affected by the agent’s actions. To illustrate these ideas, we use a simple
example—the vacuum-cleaner world, which consists of a robotic vacuum-cleaning agent in a world
consisting of squares that can be either dirty or clean.
 4
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

In the simple world, the vacuum cleaner agent has location sensor and a dirt sensor. So that
it knows where it is ( Room A or Room B) and whether the room is dirty. It can go left, go right,
suck, and idle. A possible performance measure is to maximize the number of clean rooms over a
certain period

Figure 2.2 shows a configuration with just two squares, A and B. The vacuum agent
perceives which square it is in and whether there is dirt in the square. The agent starts in square A.
The available actions are to move to the right, move to the left, 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 Figure 2.3 and an
agent program that implements it appears in Figure 2.8 on page 49.

Looking at Figure 2.3, we see that various vacuum-world agents can be defined simply by
filling in the right-hand column in various ways. The obvious question, then, is this: What is the
right way to fill out the table? In other words, what makes an agent good or bad, intelligent or
stupid? We answer these questions in the next section.
 5
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

2.2 GOOD BEHAVIOR: THE CONCEPT OF RATIONALITY

A rational agent is one that does the right thing. Obviously, doing the right thing is better
Rational agent than doing the wrong thing, but what does it mean to do the right thing?

Several different notions of the “right thing,” but AI has generally stuck to one notion called
consequentialism: we evaluate an agent’s behavior by its consequences. When an agent is plunked
down in an environment, it generates a sequence of actions according to the percepts it receives.
This sequence of actions causes the environment to go through a sequence of states. If the sequence
is desirable, then the agent has performed well. This notion of desirability is captured by a
performance measure that evaluates any Performance measure given sequence of environment
states.

2.2.2 RATIONALITY

What is rational at any given time depends on four things:

 The performance measure that defines the criterion of success.

 The agent’s prior knowledge of the environment.
 The actions that the agent can perform.
 The agent’s percept sequence to date.

Consider the simple vacuum-cleaner agent that cleans a square if it is dirty and moves to the
other square if not; this is the agent function tabulated in Figure 2.3. Is this a rational agent?
That depends! First, we need to say what the performance measure is, what is known about
the environment, and what sensors and actuators the agent has.

Let us assume the following:

 6
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

 The performance measure awards one point for each clean square at each time step, over a
“lifetime” of 1000 time steps. The “geography” of the environment is known a priori
(Figure 2.2) but the dirt distribution and the initial location of the agent are not. Clean
squares stay clean and sucking cleans the current square. The Right and Left actions move
the agent one square except when this would take the agent outside the environment, in
which case the agent remains where it is.

 The only available actions are Right, Left, and Suck.

 The agent correctly perceives its location and whether that location contains [Link]
these circumstances the agent is indeed rational; its expected performance is at least as good
as any other agent’s.

Under these circumstances the agent is indeed rational; its expected performance is at least
as good as any other agent’s. One can see easily that the same agent would be irrational under
different circumstances.

For example, once all the dirt is cleaned up, the agent will oscillate needlessly back and
forth; if the performance measure includes a penalty of one point for each movement, the agent will
fare poorly. A better agent for this case would do nothing once it is sure that all the squares are
clean. If clean squares can become dirty again, the agent should occasionally check and re-clean
them if needed. If the geography of the environment is unknown, the agent will need to explore it.

2.2.3 OMNISCIENCE, LEARNING, AND AUTONOMY

AI, sometimes called machine intelligence, is simulation of human intelligence

demonstrated by machines, particularly computer systems. It is a branch of computer science that is
concerned with the creation of intelligent machines that can think and learn like the way humans
do. The idea is to get the machines to think for themselves and make decisions based on the data
being fed.

AI is all about algorithms – it takes inputs and outputs as data to function. In fact, AI is a set
of algorithms given to an AI program to help it learn from data on its own. Algorithms are the
backbone of AI. In short, it’s the algorithm that helps AI do the mast faster or automate complex
processes or help healthcare professionals determine patterns more accurately or enhance your
shopping experience.

Omniscience, on the other hand, is a metaphysical concept that refers to the capacity of
knowing unlimited knowledge of all things that can be known. The religious aspect suggests
omniscience is an attribute of the God alone. Omniscience, on the other hand, is a way to make
your AI more powerful. Omniscience is the ability to know everything that’s known and could be
known. However, in reality, omniscience is impossible.

A rational agent chooses whichever action maximizes the expected value of the
performance measure given the percept sequence. An omniscient (perfect) agent knows the actual
outcome of its actions and can act accordingly; but perfection is impossible in reality.
 7
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

LEARNING
Our definition requires a rational agent not only to gather information but also to learn as
Learning much as possible from what it perceives. The agent’s initial configuration could reflect
some prior knowledge of the environment, but as the agent gains experience this may be modified
and augmented. There are extreme cases in which the environment is completely known a priori
and completely predictable. In such cases, the agent need not perceive or learn; it simply acts
correctly.

2.3 THE NATURE OF ENVIRONMENTS

The first step in designing an AI agent is to specify the task environment. The task
environment is comprised PEAS (Performance, Environment, Actuators, Sensors) description

1. Performance Measure: Performance measure is the unit to define the success of an agent.
Performance varies with agents based on their different precepts. our automated driver to aspire?
Desirable qualities include getting to the

 Correct destination
 Minimizing
 Fuel consumption and Wear and tear;
 Minimizing the trip time or cost
 minimizing violations of traffic laws and Disturbances to other drivers
 Maximizing safety and passenger comfort
 Maximizing profits

2. Environment: The environment refers to the agent's immediate surroundings at the time the
agent is working in that environment. Depending on the mobility of the agent, it might be static or
dynamic. The needed sensors and behaviors of the Agent will also alter in response to a slight
change in the surroundings.

 Roads − Automated automobile drivers ought to be able to go on any type of route,

from local streets to interstates.

 Traffic Conditions − For various types of roadways, there are various traffic conditions
to be found.

3. Actuators: Agents rely on actuators to function in their surroundings. Display boards, object-
picking arms, track-changing devices, etc. are examples of actuators. The environment can alter as
a result of actions taken by agents.
 8
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

 Roads − Automated automobile drivers ought to be able to go on any type of route,

from local streets to interstates.

 Traffic Conditions − For various types of roadways, there are various traffic
conditions to be found.

4. Sensors : By providing agents with a comprehensive collection of Inputs, sensors enable them to
comprehend their surroundings. Agent behavior is influenced by their recent past and their
present input set. Various sensing devices, such as cameras, GPS, odometers, and others, are
examples of sensors.

 In-car driving tools like cameras, sonar systems, etc. are used to collect environmental data.

2.3.2 PROPERTIES OF TASK ENVIRONMENTS

The range of task environments that might arise in AI is obviously vast.

 Fully observable vs. partially observable

 Single-agent vs. multiagent
 Deterministic vs. nondeterministic
 Episodic vs. Sequential
 Static vs. dynamic
 Discrete vs. Continuous
 9
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

 Known vs. unknown

Fully observable vs. partially observable

 A fully observable environment is one in which the agent have complete information about
the current state of the environment

 A partially observable environment is one in which the agent does not have complete
information about the current state of the environment.
Examples:
 Chess – the board is fully observable, and so are the opponent’s moves.

 Driving – the environment is partially observable because what’s around the corner
is not known.
Single-agent vs. multiagent
 An environment consisting of only one agent is said to be a single-agent environment. A
person left alone in a maze is an example of the single-agent system.

 An environment involving more than one agent is a multi-agent environment. The game
of football is multi-agent as it involves 11 players in each team.

Cooperative: All agents working towards a common goal.

Competitive: Agents competing with one another to accomplish a goal. · Some mix of the
two: Think a 5v5 basketball game, where individuals on the same team are coordinating
with one another, but the two teams are competing against one another.

Deterministic vs. Nondeterministic

 In a deterministic algorithm, for a given particular input, the computer will always
produce the same output going through the same states. For a particular input, the
computer will give always the same output. Taxi driving is clearly nondeterministic in this
sense, because one can never predict the behavior of traffic exactly; moreover, one’s tires
may blow out unexpectedly and one’s engine may seize up without warning.

 In a non-deterministic algorithm, for the same input, the compiler may produce
different output in different runs. In fact, non-deterministic algorithms can’t solve the
problem in polynomial time and can’t determine what is the next step. The non-
deterministic algorithms can show different behaviors for the same input on different
execution and there is a degree of randomness to it. For a particular input the computer
will give different outputs on different execution.

The vacuum world as we described it is deterministic, but variations can include

nondeterministic elements such as randomly appearing dirt and an unreliable suction
mechanism
 10
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

One final note: the word stochastic is used by some as a synonym for “nondeterministic,”
Stochastic but we make a distinction between the two terms; we say that a model of the
environment is stochastic if it explicitly deals with probabilities (e.g., “there’s a 25% chance of rain
tomorrow”) and “nondeterministic” if the possibilities are listed without being quantified (e.g.,
“there’s a chance of rain tomorrow”).

Episodic vs. Sequential

 In an Episodic task environment, each of the agent’s actions is divided into atomic
incidents or episodes. There is no dependency between current and previous incidents. In
each incident, an agent receives input from the environment and then performs the
corresponding action.
Example: Consider an example of Pick and Place robot, which is used to detect
defective parts from the conveyor belts. Here, every time robot(agent) will make the
decision on the current part i.e. there is no dependency between current and previous
decisions.
 In a Sequential environment, the previous decisions can affect all future decisions. The
next action of the agent depends on what action he has taken previously and what action
he is supposed to take in the future.

Example: Checkers- Where the previous move can affect all the following moves.

In an episodic task environment, the agent’s experience is divided into atomic episodes. In
each episode the agent receives a percept and then performs Sequential a single action. Crucially,
the next episode does not depend on the actions taken in previous episodes. Many classification
tasks are episodic.

For example, an agent that has to spot defective parts on an assembly line bases each
decision on the current part, regardless of previous decisions; moreover, the current decision
doesn’t affect whether the next part is defective. In sequential environments, on the other hand, the
current decision could affect all future decisions.

Chess and taxi driving are sequential: in both cases, short-term actions can have long-term
consequences. Episodic environments are much simpler than sequential environments because the
agent does not need to think ahead.

Static vs. Dynamic

 An idle environment with no change in its state is called a static environment.

An empty house is static as there’s no change in the surroundings when an agent enters.

 An environment that keeps constantly changing itself when the agent is up with some
action is said to be dynamic.A roller coaster ride is dynamic as it is set in motion and the
environment keeps changing every instant.

Discrete vs. Continuous

 11
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

 If an environment consists of a finite number of actions that can be deliberated in the

environment to obtain the output, it is said to be a discrete environment.
The game of chess is discrete as it has only a finite number of moves. The number of
moves might vary with every game, but still, it’s finite.

 The environment in which the actions are performed cannot be numbered i.e. is not
discrete, is said to be [Link]-driving cars are an example of continuous
environments as their actions are riving, parking, etc. which cannot be numbered.

Known vs. unknown

 In a known environment, the output for all probable actions is given. Obviously, in case
of unknown environment, for an agent to make a decision, it has to gain knowledge about
how the environment works.

2.4 THE STRUCTURE OF AGENTS

To understand the structure of Intelligent Agents, we should be familiar

with Architecture and Agent programs. Architecture is the machinery that the agent executes
on. It is a device with sensors and actuators, for example, a robotic car, a camera, and a PC. An
agent program is an implementation of an agent function. An agent function is a map from the
percept sequence(history of all that an agent has perceived to date) to an action.

Agent = Architecture + Agent Program

There are many examples of agents in artificial intelligence. Here are a few:
 Intelligent personal assistants: These are agents that are designed to help users with various
tasks, such as scheduling appointments, sending messages, and setting reminders. Examples
of intelligent personal assistants include Siri, Alexa, and Google Assistant.

 Autonomous robots: These are agents that are designed to operate autonomously in the
physical world. They can perform tasks such as cleaning, sorting, and delivering goods.
 12
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

Examples of autonomous robots include the Roomba vacuum cleaner and the Amazon
delivery robot.

 Gaming agents: These are agents that are designed to play games, either against human
opponents or other agents. Examples of gaming agents include chess-playing agents and
poker-playing agents.

TYPES OF AGENTS

Agents can be grouped into five classes based on their degree of perceived intelligence
and capability
 Simple Reflex Agents
 Model-Based Reflex Agents
 Goal-Based Agents
 Utility-Based Agents
 Intelligent Agents

Simple Reflex Agents

Simple reflex agents ignore the rest of the percept history and act only on the basis of
the current percept. Percept history is the history of all that an agent has perceived to date. The
agent function is based on the condition-action rule.

A condition-action rule is a rule that maps a state i.e., a condition to an action. If the
condition is true, then the action is taken, else not. This agent function only succeeds when the
environment is fully observable. For simple reflex agents operating in partially observable
environments, infinite loops are often unavoidable. It may be possible to escape from infinite
loops if the agent can randomize its actions.

Problems with Simple reflex agents are :

 Very limited intelligence.
 No knowledge of non-perceptual parts of the state.
 Usually too big to generate and store.
 If there occurs any change in the environment, then the collection of rules needs to be
updated.
 13
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

Model-Based Reflex Agents

It works by finding a rule whose condition matches the current situation. A model-based
agent can handle partially observable environments by the use of a model about the world.
The agent has to keep track of the internal state which is adjusted by each percept and that
depends on the percept history. The current state is stored inside the agent which maintains some
kind of structure describing the part of the world which cannot be seen.
 Updating the state requires information about:
 How the world evolves independently from the agent?
 How do the agent’s actions affect the world?
 14
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

Goal-Based Agents
These kinds of agents take decisions based on how far they are currently from
their goal(description of desirable situations). Their every action is intended to reduce their
distance from the goal. This allows the agent a way to choose among multiple possibilities,
selecting the one which reaches a goal state. The knowledge that supports its decisions is
represented explicitly and can be modified, which makes these agents more flexible. They
usually require search and planning. The goal-based agent’s behavior can easily be changed.
 15
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

Utility-Based Agents
The agents which are developed having their end uses as building blocks are called
utility-based agents. When there are multiple possible alternatives, then to decide which one is
best, utility-based agents are used. They choose actions based on a preference (utility) for each
state. Sometimes achieving the desired goal is not enough.

We may look for a quicker, safer, cheaper trip to reach a destination. Agent happiness
should be taken into consideration. Utility describes how “happy” the agent is. Because of the
uncertainty in the world, a utility agent chooses the action that maximizes the expected utility. A
utility function maps a state onto a real number which describes the associated degree of
happiness.
 16
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

Learning Agent
A learning agent in AI is the type of agent that can learn from its past experiences or it
has learning capabilities. It starts to act with basic knowledge and then is able to act and adapt
automatically through learning. A learning agent has mainly four conceptual components, which
are:
1. Learning element: It is responsible for making improvements by learning from the
environment.
2. Critic: The learning element takes feedback from critics which describes how well the
agent is doing with respect to a fixed performance standard.
3. Performance element: It is responsible for selecting external action.
4. Problem Generator: This component is responsible for suggesting actions that will lead
to new and informative experiences .
 17
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

3.1 PROBLEM-SOLVING AGENTS

In artificial intelligence, a problem-solving agent refers to a type of intelligent agent
designed to address and solve complex problems or tasks in its environment. These agents are a
fundamental concept in AI and are used in various applications, from game-playing algorithms to
robotics and decision-making systems.. With that information, the agent can follow this four-phase
problem-solving process.

Goal formulation

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

Problem formulation

Problem formulation is the process of deciding what actions and states to consider, given a
goal. The process of looking for a sequence of actions that reaches the goal is called search. A
search algorithm takes a problem as input and returns a solution in the form of an action sequence.

Search

Before taking any action in the real world, the agent simulates sequences of actions in its model,
searching until it finds a sequence of actions that reaches the goal .Such a sequence is called a
solution. The agent might have to simulate multiple sequences that do not reach the goal, but
eventually it will find a solution or it will find that no solution is possible.

Execution

The agent can now execute the actions in the solution, one at a time

3.3 SEARCH ALGORITHMS

Search algorithm takes a search problem as input and returns a solution, or an indication of Search
algorithm failure

 Each node in the search tree corresponds to a state in the state space and
 the edges Node in the search tree correspond to actions.
 The root of the tree corresponds to the initial state of the problem.
 18
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

3.3.1 search data structures

Search algorithms require a data structure to keep track of the search tree. A node in the tree
is represented by a data structure with four components:

• [Link]: the state to which the node corresponds;

• [Link]: the node in the tree that generated this node;
• [Link]: the action that was applied to the parent’s state to generate this node;
• [Link]-COST: the total cost of the path from the initial state to this node.

In mathematical formulas, we use g(node) as a synonym for PATH-COST. Following the PARENT
pointers back from a node allows us to recover the states and actions along the path to that node.
Doing this from a goal node gives us the solution.

We need a data structure to store the frontier. The appropriate choice is a queue of some kind,
because the operations on a frontier are:

• IS-EMPTY(frontier) returns true only if there are no nodes in the frontier.

• POP(frontier) removes the top node from the frontier and returns it.
• TOP(frontier) returns (but does not remove) the top node of the frontier.
• ADD(node, frontier) inserts node into its proper place in the queue.

Three kinds of queues are used in search algorithms:

A priority queue first pops the node with the minimum cost according to some evaluation
function, f . It is used in best-first search.

A FIFO queue or first-in-first-out queue first pops the node that was added to the queue
first; we shall see it is used in breadth-first search.

A LIFO queue or last-in-first-out queue (also known as a stack) pops first the most recently added
node; we shall see it is used in depth-first search. The reached states can be stored as a lookup table
(e.g. a hash table) where each key is a state and each value is the node for that state

3.3.2 Measuring problem-solving performance

We can evaluate an algorithm’s performance in four ways

 Completeness: Is the algorithm guaranteed to find a solution when there is one, and to
correctly report failure when there is not?
 Cost optimality: Does it find a solution with the lowest path cost of all solutions?
 Time complexity: How long does it take to find a solution? This can be measured in
seconds, or more abstractly by the number of states and actions considered.
 Space complexity: How much memory is needed to perform the search?
 19
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

3.4 UNINFORMED SEARCH STRATEGIES

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
 20
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

1. Breadth-first Search:
o readth-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.
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:
 21
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

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.
 22
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

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.

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:

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.
 23
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

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 space complexity of DFS is equivalent to the size of the fringe
set, which is O(bm).

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:

 24
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

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.

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:
 25
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

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:

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.
 26
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

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.
 27
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

5. Iterative deepeningdepth-first Search:

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:

1st 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.
 28
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

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:
 29
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

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.
 30
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

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.

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.

3.4.6 Comparing uninformed search algorithms

Figure 3.15 compares uninformed search algorithms in terms of the four evaluation
criteria set
 31
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

forth in Section 3.3.4. This comparison is for tree-like search versions which don’t
check for
repeated states. For graph searches which do check, the main differences are that
depth-first
search is complete for finite state spaces, and the space and time complexities are
bounded
by the size of the state space (the number of vertices and edges, |V|+|E|).
 32
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

UNIT – II

3.5 INFORMED (HEURISTIC) SEARCH STRATEGIES

The algorithms of an informed search contain information regarding the goal state. It helps
an AI make more efficient and accurate searches. A function obtains this data/info to estimate the
closeness of a state to its goal in the system. For example, Graph Search and Greedy Search.

3.5.1 Greedy best-first search

Greedy best-first search is a form of best-first search that expands first the node with the
lowest h(n) value—the node that appears to be closest to the goal—on the grounds that this is likely
to lead to a solution quickly. So the evaluation function f (n) = h(n). Consider the graph which is
given below:

irst search
algorithm:
◦
 33
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

We have to travel from the source to the destination at the minimum cost. Since we have
three feasible solutions having cost paths as 10, 20, and 5. 5 is the minimum cost path so it is the
optimal solution. This is the local optimum, and in this way, we find the local optimum at each
stage in order to calculate the global optimal solution

Applications of Greedy Algorithm

 It is used in finding the shortest path.
 It is used to find the minimum spanning tree using the prim's algorithm or the Kruskal's
algorithm.
 It is used in a job sequencing with a deadline.
 This algorithm is also used to solve the fractional knapsack problem.

A* SEARCH ALGORITHM
What is A* Search Algorithm?

A* Search algorithm is one of the best and popular technique used in path-finding and
graph traversals A * (pronounced "A-star") is a powerful graph traversal and pathfinding algorithm
widely used in artificial intelligence and computer science.

It is mainly used to find the shortest path between two nodes in a graph, given the estimated
cost of getting from the current node to the destination node. The main advantage of the algorithm
is its ability to provide an optimal path by exploring the graph in a more informed way compared to
traditional search algorithms such as Dijkstra's algorithm.

Algorithm A* combines the advantages of two other search algorithms: Dijkstra's algorithm
and Greedy Best-First Search. Like Dijkstra's algorithm, A* ensures that the path found is as short
as possible but does so more efficiently by directing its search through a heuristic similar to Greedy
Best-First Search.

A heuristic function, denoted h(n), estimates the cost of getting from any given node n to the
destination node. This kind of algorithm looks at the problem of re-arranging an array of items in
ascending order. The two most classical examples of that is the binary search and the merge sort
algorithm

To find the lowest cost path, a search tree is constructed in the following way:

1. Initialize a tree with the root node being the start node S.
2. Remove the top node from the open list for exploration.
3. Add the current node to the closed list.
4. Add all nodes that have an incoming edge from the current node as child nodes in the tree.
 34
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

5. Update the lowest cost to reach the child node.

6. Compute the evaluation function for every child node and add them to the open list.

Consider the following example of trying to find the shortest path from S to G in the following
graph:

Each edge has an associated weight, and each node has a heuristic cost (in parentheses). An open
list is maintained in which the node S is the only node in the list. The search tree can now be
constructed.

Exploring S:
 35
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

A is the current most promising path, so it is explored next:

Exploring D:
 36
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE
 37
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

Exploring F:

Notice that the goal node G has been found. However, it hasn’t been explored, so the
algorithm continues because there may be a shorter path to G.

The node B has two entries in the open list: one at a cost of 16 (child of S) and one at a cost
of 18 (child of A). The one with the lowest cost is explored next
 38
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

Exploring C:
 39
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

The next node in the open list is again B. However, because B has already been explored, meaning
a shortest path to B has been found, it is not explored again and the algorithm continues to the next
candidate.

he next node to be explored is the goal node G, meaning the shortest path to G has been
found! The path is constructed by tracing the graph backward from G to S:
 40
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

4.1 LOCAL SEARCH AND OPTIMIZATION PROBLEMS

Local search algorithms operate by searching from a start state to neighboring states,
without keeping track of the paths, nor the set of states that have been reached. That means they are
not systematic—they might never explore a portion of the search space where a solution actually
resides. However, they have two key advantages:

 They use very little memory

 They can often find reasonable solutions in large or infinite state spaces for which
systematic algorithms are unsuitable

4.1.1 HILL-CLIMBING SEARCH

Hill climbing is a simple optimization algorithm used in Artificial Intelligence (AI) to
find the best possible solution for a given problem. It belongs to the family of local search
algorithms and is often used in optimization problems where the goal is to find the best solution
from a set of possible solutions.
 41
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

 In Hill Climbing, the algorithm starts with an initial solution and then iteratively makes
small changes to it in order to improve the solution. These changes are based on a
heuristic function that evaluates the quality of the solution. The algorithm continues to
make these small changes until it reaches a local maximum, meaning that no further
improvement can be made with the current set of moves.

 There are several variations of Hill Climbing, including steepest ascent Hill Climbing,
first-choice Hill Climbing, and simulated annealing. In steepest ascent Hill Climbing, the
algorithm evaluates all the possible moves from the current solution and selects the one
that leads to the best improvement. In first-choice Hill Climbing, the algorithm randomly
selects a move and accepts it if it leads to an improvement, regardless of whether it is the
best move. Simulated annealing is a probabilistic variation of Hill Climbing that allows
the algorithm to occasionally accept worse moves in order to avoid getting stuck in local
maxima.

Hill Climbing can be useful in a variety of optimization problems, such as scheduling, route
planning, and resource allocation. However, it has some limitations, such as the tendency to get
stuck in local maxima and the lack of diversity in the search space. Therefore, it is often
combined with other optimization techniques, such as genetic algorithms or simulated annealing,
to overcome these limitations and improve the search results.
Advantages of Hill Climbing algorithm:

 Hill Climbing is a simple and intuitive algorithm that is easy to understand and
implement.

 It can be used in a wide variety of optimization problems, including those with a large
search space and complex constraints.

 Hill Climbing is often very efficient in finding local optima, making it a good choice for
problems where a good solution is needed quickly.

 The algorithm can be easily modified and extended to include additional heuristics or
constraints.

Disadvantages of Hill Climbing algorithm:

 Hill Climbing can get stuck in local optima, meaning that it may not find the global
optimum of the problem.

 The algorithm is sensitive to the choice of initial solution, and a poor initial solution may
result in a poor final solution.

 Hill Climbing does not explore the search space very thoroughly, which can limit its
ability to find better solutions.
 42
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

 It may be less effective than other optimization algorithms, such as genetic algorithms or
simulated annealing, for certain types of problems.

Hill Climbing is a heuristic search used for mathematical optimization problems in the field of
Artificial Intelligence. Given a large set of inputs and a good heuristic function, it tries to find a
sufficiently good solution to the problem. This solution may not be the global optimal
maximum.

 In the above definition, mathematical optimization problems imply that hill-climbing

solves the problems where we need to maximize or minimize a given real function by
choosing values from the given inputs. Example-Travelling salesman problem where we
need to minimize the distance traveled by the salesman.

 ‘Heuristic search’ means that this search algorithm may not find the optimal solution to
the problem. However, it will give a good solution in a reasonable time.

 A heuristic function is a function that will rank all the possible alternatives at any
branching step in the search algorithm based on the available information. It helps the
algorithm to select the best route out of possible routes.

Features of Hill Climbing

Following are some main features of Hill Climbing Algorithm

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

 Greedy approach: Hill-climbing algorithm search moves in the direction which optimizes
the cost.

 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.
 43
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

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:

 Simple hill Climbing:

 Steepest-Ascent hill-climbing:
 Stochastic hill Climbing:

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
 44
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

better than the current state, then move else be in the same state. This algorithm has the
following features:

 Less time consuming

 Less optimal solution and the solution is not guaranteed

Algorithm for Simple Hill Climbing

 Step 1: Evaluate the initial state, if it is goal state then return success and Stop.

 Step 2: Loop Until a solution is found or there is no new operator left to apply.

 Step 3: Select and apply an operator to the current state.

 Step 4: Check new state

1. If it is goal state, then return success and quit.

2. Else if it is better than the current state then assign new state as a current state.

3. Else if not better than the current state, then return to step2.

 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

 Step 1: Evaluate the initial state, if it is goal state then return success and stop, else make
current state as initial state.

 Step 2: Loop until a solution is found or the current state does not change.

1. Let SUCC be a state such that any successor of the current state will be better than it.

2. For each operator that applies to the current state:

1. Apply the new operator and generate a new state.

2. Evaluate the new state.

 45
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

3. If it is goal state, then return it and quit, else compare it to the SUCC.

4. If it is better than SUCC, then set new state as SUCC.

5. If the SUCC is better than the current state, then set current state to SUCC.
 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.
 46
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

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

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

4.2 LOCAL SEARCH IN CONTINUOUS SPACES

4.3 SEARCH WITH NONDETERMINISTIC ACTIONS

The simple answer is a non-deterministic system is one where the same input can produce
different outputs and can also produce the same output.. It's non-deterministic because we can't
determine ahead of time what the output will be and therefore can't rely on the output to be
consistent.

AND–OR SEARCH TREES

The AO* method divides any given difficult problem into a smaller group of problems that are
then resolved using the AND-OR graph concept. AND OR graphs are specialized graphs that
 47
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

are used in problems that can be divided into smaller problems. The AND side of the graph
represents a set of tasks that must be completed to achieve the main goal, while the OR side of
the graph represents different methods for accomplishing the same main goal.

In the above figure, the buying of a car may be broken down into smaller problems or tasks that
can be accomplished to achieve the main goal in the above figure, which is an example of a
simple AND-OR graph.

The other task is to either steal a car that will help us accomplish the main goal or use
your own money to purchase a car that will accomplish the main goal. The AND symbol is used
to indicate the AND part of the graphs, which refers to the need that all subproblems containing
the AND to be resolved before the preceding node or issue may be finished.

The start state and the target state are already known in the knowledge-based search
strategy known as the AO* algorithm, and the best path is identified by heuristics. The
informed search technique considerably reduces the algorithm’s time complexity. The AO*
algorithm is far more effective in searching AND-OR trees than the A* algorithm.

Working of AO* algorithm:

The evaluation function in AO* looks like this:
f(n) = g(n) + h(n)
f(n) = Actual cost + Estimated cost
here,
f(n) = The actual cost of traversal.
g(n) = the cost from the initial node to the current node.
 48
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

h(n) = estimated cost from the current node to the goal state.

DIFFERENCE BETWEEN THE A* AND AO* ALGORITHM

 A* algorithm and AO* algorithm both works on the best first search.
 They are both informed search and works on given heuristics values.
 A* always gives the optimal solution but AO* doesn’t guarantee to give the optimal
solution.
 Once AO* got a solution doesn’t explore all possible paths but A* explores all paths.
 When compared to the A* algorithm, the AO* algorithm uses less memory.
 opposite to the A* algorithm, the AO* algorithm cannot go into an endless loop

4.4 SEARCH IN PARTIALLY OBSERVABLE ENVIRONMENTS

Environments in which the agent’s sensors provide access to only partial or incomplete
information about the state of the environment at each point in time. are known as partially
observable environments.

Unlike fully observable environments where the agent has complete access to all relevant
aspects of the environment, in a partially observable environment, certain states or factors may
be obscured, uncertain, or missing from the sensor data.

The absence of complete information creates difficulties in decision-making because the

agent might not fully grasp the present situation or find it challenging to predict future situations
with accuracy.

Partial observability may result from different causes, such as imprecise sensors,
restricted sensor range, or the complexity of the environment. In a partially observable
environment, agents must employ strategies to address partial observability include state
estimation, probabilistic reasoning, and memory utilization. Formal frameworks such as Partially
Observable Markov Decision Processes (POMDPs) are commonly used to model and solve
problems in such environments, enabling agents to develop sophisticated strategies that balance
exploration and exploitation.

Characteristics of Partially Observable Environments

1. Incomplete Perception: Agents’ sensors provide access to only partial or incomplete

information about the environment’s state at each point in time.
 49
SSM COLLEGE OF ARTS & SCIENCE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE
FOUNDATION OF ARTIFICIAL INTELLIGENCE II [Link] ARTIFICIAL INTELLIGENCE & DATA SCIENCE

2. Uncertainty: The agent’s understanding of the environment is uncertain due to obscured or

missing information, making decision-making challenging.

3. Limited Access: Certain states or factors may be obscured, uncertain, or unavailable from
the sensor data, hindering the agent’s ability to perceive the complete environment.
4. Complex Decision-Making: Agents must employ strategies to cope with uncertainty, such
as state estimation, probabilistic reasoning, or memory utilization, to make informed
decisions.

5. Need for Sophisticated Techniques: Dealing with partial observability requires the use of
advanced techniques like Partially Observable Markov Decision Processes (POMDPs) to
model and solve problems effectively.

Poker Game, Autonomous driving, Robot navigation is example

4.5 ONLINE SEARCH AGENTS AND UNKNOWN ENVIRONMENTS