Chapter 3: Problem-Solving Agents
3.1 Introduction to Problem-Solving Agents:
Intelligent agents aim to maximize their performance measure, often simplified by adopting
goals. A goal helps the agent focus on specific objectives and organize behavior by limiting the
actions it needs to consider.
3.1.2 Goal Formulation:
Goal formulation is based on the agent's current situation and performance measure.
A goal is defined as a set of world states where the goal is satisfied.
The agent’s task is to determine how to act so that it reaches one of these goal states.
3.1.3 Problem Formulation:
Problem formulation involves deciding:
• What states the agent will consider.
• What actions it should take to reach the goal.
• If actions are too detailed (e.g., “move the left foot an inch”), the agent would struggle with
too much complexity and uncertainty.
Example: Driving from town to town instead of considering every minute action.
3.1.4 Agent's Decision Process:
Initial Problem: From Belgaum, the agent has three roads leading to Bangalore, Hubli, and
Mangalore —none of which directly reaches Goa.
• Without knowledge of Goa’s geography, the agent won’t know which road to follow.
• If the agent has no additional information, it must select a random action, a scenario
discussed in detail in next Module.
3.1.5 Using Knowledge to Guide Decisions:
Maps provide agents with information about the states they could enter and the actions they
can take.
The agent can simulate future actions using the map to find a route to Goa.
Example:
By identifying a path on the map, the agent can plan its journey step-by-step and achieve
the goal by following the identified route.
3.1.6 Significance of Problem-Solving Process:
When options have unknown value, the agent can evaluate future actions that might
eventually lead to known states of value (goal states).
This process of reasoning and simulating future actions is crucial for problem-solving in
uncertain environments.
3.2 What is a State Space?
• A state space is the set of all possible configurations (states) of a problem.
• A state represents a particular condition or situation in the problem-solving process.
Example: In a route-finding problem, a state could be the agent being in a specific city.
3.2.1 Components of a State Space Search:
1. Initial State:
The starting point of the search.
Example: In a pathfinding problem, the agent starts in Belgaum.
2. Goal State:
A desired state that the agent aims to reach.
Example: The goal is to reach Goa.
3. State Transition Function (Successor function):
A function that defines how the agent moves from one state to another by
performing actions. Successor function – Result (state, action)
Example: The agent transitions from one town or city to another by following
roads.
4. Actions (Operators):
These are operations or moves that transition the agent from one state to another.
Example: Belgaum → Khanapur → Londa → Goa.
5. Path Cost:
A measure of the total cost to reach a state from the initial state.
Example: Distance in kilometers, Travel time and Fuel consumption or toll charges.
3.3 Example Problems:
Toy problems:
1. Vacuum world:
This can be formulated as a problem as follows:
1. Initial state: Any state can be designated as the initial state.
2. Actions: In this simple environment, each state has just three actions: Left, Right, and Suck.
Larger environments might also include Up and Down.
3. Transition model (Successor Function): The actions have their expected effects, except
that moving Left in the leftmost square, moving Right in the rightmost square, and Sucking in
a clean square have no effect. The complete state space is shown in Figure 3.3.
4. Goal test: This checks whether all the squares are clean.
5. Path cost: Each step costs 1, so the path cost is the number of steps in the path.
States: The state is determined by both the agent location and the dirt locations. The agent
is in one of two locations, each of which might or might not contain dirt. Thus, there are 2 *
22 = 8 possible world states. A larger environment with n locations has n * 2n states.
2. The 8-puzzle: an instance of which is shown in Figure 3.4, consists of a 3×3 board with
eight numbered tiles and a blank space. A tile adjacent to the blank space can slide into the
space. The object is to reach a specified goal state, such as the one shown on the right of the
figure. The standard formulation is as follows:
1. States: A state description specifies the location of each of the eight tiles and the blank in
one of the nine squares.
2. Initial state: Any state can be designated as the initial state. Note that any given goal can be
reached from exactly half of the possible initial states (Exercise 3.4).
3. Actions: The simplest formulation defines the actions as movements of the blank space
Left, Right, Up, or Down. Different subsets of these are possible depending on where the
blank is.
4. Transition model: Given a state and action, this returns the resulting state; for example, if
we apply Left to the start state in Figure 3.4, the resulting state has the 5 and the blank
switched.
5. Goal test: This checks whether the state matches the goal configuration shown in Figure
3.4. (Other goal configurations are possible.)
6. Path cost: Each step costs 1, so the path cost is the number of steps in the path.
The 8-puzzle belongs to the family of sliding-block puzzles, which are often used as test problems
for new search algorithms in AI. This family is known to be NP-complete, so one does not expect
to find methods significantly better in the worst case than the search algorithms described in this
chapter and the next. The 8-puzzle has 9!/2=181, 440 reachable states and is easily solved. The
15-puzzle (on a 4×4 board) has around 1.3 trillion states, and random instances can be solved
optimally in a few milliseconds by the best search algorithms. The 24-puzzle (on a 5 × 5 board)
has around 1025 states, and random instances take several hours to solve optimally.
3. The 8 – Queens Problem:
The goal of the 8-queens problem is to place eight queens on a chessboard such that no
queen attacks any other. (A queen attacks any piece in the same row, column or diagonal.)
Figure 3.5 shows an attempted solution that fails: the queen in the rightmost column is
attacked by the queen at the top left.
1. States: Any arrangement of 0 to 8 queens on the board is a state.
2. Initial state: No queens on the board.
3. Actions: Add a queen to any empty square.
4. Transition model (Suc: Returns the board with a queen added to the specified square.
5. Goal test: 8 queens are on the board, none attacked.
Additional Information:
In this formulation, we have 64 * 63 * ・ ・ 57 ≈ 1.8 * 1014 possible sequences to investigate. A
better formulation would prohibit placing a queen in any square that is already attacked:
• States: All possible arrangements of n queens (0 ≤ n ≤ 8), one per column in the
leftmost n columns, with no queen attacking another.
• Actions: Add a queen to any square in the leftmost empty column such that it is not
attacked by any other queen.
This formulation reduces the 8-queens state space from 1.8×1014 to just 2,057 and solutions
are easy to find. On the other hand, for 100 queens the reduction is from roughly 10400 states
to about 1052 states - a big improvement, but not enough to make the problem tractable.
3.4 Uninformed Search vs Informed Search:
Traveling from Belgaum to Goa
• Uninformed Search:
The agent tries all possible routes systematically without knowing which is shortest,
exploring Belgaum → Khanapur → Londa → Goa, or Belgaum → Ramnagar → Molem →
Goa.
• Informed Search:
The agent uses a heuristic like the straight-line distance to Goa, prioritizing a route
through Ramnagar if it seems shorter, leading to faster convergence on the solution.
Aspect Uninformed Search Informed Search
Does not use problem-specific Uses heuristic knowledge to
Knowledge Used knowledge beyond the problem guide the search towards the goal
definition. more efficiently.
Heuristic search: Uses
Blind search: Explores the state estimates (heuristics) to make
Guidance space without any knowledge of the decisions about which path is
cost or distance to the goal. more likely to reach the goal
quickly.
Expands nodes based on the
Expands nodes systematically (e.g.,
Exploration Strategy estimated cost or proximity to
all neighbors or levels).
the goal.
Some algorithms are optimal, like Optimal if the heuristic used is
Optimality
Uniform Cost Search. admissible (e.g., A* search).
Generally higher because it
Time and Space Generally lower due to focused
explores more nodes before
Complexity exploration using heuristics.
reaching the goal.
- Greedy Best-First Search
- Breadth-First Search (BFS)
Examples - A* Search
- Depth-First Search (DFS)
- Heuristic Search
When domain-specific
When there is no prior information
knowledge (like straight-line
When to Use about the goal location or path
distance) is available to make
costs.
better decisions.
Example for Uninformed Search
Example for Informed Search
3.4.1 Uninformed Search Strategies:
1. Breadth-first search:
Breadth-First Search (BFS) is an uninformed search algorithm that explores a graph or tree
systematically, level by level. It is widely used in AI for problems where all solutions at the
shallowest level need to be found. BFS guarantees finding the shortest path (in terms of the
number of steps) in unweighted graphs or state spaces.
How BFS Works
BFS starts from a given initial state (or root node) and explores all its neighbors before moving
to the next level of nodes. It uses a queue data structure (FIFO: First In, First Out) to keep
track of nodes that need to be visited.
Properties of BFS:
Property Details
Completeness Yes, if the branching factor is finite.
Optimality Yes, if all step costs are equal (unweighted graph).
O(b^d), where b is the branching factor and d is the depth of the
Time Complexity
solution.
Space Complexity O(b^d), as BFS stores all nodes at the current level in memory.
Explores level by level (all nodes at one depth before moving to the
Search Strategy
next).
Finding the shortest path in unweighted graphs or problems with
Suitable for
shallow solutions.
Advantages of BFS:
1. Completeness: BFS will find a solution if one exists.
2. Optimality: Guarantees the shortest path if all step costs are equal.
3. Simple Implementation: It uses a straightforward queue-based approach.
Disadvantages of BFS:
1. High Memory Usage: BFS stores all nodes at the current level, making it memory-intensive
for deep graphs.
2. Slow for Large State Spaces: If the branching factor is large or the goal state is far, BFS can
take a lot of time.
3. Not Suitable for Infinite Depths: Without additional checks, BFS can get stuck exploring
infinite graphs.
When to Use BFS:
• When you need the shortest path (in terms of the number of steps).
• For problems with small or shallow state spaces.
• When all edges have equal weight (unweighted graphs).
2. Depth-First Search (DFS) in AI:
Depth-First Search (DFS) is an uninformed search algorithm that explores a graph or tree
along one path as deeply as possible before backtracking. Unlike BFS, which explores level-by-level,
DFS dives deep into a branch and only moves to the next branch when the current path is exhausted.
This strategy is helpful when solutions are located deep in the search tree.
How DFS Works:
DFS uses a stack (either explicitly or via recursion) to manage the nodes. It explores a node and
continues to its first unvisited child, moving deeper until it reaches a dead-end (i.e., no more
unexplored children). At that point, it backtracks to the previous node and tries the next child.
Properties of BFS:
Property Details
Completeness No, DFS can get stuck in infinite loops.
Optimality No, DFS may find a solution that is not the shortest.
O(b^m), where b is the branching factor and m is the maximum
Time Complexity
depth.
Space Complexity O(b * m), as DFS only stores the current path in memory.
Explores deep paths first (goes down one branch before trying
Search Strategy
others).
Problems where the solution is likely deep in the search tree or
Suitable for
memory is limited.
Advantages of DFS:
1. Low Memory Usage: DFS only stores the current path, resulting in better space efficiency.
2. Suitable for Deep Solutions: DFS works well if the solution is far down the tree.
3. Simple Implementation: DFS can be easily implemented using recursion or an explicit
stack.
Disadvantages of DFS:
1. Not Complete: If the search space has cycles or infinite paths, DFS may get stuck in a
loop.
2. Not Optimal: DFS might not find the shortest path.
3. High Time Complexity: If the solution is far down the search tree, DFS can take a long time.
When to Use DFS:
• When memory is limited.
• When the solution is likely to be deep.
• When all solutions need to be found (e.g., for backtracking puzzles).
• When the search space is large, and the solution depth is unknown.