UNIT - I

Syllabus: Introduction to artificial intelligence: Introduction, history, intelligent

systems, foundations of AI, applications, tic-tac-tie game playing, development of
AI languages, current trends in AI.
Problem solving-state-space search and control strategies: Introduction, general
problem solving, characteristics of problem, exhaustive searches, heuristic search
techniques, iterative- deepening a*, constraint satisfaction.
Introduction:
 The field of artificial intelligence, or AI, attempts to understand intelligent entities.
 Computers with human-level intelligence (or better) would have a huge impact on our
everyday lives and on the future course of civilization.
 Computers have unlimited potential for intelligence.
 AI currently encompasses a huge variety of subfields, from general-purpose areas
such as perception and logical reasoning, to specific tasks such as playing chess,
proving mathematical theorems, writing poetry, and diagnosing diseases.
Definitions of artificial intelligence:
Definitions of AI vary along following dimensions.
 thought processes and reasoning
 address behaviour
 measure success in terms of human performance,
 measure against an ideal concept of intelligence, which we will call rationality
 A system is ―rational‖ if it does the right thing.
Definitions are organized into four categories:

 Systems that think like humans: The exciting new effort to make computers

Dr. Ram Prasad Reddy Sadi Page 1

 UNIT - I

think machines with minds.

 Systems that think rationally: The study of the computations that make it
possible to perceive, reason, and act.
 Systems that act like humans: The study of how to make computers do
things at which, at the moment, people are better.
 Systems that act rationally: The branch of computer science that is
concerned with the automation of intelligent behaviour.
 The Turing Test, proposed by Alan Turing (1950), was designed to provide a
satisfactory operational definition of intelligence.
 Turing defined intelligent behaviour as the ability to achieve human-level
performance in all cognitive tasks, sufficient to fool an interrogator.
 The test he proposed is that the computer should be interrogated by a human
via a teletype, and passes the test if the interrogator cannot tell if there is a
computer or a human at the other end.
The computer would need to possess the following capabilities:
 natural language processing to enable it to communicate successfully in
English (or some other human language);
 knowledge representation to store information provided before or during the
interrogation;
 automated reasoning to use the stored information to answer questions and to
draw new conclusions
 machine learning to adapt to new circumstances and to detect and extrapolate
patterns.
 Turing's test deliberately avoided direct physical interaction between the interrogator
and the computer, because physical simulation of a person is unnecessary for
intelligence.
 To say that a given program thinks like a human, we must have some way of
determining how humans think. We need to get inside the actual workings of human
minds.
There are two ways for this:
 through introspection—trying to catch our own thoughts as they go by.
 through psychological experiments
Once we have a sufficiently precise theory of the mind, it becomes possible to express the
theory as a computer program. If the program's input/output and timing behaviour matches
human behaviour, that is evidence that some of the program's mechanisms may also be
operating in humans.
The Greek philosopher Aristotle was one of the first to attempt to codify "right thinking," that
is, irrefutable reasoning processes.
His famous syllogisms provided patterns for argument structures that always gave correct
conclusions given correct premises. For example, "Socrates is a man; all men are mortal;
therefore Socrates is mortal."

Dr. Ram Prasad Reddy Sadi Page 2

 UNIT - I

These laws of thought were supposed to govern the operation of the mind, and initiated the
field of logic.
There are two main obstacles to this approach.
 First, it is not easy to take informal knowledge and state it in the formal terms
required by logical notation, particularly when the knowledge is less than
100% certain.
 Second, there is a big difference between being able to solve a problem "in
principle" and doing so in practice.
Acting rationally: The rational agent approach:
 Acting rationally means acting so as to achieve one's goals, given one's
beliefs.
 An agent is just something that perceives and acts.
 In this approach, AI is viewed as the study and construction of rational agents.
In the ‗laws of thought" approach to AI, the whole emphasis was on correct
inferences.
 Making correct inferences is sometimes part of being a rational agent, because
one way to act rationally is to reason logically to the conclusion that a given
action will achieve one's goals, and then to act on that conclusion.
 Correct inference is only a useful mechanism for achieving rationality, and not
a necessary one.
Foundations of Artificial Intelligence:
 AI itself is a young field; it has inherited many ideas, viewpoints, and techniques from
other disciplines.
 Over 2000 years of tradition in philosophy, theories of reasoning and learning have
emerged, along with the viewpoint that the mind is constituted by the operation of a
physical system.
 From over 400 years of mathematics, we have formal theories of logic, probability,
decision making, and computation.
 From psychology, we have the tools with which to investigate the human mind, and a
scientific language within which to express the resulting theories.
 From linguistics, we have theories of the structure and meaning of language.
 From computer science, we have the tools with which to make AI a reality.
Philosophy (428 B.C.-present)
 We have the idea of a set of rules that can describe the working of (at least part of) the
mind, the next step is to consider the mind as a physical system.
 Mental processes and consciousness are therefore part of the physical world, but
inherently unknowable; they are beyond rational understanding.
 Some philosophers critical of AI have adopted exactly this position.
 Barring these possible objections to the aims of AI, philosophy had thus established a
tradition in which the mind was conceived of as a physical device operating

Dr. Ram Prasad Reddy Sadi Page 3

 UNIT - I

principally by reasoning with the knowledge that it contained.

 All knowledge can be characterized by logical theories connected, ultimately, to
observation sentences that correspond to sensory inputs.
 Confirmation theory of Rudolf Carnap and Carl Hempel attempted to establish the
nature of the connection between the observation sentences and the more general
theories— understand how knowledge can be acquired from experience.
Mathematics (800 B.C. -present)
 AI used mathematical formalization in three main areas: computation, logic, and
probability.
 First-order logic is used today as the most basic knowledge representation system.
 Theory of reference that shows how to relate the objects in a logic to objects in the
real world.
 There are some functions on the integers that cannot be represented by an algorithm—
that is, they cannot be computed.
 This motivated Alan Turing (1912-1954) to try to characterize exactly which
functions are capable of being computed.
 Church-Turing thesis, which states that the Turing machine (Turing, 1936) is capable
of computing any computable function, is generally accepted as providing a sufficient
definition.
Psychology (1879-present)
 The view that the brain possesses and processes information, is the principal
characteristic of cognitive psychology,
 The three key steps of a knowledge-based agent:
o The stimulus must be translated into an internal representation,
o The representation is manipulated by cognitive processes to derive new
internal representations,
o These are in turn retranslated back into action.
 For artificial intelligence to succeed, we need two things: intelligence and an artifact.
 The computer has been unanimously acclaimed as the artifact with the best chance of
demonstrating intelligence.
 AI also owes a debt to the software side of computer science, which has supplied the
operating systems, programming languages, and tools needed to write modern
programs.
 AI has pioneered many ideas that have made their way back to "mainstream"
computer
 science, including time sharing, interactive interpreters, the linked list data type,
