NAAC A+ Accredited

TULSIRAMJI GAIKWAD-PATIL
College of Engineering & Technology

Department of Computer Science & Engineering

Session 2020-2021

Artificial Intelligence(AI) -----6th sem

Prof. Neha Mogre

Subject Incharge
 Syllabus
UNIT‐I:
Introduction: What is AI? History & Applications, Artificial intelligence as
representation & Search, Production system, Basics of problem solving:
problem representation paradigms, defining problem as a state space
representation, Characteristics.
UNIT‐II:
Search Techniques: Uninformed Search techniques, Informed Heuristic
Based Search, Generate and test, Hill-climbing, Best-First Search, Problem
Reduction, and Constraint Satisfaction.
UNIT‐III:
Knowledge representation: Knowledge representation Issues: First order
logic, Predicate Logic, Structured Knowledge Representation: Backward
Chaining, Backward Chaining, Resolution ,Semantic Nets, Frames, and
Scripts, Ontology.

2 Department of CSE Artificial Intelligence

 UNIT‐IV:
Uncertainty: Handing uncertain knowledge, rational decisions, basics of
probability, axioms of probability, Baye’s Rule and conditional
independence, Bayesian networks, Exact and Approximate inference in
Bayesian Networks, Fuzzy Logic.
UNIT‐V:
Learning: What is learning?, Knowledge and learning, Learning in
Problem Solving, Learning from example, learning probabilistic
models, Formal Learning Theory
UNIT‐VI:
Expert Systems: Fundamental blocks, Knowledge Engineering,
Knowledge Acquisition, Knowledge Based Systems, Automated
Reasoning, Understanding Natural language

3 Department of CSE Artificial Intelligence

 Books
Text Books:
E. Rich and K. Knight, Artificial Intelligence, Tata
McGraw Hill, 2008.
 Artificial intelligence and soft computing for beginners  by
Anandita Das Bhattachargee, Shroff Publishers
 Artificial Intelligence – A Practical Approach : Patterson , Tata
McGraw Hill, 3rd Edition

Reference Books:
 Introduction to Artificial Intelligence – Charniak (Pearson
Education)

4 Department of CSE Artificial Intelligence

 Course Outcome
BECSE306T

CO1 Able to implement standard algorithm for searching and

sorting based on requirement and also analyze the average,
best and worst case in terms of space and time complexity
CO2 Understand various representations for linear and non-linear
data structures such as Arrays and Linked List.
CO3 Able to understand the concepts of Stacks, Queues.
CO4 Understand various representations of various Trees.
CO5 Understand various types of graphs and the algorithms to find
minimum spanning trees & shortest path between the vertices.
CO6 Understand hashing and collision resolution techniques for
performing direct searches on Hash tables.
5 Department of CSE Artificial Intelligence
 Artificial Intelligence

P re
sen
Neh ted b
a M y:-
ogr
e
What is Intelligence???
Intelligence is the ability to learn
about, to learn from, to understand
about, and interact with one’s
environment.

Intelligence is the faculty of

understanding

Intelligence is not to make no mistakes

but quickly to understand how to
make them good
(German Poet)
 What Is Artificial Intelligence???
 Artificial Intelligence (AI) is
usually defined as the science
of making computers do
things that require
intelligence when done by
humans.
 A.I is the study of ideas that
enable computers to be
intelligent
How Does AI Works??
Artificial intelligence works
with the help of

• Artificial Neurons
(Artificial Neural
Network)

And
• Scientific theorems(If-
Then Statements, Logics)
 Turing Test
Imitation Game Test!!!!

The Turing test is a test of a machine's

ability to demonstrate intelligence
Chinese Room Test
A Counter Argument to Turing Test
 Intelligent agents

Agent Percepts
Sensors

Environment
?

Actions

Actuators

12 03/06/22
Examples Of Artificial Intelligence
Expert Systems!!

An expert system is a computer program that is designed to

hold the accumulated knowledge of one or more domain
experts
It reasons with knowledge of some specialist subject with a
view to solving problems or giving advice

They are tested by being placed in the same real world

problem solving situation
 Applications of Expert Systems

PUFF:
Medical system
for diagnosis of respiratory
conditions

PROSPECTOR:
Used by geologists to identify
sites for drilling or mining
 Applications of Expert Systems

DENDRAL: Used to identify the

structure of chemical
compounds. First used in 1965

LITHIAN: Gives advice to

archaeologists examining stone
tools
Resemblance To Human Mind....

The special ability of artificial intelligence is to reach a

