19CSCN1602 – Machine Intelligence

Unit –I –Session 1

Unit I : Problem Solving Agents

Topic : Define Artificial Intelligence

Senthil Prabhu S, AP(SS)/CSE

Syllabus
Unit I: Problem Solving Agents
Foundation – Agents and Environments – Nature of Environments – Structure
of agents –Problem solving agents– Measuring problem solving performance –
Informed search strategies – Greedy BFS, A* search – Local search algorithms.
Constraint satisfaction problem – Inference in CSP – Backtracking search for
CSP.
Unit II: Logical Agents
Logical agents – Propositional logic – First order logic – syntax and semantics
of FOL–Using first order logic – knowledge engineering in FOL– Inference in
FOL– Unification and Lifting – Forward and backward chaining – Resolution.
Syllabus contd

Unit III: Regression and Classification

Supervised and Unsupervised learning – Classification and Regression –
Assessing model accuracy – Simple Linear regression – Multiple linear
regression – Qualitative predictors – Extensions of the linear Model – Logistic
regression – Naïve Bayes classifier.
Unit IV : Tree Based Methods and Support Vector Machines
Decision Tree – Random Forest – Maximal margin classifier – Support vector
classifiers –Support Vector Machines (SVM) – SVMs with more than two
classes – Relationship to logistic regression.
Unit V : Resampling and Model Selection
Resampling: Cross Validation, Bootstrapping – Linear Model Selection: Subset
selection, Shrinkage methods, Dimension reduction methods – High
Dimensional data.
Course Outcomes
At the end of the unit, students will be able to:
CO1: Compare the efficiency of various searching techniques in solving a
problem

CO2: Apply inference rules to the given knowledge base for theorem proving
CO3: Utilize regression and classification algorithms for data modeling and
prediction

CO4: Model data classification using tree based methods and support vector
machines for solving multi class problems

CO5: Develop resampling and model selection methods to construct optimal

models for high dimensional data spaces
Text Books:

T1. Stuart Russell, Peter Norvig, “Artificial Intelligence– A modern Approach”, 3rd
Edition,Pearson Education,2014.
T2. James G, Witten D, Hastie T and Tibshirani R, “An Introduction to Statistical Learning
with Applications in R”, Springer,2013.
Reference Books:

R1. Ethem Alpaydin, “Introduction to Machine Learning 3e (Adaptive Computation and

Machine Learning Series)”, 3rd Edition, MIT Press, 2014.
R2. Jason Bell, "Machine learning – Hands on for Developers and Technical Professionals”,
R3. Peter Flach, "Machine Learning: The Art and Science of Algorithms that Make Sense of
Data”, Cambridge University Press, 2012.
Web References:
1. https://www.kaggle.com/kanncaa1/machine– learning– tutorial– for– beginners
2. https://nptel.ac.in/courses/106/106/106106139/
3. https://archive.ics.uci.edu/ml/datasets.php
 Unit I

Problem Solving Agents

Foundation – Agents and Environments – Nature of Environments – Structure

of agents –Problem solving agents– Measuring problem solving performance
– Informed search strategies – Greedy BFS, A* search – Local search
algorithms. Constraint satisfaction problem – Inference in CSP – Backtracking
search for CSP.
 Unit I

Problem Solving Agents

Session 1

Foundation – Agents and Environments – Nature of Environments –

Structure of agents –Problem solving agents– Measuring problem
solving performance – Informed search strategies – Greedy BFS, A*
search – Local search algorithms. Constraint satisfaction problem –
Inference in CSP – Backtracking search for CSP.
 • Describe the type and behavior for a given
CO agent.

LO • Define Artificial Intelligence

SO • Explain the categories of defining AI

Topic • Foundation
AI - Introduction
 Artificial Intelligence ?

• AI is the study of ideas that enable computers

to be intelligent
• It is the science and engineering of making
intelligent machines, especially intelligent
computer programs.
• AI is Concerned with Design of Intelligence in
an artificial device

• Computers with the ability to mimic or

duplicate the functions of the human brain
Artificial Intelligent System

The people, Procedure , Hardware, Software, Data

and Knowledge needed to develop computer systems
and machines that demonstrates the characteristics
of Intelligence

The term AI was coined by McCarthy

in 1956
Intelligence
 Definition
According to Webster’s New World Pocket Dictionary (3rd Edition),
Intelligence is defined as, “The ability to learn, or solve problems”.
In particular
• the ability to solve novel problems
• the ability to act rationally
• the ability to act like humans
Fogel in (Fogel, D. B., Evolutionary Computation: Toward a New
Philosophy of Machine Intelligence, IEEE Press, 2000) defines
Intelligence, “as the capability of a system to adapt its behavior to
meet its goal in a range of environments.”
Intelligence is the faculty of understanding
What’s involved in Intelligence?
 Ability to interact with the real world
to perceive, understand, and act
e.g., speech recognition and understanding
e.g., image understanding
e.g., ability to take actions, have an effect
 Reasoning and Planning
solving new problems, planning, and making decisions
ability to deal with unexpected problems, uncertainties
 Learning and Adaptation
we are continuously learning and adapting
our internal models are always being “updated”
e.g., a baby learning to categorize and recognize animals
What is Intelligent Behavior ?
Learn from experience
Apply knowledge acquired from experience
Handle complex situations
Solve problems when important information is Missing
Determine what is important
React quickly and correctly to a new situation
Understanding the visual images
Process and manipulate symbols
Be creative and Imaginative
Use heuristics
 Artificial Intelligence
• Definitions of artificial intelligence, organized into four categories

Thinking Humanly: Thinking Rationally:

Cognitive Modeling Logic
Acting Humanly: Acting Rationally:
Turing Test Intelligent Agents
Thinking Humanly: Cognitive Modeling

