Problem-Solving Agents in AI

A problem-solving agent is a type of intelligent agent in Artificial Intelligence (AI) that

decides what to do by finding sequences of actions that lead to desirable goals. These
agents operate in deterministic, fully observable, and discrete environments.

🔷 Characteristics of Problem-Solving Agents

 Goal-based: Focused on achieving a particular goal.

 Use search strategies: Explore different possible sequences of actions.
 Work with models: Need knowledge of action consequences (i.e., transition model).
 Environment assumptions:
o Fully observable (can perceive all aspects of the state).

o Deterministic (outcome of actions is predictable).

o Static (environment doesn’t change while thinking).

o Discrete (finite number of distinct states and actions).

🔷 Components of a Problem-Solving Agent

Component Description

Initial State The starting point of the agent.

Actions (Operators) Set of actions available to the agent.

Transition Model Description of what each action does.

Goal Test Determines if a given state is a goal state.

Path Cost Numeric cost associated with a sequence of actions.

🔷 Problem-Solving Process

1. Formulate the problem (define initial state, goal, actions, etc.)

2. Search for a solution (using search algorithms)
3. Execute the solution (apply the actions in the real world)

🔷 Types of Search in Problem Solving

 1. Uninformed (Blind) Search: No domain-specific knowledge
o Breadth-First Search

o Depth-First Search

o Uniform Cost Search

2. Informed (Heuristic) Search: Uses problem-specific knowledge

o Greedy Best-First Search

o A* Search

🔷 Example: 8-Puzzle Problem

 Initial State: A specific arrangement of the 8 tiles.

 Goal State: Tiles in a specific final arrangement.
 Actions: Move the blank tile up/down/left/right.
 Transition Model: Defines the result of moving the blank.
 Goal Test: Check if the current state matches the goal.
 Path Cost: Number of moves made.

🔷 Advantages

 Effective in structured environments.

 Helps in planning and decision-making.

🔷 Limitations

 May not perform well in dynamic or partially observable environments.

 Search space can be very large (combinatorial explosion).

🔷 Applications

 Pathfinding in robotics and games.

 Puzzle solving (8-puzzle, Sudoku).
 Planning in logistics and operations.
