Problem Solving Agents

A problem-solving agent is a type of AI that is built to solve problems by

trying out different steps or actions. It works like this:

• It has a clear goal (what it needs to achieve).

• It looks at all the possible actions it can takes.
• It chooses the best steps to reach the goal.
• It works in a well-defined environment (it knows the rules, the goal,
and the available actions)
Maze Solver Example:
Imagine a robot in a maze:
•The goal is to reach the exit.
• It knows what directions it can move (left, right, forward, back).
• It tries different paths, avoids dead ends, and finds the correct way out.
That robot is acting like a problem-solving agent.

A problem-solving agent is like a smart robot that thinks step-by-step to solve a problem and reach
its goal, using a plan and knowledge of the environment.
Steps Performed by a Problem-Solving Agent
A problem-solving agent typically follows a sequence of steps to identify and execute the best solution to a
problem. These steps include:
1. Formulating the Problem: The agent begins by defining the problem it needs to solve. This involves
specifying the initial state, goal state, actions, and state space.
 Initial State: The starting point or current situation of the agent.
 Goal State: The desired situation the agent aims to reach.
 Actions/Operators: The possible actions the agent can take to move from one state to another.
 State Space: The set of all possible states reachable from the initial state by applying the available
actions.
2. Formulating the Goal: Clearly define the objective the agent aims to achieve.
• The agent defines the goal that it needs to achieve. The goal is often represented as a specific
state or a set of criteria that the solution must satisfy.
• Example: In a navigation problem, the goal might be to reach a particular destination.
3. Exploring the State Space: It defines the objective the agent aims to achieve.
o The agent explores the state space to identify possible paths from the initial state to the goal state. This
involves considering all possible actions at each state and determining which paths lead closer to the
goal.
o Search Strategies:
 Uninformed Search: No additional information about the problem (e.g., breadth-first search,
depth-first search).
 Informed Search: Uses heuristics or additional knowledge to guide the search (e.g., A* algorithm).
4. Choosing a Solution Path: Evaluate and select the most efficient path to the goal.
o The agent evaluates the different paths it has explored and selects the one that leads to the goal in the
most efficient manner. This path is the solution to the problem.
o Evaluation Criteria:
 Cost: The total cost or resources required to reach the goal (e.g., time, distance).
 Efficiency: The speed or efficiency of the path to the goal.
5. Executing the Solution: Perform the actions to reach the goal.
o Once the best path is chosen, the agent executes the sequence of actions that lead from the initial
state to the goal state. The agent carries out these actions in the environment to achieve the desired
outcome.
o Monitoring: The agent may need to monitor progress and make adjustments if the environment
changes or if unexpected obstacles are encountered.
6. Learning and Improvement (Optional): Reflect on the process to improve future problem-solving.
o Some problem-solving agents are capable of learning from their experiences. After solving the
problem, the agent may analyse its performance to improve future problem-solving efforts. This could
involve refining its heuristics or updating its knowledge base.
When dealing with problem-solving in artificial intelligence (AI), problems are often categorized into two types
based on their complexity and real-world relevance: Toy Problems and Real-World Problems.
1. Toy Problems : Toy problems are simple, clear, and small problems used by researchers and students to test
and understand AI algorithms. They are not real-world problems but are helpful for learning and practicing
how AI works.
Feature Explanation
Easy to understand with limited options and
Simplicity
actions.
The rules, starting point, and goal are very
Well-Defined Rules
clear.
Can be easily written as a math problem or
Easy to Model
simple program.
Useful for testing algorithms and solving
Great for Learning
methods.
No Real-World Mess No noise, uncertainty, or real-life complexity.
Example 8 puzzle problem, 8 Queens problem
 Toy Problems is used to:
•To compare different algorithms
•To learn problem-solving techniques
•To experiment in a safe, simple setting
Toy Problem Description
A 3x3 tile puzzle with 8 numbered tiles and 1 empty
space. The goal is to slide tiles and arrange them in
8-Puzzle order.

A 3x3 grid game where two players try to make a line

Tic-Tac-Toe of 3 marks (X or O).

Move disks between rods following rules to achieve a

Tower of Hanoi goal setup.

A simplified chess setup with fewer pieces to test