automatic storage management, and some of the key concepts of object-oriented
programming and integrated program development environments with graphical user
interfaces.
Linguistics (1957-present)

Dr. Ram Prasad Reddy Sadi Page 4

 UNIT - I

 Understanding language requires an understanding of the subject matter and context,

not just an understanding of the structure of sentences.
 Much of the early work in knowledge representation (the study of how to put
knowledge into a form that a computer can reason with) was tied to language and
informed by research in linguistics, which was connected in turn to decades of work
on the philosophical analysis of language.
 Modern linguistics and AI were "born" at about the same time, so linguistics does not
play a large foundational role in the growth of AI. Instead, the two grew up together,
intersecting in a hybrid field called computational linguistics or natural language
processing, which concentrates on the problem of language use.
The History of Artificial Intelligence
The gestation of artificial intelligence (1943-1956)
 The first work that is now generally recognized as AI was done by Warren
McCulloch and Walter Pitts (1943). They drew on three sources:
 knowledge of the basic physiology
 function of neurons in the brain
 the formal analysis of propositional logic
 Turing's theory of computation: They proposed a model of artificial neurons in which
each neuron is characterized as being "on" or "off," with a switch to "on" occurring in
response to stimulation by a sufficient number of neighbouring neurons.
 Claude Shannon (1950) and Alan Turing (1953) were writing chess programs for von
Neumann-style conventional computers.
 At the same time, two graduate students in the Princeton mathematics department,
Marvin Minsky and Dean Edmonds, built the first neural network computer in 1951.
Early enthusiasm, great expectations (1952-1969)
 Newell and Simon's early success was followed up with the General Problem Solver,
or GPS. Unlike Logic Theorist, this program was designed from the start to imitate
human problem-solving protocols.
 Within the limited class of puzzles it could handle, it turned out that the order in
which the program considered subgoals and possible actions was similar to the way
humans approached the same problems. Thus, GPS was probably the first program to
embody the "thinking humanly" approach.
 Herbert Gelernter (1959) constructed the Geometry Theorem Prover. Like the Logic
Theorist, it proved theorems using explicitly represented axioms.
 Gelernter soon found that there were too many possible reasoning paths to follow,
most of which turned out to be dead ends.
 Arthur Samuel wrote a series of programs for checkers (draughts) that eventually
learned to play tournament-level checkers. Along the way, he disproved the idea that
computers can only do what they are told to, as his program quickly learned to play a
better game than its creator.
 McCarthy defined the high-level language Lisp, which was to become the dominant
AI programming language.

Dr. Ram Prasad Reddy Sadi Page 5

 UNIT - I

 Rosenblatt proved the famous perceptron convergence theorem, showing that his
learning algorithm could adjust the connection strengths of a perceptron to match any
input data.
A dose of reality (1966-1974)
 Most of the early AI programs worked by representing the basic facts about a problem
and trying out a series of steps to solve it, combining different combinations of steps
until the right one was found.
 The early programs were feasible only because micro worlds contained very few
objects.
 Before the theory of NP-completeness was developed, it was widely thought that
"scaling up" to larger problems was simply a matter of faster hardware and larger
memories.
 Resolution theorem proving, was soon dampened when researchers failed to prove
theorems involving more than a few dozen facts.
 A two-input perceptron could not be trained to recognize when its two inputs were
different.
 Although their results did not apply to more complex, multilayer networks, solved the
problem.
 The new back-propagation learning algorithms for multilayer networks that were to
cause an enormous resurgence in neural net research.
 General-purpose search mechanism performs elementary reasoning steps to find
complete solutions. Such approaches are called weak methods, because they use weak
information about the domain.
 The only way around this is to use knowledge more suited to making larger reasoning
steps and to solving typically occurring cases in narrow areas of expertise.
 The DENDRAL program solves the problem of inferring molecular structure from
the information provided by a mass spectrometer.
 The input to the program consists of the elementary formula of the molecule, and the
mass spectrum giving the masses of the various fragments of the molecule generated
when it is bombarded by an electron beam.
 The naive version of the program generated all possible structures consistent with the
formula, and then predicted what mass spectrum would be observed for each.
 The significance of DENDRAL was that it is the first successful knowledge-intensive
System.
 MYCIN diagnoses blood infections. With about 450 rules, MYCIN was able to
perform as well as some experts, and considerably better than junior doctors.
 It also contained two major differences from DENDRAL.:
o First, unlike the DENDRAL rules, no general theoretical model existed from
which the MYCIN rules could be deduced. They had to be acquired from
extensive interviewing of experts, who in turn acquired them from direct
experience of cases.
o Second, the rules had to reflect the uncertainty associated with medical

Dr. Ram Prasad Reddy Sadi Page 6

 UNIT - I

knowledge. MYCIN incorporated a calculus of uncertainty called certainty

factors.
 In 1981, the Japanese announced the "Fifth Generation" project, a 10-year plan to
build intelligent computers running Prolog in much the same way that ordinary
computers run machine code.
 It has the ability to make millions of inferences per second.
 The project proposed to achieve full-scale natural language understanding, among
other ambitious goals.
 The booming AI industry also included companies such as Carnegie Group,
Inference,
 Intellicorp, and Teknowledge that offered the software tools to build expert systems,
and hardware companies such as Lisp Machines Inc., Texas Instruments, Symbolics,
and Xerox that were building workstations optimized for the development of Lisp
programs.
The return of neural networks (1986-present)
 Back-propagation learning was applied to many learning problems in computer
science and psychology, and the widespread dissemination of the results in Parallel
Distributed Processing.
 In recent years, approaches were based on hidden Markov models (HMMs) which are
based on a rigorous mathematical theory. These are generated by a process of training
on a large corpus of real speech data.
Intelligent Systems
 Intelligence: The ability of a system to calculate, reason, perceive relationships and
analogies, learn from experience, store and retrieve information from memory, solve
problems, comprehend complex ideas, use natural language fluently, classify,
generalize, and adapt new situations.
 Intelligent systems are technologically advanced machines that perceive and respond
to the world around them.
 An intelligent system is a computer-based system that can represent reason about, and
interpret data.
An intelligent system is a system with artificial intelligence.

 Reasoning − It is the set of processes that enables us to provide basis for judgement,
making decisions, and prediction.

Dr. Ram Prasad Reddy Sadi Page 7

 UNIT - I

 Learning − It is the activity of gaining knowledge or skill by studying, practising,

being taught, or experiencing something.
 Problem solving- It is the process of selecting the best suitable alternative out of
multiple alternatives to reach the desired goal are available.
 Perception − It is the process of acquiring, interpreting, selecting, and organizing
sensory information. Perception presumes sensing. In humans, perception is aided by
sensory organs. In the domain of AI, perception mechanism puts the data acquired by
the sensors together in a meaningful manner.
 Linguistic Intelligence − It is one‘s ability to use, comprehend, speak, and write the
