18

Problem solving agents in AI

© Dr. Dafda
❖ Introduction to Problem-Solving Agents:
•What are Problem-Solving Agents?
➢ A type of goal-based agent that plans actions to achieve
specific goals.
➢ Operate in simple environments with clear goals and
fixed sequences of actions.
•How They Work:
➢ Formulate a Problem: Define the initial state, goal state,
and possible actions.
➢ Search for a Solution: Explore different paths using
search algorithms.
➢ Execute the Solution: Perform the actions step by step.
•Example:
➢ Taxi Agent trying to get from City A to City B using a
map.
❖ Goal formulation and Problem formulation:

• The problem of AI is directly associated with the nature of humans and their activities. So we
need a number of finite steps to solve a problem which makes human easy works. Major steps are:

•Goal Formulation:
➢ This one is the first and simple step in problem-solving. It organizes finite steps to formulate
a target/goals which require some action to achieve the goal. Today the formulation of the
goal is based on AI agents.

•Problem formulation:
➢ It is one of the core steps of problem-solving which decides what action should be taken to
achieve the formulated goal. Instead of focusing on minor details like "turn steering wheel," it
focuses on driving between major cities like City A→ City D → City B.
❖ Well defined problems and solutions:
• Formulating Problems in AI
Formulating a problem means defining the problem in a structured way
that a problem-solving agent can process. This involves:

✓ Initial State: The starting point of the agent.

Example: The agent is in "City A" and needs to travel to "City B."
✓ Actions: The set of actions the agent can take from each state.
Example: From "City A," the agent can drive to "City C" or "City D."
✓ Transition Model: Defines how actions change the state. Transition The initial state, the actions and the
model is specified by a function RESULT(s, a) that returns the state transition model together define the state
that results from doing action ‘a’ in state ‘s’. e.g. space of the problem i.e. the set of all
RESULT(In(Oradea),Go(Zerind)) = In(Zerind) . states reachable by any sequence of
actions. Figure is the graphical
Example: If the agent drives to "City C," the new state becomes "In City C." representation of the state space
✓ Goal Test: A condition that checks if the goal is achieved. representation of the traveling problem.
Example: The agent is "In City B." The state space forms a graph in which
✓ Path Cost: A measure of how costly a path is, helping choose the best the nodes are states and the links between
nodes are actions. A path in the state
one. space is a sequence of states connected
Example: The shortest or fastest route to the goal. by a sequence of actions.
❖ Problem-Solving Process :
• Steps in Problem Solving:
1. Formulate: Define the problem with the
initial state, goal, actions, etc.
2. Search: Use search algorithms to find a
sequence of actions.
• Example: Breadth-first search, Depth-first
search.
3. Execute: Carry out the planned actions step
by step.
•Example:
➢ An agent finds the shortest path from City A
to City B using a map and then follows it
exactly.
❖ 8 puzzle problem :
• What is the 8-Puzzle Problem?
❑ A 3x3 sliding tile puzzle with 8 numbered tiles and one blank space.
❑ Goal: Rearrange tiles from an initial configuration to match a goal configuration.
• Problem Formulation:
1. State: Position of all tiles and the blank space.
2. Actions: Move blank space up, down, left, or right.
3. Transition Model: Resulting state after an action (e.g., swapping blank space with an
adjacent tile).
4. Goal Test: Check if the current state matches the goal state.
5. Path Cost: Each move costs 1.
❖ 8 queens problem :
• What is the 8-Queens Problem?
➢ Place 8 queens on a chessboard such that no
two queens attack each other
• Constraints: No two queens in the same row,
column, or diagonal.
• Problem Formulation:
1. State: Placement of queens on the board.
2. Actions: Place a queen in a valid position in
the next row.
3. Transition Model: Add a queen to the board
while maintaining constraints.
4. Goal Test: All 8 queens placed without
conflicts.
5. Path Cost: Not typically relevant, as it’s a
constraint satisfaction problem.
19

Vacuum world (vacuum cleaner)

as a Problem solving agent in AI
© Dr. Dafda
❖ Example problems:
✓ Toy problems
⚫ those intended to illustrate or exercise
various problem-solving methods
⚫ E.g., vacuum cleaner, puzzle, chess, etc.

