Artificial Intelligence

Ch 02 Intelligent Agents
part1

Instructor: Kamal Darwish

1
 Outline

⚫ Agents and environments

⚫ Rationality
⚫ PEAS (Performance measure, Environment,
Actuators, Sensors)
⚫ Environment types
⚫ Agent types

2
 An agent is any entity that can be viewed as:
• perceiving its environment through sensors, and
• acting upon that environment through actuators.

3
 Agents and Environments [cont.]
Agents include humans, robots, softbots, thermostats, etc.
• human:
perceives: with eyes, ears, nose, hands, ...,
acts: with voice, hands, arms, legs, ...
• robot:
perceives: with video-cameras, infra-red sensors, radar, ...
acts: with wheels, motors,
• softbot:
perceives: receiving keystrokes, files, network packets, ...
acts: displaying on the screen, writing files, sending network packets
• thermostat:
perceives: with heat sensor, ...
acts: electric impulses to valves, devices, ...
4
Agents and Environments [cont.]
▪
▪
▪
▪

5
Key concepts
Percept and Percept sequences
 percept: the collection of agent’s perceptual inputs at any given
instant
 percept sequence: the complete history of everything the agent has
ever perceived

An agent’s choice of action at any given instant

 can depend on the entire percept sequence observed to date
 does not depend on anything it hasn’t perceived
Remark
An agent can perceive its own actions, but not always it effects.
6
Key concepts [cont.]
Agent function
An agent’s behavior is described by the agent function [f: P* → A]
which maps any given percept sequence into an action.
• ideally, can be seen as a table [percept sequence, action]

Agent program
Internally, the agent function for an artificial agent is implemented by an agent program.

Note: Agent function vs. agent program

 The agent function is an abstract mathematical description
• possibly-infinite description
 The agent program is a concrete implementation of the agent function
• finite description
• runs on the physical architecture to produce the agent function f
7
• agent = architecture + program
Example : Vacuum cleaner
A very-simple vacuum cleaner
 Environment: squares A and B
 Percepts: location ({A, B}) and content ({Dirty, Clean})
• e.g. [A, Dirty]
 Actions: {left, right, suck, no_op}

8
Example : Vacuum cleaner [cont.]
A simple agent function
If the current square is dirty, then suck; otherwise, move to the other square.
⚫ Agent’s function -> look-up table
⚪ For many agents this is a very large table
Percept sequence Action
[A,Clean] Right
[A,Dirty] Suck
[B,Clean] Left
[B,Dirty] Suck
[A,Clean],[B,Clean] Left
[A,Clean],[B,Dirty] Suck
etc etc

Note: this agent function depends only on the last percept, not on the whole percept
sequence. 9
Example : Vacuum cleaner [cont.]
Corresponding agent program
function Reflex-Vacuum-Agent([location,status]) returns an action
if status = Dirty then return Suck
else if location = A then return Right
else if location = B then return Left

10
 Rational Agents
 Intuition: a rational agent is one that “does the right thing”
 i.e., every entry in the agent function-table is filled out correctly
 What is the right thing?
 Approximation: the most “succesfull” thing:
 In a given environment, according to the percept sequence it
receives, an agent generates a sequence of actions, ...
 ... causing the environment to go through a sequence of states.
 If such sequence is desirable, then the agent has performed well.
⇒ need a performance measure to evaluate any sequence of
environment states
 Performance measure should be objective.
11
Rational Agents [cont.]

 Performance measure according to what is wanted in the

environment, not to how the agents should behave
 e.g. “how clean the floor is” is a better measure than “the
amount of dirt cleaned within a certain time”

12
Rational Agents [cont.]
What is rational at any given time depends on four things:
 The performance measure that defines the criterion of success
 The agent’s prior knowledge of the environment
 The actions that the agent can perform
 The agent’s percept sequence to date (from sensors)
Definition of a rational agent
For each possible percept sequence, a rational agent should select an action
that is expected to maximize its performance measure, given the evidence
provided by the percept sequence and whatever built-in knowledge the agent has.

13
 Example of Rational Agents: vacuum-cleaner agent
Under the following assumptions:
 Performance measure: one point for each clean square at each time step, over 1000
time steps
 Environment knowledge:
• “geography” known a priori,
• dirt distribution and agent initial location unknown
• [clean squares cannot become dirty again ]
 Perception: self location, presence of dirt
 Actions: Left, Right, Suck
 Is the agent rational?
