CHAPTER 1 : INTRODUCTION

Intelligence : Intelligence refers to the capability of a machine to perform tasks

that typically require human intelligencewhich includes activities like learning
from experience, understanding natural language, recognizing patterns,
problem-solving, reasoning, and decision-making.

Artificial Intelligence : Artificial intelligence (AI) is technology that enables

computers and machines to simulate human learning, comprehension,
problem solving, decision making, creativity and autonomy.

Applications of AI :

Virtual Assistants: AI powers virtual assistants like Siri and Alexa to understand
and respond to voice commands.
Recommendation Systems: AI algorithms suggest products or content based
on user preferences and behavior, as seen on Netflix or Amazon.
Image Recognition: AI identifies and categorizes objects in images, used in
applications like facial recognition and medical imaging.
Fraud Detection: AI detects unusual patterns in financial transactions to
identify potential fraud.
Autonomous Vehicles: AI enables self-driving cars to navigate and make
decisions in real time.
Chatbots: AI-driven chatbots handle customer service inquiries and provide
instant responses.
 CHAPTER 2 : AGENTS

Agent : Agent is an entity that perceives its environment through sensors and
acts upon that environment through actuators.

Agent Examples:

Agents entities :
Environment: The part of the universe that is relevant for designing and
evaluating the agent’s actions.
Percept: The content sensed by the agent’s sensors at a specific time.
Percept Sequence: The complete history of all percepts an agent has
experienced.
Agent Function (f): A mapping from a percept sequence to an action that
determines the agent’s behavior.
Agent Program: The implementation of the agent function that executes the
mapping from percept sequences to actions.

Rationality:
Rationality in the context of artificial intelligence refers to the quality of an
agent that enables it to make decisions and take actions that maximize its
performance, given the knowledge it has about the environment.
Rational agent: take actions that are expected to maximize performance
measure
Performance Measure: In the context of rationality in artificial intelligence, a
performance measure is a quantitative criterion used to evaluate how well an
agent is performing its tasks or achieving its goals. It provides a standard by
which an agent’s actions and decisions can be assessed in terms of their
effectiveness and efficiency.
• Rationality at any given time depends on
• Performance measure (the criterion of success)
• Agent’s prior knowledge of the environment
• Available actions
• Percept sequence

Rationality ≠ Omniscience:
Rationality does not mean that an agent knows everything or can predict the
future. Instead, a rational agent makes the best possible decision based on the
information it has at the time. Omniscience would imply perfect knowledge
and foresight, which is unrealistic for any agent in a complex environment.
Do not expect the agent to always take the best action in hindsight:
Rationality doesn't require that the agent’s actions are always optimal after the
fact. An agent can make a rational decision given the information available at
the moment, but later, it may turn out that another action would have been
better due to unforeseen circumstances. Rational agents make decisions based
on what is reasonable, not perfect, at the time of action.
Nature of Environments:
The PEAS (Performance measure, Environment, Actuators, Sensors) description
for a self-driving car task environment would be:
 Performance Measure: Safety (minimizing accidents and injuries),
efficiency (optimizing route and fuel consumption), comfort (smooth ride
and minimal passenger discomfort), and adherence to traffic laws.
 Environment: The road network, traffic signals, other vehicles,
pedestrians, road conditions, and weather conditions.
 Actuators: Steering wheel, brakes, accelerator, indicators, and possibly
other control mechanisms like horn and windshield wipers.
 Sensors: Cameras, LIDAR, radar, GPS, ultrasonic sensors, and possibly
other sensors like temperature and humidity sensors.

Properties of Task Environments:

Task environments vary along several significant dimensions:
1. Fully or Partially Observable:
o Fully Observable: The agent has access to complete information
about the environment at any given time.
o Partially Observable: The agent has incomplete information about
the environment and must make decisions based on partial data.
2. Single-Agent or Multi-Agent:
o Single-Agent: The environment is designed for interaction with
one agent.
o Multi-Agent: Multiple agents interact within the environment,
which may include cooperation, competition, or both.
3. Deterministic or Nondeterministic:
o Deterministic: The environment’s state is completely predictable
from the agent's actions; there is no randomness.
o Nondeterministic: The environment includes elements of chance
or uncertainty, making outcomes less predictable.
4. Episodic or Sequential:
o Episodic: The agent’s experience is divided into discrete episodes,
where each action’s outcome does not depend on previous
actions.
o Sequential: The agent’s actions are interconnected, and each
action affects future states and decisions.
5. Static or Dynamic:
o Static: The environment remains unchanged while the agent is
deliberating.
o Dynamic: The environment can change while the agent is making
decisions or taking actions.
6. Discrete or Continuous:
o Discrete: The environment’s state and actions are distinct and
countable (e.g., a board game with a limited number of moves).
o Continuous: The environment’s state and actions are fluid and can
take on a range of values (e.g., driving a car with continuous speed
adjustments).
7. Known or Unknown:
o Known: The agent has complete knowledge about the
environment’s dynamics and the consequences of its actions.
o Unknown: The agent has incomplete knowledge about the
environment, requiring exploration and learning to understand it.
Structure of Agents :
Agent Program: The implementation of the agent function. It processes the
percept sequence (input) and determines the appropriate action (output).
Agent Architecture: The physical components and setup that execute the agent
program. It includes:
 Sensors: Devices that collect data from the environment (e.g., cameras,
microphones).
 Actuators: Components that perform actions based on the agent
program's output (e.g., motors, speakers).
 Computing Device: The hardware that runs the agent program (e.g.,
computer, microcontroller).
• Agent = Program + Architecture
Agent: The combination of the agent program and the agent architecture.

Agent Program :
1) Table-Driven Agent :

A Table-Driven Agent is a type of intelligent agent that operates based

on a predefined table or lookup table that maps percept sequences to
actions. This approach is one of the simplest forms of implementing an
agent's decision-making process.

Keeps track of percept sequence: The agent continuously records the

sequence of percepts (inputs) it receives from the environment.

Maintains a mapping between percept sequence and action in a table:

The agent has a predefined table where each percept sequence is
mapped to a specific action. This table contains all possible percept
sequences the agent could encounter and their corresponding actions.

Looks up in the table to find the action: Whenever the agent receives a
new percept, it checks the percept sequence and looks up the
corresponding action in the table.

