ARTIFICIAL INTELLIGENCE
Dr. Nidhi Kushwaha
Department of Computer Science and Engineering
Indian Institute of Information Technology, Ranchi
2
04/24/2025
OVERVIEW
Problem-Solving Agents
Definition of search space
Problem Characteristics
Searching for the Solutions
Measuring problem solving performance
Infrastructure of search algorithms
3
04/24/2025
PROBLEM SOLVING AGENTS
Goal-based agents are also called as problem-solving agent.
Problem-solving agents use atomic representations.
Search for the problem can be categorized as Uninformed or
Informed Search Algorithms.
Advanced Goal-based agents that used Factored or Structured
representations are usually called planning agents.
4
04/24/2025
DEFINING STATE SPACE
AI Problem must be represented in State Space.
The set of all possible states that are possible in given problem.
This State Space is then searched to find the solution of the problem.
It consists a set of nodes representing each state of the problem.
Arcs between nodes represent legal moves from one state to another,
Our aim is to start with the initial and achieve the goal state
Each state space takes the form of a tree or a graph.
PROBLEM SOLVING AGENTS
Goal Formulation
Organize behaviour of the agent
Goal – set of states in the world where the goal is
satisfied
Problem Formulation
What are the Actions?
What are the States?
Choosing the best Sequence
Finding the sequence of action
PROBLEM SOLVING – ATOMIC AGENTS
Atomic Agents
• States are indivisible
• Searching through the states to reach the goal
04/24/2025
7
A Problem can be defined by 5 components,
Initial state- the start the agent,
a set of actions- the set of operators that executed at
the state,
a transition model (describing the results of
those actions) or Successor- return the state that
result from doing an action in a state,
Goal test function-determine whether a given state is
goal state, and
Path cost function- function that assigns a numeric
cost to a path.
04/24/2025
8
STATE-SPACE REPRENTATIONS
A Start State is the state in which an agent exists
initially.
A State Space is the set of all possible states that
are possible in your given world.
A Successor function is a function that takes in a
state and an action and computes the cost of
performing that action.
Successor state, the state the world would be in if
the given agent performed that action.
A Goal Test is a function that takes a state as input,
and determines whether it is a goal state.
A Path Cost is the number of steps in the path of
arriving to the goal.
9
04/24/2025
EXAMPLE OF AI PROBLEMS (8-PUZZLE)
1 8 7 1 4 7
2 6 2 5 8
3 4 5 3 6
10
04/24/2025
STATE SPACE FOR 8-PUZZLE PROBLEM
04/24/2025
11
PROBLEM CHARACTERISTICS FOR 8-PUZZLE
A problem can be defined formally by four
components:
EXAMPLE: TOY VACUUM PROBLEM
State: Vaccum Cleaner and Dirt Location
Initial State: Any State
Actions: Left, Right, Such, No Op
Goal test: no dirt/clean
Path cost: cost 1 per action
EXAMPLE: 8 QUEENS PROBLEM
Place 8 Queens on a chessboard so that no
two queens are in the same row, column or
diagonal.
EXAMPLE: 8 QUEENS PROBLEM
A solution
non-
solution
EXAMPLE: 8 QUEENS PROBLEM
64
63
EXAMPLE: 8 QUEENS PROBLEM
State: Any arrangement of 8 queens on the board.
Initial State: all queens are at column 1.
Successor function: Change the position of any one
queen
Goal: 8 queens on the board, none are attached.
EXAMPLE: MISSIONARIES AND CANNIBALS
Three missionaries and three
cannibals
a boat which can carry at most two
people
The constraint, for both banks, that
the missionaries present on the bank
cannot be outnumbered by
cannibals.
The boat cannot cross the river by
itself with no people on board.
State: number of missionaries and
cannibals on the boat and each bank
Initial State: all objects one bank
Actions: move boat with x
missionaries and y cannibals, no
more cannibals than missionaries on
the boat or the shore, a boat with a
EXAMPLE: RUBIK’S CUBE
State: List of colors on each face
Initial State: A specific color pattern
Actions: rotate a row or column or a face
Goal Test: configuration has the same color
on all tiles on every face
Path Cost: cost 1 per move?
WUMPUS WORLD PROBLEM
PEAS Description for the Wumpus World problem:
Performance measures:
Agent gets the gold and return back safe = +1000 points
Agent dies = -1000 points
Each move of the agent = -1 point
Agent uses the arrow = -10 points
Environment:
A cave with 16(4×4) rooms
Rooms adjacent (not diagonally) to the Wumpus are stinking
Rooms adjacent (not diagonally) to the pit are breezy
The room with the gold glitters
Agent’s initial position – Room[1, 1] and facing right side
Location of Wumpus, gold and 3 pits can be anywhere, except in Room[1, 1].
Actuators:
Devices that allow the agent to perform the following actions in the environment.
Move forward
Turn right
Turn left
Shoot
Grab
Release
Sensors:
Devices which helps the agent in sensing the following from the environment.
Breeze
Stench
Glitter
Scream (When the Wumpus is killed)
Bump (when the agent hits a wall)
WUMPUS WORLD PROBLEM
WUMPUS WORLD PROBLEM
EXAMPLE: REAL WORLD
Travelling Salesman Problem (TSP)
Robot Navigation
Protein folding
Graph Coloring
23
04/24/2025
EXAMPLE OF AI PROBLEMS (TOUR PROBLEM)
24
04/24/2025
EXAMPLE OF AI PROBLEMS (TOUR PROBLEM)
04/24/2025
25
STATE SPACE FOR TOUR PROBLEM
26
04/24/2025
PROBLEM CHARACTERISTICS FOR TOURING
PROBLEM
SEARCHING FOR THE SOLUTIONS
(CONT..)
The process of looking for a sequence of actions that
reaches the goal is called SEARCH.
Search Algorithms:
Takes Input: A problem (Touring Problem, Robot
Navigation)
Returns Output: Solution in form of action
sequence
Calls Search Procedure: Searching Algorithms
Execution Phase: Once the solution is found, the
action it recommends can be carried out.
INFRASTRUCTURE OF SEARCH
ALGORITHMS
Search Algorithms need data structure to
keep track of the search tree that is being
constructed.
For each ‘n’ node of the tree,
N. STATE : State in the state space
N.Parent : The node in the search tree that
generated this node
N.Action : The action we applied to the parent to
generate this node.
N.PathCost : The cost, denoted by g(n), of the
path from initial state to goal state.
MEASURING PROBLEM SOLVING PERFORMANCE
TYPES OF SEARCH STRATEGIES
UNINFORMED-
has no information about the number of steps or path
cost from the current state to goal state.
only distinguish a goal state from a non-goal state
INFORMED-
strategies that know whether on non-goal state is
more promising than the other
MISSIONARIES AND CANNIBALS
On one bank of a river are three missionaries (black
triangles) and three cannibals (red circles). There is one
boat available that can hold up to two people and that they
would like to use to cross the river. If the cannibals ever
outnumber the missionaries on either of the river’s banks,
the missionaries will get eaten.
How can the boat be used to safely carry all the
missionaries and cannibals across the river?
33
04/24/2025
MISSIONARIES AND CANNIBALS: INITIAL
STATE AND ACTIONS
Initial State: 5 possible actions:
all missionaries, all one missionary crossing
cannibals, and the boat one cannibal crossing
are on the left bank two missionaries crossing
two cannibals crossing
one missionary and one
cannibal crossing
34
04/24/2025
MISSIONARIES AND CANNIBALS: STATE
SPACE
1 1
2 c c 2
c c
1 1 1 1
m m 2 2 m m
1 c c 1
c c
1 1
c c
1 1
c c
2 2
m m
1
m
1
c
35
04/24/2025
BREADTH-FIRST SEARCH
Strategy:
Expand root node
Expand successors of root node
Expand successors of successors of root node
Implementation:
use FIFO queue to store fringe nodes in general tree search
algorithm
BREADTH-FIRST SEARCH: MISSIONARIES
04/24/2025
AND CANNIBALS
depth = 0
depth = 1
depth = 2
depth = 3
36
38
04/24/2025
BREADTH FIRST SEARCH
39
04/24/2025
BREADTH FIRST SEARCH (CONT..)
40
04/24/2025
BREADTH FIRST SEARCH (CONT..)
41
04/24/2025
BREADTH FIRST SEARCH (CONT..)
04/24/2025
42
SUMMARY
Uniformed Search methods have access only to the problem
definition.
BFS algorithm is one of the basic algorithm that expands the
shallowest nodes first;
It is complete. Optimal for unit step costs, but has exponential
space complexity.
44
04/24/2025
BREADTH FIRST SEARCH (CONT..)
04/24/2025
45
SUMMARY
It is complete. Optimal for unit step costs, but has exponential
space complexity.
Memory requirement is bigger problem than the exeecution time.
Executin time is still s major factor.
In general exponential complexity search problems can not be
solved by Uninformed methods, but solution of small instances can
by easily determined.
46
04/24/2025
UNIFORM-COST SEARCH
When all the step costs are equal, BFS is optimal, because it
always expand the unexpanded shallowest node.
By simple modifications in BFS we can find optimal algorithm in
any step-cost function.
Instead of expanding the shallowest node, Uniform-Cost Search
expands node n with the lowest path cost g(n).
By storing the frontiers as a priority queue ordered by g.
47
UNIFORM-COST SEARCH ON GRAPH
04/24/2025
function UNIFORM-COST-SEARCH
(problem) returns a solution, or
failure
node←←a
frontier node with
a priority queueSTATEordered
=
problem.INITIAL
byloop
PATH-COST, -STATE
with , PATHas
node -COST
the =only
0
do
element
if EMPTY?( frontier) then function CHILD-NODE(prob
explored
return ← an empty set
failure parent, action)
node ← POP( frontier) return a node with
if problem.GOAL- STATE = problem.RESULT(p
for each action
TEST(node.STATE) in return action),
then
problem.A CTIONS(node.STATE)
SOLUTION(node) PARENT = parent, ACTION =
doifadd
child.S TATE is not in explored or
node.S TATE to explored PATH-COST = parent.PATH-
frontier
childthen
← CHILD- + problem.STEP-
frontier ←node,
NODE(problem, INSERT(child,
action)frontier)COST(parent.STATE, action)
else if child.STATE is in frontier with
higher PATH-COST then
48
04/24/2025
UNIFORM-COST SEARCH (CONT..)
if child.STATE is not in explored or frontier then
frontier ← INSERT(child, frontier)
else if child.STATE is in frontier with higher PATH-COST then
replace that frontier node with child
UNICOST SEARCH METHOD
Uniform-cost search expands the node with lowest path
cost, g(n), and its optimal for general step costs.
50
04/24/2025
DIFFERENCE BETWEEN UNIFORM-COST SEARCH & BFS
Uniform-Cost search works with the different cost path rather than
equal cost path as in BFS.
In Uniform-Cost search Frontier is not a simple queue but it’s a
priority queue, in which the lowest element comes first and then the
second lower element, and so on.
51
04/24/2025
DIFFERENCE BETWEEN UNIFORM-COST SEARCH & BFS
In BFS, Goal test is performed, first for the root and again before the
node is visited or explored.
However, in Uniform-Cost search, Goal test is performed just
before the node is added to explored list that means it is already visited
but yet to be explored.
In Uniform-Cost search, if the node is already visited with the higher
cost then algorithm will replace it with the node having lower cost
path.
52
04/24/2025
ASSIGNMENT FOR TODAY
Consider the below example, where we need to reach any one of the
destination node{G1, G2, G3} starting from node S. Node{A, B, C,
D, E and F} are the intermediate nodes.
Uniform-cost search is guided by path costs
rather than depths, so its complexity is not
easily characterized in terms of b and d.
ITERATIVE DEEPENING SEARCH(IDS)
IDS- ANALYSIS
Completeness: Yes!
Optimality: Yes for Uniform cost edges,
can be modified for non-uniform cost trees
Time Complexity: exponential in d
Space Complexity: bd
DEPTH-LIMITED SEARCH (DLS)
Implementation: nodes at depth 𝑙 have no
Depth-first search with depth limit l.
successors.
Only finite space to be explored.
Completeness: Yes/No???
Optimality: Yes/No???
ASSIGNMENT
BFS ?
DFS ?
IDDFS?