✓ Real-world problems
⚫ tend to be more difficult and whose
solutions people actually care about
⚫ E.g., Design, planning, etc.
❖ Toy problems
❑ Example: Vacuum world
The agent is in one of two locations, each of
which might or might not contain dirt. Therefore,
there are 2 x 2² = 8 possible world states.

✓ Number of states: 8
✓ Initial state: Any
✓ Number of actions: 4
▪ left, right, suck, noOp
✓ Goal: clean up all dirt
▪ Goal states: { state 7, state 8 }.
✓ Path Cost:
▪ Each step costs 1
❖ Vacuum World problem example:
1. Initial state: Any state can be designated as initial state.
2. Actions: Each state has just three actions: Left, Right, and Suck. The complete state space is shown in this figure.
3. Transition model: 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. transition is given by successor
function RESULT(s, a).
4. Goal Test: This checks whether all the squares are clean.
5. Path cost: Each step costs 1, so that the the path cost is the number of steps in the path.
❖ Vacuum World State Space:
 20

The 8 puzzle problem

as the Problem solving agent in AI
(problem formulation steps)
© Dr. Dafda
❖ The 8-puzzle problem:
1. An 8-puzzle consists of a 3x3
board with eight numbered tiles and
a blank space.
2. A tile adjacent to the blank space
can slide into that space. The
objective is to reach the specific
goal state, as shown in figure.
3. In the figure, our task is to
In the above figure, our task is to convert the Initial(Start)
convert the Initial state into goal state into Goal state by sliding digits into the blank space
state by sliding digits into the blank
space.
❖ The problem formulation of the 8-puzzle problem:
▪ States:
It describes the location of each numbered tiles and the
blank tile.
1. Initial State:
Here the Initial state is given {(1,2,3), ( _ ,4,6), (7,5,8)}.
2. Actions:
Movements of the blank space Left, Right, Up, or Down.
Different subsets of these are possible depending on where
the blank is.
3. Transition model:
It returns the resulting state as per the given state and actions.
4. Goal test:
It identifies whether we have reached the correct goal-state.
5. Path cost:
The path cost is the number of steps in the path where the
cost of each step is 1.
21

The 8 queens problem as the