• The Exciting new effort to make computers think

• Automation of activities that we associate with human
thinking, activities such as decision making, Problem
solving , Learning.
• Learning the Working of Human Minds
• Introspection – Catch our own thoughts as they go by
• Psychological Experiments

• Cognitive science brings together theories and

experimental evidence to model internal activities of the
brain
Acting Humanly :The Turing Test Approach

• The study of how to make computers do things at which, at the

moment ,People are better.

• Alan Turing's 1950 article Computing Machinery and Intelligence

discussed conditions for considering a machine to be intelligent
• “Can machines think?”  “Can machines behave
intelligently?”
• The Turing test (The Imitation Game): Operational definition of
intelligence
Acting Humanly :The Turing Test
Approach
• Computer needs to posses:
• Natural language processing: Communicate Successfully

• Knowledge representation: to store what it knows or hears

• Automated reasoning: To use the stored information to conclude new

results

• Machine learning: To adapt to new circumstances

• Total Turing Test – Includes the video signal so that the interrogator can
test the subjects perceptual abilities
• Computer Vision

• Robotics
Thinking Rationally – Laws of Thought

Aristotle : what are correct arguments/thought processes?

• Logic Based

• Example : Socrates is a man, all men are mortal; therefore Socrates

is mortal”

• Main obstacle here – not easy to take the informal knowledge as

required by the logical notation

• Difference in solving a problem in principle and doing so in practice

Acting Rationally – The Rational Agent
Approach

• Rational behavior: Doing the right thing!

• The right thing: That which is expected to maximize the expected

return

• Advantages:

1) More general

2) Its goal of rationality is well defined

The Foundations of AI
 History of disciplines that contributed ideas, view points and techniques to AI

Disciplines Ideas taken

Philosophy Logic, methods of reasoning, mind as physical system
foundations of learning, language, rationality
Mathematics Formal representation and proof algorithms, computation,
probability
Economics utility, decision theory
Neuroscience physical substrate for mental activity
Psychology phenomena of perception and motor control,
experimental techniques
Computer building fast computers
Engineering
Control theory design systems that maximize an objective function over time

Linguistics knowledge representation, grammar

 19CSCN1602 – Machine Intelligence
Unit –I –Session 2

Unit I : Problem Solving Agents

Topic : Agents and Environments

 Unit I

Problem Solving Agents

Session 2

Foundation – Agents and Environments – Nature of Environments –

Structure of agents –Problem solving agents– Measuring problem
solving performance – Informed search strategies – Greedy BFS, A*
search – Local search algorithms. Constraint satisfaction problem –
Inference in CSP – Backtracking search for CSP.
 • Describe the type and behavior for a given
CO agent.

• Develop design principles for building

LO successful agents

SO • Explain agent and environment

Topic • Agents and Environment

Recap

• Artificial Intelligence
• Intelligence
• What’s involved in Intelligence?
• What is Intelligent Behavior ?
• Definitions of Artificial Intelligence
• The Foundations of AI
Intelligent Agents
An agent:

• Perceives its environment, through its sensors, then achieves

its goals by acting on its environment via actuators
• An agent can be
• Human-Agent
• Robotic Agent
• Software Agent
Human agent

• A human agent has eyes, ears, and other organs for sensors and hands, legs,
vocal tract, and so on for actuators.
 Robotic agent

• A robotic agent might have cameras and infrared range finders for sensors
and various motors for actuators.
 Software agent

• A software agent receives keystrokes, file contents, and network packets as

sensory inputs and acts on the environment by displaying on the screen,
writing files, and sending network packets.

• Rational Agent – is one that acts so as to achieve the best outcome or the best
expected outcome. A rational agent is one that does the right thing
Agents and Environment

Agen
Percept
t Sensors s

Environment
?
Actions
Actuato
rs
Agents and Environment
• Percept – Agent’s Perceptual input at any given time

• Percept Sequence – Complete history of everything the agent has

ever perceived
• Agent Function – Decides the Agents behavior that maps the given
percept sequence to an action –Implemented by the agent
program
• The agent function is an abstract mathematical description; the
agent program is a concrete implementation, running within some
physical system
Example : Vacuum-cleaner world

• Percepts: Location and contents, e.g., [ A, Dirty]

• Actions: Left, Right, Suck, NoOp
• Agent function: If Current square is dirty suck the dirt
otherwise move to the next square
Example : Vacuum-cleaner world

Percept Sequence Action

[ A, Clean] Right
[A ,Dirty] Suck
[ B , Clean] Left
[B ,Dirty] Suck
[ A, Clean], [ A, Clean] Right
[ A, Clean], [ A, Dirty] Suck
.
.
.
[ A, Clean], [ A, Clean],[A, Clean] Right
[ A, Clean], [ A, Clean],[A, Dirty] Suck

Partial Tabulation of a simple agent function for vacuum Cleaner world

Good Behavior

• Rational Agent – Right action is the one that make the agent to be more
successful

• Rational Depends on the following four at any time

• The performance measure that define the criterion of success

• Agents prior knowledge of the environment

• The Actions that the agents can perform

• The agents percept sequence up to date

E.g., performance measure of a vacuum-cleaner agent could be dirt

cleaned up, amount of time taken, amount of electricity consumed,
amount of noise generated, etc…
Definition of the 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 what ever the
built in knowledge the agent has
 Omniscience, learning, and autonomy

• An omniscient agent knows the actual outcome of its actions and can
act accordingly -omniscience is impossible in reality.

• Rationality maximizes expected performance, while perfection

maximizes actual performance

• information gathering-is an important part of rationality

• example of information gathering is provided by the exploration that

must be undertaken by a vacuum-cleaning agent in an initially
unknown environment.
Omniscience, learning, and autonomy