solution based on facts rather than on a preset series of steps
—is what most closely resembles the thinking function of the
human brain
Human Intelligence VS Artificial Intelligence
Human Intelligence VS Pros
Artificial Intelligence

Human Intelligence Artificial Intelligence

Intuition, Common sense, Ability to simulate human
Judgement, Creativity, behavior and cognitive
Beliefs etc processes
The ability to demonstrate Capture and preserve
their intelligence by human expertise
communicating Fast Response. The ability
effectively to comprehend large
Plausible Reasoning and amounts of data quickly.
Critical thinking
Human Intelligence VS Artificial Intelligence
Cons
Human Intelligence Artificial Intelligence
• Humans are fallible No “common sense”
• They have limited Cannot readily deal with
knowledge bases “mixed” knowledge
• Information processing of
May have high
serial nature proceed very
slowly in the brain as development costs
compared to computers Raise legal and ethical
Humans are unable to concerns
retain large amounts of
data in memory.
 Human Intelligence VS Artificial Intelligence

We achieve more than we know. We know more than we

understand. We understand more than we can explain (Claude
Bernard, 19th C French scientific philosopher)
Artificial Intelligence VS Conventional Computing

Artificial Intelligence Conventional Computing

AI software uses the Conventional computer

techniques of search and software follow a logical

pattern matching series of steps to reach a
conclusion
Programmers design AI
Computer programmers
software to give the
originally designed software
computer only the
that accomplished tasks by
problem, not the steps
completing algorithms
necessary to solve it
 Psychology And Artificial intelligence

The functionalist approach of AI views the mind as a

representational system and psychology as the study of the
various computational processes whereby mental
representations are constructed, organized, and interpreted.
(Margaret Boden's essays written between 1982 and 1988)
 Artificial intelligence & Our society

Why we need AI??

To supplement natural intelligence for e.g we are building

intelligence in an object so that it can do what we want it to do, as for
example-- robots, thus reducing human labour and reducing human
mistakes
 •My Perspective

For Humans Intelligence is no more than

TAKING a right decision at right time
And
For Machines Artificial Intelligence is no more
than CHOOSING a right decision at right time

I think Artificial intelligence is the Second

intelligence ever to exist
 UNIT- I
Introduction to AI

25 Department of CSE Ethics in IT

 UNIT I

ARTIFICIAL INTELLIGENCE
WHAT IS INTELLIGENECE
DEFINITION
 It is the study of how to make computers do things which, at the
moment, people do better.
 This defination is somewhat ephemeral because of its reference
to the current state of computer science.
 What are the problems contained within AI?
•Much of early work focused
on formal task such as game
playing and theorem proving.

•Samuel wrote a checkers-

playing program that not
played games with opponents
but also its experience at those
games to improve its later
performance.
•Chess also received a good
deal of attention.

29 Department of CSE Ethics in IT

  AI focused on the sort of problem solving that we do every
day when we decide how to get to work in the morning,
often called common sense reasoning.
 To investigate this sort of reasoning, Newell, Shaw, and
Simon built General Problem Solver(GPS).
 As AI research progressed and techniques for handling
large amount of world knowledge were developed, some
progress was made on task.

30 Department of CSE Ethics in IT

AI TASK DOMAINS
AI PROBLEM FEATURES
AI TECHNIQUE
CONCLUSION
THREE IMPORTANT AI TECHNIQUES
PROBLEMS, PROBLEM SPACE,
AND SEARCH
CHAPTER 2
TO BUILD A SYSTEM
DEFINING THE PROBLEM AS A
STATE SPACE SEACH
FOR EXAMPLE: PLAY CHESS
DEFINING THE PROBLEM AS A
STATE SPACE SEACH
FOR EXAMPLE: PLAY CHESS
WATER JUG PROBLEM
SOLUTION
FORMAL DESCRIPTION OF A
PROBLEM
PRODUCTION SYSTEM
CONTROL STRATEGY
SEARCHING TECHNIQUES

BFS AND DFS

BFS
DFS
FOR EXAMPLE
COMBINATORIAL EXPLOSION
HEURISTIC SEARCH
HEURISTIC SEARCH
PROBLEM CHARACTERICTICS
PROBLEM CHARACTERICTICS
1) IS YOUR PROBLEM
DECOMPOSABLE?
2) CAN SOLUTION STEPS BE
IGNORED OR UNDONE?
3)IS THE UNIVERSE
PREDICTABLE?
4) IS THE GOOD SOLUTION
ABSOLUTE OR RELATIVE?
4) IS THE GOOD SOLUTION
ABSOLUTE OR RELATIVE?
4) IS THE GOOD SOLUTION
ABSOLUTE OR RELATIVE?
4) IS THE GOOD SOLUTION
ABSOLUTE OR RELATIVE?
5)IS THE SOLUTION A STATE OR
A PATH?
6) WHAT IS THE ROLE OF
KNOWLEDGE?
7) DOES THE TASK REQUIRE
INTERACTION WITH A PERSON?
PROBLEM
PROBLEM
HEURISTIC SEARCH
TECHNIQUES