Chess Endgame
specific strategies or moves.
Example 1: 8 Puzzle problem
Allowed Moves
The blank space can be moved horizontally or vertically by swapping it with an adjacent tile. The possible moves are:
• Up: Move the blank space up by swapping it with the tile above.
• Down: Move the blank space down by swapping it with the tile below.
• Left: Move the blank space left by swapping it with the tile to the left.
• Right: Move the blank space right by swapping it with the tile to the right.
Problem Formulation
State Space:
o It describes the location of each numbered tiles and the blank tile.
o Each configuration of the puzzle is a unique state. The total number of possible states in the 8-puzzle is 9! (9 factorial),
but only half of these are solvable, so there are 9!/2 = 181,440 possible solvable states.
Initial State:
o This is the starting configuration of the tiles. We can start from any state as initial state.
Goal State:
o The state in which all tiles are in the correct order, with the blank space in the bottom-right corner.
Actions:
o The possible moves of the blank space (Up, Down, Left, Right).
Transition Model:
o The result of applying an action to a state, leading to a new state.
Path Cost:
o The cost of a path from the initial state to the goal state, typically measured as the number of moves made (with each
move having a cost of 1).
Solving the 8-Puzzle Problem
The 8-puzzle problem is often solved using search algorithms, such as:
Breadth-First Search (BFS):
o Explores all nodes at the present depth level before moving on to nodes at the next depth level. BFS is
guaranteed to find the shortest path to the goal state, but it can be memory-intensive.
Depth-First Search (DFS):
o Explores as far down a branch as possible before backtracking. DFS uses less memory but can get stuck
in deep branches and may not find the shortest solution.
A Search*:
o A* is a heuristic search algorithm that combines the cost to reach a node (g(n)) and the estimated cost
from that node to the goal (h(n)). A* is efficient and guarantees finding the optimal solution if the
heuristic is admissible.
Example 2: 8-Queens Problem
The 8-Queens Problem is a classic puzzle in Artificial Intelligence and computer science.

Goal: Place 8 queens on a standard 8×8 chessboard in such a way that no two queens attack each other.
Queens can attack:
Vertically (same column),
Horizontally (same row),
Diagonally.
So, the challenge is to place all 8 queens so that none share the same row, column, or diagonal.
Two Ways to Solve It: Formulations
There are two main formulations or ways to design the problem for a computer to solve:

1. Incremental Formulation
Start with an empty board and add one queen at a time in a safe place, step by step.
Steps:
• Start with an empty chessboard.
• Place the first queen in a safe position (e.g., row 1).
• Go to the next row and place another queen in a spot that doesn't conflict with
the previous queen(s).
• Keep going until all 8 queens are placed without conflict.
• If you get stuck, go back (backtrack) and try a different position.
Complete-State Formulation

Start with all 8 queens already on the board, one in each row (or column), and then
move them around to make the board safe.
Steps:
• Place 8 queens on the board (one per row), but not necessarily in safe spots.
• Check how many pairs of queens are attacking each other.
• Use a method like hill climbing to move queens to reduce the number of
conflicts.
• Keep adjusting until there are no conflicts left.
• If stuck in a bad position (local maximum), you might need to restart or use
random moves.

Both methods aim to reach a goal state where all 8 queens are placed safely — no
two attacking each other. The incremental approach builds the solution, while the
complete-state approach adjusts until it's correct.
2. Real-World Problems
Real-world problems are complex, practical problems encountered in everyday life or specific industries. These
problems are typically much more challenging to solve because they involve large state spaces, uncertain
environments, incomplete information, and multiple interacting factors.
Characteristics of Real-World Problems:
 Complexity: Real-world problems often involve many variables, large state spaces, and a wide range of
possible actions.
 Uncertainty: The environment may be dynamic and unpredictable, with incomplete or noisy data.
 Realistic Constraints: These problems often involve constraints like time, resources, and real-world physical
limitations.
 High Stakes: The outcomes of real-world problems can have significant consequences, making accurate
and efficient problem-solving critical.
 Interdisciplinary: Solving real-world problems often requires knowledge from multiple disciplines (e.g.,
engineering, economics, psychology).
Examples of Real-World Problems:
 Self-Driving Cars: Navigating complex environments with unpredictable elements like pedestrians, traffic,
and road conditions.
 Medical Diagnosis: Analyzing patient data to diagnose diseases, where the information might be
incomplete or uncertain.
 Supply Chain Optimization: Managing logistics and supply chain networks with varying demands, resources,
and constraints.
 Robotic Navigation: Enabling robots to move and perform tasks in dynamic, unstructured environments
(e.g., disaster areas, homes).
 Natural Language Processing: Understanding and generating human language in a way that is contextually
accurate and meaningful.
Real world problem Examples:
1. Travelling Salesman Problem (TSP)
The Travelling Salesman Problem (TSP) is a classic optimization problem in computer science and AI.

Goal: A salesman must visit a list of cities exactly once and return to the starting city, covering the shortest possible
distance.
Why is it important?
• It helps in solving routing problems, like GPS navigation, delivery route planning, and circuit design.
• It becomes difficult to solve as the number of cities increases, making it a combinatorial problem.
• TSP is used to study search and optimization algorithms like: Greedy algorithms, Dynamic programming,
Genetic algorithms A* search
2. VLSI Layout Problems (Very-Large-Scale Integration)
VLSI layout problems deal with how to place and connect millions of components (like transistors) efficiently on a
microchip. It's like solving a 2D puzzle under strict space and performance limits.

