Module 1 AI

Amity School of Engineering & Technology
Artificial Intelligent
Module 1
By- Chandan Sharma
A2305219668 , 6CSE11Y
ASET, Amity University, Noida
Introduction
According to John McCarthy, who is known as the
father of AI,
“AI is the science and engineering of making
intelligent machines, especially computer programs.”
“A system's ability to correctly interpret external data,

to learn from such data, and to use those learnings to
achieve specific goals and tasks through flexible
adaptation.“
Artificial Intelligence
History
• Up-to early 80’s: Creation of expert systems
(systems specialized for one particular task
based on experts’ knowledge), wide industry
adoption
Modern AI
• Towards more scientific, formal/mathematical
• Divided into many subareas interested in
particular aspects
• More directly connected to theoretical
computer science, statistics, operations
research, biology, economics, psychology,
neuroscience etc
What is AI
• Artificial Intelligence is concerned with the design of
intelligence in an artificial device. The term was coined by
McCarthy in 1956.
• There are two ideas in the definition.
1. Intelligence
2. Artificial device
• What is intelligence?
• Is it that which characterize humans? Or is there an
absolute standard of judgement? – Accordingly there are
two possibilities:
• A system with intelligence is expected to behave as
intelligently as a human .
• A system with intelligence is expected to behave in the
best possible manner
What is Intelligence?
• Intelligence is a property of mind
that encompasses many related
mental abilities, such as the
capabilities to
• reason
• plan
• solve problems
• think abstractly
• comprehend ideas and language
and learn
Concept of AI
• Artificial Intelligence is the study of how to make
computers do things which, at the moment, people do
better”
• This definition is of course somewhat ephemeral because
of its reference to the current state of computer science.
And it fails to include some areas of potentially large
impact, namely problems that cannot now be solved well
by either computers or people. But it provides a good
outline of what constitutes artificial intelligence and it
avoids the philosophical issues that determines attempts
to define the meaning of either artificial or intelligence.
• “Also we can say AI is the study of techniques for
solving the exponentially hard problem in polynomial
time by exploiting knowledge about the problem
domain”.
Some task domain of AI

• Mundane Tasks
Perception
• Vision
• Speech
Natural Language
• Understanding
• Generation
• Translation
Commonsense Reasoning
Robot control
Some task domain of AI
• Formal Tasks
Games
• Chess
• Backgammon
• Checkers
• Go
Mathematics
• Geometry
• Logic
• Integral Calculus
• Proving properties of programs.
Some task domain of AI(Cont..)

• Expert Task
Engineering
• Design
• Fault finding
• Manufacturing Planning
Scientific Analysis
Medical Diagnosis
Financial Analysis
Types of Artificial Intelligence
• Artificial Intelligence can be

divided in various types
• There are mainly two types of
main categorization which are
based on capabilities and based
on functionally of AI.
• Following is flow diagram which
explain the types of AI.
AI type-1: Based on Capabilities

• Weak AI or Narrow AI:
Narrow AI is a type of AI which is able to perform a
dedicated task with intelligence. The most common
and currently available AI is Narrow AI in the world
of Artificial Intelligence.
• General AI:
General AI is a type of intelligence which could
perform any intellectual task with efficiency like a
human.
• Super AI:
Super AI is a level of Intelligence of Systems at which
machines could surpass human intelligence, and can
perform any task better than human with cognitive
properties. It is an outcome of general AI.
AI type-2: Based on functionality

1. Reactive Machines
3. Theory of Mind
Purely reactive machines are the most basic types of
Artificial Intelligence. Theory of Mind AI should understand the human
emotions, people, beliefs, and be able to interact
Such AI systems do not store memories or past experiences socially like humans.
for future actions.
This type of AI machines are still not developed, but
These machines only focus on current scenarios and react on researchers are making lots of efforts and
it as per possible best action.
improvement for developing such AI machines.
IBM's Deep Blue system is an example of reactive machines.
4. Self-Awareness
Google's AlphaGo is also an example of reactive machines. Self-awareness AI is the future of Artificial
2. Limited Memory Intelligence. These machines will be super intelligent,
Limited memory machines can store past experiences or
and will have their own consciousness, sentiments,
some data for a short period of time. and self-awareness.
These machines can use stored data for a limited time period These machines will be smarter than human mind.
only. Self-Awareness AI does not exist in reality still and it
Self-driving cars are one of the best examples of Limited is a hypothetical concept.
Memory systems. These cars can store recent speed of
nearby cars, the distance of other cars, speed limit, and other
information to navigate the road.
The Underlying Assumption:

• There is good question about intelligence is : what
are our underlying assumptions.
• The research in AI produces a physical symbol
system hypothesis for underlying assumption.
• A physical symbol system consists of a set of
entities called symbol. Which are physical patterns
that can occur as components of other type of entity
called an expression or symbol structure?
• A symbol structure composed of a number of
instances of symbol related in some physical way.

The Underlying Assumption(Cont..)

• At any instant of time the system will contain a
collection of these symbol structures. Besides the
structure the system also contains a collection of
processes of that operate on expression to produce
expression: processes of creation, modification,
reproduction and destruction.
• Computer provides the perfect medium for this
experiment since they can be programmed to
simulate any physical symbol system.
• The importance of the physical symbol system
hypothesis is twofold. It is a significant theory of
the nature of human intelligence and so is of great
interest to psychologists.
AI Techniques
There are three important AI Techniques. They are:
• Search: This technique provides a way of solving problems

for no more direct approach is available as well as a
framework into which any direct techniques that are can be
embedded. A search program finds a solutions for a problem
by trying various sequences of actions or operators until a
solution is found.
• Use of Knowledge: This technique provides a way of solving
complex problem by exploiting the structures of the object
that are involved.
• Abstraction: This techniques provides a way of separating
important features and variations from the many unimportant
ones that would otherwise overwhelm any process.
AI Techniques Cont..
AI technique is a method that exploits knowledge that should be
represented in following manner.
• The knowledge captures generalizations.
That is : it is not necessary to represent separately each individual
situation. Instead situation, that share important role or properties are
grouped together. If knowledge does not have this property, inordinate
amount of memory and updating will be required.
• It can be understood by people who must provide it.
• It can easily be modified to correct errors and to reflect changes in the
world and our world view.
• It can be used in a great many situations even if it is not totally accurate.

The Level of Model

To build programs that perform tasks the way people do
can be divided into two classes.
• Programs in first class attempt to solve problems that
do not really fit our definition of an AI task. They are
problems that computer could easily solve, although
that easy solution would exploit mechanisms that do
not seem to be available to people. These programs
can, however be useful tools for psychologists who
want to test theories of human performance.
• The second class of programs that performs that
attempt to model human performance are those that do
things that fall more clearly within our definition of AI
task. They do things that are not trivial for the
computer.
The Level of Model (cont..)

The following reason on the human performance.
• To test psychological theories of human performance.
• To enable computer to understand human reasoning.
• To enable people to understand computer reasoning.
• To exploit that knowledge we can gain from people. Since people are the
best known performance of most of the tasks with which we are dealing,
it makes a lot of sense to look to them for clues as to how to produce.
Criteria for Success

• The criteria for success How will we know if we have constructed a
machine that is intelligent. Whether a machine has intelligence or can
think is too nebulous answer precisely.
• But it is often possible to construct a computer program that meets some
performance standard on a particular task. That does not mean that the
program does the task in the best possible way.
• It means only that we understand at least one way of doing at least one
task. When we set out to design an AI program. We should attempt to
specify as well as possible the criteria for success for that particular
program functioning in its restricted domain. For the moment that is the
best we can do.
The Turing Test

