ARTIFICIAL

INTELLIGENCE
AND MACHINE
LEARNING

PRESENTATION BY:- DR. AMIT KUMAR GANTAYAT

FACULTY MECHANICAL ENGINEERING, VSSUT

INTRODUCTION TO ARTIFICIAL INTELLIGENCE

Artificial Intelligence (AI) is a branch of

computer science that deals with the
creation of intelligent machines capable of
performing tasks that normally require
human intelligence such as learning,
reasoning, problem solving, perception, and
language understanding.
“It is a branch of computer science by which
we can create intelligent machines that can
behave like a human, think like humans, and
be able to make decisions.”

Standard Definitions:
•John McCarthy: “Artificial Intelligence is the science and engineering of making intelligent machines.”
•AI focuses on building rational agents that perceive their environment and act to achieve goals.
Systems that can think humanly Systems that can think rationally
• For following this approach, one first needs to • The aim of this approach is to build upon programs
understand how humans think. Knowing the internal that represent “right thinking”, to create intelligent
working of human brain can be achieved by introspection systems. This “right thinking” or irrefutable reasoning
or psychological experiments. This, in itself, is a vast processes, is defined in coding (in mathematical
interdisciplinary field, known as Cognitive Science. terms)
using logic or laws of thought.
• Systems that can act humanly 1. Not all knowledge can be expressed with logical
• This definition came into being when Alan Turing notations (especially when knowledge is not 100%
proposed the Turing Test. A system passes this test, if it certain).
can fool a human interrogator by depicting intelligent 2. It can lead to computational blow up, as without
behavior. By intelligent behavior, we mean achieving guidance, there are many reasoning steps that can
human level performance in cognitive tasks. Such a be tried.
system would require to have major components of A.I.,
including natural language processing, knowledge • Systems that can act rationally
representation, automated reasoning, machine learning, • This approach involves creating systems that act in
robotics and computer vision. Seeing the underlying a way which maximizes its chances of achieving its
complications, no major effort has been made in trying goal, given the available information. These systems
to make such a machine. are known as Rational Agents,
Machine Learning vs Artificial Intelligence

Aspect Artificial Intelligence (AI) Machine Learning (ML)

Broad field of making Subset of AI focused on
Definition
machines intelligent learning from data
Includes reasoning, Mainly data-driven
Scope
planning, NLP, robotics learning algorithms
Strongly dependent on
Dependency May or may not use data
data
Spam filtering,
Example Chatbots, expert systems
recommendation systems

Machine Learning is a subset of Artificial Intelligence.

AI TYPE 1: BASED ON CAPABILITIES

[Link] AI or Narrow AI: This type of AI can be used to solve certain problems and focus on a particular
kind of job. It is only effective when it is used in a specific area and does not produce the same results
when applied in other areas. It applies to smart products, known as virtual assistants such as Siri,
systems engaged in image recognition, and IBM's Watson.

[Link] AI: General AI, also known as Strong AI, on the other hand, refers to machines capable of
achieving any action that a man is capable of accomplishing. It is planning to attain human-like features
such as intelligence characteristics like reasoning and learning processes. This is another type of AI that
is still under research and has not been developed to its realization.

[Link] AI: An advanced artificial intelligence in which every domain is superior to that of humans in
terms of their decision-making power, problem-solving skills, learning capabilities, as well as their feelings
and emotions. It is the final stage of AI development, and it does not currently exist in the world.
Narrow AI (Weak AI)
Narrow AI is designed to perform a specific task or a limited range of tasks.
Examples:
•Voice assistants (Siri, Alexa)
•Face recognition systems
•Recommendation engines
General AI (Strong AI)
General AI refers to machines with human-level intelligence capable of performing any intellectual task that a
human can do.
Status:
•Still theoretical
•Does not exist currently
Difference Between Narrow AI and General AI

Feature Narrow AI General AI

Intelligence Task-specific Human-like
Flexibility Low High
Current Status Exists today Not yet achieved
AI TYPE 2: BASED ON FUNCTIONALITY
7
[Link] Machines: This type of AI processes the current input data and does not have any previous
experience. They follow pre-defined rules. Some of the most widely known examples include IBM's chess
machine known as Deep Blue and the Go-playing computer termed Google's AlphaGo.

[Link] Memory: Many of them use the earlier information to establish something for a limited period. Some
of the concrete samples include self-driving cars that follow other vehicles, the speed, and the road condition of
the environment.

[Link] of Mind: The purpose of this AI is to comprehend the feelings, desires or even gestures of people. As
previously stated, it is still part of the theoretical research and has not been fully realized.

[Link]-Awareness: The final type of artificial intelligence that remains at the level of theory is even more
superior to human intelligence as it would have consciousness and feelings. People would consider this level of
AI as a significant level of advancement in technology as well as in knowledge.
 History of Artificial Intelligence