1.Cell Layout Problem

Goal: Place all components (cells or modules) on a chip in a way that:
• Uses minimum space
• Minimizes connection lengths
• Avoids overlap
Real-World Example:
Designing the layout of logic gates in a CPU so it’s fast and compact.

2 Channel Routing Problem

Goal: Route the wires between cells without them crossing, using as few layers and channels as possible.
Real-World Example:
Connecting different parts of a chip without causing short circuits or using too much area.
3 Protein Design
Goal: Find a 3D shape (structure) of a protein that results in a stable and functional molecule.
In AI context:
This is like puzzle-solving, where you try to fold a protein chain into a form that:
• Uses least energy
• Matches desired biological function
Used in bioinformatics, drug design, and healthcare AI.

4 Robot Navigation
Goal: Move a robot from start to goal position in an environment full of obstacles, using the shortest and safest
path.
Techniques used:
• Path finding algorithms (A*, Dijkstra’s)
• Sensors and maps (SLAM)
• Machine learning for obstacle avoidance
Real-World Use:
• Vacuum robots (like Roomba)
• Warehouse robots (like Amazon's Kiva robots)
• Self-driving cars
Water Jug Problem
The Water Jug Problem is a simple yet powerful example of how AI can be applied to solve puzzles
using search algorithms.
By representing the problem as a state space and exploring the transitions between states, AI can
find the optimal solution through search techniques like BFS and DFS.
This problem not only teaches fundamental concepts of AI but also provides insights into how AI can
be used to solve more complex resource management issues in real-world scenarios.

You are given:

• One jug X with capacity X liters
• One jug Y with capacity Y liters
• Goal: Measure exactly Z liters using the two jugs
You can:
• Fill a jug completely
• Empty a jug completely
• Pour water from one jug to the other until:
o the first jug is empty, or
o the second jug is full
Let’s take:
 Jug X = 4 liters
 Jug Y = 3 liters
 Goal = 2 liters

Operations You Can Perform

Operation Description
Fill X Fill the 4L jug completely
Fill Y Fill the 3L jug completely
Empty X Empty the 4L jug
Empty Y Empty the 3L jug
Pour X → Y Pour water from X to Y until Y is full or X is empty
Pour Y → X Pour water from Y to X until X is full or Y is empty
Production Rules for Water Jug Problem
Rule No. Condition (WHEN) Action (THEN)
1 Jug X is not full Fill Jug X completely
2 Jug Y is not full Fill Jug Y completely
3 Jug X is not empty Empty Jug X completely
4 Jug Y is not empty Empty Jug Y completely
Pour water from X to Y until Y is
5 Jug X is not empty AND Jug Y is not full
full or X is empty
Pour water from Y to X until X is
6 Jug Y is not empty AND Jug X is not full
full or Y is empty
7 Jug X or Jug Y has exactly Z liters (goal) Stop – Goal is reached
Backtrack or restart from a
8 No valid move left (dead end)
previous state
Note:
 These rules can be used in AI search algorithms like BFS, DFS, or A* to find the solution path.
 Rule 7 is the goal test condition.
 Rule 8 helps implement backtracking in search problems.
Assumptions for the Water Jug Problem

No. Assumption Explanation

1 Both jugs have fixed capacities Jug X = 4 liters, Jug Y = 3 liters (or any defined values).
You can only fill, empty, or pour completely — not
2 Jugs do not have measurement markings
measure partial amounts directly.
You can refill the jugs as many times as needed from
3 Unlimited water supply
an external source.
4 No water is lost during pouring Transfers between jugs are exact — no spillage.
Each action (fill, empty, pour) is considered as one
5 Actions are atomic and instant
complete and discrete step.
You always know the amount of water in each jug at
6 You can see and control the water level
every step.
You know the target volume Z (e.g., 2 liters) before
7 Goal is pre-defined
starting.
The jugs can only hold water up to their Overflow is not allowed; pouring stops when the
8
maximum capacity receiving jug is full.
Steps to Get 2 Liters
At the end of Step 7, Jug X has 2 liters, which is our goal.

Jug X Jug Y
Step Action
(4L) (3L)
1 0 0 Start
2 4 0 Fill X
Pour X → Y (3 from X
3 1 3
to Y)
4 1 0 Empty Y
5 0 1 Pour X → Y
6 4 1 Fill X
Pour X → Y → ✅
7 2 3
GOAL Achieved
Applications of the Water Jug Problem
Although the Water Jug Problem itself is a theoretical puzzle, its principles apply to real-world
problems, such as:
 Managing resources under constraints, like liquid distribution in a refinery or industrial
process.
 Puzzle-solving AI: Similar problems can be found in robotics, where robots must handle tasks
with limited resources and defined constraints.
 Game theory: The problem also serves as a model for certain types of decision-making tasks in
game theory and optimization.