Not practical—Table can get very large: As the environment or the

number of percept sequences increases, the size of the table grows
 exponentially, making it inefficient and impractical for real-world
applications.

How It Works

1. Predefined Table: The agent uses a table, known as the action table,
which contains a comprehensive mapping from percept sequences to
actions. Each entry in the table corresponds to a particular sequence of
percepts and specifies the appropriate action for that sequence.

2. Percept Sequence: When the agent perceives the environment, it

collects data using its sensors, which forms a percept. This percept is
either an immediate snapshot or a history of percepts.

3. Lookup Process: The agent looks up the current percept sequence in the
action table. The table contains predefined responses for all possible
percept sequences that the agent might encounter.

4. Action Selection: Based on the percept sequence found in the table, the
agent selects the corresponding action. This action is then executed
using the agent's actuators.

2) Reflex Agent :
A Reflex Agent acts based solely on the current percept, ignoring the history
of past percepts. It makes decisions by applying a set of condition-action
rules, often referred to as if-then rules. Here’s a breakdown of its
functioning:
 No Percept History: Unlike table-driven agents, reflex agents do not store
or rely on a sequence of percepts. They respond only to the current
situation.
 Condition-Action Rules: The agent operates by matching the current
percept with a predefined set of condition-action rules. If a condition is
met, it executes the corresponding action.
o Example: "If car ahead is too close, then brake."
 Simple and Fast: Reflex agents are typically fast and efficient because
they don't need to store or process large amounts of data (like percept
sequences).
 Works Best in Fully Observable, Predictable Environments: Reflex agents
perform well when the environment is fully observable, meaning the
agent has all the information it needs from the current percept to make
a decision.
Example:
In a simple vacuum cleaner agent:
 Percept: Dirty floor.
 Rule: "If dirty, then suck."
 Action: The vacuum cleans the dirt whenever it detects it, but it won't
store information about whether it cleaned a particular spot in the past.

3) Model-Based Agent:
A Model-Based Agent is an intelligent agent that maintains an internal state
to track aspects of the environment that are not directly observable at any
given moment. This internal state is updated based on a model of how the
world evolves and how the agent's actions affect the environment. The
agent uses this model to handle partially observable environments more
effectively than reflex agents.
Key Components of a Model-Based Agent:
1. Internal State:
o The agent keeps an internal record of the state of the environment
that it cannot directly observe. This helps the agent maintain
 useful information about the world over time, allowing it to make
decisions even with incomplete data.
2. Transition Model:
o This is a model of how the environment changes over time,
particularly as a result of the agent’s actions. It defines the
relationship between the current state of the environment and the
likely next state.
o Example: The agent knows that if it drives a certain speed for a
given amount of time, it will cover a specific distance. This helps it
predict future states based on current and past information.
3. Sensor Model:
o The sensor model defines how the agent’s perceptions (percepts)
relate to the state of the world. It provides an understanding of
how the environment reflects into the agent's sensors.
o Example: If it perceives darkness and headlights are on, the agent
infers that the sun has set, even if it hasn't directly observed the
sunset.
Example:
Consider a self-driving car (model-based agent):
 Internal State: The car keeps track of road conditions, its location, and
nearby traffic.
 Transition Model: If the car accelerates, it knows how its speed will
change the distance covered over time.
 Sensor Model: Based on sensory inputs like lighting and traffic signals,
the car can infer environmental conditions such as night or day, even if it
can't directly see the sun.
4) Goal-Based Agent:

A Goal-Based Agent selects its actions based on a desired outcome, or

goal, rather than just responding to the current state of the
environment. Unlike reflex or model-based agents, which act based on
immediate percepts or internal models, goal-based agents plan and
execute actions with the aim of achieving a specified goal.

Key Concepts: Goal-Based Agents

•Need for Goals: When multiple actions seem rational but lead to
different outcomes, a goal helps guide the agent's decision-making.

Example: A self-driving car needs to know its destination to choose the

right turn at an intersection.

•Goal-Based Action Selection: The agent selects actions based on what

moves it closer to its goal, not through predefined percept-action
mappings.

Example: A self-driving car chooses turns based on its destination.

•Methods:
 oEpisodic tasks: Simple, isolated tasks with no long-term effects.

oSearch: Finding a sequence of actions to reach the goal.

oPlanning: Deciding steps to achieve the goal with forward-looking

strategies.

•Flexibility: Goal-based agents can adapt to new tasks by changing their

goals without structural changes.

Example: A robot assigned a new task adjusts its actions to achieve the
new goal.

5) Utility-Based Agents :

Utility in the context of artificial intelligence and decision-making refers

to a measure of the satisfaction or value that an agent derives from
being in a particular state or achieving a certain outcome.

Utility-Based Agents:

•Goals can be achieved in different ways: Utility-based agents aim to

select the best course of action from a range of options.
 •Maximizing performance: Utility-based agents seek to maximize their
overall performance by considering not just goal achievement, but also
the quality of outcomes.

•Utility Function: The agent uses a utility function to quantify how

"good" a particular state is, which is an internal measure aligned with
the performance objective.

•Distinguishes between states: Utility allows the agent to rank different

states and choose the one with the highest utility.

•Evaluating tradeoffs: Utility-based agents can make decisions by

considering tradeoffs between different goals and outcomes.

•Factoring in probabilities: When faced with multiple goals, the agent

weighs the likelihood of success against the importance of achieving
each goal.

6) Learning Agents:
Concept: Learning agents are designed to improve their performance over
time by learning from their experiences rather than relying solely on pre-
programmed instructions. This approach, inspired by Turing's vision in 1950,
is particularly useful in environments that are complex or unknown.
Components:
 Performance Element: Initially, this is the core component that selects
actions based on the current state of the environment. It represents the
agent's behavior and decision-making process.
 Learning Element: This component enhances the agent's ability by
incorporating feedback from a critic. It uses this feedback to refine and
improve the performance element, enabling the agent to adapt and
perform better over time.
 Critic: Provides feedback on the agent’s actions and overall performance.
The critic evaluates how well the performance element is achieving its
goals and identifies areas for improvement.
 Problem Generator: Proposes new actions or strategies for exploration.
