Artifical Intelligence

Dr Abhishek Mukhopadhyay
Assistant Professor, Amity University
(Ex Manager, Ashok Leyland || PostDoc, IISc)
Copyright: Dr Abhishek Mukhopadhyay
Module I : Scope of AI &
Problem Solving

Copyright: Dr Abhishek Mukhopadhyay

Copyright: Dr Abhishek Mukhopadhyay

What is AI
• Top are concerned with thought
processes and reasoning,
• Bottom address behavior.

• Left measure success in terms of fidelity

to human performance,
• Right one measure against an ideal
performance measure, called rationality
Copyright: Dr Abhishek Mukhopadhyay

Acting Humanly,
Thinking Humanly
• Turing test is based on a party game "Imitation
game,"
• This game involves three players
• One player is Computer,
• Another player is human responder, and
• Third player is a human Interrogator, who is
isolated from other two players
• His job is to find that which player is machine among
two of them
• if an interrogator would not be able to identify which
is a machine and which is human, then the computer
passes the test successfully, and the machine is said
to be intelligent and can think like a human
 Foundation of AI
Philosophy Neuroscience
• Can formal rules be used to draw valid conclusions? • How do brains process information?
• How does the mind arise from a physical brain?

Mathematics Computer engineering

• What are the formal rules to draw valid conclusions? • How can we build an efficient computer?
• What can be computed?
• How do we reason with uncertain information?

Economics Control theory and cybernetics

• How should we make decisions so as to maximize payoff? • How can artifacts operate under their own control?
• How should we do this when others may not go along?

Copyright: Dr Abhishek Mukhopadhyay

COPYRIGHT: DR ABHISHEK MUKHOPADHYAY
 Application of AI
Copyright: Dr Abhishek Mukhopadhyay
Optical character recognition (OCR)
Technology to convert scanned docs to text
• If you have a scanner, it probably came with OCR software

Digit recognition, AT&T labs License plate readers

[Link] [Link]
Face detection

• Many new digital cameras now detect faces

– Canon, Sony, Fuji, …
Smile detection

Sony Cyber-shot® T70 Digital Still Camera

3D from thousands of images

Building Rome in a Day: Agarwal et al. 2009

Object recognition (in supermarkets)

LaneHawk by EvolutionRobotics
“A smart camera is flush-mounted in the checkout lane, continuously
watching for items. When an item is detected and recognized, the
cashier verifies the quantity of items that were found under the basket,
and continues to close the transaction. The item can remain under the
basket, and with LaneHawk,you are assured to get paid for it… “
Copyright: Dr Abhishek Mukhopadhyay
Vision-based biometrics

“How the Afghan Girl was Identified by Her Iris Patterns” Read the story
wikipedia
Application

14
Copyright: Dr Abhishek Mukhopadhyay
Copyright: Dr Abhishek Mukhopadhyay

Agents and
Environments
• Agent is anything that can be viewed
as perceiving its environment through
sensors and acting upon that
environment through actuators
• Percept to refer to the agent’s
perceptual inputs at any given instant
• Mathematically, we say that an
agent’s behavior is described by the
agent function that maps any given Figure: Agents interact with environments through
percept sequence to an action sensors and actuators
 How an agent works
Copyright: Dr Abhishek Mukhopadhyay
 Problem solving agents
• 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
• Given a particular state s,
ACTIONS(s) returns the set of actions
that can be executed in s
• For example, from the state In(Arad),
the applicable actions are {Go(Sibiu),
Go(Timisoara), Go(Zerind)}

Copyright: Dr Abhishek Mukhopadhyay

 Problem solving agents
• A problem can be defined formally by
five components:
• A description of what each action
does; the formal name for this is the
transition model, specified by a
function RESULT(s, a), s: current
state, a: action
RESULT(In(Arad),Go(Zerind)) =
In(Zerind)
• The goal test, which determines
whether a given state is a goal state
• Here, goal in Romania is the
singleton set {In(Bucharest )}
• A path cost function that assigns a
numeric cost to each path
Copyright: Dr Abhishek Mukhopadhyay
 Do it Yourself
• 8 Queen Problem
• States: Any arrangement of 0 to 8 queens on the board is a
state

• Initial state: No queens on the board.

• Actions: Add a queen to any empty square.

• Transition model: Returns the board with a queen

added to the specified square.

• Goal test: 8 queens are on the board, none attacked.

Copyright: Dr Abhishek Mukhopadhyay