• An agent relies on the prior knowledge of its designer rather

than on its own percepts, we say that the agent lacks autonomy
• Rational agent should be autonomous
• Task environments, which are essentially the "problems" to
which rational agents are the "solutions.“
• Rationality of the simple vacuum-cleaner agent,-we had to
specify the performance measure, the environment, and the
agent's actuators and sensors. Group all these under the
heading of the task environment
Summary

• Agents and Environment

• Example : Vacuum-cleaner world
• Good Behavior
• Rational Agent
• Omniscience, learning, and autonomy
 19CSCN1602 – Machine Intelligence
Unit –I –Session 3

Unit I : Problem Solving Agents

Topic : Nature of Environments

 Unit I

Problem Solving Agents

Session 3

Foundation – Agents and Environments – Nature of Environments –

Structure of agents –Problem solving agents– Measuring problem
solving performance – Informed search strategies – Greedy BFS, A*
search – Local search algorithms. Constraint satisfaction problem –
Inference in CSP – Backtracking search for CSP.
 • Describe the type and behavior for a given
CO
agent.

• Develop design principles for building

LO
successful agents

• Summarize the PEAS description for the given

SO
task environment

Topic • Nature of Environments

The Nature of the Environment
Specifying the task environment

• PEAS – Performance measure, Environment , Actuator, Sensors

Agent Type Performance Environment Actuator Sensors
measure

Taxi Driver Safe, fast, legal, Roads, other Steering Cameras,

comfortable trip, traffic, wheel, sonar,
maximize profits pedestrians, accelerator, speedomet
customers brake, signal, er, GPS,
horn odometer,
engine
sensors,
keyboard
Examples of agent types and their PEAS
descriptions
Agent Type Performance Environment Actuator Sensors
measure

Medical Healthy Patient, hospital, Display of Keyboard entry

diagnosis patient, staff questions, of symptoms,
system reduced costs tests, findings,
diagnoses, patient's
treatments, answers
referrals
Satellite image Correct image Downlink from Display of Color pixel arrays
analysis categorization orbiting satellite scene
system categorization
Part-picking Percentage of Conveyor belt Jointed arm Camera, joint
robot parts in with parts; bins and hand angle sensors
correct bins
Examples of agent types and their PEAS descriptions

Agent Type Performance Environment Actuator Sensors

measure

Refinery Purity, yield, Refinery, Valves, pumps, Temperature,

controller safety operators heaters, pressure,
displays chemical sensors

Interactive Student's score Set of students, Display of Keyboard entry

English tutor on test testing agency exercises
suggestions,
corrections
Properties of task environments
Environment types
• Fully observable • Partially observable
• An agent can always see the • An agent can never see the
entire state of the entire state of an
environment environment
• Example: Chess • Example: Card game
Environment types
• Stochastic
• Deterministic
• A stochastic environment is
• The next state of the
random in nature and cannot
environment is completely
be determined completely by
determined by the current an agent
state and the action • Example: Ludo
executed by the agent
• Example: Tic tac toe
 Environment types
• Episodic • Sequential

• The agent's experience is divided • An agent requires memory of

into atomic "episodes“. past actions to determine the
• Only current percept is required for next best actions
the action
• The current decision could
• Each episode is independent of
affect all future decisions
each other.
• Example: Chess
• Example: part picking robot
Environment types
• Single agent • Multi agent
• only one agent is involved in • Multiple agents operating in an
an environment and operates environment
• Example: football
by itself

• Example: Maze
Environment types
• Static • Dynamic
• The environment is • The environment may change
over time
unchanged while an agent is
• Example: Taxi driving
deliberating.

• Example: Crossword
puzzle
Environment types
• Discrete
• Continuous
• The environment consists of
• The environment in which the
a finite number of actions
action performed cannot be
that can be deliberated in the
numbered ie. is not discrete
environment to obtain the
• Example: Self driving cars
output.

• Example: Chess
Environment types
• Known
• Unknown
• In a known environment, the
• In a Unknown environment, the
outcomes for all actions are
agent needs to know how it works
known to the agent.
in order to perform an action
• Example: Card game
• Example: A new video game
Properties of task environments

• The environment type largely determines the agent design

• The real world is partially observable, stochastic, sequential, dynamic,
continuous, multi-agent
Example

Task Observable Agents Deterministic Episodic Static Discrete

Environme
nt
Crossword Fully Single Deterministic Sequential Static Discrete
puzzle

Chess with a Fully Multi Deterministic Sequential Semi Discrete

clock

Taxi driving Partially Multi Stochastic Sequential Dynamic Continuous

Medical Partially Single Stochastic Sequential Dynamic Continuous

diagnosis

Part-picking Partially Single Stochastic Episodic Dynamic Continuous

robot

Interactive Partially Multi Stochastic Sequential Dynamic Discrete

English tutor
Structure of agents
Structure of the Agent

• Agent Program – Implements the agent functions-Mapping Percepts

to actions

• Agent = Program + Architecture (Computing device with physical

sensors and actuators)

• Architecture ordinary PC or robotic car with onboard computers ,

cameras and other sensors

• Agent program: current percept as input

• Agent function: entire percept history as input

Function Table Driven Agent(percept) returns an action
Persistent: Percepts, a Sequence ,initially empty table, a table of
actions, indexed by percept sequences, initially fully specified
Percept Sequence Action
append percept to the end of percept
[ A, Clean] Right
action LOOKUP(percepts , table) [A ,Dirty] Suck

[ B , Clean] Left
return action
[B ,Dirty] Suck

[ A, Clean], [ A, Right
Clean]
[ A, Clean], [ A, Dirty] Suck