While some of these suggestions may be sub-optimal in the short term,
they help the agent explore new possibilities and discover more effective
strategies in the long run.
Short-Term Sub-Optimality: The problem generator might suggest actions
that are not immediately optimal but are intended to explore and learn
about the environment.
Agent Representations:
1. Atomic:
o Description: Represents the state as an indivisible entity or "black
box" with no internal structure.
o Characteristics: Simple and minimal, but lacks detailed internal
representation.
o Example: A basic sensor that outputs a single value, like whether a
room is occupied or not.
2. Factored:
o Description: Represents the state as a vector of values, where
each value corresponds to a particular attribute or feature of the
state.
o Characteristics: More detailed than atomic representation; allows
for the decomposition of the state into multiple factors or
dimensions.
o Example: A robot's state might be represented by a vector
containing its position coordinates, battery level, and orientation.
3. Structured:
o Description: Represents the state with objects that can interact
with one another. It captures complex relationships and
interactions within the state.
o Characteristics: Most complex and expressive, allowing detailed
representation of states and their components.
o Example: A smart home system where the state includes various
objects like lights, thermostats, and doors, and their interactions
(e.g., lights turning on when the door is opened).
 CHAPTER 3 SEARCH
Problem-Solving Agents:
A problem-solving agent aims to find a sequence of actions that lead to a
desired goal state. Here’s how it operates:
1. Goal Formulation:
o Description: Defines what the agent is trying to achieve, which
helps narrow down the available actions. It sets clear objectives
for the agent to work towards.
o Effect: Limits the action choices by focusing only on those that
contribute to achieving the goal.
2. Problem Formulation:
o Description: Provides a detailed description of the states, actions,
and transitions needed to reach the goal. It outlines the problem
space and how to navigate it.
o Effect: Sets up a structured approach for the agent to understand
and address the problem.
3. Search:
o Description: The agent explores various sequences of actions in its
model to find a viable path to the goal. It simulates different
scenarios and evaluates their outcomes.
o Effect: Produces a solution by identifying a sequence of actions
that successfully lead to the goal.
4. Execution:
o Open Loop System: In fully observable, deterministic, and known
environments, the agent can execute actions based on its plan
without needing to continuously monitor the environment. The
execution follows a predetermined sequence.
 Example: A robotic arm performing a repetitive
manufacturing task.
o Closed Loop System: In partially observable or nondeterministic
environments, the agent must continuously monitor its percepts
and adjust its actions accordingly. This allows the agent to handle
unexpected changes and uncertainties in the environment.
  Example: A self-driving car adjusting its route in response to
real-time traffic conditions.

Defining a Search Problem:

1. State Space:
o Description: A collection of all possible states that the
environment can be in. This defines the entire set of conditions or
configurations the agent may encounter.
o Example: For a navigation problem, the state space includes all
cities and possible locations.
2. Initial State:
o Description: The starting point from which the agent begins its
journey. This is the specific state where the agent starts its search.
o Example: The initial state might be "Arad" in a travel problem.
3. Goal States:
o Description: One or more states that represent the objectives or
desired end conditions the agent aims to achieve.
o Example: In a travel problem, the goal states could be "Bucharest"
or any other destination.
4. Actions:
o Description: The set of possible actions available to the agent
from a given state. For each state sss, the function ACTIONS(s)
returns a set of actions that can be executed.
o Example: For the state "Arad", the actions might be {ToSibiu,
ToTimisoara, ToZerind}.
5. Transition Model:
o Description: Defines what happens when an action is executed in
a given state. It describes how the state changes in response to an
action.
o Function: RESULT(s, a) returns the new state that results from
performing action a in state s.
 o Example: If the agent is in "Arad" and takes the action "ToSibiu",
the transition model might result in moving to the state "Sibiu".

Action Cost Function:

An action cost function, denoted by ACTION-COST(s, a, s′) that gives the
numeric cost of applying action a in state s to reach state s′.
Purpose: The cost function should reflect the performance measure of the
agent. It helps in evaluating and comparing different paths or sequences of
actions based on their cost.
Example:
 Route-Finding Agents: In problems like route navigation, the cost of an
action could be:
o Distance: The length in miles or kilometers.
o Time: The duration it takes to travel between two points.
Path and Solution:
 Path: A sequence of actions that leads from the initial state to the goal
state. Each action in the sequence has an associated cost.
 Solution: A specific path from the initial state to a goal state.
Optimal Solution:
 Definition: The path with the lowest total cost among all possible paths
from the initial state to a goal state.
 Objective: The goal is to find this optimal solution to minimize the total
cost and achieve the best performance according to the cost function.

State-Space Graph :
The state space can be represented as a graph in which the vertices are states
and the directed edges between them are actions.
Search Algorithms :
• A search algorithm takes a search problem as input and returns a solution or
indicates failure
Search Tree:
 Concept: A search tree is a conceptual structure used to represent the
paths an agent explores while attempting to solve a problem. Each node
in the tree represents a state, and the branches represent actions
leading to new states.
• Node corresponds to a state in the state space
• Edge corresponds to an action
• The root of the tree corresponds to the initial state
• Search tree describes paths between states leading to the goal
• A state may appear multiple times in the search tree

Frontier:
 Definition: The frontier (green in diagrams) is the boundary separating
the explored (interior) part of the search tree from the unexplored
(exterior) part. It consists of nodes that have been generated but not yet
expanded.
 Expansion: A search algorithm chooses which frontier node to expand
next, meaning it explores the possible actions that can be taken from
that state.
Search Algorithm:
 Task: The algorithm determines the order in which frontier nodes are
expanded. Different algorithms prioritize nodes differently (e.g., depth-
first, breadth-first).
 Goal: The search continues until a goal state is reached, expanding
frontier nodes step by step.
Search Tree vs. State-Space Graph:
 Search Tree: Represents various paths from the initial state toward the
goal, as the agent explores possible actions.
 State-Space Graph: The underlying structure showing all possible states
and actions in the environment.
 Relationship: The search tree is superimposed over the state-space
graph, tracing out paths from the initial state in an attempt to find the
goal.

Best-First Search :
Evaluation Function f(n):
 Definition: Each node n is assigned an evaluation function f(n), which
determines the desirability of expanding that node.
  Function: The value of f(n) can change over time depending on the
specific search algorithm being used.
Different Algorithms:
 The choice of f(n) results in different search algorithms. For example:
o Greedy Best-First Search: f(n)=h(n) ,where h(n) is the heuristic
estimating the cost to reach the goal.
o A Search*: f(n)=g(n)+h(n), where g(n) is the cost to reach node n,
and h(n) is the estimated cost to the goal.
Selecting Nodes:
 Out of all the nodes in the frontier, the algorithm selects the node with
the smallest f(n), as it is considered the most promising for reaching the
goal.
Multiple Frontier Additions:
 A node may be added to the frontier multiple times if the agent
discovers a lower-cost path to that node. This ensures that the agent
always follows the most efficient route.

Search Data Structure :

1. Node Structure:
o node.STATE: The state the node represents.
o node.PARENT: The node that generated this current node (its
parent).
 o node.ACTION: The action applied to the parent’s state to create
this node.
o node.PATH-COST: The total cost of the path from the initial state to
this node. Also referred to as g(node)g(node)g(node).
Why Important?:
o The node structure helps trace back from the goal node to the
initial state by following the PARENT pointers. This process allows
the reconstruction of the solution (the sequence of states and
actions taken).

2. Frontier:
o Definition: The frontier is a queue that stores nodes yet to be
explored.
Operations on Frontier:
o IS-EMPTY(frontier): Returns true if the frontier has no nodes.
o POP(frontier): Removes and returns the top node from the
frontier.
o TOP(frontier): Returns the top node without removing it.
o ADD(node, frontier): Inserts the node in its proper place in the
frontier (depending on the search algorithm).

3. Types of Queues:
o Priority Queue: Pops the node with the minimum cost.
 Usage: Best-First Search and A* Search.
o FIFO (First-In-First-Out) Queue: Pops the node that was added to
the queue the earliest.
 Usage: Breadth-First Search (BFS).
o LIFO (Last-In-First-Out) Queue or Stack: Pops the most recently
added node.
 Usage: Depth-First Search (DFS).
Performance Metrics for Search Algorithms:
1. Completeness:
o Definition: Determines if the algorithm always finds a solution
when one exists. It also evaluates whether the algorithm correctly
reports failure when no solution exists.
2. Cost Optimality:
o Definition: Measures whether the algorithm finds the solution
with the lowest possible cost (optimal solution).
3. Time Complexity:
o Definition: Refers to the time required by the algorithm to find a
solution, which is typically based on the number of states and
actions considered during the search process.
4. Space Complexity:
o Definition: Refers to the amount of memory or storage the
algorithm needs to perform the search, particularly for managing
nodes, frontiers, and paths.

Breadth-First Search (BFS):

1. Evaluation Function:
o f(n) = depth of node n.
o BFS explores nodes level by level, expanding nodes at the current
depth before moving to the next depth.
2. Properties:
o Completeness: BFS is complete, meaning it will always find a
solution if one exists.
o Optimality: BFS is not optimal if costs vary between actions. It
only guarantees an optimal solution if all actions have the same
cost.
3. Complexity:
o Time Complexity: O(b^d), where:
  B is the branching factor (the number of child nodes each
node has).
 d is the depth of the shallowest goal node.
o Space Complexity: O(b^d) , meaning BFS requires storing all the
nodes in memory at each level.
 This is problematic because it requires significant memory.
For example, at a depth of 10 and a branching factor of 10,
it would require approximately 10 TB of memory (assuming
each node takes 1 KB).
4. Memory Issue:
o All nodes in the search tree must be stored in memory, making BFS
inefficient in terms of space for deeper or broader trees.

Dijkstra’s Algorithm (Uniform-Cost Search):

Overview:
 Uniform-cost search is a variant of BFS where nodes are expanded based
on their path cost rather than their depth.
 The node with the least cost is expanded first.
Properties:
 Complete: Dijkstra’s algorithm guarantees finding a solution if one exists.
 Optimal: It finds the solution with the lowest path cost, making it an
optimal search algorithm.
Time and Space Complexity:
Complexity : O(b 1 + └C*/ε┘)
where:
 b is the branching factor.
  C∗ is the cost of the optimal solution.
 ϵ\epsilonϵ is the minimum action cost.
This means it can sometimes be worse than BFS in terms of time and space
complexity, especially if the costs are uniform or nearly uniform.
When It’s Less Efficient:
 Dijkstra’s algorithm can perform worse than BFS if most paths have
similar or equal costs because it spends more time expanding nodes
based on cost, which may add unnecessary overhead.

Depth-First Search (DFS):

1. Evaluation Function:
o f(n) = − (depth of node n).
o DFS explores as far down a branch as possible before backtracking
and exploring the next branch.
2. Properties:
o Completeness:
 DFS is complete if the state space is a tree or Directed
Acyclic Graph (DAG), meaning it will find a solution if one
exists.
  DFS is incomplete in cyclic graphs or infinite-depth spaces,
as it may get stuck in loops.
o Optimality: DFS is not optimal, as it does not guarantee the
lowest-cost or shortest solution.
3. Memory Requirement:
o DFS has a small memory footprint. It only needs to store a single
path from the root to the leaf node, along with the unexplored
sibling nodes.
o The space complexity is O(bm), where:
 b is the branching factor.
 m is the maximum depth of the tree.
4. Time Complexity:
o Time complexity is also O(bm), where b is the branching factor
and m is the maximum depth. DFS explores all possible paths to
the maximum depth.
Improvements to Depth-First Search (DFS):
1. Depth-Limited Search:
o Concept: DFS is performed but with a maximum depth limit set.
o Example: For the Romania map navigation problem, set depth =
19.
o Properties:
 Completeness: Not complete, as it may miss solutions if
they are deeper than the limit.
 Optimality: Not optimal, since it does not guarantee the
lowest-cost solution.
2. Iterative Deepening Search:
o Concept: Performs a series of depth-limited searches, increasing
the depth limit progressively (0, 1, 2, 3, …).
o Efficiency: Most nodes in large trees are at the bottom level, and
this method efficiently finds solutions without unnecessary
memory usage.
o Combination of BFS and DFS:
 It has the memory requirements of DFS O(bd) and gradually
explores deeper levels like BFS.
o Properties:
 Completeness: Iterative deepening is complete, meaning it
will find a solution if one exists.
 Optimality: It is not optimal in general, but it is optimal if