Early Development (1940–1956)
•1943: Artificial neuron model by McCulloch and Pitts.
•1950: Alan Turing proposed the Turing Test.
•1956: Term “Artificial Intelligence” coined by John McCarthy
(Dartmouth Conference).
Growth Period (1956–1970)
Goals of Artificial Intelligence •Development of symbolic AI and problem-solving programs.
The main goals of AI are: •Programs for chess playing and theorem proving.
[Link] create expert systems that exhibit intelligent •Optimism about achieving human-level intelligence.
behavior. AI Winter (1970–1990)
[Link] implement human intelligence in machines. •Limited computing power and memory.
[Link] enable learning from experience. •Failure to meet expectations.
[Link] perform tasks efficiently and accurately. •Reduction in research funding.
Revival Phase (1990–2010)
•Emergence of machine learning and expert systems.
•Improved hardware and availability of data.
•Practical AI applications in industries.
Modern AI (2010–Present)
•Deep learning and neural networks.
•Big data and high-performance computing.
•AI success in speech, vision, and language tasks
Foundations of Artificial Intelligence
AI is an interdisciplinary field based on the following foundations:
Mathematics
•Linear algebra, probability, statistics, calculus.
•Used in optimization and machine learning models.
Computer Science
•Algorithms and data structures.
•Programming languages and software systems.
Philosophy
•Logic, reasoning, knowledge representation.
•Concepts of mind and intelligence.
Psychology & Cognitive Science
•Human learning and behavior.
•Models of perception and decision making.
Neuroscience
•Study of biological neural systems.
•Basis for artificial neural networks.
Linguistics
•Syntax and semantics of language.
•Foundation for natural language processing.
Intelligent Agents
Definition
An intelligent agent is an entity that
perceives its environment through sensors
and acts upon that environment using
actuators.
Components of an Intelligent Agent
•Sensors
•Actuators
•Environment
•Performance measure
Types of Agents
[Link] Reflex Agent
[Link]-Based Agent
[Link]-Based Agent
[Link]-Based Agent
[Link] Agent
Simple reflex agent: Simple reflex agents ignore the rest Model-based reflex agents: It works by searching for a rule
of the concept history and act only based on the current whose position matches the current state. A model-based
concept. Concept history is the history of all that an agent can handle a partially observable environment using
a model about the world. The agent has to keep track of
agent has believed to date. The agent function is based
the internal state, adjusted by each concept, depending on
on the condition-action rule. A condition-action rule is a
the concept history. The current state is stored inside the
rule that maps a state, that is, a condition, to an action. agent, which maintains some structure describing the part
If the condition is true, then action is taken; otherwise, of the world that cannot be seen.
not.
Goal-based agents: These types of agents make Utility-based agents: The agents which are developed having their end
decisions based on how far they are currently uses as building blocks are called utility-based agents. When there are
from their goals (details of desired conditions). multiple possible alternatives, then to decide which one is best,
utility-based agents are used. They choose actions based on a
Their every action is aimed at reducing its
preference (utility) for each state. Sometimes achieving the desired
distance from the target. This gives the agent a
goal is not enough. We may look for a quicker, safer, cheaper trip to
way to choose from a number of possibilities, reach a destination. Agent happiness should be taken into
leading to a target position. The knowledge consideration.
supporting their decisions is clearly presented Utility describes how "happy" the agent is. Because of the uncertainty
and can be modified, which makes these agents in the world, a utility agent chooses the action that maximizes the
more flexible. expected utility. A utility function maps a state onto a real number
which describes the associated degree of happiness.
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:
• Learning element: It is responsible for making
improvements by learning from the environment
• Critic: The learning element takes feedback from
critics which describe how well the agent is doing
with respect to a fixed performance standard.
• Performance element: It is responsible for selecting
external action
• Problem Generator: This component is responsible
for suggesting actions that will lead to new and
informative experiences.
PEAS stands for performance measure, environment, actuators, and sensors. PEAS defines AI models and helps
determine the task environment for an intelligent agent.
• Performance measure: It defines the success of an agent. It evaluates the criteria that determines whether the
system performs well.
• Environment: It refers to the external context in which an AI system operates. It encapsulates the physical and
virtual surroundings, including other agents, objects, and conditions.
• Actuators: They are responsible for executing actions based on the decisions made. They interact with the
environment to bring about desired changes.
• Sensors: An agent observes and perceives its environment through sensors. Sensors provide input data to the
system, enabling it to make informed decisions.
Applications of Artificial Intelligence . Advantages of Artificial Intelligence
Healthcare •High accuracy and efficiency
•Medical diagnosis systems •Reduced human error
•AI-based imaging and robotic surgery •Continuous operation (24×7)
Education •Automation of repetitive tasks
•Intelligent tutoring systems
•Personalized learning platforms
Industry . Limitations of Artificial Intelligence
•Robotics and automation •High development cost
•Predictive maintenance •Lack of creativity and emotions
Transportation •Ethical and security issues
•Autonomous vehicles •Dependence on quality data
•Traffic control systems
Finance
•Fraud detection . Future Scope of Artificial Intelligence
•Credit scoring and trading systems •Smart cities
Agriculture •Advanced robotics
•Crop yield prediction •Human-AI collaboration
•Disease detection in plants •Ethical and responsible AI development
 State-Space Problem