Turing proposed operational test for intelligent
behavior in 1950.
Human
Human ?
Interrogator
AI system
Turing Test (Cont..)

It is a method for determining whether a
machine can think.
• To construct this test we need two
people and the machine. One person
plays the role of interrogator.
• The interrogator will be in the separate
room from the computer and the other
person.
• The interrogator can ask the question of
either the person or the computer by
typing them.
Turing Test (Cont..)
we need four steps:
• Define the problem precisely. In this we
determine the initial and final situation of
the problem.
• Analyze the problem.
• Isolate and represent the task knowledge
that is necessary to solve the problem.
• Choose the best problem solving technique
and apply it to the particular problem.
Game playing
• Game playing share the property that people who do them well are considered to be displaying
intelligence. Despite this, it appeared initially that computers could perform well act those tasks
simply by being fast at exploring a large number of solution paths and selecting the best one and if
we apply this rule to day to day life then we can understand that, it is basic rule of problem solving.
• Almost in every case for every problem in a particular situation we may have various possible
solutions but if we want to solve the problem correctly then we have to choose a right path then
only we can overcome the problem.
• Same strategy we adopt in game playing, if we want to be a winner then we have to select right
option among the various possible options.
• By adopting this approach we can design best possible game (AI based). But it may not be winner
all
• We can understand it by following examples: Tic- Tac- Toe
Theorem proving
• Theorem proving has the property that people who do them well are considered to
be displaying intelligence.
• The Logic Theorist was an early attempt to prove mathematical theorems.
• There are three types of problems in A.I.
• Ignorable problems, in which solution steps can be ignored
• Recoverable problems in which solution steps can be undone
• Irrecoverable in which solution steps cannot be undone.
• Theorem proving falls into the first category i.e. it is ignorable suppose we are
trying to solve a theorem, we proceed by first proving a lemma that we think will
be useful. Eventually we realize that the lemma is not help at all. In this case we
can simply ignore that lemma, and can start from beginning.
Natural Language Processing (NLP)

• Natural Language Processing (NLP) is a subfield of artificial intelligence
(AI). It helps machines process and understand the human language so that
they can automatically perform repetitive tasks. Examples include machine
translation, summarization, ticket classification, and spell check.
• Take sentiment analysis, for example, which uses natural language
processing to detect emotions in text. This classification task is one of the
most popular tasks of NLP, often used by businesses to
automatically detect brand sentiment on social media. Analysing these
interactions can help brands detect urgent customer issues that they need to
respond to right away, or monitor overall customer satisfaction.
Why Is Natural Language Processing Important?

• One of the main reasons natural language processing is so critical to businesses is that it
can be used to analyse large volumes of text data, like social media comments, customer
support tickets, online reviews, news reports, and more.
• All this business data contains a wealth of valuable insights, and NLP can quickly help
businesses discover what those insights are.
• It does this by helping machines make sense of human language in a faster, more accurate,
and more consistent way than human agents.
• NLP tools process data in real time, 24/7, and apply the same criteria to all your data, so
you can ensure the results you receive are accurate – and not riddled with inconsistencies.
• Once NLP tools can understand what a piece of text is about, and even measure things like
sentiment, businesses can start to prioritize and organize their data in a way that suits their
needs.
Future of NLP
• Human level or human readable natural language processing is an AI-complete problem .
• It is equivalent to solving the central artificial intelligence problem and making computers
as intelligent as people
• Make computers as they can solve problems like humans and think like humans as well as
perform activities that humans cant perform and making it more efficient than humans
• NLP's future is closely linked to the growth of Artificial intelligence
• As natural language understanding or readability improves, computers or machines or
devices will be able to learn from the information online and apply what they learned in the
real world
• Combined with natural language generation, computers will become more and more
capable of receiving and giving useful and resourceful information or data
NLP Applications
Applications
• Machine Translation
• Information Retrieval
• Question Answering
• Dialogue Systems
• Information Extraction
• Summarization
• Sentiment Analysis
Computer Vision Scope

• Computer vision is a field of artificial intelligence
that trains computers to interpret and understand the
visual world. Machines can accurately identify and
locate objects then react to what they “see” using
digital images from cameras, videos, and deep
learning models.
• If AI enables computers to think, computer vision
enables them to see, observe and understand.
• Computer vision works much the same as human
vision, except humans have a head start. Human sight
has the advantage of lifetimes of context to train how
to tell objects apart, how far away they are, whether
they are moving and whether there is something.
• Computer vision needs lots of data. It runs analyses of
data over and over until it discerns distinctions and
ultimately recognize images.
Computer Vision (Cont..)

Applications of computer vision
• Automatic inspection (image-based automated
inspection), e.g., in manufacturing applications
• Assisting humans in identification tasks (to identify
object/species using their properties), e.g., a species
identification system
• Controlling processes (in a way of monitoring robots),
e.g., an industrial robot
• Detecting events, e.g., for visual surveillance or people
counting
• Modeling objects or environments (using drones can
analyses about climatic factors that leads to change in
vegetation, etc.), e.g., medical image analysis or
topographical modelling
• Navigation, e.g., by an autonomous vehicle or mobile
robot
• Organizing information, e.g., for indexing databases of
images and image sequences
Computer Vision
Image processing to computer vision progression
can be broken up into low-, mid- and high-level
processes
Low Level Mid Level High Level

Process Process Process
Input: Image Input: Image
Output: Image Input: Attributes
Output: Attributes Output:
Examples: Noise Examples: Object Understanding
removal, image recognition,
sharpening Examples: Scene
segmentation understanding,
autonomous
navigation
Image Processing To Computer Vision

Speech Processing
• Speech recognition refers to a computer
interpreting the words spoken by a person
and converting them to a format that is
understandable by a machine. Depending on
the end-goal, it is then converted to text or
voice or another required format.
• For instance, Apple’s Siri and Google’s
Alexa use AI-powered speech recognition to
provide voice or text support whereas voice-
to-text applications like Google Dictate
transcribe your dictated words to text. Voice
recognition is another form of speech
recognition where a source sound is
recognized and matched to a person’s voice.
Use Cases of Speech Recognition
• Voice-based speech recognition software is now used to initiate purchases, send emails, transcribe
meetings, doctor appointments, and court proceedings, etc.
• Virtual assistants or digital assistants and smart home devices use voice recognition software to answer
questions, provide weather news, play music, check traffic, place an order, and so on.
• Companies like Venmo and PayPal allow customers to make transactions using voice assistants. Several
banks in North America and Canada also provide online banking using voice-based software.
• Ecommerce is significantly powered by voice-based assistants and allows users to make purchases
quickly and seamlessly.
• Speech recognition is poised to impact transportation services and streamline scheduling, routing, and
navigating across cities.
• There has been a huge impact on security through voice biometry where the technology analyses the
varying frequencies, tone and pitch of an individual’s voice to create a voice profile. An example of this
is Switzerland’s telecom company Swisscom which has enabled voice authentication technology in its
call centres to prevent security breaches.
• Customer care services are being traced by AI-based voice assistants, and chatbots to automate
repeatable tasks.
What is Robotics
• Robotics is a branch of AI, which is
composed of Electrical Engineering,
Mechanical Engineering, and Computer
Science for designing, construction, and
application of robots.
• Robots are the artificial agents acting in
real world environment
• Robots are aimed at manipulating the
objects by perceiving, picking, moving,
modifying the physical properties of
object, destroying it, or to have an effect
thereby freeing manpower from doing
repetitive functions without getting bored,
distracted, or exhausted.
Aspects of Robotics
• The robots have mechanical
construction, form, or shape
designed to accomplish a
particular task.
• They have electrical
components which power and
control the machinery.
• They contain some level
of computer program that
determines what, when and how a
robot does something.
What is an Expert System?