⇒ Yes! (provided the given performence measure)

Beware: if a penalty for each move is given, the agent behaves poorly
⇒ better agent: do nothing once it is sure all the squares are clean
14
 Rationality vs. Omniscience vs. Perfection
 Remark
 Rationality ≠ Omniscience!
• An omniscient agent knows for sure the outcome of its actions
⇒ omniscience impossible in reality
• A rational agent may only know “up to a reasonable confidence”
(e.g., when crossing a road, what if something falling from a plane
flattens you? if so, would you be considered irrational?)

 Rational behaviour is not perfect behaviour!

• perfection maximizes actual performance
• (given uncertainty) rationality maximizes expected performance
15
Other important features

 Rationality requires other important features

Information gathering/exploration:
the rational choice depends only on the percept sequence to date
⇒ actions needed in order to modify future percepts
Ex: look both ways before crossing a busy road
Learning:
agent’s prior knowledge of the environment incomplete
⇒ learning from percept sequences improves & augments it
Ex: a baby learns from trial&errors the right movements to walk
16
Autonomy in Agents
The autonomy of an agent is the extent to which its behaviour is determined by its own
experience, rather than knowledge of designer.

⚫ Therefore, a system is not autonomous if it is guided by its designer according

to a priori decisions.
⚫ An autonomous agent can always say “no”.
⚫ Extremes
 No autonomy – ignores environment/data
 Complete autonomy – must act randomly/no program
⚫ Ideal: design agents to have some autonomy
 Possibly become more autonomous with experience
⚫ Example: a child learns how to climb a tree

17
Task Environments - PEAS

 To design a rational agent we must specify its task environment

i.e. the “problems” to which rational agents are the “solutions

 Task environment described in terms of four elements (“PEAS”):

Performance measure
Environment
Actuators
Sensors

18
PEAS: Vacuum Cleaner

Simple Vacuum Cleaner

Performance measure: 1 point per clean square per time step
Environment: squares A and B, possibly dirty
Actuators: move left/right, suck
Sensors: self location, presence of dirt

19
PEAS: Automated taxi driver
 Performance measure
• safety, destination, profits, comfort, ...
 Environment
• streets/freeways, other traffic, pedestrians, ...
 Actuators
• steering, accelerator, brake, horn, speaker/display, ...
 Sensors
• video, sonar, speedometer, engine sensors, GPS, ...
Remark
 Some goals to be measured may conflict!
e.g. profits vs. safety, profits vs. comfort, ...
=⇒ tradeoffs are required 20
▪
▪
▪
▪
▪
▪
▪
▪

21
PEAS: Part-picking robot

 Performance measure
• Percentage of parts in correct bins
 Environment
• Conveyor belt with parts, bins
 Actuators
• Jointed arm and hand
 Sensors
• Camera, joint angle sensors

22
PEAS: Interactive English tutor

 Performance measure
• Maximize student's score on test
 Environment
• Set of students
 Actuators
• Screen display (exercises, suggestions, corrections)
 Sensors
• Keyboard, microphone

23
Properties of Task Environments

Task environments can be categorized along six dimensions:

 Fully observable vs. partially observable
 Single-agent vs. multi-agent
 Deterministic vs. stochastic
 Episodic vs. sequential
 Static vs. dynamic
 Discrete vs. continuous

24
 Properties of Task Environments [cont.]
Fully observable vs. partially observable

 A task environment is (effectively) fully observable iff the sensor

detect the complete state of the environment needed to choose an
action.
 ”relevant” depends on the performance measure
 no need to maintain internal state to keep track of the environment
 A task environment may be partially observable
 Ex: Taxi driving
• noisy and inaccurate sensors
• parts of the state are not accessible for sensors
 A t.e. might be even unobservable (no sensors)
 e.g. fully-deterministic actions
25
Properties of Task Environments [cont.]
Deterministic vs. stochastic
 A task environment is deterministic iff its next state is completely
determined by its current state and by the action of the agent.
 (Ex: a crossword puzzle).
 A task environment is stochastic if uncertainty about outcomes is
quantified in terms of probabilities (Ex: dice, poker game, component
failure,...)
 A t.e. is nondeterministic iff actions are characterized by their possible