Definition
Problem Solving in AI A State-Space Problem is a mathematical representation of a
problem where:
•Each state represents a configuration of the problem
Problem solving in Artificial
•Operators (actions) move the system from one state to
Intelligence involves finding a
another
sequence of actions that transforms
•A solution is a path from the initial state to the goal state
an initial state into a goal state.
Components of a State-Space Problem
AI represents problems formally so
A state-space problem consists of the following elements:
that search algorithms can be applied
[Link] State
to obtain solutions efficiently.
The starting point of the problem.
[Link] Space
In AI, problem solving is generally
The set of all possible states reachable from the initial state.
done using state-space
[Link] / Actions
representation and search techniques.
Rules that define transitions between states.
[Link] State
The desired target state.
[Link] Cost (optional)
Cost associated with moving from one state to another.
PROBLEM, PROBLEM SPACE, SEARCH

A problem is a specific task or challenge that requires finding a solution or making a decision. In artificial
intelligence, problems can vary in complexity and scope, ranging from simple tasks like arithmetic calculations
to complex challenges such as image recognition, natural language processing, game playing, and optimization.
Each problem has a defined set of initial states, possible actions or moves, and a goal state that needs to be
reached or achieved.

The problem space is the set of all possible states, actions, and transitions that can be encountered while
attempting to solve a specific problem. It represents the entire landscape of potential solutions and paths from
the initial state to the goal state. In other words, the problem space defines all the possible configurations or
arrangements of elements involved in the problem and the set of valid moves or actions that can be taken at
each state. Each state in the problem space represents a specific configuration, and each action represents a
possible move or step from one state to another.

Search is the process of exploring the problem space to find a sequence of actions or moves that lead to the
goal state or a satisfactory solution. In AI, search algorithms are used to systematically navigate through the
problem space and discover paths or solutions that satisfy the problem’s constraints and objectives.
State-Space Graph vs Search Tree Importance of State-Space and Search Space
State-Space Graph •Helps in systematic problem solving
•Represents all possible states •Forms the basis for search algorithms like:
•May contain cycles • Breadth First Search (BFS)
Search Tree • Depth First Search (DFS)
•Generated during search • A* Algorithm
•Nodes may repeat •Reduces complexity by defining structured solutions
•Depends on search algorithm

Problem Formulation Using State Space . Advantages and Limitations

Advantages
Example (Vacuum Cleaner Problem): •Clear problem representation
•Initial State: Dirty rooms •Easy application of algorithms
•Operators: Move left, move right, suck •Suitable for many classical AI problems
Limitations
dirt •Large state space leads to state explosion
•Goal Test: All rooms clean •High memory and time consumption
•Path Cost: Number of actions •Not suitable for real-time problems without optimization
 State space Representation involves defining an INITIAL STATE and a GOAL
State space search has
STATE and then determining a sequence of actions, called states, to follow.
several features that make it an
• State: A state can be an Initial State, a Goal State, or any other possible state
effective problem-solving
that can be generated by applying
technique in Artificial
rules between them.
Intelligence. These features
➢ Initial State: The state of the issue as it first arises.
include:
➢ Goal State: The idealized final state that delineates a problem-solving
• Exhaustiveness: State
strategy.
space search explores all
➢ Operators: The collection of maneuvers or actions that can be used to
possible states of a problem to
change a state.
find a solution.
➢ Restrictions: Guidelines or limitations must be adhered to to solve the
• Completeness: If a solution
problem.
exists, state space search will
• Space: In an AI problem, space refers to the exhaustive collection of all
find it.
conceivable states.
• Optimality: Searching
• Search: This technique moves from the beginning state to the desired state by
through a state space results in
applying good rules while traversing the space of all possible states.
an optimal solution.
• Search Tree: To visualize the search issue, a search tree is used, which is a
• Uninformed and Informed
tree-like structure that represents the problem. The initial state is represented by
Search: State space search in
the root node of the search tree, which is the starting point of the tree.
artificial intelligence can be
• Transition Model: This describes what each action does, while Path Cost
classified as uninformed if it
assigns a cost value to each path, an activity sequence that connects the
provides additional information
beginning node to the end node. The optimal option has the lowest cost among all
about the problem.
alternatives.
To begin the search process, we set the current state to
the initial state.
• We then check if the current state is the goal state. If it
is, we terminate the algorithm and return the result.
• If the current state is not the goal state, we generate
the set of possible successor states that can be reached
from
the current state.
• For each successor state, we check if it has already
been visited. If it has, we skip it, else we add it to the
queue of
states to be visited.
• Next, we set the next state in the queue as the current
state and check if it's the goal state. If it is, we return the
result. If not, we repeat the previous step until we find
the goal state or explore all the states.
• If all possible states have been explored and the goal
state still needs to be found, we return with no solution
8-puzzle problem
Search algorithms in AI provide search solutions by
transforming the initial state to the desired state.
Properties of Search Algorithms: The four important
properties of search algorithms in artificial intelligence for
comparing their efficiency are as follows:
• Completeness - A search algorithm is said to be
complete if it guarantees to yield a solution for any
random input if
at least one solution exists.
• Optimality - A solution discovered for an algorithm is
considered optimal if it is assumed to be the best solution
(lowest path cost) among all other solutions.
• Time complexity - It measures how long an algorithm
takes to complete its job.
• Space Complexity - The maximum storage space
required during the search, as determined by the
problem's
complexity.
Uninformed/Blind Search
The uninformed search needs domain information, such as proximity or goal location. It works by brute force
because it only contains information on traversing the tree and identifying leaf and goal nodes.
Uninformed search is a method of searching a search tree without knowledge of the search space, such as initial
state operators and tests for the objective, and is also known as blind search. It goes through each tree node until
it reaches the target node. These algorithms are limited to producing successors and distinguishing between goal
and non-goal states.
[Link]-first search - This is a search method for a graph or tree data structure. It starts at the tree root or
searches key and goes through the adjacent nodes in the current depth level before moving on to the nodes in the
next depth level. It uses the queue data structure that works on the first in, first out (FIFO) concept. It is a complete
algorithm as it returns a solution if a solution exists.
[Link]-first search - It is also an algorithm used to explore graph or tree data structures. It starts at the root
node, as opposed to the breadth-first search. It goes through the branch nodes and then returns. It is implemented
using a stack data structure that works on the concept of last in, first out (LIFO).
 Breadth First Search Algorithm Depth First Search Algorithm