.
.
.
[ A, Clean], [ A, Right
Clean],[A, Clean]
[ A, Clean], [ A, Suck
Clean],[A, Dirty]
Agent Types

• Simple Reflex Agents

• Model Based reflex Agents
• Goal- Based Agents
• Utility Based Agents
• Learning agents
Simple Reflex Agents

• Reactive: No memory
• Works based on the current percept-
Action depends only on immediate
percepts.
• Ignores the previous percept
history
• Implement by condition-action
rules
• E.g. If car in front is braking
then initiate braking
Simple Reflex Agents
function SIMPLE-REFLEX-AGENT(percept) returns an action
persistent: rules, a set of condition-action rules
state  INTERPRET-INPUT(percept)
rule  RULE-MATCH(state, rules)
action  rule.ACTION
return action
Problems faced
• Very limited intelligence
• No knowledge about the non perceptual parts of the state
• Operating in a partially observable environment infinite loops are
unavoidable Ex: car in front is braking

• To escape from infinite loops randomize its actions

• Randomized simple reflex agent outperform a deterministic simple reflex agent
Model Based Reflex Agents
• Action may depend on history or
unperceived aspects of the world.
• Need to maintain internal world
model.
• Example:
•Agent: robot vacuum cleaner
•Environment: dirty room,
furniture.
•Model: map of room, which areas
already cleaned.

• we need some information about how the world evolves independently of the
agent: Overtaking car
• we need some information about how the agent's own actions affect the world:
steering wheel clockwise
Model Based Reflex Agents

function MODEL-BASED-REFLEX-AGENT(percept) returns an action

persistent: state, the agent's current conception of the world state
model, a description of how the next state depends on current state and action
rules, a set of condition-action rules
action, the most recent action, initially none
state  UPDATE-STATE( state, action, percept, model)
rule  RULE-MATCH(state, rules)
action  RULE.ACTION
return action
Goal Based Agents
• It focuses only on reaching the goal set

• Decision took by the agent is based on how

far it is currently from their goal and

desired state

• Their every action is intended to minimize

their distance from the goal

• It is more flexible and it develops its

decision making skill by choosing the right

from the various options available

• Example:
•Agent: robot maid
•Environment: house & people.
•Goals: clean clothes, tidy room, table
laid, etc
Utility Based Agents
• Similar to goal based agent but provide
an extra component of utility
measurement which makes them
different by providing a measure of
success at a given state
• It acts based not only goals but also the
best way to achieve the goal
• It is useful when there are multiple
possible alternatives and an agent has
to choose in order to perform the best
action
• The utility function maps each state to
a real number to check how efficiently
Example
each action
Many achieves
action the goals
sequences get taxi to destination
Consider other things. How fast, how safe…..
Learning agents

• It can learn from its past

experience or it has a
learning capabilities
• It starts to act with basic
knowledge and then able
to act and adapt
automatically through
learning
Learning agents

• A learning agent has mainly four conceptual components which are

• Learning element: It is responsible for making improvements by learning from
environment
• Critic: Learning element takes feedback from critic which describes that how
well the agent is doing with respect to fixed performance standard
• Performance element: It is responsible for selecting external action
• Problem generator: It is responsible for suggesting actions that will lead to new
and informative experiences
• The learning agent are able to learn, analyze performance and look for new ways to
improve the performance
Problem solving agents
Problem solving Agent
• It is a kind of goal-based agent
• Use atomic representations -states of the world are considered
as wholes, with no internal structure visible to the problem
solving algorithms.
• Goal formulation: based on the current situation and the
agent's performance measure, is the first step in problem
solving
• Problem formulation : The process of deciding what actions
and states to consider, given a goal.
Problem solving agent

• The process of looking for a sequence of actions that reaches

the goal is called search.

• A search algorithm takes a problem as input and returns a

solution in the form of an action sequence

• Once a solution is found, the actions it recommends can be

carried out. This is called the execution phase

• Simple "formulate, search, execute" design for the agent

function SIMPLE-PROBLEM-SOLVING-AGENT(percept) returns an action
persistent: seq, an action sequence, initially empty
state, some description of the current world state
goal, a goal, initially null
problem, a problem formulation
state  UPDATE-STATE( state, percept)
if seq is empty then
goal  FORMULATE-GOAL( state)
problem  FORMULATE-PROBLEM(state, goal)
seq  SEARCH(problem)
if seq =failure then return a null action
action  FIRST(seq)
seq  REST( seq)
return action
Problem solving agent
Problem solving

• Properties of the environment

• Observable: knows the current state Ex: each city on the

map has a sign indicating its presence to arriving drivers
• Discrete: at any given state there are only finitely many
actions to choose from. Ex: each city is connected to a
small number of other cities
• Known : the agent knows which states are reached by
each action
• Deterministic :each action has exactly one outcome
Well-defined problems and solutions
• A problem can be defined formally by five components

• The initial state that the agent starts in. For example, the initial
state for our agent in Romania might be described as In(Arad).
• A description of the possible actions available to the agent. For
example, from the state In(Arad), the applicable actions are

{ Go(Sibiu), Go( Timisoara ), Go(Zerind)}.

Well-defined problems and solutions
• Transition model, specified by a function RESULT(s, a)
Ex: RESULT(In(Arad), Go(Zerind)) = In(Zerind) .
Transition model implicitly define the state space of the problem
• The state space is the set of all states reachable from the initial
state.
• It forms a graph (or map) in which the nodes are states and the
arcs between nodes are actions.
• A path in the state space is a sequence of states connected by a
sequence of actions.
• The solution of the problem is part of the map formed by the
state space
•
Well-defined problems and solutions

• The goal test: which determines whether a given state is a