outcomes, but no probabilities are attached to them
A partially observable environment could appear to be stochastic.
• ⇒ for practical purposes, when it is impossible to keep track of all
the unobserved aspects, they must be treated as stochastic.
26
• (Ex: Taxi driving)
Properties of Task Environments [cont.]
Episodic vs. sequential
 In an episodic task environment
 the agent’s experience is divided into atomic episodes
 in each episode the agent receives a percept and then performs a
single action
⇒ episodes do not depend on the actions taken in previous
episodes, and they do not influence future episodes
 Ex: an agent that has to spot defective parts on an assembly line,
 In sequential environments the current decision could affect future
decisions ⇒ actions can have long-term consequences
 Ex: chess, taxi driving, ...
 Episodic environments are much simpler than sequential ones
 No need to think ahead!
27
Properties of Task Environments [cont.]
Static vs. dynamic
 The task environment is dynamic iff it can change while the
agent is choosing an action, static otherwise
⇒ agent needs keep looking at the world while deciding an
action
 Ex: crossword puzzles are static, taxi driving is dynamic
 The t.e. is semidynamic if the environment itself does not change
with time, but the agent’s performance score does
 Ex: chess with a clock
 Static environments are easier to deal wrt. [semi]dynamic ones

28
Properties of Task Environments [cont.]
Discrete vs. continuous
 The state of the environment, the way time is handled,
and agents percepts & actions can be discrete or
continuous
 Ex: Crossword puzzles: discrete state, time, percepts & actions
 Ex : Chess: : discrete state, time, percepts & actions
 Ex: Taxi driving: continuous state, time, percepts & actions
...

29
Properties of Task Environments [cont.]
Single-agent vs. multi-agent
 A task environment is multi-agent iff contains other agents who are
also maximizing some performance measure that depends on the
current agent’s actions
 latest condition essential
 distinction between single- and multi-agent sometimes subtle
 Two important cases
 competitive multi-agent environment: other agents’ goals conflict with
or oppose to the agent’s goals
Ex: chess, war scenarios, taxi driving (compete for parking lot), ...
 cooperative multi-agent environment: other agents’ goals coincide in
full or in part with the agent’s goals
• Ex: ants’ nest, factory, taxi driving (avoid collisions), ...
30
Properties of Task Environments [cont.]
Single-agent vs. multi-agent
 different design problems for multi-agent wrt. single-agent
 competitive: randomized behaviour often rational
(unpredictable)
 collaborative: communication with other agents often
rational

 In a multi-agent environment we ignore uncertainty that

arises from the actions of other agents
 Ex: chess is deterministic even though each agent is
unable to predict the actions of the others.
31
Properties of Task Environments [cont.]

Note
 The simplest environment is fully observable, single-agent,
deterministic, episodic, static and discrete.
 Ex: simple vacuum cleaner
 Most real-world situations are partially observable, multi-agent,
stochastic, sequential, dynamic, and continuous.
 Ex: taxi driving

32
Properties of Task Environments [cont.]
Example properties of task Environments

Several of the answers in the table depend on how the task

environment is defined.
 Artificial Intelligence
Ch 02 Intelligent Agents
part2

Instructor: Kamal Darwish

1
Properties of the Agent’s State of Knowledge
Known vs. unknown
Describes the agent’s (or designer’s) state of knowledge about
the “laws of physics” of the environment
if the environment is known, then the outcomes (or outcome
probabilities if stochastic) for all actions are given.
if the environment is unknown, then the agent will have to learn
how it works in order to make good decisions
Orthogonal wrt. task-environment properties

Known ≠ Fully observable

a known environment can be partially observable
(Ex: a solitaire card games)
an unknown environment can be fully observable
(Ex: a game I don’t know the rules of)
2
The structure of Agents
Agent = Architecture + Program
 AI Job: design an agent program implementing the agent
function
 The agent program runs on some computing device with
physical sensors and actuators: the agent architecture
 All agents have the same skeleton:
• Input: current percepts
• Output: action
• Program: manipulates input to produce output
Remark
the agent function takes the entire percept history as input the
agent program takes only the current percept as input
⇒ if the actions need to depend on the entire percept sequence, the
agent will have to remember the percepts 3
A trivial Agent Program
The Table-Driven Agent
The table represents explicitly the agent function
Ex: the simple vacuum cleaner

Blow-up in table size ⇒ doomed to failure

4
Agent types
Four basic types in order of increasing generality:
 Simple reflex agents
 Reflex agents with state/model
 Goal-based agents
 Utility-based agents
 All these can be turned into learning agents