CHAPTER III
HEURISTIC SEARCH
TECHNIQUES
GENERATE AND TEST
 HILL CLIMBING

SIMPLE HILL CLIMBING

STEEPEST ASCENT HILL CLIMBING
SIMULATED ANNEALING
SIMPLE HILL CLIMBING
STEEPEST ASCENT HILL
CLIMBING
DISADVANTAGES OF SAHC
PROBABLE SOLUTION
SIMULATED ANNEALING
BEST-FIRST SEARCH

COMBINATION OF BFS AND DFS

GRAPHS
TWO TYPES OF GRAPHS
OR GRAPH
AND-OR GRAPH
OR GRAPHS
EXAMPLE OF BEST-FS
NODES USED FOR BEST-FS
ALGORITHM
 BEST FIRST SEARCH IS THE
SIMPLIFICATION OF BEST FIRST
SEARCH
A* ALGORITHM
A* ALGORITHM
A* ALGORITHM
A* ALGORITHM
AND-OR GRAPH
AND-OR GRAPH
PROBLEM REDUCTION
EXAMPLE
PROBLEM REDUCTION
AO* ALGORITHM
AO* ALGORITHM
CONSTRAINT SATISFACTION
CONSTRAINT SATISFACTION
MEANS END ANALYSIS
MEANS END ANALYSIS
END OF UNIT I
UNIVERSITY QUESTIONS
What are the steps involved in designing a program to
solve an AI problem?
Define AI. State the various task domains of AI
Why is it necessary to apply control strategies to
production rule system?
What is production rule system?
Discuss the importance of heuristic search over blind
search?
UNIVERSITY QUESTIONS
 What are the steps involved in designing a program to
solve an AI problem?
 Describe a problem for which means end analysis can be
successfully applied. Give an example of a few solution
steps.
 What is the difference between OR graph and AND-OR
graph.
 Give some examples with best-first search is suitable as
compared to breadth-first search on depth-first search.
Justify your answers.
UNIVERSITY QUESTIONS
Explain production system in detail.
State advantages and disadvantages of Breadth-first
search and Depth-first search.
Explain 1)Local maxima 2)Plateau 3)Ridge
Difference between Hill climbing and Steepest ascent
hill climbing
Explain the term combinatorial explosion.
UNIVERSITY QUESTIONS
Explain the problem characteristics of AI problem.
Explain 1) Simulated annealing 2) Means-End
Analysis
Difference between: 1) A* and AO* algo 2)Data and
knowledge
Write and explain the algos:- 1)A* 2)AO*
UNIVERSITY QUESTIONS
Analyze the following problems with respect to
various problems characteristics
a) chess playing b)Water jug problem c)Travelling
salesman problem d)8-puzzle e)Natural language
understanding
Problem-Solving Agents
 Intelligent agents can solve problems by searching a state-space

 State-space Model
 the agent’s model of the world
 usually a set of discrete states
 e.g., in driving, the states in the model could be towns/cities

 Goal State(s)
 a goal is defined as a desirable state for an agent
 there may be many states which satisfy the goal test
 e.g., drive to a town with a ski-resort
 or just one state which satisfies the goal
 e.g., drive to Mammoth

 Operators (actions, successor function)

 operators are legal actions which the agent can take to move from one state to another
Example: Romania
On holiday in Romania; currently in Arad.
Flight leaves tomorrow from Bucharest
Formulate goal:
be in Bucharest
Formulate problem:
states: various cities
actions: drive between cities
Find solution:
sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest
Example: Romania
 Problem types

 Static / Dynamic
Previous problem was static: no attention to changes in environment
 Observable / Partially Observable / Unobservable
Previous problem was observable: it knew its initial state.
 Deterministic / Stochastic
Previous problem was deterministic: no new percepts
were necessary, we can predict the future perfectly
 Discrete / continuous
Previous problem was discrete: we can enumerate all possibilities
State-Space
Problem Formulation
A problem is defined by four items:

