Foundations

Artificial Intelligence
Module 2 AI Problem Solving

Unit 7 Problem Solving Agents (Concept Only), Examples

Problems: Toy problems, Real world problems
Problem-Solving Agent

A problem-solving agent is a type of goal-based intelligent agent in Artificial

Intelligence. It is designed for situations where the agent has a specific goal to
achieve and must plan a sequence of actions to reach that goal.
The agent operates by searching through possible actions and future states to decide
the most suitable actions that will lead it toward achieving the goal efficiently. This
makes problem-solving agents smarter and more flexible.

The three main phases are:

1. Goal Formulation
2. Problem Formulation
3. Search and Execution

Goal Formulation
Goal formulation is the process of defining the desired outcome an agent should
achieve, based on its current situation and performance measure. It sets a clear target,
allowing the agent to focus only on actions that lead to the goal. It’s the first and
most crucial step in problem-solving, guiding all decisions the agent makes.

Example:
An agent in Kozhikode with a flight from Thiruvananthapuram at 8 PM formulates
the goal:
“Reach Thiruvananthapuram before 7:30 PM”.
Now it ignores other activities and plans city-to-city travel routes.

Importance of Goal Formulation:

• It simplifies decision-making by removing irrelevant actions.
• It allows the use of search algorithms to plan a solution.
• It helps in designing efficient, intelligent agents that act purposefully.
• Without goal formulation, an agent would waste time exploring everything
and achieve nothing useful.
Problem Formulation

Problem formulation is the process of turning a general goal into a clear and well-
organized problem that an agent can solve step by step. It decides what the agent
should treat as its current state, what actions it can take, what happens after each
action, how to check if the goal is reached, and how to compare different ways to
reach the goal. This makes it easier for the agent to plan and choose the best path,
instead of guessing randomly. In short, problem formulation converts a vague goal
into a clear problem with simple rules, actions, and conditions for success.

Abstraction is the process of removing unimportant details and keeping only the
information that matters for solving a problem. In real-life situations, there are so
many extra details that, if considered, would make problem-solving very difficult
and confusing. So, to make it easier, we focus only on the things that affect the
outcome and ignore the rest.
Example:
When planning a route from Kozhikode to Thiruvananthapuram:
• You care about roads and distances.
• You ignore things like the color of road signs, songs playing in the car, or
cloud patterns.

5 Components of Problem Formulation

To solve a problem, an agent needs a clear and structured way to plan its actions.
This is done by defining the problem using five important components. These
components help the agent understand where it starts, what it can do, what happens
after each action, how to check if the goal is reached, and how to compare different
possible solutions.
1. Initial State
The initial state is the starting point of the agent before it begins solving the
problem. It describes the current situation of the agent in the environment. From
this state, the agent will decide which actions to take next. It marks the beginning
of the agent’s search for a solution.
2. Actions
Actions are the possible moves or operations the agent can perform from a
particular state. Each action changes the current state and moves the agent closer
to or further from the goal. The list of available actions depends on the current
state. Problem formulation should clearly mention all possible actions for every
state.
3. Transition Model
The transition model defines what happens when an action is performed in a
given state. It explains how the state changes and what the resulting new state
will be after taking an action. This helps the agent understand the effects of its
actions. It is necessary for predicting future states while planning.
4. Goal Test
The goal test checks whether the agent has reached its desired goal state. It is a
condition or rule that determines if the problem has been successfully solved.
Every time the agent reaches a new state, it applies the goal test to see if the task
is complete. The problem formulation must clearly define this condition.
5. Path Cost
The path cost is a numeric value assigned to each path that the agent can follow.
It helps in comparing different possible paths and selecting the best one. The path
cost could be based on distance, time, money, or any other measurable factor. A
good problem formulation includes a cost function to guide the agent toward an
efficient solution.
Example
Goal: Reach Thiruvananthapuram from Kozhikode.
• Initial State: In(Kozhikode)
• Actions: {Go to Thrissur, Go to Ernakulam, Go to Alappuzha, Go to
Thiruvananthapuram}
• Transition Model:
o Result(In(Kozhikode), Go to Thrissur) = In(Thrissur)
o Result(In(Ernakulam), Go to Alappuzha) = In(Alappuzha)
• Goal Test: Is the agent in Thiruvananthapuram?
• Path Cost: Sum of distances in kilometers or travel time in hours.

Search and Execution

Search is the process where an intelligent agent looks for a sequence of actions that
will lead it from the initial state to the goal state. Once the problem is well-
formulated with its states, actions, transitions, goal test, and path cost, the agent uses
a search algorithm to explore possible paths and find a solution. After a suitable
action sequence is found, the agent moves to the Execution phase. In this phase, the
agent performs the actions one by one in the real environment, following the plan
made during the search, until it successfully reaches the goal state.
EXAMPLE PROBLEMS

In AI, problems are broadly categorized based on their nature and usage.
There are two main types of problems in problem-solving approaches.
1. Toy Problems
2. Real-World Problems.

Toy Problems
Toy problems are small, simple, and well-defined problems used in Artificial
Intelligence to test and practice different problem-solving methods. These problems
have a clear description, limited number of states, and fixed rules. They are specially
designed for learning purposes, demonstrations, and comparing the performance of
different algorithms. Since they are easy to understand and solve, researchers use
toy problems to explain concepts before applying them to bigger, real-world
problems.
common toy problems used in AI:
• Vacuum World Problem
• 8-Puzzle Problem
• 8-Queens Problem
• Water Jug Problem
Vacuum World Problem
The Vacuum World Problem is a simple AI problem where a vacuum cleaner acts
as an agent inside a small room. The room usually has two locations (like A and
B), and each location may either be clean or dirty. The agent can sense whether its
current location is dirty or clean and perform actions to clean it.