goal state
• A path cost function that assigns a numeric cost to each path
• A solution to a problem is an action sequence that leads from
the initial state to a goal state
• Solution quality is measured by the OPTIMAL solution path
cost function, and an optimal solution has the lowest path
cost among all solutions.
Example Toy problems

The state space for the vacuum world

Toy problems

• States: The state is determined by both the agent location and the dirt
locations. There are 2 x 22 = 8 world states . In general for n locations

(n.2 n)possible world states

• Initial state: Any state can be designated as initial state

• Actions: each state has just three actions: Left, Right, and Suck.

• Transition model: The actions have their expected effects

• Goal Test: This checks whether all the squares are clean

• Path cost: Each step costs 1, so the path cost is the number of steps in the
path
Measuring problem solving performance
Measuring problem solving performance

• Strategies are evaluated along the following dimensions:

• completeness: does it always find a solution if one exists?

• time complexity: How long does it take to find a solution?
• space complexity: How much memory is needed to perform the search?
• 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 ∞)

• Total cost=search cost(time for search)+path cost(length of the path)

Example
Example: holiday in Romania
• On holiday in Romania; currently in Arad

• Flight leaves tomorrow from Bucharest at 13:00

• Let’s configure this to be an AI problem

Romania
• What’s the problem?
• Accomplish a goal
• Reach Bucharest by 13:00
• So this is a goal-based problem

• What’s an example of a non-goal-based problem?

• Live long and prosper
• Maximize the happiness of your trip to Romania
• Don’t get hurt too much

• What qualifies as a solution?

• You can/cannot reach Bucharest by 13:00

• The actions one takes to travel from Arad to Bucharest along the shortest
(in time) path
Romania

• What additional information does one need?

• A map
More concrete problem definition

A state space Which cities could you be in?

An initial state Which city do you start from?

A goal state Which city do you aim to reach?

When in city foo, the following

A function defining state transitions
cities can be reached

A function defining the “cost” of a How long does it take to travel

state sequence through a city sequence?
Informed search algorithms
 Informed search strategies
• Informed search strategy--one that uses problem-specific knowledge
beyond the definition of the problem itself

• can find solutions more efficiently than can an uninformed strategy.

• Idea: use an evaluation function f(n) for each node

• estimate of "desirability"

• Expand most desirable unexpanded node

• greedy best-first search

• Tries to expand the node that is closest to the goal

• Evaluation function f(n) = h(n) (heuristic)

• A* search
Heuristic Function

• Heuristics is a method of problem-solving where the goal is to

come up with a workable solution in a feasible amount of time.

• Heuristic techniques strive for a rapid solution that stays within an

appropriate accuracy range rather than a perfect solution.

• A heuristic is a function that determines how near a state is to the

desired state.
Example :greedy best-first search

Romania with step costs in km

Values of hSLD-straight-line distances to Bucharest
Greedy best-first search example
Greedy best-first search example
Greedy best-first search example
Greedy best-first search example
 Properties of greedy best-first search
• Complete? No – can get stuck in loops, e.g., Iasi  Neamt  Iasi  Neamt 

• Worst case Time and space complexity is O(bm), but a good heuristic can give
dramatic improvement

• Optimal? No
A* Search
A* search

• form of best-first search

• Idea: avoid expanding paths that are already expensive

• Evaluation function f(n) = g(n) + h(n)

• g(n) = cost so far to reach n

• h(n) = estimated cost from n to goal

• f(n) = estimated total cost of path through n to goal

A* search example
A* search example
A* search example
A* search example
A* search example
A* search example
A* search example

Open List:
Arad

We start with our initial state Arad. We make a node and add it to the open
list. Since it’s the only thing on the open list, we expand the node.
Think of the open list as a priority queue (or heap) that sorts the nodes
inside of it according to their g()+h() score.
A* search example

Open List:
Sibiu
Timisoara
Zerind

We add the three nodes we found to the open list.

We sort them according to the g()+h() calculation.
A* search example

Open List:
Rimricu Vicea
Fagaras
Timisoara
We’ve been to
Zerind
Arad before.
Arad Don’t list it
again on the
Oradea open list.

When we expand Sibiu, we run into Arad again. But we’ve already
expanded this node once; so, we don’t add it to the open list again.
A* search example

Open List:
Rimricu Vicea
Fagaras
Timisoara
Zerind
Oradea

We see that Rimricu Vicea is at the top of the open list; so, it’s the next
node we will expand.
 A* search example

Open List:
Fagaras
Pitesti
Timisoara
Zerind
Craiova
Sibiu
Oradea

When we expand Rimricu Vicea, we run into Sibiu again.

But we’ve already expanded this node once; so, we don’t add it to the open
list again.
A* search example

Open List:
Fagaras
Pitesti
Timisoara
Zerind
Craiova
Oradea

Fagaras will be the next node we should expand – it’s at the top of the
sorted open list.
A* search example

Open List:
Pitesti
Timisoara
Zerind
Bucharest
Craiova
Sibiu
Oradea

When we expand Fagaras, we find Sibiu again. We don’t add it to the open
list.
We also find Bucharest, but we’re not done. The algorithm doesn’t end
until we “expand” the goal node – it has to be at the top of the open list.
A* search example

Open List:
Pitesti
Timisoara
Zerind
Bucharest
Craiova
Oradea

It looks like Pitesti is the next node we should expand.

A* search example

Open List:
Bucharest
Timisoara
Zerind
Craiova
Rimricu Vicea
Oradea

We just found a better value for Bucharest; so, it got moved higher in the
list. We also found a worse value for Craiova – we just ignore this.
And of course, we ran into Rimricu Vicea again. Since it’s already been
expanded once, we don’t re-add it to the Open List.
A* search example

Open List:
Bucharest
Timisoara
Zerind
Craiova
Oradea

Now it looks like Bucharest is at the top of the open list…