• A system that uses human
expertise to make complicated
decisions.
• Simulates reasoning by
applying knowledge and
interfaces.
• Uses expert’s knowledge as
rules and data within the
system.
• Models the problem solving
ability of a human expert.
Expert System(Cont..)
• An expert system is a system that
employs human knowledge
captured in a computer to solve
problems that ordinarily require
human expertise.(Turban)
• A computer program that emulates
the behaviour of human experts
who are solving real-world
problems associated with a
particular domain of knowledge.
(Pigford & Braur)
Expert System(Cont..)
Defining the Problem as a State Space Search

• It permits us to define the process of solving a particular problem as a combination of known
techniques and search. The general technique of exploring the space to try to find some path
from the current state to a good state.
• Search is very important process in the solution of hard problem for which no more direct
technique are available.
• In order to provide a formal description of a problem it is necessary to do the following
things:
1. Define a state space that contains all the possible configurations of the relevant objects.
2. Specify one or more states within that space that describe possible situation from which the
problem solving process may start. These states are called the initial states.
3. Specify one or more states that would be acceptable as solution to the problem. These states
are called goal states.
4. Specify a set of rules that describe the actions (operators) available.
Defining the Problem as a State Space Search(cont..)

Search Algorithm Terminologies:
Search: Searchingis a step by step procedure to solve a search-problem in a given search space. A
search problem can have three main factors:
Search Space: Search space represents a set of possible solutions, which a system may have.
Start State: It is a state from where agent begins the search.
Goal test: It is a function which observe the current state and returns whether the goal state is
achieved or not.
Search tree: A tree representation of search problem is called Search tree. The root of the search
tree is the root node which is corresponding to the initial state.
Actions: It gives the description of all the available actions to the agent.
Transition model: A description of what each action do, can be represented as a transition model.
Path Cost: It is a function which assigns a numeric cost to each path.
Solution: It is an action sequence which leads from the start node to the goal node.
Optimal Solution: If a solution has the lowest cost among all solutions.
Production Systems
Production system provide the structure for solving the AI problem. It
consist of :
• A set of rules each consisting of a left side determines the applicability
and right side that describes the operation to be performed.
• One or more knowledge/ database that convert whatever information is
appropriate for the particular task.
• A control strategy that specify the order in which the rules will be
compared to the database and a way of resolving the conflicts that arise
when several rules match at once.
• A rule applier
Control Strategies
Control Strategy deal with how to decide which rule to apply next during the
process of searching for a solution to a problem because it may happen more
than one rule will have its left side match the current state.
• The first requirement of a good control strategy is that because motion will
never lead to a solution.
• The second requirement of a good control strategy is that it be semantic. If its
not semantic we may explore a particular useless sequence of operators several
times before we finally find a solution. The requirement that a control strategy
be semantic corresponds to the need for global motion as well as for local
motion.
Water Jug Problem

• Problem: You are given two jugs. A 4 gallon one and a 3 gallon one.
Neither has any measuring marker on it. There is a pump that can be used
to fill the jugs with water. How can you get exactly 2 gallons of water into
the 4 gallon jug?
• Solution: The state space for this problem can be described as a set of
ordered pair of integers (x, y) such that x = 0, 1, 2, 3, 4 and y = 0, 1, 2, 3. x
represent the numbers of gallon of water in 4 gallon jug and y represent
the numbers of gallon of water in 3 gallon jug. The start state is (0, 0). The
goal state is (2, n) for any value of n because the problem does not specify
how many gallon need to be in the 3 gallon jug.
Production Rules of WJ Problem

Assumptions
• We have assumed that we can fill a
jug from the pump and we can pour
water out of a jug onto the ground.
There are no measuring device:
• Sample Solution:
Three water Jug problem:

Suppose that you are given 3 jugs A,B,C with capacities 8, 5 and 3 liters respectively but are
not calibrated (i.e. no measuring mark will be there). Jug A is filled with 8 liters of water. By a
series of pouring back and forth among the 3 jugs, divide the 8 liters into 2 equal parts i.e. 4
liters in jug A and 4 liters in jug B. How?
In this problem, the start state is that the jug A will contain 8 liters water whereas jug B and jug C will be empty. The
production rules involve filling a jug with some amount of water, taking from the jug A. The search will be finding the
sequence of production rules which transform the initial state to final state. The state space for this problem can be described
by set of ordered pairs of three variables (A, B, C) where variable A represents the 8 liter jug, variable B represents the 5 liter
and variable C represents the 3 liters jug respectively.
The production rules are formulated as follows:

Step 1:
In this step, the initial state will be (8, 0, 0) as the jug B and jug C
will be empty. So the water of jug A can be poured like:
(5, 0, 3) means 3 liters to jug C and 5 liters will remain in jug A.
(3, 5, 0) means 5 liters to jug B and 3 liters will be in jug A.
(0, 5, 3) means 5 liters to jug B and 3 liters to jug C and jug C and
jug A will be empty.
• In this step, start with the first current state of step-1
i.e. (5, 0, 3). This state can only be implemented by
pouring the 3 liters water of jug C into jug B. so the
state will be (5, 3, 0).
• Next, come to the second current state of step-1 i.e.
(3, 5, 0). This state can be implemented by only
pouring the 5 liters water of jug B into jug C. So the
remaining water in jug B will be 2 liters. So the state
will be (3, 2, 3).
• Finally come to the third current state of step-1 i.e. (0,
5, 3). But from this state no more state can be
implemented because after implementing we may get
(5, 0, 3) or (3, 5, 0) or (8, 0, 0) which are repeated
state. Hence these states are not considerably again for
going towards goal.
So finally the state will be (4, 4, 0)

that means jug A and jug B contains
4 liters of water each which is our
goal state. One thing you have to
very careful about the pouring of
water from one jug to another that
the capacity of jug must satisfy the
condition to contain that much of
water.
The tree of the water jug problem
can be like:
Missionaries and Carnivals Problem

Initially a boatman, Grass, Tiger and Goat is present at the left bank of the river and want to cross it. The only boat
available is one capable of carrying 2 objects of portions at a time. The condition of safe crossing is that at no time the
tiger present with goat, the goat present with the grass at the either side of the river. How they will cross the river?
Let us use different representations for
each of the missionaries and Carnivals as follows.
B: Boat
T: Tiger
G: Goat
Gr: Grass

Three missionaries and three cannibals must cross a river using a boat which can carry at most two people,
under the constraint that, for both banks, that the missionaries present on the bank cannot be outnumbered
by cannibals. The boat cannot cross the river by itself with no people on board.
Solution:
First let us consider that both the missionaries (M) and cannibals(C) are on the same side of the river.
Left Right
Initially the positions are : 0M , 0C and 3M , 3C (B)
Now let’s send 2 Cannibals to left of bank : 0M , 2C (B) and 3M , 1C
Send one cannibal from left to right : 0M , 1C and 3M , 2C (B)
Now send the 2 remaining Cannibals to left : 0M , 3C (B) and 3M , 0C
Send 1 cannibal to the right : 0M , 2C and 3M , 1C (B)
Now send 2 missionaries to the left : 2M , 2C (B) and 1M . 1C
Send 1 missionary and 1 cannibal to right : 1M , 1C and 2M , 2C (B)
Send 2 missionaries to left : 3M , 1C (B) and 0M , 2C
Send 1 cannibal to right : 3M , 0C and 0M , 3C (B)
Send 2 cannibals to left : 3M , 2C (B) and 0M , 1C
Send 1 cannibal to right : 3M , 1C and 0M , 2C (B)’
Send 2 cannibals to left : 3M , 3C (B) and 0M , 0C
• Here (B) shows the position of the boat after the action is performed.
Therefore all the missionaries and cannibals have crossed the river safely.
Problem Characteristics
• In order to choose the most appropriate method for a particular

