Artificial Intelligence
T.Y. [Link]. (COMPUTER SCIENCE) – SEM V
CHAPTER 4: PROBLEM SOLVING AGENTS
Problem-Solving Agent
A problem-solving agent is a type of goal-based agent that operates by:
• Formulating goals based on its current state.
• Defining problems that need to be solved to achieve those goals.
• Searching for a solution (i.e., a sequence of actions) that leads from the initial state to a goal state.
• Executing the found solution.
Problem-Solving Agent
It works in environments that are:
• Fully observable (the agent knows the complete state).
• Deterministic (the results of actions are predictable).
• Discrete (finite and countable number of states).
• Static (doesn’t change while the agent is thinking).
Example: GPS Navigation
• A GPS navigation system formulates the problem of finding a route from the current location (initial state) to the
destination (goal state) using a map (state space), evaluating various routes (search), and suggesting the optimal path
(solution).
Problem-Solving Agent
Algorithm: Simple Problem-Solving Agent •UPDATE-STATE: Processes current percept into an
function SIMPLE-PROBLEM-SOLVING-AGENT(percept) internal representation.
returns an action
•FORMULATE-GOAL: Determines the agent's next
persistent: state, goal, problem, plan objective.
state ← UPDATE-STATE(state, percept)
•FORMULATE-PROBLEM: Converts the goal into a
if plan is empty then
formal problem description.
goal ← FORMULATE-GOAL(state)
•SEARCH: Uses a search algorithm (BFS, DFS, A*) to find a
problem ← FORMULATE-PROBLEM(state, goal)
sequence of actions.
plan ← SEARCH(problem)
return FIRST(plan) •FIRST(plan): Takes the next action from the planned
sequence.
Components of a Well-Defined Problem
Component Description
Initial State The state from where the agent starts. Example: (Arad) in a Romania map.
State Space The set of all possible states reachable from the initial state.
Legal moves the agent can make at each state. Example: Drive(Arad →
Actions
Sibiu).
Describes the result of an action. Example: Performing Drive from Arad
Transition Model
leads to Sibiu.
Goal Test A function that checks whether a given state satisfies the goal condition.
(Optional) Numeric value representing the cost of a path, e.g., total distance
Path Cost
or time.
Problem Formulation Examples
Vacuum Cleaner Problem
•Initial State:
• Agent’s location (A or B)
• Dirt status of both locations: Clean or Dirty
• Example: ((A, Dirty), (B, Clean))
•Actions:
• Suck: Cleans the current location
• Move Left or Move Right
•Transition Model:
• Updates agent's location or cleans a square depending on the action.
Problem Formulation Examples
8-Puzzle Problem
•Initial State:
• A 3×3 board with 8 numbered tiles and one empty space.
• Example:
123
456
78_
•Actions:
• Move the blank space: Up, Down, Left, Right
•Transition Model:
• Swaps the blank with the adjacent tile in the direction of the move
•Goal Test:
• The tiles are in order:
Problem Formulation Examples
8-Queens Problem
•Initial State:
• Empty 8x8 chessboard
•Actions:
• Place a queen in the next row in a column where it doesn’t attack others.
•Transition Model:
• Adds one more queen to the board in a legal position.
•Goal Test:
• All 8 queens are placed with no two attacking each other.
Problem Formulation Examples
Route-Finding Problem
•Initial State:
• Starting city (e.g., Arad)
•Actions:
• Drive to a connected city
•Transition Model:
• Moves from one city to another
•Goal Test:
• Destination city (e.g., Bucharest) is reached
Problem Formulation Examples
Traveling Salesperson Problem (TSP)
•Initial State:
• Starting city (e.g., Mumbai)
•Actions:
• Move to any unvisited city
•Transition Model:
• Moves from current city to another, marking it as visited
•Goal Test:
• All cities visited exactly once and returned to starting point
Problem Formulation Examples
VLSI Layout Problem
•Initial State:
• A blank layout of a chip
•Actions:
• Place a gate or wire in a certain location
•Transition Model:
• Places component, updates constraints (e.g., space used, heat)
•Goal Test:
• All components are placed and connected correctly
Problem Formulation Examples
Problem Initial State Actions Transition Model Goal Test Path Cost
Position + room Suck, Move Updates # of moves/suck
Vacuum Cleaner All squares clean
status Left/Right location/status actions
Swap blank with
8 Puzzle Any tile config Move blank Goal tile config # of moves
adjacent tile
Add queen without 8 queens placed
8 Queens Empty board Place queen Not usually used
conflict safely
Drive to adjacent
Route Finding Starting city Updates location Reached destination Distance/time
city
Move to unvisited Update visited, All cities visited +
TSP Start city Total travel cost
cities current city return
Valid and complete Area, power,
VLSI Layout Blank chip Place gate/wire Update layout
layout performance
Assignment Questions
•State and explain the algorithm of a Simple Problem-Solving Agent
•State and explain the components of a well-defined problem.
•Write states, Initial States, Actions, Transition Model and Goal test to formulate the following problems:
• Vacuum Cleaner
• 8 Puzzle
• 8 Queens
• Route Finding
• TSP
• VLSI Layout