verbal and written language. It is important in interpersonal communication.
Applications of AI
Air Operations Division (AOD) - uses AI for the rule based expert systems.
 The AOD has use for artificial intelligence for surrogate operators for combat and
training simulators, mission management aids, support systems for tactical decision
making, and post processing of the simulator data into symbolic summaries.
o Airplane simulators are using artificial intelligence in order to process the data
taken from simulated flights.
o Simulated aircraft warfare computers are able to come up with the best
success scenarios in these situations
Computer Science: AI researchers have created many tools to solve the most difficult
problems in computer science.
 time sharing
 interactive interpreters,
 graphical user interfaces and the computer mouse
 rapid development environments
 the linked list data structure
 automatic storage management
 symbolic programming
 functional programming
 dynamic programming
 object-oriented programming
Education: Number of companies that create robots to teach subjects to children ranging
from biology to computer science.
 Intelligent tutoring systems: An ITS called SHERLOCK teaches Air Force
technicians to diagnose electrical systems problems in aircraft. Another example is
DARPA, Defense Advanced Research Projects Agency, which used AI to develop a
digital tutor to train its Navy recruits in technical skills in a shorter amount of time.
Finance: Algorithmic Trading involves the use of complex AI systems to make trading
decisions at speeds several orders of magnitudes greater than any human is capable of, often
making millions of trades in a day without any human intervention. Such trading is called

Dr. Ram Prasad Reddy Sadi Page 8

 UNIT - I

High-frequency Trading. Many banks, funds, and proprietary trading firms now have entire
portfolios which are managed purely by AI systems.
Hospitals and medicine: used as clinical decision support systems for medical diagnosis.
 Computer-aided interpretation of medical images help scan digital images, e.g. from
computed tomography, for typical appearances and to highlight conspicuous sections,
such as possible diseases. A typical application is the detection of a tumor.
 Heart sound analysis
 Companion robots for the care of the elderly
 Mining medical records to provide more useful information.
 Design treatment plans.
 Assist in repetitive jobs including medication management.
 Provide consultations.
 Drug creation[27]
 Using avatars in place of patients for clinical training[28]
 Predict the likelihood of death from surgical procedures
 Predict HIV progression
Media and E-commerce: Typical use case scenarios include:
 analysis of images using object recognition or face recognition techniques
 analysis of video for recognizing relevant scenes, objects or faces.
o facilitation of media search,
o creation of a set of descriptive keywords for a media item,
o media content policy monitoring (such as verifying the suitability of content
for a particular TV viewing time),
 speech to text for archival or other purposes, and the detection of logos,
 products or celebrity faces for the placement of relevant advertisements
 AI is also widely used in E-commerce Industry for applications like Visual search,
Visually similar recommendation, Chatbots, Automated product tagging
etc
Music: At Sony CSL Research Laboratory, their Flow Machines software has created pop
songs by learning music styles from a huge database of songs. By analyzing unique
combinations of styles and optimizing techniques, it can compose in any style.
News, publishing and writing: Artificial intelligence is used to turn structured data into
intelligent comments and recommendations in natural language. We can be able to write
financial reports, executive summaries, personalized sales or marketing documents and more
at a speed of thousands of pages per second and in multiple languages including English,
Spanish, French & German.
Online and telephone customer service: Artificial intelligence is implemented in automated
online assistants which uses natural language processing.

Dr. Ram Prasad Reddy Sadi Page 9

 UNIT - I

 Sensors: Artificial Intelligence has been combined with many sensor technologies,
such as Digital Spectrometry TM which enables many applications such as at home
water quality monitoring.
 Telecommunications maintenance: Many telecommunications companies make use
of heuristic search in the management of their workforces, for example BT Group has
deployed heuristic search in a scheduling application that provides the work schedules
of 20,000 engineers.
 Toys and games: AI has been applied to video games, for example video game bots,
which are designed to stand in as opponents where humans aren't available or desired.
 Transportation: Fuzzy Logic controllers have been developed for automatic
gearboxes in automobiles. For example, the 2006 Audi TT, feature the DSP
transmission which utilizes Fuzzy Logic.
AI trends in various sectors
 Healthcare:
o AI and ML technology has been particularly useful in the healthcare industry
because it generates massive amounts of data to train with and enables
algorithms to spot patterns faster than human analysts.
o Medecision developed an algorithm that detects 8 variables in diabetes
patients to determine if hospitalization is required.
o An app called BiliScreen utilizes a smartphone camera, ML tools, and
computer vision algorithms to detect increased levels of bilirubin in the sclera
(white portion) of a person‘s eye, which is used to screen people for pancreatic
cancer.
o This cancer has no telltale symptoms, hence it has one of the worst prognoses
of all cancers.
o NuMedii, a biopharma company, has developed a platform called Artificial
Intelligence for Drug Discovery (AIDD), which uses big data and AI to detect
the link between diseases and drugs at the systems level.
o GNS Healthcare uses ML algorithms to match patients with the most effective
treatments for them.
 Entertainment:
o A familiar application of AI in everyday life is seen with services like Netflix
or Amazon, wherein ML algorithms analyze the user‘s activity and compare it
with that of other users to determine which shows or products to recommend.
The algorithms are becoming intelligent with time—to the extent of
understanding that a user may want to buy a product as a gift and not for
him/her, or that different family members have different watching preferences.
 Finance:
o Financial services companies use AI-based natural language processing tools
to analyze brand sentiment from social media platforms and provide
actionable advice.
o Investment companies like Aidya and Nomura Securities use AI algorithms to
conduct trading autonomously and robo-traders to conduct high-frequency

Dr. Ram Prasad Reddy Sadi Page 10

 UNIT - I

trading for greater profits, respectively.

o Fintech firms like Kensho and ForwardLane use AI-powered B2C robo-
advisors to augment rebalancing decisions and portfolio management
performed by human analysts. Wealthfront uses AI algorithms to track
account activity and help financial advisors customize their advice.
o Chatbots, powered by natural language processing, can serve banking
customers quickly and efficiently by answering common queries and
providing information promptly.
o Fraud detection is an important application of AI in financial services. For
example, Mastercard uses Decision Intelligence technology to analyze various
data points to detect fraudulent transactions, improve real-time approval
accuracy, and reduce false declines.
 Data security:
o Cyber attacks are becoming a growing reality with the move to a digital world.
There are also concerns about AI programs themselves turning against
systems.
o Automatic exploit generation (AEG) is a bot that can determine whether a
software bug, which may cause security issues, is exploitable. If a
vulnerability is found, the bot automatically secures it. AEG systems help
develop automated signature generation algorithms that can predict the
likelihood of cyberattacks.
o PatternEx and MIT‘s Computer Science and Artificial Intelligence Laboratory
(CSAIL) have developed an AI platform called AI2 which claims to predict
cyber attacks better than existing systems. The platform uses Active
Contextual Modeling, a continuous feedback loop between a human analyst
and the AI system, to provide an attack detection rate that is better than ML-
only solutions by a factor of 10.
o Deep Instinct, an institutional intelligence company, says that malware code
varies between 2%-10% in every iteration and that its AI model is able to
handle the variations and accurately predict which files are malware.
 Manufacturing:
o Landing AI claims to have created machine-vision tools to find microscopic
defects in objects like circuit boards using an ML algorithm trained using tiny
volumes of sample images. In the future, self-driving robots may be created
which can move finished goods around without endangering anyone or
anything around.
o Robots in factories are often stationary but are still in danger of crashing into
objects around it. A new concept called collaborative robots or ―cobots,
enabled by AI, can take instructions from humans, including instructions that
the robot has not been previously exposed to, and work productively with
them.
o AI algorithms can influence the manufacturing supply chain by detecting the
patterns of demand for products across geographies, socioeconomic segments,
and time, and predicting market demand. This, in turn, will affect inventory,
raw material sourcing, financing decisions, human staffing, energy

Dr. Ram Prasad Reddy Sadi Page 11

 UNIT - I

consumption, and maintenance of equipment.

o AI tools help in predicting malfunctions and breakdown of equipment and
taking or recommending preemptive actions as well as tracking operating
conditions and performance of factory tooling.
 Automotive industry
o Tesla introduced TeslaBot, an intelligent virtual assistant integrated with Tesla
models S and X, allows users to interact with their car from their phone or
desktop.
o Uber AI Labs is working on developing self-driven cars with the help of the
best engineers and scientists. Uber has already tested a batch of self-driving
cars in 2016.
o Nvidia has partnered with Volkswagen to develop ―intelligent co-pilot
systems‖ in cars that will enable safety warnings, gesture control, and voice
and facial recognition.
o Ericsson predicts that 5G technology will improve vehicle-to-vehicle
communication wherein sensors will be implanted in airport runways,
railways, and roads.

Tic Tac Toe Game playing

The game Tic Tac Toe is also known as Noughts and Crosses or Xs and Os ,the player
needs to take turns marking the spaces in a 3x3 grid with their own marks, if 3 consecutive
marks (Horizontal, Vertical, Diagonal) are formed then the player who owns these moves get
won.
Assume , Player 1 - X Player 2 – O
Board's Data Structure:

The cells could be represent as Center square, Corner, Edge as like below:

Dr. Ram Prasad Reddy Sadi Page 12

 UNIT - I

General Problem Solving

To build a system to solve a particular problem, we need to do four things:
1. Define the problem precisely. This definition must include precise specifications of
what the initial situation(s) will be as well as what final situations constitute
acceptable solutions to the problem.
2. Analyse the problem. A few very important features can have an immense impact on
the appropriateness of various possible technique(s)for solving the problem.
3. Isolate and represent the task knowledge that is necessary to solve the problem.
4. Choose the best problem-solving technique(s) and apply it (them) to the particular
problem.
State-Space Search
 To build a program that could "Play chess," we would first have to specify the starting
position of the chess hoard, the rules that define the legal moves, and the board
positions that represent a win for one side or the other.
 The starting position can he described as an 8-by-8 array where each position contains
a symbol standing for the appropriate piece in the official chess opening position.
 We can define as our goal any board position in which the opponent does not have a
legal move and his or her king is under attack.
 The legal moves provide the way of getting from the initial state to a goal state. They
can he described easily as a set of rules consisting of two parts: a left side that serves
as a pattern to he matched against the current board position and a right side that
describes the change to be made to the board position in reflect the move.

 We have to write a very large number of rules since there have to be a separate rule
for each of the 10120 possible board positions. Using so many rules poses two
serious practical difficulties:
o No person could ever supply a complete set of such rules. It would take too
long and could certainly not be done without mistakes.
o No program could easily handle all those rules. Although hashing scheme
could be used to find the relevant rules for each move fairly quickly, just
storing that many rules poses serious difficulties.
 We should write the rules describing the legal moves in as general a way possible.

Dr. Ram Prasad Reddy Sadi Page 13

 UNIT - I

The convenient notation for describing patterns and substitutions is as follows:

 A problem can be defined in a ―State Space‖, where each state corresponds to a legal
position of the board.
o We can start at an initial state using a set of rules to move from one state to
another, and attempting to end up in one of a set of final states.
 The state space representation forms the basis of most of the Al methods. Its structure
corresponds to the structure of problem solving in two important ways:
o It allows formal definition of a problem as the need to convert some given
situation into some desired situation using a set of permissible operations.
o It permits us to define the process of solving a particular problem as a
combination of known techniques) each represented as a role defining a single
step in the space) and search, the general technique of exploring the space to
try to find some path from the current state to a goal state. Search is a very
important process in the solution of hard problems for which no more direct
techniques are available.
Water Jug Problem
Consider the following problem: A Water Jug Problem: You are given two jugs, a 4-gallon
one and a 3-gallon one, a pump which has unlimited water which you can use to fill the jug,
and the ground on which water may be poured. Neither jug has any measuring markings on
it. How can you get exactly 2 gallons of water in the 4-gallon jug?
State Representation and Initial State – we will represent a state of the problem as a tuple
(x, y) where x represents the amount of water in the 4-gallon jug and y represents the amount
of water in the 3- gallon jug. Note 0 ≤ x ≤ 4, and 0 ≤ y ≤ 3.
Our Initial state: (0,0) Goal state = (2,y) where 0 ≤ y ≤ 3.
To solve this we have to make some assumptions not mentioned in the problem. They are:
 We can fill a jug from the pump.
 We can pour water out of a jug to the ground.
 We can pour water from one jug to another.
 There is no measuring device available.
To solve the water jug problem, all we need is a control structure that loops through a simple
cycle in which some rule whose left side matches the current state is chosen. The appropriate
change to the state is made as described in the corresponding right side, and the resulting
state is checked to see ii ii corresponds to a goal state. As long as it does not, the cycle
continues. Clearly the speed with which the problem gets solved depends on the mechanism
that is used to select the next operation to be performed.

Dr. Ram Prasad Reddy Sadi Page 14

 UNIT - I

We must define a set of operators that will take us from one state to another:

The first step toward the design of a program to solve a problem must be the creation of a
formal and manipulable description of the problem itself. We should be able to write
programs that can themselves produce such formal descriptions from informal ones. This
process is called Operationalization.
In order to provide a formal description of a problem, we must do the following:
 Define a state space that contains all the possible configurations of the relevant

Dr. Ram Prasad Reddy Sadi Page 15

 UNIT - I

objects (and perhaps some impossible ones). It is, of course, possible to define this
space without explicitly enumerating all of the states it contains.
 Specify one or more states within that space that describes possible situations from
which the problem-solving process may start. These states are called the Initial states.
 Specify one or more states that would be acceptable as solutions to the problem.
These states are called goal states.
 Specify a set of rules that describe the actions (operators) available.
 The problem can then be solved by using the rules, in combination with an