problem it is necessary to analyze the problem using several key
dimensions:
• Is the problem decomposable into one of independent smaller or
easier sub problem?
• Can solution steps be ignored or used.
• Is the problem universe predictable
• Is the good solution to the problem obvious without comparison to
all possible solution
• Is the desired solution a state word or a path to a state.
• Is a large amount of knowledge absolutely required to solve the
problem or knowledge important only to constrain the search.
Problem Decomposable
Block World Problem
Block World Problem(cont..)
• Soln. There are some actions given. According to that the robot arm that can manipulate
the blocks.
• UNSTACK (A, B): Pick block A from its current position on Block B. The arm must be empty and
block A must have no blocks on top of it.
• STACK (A, B): Place block A on block B. The arm must already be holding A and the surface
of B must be clear.
• PICK UP(A): Pickup block A from the table and hold it. The arm must be empty and therefore
must be nothing on top of block A.
• PUT DOWN (A): Put block A down on the table. The arm must have been holding block A.
• ON (A, B): block A is on block B.
• ON TABLE (A): block A is on the table.
• CLEAR(A): There is nothing on the top of block A
• HOLDING(A): The arm is holding block A.
• ARM EMPTY: The arm is holding nothing.
• There are some constraints for

• solving the problem. They are:
• P : Precondition
• D : Delete
• O : Operation
Solve Following
Problem 2 soln:
Can Solution step be ignored or undone
• There are generally three class of problem.

• Ignorable (e.g. Theorem proving): In this solution steps can be ignored.
• Recoverable (ex. 8 Puzzle) : In this solution step can be undone.
• Irrecoverable (ex. Chess) : In this solution steps cannot be undone.
• Recoverable problem can be solve by slightly more complicated
control strategy, that does some time make mistakes. Back tracking
is necessary to recover from such mistake.
• Ignorable problem can be solve using simple control structure that
never backtracks such control structure is easy to implement.
• Irrecoverable problems will need to be solved by a system that
expands a great deal of effort making each decision since the
decision must be final.
Is a Good Solution Absolute or Relative
• Let us consider the example of predicate logic:

• Marcus was a man.
• Marcus was Pompeian.
• Marcus was born in 40 A.D.
• All men are mortal.
• All Pompeian died when the volcano erupted in 79 A.D.
• No mortal lives longer than 150 years.
• It is now 1991 A.D.
Suppose we ask the question “Is Marcus alive”. The solution of this problem is:
Is a Good Solution Absolute or Relative(cont..)
• 1. Marcus was a man.

• 2. All men are mortal.
• 3. Marcus was born in 40 A.D.
• 7. It is now 1991 A.D.
• 9. Marcus’s age 1991 year.
• 6. No mortal lives longer than 150 years.
• 10. Marcus was dead.
Or (Relative)
• 7. It is now 1991 A.D.
• 5. All Pompeian are dead in 79 A.D.
• 11. All Pompeian are dead now.
• 2. Marcus was a Pompeian.
• 12. Marcus is dead.

Amity School of Engineering and Technology
Types of search algorithms

Based on the search problems we can classify the search algorithmsinto uninformed (Blind search)
search and informed search (Heuristic search) algorithms.
Search space control:

• Uninformed/Blind Search:
• The uninformed search does not contain any domain knowledge such as closeness, the location of the goal. It operates in a brute-
force way as it only includes information about how to traverse the tree and how to identify leaf and goal nodes. Uninformed
search applies a way in which search tree is searched without any information about the search space like initial state operators
and test for the goal, so it is also called blind search.It examines each node of the tree until it achieves the goal node.
• Informed Search
• Informed search algorithms use domain knowledge. In an informed search, problem information is available which can guide the
search. Informed search strategies can find a solution more efficiently than an uninformed search strategy. Informed search is
also called a Heuristic search.
• A heuristic is a way which might not always be guaranteed for best solutions but guaranteed to find a good solution in reasonable
time.
• Informed search can solve much complex problem which could not be solved in another way.
• An example of informed search algorithms is a traveling salesman problem.
Heuristic Search
• Heuristic is a technique that improves the efficiency of a search

process possibly by sacrificing claims of completeness.
• Heuristic are like tour guides.
• They are good to the extent that they point in generally interesting
directions.
• They are bad to the extent that they miss point of interest to
particular individuals.
• Some of heurists help to guide a search process without sacrificing
any claims to completeness that the process might previously had.
• Using good heuristics we can get good solution to hard problem.
Heuristic search uses the Heuristic functions for finding the
solution of problem.
Brute Force or Uninformed Search Strategies

• These are commonly used search procedure which explore all
the alternatives during the search process.
• They do not have any domain specific knowledge.
• They need the initial state, the goal state and a set of legal
operators.
• The strategy gives the order in which the search space is
searched
• The followings are example of uninformed search
–Depth First Search (DFS)
–Breadth First Search (BFS)
Search Strategies: Blind Search
• Breadth-first search
Expand all the nodes of
one level first.
• Depth-first search
Expand one of the nodes at
the deepest level.
Depth First Search
• The search begins by expanding the initial node,

generate all successors of the initial node and test
them.
• Depth-first search always expands the deepest node
in the current frontier of the search tree.
• Depth-first search uses a LIFO approach.
• Depth-first search implemented by STACK.
Algorithm for Depth First Search

1. If the initial state is a goal state, quit and return success.
2. Otherwise, do the following until success or failure is
signaled:
1. Generate a successor, E, of the initial state. If there are
no more successors, signal failure.
2. Call Depth-First Search with E as the initial state.
3. If success is returned, signal success. Otherwise
continue in this loop.
Time and space complexity
Time Complexity :
1 + b + b2 + b3 +…+……bd.
Hence Time complexity =O (bd)
Where b-> branching factor
d-> Depth of a tree
Space Complexity :
Hence Space complexity = O (d)
Advantages of Depth-First Search

• It requires less memory since only the nodes of the current
path are stored.
• By chance, it may find a solution without examining
much of the search space at all.
Disadvantages of Depth-First Search
• Determination of the depth until which the search has to proceed. This
depth is called cut-off depth.
• If the cut-off depth is smaller, solution may not be found.
• If cut-off depth is large, time complexity will be more.
• And there is no guarantee to find a minimal solution, if more than one
solution exists.
Breadth First Search
• Searching processes level by level unlike depth first

search which goes deep into the tree.
• An operator is employed to generate all possible
children of a node.
• Implemented by QUEUE.
• Follow FIFO approaches
Algorithm of Breadth First Search
1. Create a variable called Node-LIST and set it to the initial

state.
2. Until a goal state is found or Node-LIST is empty:
1. Remove the first element from Node-LIST and call it E.
if Node-LIST was empty, quit.
2. For each way that each rule can match the state
described in E do:
1. Apply the rule to generate a new state,
2. If the new state is a goal state, quit and return this
state.
3. Otherwise, add the new state to the end of Node-
LIST.
Time and space complexity
Time Complexity :
1 + b + b2 + b3 +…+……bd.
Hence Time complexity = O (bd)
Space Complexity :
1 + b + b2 + b3 +…+……bd.
Hence Space complexity = O (bd)
Advantages of Breadth-First Search
• Breadth first search will never get trapped exploring the useless
path forever.
• If there is a solution, BFS will definitely find it out.
• If there is more than one solution then BFS can find the minimal
one that requires less number of steps.
Disadvantages of Breadth-First Search
• It requires more memory