Initialization: Initialization:
1. Start with a designated "SOURCE" node and a "TARGET" 1. Start with a designated source node and a target node.
node. 2. Initialize a stack and push the source node onto it.
2. Initialize a queue and add the source node to it. 3. Maintain a visited set or array to keep track of nodes that have
3. Maintain a "visited" set or array to keep track of nodes already been explored, preventing infinite
already explored, preventing cycles and redundant loops in cyclic graphs.
processing. 4. Optionally, maintain a parent dictionary or array to reconstruct
4. Optionally, maintain a "PARENT" dictionary or array to the path later, storing the node from which each
reconstruct the path later, storing the node from which visited node was reached.
each visited node was reached. • Exploration:
• Exploration: 1. While the stack is not empty:
1. While the queue is not empty: a. Pop a node (the current node) from the top of the stack.
a. Dequeue a node (the "CURRENT" node). b. If the current node is the target node, the path is found.
b. If the current node is the TARGET node, the path is found. i. Reconstruct the path by backtracking through the parent
Reconstruct the path by backtracking through pointers from the target to the source.
the PARENT pointers from the target to the source. c. For each unvisited neighbor of the current node:
c. For each unvisited neighbor of the CURRENT node: i. Mark the neighbor as visited.
i. Mark the neighbor as visited. ii. Set the current node as the neighbor's parent. iii. Push the
ii. Set the CURRENT node as the neighbor's parent. iii. neighbor onto the stack.
Enqueue the neighbor. • Termination: The algorithm terminates when the target node is
• Termination: The algorithm terminates when the TARGET found or when the stack becomes empty (meaning
node is found or when the queue becomes empty the target is unreachable from the source).
(meaning the target is unreachable from the source).
Depth Limited Depth First Search Algorithm
Depth limited search is the new search algorithm for
uninformed search. The unbounded tree problem
happens to appear in the depth-first search algorithm,
and it can be fixed by imposing a boundary or a limit to
the depth of the search domain. We will say that this
limit as the depth limit, making the DFS search strategy
more refined and organized into a finite loop. We denote
this limit by l, and thus this provides the solution to the
infinite path problem that originated earlier in the DFS
algorithm.
 Depth Limited Depth First Search Algorithm

Initialization:
1. Start with a designated source node and a target node.
2. Define a maximum depth limit up to which the search will explore.
3. Maintain a visited set or array to avoid revisiting nodes in the current path.
4. Optionally, maintain a parent dictionary or array to reconstruct the path later.
Exploration (Recursive or Stack-Based):
1. Begin at the source node with the current depth = 0.
2. If the current node is the target node, return success and reconstruct the path using
parent pointers.
3. If the current depth equals the depth limit, terminate this branch (do not expand
further).
4. For each unvisited neighbor of the current node:
a. Mark the neighbor as visited.
b. Set the current node as the neighbor’s parent.
c. Recursively call Depth-Limited Search on the neighbor with depth + 1.
Termination:
1. The search ends when:
a. The target node is found within the depth limit (success), or
b. All paths are explored up to the depth limit without finding the target (failure).
Iterative Deepening Depth-First Search (IDDFS) Algorithm

IDDFS combines depth-first search's space-efficiency and breadth-first search's fast search (for nodes
closer to root). How does IDDFS work?
IDDFS calls DFS for different depths starting from an initial value. In every call, DFS is restricted from
going beyond given depth. So basically, we do DFS in a BFS fashion.
Exercise
Iterative Deepening Depth-First Search (IDDFS) Algorithm