Searching for solutions
• Solution is an action sequence
• Search algorithms work by considering
various possible action sequences
• Form a search tree
• Initial state at root ( In(Arad) )
• Apply each legal action to the current
state
• thereby generating a new set of
states
• In(Sibiu), In(Timisoara), and
In(Zerind).
• Choose which of these three
possibilities to consider further
Copyright: Dr Abhishek Mukhopadhyay
Copyright: Dr Abhishek Mukhopadhyay

• Define the problem accurately including detailed

specifications and what constitutes a suitable
Problems, solution

Problem • A ‘problem space’ is an abstract space.

• encompasses all valid states that can be generated
Spaces and by the application of any combination of operators
on any combination of objects
Search • Example: Tic-Tac-Toe, Missionaries and Cannibals
• A search refers to the search for a solution in a problem
space
• Search proceeds with different types of ‘search
control strategies’
• Example: Depth First Search, Breadth First Search
 • Three missionaries and three cannibals wish to cross a
river using a two person boat. If at any time the
cannibals outnumber the missionaries on either side of
Example: the river, they will eat the missionaries. How can a
sequence of boat trips be performed that will get
Missionaries everyone to the other side of the river without any
missionaries being eaten?
and Cannibals State representation:
• BOAT position: original (T) or final (NIL) side of the river.
• Number of Missionaries and Cannibals on the original
side of the river.
• Start is (T 3 3); Goal is (NIL 0 0).

Copyright: Dr Abhishek Mukhopadhyay

Example: Missionaries and Cannibals

• Operators • Search Graph

Copyright: Dr Abhishek Mukhopadhyay

 • A heuristic is a technique that is used to solve a problem
faster than the classic methods

• These techniques are used to find the approximate

solution of a problem when classical methods do not

• Heuristics are said to be the problem-solving

techniques that result in practical and quick solutions
Heuristic AI
• Heuristics are strategies that are derived from past
experience with similar problems

• Heuristics use practical methods and shortcuts used to

produce the solutions that may or may not be optimal,
but those solutions are sufficient in a given limited
timeframe

Copyright: Dr Abhishek Mukhopadhyay

Why do we need heuristics?

Copyright: Dr Abhishek Mukhopadhyay

Heuristic Search Methods

Copyright: Dr Abhishek Mukhopadhyay

Different Search Algorithms

Copyright: Dr Abhishek Mukhopadhyay

Copyright: Dr Abhishek Mukhopadhyay

• Uninformed search (also called blind search)

• Strategies have no additional information about
states beyond that provided in the problem
definition
Search • Generate successors and distinguish a goal state
from a non-goal state
Strategies • Example: BFS, DFS
• Informed search or heuristic search
• Know whether one non-goal state is “more
promising” than another
• Example: Best Fast Search, A* search
 • A traversing algorithm used in tree and graph-like data
structures

Depth First • Starts by exploring the deepest node in the frontier

• Starting at the root node, the algorithm proceeds to
Search (DFS) search to the deepest level of the search tree until
nodes with no successors are reached
• DFS is not cost-optimal since it doesn't guarantee to
find the shortest paths

Copyright: Dr Abhishek Mukhopadhyay

Example of DFS
Time complexity

• DFS traverses each

vertex and edge exactly
once in the worst-case
scenario

• The time complexity of

DFS is O(|V| + |E|)

Traversed Path: A – B – D – E – C – F - G

Copyright: Dr Abhishek Mukhopadhyay

Do it yourself !
• Apply DFS to find the search space to reach M

Copyright: Dr Abhishek Mukhopadhyay

Copyright: Dr Abhishek Mukhopadhyay

• Operates solely based on the connectivity of nodes

• Doesn't prioritize any particular path over another based
on heuristic knowledge or domain-specific information
Breadth First • It starts at the root node, expands all of its successors

Search (BFS) • Systematically explores all its neighboring nodes before

moving to the next level of nodes
• BFS always aims to find a solution with a minimum cost
prioritizing the shortest path, said to be a cost-optimal
solution
Example of BFS
Time complexity

• The time complexity of

BFS is O(|V| + |E|)

Traversed Path: A – B – C – D – E – F - G
Copyright: Dr Abhishek Mukhopadhyay
 Do It Yourself

Show output of both DFS and BFS