• Searching process remembers all unwanted nodes which is of no
practical use for the search.
DFS Vs BFS
DFS BFS
It require less memory because only the It require more memory because all the tree
nodes on the current path are stored. that has so far been generated must be
stored.
It is one in which by luck solution can be While in BFS all parts of the tree must be
found without examining much of the examined to level n before any nodes on
search space at all. level n+1 can be examined.
It does not give optimal solution. It gives optimal solution.
DFS may find a long path to a solution in BFS guarantees to find a solution if it
one part of the tree, when a shorter path exists. Furthermore if there are multiple
exists in some other, unexplored part of the solutions, then a minimal solution will be
tree. found.
Time complexity: O(bd ) Time complexity: O(bd )
where b : branching factor, d: depth where b : branching factor, d: depth
Space complexity: O(d) , d: depth Space complexity: O(bd )
where b : branching factor, d: depth
Search Process
• Uniformed search is a searching technique which have no additional
information about the distance from current state to the goal.
• Informed Search is a another technique which have additional
information about the estimate distance from the current state to the goal.
• Difference between uniformed search and informed search are given :
• Uniformed search technique have access only to the problem definition
whereas Informed search technique have access to heuristic function as
well as problem definition.
Search Process(Cont..)
 Uniformed search is less efficient whereas informed search is

more efficient.
Every action is equally good in uninformed search whereas
Every action is not equally good in informed search.
Many problems are not solved by uniformed search whereas
Most of the problem are solved by informed search.
Uniformed search known as blind search whereas Informed
search is known as heuristic search.
Uniformed search can handle large search problem whereas
Informed search can not handle large search problem.
Uniformed search use more computation whereas Informed
search use less computation.
Heuristic Search
• Heuristic is a technique that improves the
efficiency of a search process possibly by
sacrificing claims of completeness.
• Heuristic are like tour guides.
• They are good to the extent that they point in
generally interesting directions.
• They are bad to the extent that they miss point of
interest to particular individuals.
• Some of heurists help to guide a search process
without sacrificing any claims to completeness that
the process might previously had.
• Using good heuristics we can get good solution to
hard problem. Heuristic search uses the Heuristic
functions for finding the solution of problem.
HEURISTIC SEARCH TECHNIQUES

• The artificial intelligence provides the appropriate search technique to solve the
problem,
• Because the problem that falls within the artificial intelligence are too complex to
be solved by
• the direct technique. Hence AI provides the varieties of heuristic search for
solving these problems.
1.Generate –and –Test
2.Hill Climbing
3.Best- first search
4. Problem reduction
5.Constraint Satisfaction
6.Mean –End analysis
Heuristic Function
A Heuristic (or a heuristic function) takes a look at search algorithms. At each
branching step, it evaluates the available information and makes a decision on which
branch to follow.
It does so by ranking alternatives. The Heuristic is any device that is often effective but
will not guarantee work in every case.
So why do we need heuristics?
• One reason is to produce, in a reasonable amount of time, a solution that is good
enough for the problem in question. It doesn’t have to be the best- an approximate
solution will do since this is fast enough.
• Most problems are exponential. Heuristic Search let us reduce this to a rather
polynomial number. We use this in AI because we can put it to use in situations where
we can’t find known algorithms
Heuristic Search and Heuristic Function

• A heuristic is a function that estimates how close a state is to the goal state.
• ‘Heuristic search’ means that this search algorithm may not find the optimal solution to the problem. However, it
will give a good solution in reasonable time.
• A Heuristic Function is a function that will rank all the possible alternativesat any branching step in search
algorithm based on the availableinformation.
• • It helps the algorithm to select the best route out of possible routes.
• • Well designed heuristic functions can play an important part inefficiently guiding asearch process toward a
solution. Sometimes very simple heuristic functions can provide a fairly good estimate of whether a path is any
good or not.
• The efficiency of a brute-force search can be greatly enhanced by the use of a Heuristic static evaluation function or
heuristic function.
• Heuristic Function can improve the efficiency of a search algorithm in two ways:
•  Leading the algorithm toward a goal state.
•  Pruning off branches that don’t lie on any optimal solution path.
Heuristic Search and Heuristic Function

SOLN:
SOLN:
GENERATE –AND –TEST METHOD

• The generate and test method consist of following steps:
1. Generate a possible solution for some problem. Hence it
generates a particular point in the problem space and for some
other problem it generates a path from start state.
2. Test to see if this is actually a solution by comparing the
chosen point or the endpoint of chosen path to set the
acceptable goal states.
3. If the solution has been found then quit otherwise go to step
(1).
• If the generation of possible solution performed systematically
then this procedure will find a solution eventually.
Unfortunately if the problem space is very large then generate-
and-test takes very long time for finding the solution.
• The generate -and-test algorithm is a depth first search
procedure since the complete solution must be generated before
they can be tested.
HILL CLIMBING
• The Hill Climbing is a variant of generate-and test
procedure. In this method we take the feedback from the
possible solution which is used to help the generator to
decide which direction to move in the search space. In
the pure generate-and-test method the function respond
only yes or no but if the test function is augmented with
heuristic function that provide an estimate of how close a
given state is to a goal state.
• Hill Climbing is often used when a good heuristic
function is available for evaluating state but when no
other useful knowledge is available.
• Example: Suppose you are in unfamiliar city without a
map and you want to get down town .You simply aim for
some location. The heuristic function is just distance
between the current location and the location of the goal.
The desire states are those in which the distance is
minimum
Algorithms
The Key difference is that the use of evaluating function and the task specific knowledge into the control
process .
This algorithm also called as discrete optimization algorithm.
• Utilizes simple heuristic function.
• Hill Climbing = Depth First Search + Heuristic Function
• These is practically no difference between hill climbing and depth-first
search except that the children of the node that has been expanded are
sorted by the remaining distance.
Methods to overcome these problems

Backtracking for local maximum: Backtracking helps in undoing what
has been done so far and permits to try totally different path to attain the
global peak.
• A big jump is the solution to escape from the plateau. A huge jump is
recommended because in a plateau all neighboring points have the same
value.
• Trying different paths at the same time is the solution for
circumventing ridges
SIMULATED ANNEALING
• The simulated annealing as a computational process is
patterned after the physical process of annealing in
which physical substances such as metals are melted
and then gradually cooled until some solid state is
reached. Hence the goal of this process is produce of
minimal energy in final state. Hence we can say this
minimal energy level is equivalent to the heuristic
function. Hence
• We have to minimize the value of heuristic function
of some level in which we found the goal.
• Physical substances usually move from higher energy
level to lower energy level.
• But there is some probability of that transition to
higher energy state will occur.
Steepest Ascent Hill Climbing Algorithm

1. Evaluate the initial state. If it is a goal state then stop and return success. Otherwise,
make initial state as current state.
2. Repeat these steps until a solution is found or current state does not change
a) Select a state that has not been yet applied to the current state.
b) Initialize a new ‘best state’ equal to current state and apply it to produce a newstate.
c) Perform these to evaluate new state
i. If the current state is a goal state, then stop and return success.
ii. If it is better then best state, then make it best state else continue loop with another
new state.
d) Make best state as current state and go to Step 2: b) part.
3. Exit
BEST-FIRST SEARCH
• Best-first search is a search algorithm, which explores a graph by
expanding the most promising node chosen according to a
specified rule.
• Judea Pearl described best-first search as estimating the promise of
node n by a “heuristic evaluation function f(n) which, in general,
may depend on the description of n, the description of the goal, the
information gathered by the search up to that point, and most
important, on any extra knowledge about the problem domain.”
• Some authors have used “best-first search” to refer specifically to
a search with a heuristic that attempts to predict how close the end
of a path is to a solution, so that paths, which are judged closer to
a solution, are extended first. This specific type of search is called
greedy best-first search.
• Efficient selection of the current best candidate for extension is
typically implemented using a priority queu
ALGORITHM: BEST FIRST SEARCH