all action costs are the same.
Bidirectional Search:
1. Concept:
o Bidirectional search runs two simultaneous searches: one from
the initial state (forward search) and one from the goal state
(backward search).
o The goal is for these two searches to meet in the middle,
significantly reducing the search space.
2. How It Works:
o The forward search explores from the start state, and the
backward search explores from the goal state.
o The algorithm terminates when the two searches intersect, i.e., a
node is found that both searches have in common.
o Once the searches meet, the solution path is reconstructed by
combining the paths from both directions.
3. Advantages:
 o Time Efficiency: Bidirectional search is faster than unidirectional
search. Instead of exploring the entire search tree (with time
complexity O(b^d), where b is the branching factor and d is the
depth), each search only explores up to half the depth, resulting in
a time complexity of O(b^{d/2})
o Reduced Search Space: Since each search only has to go halfway,
the overall number of nodes explored is significantly reduced.
4. Properties:
o Completeness: Bidirectional search is complete if both the
forward and backward searches are complete.
o Optimality: It can be optimal if the search algorithm used in both
directions is optimal (e.g., uniform-cost or BFS).
5. Example:
o In a navigation problem where an agent needs to travel from city A
to city B, one search can begin from city A and the other from city
B. When the two searches meet, the optimal path can be traced.

Informed Search (Heuristic Search)

Informed search strategies use heuristic information to guide the search
process, making it more efficient than uninformed (blind) search methods. The
goal of informed search is to explore the most promising paths first based on
available information, leading to faster solutions.

Key Components:
1. Heuristic Function h(n):
o A heuristic function estimates the cost from the current state to
the goal.
o h(n)h(n)h(n) provides an estimate of how "close" the current node
is to the goal.
o The quality of the heuristic significantly impacts the performance
of the search.
o Example: In a route-finding problem, h(n) might represent the
straight-line distance to the goal.
 2. Evaluation Function:
o The evaluation function f(n) determines which node to expand
next.
o It combines the heuristic estimate with the actual cost of reaching
the node (for optimal algorithms).
o Two common evaluation functions are:
 f(n)=h(n) (used in greedy best-first search).
 f(n)=g(n)+h(n) , where g(n) is the cost to reach node n from
the start (used in A* search).

Greedy Best-First Search

Greedy Best-First Search is an informed search algorithm that aims to find the
path to the goal node by expanding the most promising nodes based on a
heuristic function. Unlike uninformed search methods, which explore nodes
without guidance, greedy best-first search uses heuristics to make more
informed decisions about which node to expand next.
Key Points:
 Heuristic Function h(n) : Estimates the cost from the current node to the
goal.
 Evaluation Function: f(n)=h(n) Nodes with the smallest h(n) are
expanded first.
  Algorithm:
1. Initialize with the start node.
2. Expand the node with the smallest h(n).
3. Add successors to the open list if they are more promising.
4. Continue until the goal node is found or the open list is empty.
Properties:
 Complete: Not guaranteed.
 Optimal: Not guaranteed.
 Time Complexity: O(b^m) (where b is the branching factor and m is the
maximum depth).
 Space Complexity: O(b^m).
A* Search :
A* Search is an informed search algorithm that combines the features of
uniform-cost search and greedy best-first search. It efficiently finds the shortest
path to a goal by considering both the cost to reach a node and the estimated
cost to the goal.
Key Concepts:
1. Evaluation Function f(n) :
o Definition: Combines the actual cost to reach the node and the
heuristic estimate of the cost from the node to the goal.
o Formula: f(n)=g(n)+h(n)
 g(n): Cost to reach node n from the start.
 h(n): Estimated cost from node n to the goal (heuristic).
o Purpose: Balances between the cost already incurred and the
estimated cost to find an optimal path.
2. Algorithm Steps:
1. Initialize:
 Create an open list (priority queue) containing the start node with
f(start)=h(start)f(start) = h(start)f(start)=h(start).
 Initialize an empty closed list to keep track of expanded nodes.
2. Search Process:
While the open list is not empty:
1. Remove the node with the smallest f(n) from the open list.
2. If this node is the goal, reconstruct the path and terminate.
3. Else, expand the node to generate its successors.
4. For each successor:
 Calculate g(successor) and h(successor).
 Compute f(successor)=g(successor)+h(successor).
 If the successor is not in the closed list or has a lower f value than
previously found, add/update it in the open list.
5. Add the expanded node to the closed list.
3. Properties:
o Complete: A* is guaranteed to find a solution if one exists.
o Optimal: A* is optimal if the heuristic h(n) is admissible (never
overestimates the true cost) and consistent (monotonic).
o Time Complexity: Depends on the heuristic; in general, it is
O(b^d), where b is the branching factor and d is the depth.
o Space Complexity: Also O(b^d), due to the need to store all nodes
in the open and closed lists.
4. Advantages:
o Optimality: Guarantees the shortest path if the heuristic is
admissible.
o Flexibility: The choice of heuristic can significantly impact
efficiency.
• Heuristic estimates must be optimistic or realistic
• Estimates ≤ Actual costs
• A heuristic is called admissible if it never overestimates the cost to a goal
• 0 ≤ h(n) ≤ h*(n), h*(n) : actual cost

Consistent Heuristic
Consistency is a property of heuristic functions used in search algorithms like
A*. It ensures that the heuristic does not underestimate the true cost, and it
maintains certain properties related to cost estimation.
Definition:
 Consistent Heuristic: A heuristic h is consistent if, for every node n, every
action a leading to a successor n′, and the cost c(n,a,n′) of taking action a
from n to n′, the following condition holds: h(n)≤c(n,a,n′)+h(n′)
 Key Points:
1. Triangle Inequality: The heuristic value h(n) should not be more than the
cost of reaching n′ plus the heuristic value h(n′). This ensures that taking
a path through n′ does not reduce the estimated cost to reach the goal.
2. Properties:
o Every Consistent Heuristic is Admissible: If a heuristic is
consistent, it is also admissible, meaning it never overestimates
the true cost to reach the goal.
o Not All Admissible Heuristics are Consistent: A heuristic can be
admissible but not consistent, as consistency is a stricter
condition.
3. Implications for A* Search:
o Optimal Path: With a consistent heuristic, the first time A*
reaches a node n, it will be along an optimal path.
o Node Expansion: A* will not expand any node with f(n) greater
than the optimal cost C∗ This is because consistent heuristics
ensure that the cost function f(n)=g(n)+h(n) will be tightly bound
to the true path costs.
4. Example:
o In a grid-based pathfinding problem, a consistent heuristic could
be the Manhattan distance (for a grid where movements are
restricted to horizontal and vertical directions) since it always
underestimates or exactly matches the true cost to the goal.
Weighted A* - Satisficing Search :
Weighted A* Search is a variant of the A* algorithm that adjusts the balance
between the cost to reach a node and the heuristic estimate of the cost to
reach the goal. It allows for quicker solutions at the expense of optimality.
Key Concepts:
1. Satisficing:
o Definition: The approach of finding a solution that is "good
enough" rather than the absolute optimal. It is particularly useful
when A* expands too many nodes and finding the perfect solution
is computationally expensive.
2. Weighted A* Search:
o Formula: f(n)=g(n)+W⋅h(n), where W>1.
 g(n): Cost to reach node n from the start.
 h(n): Heuristic estimate of the cost from n to the goal.
 W: Weight factor that amplifies the heuristic function.
3. Detour Index:
o Usage: Adjusts the heuristic to account for factors such as road
curvatures or obstacles. It is used to modify the straight-line
distance to more accurately reflect the true cost.
o Example: If the detour index is 1.5, it means the heuristic value
will be 1.5 times the straight-line distance, accounting for
additional road curvature.
4. Example:

In route planning with road curves, if the heuristic function is the straight-
line distance and the roads have significant detours, Weighted A* might use
a detour index to better approximate the actual travel cost. For instance,
using W=2W = 2W=2 would make the search more focused on the heuristic
but could lead to faster, though potentially suboptimal, route discovery.
Improvements to A* Search :
A* Search can be memory-intensive, storing all explored nodes. Several
improvements address this issue, making A* more efficient in terms of memory
usage.
1. Iterative Deepening A* (IDA*)
 Overview: IDA* modifies A* by using a depth-first approach with
iterative deepening.
 Key Concepts:
o Cutoff: Instead of limiting search depth, IDA* uses a cutoff based
on the f-cost (f(n)=g(n)+h(n)).
o Iteration: The search is performed with increasing f-cost limits.
Each iteration explores nodes within the current f-cost cutoff.
o Bounded Iterations: The number of iterations is bounded by the
optimal cost C∗ if the f-cost values are integers.
 Advantages:
o Memory Efficiency: Uses less memory than traditional A* as it
only stores nodes along the current search path.
o Complete: Guarantees to find a solution if one exists, similar to A*.
2. Recursive Best-First Search (RBFS)
 Overview: RBFS is a recursive approach that focuses on the best node
within a limited f-cost.
 Key Concepts:
 o f-Limit: The algorithm maintains a limit on the f-value,
representing the best alternative path found so far.
o Recursion: It performs depth-first search within the f-limit. If a
node's cost exceeds the f-limit, the recursion unwinds.
o Backtracking: If the recursion limit is exceeded, the search
backtracks to explore other paths.
 Advantages:
o Memory Efficiency: Uses less memory than A* as it avoids storing
all nodes. Only the current path and best alternative are kept in
memory.
o Completeness: RBFS is complete and will find a solution if one
exists, given that the heuristic is admissible and consistent.

Recursive Best-First Search (RBFS) :

Recursive Best-First Search (RBFS) is an improvement on the A* search
algorithm designed to reduce memory usage while maintaining completeness.
It addresses the issue of A*'s high memory consumption by using a recursive
approach to search.
Key Features:
1. Recursive Approach:
o RBFS uses recursion to explore nodes rather than storing all nodes
in memory. It recursively explores paths from the current node
while keeping track of the best path found so far.
2. f-Limit:
o The algorithm maintains a limit on the f-value (cost estimate) for
nodes. This limit represents the best cost found so far among
alternative paths.
o f(n): The cost function used is f(n)=g(n)+h(n), where g(n) is the
cost to reach node n from the start, and h(n) is the heuristic
estimate of the cost to reach the goal.
3. Handling Node Expansion:
o If a node's f-value exceeds the current limit, RBFS will backtrack
and explore other paths.
 o When a node's f-value exceeds the limit, the search unwinds,
allowing the algorithm to explore alternative nodes.
4. Backtracking:
o RBFS employs backtracking to manage nodes that exceed the f-
limit. When the search path exceeds the limit, it returns to
previous nodes and explores other potential paths.
5. Memory Efficiency:
o Memory Usage: RBFS is designed to use less memory compared to
A*, as it only stores the current path and the best alternative path
found, avoiding the need to store all explored nodes.
Advantages:
 Memory Efficiency: RBFS uses less memory than A* by not storing the
entire search tree, making it more suitable for large state spaces.
 Completeness: It is complete, meaning it will find a solution if one exists,
given an admissible and consistent heuristic.
Creating Admissible Heuristic
An admissible heuristic is one that is used in search algorithms to guide the
search towards the goal more efficiently while ensuring that the solution found
is optimal. For a heuristic to be admissible, it must meet specific criteria.
Definition of Admissibility:
 Admissibility: A heuristic h(n)h(n)h(n) is admissible if it never
overestimates the true cost to reach the goal from node nnn. In other
words, the heuristic must be optimistic.
o Formally: For all states nnn, the heuristic h(n)h(n)h(n) must satisfy:
h(n)≤h∗(n)h(n) \leq h^*(n)h(n)≤h∗(n) where h∗(n)h^*(n)h∗(n) is
the true cost to reach the goal from nnn.
Steps to Create an Admissible Heuristic:
1. Understand the Problem Domain:
o Analyze the problem to identify key aspects that the heuristic
should estimate. For example, in route planning, the heuristic
could estimate the straight-line distance between two points.
2. Design a Simple, Lower Bound Heuristic:
o Create a heuristic that estimates the minimum possible cost to
reach the goal. Ensure that this estimate is always less than or
equal to the actual cost from any state to the goal.
o Example: In a pathfinding problem on a grid, the Manhattan
distance or Euclidean distance can be used as a heuristic. These
distances never exceed the actual shortest path cost if there are
no obstacles.
3. Validate with Problem Constraints:
o Ensure that the heuristic respects the constraints and limitations
of the problem. For instance, if certain actions are restricted, the
heuristic should account for these restrictions.
4. Test for Admissibility:
o Verify that the heuristic never overestimates the true cost. This
can be done by comparing heuristic values with actual costs in
various scenarios or through theoretical analysis.
5. Refine the Heuristic:
 o If the initial heuristic is not admissible, refine it by adjusting the