Problem solving agent in AI
(problem formulation steps)
© Dr. Dafda
❖ The 8 queens problems:
• The goal of 8-queens problem is to place 8 queens on
the chessboard such that no queen attacks any other. (A
queen attacks any piece in the same row, column or
diagonal).
• An Incremental formulation involves operators that
augments the state description,starting with an empty
state. For 8-queens problem,this means each action adds
a queen to the state.
• A complete-state formulation starts with all 8 queens on
the board and move them around.
• In either case the path cost is of no interest because only
the final state counts. For each action path cost will be 1.
So default is 8(but it will be varied based on the number
of iterations to take to complete the problem.
❖ The problem formulation of the 8 queens problems:
There are two ways to formulate the problem:
(1) Incremental formulation:
States: Any arrangement of 0 to 8 queens on board is a state.
a. Initial state: No queen on the board.
b. Action: Add a queen to any empty square.
c. Transition model: It returns the resulting state as per the given state and actions.
d. Goal Test: 8 queens are on the board, none attacked.
e. Path cost: The path cost is of no interest because only the final state counts.
In this formulation, there are 3 x 1014 possible sequences to investigate.
(2) Complete-state formulation
A better formulation would prohibit placing a queen in any square that is already attacked.
States: Arrangements of n queens ( 0 <= n < = 8 ) ,one per column in the left most columns ,with no queen attacking
another are states.
a. Initial state: All 8 queens on the board.
b. Action: Add a queen to any square in the left most empty column such that it is not attacked by any other queen.
c. Transition model: It returns the resulting state as per the given state and actions.
d. Goal Test: 8 queens are on the board, none attacked.
e. Path cost: The path cost is of no interest because only the final state counts.
This formulation reduces the 8-queen state space from 3 x 1014 to just 2057,and solutions are easy to find.
❖ The 8 queens problems one possible solution:
22

The Real World problems in AI

(Problem solving agents)
© Dr. Dafda
❖ Real World Problems:
• A real world problem is one whose solutions people actually care about.
• They tend not to have a single agreed upon description, but attempt is
made to give general flavor of their formulation.
• The following are the some real world problems,
a. Route Finding Problem
b. Touring Problems
c. Travelling Salesman Problem
d. VLSI Layout design
e. Robot Navigation
f. Automatic assembly sequencing
g. Internet searching etc.
❖ Route-Finding Problem:
• Consider the airline travel problem that must be solved by a travel-planning web
site:
• States: Each state includes a location and the current time.
(1) Initial state: This is specified by the user’s query.
(2) Actions: Take any flight from the current location, in any seat class, leaving
after the current time, leaving enough time for within-airport transfer if needed.
(3) Transition model: The state resulting from taking a flight will have the flight’s
destination as the current location and the flight’s arrival time as the current
time.
(4) Goal test: Are we at the final destination?
(5) Path cost: This depends on monetary cost, waiting time, flight time, seat
quality etc.
❖ Touring Problem:
1. Initial State:
The agent starts in Bucharest. The set of visited cities initially contains only Bucharest.
Example: (Current city: Bucharest, Visited cities: {Bucharest})
2. Actions:
The agent can travel to any adjacent city based on the map of Romania. Each action
represents moving from the current city to a directly connected neighboring city.
Example: From Bucharest, the agent can move to cities like Pitesti, Giurgiu, or Urziceni.
3. Transition Model:
When the agent moves from city X to city Y, the current city updates to Y, and Y is
added to the set of visited cities.
Example: If the agent moves from Bucharest → Urziceni → Vaslui, the new state is
(Current city: Vaslui, Visited cities: {Bucharest, Urziceni, Vaslui}).
4. Goal Test:
The agent must check whether it is back in Bucharest and has visited all 20 cities at least
once.
Example: If the visited set contains all cities in Romania and the agent is in Bucharest,
the goal is achieved.
5. Path Cost:
The cost is typically calculated as the total travel distance, time, or another metric (e.g.,
fuel usage). A standard cost function could sum the road distances traveled between
cities.
Example: If the agent moves along a path of 1000 km total, the path cost is 1000.
❖ The Travelling Salesperson Problem (TSP):

1. Initial State:
The agent starts at a specific city (e.g., City A). The set of visited cities initially contains only the starting city.
Example: (Current city: A, Visited cities: {A})
2. Actions:
The agent can travel to any unvisited city. Each action corresponds to moving from the current city to an unvisited city.
Example: If the agent is in City A, and B, C, and D are unvisited, the possible actions are: Move(A → B), Move(A → C), Move(A
→ D).
3. Transition Model:
When the agent moves from city X to city Y, the new state updates as: Current city becomes Y. Y is added to the set of visited cities.
Example: If the agent moves from A → B → C, the new state is: (Current city: C, Visited cities: {A, B, C})
4. Goal Test:
The goal is reached when: All cities have been visited exactly once, and The agent returns to the starting city.
Example: If there are 5 cities {A, B, C, D, E}, a valid goal state would be: (Current city: A, Visited cities: {A, B, C, D, E})
5. Path Cost:
The path cost is the total distance traveled (or another measure like time or fuel usage). The objective is to minimize this cost.
Example: If the agent follows the route A → B → C → D → E → A and the total distance is 500 km, the path cost is 500.
❖ VLSI layout:
1. Initial State:
Empty chip with no placed components or routed connections.
2. Actions:
Place components at valid positions.
Route connections between components.
Adjust placement to optimize space and minimize wire congestion.
3. Transition Model:
Each action updates the layout by modifying placements and routing.
Ensures no component overlap and minimal delay.
4. Goal Test:
All components are placed and connected with minimal area and delay.
No overlap, minimal capacitance, and high manufacturing yield.
5. Path Cost:
Cost = Area Used + Wire Length + Signal Delay + Capacitance (minimized).
👉 Objective: Efficient component placement & routing for optimal chip performance.
❖ Robot Navigation:
1. Initial State:
Robot starts at (x₀, y₀) with orientation θ.

2. Actions:
Move in any direction, rotate, or adjust arms/wheels if applicable.

3. Transition Model:
Updates position (x, y, θ) based on movement and avoids obstacles.

4. Goal Test:
Robot reaches the target position while avoiding obstacles.

5. Path Cost:
Minimize distance, energy, and time for optimal navigation.
👉 Objective: Efficient movement in continuous space while avoiding obstacles.
❖ Automatic Assembly sequencing:
1. Initial State: All parts unassembled, no
connections made.
2. Actions: Attach parts in a valid order to avoid
conflicts.
3. Transition Model: Each step updates the
assembly, ensuring correctness.
4. Goal Test: Full assembly completed without
errors or missing parts.
5. Path Cost: Minimize steps, errors, material
waste, and time.
👉 Objective: Efficiently assemble components in
the correct sequence.
❖ Internet Searching:
1. Initial State:
Start at a given webpage (node) or a search query input.
2. Actions:
Follow hyperlinks to connected pages. Refine the search query or extract relevant
content.
3. Transition Model:
Moving from one page (node) to another through links. Updating search results
based on relevance and ranking.
4. Goal Test:
Desired information is found or query conditions are met.
5. Path Cost:
Minimize number of visited pages, loading time, and irrelevant searches.
👉 Objective: Efficiently find relevant information on the internet using minimal
resources.
 23

Searching for Solutions in AI

© Dr. Dafda
❖ Example problems:
✓ Toy problems
⚫ those intended to illustrate or exercise
various problem-solving methods
⚫ E.g., vacuum cleaner, puzzle, chess, etc.

✓ Real-world problems
⚫ tend to be more difficult and whose
solutions people actually care about
⚫ E.g., Design, planning, etc.
❖ The Concept of Search in AI:
• A solution in AI is an action sequence that
leads from an initial state to a goal state.
• Search algorithms generate and evaluate
action sequences to find solutions.
•The search tree is formed with:
• The initial state as the root node
• Actions as branches
• Resulting states as nodes
❖ Expanding Nodes in a Search Tree:

•Expansion: Generating new states from a

current state.
•Parent Node: The original state before
expansion.
•Child Node: The resulting states after
applying an action.
•Example: Expanding the state In(Arad)
results in In(Sibiu), In(Timisoara), and
In(Zerind).
•Choosing which node to expand next is
the essence of search.
❖ The Frontier and Leaf Nodes:
• Leaf Node: A node with no children in
the search tree.i.e. that hasn’t been
expanded yet.
• Frontier: The set of all leaf nodes
available for expansion.
• The frontier determines the next step in
the search.
• Some algorithms call the frontier the
open list (less accurate term).
• In figure(c), cities Arad, Fagaras,
Oradea, RimnicuVilcea, Timisoara or
Zerind are the Frontiers in the Search
Tree.
❖ Tree-Search Algorithm :

•The TREE-SEARCH algorithm expands

nodes until a solution is found.
•The basic steps:
1. Start at the initial state (root node).
2. Expand a node from the frontier.
3. Check if it is the goal.
4. If not, add its child nodes to the frontier.
5. Repeat until a solution is found or no
nodes remain.
❖ Repeated States and Loopy Paths :

•Repeated State: A state that appears

multiple times in a search tree.
•Loopy Path: A path that returns to the
same state repeatedly.
•Loops make the search tree infinite, even if
the state space is finite.
•Example: Arad → Sibiu → Arad creates a
loop.
•Loopy paths waste time and computational
resources.
❖ Redundant Paths in Search :

•Redundant Path: An inefficient way

to reach a state.
•Example:
•Arad → Sibiu (140 km)
•Arad → Zerind → Oradea →
Sibiu (297 km)
•The second path is redundant.
•Redundant paths increase search
complexity unnecessarily.
❖ Avoiding Redundant Paths :
•Some problems can be reformulated to
eliminate redundancy.
•Example: 8-Queens problem
•Allowing any column: n! different
paths.
•Restricting to leftmost empty column:
only one path per state.
•Some problems (e.g., route-finding) must
deal with redundancy.
•For example in this figure, the white
nodes seperates the explored black nodes
from the search.
❖ Graph-Search Algorithm:
•Graph-Search Algorithm avoids
redundant paths by maintaining an
explored set.
•Explored Set (Closed List): Keeps track
of visited states to prevent repetition.
•Steps:
1. Expand a node from the frontier.
2. Check if it is in the explored set.
3. If yes, discard it; if no, add it to the set
and expand it.
• Ensures each state appears only once in
the search tree.
❖ Conclusion :

•Searching for solutions involves:

➢ Expanding nodes in a search tree.
➢ Managing the frontier and choosing nodes strategically.
➢ Avoiding loopy paths and redundant paths.
• Using Graph-Search to prevent unnecessary exploration.
•Efficient search techniques improve AI problem-solving capabilities.
24

Infrastructure for search algorithms

in AI
© Dr. Dafda
❖ Components of a Search Tree Node:
• Each node n of the tree, in the search
tree has four components:
1. [Link]: Represents the
corresponding state in the state space.
2. [Link]: References the node that
generated this node.
3. [Link]: Action taken from the
parent node to generate this node.
4. [Link]-COST: Cost, g(n), from the
initial state to this node.
❖ Storing and Extracting Search Paths

• Parent pointers link nodes into a tree

structure.
• SOLUTION function extracts the
solution path by following parent
pointers to the root.
• Difference between nodes and states:
✓ Nodes represent specific paths in
the search tree.
✓ States are problem configurations,
not tied to a specific path.
❖ Data Structures for Storing Nodes:
• To implement search, we need to store and manage nodes efficiently. The
frontier stores nodes yet to be expanded.
• We use different types of queues to determine how nodes are expanded:
⚫ FIFO Queue (First-In-First-Out): Expands oldest nodes first (used in BFS).

⚫ LIFO Queue (Last-In-First-Out): Expands newest nodes first (used in DFS).

⚫ Priority Queue: Expands nodes based on priority function (used in A*

Search).
• These queues are implemented using standard operations like:
⚫ EMPTY?(queue): Checks if the queue is empty.

⚫ POP(queue): Removes and returns the first element.

⚫ INSERT(element, queue): Adds an element to the queue.

❖ Explored Set and Avoiding Redundant Paths:
• The explored set prevents expanding the same state multiple times, reducing
redundant computation.
• A hash table is used for efficient lookup and insertion, ensuring fast operations.
• Canonical Form ensures logically equivalent states map to the same data
structure.
• Example: {Bucharest, Urziceni, Vaslui} = {Urziceni, Vaslui, Bucharest} in the
Traveling Salesperson Problem. Without a canonical form, the same set of cities
could be stored differently as:
✓ {Bucharest, Urziceni, Vaslui}
✓ {Urziceni, Vaslui, Bucharest}
• Even though they represent the same visited cities, they might be mistakenly
considered different states, leading to redundant processing.
25

Measuring problem-solving
performance in AI
© Dr. Dafda
❖ Criteria for Evaluating Search Algorithms:

• To compare and choose among search algorithms, we evaluate them

based on:
1. Completeness: Does it guarantee finding a solution if one exists?
2. Optimality: Does it find the best solution?
3. Time Complexity: How long does it take to find a solution?
4. Space Complexity: How much memory does it use?
❖ Understanding Time and Space Complexity:
• Complexity is measured relative to the problem difficulty.
• In theoretical computer science:
⚫ State space graph size = |V| + |E|, where V = vertices (nodes) & E = edges
(links).
• In AI, complexity depends on:
⚫ b: Branching factor(how many child nodes each node generates).

⚫ d: Depth(steps needed to reach the nearest goal).

⚫ m: Maximum path length(longest possible solution path).

• Time Complexity = Number of nodes generated.
• Space Complexity = Maximum number of nodes stored in memory.
❖ Search Cost vs. Total Cost:
• Search Cost = Time + Memory used during search.
• Total Cost = Search Cost + Path Cost of the final solution.
• Example: Finding a route from Arad to Bucharest:
⚫ Search Cost = Computation time to find the path.
⚫ Solution Cost = Distance traveled in km.
⚫ Total Cost = Time taken to compute + Distance of the route.
❖ Conclusion – Why Measuring Performance Matters?
• Choosing the right search algorithm depends on performance evaluation.

• We assess completeness, optimality, time, and space complexity.

• Tradeoffs are common—some algorithms are fast, others are memory-

efficient or find better solutions.

• Understanding performance helps design smarter and more efficient AI

agents.