Properties of A*

• Complete? Yes (unless there are infinitely many nodes with f ≤ f(G) , i.e. step-
cost > ε)

• Time/Space? Exponential: bd
| h(n)  h * (n) |O (logh * (n))
except if:

• Optimal? Yes

• Optimally Efficient: Yes (no algorithm with the

same heuristic is guaranteed to expand fewer nodes)

Local search algorithms
Local search algorithms

In many optimization problems, the path to the goal is irrelevant; the

goal state itself is the solution

• State space = set of "complete" configurations

• Find configuration satisfying constraints, e.g., n-queens

• In such cases, we can use local search algorithms

• keep a single "current" state, try to improve it

• Local search
• Keep track of single current state
• Move only to neighboring states
• Ignore paths
Local search and optimization
• Advantages:
• Use very little memory
• Can often find reasonable solutions in large or infinite (continuous)
state spaces.
• “Pure optimization” problems
• All states have an objective function
• Goal is to find state with max (or min) objective value
• Does not quite fit into path-cost/goal-state formulation
• Local search can do quite well on these problems.
• A complete local search algorithm always finds a goal if one exists;
• an optimal algorithm always finds a global minimum/maximum
Example: n-queens

• Put n queens on an n × n board with no two queens on the same row,

column, or diagonal
“Landscape” of search

A landscape has both location(defined by the state) and elevation(defined

by the value of the heuristic cost function or objective function)
If elevation corresponds
• to cost find a global minimum
• to an objective function find global maximum
Hill-climbing search

• The hill-climbing search algorithm is simply a loop that continuously moves in

the direction of increasing value
• terminates when a peak is reached
• greedy local search
• Value can be either
• Objective function value
• Heuristic function value (minimized)
• Hill climbing does not look ahead of the immediate neighbors of the current
state.
• Can randomly choose among the set of best successors, if multiple have the best
value
• Characterized as “trying to find the top of Mount Everest while in a thick fog”
Hill-climbing search
• "Like climbing Everest in thick fog with amnesia”
function HILL-CLIMBING(problem) returns a state that is a local maximum
current  MAKE-NODE(problem . lNITIAL_STATE)
loop do
neighbor  a highest-valued successor of current
if neighbor. VALUE <= current. VALUE then return current.STATE
current  neighbor
Hill-climbing search
Hill-climbing search: 8-queens problem

• h = number of pairs of queens that are attacking each other, either directly or indirectly

• h = 17 for the above state

Hill-climbing search: 8-queens problem

• heuristic cost estimate h = 17 • A local minimum with h = 1

 Problems of hill climbing

• Depending on initial state, can get stuck in local maxima

• Ridge: Sequence of local maxima difficult for greedy algorithms to navigate

• Plateau: a flat area of the state-space landscape. It can be a flat local maximum,
from which no uphill exit exists, or a shoulder, from which progress is possible
Performance of hill-climbing on 8-queens

• Randomly generated 8-queens starting states

• 14% the time it solves the problem

• 86% of the time it get stuck at a local minimum

• However…

• Takes only 4 steps on average when it succeeds

• And 3 on average when it gets stuck

• (for a state space with ~17 million states)

Possible solution…sideways moves

• If no downhill (uphill) moves, allow sideways moves in hope that algorithm

can escape
• Need to place a limit on the possible number of sideways moves to avoid
infinite loops

• For 8-queens

• Now allow sideways moves with a limit of 100

• Raises percentage of problem instances solved from 14 to 94%

• However….

• 21 steps for every successful solution

• 64 for each failure

Hill-climbing variations

• Stochastic hill-climbing

• Random selection among the uphill moves.

• The selection probability can vary with the steepness of the uphill
move.

• First-choice hill-climbing

• stochastic hill climbing by generating successors randomly until a

better one is found

• Useful when there are a very large number of successors

• Random-restart hill-climbing
• It conducts a series of hill-climbing searches from randomly generated
initial states

• Tries to avoid getting stuck in local maxima.

Simulated annealing search
• Idea: escape local maxima by allowing some "bad" moves but
gradually decrease their frequency
Physical Interpretation of Simulated
Annealing

• A Physical Analogy:
• imagine letting a ball roll downhill on the function surface
• this is like hill-climbing (for minimization)
• now imagine shaking the surface, while the ball rolls, gradually
reducing the amount of shaking
• this is like simulated annealing
• Annealing = physical process of cooling a liquid or metal until particles
achieve a certain frozen crystal state
• simulated annealing:
• free variables are like particles
• seek “low energy” (high quality) configuration
• get this by slowly reducing temperature T, which particles
move around randomly
Search using Simulated Annealing
• Simulated Annealing = hill-climbing with non-deterministic search
• Basic ideas:
• like hill-climbing identify the quality of the local improvements
• instead of picking the best move, pick one randomly
• say the change in objective function is d
• if d is positive, then move to that state
• otherwise:
• move to this state with probability proportional to d
• thus: worse moves (very large negative d) are executed less often
• however, there is always a chance of escaping from local maxima
• over time, make it less likely to accept locally bad moves
• (Can also make the size of the move random as well, i.e., allow “large”
steps in state space)
Properties of simulated annealing search

One can prove: If T decreases slowly enough, then simulated annealing

search will find a global optimum with probability approaching 1
• Widely used in VLSI layout, airline scheduling, etc
Local beam search
• Keep track of k states instead of one

• Initially: k randomly selected states

• Next: determine all successors of k states

• If any of successors is goal  finished

• Else select k best from successors and repeat.

• Major difference with random-restart search

• Information is shared among k search threads.

• Can suffer from lack of diversity.

• Stochastic beam search

• choose k successors proportional to state quality.

Genetic algorithms

• A Genetic algorithm is a search technique used to find true or