estimation method. For instance, if a heuristic is too aggressive
and overestimates, simplify it to ensure it remains within bounds.
Examples of Admissible Heuristics:
 Straight-Line Distance: Often used in navigation problems, it calculates
the direct distance between two points (e.g., Euclidean distance) and is
admissible if no shortcuts or obstacles are considered.
 Manhattan Distance: Used in grid-based pathfinding problems, it
calculates the sum of the horizontal and vertical distances between two
points and is admissible if movement is restricted to grid lines.
 Number of Misplaced Tiles: In the 8-puzzle problem, a heuristic can be
the number of tiles that are out of place. This heuristic is admissible
because moving each misplaced tile to its correct position has a cost that
is always greater than or equal to the heuristic estimate.

Creating a Good Heuristic :

A good heuristic improves search efficiency by estimating the cost to reach the
goal. Here’s how to create an effective one:
1. Understand the Problem:
o Analyze: Identify key aspects and constraints of the problem.
o Identify Factors: Determine relevant factors that affect reaching
the goal.
2. Define the Heuristic Function:
o Admissibility: Ensure the heuristic never overestimates the true
cost (i.e., it’s optimistic).
o Consistency: Ideally, it should be consistent, meaning it satisfies:
h(n)≤c(n,a,n′)+h(n′) where h(n) is the heuristic value, and c(n,a,n′)
is the cost of moving from n to n′.
3. Design the Heuristic:
o Simplicity: Start with a simple, easy-to-compute heuristic.
o Lower Bound: Ensure it provides a lower bound on the actual cost
to the goal.
4. Test and Refine:
o Empirical Testing: Test the heuristic on various problem instances.
o Refinement: Adjust based on performance. Simplify if it
overestimates; enhance if it underestimates.
5. Use Domain-Specific Knowledge:
o Incorporate Features: Use specific knowledge or features of the
problem.
o Combine Heuristics: Sometimes combining multiple heuristics can
improve results.
6. Examples of Good Heuristics:
o Euclidean Distance: Straight-line distance in continuous spaces.
o Manhattan Distance: Sum of horizontal and vertical distances in
grid-based problems.
o Number of Misplaced Tiles: In puzzles, counting out-of-place tiles.
Generating Heuristics from Relaxed Problems :
Generating heuristics from relaxed problems involves creating a simpler version
of the original problem where some constraints are removed. Here’s how it
works:
1. Relaxation:
o Relaxed Problem: Simplify the original problem by removing some
constraints. This usually results in additional edges in the state-
space graph.
o Supergraph: The state-space graph of the relaxed problem is a
supergraph of the original problem’s graph, meaning it includes all
possible states of the original problem plus additional ones.
2. Admissibility:
o Lower Cost: Solutions to the relaxed problem have lower costs
compared to the original problem.
o Admissible Heuristic: The cost of the solution to the relaxed
problem serves as an admissible heuristic for the original problem,
ensuring that it never overestimates the true cost.
3. Efficiency:
o Fast Generation: The heuristic cost should be computed quickly.
 o Automation: Heuristic generation can often be automated for
efficiency.
4. Examples:
o Absolver: A system developed by Prieditis in 1993 that generated
effective heuristics for problems like the 8-Puzzle and Rubik’s
Cube, outperforming previous methods.
5. Combining Heuristics:
o Max Function: Combining multiple admissible heuristics can be
done by taking the maximum value: h(n)=max(h1(n),h2(n),…,hk(n))
o This approach can leverage the strengths of various heuristics.

Generating Heuristics from Subproblems :

Heuristics can be generated by solving subproblems of the original problem.
Here’s how it works:
1. Subproblem Solutions:
o Lower Bound: The cost of the optimal solution for a subproblem
provides a lower bound on the cost of the complete problem.
o Pattern Database: Store exact solution costs for various
subproblems. This database helps quickly retrieve the heuristic
cost for a given subproblem configuration.
2. Pattern Database:
o Examples: For puzzles like the 8-Puzzle, store the exact costs of
reaching certain patterns, such as the positions of the tiles (e.g., 1-
2-3-4).
o Accuracy: Heuristics derived from pattern databases can be more
accurate than simpler heuristics like Manhattan distance.
3. Combining Heuristics:
o Max Function: Combine heuristic costs from multiple patterns by
taking the maximum value: h(n)=max(h1(n),h2(n),…,hk(n))
 o This approach leverages the strengths of different patterns to
improve heuristic accuracy.
4. Practical Benefits:
o Speedups: Using pattern databases can lead to significant
improvements in search efficiency by providing more precise
heuristics.
 CHAPTER 4 : LOCAL SEARCH

Local search algorithms operate by searching from a start state to neighbouring

states, without keeping track of the paths, nor the set of states that have been
reached.
Objective function is a mathematical function that evaluates the quality or
"fitness" of a particular solution in the search space

Gradient Descent (Hill Climbing)

Gradient Descent is an optimization algorithm used to minimize (or maximize)
an objective function by iteratively moving towards the function's minimum (or
maximum) based on the gradient of the function.
It is not a systematic search
We go to one of immediate neighbouring states from a given state.

Objective Function: The function to be minimized (or maximized). In machine

learning, this is often a cost function (e.g., mean squared error, cross-entropy
loss).
Gradient: The gradient of a function points in the direction of the steepest
increase. The negative gradient points in the direction of the steepest
decrease, which is used to minimize the function.
Learning Rate (α): This is a hyperparameter that controls the step size at each
iteration while moving towards the minimum. A small learning rate makes
convergence slow but stable, while a large one may cause the algorithm to
overshoot the minimum.
4 Queens Problem using Gradient Descent
The 4-Queens Problem involves placing 4 queens on a 4x4 chessboard such
that no two queens threaten each other (i.e., no two queens share the same
row, column, or diagonal). Gradient Descent is traditionally used for continuous
optimization problems, but it can be adapted to solve this discrete problem by
minimizing a custom objective function. Here's how it can be approached:
Problem Representation:
 State Representation: Each queen is placed in a unique row, and the