• Initialization:
1. Start with a designated source node and a target node.
2. Set an initial depth limit to 0.
3. Incrementally increase the depth limit by 1 in each iteration until:
a. The target node is found (success), or
b. The maximum allowed depth is reached (failure).
• Exploration:
1. For each depth limit d:
a. Perform a Depth-Limited Search (DLS) starting from the source node with the current depth = 0 and limit
= d.
b. If DLS finds the target node, terminate and reconstruct the path.
c. If DLS reaches the depth limit without success, increase the limit and repeat.
• Termination:
1. The algorithm terminates when:
a. The target node is found at some depth limit (success), or
b. All nodes up to the maximum depth have been explored without finding the target (failure).
 Production rules for the water jug problem in AI are as follows
WATER JUG PROBLEM
1. (x,y) is X<4 -> (4, Y) Fill the 4-litre jug

The Water Jug Problem is a 2. (x, y) if Y<3 -> (x, 3) Fill the 3-litre jug
classic puzzle in artificial 3. (x, y) if x>0 -> (x-d, d)
Pour some water from a 4-
litre jug
intelligence. In this version, there
are two jugs: one with a capacity Pour some water from a 3-
4. (x, y) if Y>0 -> (d, y-d)
litre jug
of 4 liters and another with a
Empty 4-litre jug on the
capacity of 3 liters. Neither jug 5. (x, y) if x>0 -> (0, y)
ground
has any measurement markings.
Empty 3-litre jug on the
A pump is available to completely 6. (x, y) if y>0 -> (x,0)
ground
fill either jug with water. The (x, y) if X+Y >= 4 and y>0 -> (4, y- Pour water from a 3-litre jug into a
7.
objective is to measure exactly 2 (4-x)) 4-litre jug until it is full

liters of water in the 4-liter jug.

(x, y) if X+Y>=3 and x>0 -> (x-(3- Pour water from a 3-litre jug into a
Starting with both jugs empty, the 8.
y), 3)) 4-litre jug until it is full
task is to determine a sequence of
steps that results in exactly 2 liters (x, y) if X+Y <=4 and y>0 -> (x+y, Pour all the water from a 3-litre jug
9.
0) into a 4- litre jug
being poured into the 4-liter jug. In
production rules for the water jug 10.
(x, y) if X+Y<=3 and x>0 -> (0, Pour all the water from a 4-litre jug
x+y) into a 3- litre jug
problem, let x denote a 4-litre jug,
and y denote a 3-litre jug, i.e. Pour 2-litre water from 3-litre jug
11. (0, 2) -> (2, 0)
x=0,1,2,3,4 or y=0,1,2,3 into 4-litre jug
Start state/Initial State = (0,0), Goal
Empty 2-litre in the 4-litre jug on
state = (2,n) from any n 12. (2, Y) -> (0, y)
the ground.
Informed/Heuristic Search Key Characteristics of Informed Search Algorithms
Informed search algorithms are a class of algorithms 1. Heuristic Function: Informed search algorithms use a
in artificial intelligence that use heuristic functions to heuristic function h(n) that provides an estimate of the
guide the search process. A heuristic is a function minimal cost from node n to the goal. This function helps the
that estimates the cost of reaching the goal from a algorithm to prioritize which nodes to explore first
given node, providing additional information that based on their potential to lead to an optimal solution.
helps the algorithm make smarter decisions. 2. Efficiency: By focusing on more promising paths, informed
Role of Heuristics search algorithms often find solutions more quickly
Heuristics play a crucial role in informed search than uninformed methods, especially in large or complex
algorithms. They help prioritize which nodes or search spaces.
paths the algorithm should explore first by 3. Optimality and Completeness: Depending on the heuristic
estimating how close a node is to the goal. This used, informed search algorithms can be both optimal
dramatically reduces the number of states explored, and complete. An algorithm is complete if it is guaranteed to
making the search process more efficient. find a solution if one exists, and it is optimal if it always
Comparison with Uninformed Search finds the best solution. For instance, the A* search algorithm is
In contrast to informed search, uninformed search both complete and optimal when the heuristic
algorithms like breadth-first or depth-first search function is admissible (i.e., it never overestimates the true
explore the search space without any additional cost).
information, often leading to longer search times 4. Admissibility and Consistency of Heuristics: An
and inefficient exploration. For example, breadth- admissible heuristic guarantees that the algorithm finds the
first search explores all possible states level by optimal solution. A heuristic is admissible if it never
level, which can be highly time-consuming in large overestimates the true cost to reach the goal.
search spaces.
HILL CLIMBING
Hill climbing is a widely used optimization algorithm in
Artificial Intelligence (AI) that helps find the best
possible solution to a given problem. As part of the local
search algorithms family, it is often applied to
optimization problems where the goal is to identify the
optimal solution from a set of potential candidates.
In the Hill Climbing algorithm, the state-space diagram
is a visual representation of all possible states the search
algorithm can reach, plotted against the values of the
objective function (the function we aim to maximize).
In the state-space diagram:
• X-axis: Represents the state space, which includes all
the possible states or configurations that the algorithm can
reach.
• Y-axis: Represents the values of the objective function
corresponding to each state.
The optimal solution in the state-space diagram is
represented by the state where the objective function
reaches its maximum value, also known as the global
maximum.
Key Regions in the State-Space Diagram

