Problem Solving by Search

Lecture 3
chapter 3 Artificial Intelligence
A modern Approach

Umme Zahoora
Recap of Previous Lecture
• Types of rational Agents
• Properties of Task Environment
• Fully observable vs. Partially observable
• Deterministic vs. stochastic vs. Strategic
• Episodic vs. Sequential
• Static vs. Dynamic
• Discrete vs. Continuous
• Single agent vs. Multi agent
• Cooperative vs. Competitive
Introduction
• Search is a central topic in AI.

• Automated reasoning is a natural search task.

Outline
• Problem-solving agents
• Problem types
• Problem formulation
• Example problems
• Basic search algorithms
Problem-Solving Agent
sensors

?
environment
agent

actuators
Problem-Solving Agent

sensors

?
environment
agent

actuators
• Formulate Goal
• Formulate Problem
• States
• Actions
• Find Solution
Goal-Based Agents
• Goal reflects desires of
agents
• May project actions to
see if consistent with
goals
• Takes time, world may
change during
reasoning
 Problem-solving agents

• Problem solving agents are goal-directed agents:

1. Goal Formulation: Set of one or more (desirable) world

states (e.g. checkmate in chess).
2. Problem formulation: What actions and states to
consider given a goal and an initial state.
3. Search for solution: Given the problem, search for a
solution --- a sequence of actions to achieve the goal
starting from the initial state.
•4. Execution of the solution
Assumptions
• Goal states:World States

• Actions as transitions between states

• Goal Formulation: A set of states

• Problem Formulation:
• The sequence of required actions to move from current state to a goal state
 Example: Path Finding problem
Initial
State
• Formulate goal:
• be in Bucharest (Romania)
•
• Formulate problem: Goal
State
• action: drive between pair of
connected cities (direct road)
•
• state: be in a city
(20 world states)

Environment: fully observable (map),

• Find solution:
deterministic, and the agent knows effects
• sequence of cities leading of each action. Is this really the case?
from start to goal state, e.g.,
Arad, Sibiu, Fagaras, Bucharest Note: Map is somewhat of a “toy” example. Our real
• interest: Exponentially large spaces, with e.g. 10^100
• Execution or more states. Far beyond full search. Humans can
• drive from Arad to often still handle those!
Bucharest according to
the solution One of the mysteries of cognition.
 Example: Path Finding problem
Initial
State

Goal
State

• States: All possible states

• Initial State: In (Arad)
• Successor Function:<action,successor>
• {<Go(Sibiu),In(Sibiu)>,<Go(Timisoara),In(Timisoara)>,<Go(Zerind),In(Zerind)>}
• actions?
• goal test? In(Bucharest)
• path cost? Suppose I unit cost for each path from one city to another
 Example: Vacuum world state space graph

Start state

Goal
(reach one in
this set of states)

states?
Initial State:
Successor Function:
actions?
goal test?
path cost?
 Example: Vacuum world state space graph

Start state

Goal
(reach one in
this set of states)

states
Initial State:
Successor Function:
actions?
goal test?
path cost?
 Example: The 8-puzzle“sliding tile puzzle”

Aside:
variations
on goal state.
eg empty square
bottom right or
in middle.
• states?
• Initial State:
• Successor Function:
• actions?
• goal test?
• path cost?
•
 Example: The 8-puzzle“sliding tile puzzle”

Aside:
variations
on goal state.
eg empty square
bottom right or
in middle.
• states? The boards, i.e., locations of tiles
• Initial State: Any state can be designated as initial state
• Successor Function: This generates the legal states that
result from trying the four actions (blank moves left, right,
up, or down)
• actions? move blank left, right, up, down
• goal test? goal state (given; tiles in order)
•
 Searching for a solution to the 8-puzzle

Aside: in this tree, Start state

immediate
duplicates are
removed.

Goal
Example: Romania
• On holiday in Romania; currently in Arad.
• Flight leaves tomorrow from Bucharest
•
• Formulate goal:
• be in Bucharest
•
• Formulate problem:
• states: various cities
• actions: drive between cities
•
• Find solution:
• sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest
• 17
Problem-solving agents

18
 N-Queen

• N-Queen problem is a classical problem in the field of

Artificial Intelligence, where we try to find a chessboard
configuration where in a N × N board there will be N
queens, not attacking each other. There are different
ways to address this problem, each having own time
complexity.
N-Queen
 Implementation steps

• Follow the steps below to implement the idea:

• Make a recursive function that takes the state of the board and the current
row number as its parameter.
• Start in the topmost row.
• If all queens are placed, return true
• For every row.
• Do the following for each column in current row.
• If the queen can be placed safely in this column
• Then mark this [row, column] as part of the solution and recursively check if placing queen here leads
to a solution.
• If placing the queen in [row, column] leads to a solution, return true.
• If placing queen doesn’t lead to a solution then unmark this [row, column] and track back and
try other columns.
• If all columns have been tried and nothing worked, return false to trigger
backtracking.
 4- Queen Problem

• The 4 Queens Problem consists in placing four queens on a 4 x 4 chessboard so that

no two queens attack each other. That is, no two queens are allowed to be placed on
the same row, the same column or the same diagonal.
• We are going to look for the solution for n=4 on a 4 x 4 chessboard in this article.
 4 – Queen Problem

Step 0: Initialize a 4×4 board.

 4 – Queen Problem

• Step 1:
• Put our first Queen (Q1) in the (0,0) cell .
• ‘x‘ represents the cells which is not safe i.e. they are
under attack by the Queen (Q1).
• After this move to the next row [ 0 -> 1 ].
 4 – Queen Problem
Step 2:
•Put our next Queen (Q2) in the (1,2) cell .
•After this move to the next row [ 1 -> 2 ].
Step 3:
•At row 2 there is no cell which are safe to place
Queen (Q3) .
•So, backtrack and remove queen Q2 queen from
cell ( 1, 2 ) .
 4 – Queen Problem
Step 4:
•There is still a safe cell in the row 1 i.e. cell ( 1,
3 ).
•Put Queen ( Q2 ) at cell ( 1, 3).
 4 – Queen Problem
• Step 5:
• Put queen ( Q3 ) at cell ( 2, 1 ).
 4 – Queen Problem
• Step 6:
• There is no any cell to place Queen ( Q4 ) at row 3.
• Backtrack and remove Queen ( Q3 ) from row 2.
• Again there is no other safe cell in row 2, So backtrack again and remove queen ( Q2 ) from row 1.
• Queen ( Q1 ) will be remove from cell (0,0) and move to next safe cell i.e. (0 , 1).
• Step 7:
• Place Queen Q1 at cell (0 , 1), and move to next row.
 4 – Queen Problem

Step 8:
•Place Queen Q2 at cell (1 , 3), and move to next
row.
 4 – Queen Problem

Step 9:
•Place Queen Q3 at cell (2 , 0), and move to next
row.
 4 – Queen Problem
Step 10:
•Place Queen Q4 at cell (3 , 2), and move to next
row.
•This is one possible configuration of solution