approximate solutions
• Genetic algorithms are categorized as global search heuristics
• GAs are particular class of evolutionary algorithms that use
techniques inspired by evolutionary biology such as
inheritance ,mutation , selection and crossover
• The evolution usually starts from a population of randomly
generated individuals and happens in generations
Genetic algorithms

• The evolution usually starts from a population of randomly generated

individuals and happens in generations
• In each generation, the fitness of every individual in the population is
evaluated
• Multiple individuals are selected from the current population(based
on their fitness),and modified(recombined and possibly mutated) to
form a new population
• The new population is then used in the next iteration of the algorithm
Genetic algorithms

• The algorithm terminates when

• Either a maximum number of generations has been produced
• Or a satisfactory fitness level has been reached for the
population
• Steps in GA
• Select initial population
• Fitness function
• Parent selection
• Crossover
• Mutation
Genetic algorithms
• Different approach to other search algorithms
• A successor state is generated by combining two parent states
• A state is represented as a string over a finite alphabet (e.g. binary)
• 8-queens
• State = position of 8 queens each in a column
=> 8 x log(8) bits = 24 bits (for binary representation)
• Start with k randomly generated states (population)
• Evaluation function (fitness function).
• Higher values for better states.
• Opposite to heuristic function, e.g., # non-attacking pairs in 8-queens
• Produce the next generation of states by “simulated evolution”
• Random selection
• Crossover
• Random mutation
Genetic algorithms

4 states for 2 pairs of 2 states randomly New states Random

8-queens selected based on fitness. after crossover mutation
problem Random crossover points applied
selected

Fitness function: number of non-attacking pairs of queens (min = 0, max = 8 × 7/2 = 28)
24/(24+23+20+11) = 31%
23/(24+23+20+11) = 29% etc
Genetic algorithms
Cross over

327 52411 247 48552 32748552

Genetic algorithm pseudocode

function GENETIC_ALGORITHM( population, FITNESS-FN) return an

individual
input: population, a set of individuals
FITNESS-FN, a function which determines the quality of the
individual
repeat
new_population  empty set
loop for i from 1 to SIZE(population) do
x  RANDOM_SELECTION(population, FITNESS_FN)
y  RANDOM_SELECTION(population,
FITNESS_FN)
child  REPRODUCE(x,y)
if (small random probability) then child  MUTATE(child
)
add child to new_population
population  new_population
Constraint Satisfaction Problem(CSP)
Definition of CSP
• A constraint satisfaction problem consists of three components, X, D ,
and C:
• X is a set of variables, { X1, . . . , Xn}.

• D is a set of domains, { D1, . . . , Dn}, one for each variable.

• C is a set of constraints that specify allowable combinations of
values.
• Each domain Di consists of a set of allowable values, {v1, . . . , vk} for

variable Xi

• Each constraint Ci consists of a pair (scope, rel), where scope is a tuple

of variables that participate in the constraint and rel is a relation that
defines the values that those variables can take on
Definition of CSP
• State is defined by variables xi with values from domain di
• Goal test is a set of constraints specifying allowable combinations of
values for subsets of variables
• An assignment that does not violate any constraints is called
consistent or legal assignment
• A complete assignment is the one in which every variable is
mentioned and the solution to the CSP is a complete assignment
that satisfies all the constraints
• A partial assignment is one that assigns values to only some of the
variables
• CSP require a solution that maximizes an objective function
Example: Map-Coloring

• Variables X={WA, NT, Q, NSW, V, SA, T }

• Domain of each variable is the set Di = { red, green, blue}
• Constraints: adjacent regions must have different colors
• C = {SA ≠ WA, SA ≠ NT, SA ≠Q, SA ≠ NSW, SA ≠ V, WA ≠ NT, NT ≠ Q, Q ≠
NSW, NSW ≠ V}
• SA ≠ WA = {(red, green),(red, blue),(green, red), (green, blue),(blue,
red),( blue, green)}
Example: Map-Coloring

• Solutions are complete and consistent assignments,

• e.g., WA = red, NT = green, Q = red ,NSW = green, V = red , SA = blue, T
= green
Constraint graph

• Visualization of CSP – Constraint Graph

• Binary CSP: each constraint relates two variables
• Constraint graph: nodes are variables, arcs are constraints
Varieties of CSPs
• Discrete variables
• finite domains:
• n variables, domain size d  O(dn) complete assignments
• Eg 8 Queens Problem ( Variables, Domain ? )
• Boolean CSP
• infinite domains:
• integers, strings, etc.
• e.g., job scheduling, variables are start/end days for each job, Values integer
numbers ( infinite)
• need a constraint language, e.g., StartJob1 + 5 ≤ StartJob3
• Continuous variables
• e.g., start/end times for Hubble Space Telescope observations
• linear constraints solvable in polynomial time by linear programming
Varieties of constraints

• Unary constraints involve a single variable

• e.g., SA ≠ green
• Binary constraints involve pairs of variables
• e.g., SA ≠ WA
• Higher-order constraints involve 3 or more variables
• e.g., cryptarithmetic column constraints( auxiliary variables,
Constraint HyperGraph, Alldiff constraint)
• Preferences (soft Constraints) - e g. Red is better than green
• Often representable by a cost for each variable assignment
• Constraint optimization problems
Real-world CSPs

• Assignment problems
• e.g., who teaches what class
• Timetabling problems
• e.g., which class is offered when and where?
• Transportation scheduling
• Factory scheduling
• Notice that many real-world problems involve real-valued
variables
• Optimization search methods – Local Search CSP
Inference in CSP
Inference in CSP
• In CSPs there is a choice: an algorithm can search or do a specific type
of inference called constraint propagation
• using the constraints to reduce the number of legal values for a
variable, which in turn can reduce the legal values for another
variable, and so on
• It may be done as a preprocessing step, before search starts
• Different types of local consistency
• Node consistency
• Arc consistency
• Path consistency
• K-consistency
• Global constraints
Node consistency