5
Agent Types: Simple-reflex agent
 Select action on the basis of the current percept only
Ex: the simple vacuum-agent

 Implemented through condition-action rules

Ex: “if car-in-front-is-braking then initiate-braking”
can be implemented, e.g., in a Boolean circuit
 Large reduction in possible percept/action
situations due to ignoring the percept history

6
Agent Types: Simple-reflex agent [cont.]
 Simple but very limited intelligence.
 Action does not depend on percept history, only on current
percept.
 Therefore no memory requirements.
 may work only if the environment is fully observable
• deadlocks or infinite loops may occur otherwise
• ⇒ limited applicability

7
 Agent Types: Model-based agent

 Idea: To tackle partially-observable environments, keeps track

of the part of the world it can’t see now
• Maintain internal state depending on the percept history
• reflects at least some of the unobserved aspects of current
state
 To update internal state the agent needs a model of the world:
• how the world evolves independently of the agent
Ex: an overtaking car will soon be closer behind than it was before
• how the agent’s own actions affect the world
Ex: turn the steering wheel clockwise ⇒ the car turns to the right

8
Agent Types: Model-based Agent [cont.]

Model-based Agent program

Agent Types: Goal-based agent
 The agent needs goal information describing desirable
situation
• Ex: destination for a Taxi driver
 Idea: combine goal with the model to choose actions
 Difficult if long action sequences are required to reach
the goal
⇒ Typically investigated in search and planning research.
 Major difference: future is taken into account
• rules are simple condition-action pairs, do not target a
goal

10
 Agent Types: Goal-based Agent [cont.]

Goal-based Agents
 more are flexible:
• the knowledge that supports its decisions is represented explicitly
• such knowledge can be modified
⇒ all of the relevant behaviors to be altered to suit the new conditions
o Ex: If it rains, the agent can update its knowledge of how effectively its
brakes operate
• the goal can be modified/updated ⇒ modify its behaviour
o no need to rewrite all rules from scratch
 more complicate to implement
 may require expensive computation (search, planning)

11
Agent Types: Utility-based agent
 Goals alone often not enough to generate high-quality
behaviors
 Certain goals can be reached in different ways, of different
quality
• Ex: some routes are quicker, safer, or cheaper than others
 Idea: Add utility function(s) to drive the choice of actions
• maps a (sequence of) state(s) onto a real number
⇒ actions are chosen which maximize the utility
function under uncertainty, maximize the expected
utility function
⇒ utility function = internalization of performance measure

12
Agent Types: Utility-based Agent [cont.]

Utility-based Agents
advantages wrt. goal-based:
with conflicting goals, utility specifies and appropriate tradeoff
with several goals none of which can be achieved with certainty,
utility selects proper tradeoff between importance of goals and
likelihood of success
still complicate to implement
require sophisticated perception, reasoning, and learning
may require expensive computation

13
 Artificial Intelligence
Ch 02 Intelligent Agents
Part2[continue]

Instructor: Kamal Darwish

1
Agent Types: Learning

Problem
 Previous agent programs describe methods for selecting actions
 How are these agent programs programmed?
 Programming by hand inefficient and ineffective!
 Solution: build learning machines and then teach them (rather than instruct
them)
 Advantage: robustness of the agent program toward initially-unknown
environments

2
Agent Types: Learning
Performance element: selects actions based on percepts
 Corresponds to the previous agent programs

3
Agent Types: Learning
Learning element: introduces improvements
 uses feedback from the critic on how the agent is doing
 determines improvements for the performance element

4
Agent Types: Learning
Critic tells how the agent is doing wrt. performance standard

5
Agent Types: Learning
Problem generator: suggests actions that will lead to new and
informative experiences
 forces exploration of new stimulating scenarios

6
Learning Agent Types: Example

Taxi Driving
After the taxi makes a quick left turn across three lanes, the critic
observes the shocking language used by other drivers.
From this experience, the learning element formulates a rule
saying this was a bad action.
The performance element is modified by adding the new rule.
The problem generator might identify certain areas of behavior in
need of improvement, and suggest trying out the brakes on
different road surfaces under different conditions.

7
 Artificial Intelligence
Ch 03 Problem Solving by Search
Part1

Instructor: Kamal Darwish

1
Types ofAgents
a Reflex Agent : a Planning agent :