Example Problems in Problem-Solving Agents in AI
Problem-solving agents in AI use search algorithms and strategies to find solutions to given
problems. Here are some classic examples of problems that are often used to illustrate
problem-solving agents:
1. Toy Problems
These are simplified problems used to test and compare different search algorithms.
(a) 8-Puzzle Problem
Description: A 3×3 grid with 8 numbered tiles and 1 blank space. The goal is to rearrange the
tiles from a given initial state to a goal state by sliding tiles into the empty space.
Example:
Initial State: Goal State:
283 123
164 8 4
7 5 765
Challenges: Finding the shortest sequence of moves (optimal path).
Algorithms Used: BFS, DFS, A* (with Manhattan distance heuristic).
(b) Missionaries and Cannibals Problem
Description: Three missionaries and three cannibals must cross a river using a boat that can
carry at most two people. At no point should cannibals outnumber missionaries on either side.
Example Moves:
(3M, 3C, Left) → (2M, 2C, Right) after one missionary and one cannibal cross.
Algorithms Used: State-space search, BFS.
c) N-Queens Problem
Description: Place N queens on an N×N chessboard such that no two queens threaten each
other.
Example (4-Queens):
```
·Q··
···Q
Q···
··Q·
Algorithms Used: Backtracking, Constraint Satisfaction.
2. Real-World Problems
These are more complex problems modeled after real-world scenarios.
(a) Route-Finding Problem (Navigation)
Description: Find the shortest path between two cities given a map with distances.
Example:
Cities: A, B, C, D
Roads: A-B (5 km), B-C (3 km), A-D (10 km), D-C (2 km)
Goal: Shortest path from A to C (A → B → C = 8 km).
Algorithms Used: Dijkstra’s, A* (with Euclidean distance heuristic).
(b) Traveling Salesman Problem (TSP)
Description: Find the shortest possible route that visits each city exactly once and returns to
the origin.
Example:
Cities: A, B, C
Distances: A-B (10), B-C (15), A-C (20)
Solution: A → B → C → A (Total = 45).
Algorithms Used: Genetic Algorithms, Dynamic Programming (for small N).
(c) Sokoban (Warehouse Keeper Puzzle)
Description: A player pushes boxes to storage locations in a grid with obstacles.
Example:
Initial: Goal:
#### ####
#PB# # B#
# @# #P@#
#### ####
(P: Player, B: Box, @: Target)
Algorithms Used: A*, BFS (due to high branching factor).

3. Constraint Satisfaction Problems (CSPs)

These involve finding solutions that satisfy a set of constraints.
(a) Sudoku
Description: Fill a 9×9 grid so that each row, column, and 3×3 subgrid contains digits 1–9
without repetition.
Algorithms Used: Backtracking, AC-3 (Arc Consistency).
(b) Graph Coloring
Description: Color a graph’s vertices such that no two adjacent vertices share the same color.
Example:
Minimum colors for a map (Four Color Theorem).
Algorithms Used: Backtracking, Greedy Search.
Key Takeaways
Toy Problems help test algorithms (e.g., 8-Puzzle, N-Queens).
Real-World Problems are more complex (e.g., TSP, Route-Finding).
CSPs require satisfying constraints (e.g., Sudoku, Graph Coloring).

In Artificial Intelligence (AI), problem-solving agents use search strategies to find solutions
to well-defined problems. These agents operate in environments where they can plan actions
to reach a goal. Let’s break this down clearly:

🔍 SEARCH PROBLEM IN AI

A Search Problem is defined by the following components:

1. Initial State
 The starting point of the agent.
 Example: In the 8-puzzle, it's the current arrangement of tiles.
2. Action(s)
 The possible actions the agent can take.
 Example: Move a tile up, down, left, or right.
3. Transition Model
 Describes what state results from performing a specific action in a given state.
 Example: Moving tile 1 to the empty spot changes the configuration.
4. Goal Test
  A function to determine if the current state is the goal.
 Example: All tiles are in order in the 8-puzzle.
5. Path Cost
 The total cost of a path (sum of individual step costs).
 Used in informed search to evaluate efficiency.

✅ SOLUTIONS TO SEARCH PROBLEMS

A Solution is a sequence of actions leading from the initial state to a goal state.
The agent uses search algorithms to find this sequence. These are classified as:

🔵 Uninformed Search (Blind Search)

 No domain-specific knowledge used.

 Examples:
1. Breadth-First Search (BFS) – Explores all nodes at one depth before going
deeper.
2. Depth-First Search (DFS) – Explores as far as possible down one branch
before backtracking.
3. Uniform Cost Search – Expands the lowest-cost path node.

🟢 Informed Search (Heuristic Search)

 Uses heuristics (estimated cost to goal).

 Examples:
1. Greedy Best-First Search – Chooses the path that appears best (lowest
heuristic).
2. A Search* – Combines path cost and heuristic: f(n) = g(n) + h(n).

💡 EXAMPLES OF PROBLEM-SOLVING AGENTS

1. 8-Puzzle Problem
 Goal: Arrange tiles in the correct order.
 Solution: A sequence of moves using A* or BFS.
2. Traveling Salesman Problem
 Goal: Visit all cities with the least cost.
 Solution: Brute-force search or approximation algorithms.
3. Robot Path Planning
 Goal: Navigate from point A to B avoiding obstacles.
 Solution: Grid-based A* search.
4. Wumpus World
 Goal: Find gold and avoid hazards.
 Solution: Logical inference + search.

📌 Summary Table

Component Description

Initial State Where the agent begins

Actions Possible moves from a state

Transition Model What results from actions

Goal Test Has the goal been reached?

Path Cost Total cost of a path

Solution Sequence of actions to reach the goal

Uninformed Search Strategies in Solving Problems by Searching

Uninformed search strategies (also known as blind search) are search methods that do not
have any additional information about the states beyond the problem definition. They
explore the search space without knowing how far the goal is or how costly a path might
be.

🔍 Common Uninformed Search Strategies:

1. Breadth-First Search (BFS)

 Strategy: Explores all the nodes at the current depth level before moving to the next
level.
 Data Structure Used: Queue (FIFO)
  Completeness: ✅ Yes (if branching factor is finite)

 Time Complexity: O(b^d)

 Space Complexity: O(b^d)
 Optimal: ✅ Yes (if step cost = 1)

2. Depth-First Search (DFS)

 Strategy: Explores as far as possible along each branch before backtracking.
 Data Structure Used: Stack (LIFO) or recursion
 Completeness: ❌ No (may go into infinite depth)

 Time Complexity: O(b^m)

 Space Complexity: O(bm)
 Optimal: ❌ No

3. Depth-Limited Search (DLS)

 Strategy: DFS with a predetermined depth limit.
 Limitation: May miss the solution if it’s beyond the limit.
 Completeness: ✅ Yes (if limit ≥ depth of solution)

 Time Complexity: O(b^l)

 Space Complexity: O(bl)
 Optimal: ❌ No

4. Iterative Deepening Depth-First Search (IDDFS)

 Strategy: Repeatedly applies DFS with increasing depth limits.
 Combines: Benefits of BFS (completeness, optimality) and DFS (low memory).
 Completeness: ✅ Yes

 Time Complexity: O(b^d)

 Space Complexity: O(bd)
 Optimal: ✅ Yes (if step cost = 1)
5. Uniform Cost Search (UCS)
 Strategy: Expands the node with the lowest path cost (g(n)).
 Data Structure Used: Priority Queue (based on cost)
 Completeness: ✅ Yes

 Time Complexity: O(b^C*/ε)

 Space Complexity: O(b^C*/ε)
 Optimal: ✅ Yes (always)

📌 Summary Table:

Strategy Complete Optimal Time Complexity Space Complexity

BFS Yes Yes O(b^d) O(b^d)

DFS No No O(b^m) O(bm)

DLS Yes* No O(b^l) O(bl)

IDDFS Yes Yes O(b^d) O(bd)

UCS Yes Yes O(b^C*/ε) O(b^C*/ε)

Where:
 b = branching factor
 d = depth of the shallowest goal
 m = maximum depth of the search tree
 C* = cost of optimal solution
 ε = smallest step cost

📘 Use Case Example:

Imagine a robot navigating a maze from the entrance to an exit:

 BFS guarantees finding the shortest number of steps to the exit.
 DFS might go deep into dead ends.
 UCS finds the least-cost path if steps have different weights.
 IDDFS finds the shortest path like BFS but uses less memory.
 Informed Search Strategies in Solving Problems by Searching (AI)
In Artificial Intelligence (AI), informed search strategies (also called heuristic search
strategies) use additional knowledge (heuristics) about the problem domain to find
solutions more efficiently than uninformed methods like BFS or DFS.

🔍 What is Informed Search?

Informed search strategies use heuristic functions (h(n)), which estimate the cost from a
node n to the goal. These strategies prioritize nodes that seem more promising, leading to
faster solutions.

✅ Key Features of Informed Search:

 Uses domain-specific knowledge.

 Guides the search towards the goal.
 Reduces time and memory usage compared to uninformed search.

💡 Common Informed Search Strategies

1. Best-First Search
 Uses a heuristic function h(n).
 Selects the node with the lowest heuristic value.
 May not guarantee the shortest path.
2. A Search Algorithm*
 Uses the function: f(n) = g(n) + h(n)
o g(n) = cost from start node to node n.

o h(n) = estimated cost from n to goal.

 Optimal and complete if h(n) is admissible (never overestimates).

3. Greedy Best-First Search
 Uses: f(n) = h(n)
 Fast but not guaranteed to find the optimal solution.
 Focuses only on reaching the goal quickly, ignoring path cost so far.
🔑 Heuristic Function (h(n))

 A rule-of-thumb to estimate the cost to reach the goal.

 Examples:
o Straight-line distance in route problems.

o Number of misplaced tiles in the 8-puzzle.

📊 Comparison with Uninformed Search:

Feature Uninformed Search Informed Search

Uses heuristics ❌ No ✅ Yes

Efficiency ❌ Slower ✅ Faster

Goal guidance ❌ Blind ✅ Guided

Optimality Depends on algorithm A* is optimal if h is admissible

🧠 Applications of Informed Search:

 Route finding (e.g., Google Maps)

 Game playing (e.g., Chess AI)
 Puzzle solving (8-puzzle, Sudoku)
 Robotics and path planning

📌 Summary

Informed search strategies improve problem-solving efficiency by guiding the search using
heuristics. The most notable is A*, which balances exploration and cost-effectiveness,
making it widely used in AI applications.

Heuristic Functions

✅ What is a Heuristic Function?

A heuristic function (often denoted as h(n)) is a technique in informed (heuristic) search

strategies that provides an estimated cost from the current state n to the goal state. It helps
in guiding the search algorithm efficiently toward the solution by evaluating the “desirability”
of nodes.

🎯 Purpose of Heuristic Function:

 To reduce the search space.

 To find a solution faster than uninformed strategies like BFS or DFS.
 To make the algorithm goal-directed.

💡 Common Heuristic Search Algorithms Using Heuristic Function:

Algorithm Uses Heuristic Description

Greedy Best-First Selects the node that appears to be closest to the

✅ Yes (h(n))
Search goal.

✅ Yes (f(n) = g(n) + Combines cost from start node and heuristic to
A*
h(n)) goal.

Explores only a limited number of best paths

Beam Search ✅ Yes
based on heuristic values.

🧠 Properties of a Good Heuristic Function:

1. Admissibility:
A heuristic is admissible if it never overestimates the cost to reach the goal.
→ Ensures optimality in A*.
2. Consistency (Monotonicity):
A heuristic is consistent if for every node n and successor n',
3. h(n) ≤ c(n, n') + h(n')
→ Guarantees optimality and efficiency in A*.

📘 Examples of Heuristic Functions:

1. 8-Puzzle Problem:
o h1(n) = Number of misplaced tiles.

o h2(n) = Sum of Manhattan distances of tiles from their goal positions.

2. Traveling Salesman Problem (TSP):

 o Heuristic = Minimum spanning tree (MST) estimate from current city to
unvisited cities.
3. Robot Path Planning:
o Heuristic = Euclidean or Manhattan distance to goal point.

📊 Comparison of Heuristic Functions:

Heuristic Complexity Accuracy Example Use

Misplaced Tiles Low Moderate 8-Puzzle

Manhattan Distance Moderate High 8/15-Puzzle

Straight-line Distance Low Moderate Pathfinding

⚠️Important Notes:

 A poor heuristic can mislead the search and degrade performance.

 In A*, admissibility and consistency are crucial for optimal solutions.
 Heuristic design is often domain-specific.

Beyond Classical Search: Local Search Algorithms and Optimization Problems

🔍 1. Introduction

Classical search algorithms (like BFS, DFS, A*, etc.) explore systematic paths through a
state space from a start state to a goal. However, in local search and optimization
problems, the focus shifts:
 The goal is not a specific state, but rather finding the best state according to an
objective function.
 These problems often deal with large or infinite search spaces where traditional
search is impractical.

🧭 2. What is Local Search?

Local search algorithms operate using a single current node (state) and move to
neighboring states to try and find better solutions.
Characteristics:
 Uses little memory.
  Often used in optimization problems.
 May not guarantee the optimal solution.
 Good for large state spaces where classical search is infeasible.

🧠 3. Common Local Search Algorithms

Algorithm Description Strengths Weaknesses

Move to neighbor with highest value Can get stuck in

Hill Climbing Simple, fast
(greedy) local maxima

Allows some downhill moves to

Simulated Escapes local Requires careful
escape local optima using a
Annealing maxima tuning of schedule
temperature schedule

Local Beam Keeps k states instead of one and Uses collective

Still can get stuck
Search chooses best successors information

Genetic Inspired by natural evolution; uses Works in diverse Requires tuning,

Algorithms selection, crossover, mutation spaces randomness

🧮 4. Optimization Problems

These are problems where the goal is to maximize or minimize an objective (fitness)
function.
Examples:
 Travelling Salesman Problem (TSP) – minimize total travel distance.
 Job Scheduling – maximize efficiency or minimize time.
 Knapsack Problem – maximize value without exceeding capacity.
 Neural Network Weight Optimization – minimize error rate.

📈 5. State Space Landscape

In local search:
 States are plotted against objective value.
 Problems arise from local maxima, plateaus, and ridges.

6. Strategies to Overcome Local Minima

  Random Restart: Run multiple times with different initial states.
 Simulated Annealing: Accept worse moves probabilistically.
 Stochastic Hill Climbing: Randomly choose among uphill moves.
 Tabu Search: Avoid cycles by keeping a list of recently visited states.

✅ 7. Advantages of Local Search

 Works well for combinatorial optimization.

 Space-efficient.
 Suitable for real-time and online systems.

❌ 8. Limitations

 May not find global optimum.

 No complete path information.
 Performance sensitive to problem representation.

Local search algorithms are essential tools in AI for solving complex optimization problems,
especially when classical search becomes infeasible due to space or time complexity. Their
simplicity, scalability, and applicability to real-world problems make them crucial in fields
like robotics, machine learning, and operations research.

Local Search in Continuous Spaces

🔍 What is Local Search in AI?

Local search is a heuristic-based search method that explores the neighborhood of a

candidate solution to find a better solution. It is particularly effective in optimization
problems where the search space is vast or infinite.

📌 Local Search in Continuous Spaces

In continuous spaces, the set of possible solutions is infinite and uncountable, such as real-
number domains (e.g., adjusting a robot arm's angle between 0° and 180°).
✅ Key Characteristics:

 The state space is continuous, not discrete.

 Solutions are points in a multi-dimensional real-valued space.
 Often used in robotics, machine learning hyperparameter tuning, control systems,
etc.

🌐 Examples of Problems in Continuous Space:

 Finding optimal weights in a neural network.

 Tuning parameters in a PID controller.
 Minimizing cost functions in calculus-based optimization.

⚙️Algorithms Used:

Several optimization algorithms are applied for continuous local search:

1. Hill Climbing (Gradient Ascent/Descent)
 Moves in the direction of increasing (or decreasing) value.
 Uses gradient information if available.
 May get stuck in local maxima/minima.
2. Simulated Annealing
 Randomly explores the space.
 Occasionally accepts worse solutions to escape local optima.
 Good for continuous and rugged landscapes.
3. Genetic Algorithms (GA)
 Works well for both discrete and continuous problems.
 Uses crossover, mutation, and selection.
 Maintains a population of solutions.
4. Particle Swarm Optimization (PSO)
 Inspired by social behavior of birds.
  Particles “fly” through the search space influenced by their own and neighbors’ best-
known positions.
5. Gradient Descent (if differentiable)
 Efficient in smooth landscapes.
 Uses partial derivatives to move toward minimum.
 Can use variants like SGD, Adam, etc.

📊 Visualization:

Imagine a landscape with hills and valleys:

 Each point = a potential solution.
 Local search = navigating this terrain to find the lowest valley (minimization) or
highest hill (maximization).

⚠️Challenges:

 Local optima trap.

 Plateaus: no change in cost function in nearby states.
 Requires tuning of step size, temperature (in SA), population size (in GA), etc.
 Performance heavily depends on initial conditions.

✅ Use Cases:

 AI in robotics: inverse kinematics problems.

 Neural network optimization.
 Autonomous vehicles: path planning.
 Game playing agents: parameter tuning.

📝 Summary Table:

Feature Local Search in Discrete Space Local Search in Continuous Space

State Space Finite/Countable Infinite/Uncountable

Examples N-Queens, TSP Neural Net Tuning, Robotics

Techniques Hill Climbing, Genetic Algo Gradient Descent, PSO, Simulated Annealing
Feature Local Search in Discrete Space Local Search in Continuous Space

Challenge Local Optima Local Optima, Plateaus, Derivatives

Searching with Nondeterministic Actions

In Artificial Intelligence (AI), particularly in search-based problem solving, most

algorithms assume that the outcome of actions is deterministic — that is, the result of
performing an action in a state is always predictable.
However, in many real-world scenarios, actions can have nondeterministic outcomes due to
uncertainty in the environment. This leads to the concept of:

🔍 Searching with Nondeterministic Actions

✅ Definition:

Nondeterministic actions are actions whose results are not completely predictable. A single
action may lead to multiple possible outcomes, each possibly leading to a different state.

🧠 Problem-Solving with Nondeterministic Actions

When dealing with nondeterministic actions, the traditional notion of a single-path solution
is insufficient. Instead, we use search trees or graphs where each action may branch into
multiple outcomes.

Modeling a Nondeterministic Problem:

A nondeterministic problem is typically modeled as a tuple:

(P) = (S, A, RESULT, GOAL-TEST)
 S – Set of states
 A – Set of actions
 RESULT(s, a) – Returns a set of possible outcome states
 GOAL-TEST – Function to test if a state is a goal
📌 Three Types of Solutions in Nondeterministic Settings:

1. Single-path plan (may fail due to unpredictability)

2. Contingency plan (includes branches depending on outcomes)
3. Policy (maps states to actions, like in MDPs)

🔄 AND-OR Graphs in Nondeterministic Search

To solve nondeterministic problems, we often use AND-OR trees/graphs:

 OR nodes: Represent choices of actions
 AND nodes: Represent multiple possible outcomes of one action, all of which must
be solved
Example:
To reach the goal from S, if action A can result in states S1 or S2,
AND both S1 and S2 must lead to the goal for A to be a valid solution.

🔍 Search Algorithms Used:

 AND-OR Graph Search

 Backtracking Search with Nondeterminism
 Minimax with Chance Nodes (in adversarial or probabilistic environments)

⚠️Challenges in Nondeterministic Search:

 Increased complexity (explosion of branching)

 Incomplete or unreliable information
 May require sensing or observation plans

📘 Example Scenario:

Imagine a robot in a maze:

 Action: "Move Forward"
 Outcomes:
o Robot moves forward (90%)
 o Robot slips and stays in place (10%)

Here, planning must account for both outcomes.

Searching with nondeterministic actions enables agents to plan effectively in uncertain
environments, often requiring more sophisticated strategies such as contingency planning,
AND-OR search, or policies, rather than simple action sequences.
Searching with Partial Observations
Searching with Partial Observations in AI refers to solving problems where the agent does
not have complete information about the environment or the current state. This type of
search is common in partially observable environments, where the agent only has limited,
noisy, or uncertain sensory data.

🔍 Key Concepts:

1. Partial Observability:
 The agent cannot see the full state of the world.
 It only receives observations that give partial information.
 Example: A robot navigating in a smoky room with limited visibility.
2. Belief State:
 Since the actual state is unknown, the agent keeps track of a belief state.
 A belief state is a set or probability distribution over all possible actual states.
3. Searching in Belief Space:
 The search happens over belief states rather than physical states.
 Actions and observations update the belief state.
 This leads to more complex planning compared to fully observable search.

🔧 Approaches:

🔹 Contingent Planning:

 The plan includes conditional branches based on future observations.

 Example: “If I hear a sound, go left; otherwise, go right.”
🔹 Conformant Planning:

 Finds a plan that works regardless of which state the agent starts in.
 Useful when no observations are available during execution.
🔹 Partially Observable Markov Decision Processes (POMDPs):

 A formal model for decision-making under uncertainty.

 Includes:
o A set of states

o A set of actions

o A set of observations

o Transition and observation probabilities

o A reward function

✅ Examples:

Scenario Partial Observation

Wumpus World Agent senses breeze/smell but doesn’t know exact locations of pits/Wumpus

Robot in Maze Robot uses noisy sensors (e.g., GPS)

Pacman Game Ghosts are hidden unless close

📌 Summary:

Feature Fully Observable Partially Observable

Agent knows full

✅ Yes ❌ No
state?

Uses Belief State? ❌ No ✅ Yes

Search Space State Space Belief Space

Complex (Contingent,
Planning Simple (DFS, A*)
POMDP)

online search agents and unknown

environments.
In Artificial Intelligence (AI), online search agents and unknown environments play a
crucial role in building intelligent systems that can operate under uncertainty. Here's a
structured explanation of the concept as it appears under "Solving Problems by Searching":

✅ Online Search Agents and Unknown Environments in AI

🔹 What is an Online Search Agent?

An online search agent is an agent that must interleave computation and action. Unlike
offline agents (which compute the complete solution before acting), online agents must act
without having complete knowledge of the environment.
🔸 In other words, they perceive the environment step-by-step and make decisions as they
go.
🔹 What is an Unknown Environment?

An unknown environment is one where:

 The agent has no prior knowledge of the state space.
 The effects of actions may be unknown or unpredictable.
 The map of the world is revealed only as the agent explores.

✅ Characteristics of Online Search in Unknown Environments

Feature Description

🔍 Exploration Agent learns about the environment during execution.

🔁 Interleaved execution The agent alternates between planning and acting.

❓ Incomplete knowledge The agent does not know the full map or goal state in advance.

🤖 Adaptability The agent must adapt its strategy based on new perceptions.

✅ Example Problems

1. Maze Navigation – The agent doesn’t know the maze layout and must explore it to
reach the goal.
2. Robot Vacuum Cleaner – Doesn’t know the room layout; it must clean while
discovering walls/furniture.
 3. Wumpus World – The agent explores a grid-based environment with unknown
hazards.

✅ Online Search Algorithm: General Steps

1. Sense the Environment (get percepts)

2. Update Knowledge Base (what has been learned)
3. Choose Action using a search strategy (e.g., DFS, BFS)
4. Perform the Action
5. Repeat until goal is found or task completed

✅ Common Strategies Used in Online Search

Algorithm Notes

Useful when space is tight, but can get lost in deep

Depth-First Search (DFS)
branches.

Breadth-First Search (BFS) Finds shortest path but requires memory for visited nodes.

Moves towards better states, but may get stuck in local

Hill-Climbing
maxima.

A* Search Can be adapted for online use with heuristic updates.

LRTA* (Learning Real-Time Learns the cost of states as it moves and improves over
A*) time.

✅ Advantages of Online Search in Unknown Environments

 Works without complete information.

 Can handle dynamic or changing environments.
 Agent learns from experience and improves.

✅ Limitations

 May be inefficient due to repeated exploration.

 May get stuck in loops if not designed properly.
 Requires good exploration strategy to avoid dead ends.
✅ Summary Table

Concept Description

Online Agent Acts without full knowledge, updates knowledge while exploring.

Unknown Environment Agent doesn't know all states, transitions, or goals beforehand.

Application Areas Navigation, robotics, gaming, exploration systems.