[Link] Maximum: A local maximum is a state better than its neighbors but not the best overall. While
its objective function value is higher than nearby states, a global maximum may still exist.
[Link] Maximum: The global maximum is the best state in the state-space diagram, where the
objective function achieves its highest value. This is the optimal solution the algorithm seeks.
[Link]/Flat Local Maximum: A plateau is a flat region where neighboring states have the same
objective function value, making it difficult for the algorithm to decide on the best direction to move.
[Link]: A ridge is a higher region with a slope, which can look like a peak. This may cause the
algorithm to stop prematurely, missing better solutions nearby.
[Link] State: The current state refers to the algorithm's position in the state-space diagram during
its search for the optimal solution.
[Link]: A shoulder is a plateau with an uphill edge, allowing the algorithm to move toward better
solutions if it continues searching beyond the plateau.
Types of Hill Climbing
2. Steepest-Ascent Hill Climbing (Gradient
1. Simple Hill Climbing: This is the most basic form of
Ascent/Descent): Evaluates all neighbors and moves to
hill climbing. The algorithm evaluates each neighboring
the neighbor
state
with the highest improvement (or lowest cost).
in sequence and moves to the first neighbor that improves
• Pros: More likely to find a better solution than simple hill
the objective function.
climbing since it considers all possible moves.
• Pros: Simple and easy to implement.
• Cons: More computationally expensive as it evaluates
• Cons: Can get stuck in local optima easily and may
all neighbors before making a move.
require many iterations to find a better solution.
Steps:
Steps:
1. Start with an Initial Solution: Choose an initial state
1. Start with an Initial Solution: Choose an initial state
(solution) randomly or based on some heuristic.
(solution) randomly or based on some heuristic.
2. Evaluate the Initial Solution: Compute the value of
2. Evaluate the Initial Solution: Compute the value of
the objective function for the current state.
the objective function for the current state.
3. Generate Neighbors: Generate the neighboring states
3. Generate Neighbors: Generate the neighboring states
of the current state.
of the current state.
4. Evaluate All Neighbors: Evaluate all neighbors to
4. Evaluate Neighbors: Evaluate each neighbor to see if
determine the one with the best (highest or lowest)
it improves the objective function.
objective function value.
5. Select the First Better Neighbor: Move to the first
5. Select the Best Neighbor: Move to the neighbor with
neighbor that has a better (higher or lower, depending on
the best objective function value.
the problem) objective function value.
6. Repeat: Repeat steps 3-5 until no neighbor improves
6. Repeat: Repeat steps 3-5 until no improvement is
the objective function.
found (i.e., no neighbor is better than the current state).
3. Stochastic Hill Climbing: Selects a random neighbor and moves to it if it improves the objective
function. The
randomness helps in exploring the search space more broadly.
• Pros: Can escape local optima more effectively than simple hill climbing.
• Cons: Less predictable and may require more iterations to converge.
Steps:
1. Start with an Initial Solution: Choose an initial state (solution) randomly or based on some heuristic.
2. Evaluate the Initial Solution: Compute the value of the objective function for the current state.
3. Generate a Random Neighbor: Generate a random neighboring state of the current state.
4. Evaluate the Neighbor: Compute the value of the objective function for the random neighbor.
5. Accept or Reject the Neighbor: Move to the neighbor if it has a better (higher or lower) objective
function
value.
6. Repeat: Repeat steps 3-5 until no further improvement is found.
BEST FIRST SEARCH48
Best First Search is a heuristic search algorithm that
selects the most promising node for expansion based on
an evaluation function. It prioritizes nodes in the search
space using a heuristic to estimate their potential. By
iteratively choosing the most promising node, it aims to
efficiently navigate towards the goal state, making it
particularly effective for optimization problems

Greedy Best First Search