Considers how the world IS Considers how the world WOULD BE

• Choose action based on current • Decisions based on (hypothesized)
percept. consequences of actions.
• Do not consider the future • Must have a model of how the world
consequences of actions. evolves in response to actions.
• Must formulate a goal.
State Search Graph
Problems are solved by searching among alternative choices.
 Humans consider several alternative strategies on their way to solving a problem.

 A Chess player considers a few alternative moves.

 A mathematician chooses from a different strategies to find a proof for a theorem.

 A physician evaluates several possible diagnoses.
Example:Tic-Tac-ToeGame

X X X
X X X
X X X

O O O
X X X O X X O X X X
O O O
Example: MechanicalFault Diagnosing
Start ask:
What is the problem?

Engine trouble
ask:
Transmission
ask:………
breaks
ask: ……
…
Does the car start?
Yes No

Engine starts Engine won’t start ask:

ask:………. Will engine turn over?

Yes No battery
Yes
ok
Turn over Won’t turn over ask: No
ask: …….. Do lights come on? battery
dead
 Search
We will consider the problem of designing goal-based agents in
fully observable, deterministic, discrete, known environments.

Start State

Goal State
Search
 The agent must find a sequence of actions that reaches the goal.
 The performance measure is defined by:
(a) reaching the goal, and ..
(b) how “expensive” the path to the goal is.
Problem Solving as Search
 One of the dominant approaches to AI problem solving: formulate a problem/task
as search in a state space.

Main Paradigm
1 Goal formulation: define the successful world states
Ex: a set of states, a Boolean test function ...
2 Problem formulation:
define a representation for states
define legal actions and transition functions
3 Search: find a solution by means of a search process
solutions are sequences of actions
4
Execution: given the solution, perform the actions

⇒ Problem-solving agents are (a kind of) goal-based agents

Problem Solving as Search: Example
Example: Traveling in Romania
 Informal description: 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
• Initial state: Arad
 Search for a solution: sequence of cities from Arad to Bucharest
• e.g. Arad, Sibiu, Fagaras, Bucharest
• explore a search tree/graph

Note
The agent is assumed to have no heuristic knowledge about traveling
in Romania to exploit.
Problem Solving as Search: Example [cont.]

A simplified road map of part of Romania.

Problem Solving as Search [cont.]
Assumptions for Problem-solving Agents (this chapter only)
 state representations are atomic
⇒ world states are considered as wholes, with no internal structure
Ex: Arad, Sibiu, Zerind, Bucharest,...
 the environment is observable
⇒ the agent always knows the current state
Ex: Romanian cities & roads have signs
 the environment is discrete
⇒ at any state there are only finitely many actions to choose from
Ex: from Arad, (go to) Sibiu, or Zerind, or Timisoara (see map)
 the environment is known
⇒ the agent knows which states are reached by each action
Ex: the agent has the map
 the environment is deterministic
⇒ each action has exactly one outcome
Ex: from Arad choose go to Sibiu ⇒ next step in Sibiu
Problem Solving as Search [cont.]
Notes about search
 Search happens inside the agent
a planning stage before acting different from
searching in the world
 An agent is given a description of what to achieve, not an
algorithm to solve it
⇒ the only possibility is to search for a solution
 Searching can be computationally very demanding (NP-hard)
 Can be driven with benefits by knowledge of the problem
(heuristic knowledge) ⇒ informed/heuristic search
Problem-solving Agent: Schema
 Well-defined problems and solutions

Problem Formulation: Components

 the initial state the agent starts in
Ex: In(Arad)
 the set of applicable actions available in a state (A CTIONS ( S ))
Ex: if s is In(Arad), then the applicable actions are
{Go(Sibiu), Go(Timisoara), Go(Zerind) }
 a description of what each action does (aka transition model)
• R ESULT(S,A): state resulting from applying action A in state S
Ex: R ESULT (IN (ARAD ), GO (Z ERIND )) is IN (Z ERIND )
 the goal test determining if a given state is a goal state