DFS: 0 -1 – 2 – 4 - 3 BFS: 0 -1 – 2 – 3 - 4
Copyright: Dr Abhishek Mukhopadhyay
Uniform Cost Search
• Unlike BFS or DFS, UCS considers the
cost of route
• Achieves the optimal solution with the
lowest cost
• Check the least cost to go to next node if
there are multiple paths
• Finite states and absence of loops make
UCS complete
• If each transition are of same cost, it is
similar to BFS

Copyright: Dr Abhishek Mukhopadhyay

Iterative Deepening
Depth-First Search
• Performs a depth-first search to level 1,
then restarts, completes a depth-first
search to level 2
• Continue until reach to goal state
• Generates a node once all the lower
nodes have been produced
• Algorithm terminates at depth d when
goal node is found 1st Iteration : A
2nd Iteration : A, B, C
3rd Iteration : A, B, D, E, C, F, G

Copyright: Dr Abhishek Mukhopadhyay

Time and Space Complexity

Copyright: Dr Abhishek Mukhopadhyay

Best First Search
• Both BFS and DFS blindly explore paths without considering any
cost function
• Best First Search use an evaluation function to decide which
adjacent is most promising and then explore
• Falls under the category of Heuristic Search or Informed Search
• Use a priority queue to store costs of nodes

Copyright: Dr Abhishek Mukhopadhyay

Best First Search
• Create 2 empty lists: OPEN and CLOSED
• Start from the initial node (say N) and put in the ‘ordered’ OPEN list
• Repeat the next steps until GOAL node is reached or OPEN list is empty
• Select the best node (say N) in the OPEN list and move it to the CLOSED list.
Also, capture the information of the parent node
• If N is GOAL node, then exit the loop returning “True”. The solution can be found
by backtracking the path
• If N is not GOAL node, expand node N to generate the ‘immediate’ next node
linked to N and add those to the OPEN list
• Reorder the nodes in the OPEN list in ascending order

Copyright: Dr Abhishek Mukhopadhyay

 S 10

Best First Search B

A C
7 8
Open Closed
9

Node H(n) Node Parent

S 10 D H
8 6

Open Closed Open Closed

Node H(n) Node Parent Node H(n) Node Parent F G 3

A 9 S B 7 S 6
B 7 C 8

C 8 A 9
E
0

Copyright: Dr Abhishek Mukhopadhyay

 S 10

Best First Search 9

B
A C
7 8
Open Closed Open Closed

Node H(n) Node Parent Node H(n) Node Parent

8
C 8 S H 6 S H
D 6
A 9 B S C 8 B S

D 8 D 8

H 6 A 9 F G 3
6

E
0

Copyright: Dr Abhishek Mukhopadhyay

 S 10

Best First Search 9

B
A C
7 8
Open Closed Open Closed

Node H(n) Node Parent Node H(n) Node Parent

8
C 8 S G 3 S H
D 6
D 8 B S F 6 B S

A 9 H B C 8 H B

F 6 D 8 F G 3
G 3 A 9 6

E
0

Copyright: Dr Abhishek Mukhopadhyay

 S 10

Best First Search 9

B
A C
7 8
Open Closed Open Closed

Node H(n) Node Parent Node H(n) Node Parent

8
F 6 S E 0 S H
D 6
C 8 B S F 6 B S

D 8 H B C 8 H B

A 9 G H D 8 G H F G 3
E 0 A 9 E H 6

S B H G E E
0

Copyright: Dr Abhishek Mukhopadhyay

Copyright: Dr Abhishek Mukhopadhyay

• The worst-case time complexity for Best First Search is

O(n * Log n)
• where n is number of nodes
• In worst case, we may have to visit all nodes before
we reach goal.
Analysis of
Time • Note that priority queue is implemented using Min(or
Max) Heap and insert and remove operations take O(log
n) time.

• Performance of the algorithm depends on how well the

cost or evaluation function is designed.
Copyright: Dr Abhishek Mukhopadhyay

• It evaluates nodes by combining

• g(n) – the cost to reach the node
• h(n) – the cost to get from node to
the goal
f(n) = g(n) + h(n)
A* Search : • Since
Minimizing total • g(n) gives path cost from the start
node to node n
estimated cost • h(n) is the estimated cost of the
cheapest path from n to the goal, we
have

f(n) = estimated cost of the cheapest

solution through n
A* Search : Minimizing total estimated cost

• To find the cheapest solution, first try the node with lowest value of g(n) + h(n)
• This strategy is more reasonable provided that the heuristic function h(n) satisfies
certain conditions
• A* search is both complete and optimal