1. OR-GRAPHS:-
• This algorithm will operate by searching a directed graph in which each node
represents a point in the problem space. Each node will contain to a description
of the problem state it represents and how promising node it is. The list of
successor will make it possible if a better node or path found to an existing
node then to propagate the improvement down to its successor. Hence this type
of graph called OR - graph. Since each of its branches represent an alternative
problem-solving path.
• In each step of the best first search process we select the most promising node
with the help appropriate heuristic function to each of them. After that we
expand the chosen node rules to generate its successor. If one of them is
solution then we quit otherwise again the most promising node if selecting and
process continues. This search can return to it whenever all other gets bad i.e.
the again most promising path.
OR-GRAPHS(cont..)
OR-GRAPHS(cont..)
• As shown above fig beginning of best first procedure there is one node we expand it . We
generate three nodes. The heuristic function, which is an estimate of the cost of getting to
solution from a given node, is applied to each of these new nodes. Since node D is most
promising node we expand it producing two-successor node E and F. But at this stage we
look another, which is going through B, is more promising. Hence we expand it and
generate G and H. But again when these two nodes are evaluated they look less promising
than other path. So the attention is returned to the path D and E and E is then expand
producing J and I. At next stage J is expanded since it is more promising. This process can
continue until a solution is found.
To implement such graph –search procedure we need two lists of nodes.
• OPEN: Open is actually a priority queue in which the elements with highest –priority are those with most
promising value of the heuristic function. Hence the nodes that has been generated and have heuristic function but
it is not examined.
• CLOSE: In this list we keep the node that already examined. We keep these nodes in memory because whenever a
new node is generated we need to check whether it has been generated before.
BEST FIRST SERACH EXAMPLE:

BEST FIRST SERACH EXAMPLE:

THE A* ALGORITHM
• The best first search algorithm can be simplified of an algorithm called

A*Algorithm in which we use heuristic function g, h`, f`. g is the measure of
cost getting from initial state to current state (node).
• The function h’ is an estimate of the additional cost of getting from current
node to a goal state.
• This is the place where knowledge about the problem domain is exploited. The
combined function f ‘=g+ h’ represent an estimate of the cost of getting from
the initial state to a goal state along the path that generate the current node.
• If more than one path generate the node then the algorithm will record the
best one.
• A* algorithm can be used whether we are interested in finding a minimal cost.
THE A* ALGORITHM
A* algorithm was given by Hart, Nilsson and Rafael in 1968.
• A* is a Best First Search algorithm with f(n) = 𝒈 𝒏 + 𝒉 (𝒏)
where𝑔(𝑛)= sum of edge costs from start to 𝑛.h(𝑛) = estimate of lowest cost
path from 𝑛 to goal. 𝑓(𝑛)= actual distance so far + estimated distance remaining.
• A* is Optimal and Admissible both.
Role of g function: This lets us choose which node toexpand next on the basis
of not only of how good the node
itself looks, but also on the basis of how good the path tothe node was.
h’: the distance of a node to the goal. If h’ is a perfectestimator of h, then A*
will converge immediately to the goal with no search.
THE A* ALGORITHM(cont..)
1. Start with OPEN containing only the initial node. Set the nodes g value to zero
then it h’ value to whatever it is and its f’ value to f=g+h’ 0+h=h’. Set closed
to empty list.
2. Until a goal node is found repeat the following procedure.
• If there are no node in OPEN report failure otherwise pick the node on OPEN
with lowest f’ value and call is BESTNODE.
• Remove it from OPEN and place on CLOSED and see if BESTNODE is a goal
state then exit otherwise generate the successor of BESTNODE.
• For each SUCCESSOR do the following
• Set SUCCESSOR to point back to BESTNODE. These backwards links will make it possible to recover
the path once a solution is found.
• Compute g’ (SUCCESSOR) = g(BESTNODE) + the cost of getting from BESTNODE to SUCCESSOR.
• See if SUCCESSOR is the same as any node on OPEN then call node OLD because this node already
exists.
• We can throw SUCCESSOR away and add OLD to the list of BESTNODE’ s SUCCESSOR. At this
point we must decide whether OLD’ s parent link reset to the point of BESTNODE.
• We have just found SUCCESSOR is cheaper than the current best path to OLD.
• Hence we see whether it is cheaper to get to OLD via its current parent or to SUCCESSOR via
BESTNODE by comparing their g values. If OLD is cheaper then we do nothing.
• If SUCCESSOR is cheaper then reset OLD’ s parent link to point to BESTNODE record the new cheaper
path in g(OLD) and update f ‘(OLD).
• If the SUCCESSOR was not an OPEN see if it is CLOSED, if so called node on CLOSED
OLD and add OLD to the list of BESTNODE’ s successor.
• At that time check to see if the new path or old path is better then set the parent link and g
and f’ values appropriately. If we have just found a better path to OLD we propagate the
improvement to OLD successor.
• TO propagate the new cost downward changing the each node g and f’ value and
terminating each branch when you reach either a node with no successor or a node to which
an equivalent or better path was already been found.
• If the successor was not already on either OPEN or CLOSED then put it on OPEN and add
it to the list of BESTNODES successor and compute
• F’ (SUCCESSOR)=g(SUCCESSOR)+h’(SUCCESSOR)
Advantage of A* Algorithm:
• A* is both complete and admissible. Thus A* always finds
an optimal path, if one exists.
* Best serach algorithms.
* Solve complex problem easily.
Disadvantage of A* Algorithm:
• It is costly if the computation cost is high.
* does not always provide shortest path.
* Complexity issue.
* Requires memory
SOLN:
A* Example:
Concept:
Branch and Bound: Step 1: Traverse the root node.
Step 2: Traverse any neighbour of the root node that is
maintaining least distance from the root node.
Step 3: Traverse any neighbour of the neighbour of the
root node that is maintaining least distance from the
root node.
Step 4: This process will continue until we are getting
the goal node.
Branch and Bound is an algorithmic technique which
finds the optimal solution by keeping the best solution
found so far. If partial solution can’t improve on the
best it is abandoned, by this method the number of
nodes which are explored can also be reduced. It also
deals with the optimization problems over a search
that can be presented as the leaves of the search tree.
The usual technique for eliminating the sub trees
from the search tree is called pruning. For Branch and
Bound algorithm we will use stack data structure.
Branch and Bound:

Algorithm:
Step 1: PUSH the root node into the stack.
Step 2: If stack is empty, then stop and return failure.
Step 3: If the top node of the stack is a goal node, then stop and return success.
Step 4: Else POP the node from the stack. Process it and find all its successors.
Find out the path containing all its successors as well as predecessors and then
PUSH the successors which are belonging to the minimum or shortest path.
Step 5: Go to step 5.
Step 6: Exit.
Branch and Bound:

Branch and Bound:

PROBLEM REDUCTION :-
• Sometimes problems only seem hard to solve. A hard problem may be one
that can be reduced to a number of simple problems...and, when each of the
simple problems is solved, then the hard problem has been solved.
• Problem reduction may be defined as planning how best to solve a problem
that can be recursively decomposed into subproblems in multiple ways.
• When a problem can be divided into a set of sub problems, where each sub
problem can be solved separately and a combination of these will be a
solution, AND-OR graphs or AND - OR trees are used for representing the
solution.
1. AND- OR GRAPH
• AND-OR is useful for representing the solution of the problems that can be solved by
decomposing them into a set of smaller problems after that all of them solved.
• This decomposition or reduction generates arc that we call AND arcs.
• One AND arc may point to any number of successor nodes all of which must be
solved in order for the arc to point to a solution just as in OR graph.
• Hence different arc may come from single node indicating variety of ways in which
the original problem might be solved.
• Hence this type of structure is called AND-OR graph. AND arcs are indicated with a
line connecting to all the components
1. AND- OR GRAPH(cont..)
 This type of algorithm finds a path from the starting node of the graph to a set of