Evaluating Function
𝑓(𝑛) = h(𝑛)
h(n) = Heuristic Function
A* ALGORITHM
A* (A-Star) is a popular choice for pathfinding because it
combines the strengths of Dijkstra's algorithm and Greedy
Best-First Search, making it efficient and optimal. It uses a
heuristic function to evaluate paths by balancing the cost
to reach a node (g-cost [g(n)]) and the estimated cost to
the goal (h-cost [h(n)]).
A* uses two important parameters to find the cost of a
path: Find the most cost-effective path to reach the final
1. g(n): Actual cost of reaching node n from the start state from initial state using A* Algorithm. Consider
node. This is the accumulated cost of the path from the g(n) = Depth of node and h(n) = Number of misplaced
start node tiles.
to node n.
2. h(n): The heuristic finds of the cost to reach the goal
from node n. This is a weighted guess about how much
further
it will take to reach the goal.
The function, f(n)=g(n)+h(n) is the total estimated cost of
the cheapest solution through node n. This function
combines the path cost so far and the heuristic cost to
estimate the total cost guiding the search more efficiently.
Find the most cost-effective path to reach from start state
A to final state J using A* Algorithm.
ADMISSIBILITY OF A* ALGORITHM
The cost of reaching the goal state is assessed using an admissible heuristic in an informed
search algorithm, however, if we need to discover a solution to the problem, the estimated cost
must be lower than or equal to the true cost of reaching the goal state. The algorithm employs the
allowable heuristic to determine the best-estimated route from the current node to the objective
state.
The evaluation function in A* looks like this: f(n) = g(n) + h(n)
f(n) = Actual cost + Estimated cost
here,
n = current node. f(n) = evaluation function.
g(n) = the cost from the initial node to the current node. h(n) = estimated cost from the current
node to the goal state.
Conditions:
h(n) ≤ h*(n) ∴ Underestimation
h(n) ≥ h*(n) ∴ Overestimation Key Points:
• The heuristic function h(n) is admissible if h(n) is never larger than h*(n) or if h(n) is always
less or equal to the true
value.
• If A* employs an admissible heuristic and h(goal)=0, then we can argue that A* is admissible.
• If the heuristic function is constantly tuned to be low with respect to the true cost, i.e. h(n) ≤
h*(n), then you are going
to get an optimal solution of 100%
Case 1:
Let's suppose, you are going to purchase shoes and shoes have a price of $1000. Before making the purchase, you
estimated that the shoes will be worth $1200, When you went to the store, the shopkeeper informed you that the
shoe's actual price was $1000, which is less than your estimated value, indicating that you had overestimated their
value by $200. so this is the case of Overestimation.
1200 > 1000
i.e. h(n) ≥ h*(n) ∴ Overestimation

Case 2:
Similar to the last situation, you are planning to buy a pair of shoes. This time, you estimate the shoe value to be
$800. However, when you arrive at the store, the shopkeeper informs you that the shoes' true price is $1000, which is
higher than your estimate. Indicating that you had underestimated their value by $200. In this situation,
Underestimation has occurred.
800 < 1000
i.e. h(n) ≤ h*(n) ∴ Underestimation
Case 1: Overestimation H(A)= 60, Estimated values i.e. h(n)] H(B)= 50
So, using A* equation, f(n) = G(n) + h(n) by putting values
f(A) = 100 + 60 = 160
f(B) = 100 + 50 = 150
by comparing f(A) & f(B), f(A) > f(B) so choose path of B node and apply A* equation
again
f(Y) = g(Y) + h(Y) [here h(Y) is 0, Goal state]
= 140 + 0 [g(Y)=100+40=140 this is actual cost i.e. h*(B)]
= 140
Case 2: Underestimation H(A) = 20 [This are estimated values i.e. h(n)] H(B) = 10
So, using A* equation, f(n) = G(n) + h(n) by putting values
f(A) = 100 + 20 = 120
f(B) = 100 + 10 = 110, by comparing f(A) & f(B), f(A) > f(B), so choose path of B node
and apply A* equation again
f(Y) = g(Y) + h(Y) [here h(Y) is 0, because it is goal state]
= 140 + 0 [g(Y) = 100 + 40 = 140 this is actual cost i.e. h*(B)]
= 140
f(Y) = g(Y) + h(Y)
= 130 + 0 = 130
AO* ALGORITHM - WORKING PRINCIPLES
The AO* algorithm works by utilizing a tree structure where each node represents a state in the problem space. The
key components of the algorithm are:
Node Types
• AND Nodes: Represent states where all child nodes must be satisfied to achieve a goal. If a task requires multiple
conditions to be met, it would be represented as an AND node.
• OR Nodes: Represent states where at least one child node must be satisfied to achieve a goal. This type is useful
in scenarios where multiple paths can lead to a solution.
Heuristic Function
The algorithm employs a heuristic function, similar to A*, to estimate the cost to reach the goal from any given node.
This function helps in determining the most promising paths to explore. The heuristic function h(n) estimates the cost
to reach the goal from node n: h(n)=estimated cost to reach the goal from node
• For OR Nodes: The algorithm considers the lowest
cost among the child nodes. The cost for an OR
node can be expressed as: C(n)=min{C(c1​),C(c2​),…,C(ck​)}
• For AND Nodes: The algorithm computes the cost of all
child nodes and selects the maximum cost, as all
conditions must be met. The cost for an AND node can
be expressed as: C(n)=max{C(c1​),C(c2​),…,C(ck​)}
Total Estimated Cost: f(n)=C(n)+h(n)
• C(n) is the actual cost to reach node n from the start node.
• h(n) is the estimated cost from node n to the goal.
AO* ALGORITHM
1. Initialise the graph to start node
2. Traverse the graph following the current path
accumulating nodes that have not yet been expanded
or solved
3. Pick any of these nodes and expand it and if it has
no successors call this value FUTILITY otherwise
calculate only f' for each of the successors.
4. If f' is 0 then mark the node as SOLVED
5. Change the value of f' for the newly created node to
reflect its successors by back propagation.
6. Wherever possible use the most promising routes
and if a node is marked as SOLVED then mark the
parent node
as SOLVED.
7. If starting node is SOLVED or value greater than
FUTILITY, stop, else repeat from 2.
 The Min-Max algorithm involves several key steps, executed