• States: The state of the world is defined by the position of the vacuum
cleaner (either in location A or B) and the clean/dirty status of both
locations, there are 8 possible states.
• Actions: The agent can move Left, move Right, or Suck the dirt from its
current position.
• Transition Model: Describes how the world changes after each action. For
example, if the vacuum is at A and performs ‘Suck’, then location A
becomes clean.
• Goal Test: The agent must clean both locations. The test checks whether
both squares are clean.
• Path Cost: Every action (move or suck) has a cost of 1 unit. The total cost is
the number of actions taken.
8-Puzzle Problem
The 8-Puzzle is a sliding puzzle with a 3×3 board containing 8 numbered tiles and
1 blank space.
The goal is to move the tiles by sliding them into the blank space and reach a final
target arrangement.
• States: Positions of 8 tiles and 1 blank space.
• Initial State: Any starting arrangement.
• Actions: Move the blank Left, Right, Up, or Down (if possible).
• Transition Model: Moving a tile changes its position with the blank.
• Goal Test: Check if the current arrangement matches the goal arrangement.
• Path Cost: Each move costs 1 step.

8-Queens Problem
The goal is to place 8 queens on a chessboard so that no two queens can attack
each other. A queen can attack in the same row, column, or diagonal.
Components:
• States: Any arrangement of 0 to 8 queens on the board.
• Initial State: No queens on the board.
• Actions: Place a queen in an empty square (or in better versions — in a safe
square only).
 • Transition Model: After placing a queen, the board updates with the new
position.
• Goal Test: When 8 queens are on the board without attacking each other.
• Path Cost: Not important — only the final state matters.

Real-World Problems

These are problems people actually care about in real life. They are usually more
complex, unpredictable, and lack a single standard description. Real-world problems
involve many factors like uncertainty, incomplete information, and changing
conditions. They often require smart decisions in difficult situations, where things
don’t always go as planned. Solving these problems helps in areas like travel,
medicine, factories, and robotics.
Common Real-World Problems
• Route-Finding Problem
• Travel Planning (Airline Travel Problem)
• Touring Problem
• Travelling Salesperson Problem (TSP)
• VLSI Layout Problem
• Robot Navigation Problem
• Automatic Assembly Sequencing
• Protein Design Problem

Route-Finding Problem
This problem involves finding the best way to travel from one place to another. The
system needs to know the starting location, possible routes, and what happens when
a particular route is taken. It must also check whether the destination is reached and
calculate the cost of the journey based on time, distance, or traffic. Such systems
help people and vehicles plan efficient, safe, and fast routes.
Example: Finding the fastest way to travel from Kozhikode to Ernakulam while
avoiding traffic.

Airline Travel Problem (Travel Planning)

This problem focuses on helping users plan air travel by selecting suitable flights
based on different conditions. The system checks available flights, their timings,
prices, connections, seat types, and additional factors like customs or waiting time
between flights. It must plan routes that fit the user’s schedule and budget while
ensuring proper transfer times and travel rules.
Example: Booking a flight from Kochi to Delhi via Mumbai, ensuring a minimum
1-hour gap between flights.

Touring Problem
The touring problem requires visiting a list of places at least once and returning to
the starting point. The system keeps track of which places have already been visited
and which are left. It then plans a route to visit all cities in a convenient order. The
aim is to make sure every location is covered before returning to the starting point.
Example: Planning a trip to Kozhikode, Kochi, Kottayam, and Trivandrum and
returning to Kozhikode.

Travelling Salesperson Problem (TSP)

This is a special type of touring problem where each city or location must be visited
exactly once before returning to the start. The challenge is to find the shortest
possible route that covers all cities without revisiting any of them. TSP is widely
used in delivery services, logistics, and transport route planning where time and
distance optimization is important.
Example: A courier delivering parcels to 10 different homes without repeating any
stop.

VLSI Layout Problem

Used in computer chip design, this problem involves arranging electronic
components on a small chip without overlapping. The system also ensures enough
space is left for the wires (connections) between components. The goal is to design
a chip that’s compact, efficient, and works properly while avoiding wiring issues.
Example: Arranging parts of a mobile phone processor on a microchip without any
part colliding or blocking connections.

Robot Navigation Problem

This problem involves moving a robot in a physical or virtual environment while
safely avoiding obstacles and reaching a target. Unlike route-finding, robots move
in continuous open space and may also need to rotate, lift, or adjust their actions
based on the environment. The challenge is higher due to sensor errors,
unpredictable surroundings, and the continuous nature of robot movement.
Example: A robot vacuum cleaner moving through a house, avoiding furniture and
cleaning every corner.

Automatic Assembly Sequencing

In this problem, a system must decide the correct order for assembling the parts of a
product. If parts are assembled in the wrong order, it might be impossible to add the
remaining parts without removing earlier ones. The system must check whether each
step is possible and plan a sequence that avoids mistakes.
Example: Assembling a bike, where the wheels should be fixed after placing the
frame, but before attaching the seat.

Protein Design Problem

This problem appears in biotechnology and medical research where AI systems help
create new proteins. Proteins are made from sequences of amino acids, and the AI
must find a sequence that folds into the desired 3D shape with the right properties to
treat a disease. The challenge lies in predicting how a sequence will fold and whether
it will work effectively.
Example: Designing a protein to act as a medicine for controlling blood sugar in
diabetic patients.