nodes representing the solution.
 Also it may be necessary to get to more than one solution state since each arm of
AND arc must lead to its own solution node.
 The number at each node represent the value of f’ at that node.
 Hence for every operation has a uniform cost so each arc with a single successor
has a cost of 1 and each AND arc with multiple successor has a cost of 1 for each
of its components. For example consider:
1. AND- OR GRAPH(cont..)
• Here we expand B with cost 5. In AND-OR algorithm we describe a node value and call
it FUTILITY.
• If the estimated cost of solution is greater than the value of FUTILITY then we quit the
search.
• FUTILITY is threshold such that any solution with a cost above it is too expensive to
be practical.
2. AO*(AO star) algorithms
• The main difference between the A*(A star)

and AO*(AO star) algorithms is that A* algo is a OR
graph algorithm and AO* is a AND-OR graph http://algorithm.In OR
graph algorithm it just find only one solution (i.e either OR solution means
this OR this OR this).But in the AND-OR graph algo it find more than one
solution
• AO*is a best-first algorithm for solving a cyclic AND/OR graphs.
AO*(AO star) algorithms(cont..)
• Initialise the graph to start node
• Traverse the graph following the current path accumulating nodes that have not yet been expanded or
solved
• Pick any of these nodes and expand it and if it has no successors call this value FUTILITY otherwise
calculate only f' for each of the successors.
• If f' is 0 then mark the node as SOLVED
• Change the value of f' for the newly created node to reflect its successors by back propagation.
• Wherever possible use the most promising routes and if a node is marked as SOLVED then mark the
parent node as SOLVED.
• If starting node is SOLVED or value greater than FUTILITY, stop, else repeat from 2.
AO* algorithm
1. Let G be a graph with only starting node INIT.
2. Repeat the followings until INIT is labeled SOLVED or h(INIT) >
FUTILITY
a) Select an unexpanded node from the most promising path from INIT (call it NODE)
b) Generate successors of NODE. If there are none, set h(NODE) = FUTILITY (i.e.,
NODE is unsolvable); otherwise for each SUCCESSOR that is not an ancestor of
NODE do the following:
i. Add SUCCESSSOR to G.
ii. If SUCCESSOR is a terminal node, label it SOLVED and set h(SUCCESSOR) = 0.
iii. If SUCCESSPR is not a terminal node, compute its h
AO* algorithm (Cont.)
c) Propagate the newly discovered information up the graph by doing the
following: let S be set of SOLVED nodes or nodes whose h values have been
changed and need to have values propagated back to their parents. Initialize S
to Node. Until S is empty repeat the followings:
i. Remove a node from S and call it CURRENT.

ii. Compute the cost of each of the arcs emerging from CURRENT. Assign minimum cost
of its successors as its h.
iii. Mark the best path out of CURRENT by marking the arc that had the minimum cost in
step ii
iv. Mark CURRENT as SOLVED if all of the nodes connected to it through new labeled arc
have been labeled SOLVED
v. If CURRENT has been labeled SOLVED or its cost was just changed, propagate its new
cost back up through the graph. So add all of the ancestors of CURRENT to S.
An Example
An Example
(8) A
An Example
[12] A [13]
4 5
5
(1) B D (8)
(2)
C
An Example
[15] A [13]
4 5
5
(4) B 2 D (8)
(2)
C
[15] A [8]
An Example
4 5
5
(4) B 2 D (3)
(2)
C 2
4
(1) E
(0) G
An Example
[15] A [9]
4 5
5
(4) B 2 D (4)
(2)
C 2
2
4
(3) E
3
(0) G
An Example [15] A Solved

4 5
5
(4) B 2 D Solved
(2)
C 2
2
4
(3) E
3
(0) G Solved
Assignment Question
Figure represents an AO graph with the values labeled as follows. The value in a single line circle is an estimate of
cost. The value in a double lined circle, a SOLVED node, is the actual value. Each edge is labeled with a different
cost. What is the value of the root node for the optimal solution for the AO graph?
Soln:
Advantages
• It is an optimal algorithm.
• If traverse according to the ordering of nodes.
• It can be used for both OR and AND graph.
Disadvantages
• Sometimes for unsolvable nodes, it can’t find the optimal path.
Constraint Satisfaction
• In artificial intelligence and operations research, constraint satisfaction is the
process of finding a solution to a set of constraints that impose conditions that
the variables must satisfy.
• Constraint satisfaction problems (CSPs) are mathematical problems defined as a set of
objects whose state must satisfy a number of constraints or limitations.
• CSPs represent the entities in a problem as a homogeneous collection of finite constraints over
variables, which is solved by constraint satisfaction methods.
• CSPs are the subject of intense research in both artificial intelligence and operations research,
since the regularity in their formulation provides a common basis to analyse and solve problems.
Crypt-arithmetic puzzle 
SEND
MORE
MONEY
• We have every letters standing for a digit

and every letter stands for a different digit.
• We have to find an assignment of letters to digits
such that a given arithmetic formula is correct.
• Variables are D, E, M, N, O, R, S, Y
• Domains are
– {0, 1,2,3,4,5,6,7,8,9} for D, E,N,O,R,Y
– {1,2,3,4,5,6,7,8,9} for S, M
Constraints for this problem

Constraint 1:
We can write one long constraint for the sum.
1000* S + 100* E+10* N+ D
+ 1000* M+ 100* O+10* R+ E
………………………………………….
10000*M + 1000* O+ 100*N+ 10* E+
Y
Constraint 2:
alldifferentr(D, E, M, N, O, R, S, Y)
These two constraints express the
problem precisely.
Solution
• Rules for propagating constraints generates the following constraints:
1. M = 1, since two single-digit numbers plus a carry can not total more than 19.
2. S = 8 or 9, since S+M+C3 > 9 (to generate the carry) and M = 1, S+1+C3>9, so S+C3 >8 and
C3 is at most 1.
3. O = 0, since S + M(1) + C3(<=1) must be at least 10 to generate a
carry and it can be most 11. But M is already 1, so O must be 0.
4. N = E or N=E+1, depending on the value of C2. But N cannot have the same value as E. So N =
E+1 and C2 is 1.
5. In order for C2 to be 1, the sum of N + R + C1 must be greater than 9, so N + R must be greater than 8.
6. N + R cannot be greater than 18, even with a carry in so E cannot be 9.
Solution...
• Suppose E is assigned the value 2.
• The constraint propagator now observes that:
• N = 3 since N = E + 1.
• R = 8 or 9, since R + N (3) + C1 (1 or 0) = 2 or 12. But since N is
already 3, the sum of these nonnegative numbers cannot be less than 3.
Thus R + 3 +(0 or 1) = 12
and R = 8 or 9.
• 2 + D = Y or 2 + D = 10 + Y, fro the sum in rithmost
column.
Start
M=1
SEND
S = 8 or 9
Initial state: O=0
N=E+1
 MORE