initial state e.g., "at Arad“

actions or successor function S(x) = set of action–state pairs

 e.g., S(Arad) = {<Arad  Zerind, Zerind>, … }

goal test, (or goal state)

e.g., x = "at Bucharest”, Checkmate(x)

path cost (additive)

 e.g., sum of distances, number of actions executed, etc.
 c(x,a,y) is the step cost, assumed to be ≥ 0

A solution is a sequence of actions leading from the initial state to a goal

state
 Defining Search Problems
 A statement of a Search problem has 4 components
 1. A set of states
 2. A set of “operators” which allow one to get from one state to another
 3. A start state S
 4. A set of possible goal states, or ways to test for goal states
 4a. Cost path

 A solution consists of
 a sequence of operators which transform S into a goal state G

 Representing real problems in a State-Space search framework

 may be many ways to represent states and operators
 key idea: represent only the relevant aspects of the problem (abstraction)
 Abstraction/Modeling
Process of removing irrelevant detail to create
an abstract representation: ``high-level”,
ignores irrelevant details
 Definition of Abstraction:
 Navigation Example: how do we define states and operators?
 First step is to abstract “the big picture”
 i.e., solve a map problem
 nodes = cities, links = freeways/roads (a high-level description)
 this description is an abstraction of the real problem
 Can later worry about details like freeway onramps, refueling, etc

 Abstraction is critical for automated problem solving

 must create an approximate, simplified, model of the world for the computer to deal
with: real-world is too detailed to model exactly
 good abstractions retain all important details
Robot block world
 Given a set of blocks in a certain configuration,
 Move the blocks into a goal configuration.
 Example :
(c,b,a)  (b,c,a)

A A Move (x,y)
B C
C B
Operator Description
The state-space graph
 Graphs:
 nodes, arcs, directed arcs, paths
 Search graphs:
 States are nodes
 operators are directed arcs
 solution is a path from start to goal
 Problem formulation:
 Give an abstract description of states, operators, initial state and goal
state.
 Problem solving activity:
 Generate a part of the search space that contains a solution
 The Traveling Salesperson Problem
(a touring problem)
Find the shortest tour that visits all cities without visiting
any city twice and return to starting point.
States: sequence of cities visited
S0 = A C

B
A D
F

 SG = a complete tour E

{a, c, d } {( a, c, d , x) | X  a, c, d }
Example: 8-queen problem
 Example: 8-Queens

states? -any arrangement of n<=8 queens

-or arrangements of n<=8 queens in leftmost n
columns, 1 per column, such that no queen
attacks any other.
initial state? no queens on the board
actions? -add queen to any empty square
-or add queen to leftmost empty square such that it is not
attacked by other queens.
goal test? 8 queens on the board, none attacked.
path cost? 1 per move
The sliding tile problem

8-puzzle: 181,440 states

15-puzzle: 1.3 trilion
24-puzzle: 10^25
The Sliding Tile Problem

move( x, loc y, loc z ) Up

Down
Left
Right
The “8-Puzzle” Problem
Start State
1 2 3
4 6
7 5 8

1 2 3
4 5 6
7 8

1 2 3
4 5 6
7 8
Goal State
Formulating Problems;
another angle
 Problem types
 Satisficing: 8-queen
 Optimizing: Traveling salesperson

 Object sought
 board configuration,
 sequence of moves
 A strategy (contingency plan)

 Satisfying leads to optimizing since “small is quick”

 For traveling salesperson
 satisficing easy, optimizing hard

 Semi-optimizing:
 Find a good solution

 In Russel and Norvig:

 single-state, multiple states, contingency plans, exploration problems
Searching the State Space
 States, operators, control strategies

 The search space graph is implicit

 The control strategy generates a small search tree.

 Systematic search
 Do not leave any stone unturned
 Efficiency
 Do not turn any stone more than once
Tree search example
State space of the 8 puzzle problem
Why Search can be difficult
 At the start of the search, the search algorithm does not know
 the size of the tree
 the shape of the tree
 the depth of the goal states

 How big can a search tree be?

 say there is a constant branching factor b
 and one goal exists at depth d
 search tree which includes a goal can have
bd different branches in the tree (worst case)

 Examples:
 b = 2, d = 10: bd = 210= 1024
 b = 10, d = 10: bd = 1010= 10,000,000,000
 Ahead
Go e s ti on
u
With Q

Be Not Afraid Of Falling Be Afraid Of Not Trying

Artificial Intelligence

Our Attempt To Build Models Of

Ourselves
Thank You
Elaine Rich