Admissible Heursitic
• A* is optimal if h(n) is an admissible heuristic that is, provided h(n) never
overestimates the cost to reach the goal
• Admissible heuristics are by nature optimistic, because they think the cost of solving
the problem is always less than it actually is
• There occurs the consequence
• f(n) never overestimates the true cost of a solution through n

Copyright: Dr Abhishek Mukhopadhyay

A* Search : Minimizing
total estimated cost

Copyright: Dr Abhishek Mukhopadhyay

A* Search : Minimizing
total estimated cost

Copyright: Dr Abhishek Mukhopadhyay

A* Search : Minimizing
total estimated cost

Copyright: Dr Abhishek Mukhopadhyay

Points to note

• Bucharest first appears on the fringe step (e)

• But it is not selected for expansion because its f-cost (450) is higher than that of
Pitesti (417)
• That means there might be a solution through Pitesti whose cost is as low as 417
• So, the algorithm is not settled for a solution that costs 450
• It will repeat the iterations, or it will keep expanding the nodes of OPEN list until it
finds a minimum cost of the entire nodes of OPEN LIST
• From the example we can extract a general proof that A* using tree search is optimal
if h(n) is admissible
• Hence, we can combine both costs, and the sum is called a fitness number

Copyright: Dr Abhishek Mukhopadhyay

 • A local search
algorithm used for
solving mathematical
optimization problems
• The basic idea is to
iteratively move
Hill Climbing towards the direction
of increasing elevation
(or decreasing,
depending on the
optimization goal) until
a peak or valley is
reached

Copyright: Dr Abhishek Mukhopadhyay

Copyright: Dr Abhishek Mukhopadhyay

• Initial State: Start with an

arbitrary or random solution
(initial state).

Basic
• Neighboring States: Identify
neighboring states of the
current solution by making
Concepts of small adjustments
(mutations or tweaks).

Hill Climbing • Move to Neighbor: If one of

the neighboring states offers

Algorithms a better solution (according

to some evaluation function),
move to this new state.
• Termination: Repeat this
process until no neighboring
state is better than the
current one. At this point,
you’ve reached a local
maximum or minimum
(depending on whether you’re
maximizing or minimizing).
Example
• We will apply both
local and global
heuristic
 Hill Climbing: Local Heuristic Approach

-1 1
0 4
1 1
• +1 for each block that is resting on the thing
1 1
it is supposed to be resting on
-1 1 • -1 for each block resting on a wrong thing
Hill Climbing: Local Heuristic Approach

• +1 for each block that is resting on the thing

1
it is supposed to be resting on
1 • -1 for each block resting on a wrong thing
-1 1
Hill Climbing: Local Heuristic Approach

Local
Optima

• +1 for each block that is resting on

the thing it is supposed to be
resting on
• -1 for each block resting on a wrong
thing
1 -1 1
-1 1 -1 1 -1

Results did
not improve
Hill Climbing: Global Heuristic Approach

• +1 for each block that has correct support

structure
• -1 for each block that has wrong support
structure
 Hill Climbing: Global Heuristic Approach

-3 3
-6 6
-2 2
• +1 for each block that has correct support
-1 1 structure
0 0 • -1 for each block that has wrong support
structure
Hill Climbing: Global Heuristic Approach

-3 -1
-2

-1 -1 0 0

0 0 0
 Hill Climbing: Global Heuristic Approach

-1 0

-1 0 0 0 0 0
0

0 0
 Hill Climbing: Global Heuristic Approach

-1 0 Global
Optima

-1 0 0 0 0 0
0

0 0

1 2 3 3 6
1 2
0 0
1 0
1
0 0 0
 • Local Optima
• It is a local search
technique
• Tends to get stuck in
local optimal
solution
• Lacks the ability to
explore beyond
current local
Limitations of neighborhood

Hill Climbing • Sensitivity to Initial

Conditions
• Highly dependent on
the choice of initial
solution
• Sensitivity to initial
conditions make it
challenging to
ensure consistent
and reliable
optimization
 Branch and Bound
• Depth-first branch-and-bound search is a
way to combine the space saving of
depth-first search with heuristic
information
• Applicable when many paths to a goal
exist and we want an optimal path
• Branch-and-bound search is to maintain
the lowest-cost path to a goal found so
far, and its cost

Source: [Link]
Copyright: Dr Abhishek Mukhopadhyay
 Branch and Bound