• A single variable (corresponding to a node in the CSP network) is

node-consistent if all the values in the variable's domain satisfy the
variable's unary constraints
• For example, in the variant of the Australia map-coloring problem
where South Australians dislike green, the variable SA starts with
domain {red, green, blue}
• we can make it node consistent by eliminating green, leaving SA
with the reduced domain {red, blue}.
Path consistency
• Path consistency tightens the binary constraints by using implicit
constraints that are inferred by looking at triples of variables.

• A two-variable set {Xi, Xj} is path-consistent with respect to a third

variable Xm if, for every assignment {Xi, = a, Xj = b} consistent with

the constraints on {Xi, Xj}, there is an assignment to Xm that

satisfies the constraints on {Xi, Xm} and {Xm, Xj }.

• Example: Map coloring with two color

Global constraints

• Global constraint is one involving an arbitrary number of

variables

• Global constraints occur frequently in real problems and can

be handled by special-purpose algorithms that are more
efficient than the general-purpose methods described so far.

• If m variables are involved in the constraint, and if they have n

possible distinct values altogether, and m > n, then the
constraint cannot be satisfied
Backtracking search for CSP
Backtracking search

• Variable assignments are commutative, i.e.,

[ WA = red then NT = green ] same as [ NT = green then WA = red ]
• Only need to consider assignments to a single variable at each node
• Depth-first search for CSPs with single-variable assignments and
backtracks when a variable has no legal values left to assign is called
backtracking search
• Backtracking search is the basic uninformed algorithm for CSPs
• Can solve n-queens
Backtracking search
Backtracking example
Backtracking example
Backtracking example
Backtracking example
Improving backtracking efficiency

• General-purpose methods can give huge gains in speed:

• Which variable should be assigned next?

• In what order should its values be tried?

• Can we detect inevitable failure early?

Variable and Value ordering

• Variable and Value ordering

varSelect_Unassigned_Variable(Variables[csp],assignment, csp)

• Example : WA=red NT=green then there is one possible value for

SA , if SA=blue, choices for all other variables Q,NSW,V are all
forced
Most constrained variable

MCV choose the variable with the fewest legal values

• Minimum Remaining Values (MRV) heuristic also called

“Most Constrained variable” or “ fail heuristic”
• It selects the variable that is most likely to cause a failure
Most constrained variable
• Tie-breaker among most constrained variables
• Most constraining variable:
• choose the variable with the most constraints on remaining
variables
Least constraining value
• Given a variable, choose the least constraining value:
• the one that rules out the fewest values in the
remaining variables
Forward checking

• Idea:
• Keep track of remaining legal values for unassigned
variables
• Terminate search when any variable has no legal values
Forward checking
Forward checking
Forward checking

Domains
After WA
After Q
After V
Constraint propagation
• Forward checking propagates information from assigned to
unassigned variables, but doesn't provide early detection for all
failures:

NT and SA cannot both be blue!

• Constraint propagation repeatedly enforces constraints locally
Arc consistency

• A variable in a CSP is arc-consistent if every value in its domain

satisfies the variable's binary constraints

• X Y is consistent iff for every value x of X there is some allowed y

Arc consistency

• Simplest form of propagation makes each arc consistent

• X Y is consistent iff for every value x of X there is some
allowed y

• If X loses a value, neighbors of X need to be rechecked

Arc consistency
Arc consistency detects failure earlier than forward checking
• Can be run as a preprocessor or after each assignment
•
Arc consistency algorithm AC-3
K-consistency

• Stronger forms of propagation can be defined with the notion of k-

consistency
• A CSP is k-consistent if, for any set of k - 1 variables and for any
consistent assignment to those variables, a consistent value can
always be assigned to any kth variable
• 1-consistency means that each individual variable by itself is
consistent
• 2-Consistency is same as arc consistency
• 3-consistency means that any pair of adjacent variables can always
be extended to the third neighboring variable –path consistency
• Handling Special Constraints
• Types of constraints in real problem
• All diff constraints – variables should have distinct
values
( inconsistent m >n if m- variables , n- values)
• Simple Algorithm:
• Remove any variable that has singleton domain and
delete the variable’s value from the domain of
remaining variables
• Helps to detect inconsistency
• Resource Constraint
• Atmost constraint ex. PA1…. PA4 denotes no. of persons
assigned to each of 4 tasks
• atmost(10,PA1,PA2,PA3,PA4)
• domain {3,4,5,6} isolates the constraint
• If each Var has domain { 2,3,4,5,6} can delete max values
5,6 from each domain
• {4,2,2,2} consistent
Intelligent Backtracking

• Intelligent Backtracking
• Normally chronological backtracking – when a branch of
search fails – back up to the preceding variable and try a
diff. value for it
• Variable ordering  Q,NSW,V,T,SA,WA,NT
• Assignment
{ Q=RED,NSW=GREEN,V=BLUE,T=RED}
Next SA –any value violates constraint
Backtracking – value of T to be changed –it cannot resolve
• A more intelligent approach to backtrack to all the way
back to one of the set of variables that caused the failure –
Conflict set-set of previously assigned variables that are
connected to x by constraint
• For SA conflict set { Q,NSW,V}
• Backjumping method backtracks to the most recent
variable in the conflict set  jumps to V
• Can be added to forward checking
• Called “ Conflict Directed backjumping”
Reference(s):

T1. Stuart Russell, Peter Norvig, “Artificial Intelligence– A

modern Approach”, 3rd Edition,Pearson Education,2014..