appropriate Control Strategy, to move through the problem space until a path from an
initial state to a goal state is found. Thus the process of search is fundamental to the
problem-solving process.
Control Strategies
 It is important to decide which rule to apply next during the process of searching for a
solution to a problem. This question arises when more than one will have its left side
match the current state.
 The decisions made will have a crucial impact on how quickly a problem is finally
solved.
 The following are the requirements of a control strategy:
o The first requirement of a good control strategy is that it causes motion.
Consider again the water jug problem. Suppose we implemented the simple
control strategy of starting each time at the top of the list of rules and choosing
the first applicable one. If we did that, we would never solve the problem. We
would continue indefinitely filling the 4-gallon jug with water. Control
strategies that do not cause motion will never lead to a solution.
o The second requirement of a good control strategy is that it be systematic. Let
us consider a simple control strategy for the water jug problem. On each cycle,
choose at random from among the applicable rules. This strategy is better than
the first. It causes motion. It will lead to a solution eventually. Sometimes we
arrive at the same state several times during the process and to use many more
steps than are necessary. Because the control strategy is not systematic, we
may explore a particular useless sequence of operators several times before we
finally find a solution. The requirement that a control strategy be systematic
corresponds to the need for global motion (over the course of several steps) as
well as for local motion (over the course of a single step).
Breadth First Search
For each leaf node, generate all its successors by applying all the rules that are
appropriate. Continue this process until some rule produces a goal state. This process,
called Breadth-First search.
Algorithm: 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 do:
(a) Remove the first element from NODE-LIST and call it E. If

Dr. Ram Prasad Reddy Sadi Page 16

 UNIT - I

(b) For each way that each rule can match the state described in E do:
i. Apply the rule to generate a new state.
ii. If the new state is a goal state, quit and return this state.
iii. Otherwise, add the new state to the end of' NODE-LIST.
Advantages of Breadth-First Search:
 Breadth-first search will not get trapped exploring a blind alley.
 If there is a solution, then breadth-first search is guaranteed to find it. Furthermore, if
there are multiple solutions, then a minimal solution will be found. This is guaranteed
by the fact that longer paths are never explored until all shorter ones have already
been examined.
Disadvantages of Breadth-First Search:
 All of the tree that has so far been generated must be stored which requires more
memory.
 In breadth-first search, all parts of the tree must be examined to level n before any
nodes on level n + 1 can be examined. This is particularly significant if many
acceptable solutions exist.
Depth First Search
 We could pursue a single branch of the tree until it yields a solution or until a decision
to terminate the path is made.
 It makes sense to terminate a path if it reaches a dead-end, produces a previous state,
or becomes longer than some pre-specified "futility" limit.
 In such a case backtracking occurs. The most recently created state from which
alternative moves are available will be revisited and a new state will he created. This
form of backtracking is called Chronological Backtracking because the order in which
steps arc undone depends only on the temporal sequence in which the steps were
originally made.
 The search procedure we have just described is called Depth-First search.
Algorithm: 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 signalled:
a. Generate a successor, E, of the initial state. It there are no more successors,
signal failure.
b. Call Depth-First Search with E as the initial state.
c. If success is returned, signal success. Otherwise continue in this loop.

Dr. Ram Prasad Reddy Sadi Page 17

 UNIT - I

Advantages of Depth-First Search:

 Depth-first search requires less memory since only the nodes on the current path are
stored.
 By chance (or if care is taken in ordering the alternative successor states), depth first
search may find a solution without examining much of the search space at all. Depth-
first search can stop when one of solution is found.
Disadvantages of Depth-First Search:
 Depth- first searching may follow a single unfruitful path for a very long time.
 Depth-first search, may find a long path to a solution in one part of the tree, when a
shorter path exists in some other unexplored part of the tree.
Problem Characteristics
 A heuristic is a technique that improves the efficiency of a search process, possibly by
sacrificing claims such as completeness. Heuristics 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 may miss points of interest to particular individuals. But, on the
average, they improve the quality of the paths that are explored.
 Heuristic search is a very general method applicable to a large class of problems; it