Explicit (e.g.: { In(Bucharest)} )
Implicit (e.g .: (NoDirt(x))
 the path cost function assigns a numeric cost to each path
in this chapter: the sum of the costs of the actions along the path
Well-defined problems and solutions [cont.]
Initial state, actions, and transition model implicitly define the state space of the
problem
 the state space forms a directed graph (e.g. the Romania map)
typically too big to be created explicitly and be stored in full in a state space
graph, each state occurs only once
 a path is a sequence of states connected by actions
 a solution is a path from the initial state to a goal state
 an optimal solution is a solution with the lowest path cost
 StateSpace
 An AI problem can be represented as a state space graph.
 A graph is a set of nodes and links that connect them.
 What is the state space for the Romania problem?
Well-defined problems and solutions [cont.]
 Problem formulations are models of reality (i.e. abstract descriptions) real world is
absurdly complex
⇒ state space must be abstracted for problem solving
 lots of details removed because irrelevant to the problem
Ex: exact position, “turn steering wheel to the left by 20 degree”, ...
 abstraction: the process of removing detail from representations
• abstract state represents many real states
• abstract action represents complex combination of real actions
 valid abstraction: can expand any abstract solution into a solution in the
detailed world
 useful abstraction: if carrying out each of the actions in the solution is easier
than in the original problem

The choice of a good abstraction involves removing as much detail as possible, while retaining
validity and ensuring that the abstract actions are easy to carry out.
Toy Example: Simple Vacuum Cleaner
 States: 2 locations, each {clean, dirty}: 2 · 22 = 8 states
 Initial State: any
 Actions: { Left, Right, Suck }
 Transition Model: Left [Right] if A [B], Suck if clean ⇒ no effect
 Goal Test: check if squares are clean
 Path Cost: each step costs 1 ⇒ path cost is # of steps in path
Toy Example: The 8-Puzzle
 States: Integer location of each tile ⇒ 9!/2 reachable
 states Initial State: any
 Actions: moving { Left, Right, Up, Down} the empty space
 Transition Model: empty switched with the tile in target location
 Goal Test: checks state corresponds with goal configuration
 Path Cost: each step costs 1 ⇒ path cost is # of steps in path
Toy Example: The 8-Puzzle [cont.]

NP-complete: N-Puzzle (N = k 2 − 1): N!/2 reachable states

Toy Example: 8-Queens Problem
 States: any arrangement of 0 to 8 queens on the board
⇒ 64 · 63 · ... · 57 ≈ 1.8 · 1014 possible sequences
 Initial State: no queens on the board
 Actions: add a queen to any empty square
 Transition Model: returns the board with a queen added
 Goal Test: 8 queens on the board, none attacked by other queen
 Path Cost: none

21 / 96
Toy Example: 8-Queens Problem (incremental)
 States: n ≤ 8 queens on board, one per column in the n leftmost
columns, no queen attacking another
⇒ 2057 possible sequences
 Actions: Add a queen to any square in the leftmost empty
column such that it is not attacked by any other queen.
...

22 / 96
Real-World Example: Robotic Assembly
 States: real-valued coordinates of robot joint angles, and of parts of the
object to be assembled
 Initial State: any arm position and object configuration
 Actions: continuous motions of robot joints
 Transition Model: position resulting from motion
 Goal Test: complete assembly (without robot)
 Path Cost: time to execute

23 / 96
 Artificial Intelligence
Ch 03 Problem Solving by Search
Part 2

Instructor: Kamal Darwish

1
Searching for Solutions

Search: Generate sequences of actions.

 Expansion: one starts from a state, and applying the operators (or
successor function) will generate new states
 Search strategy: at each step, choose which state to expand.
 Search Tree: It represents the expansion of all states starting
from the initial state (the root of the tree)
 The leaves of the tree represent either:
• states to expand
• Solutions
• dead-ends
Tree Search Algorithms

Tree Search: Basic idea

 Off-line, simulated exploration of state space
 start from initial state
 pick one leaf node, and generate its successors
(a.k.a. expanding a node)
• set of current leaves called frontier (a.k.a. fringe, open list)
• strategy for picking leaves critical (search strategy)
 ends when either a goal state is reached, or no more candidates
to expand are available (or time-out/memory-out occur)
Tree Search Algorithms [cont.]
Tree Search Algorithm Outline
Initialize the frontier using the starting state.
While the frontier is not empty:

• Choose a frontier node according to search strategy

and take it off the frontier.
• If the node contains the goal state, return solution.
• Else expand the node and add its children to the frontier.
Tree-Search Example

A solution is a path ending in the goal state

Tree-Search Example: Trip from Arad to Bucharest
Expanding the search tree
 Initial state: { Arad}
 Expand initial state ⇒ {Sibiu, Timisoara, Zerind}
 Pick&expand Sibiu ⇒ {Arad, Fagaras, Oradea, Rimnicu Vicea}
...

Beware: Arad ›→ Sibiu ›→ Arad (repeated state ⇒ loopy path!)

Repeated states & Redundant Paths
 redundant paths occur when there is more than one way to
get from one state to another
⇒ same state explored more than once
 Failure to detect repeated states can:
• cause infinite loops
• turn linear problem into exponential

Moral: Algorithms that forget their history are doomed to repeat it!
Repeated states & Redundant Paths
 redundant paths occur when there is more than one way to
get from one state to another
⇒ same state explored more than once
 Failure to detect repeated states can:
• cause infinite loops
• turn linear problem into exponential

Moral: Algorithms that forget their history are doomed to repeat it!
Graph Search Algorithms
Graph Search: Basic idea
 add a data structure which remembers every expanded node
• a.k.a. explored set or closed list
• typically a hash table (access O(1))
 do not expand a node if it already occurs in explored set
Graph Search Algorithms [cont.]
 Initialize the frontier using the starting state
 While the frontier is not empty
• Choose a frontier node according to search strategy
and take it off the frontier.
• If the node contains the goal state, return solution
• Else expand the node and add its children to the frontier.

To handle repeated states:

 Every time you expand a node, add that state to the explored set; do
not put explored states on the frontier again.
 Every time you add a node to the frontier, check whether it already
exists with a higher path cost, and if yes, replace that node with the
new one.
Graph Search Algorithms: Example

Graph search on the Romania trip problem

(at each stage each path extended by one step)
two states become dead-end
Graph Search Algorithms: Example

Separation Property of graph search: the frontier separates the

state-space graph into the explored region and the unexplored region

Graph search on a rectangular-grid problem

Implementation: States vs. Nodes
A state is a representation of a physical configuration
A node is a data structure constituting part of a search tree
includes fields: state, parent, action, path- cost g(x )
⇒ node ≠ state
It is easy to compute a child node from its parent
Implementation: Frontier and Explored
Frontier/Fringe
Implemented as a Queue: Three kinds of queues are used in search algorithms:
 First-in-First-Out, FIFO (aka “queue”)
• first pops the node that was added to the queue first
• we shall see it is used in breadth-first search.
 Last-in-First-Out, LIFO (aka “stack”)
• pops first the most recently added node
• we shall see it is used in depth-first search.
 Best-First-out (aka “priority queue”)
• first pops the node with the minimum cost according to some
evaluation function, f.
• It is used in best-first search.
Implementation: Frontier and Explored [cont.]

 The operations on a frontier are:

ISEMPTY(Frontier): returns true only if there are no nodes in the frontier
POP(Frontier): removes the top node from the frontier and returns it
TOP(Frontier): returns (but does not remove) the top node of the frontier.
ADD(node, Frontier ): inserts node into its proper place in the frontier.
Evaluating Search Strategies
 Strategies are evaluated along the following dimensions:
 completeness: does it always find a solution if one exists?
 time complexity: how many steps to find a solution?
 space complexity: how much memory is needed?
 optimality: does it always find a least-cost solution?
 Time and space complexity are measured in terms of
b: maximum branching factor of the search tree
d: depth of the least-cost solution
m: maximum depth of the state space (may be +∞)
⇒ # nodes: 1 + b + b2 + ... + bm = O(bm )
Uninformed Search Strategies

 Use only the information available in the problem definition

 Different uninformed search stategies
• Breadth-first search
• Uniform-cost search
• Depth-first search
• Depth-limited search & Iterative-deepening search
 Defined by the access strategy of the frontier/fringe
(i.e. the order of node expansion)
Breadth-First Search Strategy (BFS)

 Idea: Expand first the shallowest unexpanded nodes

 Implementation: frontier/fringe implemented as a FIFO queue
⇒ novel successors pushed to the end of the queue
Breadth-First Search Strategy (BFS)
Breadth-First Search Strategy (BFS)
Breadth-First Search Strategy (BFS)
Breadth-First Search Strategy (BFS) [cont.]
BFS, Graph version (Tree version without “explored”)

Note: the goal test is applied to each node when it is generated, rather than when it is
selected for expansion ⇒ solution detected 1 layer earlier
Breadth-First Search: Tiers

State space is explored by tiers (tree version)