IT314 Week6a

Artificial Intelligence(AI) Department of Computer Science & IT
Week -6
Sarhad University of Science and Information Technology,
Search agents and its applications, searchAlgorithm terminologies, state space vs. search space, search strategies
BS SoftwareEngineering/ComputerScience
Engr.HasibShamshad
Peshawar
Last lecture summary
So far we have discussed What is an Agent and its Environment
We discussed some very comment Agents i.e. Simple reflex agents with examples ,Rational
Agents and the performance measures associated with Rational agents( PEAS).
“ So.. Where are we now? “

Goal-based agents
Agents that work towards a goal.

Agents consider the impact of actions on future states.
Agent’s job is to identify the action or series of actions that lead to the goal.
Formalized as a search through possible solutions.
EXAMPLE – 8 Queen Problem
The 8-queen problem: on a chess board, place 8

queens so that no queen is attacking any other
horizontally, vertically or diagonally.
Number of possible sequences to investigate:

64 ∗ 63 ∗ 62 ∗ ... ∗ 57 = 1.8 × 1014
Problem solving by search
1. Define the problem through:
(a) Goal formulation
(b) Problem formulation
2. Solving the problem as a 2-stage process:

(a) Search: “mental” or “offline” exploration of several possibilities
(b) Execute the solution found
Problem formulation
• Initial state: the state in which the agent starts
• States: All states reachable from the initial state by any sequence of actions
(State space)
• Actions: possible actions available to the agent. At a state s, Actions(s) returns
the set of actions that can be executed in state s. (Action space)
• Transition model: A description of what each action does Results(s, a)
• Goal test: determines if a given state is a goal state
• Path cost: function that assigns a numeric cost to a path w.r.t. performance
measure
• States: all arrangements of 0 to 8 queens on
the board.
• Initial state: No queen on the board
• Actions: Add a queen to any empty square
• Transition model: updated board
• Goal test: 8 queens on the board with none
attacked
Problem Solving by search
In Artificial Intelligence, Search techniques are universal problem-solving
methods.
 Rational agents or Problem-solving agents in AI mostly used these search
strategies or algorithms to solve a specific problem and provide the best result.
 Problem-solving agents are the goal-based agents and use atomic
representation.
We will now learn various problem-solving search algorithms.
Search Algorithm Terminologies
Search: It is a procedure to solve a search-problem in a given search space.

A search problem can have 3 main factors:
1. Search space: It represents a set of possible solutions, which a system may
have.
2. Start State: It is a state from where agent begins the search.
3. Goal test: It is a function which observe the current state and returns
whether the goal state is achieved or not.
Why Search?
“Because we want to achieve the goals for our agents and want to predict the future actions for
the agents”
Real world examples
Route finding problem: typically our example of map search, where we need to
go from location to location using links or transitions. Example of applications
include tools for driving directions in websites, in-car systems, etc.
Real world examples
Traveling salesperson problem: Find the shortest tour to visit each city exactly
once.
Real world examples
VLSI layout: position million of components and connections on a chip to
minimize area, shorten delays. Aim: put circuit components on a chip so as they
don’t overlap and leave space to wiring which is a complex problem.
Real world examples
Robot navigation: Special case of route finding for robots with no specific routes
or connections. The robot navigates in 2D or 3D space or ore where the state
space and action space are potentially infinite.
Real world examples
Automatic assembly sequencing: find an order in which to assemble parts of an
object which is in general a difficult and expensive geometric search.
Real world examples
Protein design: find a sequence of amino acids that will fold into a 3D protein
with the right properties to cure some disease.
Search Algorithm Terminologies
 Search tree: A tree representation of search problem is called Search tree. The
root of the search tree is the root node which is corresponding to the initial
state.
 Actions: It gives the description of all the available actions to the agent.
 Transition model: A description of what each action do, can be represented as a

transition model.
Search Algorithm Terminologies(cont..)
 Path Cost: It is a function which assigns a numeric cost to each path.

C (s,a,x) == p where s = current state
a = action
x = next state
 Solution: It is an action sequence which leads from the start node to the goal
node.
 Optimal Solution: If a solution has the lowest cost among all solutions.
State Space vs. Search Space
State Space: a physical configuration
Search Space: an abstract configuration represented by a search tree or a graph
of possible solutions.
Search tree: models the sequence of actions
 Root: initial state

Nodes: results from actions. A node has: parent, children, depth, path
cost, associated state in the state space.
Branches: actions
Expand: A function that given a node, creates all children nodes
Search Space Regions
The search space is divided into three regions:
1. Explored (a.k.a. Closed List, Visited Set)
2. Frontier (a.k.a. Open List, the Fringe)
3. Unexplored.
 The essence of search is moving nodes from regions (3) to (2) to (1), and the
essence of search strategy is deciding the order of such moves.
In the following we adopt the following color coding: orange nodes are
explored, grey nodes are the frontier, white nodes are unexplored, and black
nodes are failures.
Tree search
Search agent example
Search agent example
Let’s show the first steps in growing the search tree to find a route from San Francisco to
another city
How to handle repeated states?
Graph search
Search Strategies
A strategy is defined by picking the order of node expansion
Strategies are evaluated along the following dimensions:
 Completeness: Does it always find a solution if one exists?

Time complexity: Number of nodes generated/expanded
Space complexity: Maximum number of nodes in memory
Optimality: Does it always find a least-cost solution?
Search Strategies
Time and space complexity are measured in terms of:
– b: maximum branching factor of the search tree (actions per state).
– d: depth of the solution
– m: maximum depth of the state space (may be ∞) (also noted sometimes D).

IT314 Week6a

Uploaded by

Copyright:

Available Formats

IT314 Week6a

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

IT314 Week6a

Uploaded by

Copyright:

Available Formats

Artificial Intelligence(AI) Department of Computer Science & IT

So far we have discussed What is an Agent and its Environment

“ So.. Where are we now? “

Agents that work towards a goal.

The 8-queen problem: on a chess board, place 8

Number of possible sequences to investigate:

2. Solving the problem as a 2-stage process:

Search: It is a procedure to solve a search-problem in a given search space.

 Transition model: A description of what each action do, can be represented as a

 Path Cost: It is a function which assigns a numeric cost to each path.

 Root: initial state

Strategies are evaluated along the following dimensions:

 Completeness: Does it always find a solution if one exists?

– b: maximum branching factor of the search tree (actions per state).

– d: depth of the solution

You might also like