• No two letters have
the same value. C2 = 1 MONEY
N+R>8
• The sum of the digits E9
must be as shown. E=2
N=3
R = 8 or 9 M=1
2 + D = 10* C1 + Y R=
M=1 C1+N+R=10+E 8
R=9 C1 = 0 C1 = 1 S=9
M=1
S=8 R= E=2
E=2 2+D=Y 8 N=3
2 + D = 10 + Y
N=3 N + R = 10 + E S=9
D=8+Y O=0
O=0 R=9 E=2
N=3 R=8, S=9 D=9
D=4 S =8
O=0 D=8 Y=1
Y =6 D=8
Y=0 Y=0 Y=1
D=9
Conflict
17
Conflict Conflict
Start
M=1
SEND
S = 8 or 9
Initial state: O=0
N=E+1
 MORE
• No two letters have
the same value. C2 = 1 MONEY
N+R>8
• The sum of the digits E9
must be as shown. E=5
N=6
R = 8 or 9
5 + D = 10* C1 + Y
M=1 C1+N+R=10+E
R=9 M=1
C1 = 0 C1 = 1 R=
S=8 8
E=5 5+D=Y S=9
N=6 N + R = 10 + E R=8, S=9
E=5
N=6
O=0 R=9 5 + D = 10 + Y O=0
D=2 S =8 D=5+Y D=7
Y =7 D=7 Y=2
Y=2
Conflict
• M=1
Final solution
• R=8
• S=9
• E=5
• N=6
• O=0
• D=7
• Y=2
• C1=1
• C2=1
• C3=0
• C4=1
SOLVE
• US +AS=ALL
• SHE +THE=BEST
• CROSS+ROADS=DANGER
• DAYS+TOO=SHORT
Exercise
Solution
Rule 1: Well you can see that the DANGER has one more letter than CROSS and ROADS, and the extra letter
is D. That means that C + R equals something more than 10. Which also means D is 1.
Rule 2: Oh look, S + S = R. That means that R must be even. We have a choice of 4, 6 and 8, because if R was 2,
S would have to be 1, and D is already 1. Let's try 6 for the value of R, because we need high numbers if we
want C
+ R to equal something more than 10. Oh look, if R is 6 and S is R divided by 2, then S must be 3!
Rule 3: S+D=E, 3+1=4, So, E=4
Rule 4: And since we now only have 4 spots in the key left, we choose the highest number for C, which is 9.
Again, we need high numbers to make C
+ R equal something more than 10.
Rule 5: In the equation, O + A = G. We have 2, 5, 7 and 8 vacant. Let's play around with these letters. Let's see if
we can find an equation in there. Yes! There is an equation there. 5 + 2 = 7! So G must equal 7. We know that
9 + 6 = 15, but it's missing the 5! So, A must equal 5. In turn, this leads to O having to be 2 (do the maths, O
+ 5 = 7). And last of all, O is 2, so 6 + 2 (6 + O) = N But 6 + 2 = 8, so now N is 8. We now have the following
equation...
• 96233
62513
158746
And the following key...
• C=9
• R=6
• O=2
• S=3
• A=5
• D=1
• E= 4
• N=8
G=7
CSP Example: Cryptarithmetic puzzle

Problem:
Problem Statement SEND
How to assign decimal digits to  MORE

MONEY
letters, so that the following sum
is valid? Assume that we already
know that
• The possible digits set for the SEND
letters is {0,1,2,…9}; + MORE
• M must be 1; --------
MONEY
• Two different letters can't be
assigned the same digit
using c1,c2 and c3 to represent carries

changing problem to solve 4 equations
S E N D D+E = Y+10*C1
M O R E C1+N+R = E+10*C2
+ C3 C2 C1 C2+E+O = N+10*C3
---------------------- C3+S+M = O+10*M
M O N E Y
SOLUTION
Class –Test Question

Solve the following Crypt Arithmetic problem.
KANSAS + OHIO = OREGON

Means End Analysis

• MEA is a problem solving technique used currently in AI for
limiting search in AI
• It is a mixture of Backward and forward search technique.
• The MEA technique was first introduced in 1961 by Allen
Newell, and Herbert A.
• The MEA analysis process centred on the evaluation of the
difference between the current state and goal state
How it works
• Evaluate the difference between Initial State and final State
• Select the various operators which can be applied for each difference
• Apply the operator at each difference, which reduces the difference
between the current state and goal state
Algorithm for MEA

Let us take Current state as CURRENT and Goal
State as GOAL
• Step 1: Compare CURRENT to GOAL, if there are
no differences between both then return Success and
Exit.
• Step 2: Else, select the most significant difference
and reduce it by doing the following steps until the
success or failure occurs.
Contd.
• Select a new operator O which is applicable for the current difference, and if
there is no such operator, then signal failure.
• Attempt to apply operator O to CURRENT. Make a description of two states.
i) O-Start, a state in which O?s preconditions are satisfied.
ii) O-Result, the state that would result if O were applied In O-start.
contd
• If
(First-Part <------ MEA (CURRENT, O-START)
And
(LAST-Part <----- MEA (O-Result, GOAL), are successful, then
signal Success and return the result of combining FIRST-PART, O, and
LAST-PART.
Example
• The image above shows that there is a difference between the

current state and the target state. This indicates that there is a need
to make adjustments to the current state to reach the end goal.
Contd
Delete operator: The dot symbol at the top right corner in the initial state
does not exist in the goal state. The dot symbol can be removed by
applying the delete operator.
contd
• Move operator: compare the new state with the end state. The green
diamond in the new state is inside the circle while the green diamond
in the end state is at the top right corner. We will move this diamond
symbol to the right position by applying the move operator.
contd
• Expand operator: After evaluating the new state generated in step 2, we find that the
diamond symbol is smaller than the one in the end state. We can increase the size of
this symbol by applying the expand operator.

Module 1 AI

Uploaded by

Copyright:

Available Formats

Module 1 AI

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Module 1 AI

Uploaded by

Copyright:

Available Formats

Amity School of Engineering & Technology

“A system's ability to correctly interpret external data,

Some task domain of AI

Some task domain of AI(Cont..)

• Artificial Intelligence can be

AI type-1: Based on Capabilities

AI type-2: Based on functionality

The Underlying Assumption:

The Underlying Assumption(Cont..)

• Search: This technique provides a way of solving problems

The Level of Model

The Level of Model (cont..)

• To test psychological theories of human performance.

• To enable computer to understand human reasoning.

• To enable people to understand computer reasoning.

Criteria for Success

The Turing Test

Turing Test (Cont..)

Natural Language Processing (NLP)

Why Is Natural Language Processing Important?

Computer Vision Scope

Computer Vision (Cont..)

Low Level Mid Level High Level

Image Processing To Computer Vision

What is an Expert System?

Defining the Problem as a State Space Search

Defining the Problem as a State Space Search(cont..)

Water Jug Problem

Production Rules of WJ Problem

Three water Jug problem:

The production rules are formulated as follows:

So finally the state will be (4, 4, 0)

Missionaries and Carnivals Problem

Missionaries and Carnivals Problem

• In order to choose the most appropriate method for a particular

• There are some constraints for

Can Solution step be ignored or undone

• There are generally three class of problem.

• Let us consider the example of predicate logic:

• 1. Marcus was a man.

Types of search algorithms

Search space control:

• Heuristic is a technique that improves the efficiency of a search

Brute Force or Uninformed Search Strategies

Search Strategies: Blind Search

Depth First Search

• The search begins by expanding the initial node,

Algorithm for Depth First Search

Time and space complexity

Advantages of Depth-First Search

Disadvantages of Depth-First Search

Breadth First Search

• Searching processes level by level unlike depth first

Algorithm of Breadth First Search

1. Create a variable called Node-LIST and set it to the initial

Time and space complexity

Advantages of Breadth-First Search

Disadvantages of Breadth-First Search

• It requires more memory

 Uniformed search is less efficient whereas informed search is