position of a queen is represented by the column it occupies. This
reduces the problem space. The state can be represented as a vector of
size 4, where the iii-th element of the vector represents the column
position of the queen in the iii-th row. State=[q1,q2,q3,q4]\text{State} =
[q_1, q_2, q_3, q_4]State=[q1,q2,q3,q4] where qiq_iqi is the column
position of the queen in the iii-th row.
Objective Function:
 The objective function will measure the number of pairs of queens that
are attacking each other (on the same row, column, or diagonal). The
goal is to minimize this number.
Objective: Count the number of attacking pairs of queens:
o Queens on the same column.
o Queens on the same diagonal (absolute difference between the
row and column of any two queens is the same).
Gradient Descent Adaptation:
Since gradient descent is typically for continuous variables and the 4-Queens
Problem has discrete variables, we can adapt the approach using Hill Climbing,
a discrete analogue of gradient descent:
1. Initial State: Randomly place the queens in the 4 rows. Example:
State=[1,3,0,2].
2. Neighbouring States: For each queen, generate neighbours by moving it
to a different column in the same row. For instance, if queen 1 is in
column 1, neighbouring states could be generated by moving it to
columns 2, 3, or 4.
3. Cost Function: For each neighbouring state, calculate the objective
function (the number of attacking pairs).
4. Update: Move to the neighbouring state that reduces the number of
attacking pairs (i.e., minimizes the objective function). If no neighbouring
state reduces the cost, the algorithm may terminate.
5. Convergence: The algorithm stops when the objective function reaches 0
(no attacking pairs), meaning all queens are placed such that none are
attacking each other.

Problems with Gradient Descent: --

 Local Maxima: A local maximum is a peak that is higher than each of

its neighbouring states but lower than the global maximum.
 Ridges: Ridges result in a sequence of local maxima that is very
difficult for greedy algorithms to navigate
 Plateaus: A plateau is a flat area of the state-space landscape. It can
be a flat local Plateau maximum, from which no uphill exit exists, or a
shoulder, from which progress is Shoulder possible.

Problems with Gradient Descent in 8 Queens problem: --

It can get stuck
There are 8 8 moves possible.
In 8 Queens  86% times it gets stuck.
 When it succeeds it takes on an average 4 moves.
Fixes for 8 Queens problem in Gradient descent: --
 Allows sideways moves
Improves success rate to 94%
Cost is average number of moves increases up to 21.
 Stochastic Gradient Descent or Stochastic Search
 Random start conditions
Among all possible improved moves, select a random move.
 First choice hill climbing
Generate random successors and choose the first one that
improves the objective function.
 Random Restart
Generate random initial states and proceed.

AND – OR SEARCH TREES

AND-OR search trees are a type of search tree used to solve problems
where some subproblems require a combination of conditions (AND) to be
satisfied, while others require a choice between alternatives (OR). These
trees are commonly used in AI and decision-making problems like game
theory, planning, and constraint satisfaction, where decisions depend on
both deterministic and non-deterministic outcomes.
Structure of AND-OR Search Trees:
1. OR Nodes:
o Represent decision points where the system can choose among
different possible actions or outcomes.
o The goal at an OR node is to find one child (subproblem) that leads
to a solution, i.e., satisfying one child is enough.
o Typically used when multiple possible actions are available, and
we need to choose the best one.
2. AND Nodes:
o Represent situations where all subproblems must be solved for the
current problem to be considered solved.
o The goal at an AND node is to solve all children, i.e., all
subproblems must be satisfied simultaneously.
AND – OR Search Trees in Vacuum World
TREE STRUCTURE
 AND Nodes: These represent states where multiple conditions must
be met simultaneously. For example, if the goal is to clean all dirty
squares, an AND node might represent the condition that every
dirty square must be cleaned.
 OR Nodes: These represent choices between different possible
actions or states. For example, from a given state, you might have
 the option to move the vacuum in different directions (up, down,
left, right), and each option is represented by an OR node.

TREE CONSTRUCTION

 Root Node: Represents the initial state of the world (e.g., the
vacuum's starting position and the initial state of the dirt).
 Children of the Root Node: Each child represents a possible action
the vacuum can take (e.g., move up, move down, or clean the
current position).

SEARCH STRATEGY

 Subsequent Levels: Each action leads to a new state, which might

have its own set of actions, continuing this process until the goal
state is reached.
 Depth-First Search: Can be used to explore each possible sequence
of actions in detail. This might involve a lot of backtracking if the
state space is large.
 Breadth-First Search: Explores all possible actions at each level
before moving to the next level, which can be useful for finding the
shortest sequence of actions.
 Heuristic Search: Using heuristics (like the number of dirty squares
remaining) to guide the search can make the process more efficient.
 Minimax Search Algorithm
The minimax algorithm is a decision-making algorithm commonly used in
two player games, such as chess or tic-tac-toe. It helps determine the
optimal move for a player assuming both players play optimally. Here's a
breakdown of how it works:

Key Concepts
1. Game Tree: The possible moves are represented in a tree structure,
where each node represents a game state.
 2. Min and Max Players: One player (Max) aims to maximize their score,
while the other player (Min) aims to minimize Max's score.
3. Leaf Nodes: The end states of the game (win, lose, draw) are evaluated
to assign a score.

Algorithm Steps
1. Generate the Game Tree: Start from the current game state and generate
all possible future states up to a certain depth or until the game ends.
2. Evaluate Terminal Nodes: For terminal states, assign scores:
o Win for Max: High positive value (e.g., +10)
o Win for Min: High negative value (e.g., -10)
o Draw: Neutral value (e.g., 0)
3. Backpropagation:
o For each non-terminal node:
 If it's Max's turn, select the maximum score from its
children.
 If it's Min's turn, select the minimum score from its children.
4. Choose the Best Move: The root node (current state) will then have a
score, and the best move is the one that leads to the child with the
optimal score.
Applications
 Board games (chess, tic-tac-toe)
 Strategy games
 Decision-making in artificial intelligence
Pseudocode
CHAPTER 6 : CONSTRAINT SATISFACTION PROBLEM