MIN-MAX ALGORITHM recursively until the optimal move is determined. Here is a
21-11-2025
step-by-step breakdown:
Min-Max algorithm is a decision-making algorithm Step 1: Generate the Game Tree
used in artificial intelligence, particularly in game • Objective: Create a tree structure representing all possible
theory and computer games. It is designed to minimize moves from the current game state. • Details: Each node
the possible loss in a worst-case scenario (hence represents a game state, and each edge represents a possible
"min") and maximize the potential gain (therefore move. Step 2: Evaluate Terminal States
"max"). • Objective: Assign utility values to the terminal nodes of the
Working of Min-Max Process in AI game tree.
Min-Max algorithm involves two players: the maximizer • Details: These values represent the outcome of the game
and the minimizer, each aiming to optimize their own (win, lose, or draw).
outcomes. Step 3: Propagate Utility Values Upwards
Players Involved Maximizing Player (Max): • Objective: Starting from the terminal nodes, propagate the
• Aims to maximize their score or utility value. utility values upwards through the tree.
• Chooses the move that leads to the highest possible • Details: For each non-terminal node:
utility value, assuming the opponent will play optimally. • If it's the maximizing player's turn, select the maximum value
Minimizing Player (Min): from the child nodes.
• Aims to minimize the maximizer's score or utility • If it's the minimizing player's turn, select the minimum value
value. from the child nodes.
• Selects the move that results in the lowest possible Step 4: Select Optimal Move
utility value for the maximizer, assuming the opponent • Objective: At the root of the game tree, the maximizing
will play optimally. player selects the move that leads to the highest utility value.
Min-Max Formula
Consider a simple game where the utility values of
The Min-Max value of a node in the game tree is
terminal states are given. To illustrate the Min-Max
calculated using the following recursive formulas:
calculations:
1. Maximizing Player's Turn:
1. Start from the terminal states and calculate the
𝑀𝑎𝑥(𝑠) = 𝑚𝑎𝑥𝑎∈𝐴(𝑠)𝑀𝑎𝑥(𝑅𝑒𝑠𝑢𝑙𝑡(𝑠, 𝑎)) Here:
utility values.
• 𝑀𝑎𝑥(𝑠)is the maximum value the maximizing player can
2. Propagate these values up the tree using the Min-
achieve from state 𝑠.
Max formulas.
• 𝐴(𝑠) is the set of all possible actions from state 𝑠.
For example, if the terminal states have utility values
• 𝑅𝑒𝑠𝑢𝑙𝑡(𝑠, 𝑎) is the resulting state from taking action aa in
𝑈1, 𝑈2, … , 𝑈𝑛 then:
state 𝑠.
• For the maximizing player's node: 𝑀𝑎𝑥(𝑠) = max(𝑈1,
• 𝑀𝑖𝑛(𝑅𝑒𝑠𝑢𝑙𝑡(𝑠, 𝑎)) is the value for the minimizing player
𝑈2, … , 𝑈𝑛)
from the resulting state.
• For the minimizing player's node: 𝑀𝑖𝑛(𝑠) = min(𝑈1,
Minimizing Player's Turn:
𝑈2, … , 𝑈𝑛)
𝑀𝑖𝑛(𝑠) = 𝑚𝑖𝑛𝑎∈𝐴(𝑠)𝑀𝑎𝑥(𝑅𝑒𝑠𝑢𝑙𝑡(𝑠, 𝑎)) Here:
• 𝑀𝑖𝑛(𝑠) is the minimum value the minimizing player can
achieve from state 𝑠.
• The other terms are similar to those defined above.
Terminal States
For terminal states, the utility value is directly assigned:
𝑈𝑡𝑖𝑙𝑖𝑡𝑦 𝑠 = 1 𝑖𝑓 𝑡ℎ𝑒 𝑚𝑎𝑥𝑖𝑚𝑖𝑧𝑖𝑛𝑔 𝑝𝑙𝑎𝑦𝑒𝑟 𝑤𝑖𝑛𝑠 𝑓𝑟𝑜𝑚
𝑠𝑡𝑎𝑡𝑒 𝑠 0 𝑖𝑓 𝑡ℎ𝑒 𝑔𝑎𝑚𝑒 𝑖𝑠 𝑑𝑟𝑎𝑤 𝑓𝑟𝑜𝑚 𝑠𝑡𝑎𝑡𝑒 𝑠 -
1𝑖𝑓 𝑡ℎ𝑒 𝑚𝑖𝑛𝑖𝑚𝑖𝑧𝑖𝑛𝑔 𝑝𝑙𝑎𝑦𝑒𝑟 𝑤𝑖𝑛𝑠 𝑓𝑟𝑜𝑚 𝑠𝑡𝑎𝑡𝑒 𝑠
ALPHA BETA PRUNING
Thank You