encompasses a variety of specific techniques, each of which is particularly effective
for a small class of problems. In order to choose the most appropriate method (or
combination of methods for a particular problem, it is necessary to analyze the
problem along several key dimensions:
o Is the problem decomposable into a set of (nearly) independent smaller or
easier sub problems?
o Can solution steps be ignored or at least undone if they prove unwise?
o Is the problem's universe predictable?
o Is good solution to the problem obvious without comparison to all other
possible solutions?
o Is the desired solution a state of the world or a path to a state?
o Is a large amount of knowledge absolutely required to solve the problem, or is
knowledge important only to constrain the search?
o Can a computer that is simple given the problem return the solution, or will
the solution of the problem require interaction n between the computer and a
person?
1. Is the Problem Decomposab1e?
Suppose we want to solve the problem of computing the expression:

We can solve this problem by breaking it down into three smaller problems each of which we
can then solve by using a small collection of specific rules.
The figure shows the problem tree that will be generated by the process of problem
decomposition as it can be exploited by a simple recursive integration program that works as

Dr. Ram Prasad Reddy Sadi Page 18

 UNIT - I

follows:
At each step, it checks to see whether the problem it is working on is immediately solvable. If
so, then the answer is returned directly.
If the problem is not easily solvable, the integrator checks to see whether it can
decompose the problem into smaller problems. If it can, it creates those problems and calls
itself recursively on them. Using this technique of problem decomposition we can often
solve very large problems easily.

Example-Blocks World Problem: Assume that the following operators are available-

Applying the technique of problem decomposition to this simple blocks world example
would lead to a solution tree such as that shown below:

 In the figure, goals are underlined. States that have been achieved are not underlined.
The idea of this solution is to reduce the problem of getting B on C and A on B to two
separate problems.
 The first of these new problems, getting B on C. is simple, given the start state.
Simply put B on C. The second sub goal is not quite so simple. Since the only
operators we have allow us to pick up single blocks at a time, we have to clear off B
by removing C before we can pick up A and put it on B This can easily be done.
 However, if we now try to combine the two sub solutions into one solution, we will
fail. Regardless of which one we do first, we will not be able to do the second as we
had planned.
 In this problem, the two sub problems are not independent. They interact and those

Dr. Ram Prasad Reddy Sadi Page 19

 UNIT - I

interactions must be considered in order to arrive at a solution for the entire problem.
2. Can Solution Steps Be Ignored or Undone?
Theorem Proving: We proceed by first proving lemma that we think will be useful.
Eventually, we realize that the lemma is no help at all.
 Everything we need to prove the theorem is still true. Any rules that could have been
applied can still be applied.
 We can just proceed as we should have in the first place. All we have lost is the effort
that was spent exploring the blind alley.
The 8-Puzzle: The 8-puzzle is a square tray in which are placed eight square tiles. The
remaining ninth square is uncovered. Each tile has a number on it. A tile that is adjacent to
the blank space can he slid into that space. A game consists of a starting position and a
specified goal position. The goal is to transform the starting position into a goal position by
sliding the tiles around.

 In attempting to solve the 8-puzzle, we might make a stupid move. We might start by
sliding tile 5 into the empty space. Having done that, we cannot change our mind
and immediately slide tile 6 into the empty space since the empty space will
essentially have moved.
 But we can backtrack and undo the first move, sliding tile 5 back to where it was.
Then we can move tile 6. Mistakes can still be recovered from but not quite easily. An
additional step must be performed to undo each incorrect step
 The control mechanism for an 8.puzzle solver must keep track of the order in which
operations are performed so that the operations can be undone one at a time if
necessary.
Chess: Now consider again the problem of playing chess. Suppose a chess-playing program
makes a stupid move and realizes it a couple of moves later. It cannot simply play as though
it had never made the stupid move. Nor can it simply back up and start the game over from
that point. All it can do is to try to make the best of the current situation and go on from there.
The three problems—theorem proving, the 8-puzzle, and chess—
illustrate the differences between three important classes of problems:
 Ignorable(e.g... theorem proving), in which solution steps can be ignored
 Recoverable(e.g... 8-puzzle), in which solution steps can be undone.
 Irrecoverable(e.g... chess), in which solution steps cannot be undone
The recoverability of a problem plays an important role in
determining the complexity of the control structure necessary for the problem's solution.
 Ignorable problems can be solved using a simple control structure that never
backtracks. Such a control structure is easy to implement.
 Recoverable problems can be solved by a slightly more complicated control strategy

Dr. Ram Prasad Reddy Sadi Page 20

 UNIT - I

that does sometimes make mistakes. Backtracking will be necessary to recover from
such mistakes, so the control structure must be implemented using a push-down stack,
in which decisions are recorded in case they need to be undone later.
 Irrecoverable problems, on the other hand, will need to be solved by a system that
expends a great deal of effort making each decision since the decision must be final
3. Is the Universe Predictable?
 8-puzzle: Every time we make a move, we know exactly what will happen. This
means that it is possible to plan an entire sequence of moves and be confident that we
know what the resulting state will be. We can use planning to avoid having to undo
actual moves, although it still be necessary to backtrack past those moves one at a
time during the planning process. Thus a control structure that allows backtracking
will be necessary.
 Play Bridge: One of the decisions we will have to make is which card to play on the
first trick. What we would like to do is to plan the entire hand before making that first
play. But now it is not possible to do such planning with certainty since we
cannot know exactly where all the cards are what the other players will do on their
turns. The best we can do is to investigate several plans and use probabilities of the
various outcomes to choose a plan that has the highest estimated probability of
leading to a good score on the hand.
 Certain–outcome problems (e.g... 8-puzzle): The open-loop approach will work fine
since the result of an action can he predicted perfectly. Thus, planning can be used to
generate a sequence of operators that is guaranteed to lead to a solution.
 Uncertain–outcome problems (e.g... Bridge): Planning can at best generate a
sequence of operators that has a good probability of leading to a solution. To solve
such problems, we need to allow for a process of plan revision to take place as the
plan is carried out and the necessary feedback is provided. In addition to providing
no guarantee of art actual solution, planning for uncertain -outcome problems has
the drawback that it is often very expensive since the number of solution paths
that need to be explored increases exponentially with the number of points at which
the outcome cannot be predicted.
4. Is a Good Solution Absolute or Relative?
Simple facts problem: Consider the problem of answering questions based on a database of
simple facts, such as the following:
1. Marcus was a man.
2. Marcus was a Pompeian.
3. Marcus was born in 40 A.D.
4. All men are mortal.
5. All Pompeians died when the volcano erupted in 79 A.D.
6. No mortal lives longer than 150 years.
7. 11 is now 1991 A.D.
 Suppose we ask the question 'Is Marcus alive?'. By representing each of these facts
in a formal language such as predicate logic, and then using formal inference
methods we can fairly easily derive an answer to the question. Since all we are

Dr. Ram Prasad Reddy Sadi Page 21

 UNIT - I

interested in is the answer to the que7sion, it does not matter which path we follow. If
we do follow one path successfully to the answer, there is no reason to go back and
see it some other path might also lead to a solution.

Travelling salesman problem: Our goal is to find the shortest route that visits each city
exactly once. Suppose the cities to be visited and the distances between them are as shown:

One place the salesman could start is Boston. In that case, one path that might be followed is
shown, which is 8850 miles long. But is this the solution to the problem? The answer is that
we cannot be sure unless we also try all other paths to make sure that none of them is shorter.
In this case, the first path is definitely not the solution to the salesman's problem.

 Best-path problems: These are, in general, computationally harder than Any-path

Dr. Ram Prasad Reddy Sadi Page 22

 UNIT - I

problems. No heuristic that could possibly miss the best solution can be used.
 Any-path problems: can often be solved in a reasonable amount of time by using
heuristics that suggest good paths to explore. If the heuristics are not perfect, the
search for a solution may not be as direct as possible. So a much more exhaustive
search will be performed.
5. Is the Solution a State or a Path?
Consistent interpretation for the sentence (NLU): There are several components of this
sentence, each of which, in isolation, may have more than one interpretation.
―The Bank president ate a dish of pasta salad with the fork‖
Some of the sources of ambiguity in this sentence are the following:
 The word "bank" may refer either to a financial institution or to a side of a river. But
only one of these may have a president.
 The word "dish" is the object of the verb "eat." It is possible that a dish was eaten.
But it is more likely that the pasta salad in the dish was eaten.
 Pasta salad is a salad containing pasta. But there are other ways meanings can be
formed from pair of nouns. For example, dog food does not normally contain dog.
Some search may be required to find a complete interpretation for the sentence. But to solve
the problem of finding the interpretation we need to produce only the interpretation itself. No
record of the processing by which the interpretation was found is necessary.
Water Jug Problem: It is not sufficient to report that we have solved the problem and that
the final state (2, 0). For this kind of problem, what we really must report is not the final state
but the path that we found to that state. Thus a statement of a solution to this problem must be
a sequence of operations called a ―plan‖ that produces the final state.
The difference between these problems is:
 Problems whose solution is a state.
 Problems whose solution is a path to a state.
In water jug problem, we must re-describe the states so that each state represents a partial
path to a solution rather than just a single state of the world.
6. What Is the Role of Knowledge?
 Playing chess: Suppose you had unlimited computing power available.The
knowledge that would be required by a perfect program is very little—just the rules
for determining legal moves and some simple control mechanism that implements a
search procedure.
 Additional knowledge about such things as good strategy, and tactics could of course
help considerably to constrain the search and speed up the execution of the program.
 Scanning daily newspapers: to decide which are supporting the Democrats and which
are supporting the Republicans in some upcoming election. Again assuming unlimited
computing power, how much knowledge would be required by a computer trying to
solve this problem? It would have to know such things as:
o The names of the candidates in each party.
o The fact that if the major thing you want to see done is have taxes lowered,

Dr. Ram Prasad Reddy Sadi Page 23

 UNIT - I

you are probably supporting the Republicans.

o The fact that it the major thing you want to see done is improved education for
minority students, you are probably supporting the Democrats.
o The fact that if you are opposed to big government you are probably
supporting the Republicans.
 These two problems, chess and newspaper story understanding, illustrate the
difference between problems for which a lot of knowledge is important only to
constrain the search for a solution and those for which a lot of knowledge is required
even to be able to recognize a solution.
7. Does the Task Require Interaction with a Person?
 Sometimes it is useful to program computers to solve problems in ways that the
majority of people would not be able to understand. This is fine if the level of the
interaction between the computer and its human users is program-in solution-out.
 But increasingly we are building programs that require intermediate interaction with
people, both to provide additional input to the program and to provide additional
reassurance to the user.
We must distinguish between two types of problems:
Solitary: in which the computer is given a problem description and produces an answer with
no intermediate communication and with no demand for an explanation of the reasoning
process
Conversational: in which there is intermediate communication between a
person and the computer, either to provide additional assistance to the computer or to provide
additional information to the user, or both.
Generic control strategy-Classification: The task here is to examine an input and then
decide which of a set of known classes the input is an instance of. Most diagnostic tasks,
including medical diagnosis as well as diagnosis of faults in mechanical devices are examples
of classification.
Propose and Refine: Many design and planning problems can be attacked with this strategy.
Heuristic Search Techniques
 A framework for describing search methods is provided and several general-purpose
search techniques are discussed.
 There are many varieties of heuristic search. They can be described
independently of any particular task or problem domain. But when applied to
particular problems, their efficacy is highly dependent on the way they exploit
domain-specific knowledge
 Over last three decades of AI research, these techniques continue to provide the
framework into which domain-specific knowledge can be placed, either by hand or as
a result of automatic learning. Thus they continue to form the core of most Al
systems.
Best-First Search
Best-first search, is a way of combining the advantages of both depth- first and breadth-first
search into a single method.

Dr. Ram Prasad Reddy Sadi Page 24

 UNIT - I

Depth-first search is good because it allows a solution to be found without all competing
branches having to be expanded. Breadth-first search is good because it does not get trapped
on dead-end paths.
One way of combining the two is to follow a single path at a time, but switch paths whenever
some competing path looks more promising than the current one does.
 At each step of the best-first search process, we select the most promising of the
nodes we have generated so far. This is done by applying an appropriate heuristic
function to each of them, We then expand the chosen node by using the rules to
generate its successors.
 If one of them is a solution, we can quit. If not, all those new nodes are added to the
set of nodes generated so far. Again the most promising node is selected and the
process continues. A bit of depth first searching occurs as the most promising branch
is explored.
 But eventually, it a solution is not found, that branch will start to look less promising
than one of the top-level branches that had been ignored. At that point, the now more
promising, previously ignored branch will be explored. But the old branch is not
forgotten, Its last node remains in the set of generated but unexpanded nodes. The
search can return to it whenever all the others get bad enough, that it is again the most
promising path.
 Initially, there is only one node, so it will be expanded. Doing so generates three new
nodes. The heuristic function, is an estimate of the cost of getting to a solution
from a given node, is applied to each of these new nodes.
 Since node D is the most promising, it is expanded next, producing two successor
nodes, E and F. Now the heuristic function is applied to them.
 Now another path that going through node B looks more promising, so it is pursued,
generating nodes G and H. But again when these new nodes are evaluated they look
less promising than another path, so attention is returned to the path through D to E. E
is then expanded, yielding nodes I and J.
 At the next step, J will be expanded, since it is the most promising. This process can
continue until a solution is found.

Dr. Ram Prasad Reddy Sadi Page 25

 UNIT - I

 In best-first search, one move is selected, but the others are kept around so that they
can be revisited later if the selected path becomes less promising.
 Further, the best available state is selected in best first search, even it that state has a
value that is lower than the value of the state that was just explored.
 In a best-first search of a tree, it is sometimes important to search a graph instead so
that duplicate paths will not be pursued.
 An algorithm to do this will operate by searching a directed graph in which each node
represents a point in the problem space. Each node will contain, in addition to a
description of the problem state it represents, an indication of how promising it is; a
parent link that points back to the best node from which it came, and a list of the
nodes that were generated from it.
 The parent link will make it possible to recover the path to the goal once the goal is
found. The list of successors will make it possible, if a better path is found to an
already existing node, to propagate the improvement down to its successors.
 We will call a graph of this sort an OR graph, since each of its branches represents an
alternative problem-solving path.
 To implement such a graph-search procedure, we will need to use two lists of nodes:
o OPEN—nodes that have been generated and have had the heuristic function
applied to them but which have not yet been examined (i.e.. had their
successors generated) OPEN is actually a priority queue in which the
elements with the highest priority are those with the most promising value
of the heuristic function.
o CLOSED— -nodes that have already been examined. We need to keep
these nodes in memory if we want to search a graph rather than a tree, since
whenever a new node is generated; we need to check whether it has been
generated before.
 We will also need a heuristic function that estimates the merits of each node we
generate. The function f1 that gives the true evaluation of the node.
 We define this function as the sum of two components: g and h1.
 The function g is a measure of the cost of getting from the initial state to the current
node.
 The function h1 is an estimate of the additional cost of getting from the current node
to a goal state.
 The combined function f1 represents an estimate of the cost of getting from the
initial state to a goal state along the path that generated the current node. If more than
one path is generated the node, then the algorithm will record the best one.
This process can be summarized as follows:
Algorithm: Best-First Search
1. Start with OPEN containing just the initial state.
2. Until a goal is found or there are no nodes left on OPEN do:
a. Pick the best node on OPEN.
b. Generate its successors.

Dr. Ram Prasad Reddy Sadi Page 26

 UNIT - I

c. For each successor do:

i. If it has not been generated before, evaluate it, add it to OPEN, and
record its parent.
ii. If it has been generated before, change the parent if this new path is,
better than the previous one. In that case, update the cost of getting to
this node and to any successors that this node may already have.
The best first search algorithm is a simplification of an algorithm called A*.
This algorithm uses the same f1, g, and h1 functions, as well as the lists OPEN and CLOSED.
Iterative Deepening:
 A number of ideas for searching two-player game trees have led to new algorithm for
single-agent heuristic search. One such idea is ―iterative deepening‖ originally used in
CHESS.
 Rather than searching to a fixed depth in the game tree, CHESS first searched only a
single ply, applying its static evaluation function to the result of each of its possible
moves.
 It then initiated a new minimax search, to a depth of two ply. This was followed by a
three-ply search, then a four-ply search etc.
 The name "iterative deepening" derives from the fact that on each iteration, the tree is
searched one level deeper.
 Since it is impossible to know in advance how long a fixed-depth tree search will
take, a program may find itself running out of time. With iterative deepening, the
current search can be aborted at any time and the best move found by the previous
iteration can be played.
 Iterative deepening can also be used in improve the performance of the A* search
algorithm.
Algorithm: Iterative-Deepening-A*
 Set THRESHOLD = the heuristic evaluation of the start state.
 Conduct a depth-first search, pruning any branch when its total cost function (g +
h1) exceeds THRFSHOLD. If a solution path is found during the search, return it.
 Otherwise, increment THRESHOLD by the minimum amount it was exceeded during
the previous step, and then go to Step 2.
Iterative-Deepening-A* (IDA*) is guaranteed to find an optimal solution provided that h1 is
an admissible heuristic.
Constraint Satisfaction
 Many problems in Al can be viewed as problems of Constraint Satisfaction in which
goal is to discover some problem state that satisfies a given set of constraints.
 Examples of this sort of problem include crypt arithmetic puzzles.
 Design tasks can also be viewed as Constraint Satisfaction problems in which a
design must be created within fixed limit, on time, cost, and materials.
 By viewing a problem as one of constraint satisfaction, its often possible to reduce
substantially the amount of search that, is required as compared with a method that

Dr. Ram Prasad Reddy Sadi Page 27

 UNIT - I

attempts to form partial solutions.

 A constraint satisfaction approach to solving this problem avoids making guesses on
particular assignments of numbers to letters. Instead, the initial set of constraints,
which says that each number may correspond to only one letter and that the sums of
the digits must be as they are given in the problem, is first augmented to include
restrictions that can be inferred from the rules of arithmetic.
 Then, although guessing may still be required, the number of allowable guesses is
reduced.
 Constraint satisfaction is a search procedure that operates in a space of Constraint
sets.
 The initial state contains the constraints that are originally given in the problem
description. A goal state is any state that has been constrained - enough." where
"enough' must be defined for cacti problem.
 Constraint satisfaction is a two-step process. First, constraints are discovered and
propagated as far as possible throughout the system. Then, if there is still not a
solution, search begins. A guess about something is made and added as a new
constraint. Propagation can then occur with this new constraint, and so forth.
 The first step, propagation, arises from the fact that there are usually dependencies
among the constraints. These dependencies occur because many constraints involve
more than one object and many objects participate in more than one constraint.
 So, for example, assume we start with one constraint: N = E + I. Then, if we added
the constraint N = 3, we could propagate that to get a stronger constraint on E, namely
that E = 2.
 Constraint propagation terminates for one of two reasons.
o First, a contradiction may be detected. If this happens, then there is no solution
consistent with all the known constraints. If the contradiction involves only
those constraints that were given as part of the problem specification (as
opposed to ones that were guessed during problem solving), then no solution
exists.
o The second possible reason for termination is that the propagation has run out
of steam and there are no further changes that can be made on the basis of
current knowledge. If this happens and a solution has not yet been adequately
specified, then search is necessary to get the process moving again.
o At this point, the second step begins. Some hypothesis about a way to
strengthen the constraints must be made. ln case of the crypt arithmetic
problem, for example this usually means guessing a particular value for some
letter. Once this has been done, constraint propagation can begin again from
this new state. If a solution is found, it can be reported. If still more guesses
are required, they can be made. If a contradiction is detected, then
backtracking can he used to try a different guess and proceed with it.
1. Propagate available constraints. To do this, first set OPEN to the set of all objects that
must have values assigned to them in a complete solution. Then do until an
inconsistency is detected or until OPEN is empty:
a. Select an object OB from OPEN. Strengthen as much as possible the set of

Dr. Ram Prasad Reddy Sadi Page 28

 UNIT - I

constraints that apply to OB.

b. If this set is different from the set that was assigned the last time OB was
examined or if this is the first time OB has been examined, then add to 0PEN
all objects that share any constraints with OB.
c. Remove OB from OPEN.
2. If the union of the Constraints discovered above defines a solution, then quit and
report the solution.
3. If the union of the constraints discovered above defines a contradiction then return
failure.
4. If neither of the above occurs, then it is necessary to make a guess at something in
order to proceed. To do this, loop until a solution is found or all possible solutions
have been eliminated:
a. Select an object whose value is not yet determined and select a way of
strengthening the constraints on that object.
b. Recursively invoke constraint satisfaction with the current set of constraints
augmented by the strengthening constraint just selected.

 The goal slate is problem state in which all letters have been assigned a digit in such a
way that all the initial constraints are satisfied.
 The solution process proceeds in cycles. At each cycle, two significant things are
done :
o Constraints are propagated by using rules that correspond to the properties of
arithmetic.
o A value is guessed for some letter whose value is not yet determined.
 In the first step, it does not usually matter a great deal what order the propagation is
done in, since all available propagations will be performed before the step ends.
 In the second step, the order in which guesses are tried may have a substantial impact
on the degree of search that is necessary.
 A few useful heuristics can help to select the best guess to try first.
 For example, if there is a letter that has only two possible values and other with
possible values, there is a better chance of guessing right on the first than on the
second.
 Another useful heuristic is that if there is a letter that participates in many constraints
then it is a good idea to prefer it to a letter that participates in a few. A guess on such

Dr. Ram Prasad Reddy Sadi Page 29

 UNIT - I

a highly constrained letter will usually lead quickly either to a contradiction (if it‘s
wrong) or to the generation of many additional constraints (if it is right). A guess on a
less constrained letter, on the other hand, provides less information.
 Let Cl, C2, C3, and C4 indicate the carry bits out of the columns, numbering from the
right. Initially, rules for propagating constraints generate the following additional
constraints:
o M 1, since two single-digit numbers plus a carry cannot total more than 19;
S=8 or 9, since S+M+C3>9 (to generate the carry) and M=1, S+l+C3>9. So S
+ C3 > 8 and C3 is at most 1.
o O=0, since S + M(l)+C3(<= 1) must be at least 10 to generate a carry and it
can be at most 11. But M is already 1. So O must be 0.
o N = E or E+1, depending on the value of C2. But N cannot have the same
value as E. So, N=E+l and C2 is 1.
o In order for C2 to be1, the sum of N+ R+CI must be greater than 9, so N+ R
must be greater than 18.
o N + R cannot be greater than 18, even with a carry in, so E cannot be 9.
 At this point, let us assume that no more constraints can be generated. Then, to make
progress from here, we must guess. Suppose E is assigned the value 2. (We chose to
guess a value for E because it occurs three times and thus interacts highly with the
other letters.) Now the next cycle begins. The constraint propagator now observes
that:
o N =3, since N = E+ 1.
o R= 8 o 9, since R + N (3) + C1 (1 or 0) = 2 or 12. But since N is already 3, the
sum of these n negative numbers cannot be less than 3. Thus R + 3 + (0
or 1)= 12 and R = 8 or 9.
o 2 + D= Y or 2 + D = 10 + Y, from the sum in the rightmost column.

Dr. Ram Prasad Reddy Sadi Page 30