• Suppose this cost is bound
• If the search encounters a path p such that
cost(p)+h(p) ≥ bound, path p can be
pruned
• If a non-pruned path to a goal is found, it
must be better than the previous best path
• This new solution is remembered and
bound is set to the cost of this new solution

Copyright: Dr Abhishek Mukhopadhyay

 Branch and Bound
• The goal nodes are shaded
• Suppose that each arc has length 1, and there is
no heuristic information (i.e., h(n)=0 for each node
n)
• Suppose depth0=∞ and the depth-first search
always chooses the leftmost child first
• subtree under the node numbered "5" does not
have a goal and is explored fully
• The ninth node checked is a goal node. It has a
path cost of 5, and so the bound is set to 5
• The fifteenth node checked is also a goal. It has a
path cost of 3, and so the bound is reduced to 3

Copyright: Dr Abhishek Mukhopadhyay

Example of Branch and Bound
 • All search techniques explored so far works in a space
Constraint of states
• States can be evaluated by domain-specific
Satisfaction heuristics and tested to see whether they are goal
states
Problems • Each state is atomic, or indivisible
(CSP) • CSP use a factored representation for each state
• A state of variables, each of which has a value
• A problem is solved when each variable has a value that
satisfies all constraints on the variable

Copyright: Dr Abhishek Mukhopadhyay

 • 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.

Definition of • C is a set of constraints that specify allowable

combinations of values
CSP • 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

Copyright: Dr Abhishek Mukhopadhyay

 • We need to define a state space and notion of a solution
to solve a CSP:
• Each state in a CSP is defined by an assignment of
Definition of values to some or all of the variables
• An assignment that does not violate any constraints
CSP is called a consistent or legal assignment.
• A complete assignment is one in which every
variable is assigned
• A partial assignment is one that assigns values to
only some of the variables

Copyright: Dr Abhishek Mukhopadhyay

Example of CSP : Map coloring
• We define variables to be the region as
• 𝑋 = {𝑊𝐴, 𝑁𝑇, 𝑄, 𝑁𝑆𝑊, 𝑉, 𝑆𝐴, 𝑇}
• Domain of each variable is the set
• 𝐷𝑖 = 𝑟𝑒𝑑, 𝑔𝑟𝑒𝑒𝑛, 𝑏𝑙𝑢𝑒
• Constraints require neighboring regions to have distinct colors. As
we have nine borders,
• 𝐶 = {𝑆𝐴 ≠ 𝑊𝐴, 𝑆𝐴 ≠ 𝑁𝑇, 𝑆𝐴 ≠ 𝑄, 𝑆𝐴 ≠ 𝑁𝑆𝑊, 𝑆𝐴 ≠ 𝑉, 𝑊𝐴 ≠
𝑁𝑇, 𝑁𝑇 ≠ 𝑄, 𝑄 ≠ 𝑁𝑆𝑊, 𝑁𝑆𝑊 ≠ 𝑉}
• There are many possible solutions. Such as

• {𝑊𝐴 = 𝑟𝑒𝑑 , 𝑁𝑇 = 𝑔𝑟𝑒𝑒𝑛, 𝑄 = 𝑟𝑒𝑑 , 𝑁𝑆𝑊 =

𝑔𝑟𝑒𝑒𝑛, 𝑉 = 𝑟𝑒𝑑 , 𝑆𝐴 = 𝑏𝑙𝑢𝑒, 𝑇 = 𝑟𝑒𝑑}

Copyright: Dr Abhishek Mukhopadhyay

Advantages

• In regular state-space search we can only ask:

• Is this specific state a goal? No? What about this one?
• With CSPs, once we find out that a partial assignment is not a solution, we can
• Immediately discard further refinements of the partial assignment.
• CSP eliminate larger swatches of search space
• For example, once we select 𝑆𝐴 = 𝑏𝑙𝑢𝑒 , we conclude none of five neighbors
can take value of blue
• Without taking advantage of constraint propagation, search have to consider 35
assignments, with constraint propagation, assignments reduce to 25 , a
REDUCTION OF 87%

Copyright: Dr Abhishek Mukhopadhyay

Assignment 1

Apply A* to find admissible heuristic path between S

and J

Copyright: Dr Abhishek Mukhopadhyay

 • Applications of AI
• Agents
• Problem solving agents
Take Away • Search Space

Points • Uninformed search (BFS, DFS, IDDFS)

• Informed search (DFS, A*, Hill
climbing, Branch and Bound, CSP)

Copyright: Dr Abhishek Mukhopadhyay