AI PDF

Introduction
Chapter-1
Outline
What is AI?
Foundation
A brief history
The state of the art
AI – Why so Important?
Homo sapiens—man the wise!

AI – Why so Important?...
• For thousands of years, we have tried to understand how we think; that is,
how a mere handful of matter can perceive, understand, predict, and
manipulate a world far larger and more complicated than itself.
• The field of artificial intelligence, or AI, goes further still: it attempts not just
to understand but also to build intelligent entities.
• AI is one of the newest fields in science and engineering. Work .started in
earnest soon after World War II, and the name itself was coined in 1956
• It is reasonably felt that all the good ideas have already been taken by Galileo,
Newton, Einstein, and the rest. AI, on the other hand, still has openings for
several full-time Einsteins and Edisons.
AI – Why so Important?...
• AI currently encompasses a huge variety of subfields, ranging from the

general (learning and perception) to the specific, such as playing chess,
proving mathematical theorems, writing poetry, driving a car on a crowded
street, and diagnosing diseases.
• AI is relevant to any intellectual task; it is truly a universal field.

Introduction – Four Approaches to AI?
• Systems that act like humans
• Systems that think like humans
• Systems that think rationally
• Systems that act rationally
Systems that think like Systems that think rationally

humans
Systems that act like humans Systems that act rationally

Introduction - What is AI ?(Contd…)
Acting humanly: The Turing Test
• Alan Turing (1950) : Wrote this paper “Computing machinery and intelligence"
• “Can machines think?“ , “Can machines behave intelligently?"
• Operational test for intelligent behavior: the Imitation Game
• Predicted that by 2000, a machine might have a 30% chance of

fooling a lay person for 5 minutes.
• Anticipated all major arguments against AI in following 50 years.

• Suggested major components of AI: knowledge, reasoning, language understanding,
learning.
------------------------------------------------------------------------------------------------------------
Alan Turing’s first paper on AI
"Computing Machinery and Intelligence" is a seminal paper written

by Alan Turing on the topic of artificial intelligence. The paper,
published in 1950 in Mind, was the first to introduce his concept of
what is now known as the Turing test to the general public.
Six Capabilities of a Computer to pass Total
Turing Test
1. Natural Language Processing: To enable it to communicate successfully in English;
2. Knowledge Representation: To store what it knows or hears;
3. Automated Reasoning: To use the stored information to answer questions and to draw new
conclusions;
4. Machine Learning: To adapt to new circumstances and to detect and extrapolate patterns;
5. Computer Vision: To perceive objects;
6. Robotics: To manipulate objects and move about;

Thinking humanly: Cognitive modeling
• 1960’s "cognitive revolution": information-processing

psychology
• Scientific theories of internal activities of the brain
• Predicting and testing behavior of human subjects
• Direct identification from neurological data
• Both approaches (roughly, Cognitive Science and
Cognitive Neuroscience) are now distinct from AI
Thinking humanly: Cognitive modeling…
• A given program thinks like a human → Determine how humans think → Get inside the actual workings of human
minds
• Three ways to do this:

I) Through introspection—trying to catch our own thoughts as they go by;
II) Through psychological experiments—observing a person in action;
III) Through brain imaging—observing the brain in action.
• 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 behavior matches corresponding human behavior, that is evidence that some of
the program’s mechanisms could also be operating in humans.
• Example: Allen Newell and Herbert Simon, who developed GPS, the “General Problem Solver” (Newell and Simon,
1961), were not content merely to have their program solve problems correctly. They were more concerned with
comparing the trace of its reasoning steps to traces of human subjects solving the same problems.
• The interdisciplinary field of cognitive science brings together computer models from AI and experimental
techniques from psychology to construct precise and testable theories of the human mind.
Cognitive Revolution
• The cognitive revolution is the name for an
intellectual movement in the 1950s that began what
are known collectively as the cognitive sciences. It
began in the modern context of greater
interdisciplinary communication and research. The
relevant areas of interchange were the combination of
psychology, anthropology, and linguistics .
• A key idea in cognitive psychology was that by

studying and developing successful functions in
artificial intelligence and computer science, it
becomes possible to make testable inferences about
human mental processes.
Thinking rationally: “Laws of thought"
• Aristotle: what are correct arguments/thought processes?
• Several Greek schools developed various forms of logic:

notation and rules of derivation for thoughts; may or may
not have proceeded to the idea of mechanization
• Direct line through mathematics and philosophy to modern
AI
• Problems:
1. Not all intelligent behavior is mediated by logical deliberation
2. What is the purpose of thinking? What thoughts should I have?

Acting rationally: Rational agent
• Rational behavior: doing the right thing
• The right thing: that which is expected to maximize goal

achievement, given the available information
• Doesn't necessarily involve thinking – e.g., blinking reflex –

but thinking should be in the service of rational action
AI Foundation
• Philosophy: Logic, methods of reasoning, mind as physical

system foundations of learning, language,
rationality
• Mathematics: Formal representation and proof algorithms,
computation, (un)decidability, (in)tractability,
probability
• Economics: Utility, decision theory
• Neuroscience: Physical substrate for mental activity
• Psychology: Phenomena of perception and motor control,
experimental techniques
• Computer Building fast computers
Engineering:
• Control theory: Design systems that maximize an objective
function over time
• Linguistics: Knowledge representation, grammar
Abridged history of AI
• 1943 McCulloch & Pitts: Boolean circuit model of brain
• 1950 Turing's "Computing Machinery and Intelligence"
• 1956 Dartmouth meeting: "Artificial Intelligence" adopted
• 1952—69 Look, Ma, no hands!
• 1950s Early AI programs, including Samuel's checkers
program, Newell & Simon's Logic Theorist,
Gelernter's Geometry Engine
• 1965 Robinson's complete algorithm for logical reasoning
• 1966—73 AI discovers computational complexity
Neural network research almost disappears
• 1969—79 Early development of knowledge-based systems
• 1980-- AI becomes an industry
• 1986-- Neural networks return to popularity
• 1987-- AI becomes a science
• 1995-- The emergence of intelligent agents
State of the art
• Deep Blue defeated the reigning world chess champion Garry Kasparov in 1997
• Proved a mathematical conjecture (Robbins conjecture) unsolved for decades
• No hands across America (driving autonomously 98% of the time from Pittsburgh to
San Diego)
• During the 1991 Gulf War, US forces deployed an AI logistics planning and
scheduling program that involved up to 50,000 vehicles, cargo, and people
• NASA's on-board autonomous planning program controlled the scheduling of
operations for a spacecraft
• Proverb solves crossword puzzles better than most humans
State of the art
• AI recently took the spotlight when IBM's Watson
supercomputer routed human competitors on the game
show Jeopardy.
• But when it comes to AI, Watson is just the tip of the

virtual frontal lobe. Labs across the United States and
around the world are exploring much more than just
ways to outwit Ken Jennings. Scientists are teaching
robots to explore extraterrestrial planets and serve you
coffee, cars are learning to drive themselves,
computers are trying to assist doctors with medical
diagnoses, and video game soldiers are training to do
battle in a virtual theatre of war.
Applications of AI
• AI has been used in a wide range of fields including medical

diagnosis, stock trading, robot control, law, scientific discovery
and toys. Many thousands of AI applications are deeply
embedded in the infrastructure of every industry. It includes :
Applications of AI
• 1 Computer science
• AI researchers have created many tools to solve the most difficult
problems in computer science.
• 2 Finance
• Banks use artificial intelligence systems to organize operations, invest
in stocks, and manage properties. In August 2001, robots beat humans
in a simulated financial trading competition.[4]
• Financial institutions have long used artificial neural network systems
to detect charges or claims outside of the norm, flagging these for
human investigation.
• Creative Virtual has deployed artificial intelligence customer support
systems, or automated online assistants, at E*TRADE, HSBC, Intuit
and Lloyds Banking Group, to assist financial services customers with
services such as checking an account balance, signing up for a new
credit card or retrieving a forgotten password.
Applications of AI
• 3 Hospitals and medicine
• A medical clinic can use artificial intelligence systems to
organize bed schedules, make a staff rotation, and provide
medical information.
• Artificial neural networks are used as clinical decision

support systems for medical diagnosis, such as in Concept
Processing technology in EMR software.
• Other tasks in medicine that can potentially be performed

by artificial intelligence include:
• Computer-aided interpretation of medical images. Such systems help
scan digital images.
Applications of AI
• 4 Heavy industry
• Robots have become common in many industries. They are often given
jobs that are considered dangerous to humans. Robots have proven
effective in jobs that are very repetitive which may lead to mistakes or
accidents due to a lapse in concentration and other jobs which humans
may find degrading. Japan is the leader in using and producing robots
in the world. In 1999, 1,700,000 robots were in use worldwide.
Applications of AI
• 5 Online and telephone customer service
• Artificial intelligence is implemented in automated online assistants
that can be seen as avatars on web pages . It can avail for enterprises to
reduce their operating and training cost . A major underlying
technology to such systems is natural language processing.
• Similar techniques may be used in answering machines of call centres ,

such as speech recognition software to allow computers to handle first
level of customer support, text mining and natural language processing
to allow better customer handling, agent training by automatic mining
of best practices from past interactions, support automation and many
other technologies to improve agent productivity and customer
satisfaction.
Applications of AI
• 6 Transportation
• Fuzzy logic controllers have been developed for automatic gearboxes in
automobiles (the 2006 Audi TT, VW Toureg and VW Caravell feature
the DSP transmission which utilizes Fuzzy Logic, a number of Škoda
variants (Škoda Fabia) also currently include a Fuzzy Logic based
controller).
• 7 Telecommunications
• 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.
Applications
• 8 Toys and games of AI
• The 1990s saw some of the first attempts to mass-produce domestically aimed types of
basic Artificial Intelligence for education, or leisure. This prospered greatly with the
Digital Revolution, and helped introduce people, especially children, to a life of dealing
with various types of Artificial Intelligence, specifically in the form of Tamagotchis and
Giga Pets, the Internet (example: basic search engine interfaces are one simple form), and
the first widely released robot, Furby. A mere year later an improved type of domestic
robot was released in the form of Aibo, a robotic dog with intelligent features and
autonomy. AI has also been applied to video games.
• 9 Music
• The evolution of music has always been affected by technology. With
AI, scientists are trying to make the computer emulate the activities of
the skillful musician. Composition, performance, music theory, sound
processing are some of the major areas on which research in Music and
Artificial Intelligence are focusing.
Applications of AI
• 10 Aviation
• The 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.
• The use of artificial intelligence in simulators is proving to be very
useful for the AOD. Airplane simulators are using artificial intelligence
in order to process the data taken from simulated flights. Other than
simulated flying, there is also simulated aircraft warfare. The
computers are able to come up with the best success scenarios in these
situations. The computers can also create strategies based on the
placement, size, speed, and strength of the forces and counter forces.
Pilots may be given assistance in the air during combat by computers.
Applications of AI
• 10 Aviation
• The system used by the AOD in order to measure performance was the
Interactive Fault Diagnosis and Isolation System, or IFDIS. It is a rule
based expert system put together by collecting information from TF-30
documents and the expert advice from mechanics that work on the
TF-30. This system was designed to be used to for the development of
the TF-30 for the RAAF F-111C. The performance system was also
used to replace specialized workers. The system allowed the regular
workers to communicate with the system and avoid mistakes,
miscalculations, or having to speak to one of the specialized workers.
• The AOD also uses artificial intelligence in speech recognition

software.
• The Artificial Intelligence supported Design of Aircraft [1], or AIDA,

is used to help designers in the process of creating conceptual designs
of aircraft.
Applications of AI
• 11 News and publishing

• The company Narrative Science makes computer generated news and
reports commercially available, including summarizing team sporting
events based on statistical data from the game. It also creates financial
reports and real estate analyses.
Intelligent Agents
Chapter-2
Outline
• Agents and environments

• Rationality
• PEAS (Performance measure, Environment, Actuators, Sensors)
• Environment types
• Agent types
Agents
• An agent is anything that can be viewed as perceiving its

environment through sensors and acting upon that
environment through actuators.
• Human agent: eyes, ears, and other organs for sensors;

hands, legs, mouth, and other body parts for actuators.
• Robotic agent: cameras and infrared range finders for

sensors; various motors for actuators.
Agents
• Software agent ( SoftBot : software robot ) :-

receives keystrokes, file contents, network packets etc as
sensory input.
acts on the environment by displaying on the screen,
writing files, sending message packets.
Agent perception and action
• Percept :- refers to an agents perceptual input at any given

instant.
• Percept sequence :- refers to the complete history of what an

agent has perceived so far.
• Action:- an agent’s choice of action at any given instant can

depend on the entire percept sequence observed till that time.
• Agent function:- an agent’s behavior is described by the agent

function that maps any percept sequence to an action.
Agent
Agents and environments
• The agent function maps from percept histories to actions: [f: P* A]

• The agent function is implemented by an agent program.
• The agent program runs on the physical architecture to produce f
• agent = architecture + program
Vacuum-cleaner world
• Percepts: location and contents , e.g.,[ A, Dirty]

• Actions: Left, Right, Suck, NoOp
Percept sequence : Action :
[A, Clean] right
[A, Dirty] suck
[B, Clean] left
[B, dirty] suck
[A, Dirty],[A, Clean] right
……………
Rational agents
• An agent should strive to "do the right thing", based on what it

can perceive and the actions it can perform. The right action is
the one that will cause the agent to be most successful.
• Performance measure: An objective criterion for success of an
agent's behavior.
• E.g., performance measure of a vacuum-cleaner agent could be
the amount of dirt cleaned up, the amount of time taken, the
amount of electricity consumed, the amount of noise generated,
etc .
RATIONALITY
Rationality at any given time depends on :
• Agent’s prior knowledge of the environment.

• Actions that the agent can perform.
• Agent’s percept sequence till that moment.
• The performance measure that defines the criterion of success.
Rational agents
• Rational Agent: For each possible percept sequence, a rational agent should
select an action that is expected to maximize its performance measure, given
the evidence provided by the percept sequence and whatever built-in
knowledge the agent has.
Requirements for a Rational agent
• Rationality ; which is distinct from omniscience (all-knowing with infinite

knowledge)
• Information gathering capability ; Agents can perform actions in order to
modify future percepts so as to obtain useful information.
Learning ability.
• Ability to adapt.
• An agent is autonomous if its behavior is determined by its own experience
(with ability to learn and adapt)
Building intelligent agents
• An agent is completely specified by the agent function which

maps percept sequences to action.
• An agent has some internal data structures that is updated as

and when new percepts arrive.
• The data structures are operated on by the agent’s decision

making procedures to generate an action choice, which is then
passed to the architecture to get executed.
Building intelligent agents
• An agent consists of an architecture plus a program that runs on

that architecture.
• In designing intelligent systems , there are 4 main factors to

consider:-
• Percepts:- the inputs to our system.
• Actions:- the outputs of our system.
• Goals:- what the agent is expected to achieve.
• Environment:- what the agent is interacting with.
PEAS
• Task environments are problems to which rational agents are

the solutions. The task environment is specified by PEAS.
• PEAS stands for :- Performance measure, Environment,
Actuators, Sensors.
• PEAS specifies the settings for an intelligent agent design.
PEAS
• Consider, e.g., the task of designing an automated taxi

driver:
• Performance measure: Safe, fast, legal, comfortable trip,

maximize profits.
• Environment: Roads, other traffic, pedestrians, customers.
• Actuators: Steering wheel, accelerator, brake, signal, horn.
• Sensors: Cameras, sonar, speedometer, GPS, odometer, engine
sensors, keyboard.
PEAS
• Agent: Medical diagnosis system

• Performance measure: Healthy patient, minimize costs, lawsuits
• Environment: Patient, hospital, staff
• Actuators: Screen display (questions, tests, diagnoses, treatments,
referrals)
• Sensors: Keyboard (entry of symptoms, findings, patient's answers)

PEAS
• Agent: Part-picking robot

• Performance measure: Percentage of parts in correct bins
• Environment: Conveyor belt with parts, bins
• Actuators: Jointed arm and hand
• Sensors: Camera, joint angle sensors
PEAS
• Agent: Interactive English tutor

• Performance measure: Maximize student's score on test
• Environment: Set of students
• Actuators: Screen display (exercises, suggestions, corrections)
• Sensors: Keyboard
PEAS
For each of the following activities, give a PEAS description of the task
environment
• Playing soccer.
• Exploring the subsurface oceans of Titan.
• Shopping for used AI books on the Internet.
• Playing a tennis match.
• Practicing tennis against a wall.
• Performing a high jump.
• Knitting a sweater.
• Bidding on an item at an auction.
Environment types
1. Fully observable vs. Partially observable

Fully observable
If an agent’s sensors give it access to the complete state of the environment at each point in
time then the environment is effectively fully observable
Examples:
Cross Word puzzle, Chess with a clock, Image Analysis
Partially observable
An environment might be Partially observable because of noisy and inaccurate sensors or
because parts of the state are simply missing from the sensor data.
Example:
Only a local dirt sensor of the vacuum cleaner without a location detection sensor
cannot tell whether other squares are clean or not.
Environment Types
2. Deterministic vs. Stochastic

● If the next state of the environment can be completely
determined by the current state and the actions executed by the
agent, then the environment is Deterministic, otherwise, it is
Stochastic.
● Strategic: Deterministic except for the actions of other agents
Examples:
1. Deterministic: Crossword Puzzle
2. Stochastic: Automated Taxi driver
3. Strategic: Chess with a clock
Environment Types
3. Episodic vs. Sequential:
Episodic
The agent's experience is divided into atomic "episodes“. Each episode
consists of the agent perceiving and then performing a single action and the
choice of action in each episode depends only on the episode itself.
Example: An agent that has to spot defective parts on an assembly line bases each decision on
the current part, regardless of previous decisions; moreover, the current decision doesn’t affect
whether the next part is defective.
Sequential
In sequential environments, on the other hand, the current decision could
affect all future decisions.
Examples: Chess and Taxi driving are sequential: in both cases, short-term actions can have
long-term consequences.
Episodic environments are much simpler than sequential environments because the agent
does not need to think ahead.
Environment types
4. Static vs. Dynamic:
Static:
The environment is unchanged while an agent is
deliberating.
Semi dynamic:
The environment itself does not change with the
passage of time but the agent's performance score
does.
Dynamic:
The environment gets changed while an agent is
deliberating.
Environment types
5. Discrete vs. Continuous:

A limited number of distinct, clearly defined percepts and actions.
6. Single agent vs. Multiagent:

Single Agent
An agent operating by itself in an environment.
Multi Agent
More than one agent operate in the environment. It can be competitive or cooperative.
Environment Types
Environment types (Contd…)
• The environment type largely determines the agent design

• The real world is (of course) partially observable, stochastic, sequential, dynamic,
continuous, multi-agent
ENVIRONMENT CLASS
A number of environments are implemented, together with a general-purpose

environment simulator that places one or more agents in a simulated environment,
observes their behavior over time, and evaluates them according to a given
performance measure. Such experiments are often carried out not for a single
environment but for many environments drawn from an environment class.
For example, to evaluate a taxi driver in simulated traffic, we would want to run
many simulations with different traffic, lighting, and weather conditions. If we
designed the agent for a single scenario, we might be able to take advantage of
specific properties of the particular case but might not identify a good design for
driving in general.
ENVIRONMENT GENERATOR
An environment generator for each environment class that selects particular

environments (with certain likelihoods) in which to run the agent.
For example, the vacuum environment generator initializes the dirt pattern and agent
location randomly. We are then interested in the agent’s average performance over
the environment class. A rational agent for a given environment class maximizes this
average performance.
Agent functions and programs
• An agent is completely specified by the agent function mapping

percept sequences to actions.
• Agent program implements agent function using agent architecture.

• Input to agent program is the current percept whereas agent function
takes the percept history as input.
Table Driven Agent
function TABLE-DRIVEN-AGENT(percept ) returns an action

persistent: percepts, a sequence, initially empty
table, a table of actions, indexed by percept sequences, initially fully
specified
append percept to the end of percepts
action ←LOOKUP(percepts, table)
return action
Examples of Table Driven Agent
•
Table Driven Agent: A Failure
•
Agent types
Four basic types of agents in order of increasing sophistication:
• Simple reflex agents

• Model-based reflex agents
• Goal-based agents
• Utility-based agents
Simple reflex agents
• It works by finding a rule whose condition matches the current

situation ( as defined by the percept ) and then doing the action
associated with that rule.
• A set of condition ~ action rules / situation ~ action rules /

productions / if~ then rules are defined.
e.g if the car – in - front is braking
then initiate – braking
• This agent function only succeeds when the environment is fully

observable.
A Simple Reflex Agent:
In the two-state vacuum environment
The agent program for a simple reflex agent in the two-state

vacuum environment:
function REFLEX-VACUUM-AGENT([location, status]) returns an

action
if status = Dirty then return Suck
else if location = A then return Right
else if location = B then return Left
A Simple Reflex Agent with Internal State:
In the two-state vacuum environment
function REFLEX-VACUUM-AGENT([location, status]) returns an action
static: remind, keeps track of clean status, initially zero
if status = Dirty then return Suck
else if (location = A and remind<1) then
{
remind=remind +1
return Right
}
else if (location = B and remind<1)then
{
remind=remind+1
return Left
}
else return NOP
Simple reflex agents
A Simple Reflex Agent in Nature
percepts
(size, motion)
RULES:
(1) If small moving object,
then activate SNAP
(2) If large moving object,
then activate AVOID and inhibit SNAP
ELSE (not moving) then NOOP
needed for
completeness Action: SNAP or AVOID or
NOOP
Model-based reflex agents
• Model based agents can handle partially observable

environments.
• Itscurrent state is stored inside the agent maintaining some

kind of structure which describes the part of the world which
can’t be seen. This behavior requires information on how the
world behaves and works. This additional information
completes the “world view” model.
• A model – based reflex agent keeps track of the current state of

the world using an internal model. It then chooses an action in
the same way as the reflex agent.
• The state changes whenever an action is performed or

something is perceived in the environment.
• For the world that is partially observable

● the agent has to keep track of an internal state
● That depends on the percept history
● Reflecting some of the unobserved aspects
● E.g., driving a car and changing lane
• Requiring two types of knowledge

● How the world evolves independently of the agent
● How the agent’s actions affect the world
Example Table Agent
With Internal State
IF THEN
Saw an object ahead, and turned Go straight

right, and it’s now clear ahead
Saw an object Ahead, turned right, Halt

and object ahead again
See no objects ahead Go straight
See an object ahead Turn randomly

Example Reflex Agent With Internal State:
Wall-Following
start
Actions: left, right, straight, open-door

Rules:
1. If open(left) & open(right) and open(straight) then choose randomly between
right and left
2. If wall(left) and open(right) and open(straight) then straight
3. If wall(right) and open(left) and open(straight) then straight
4. If wall(right) and open(left) and wall(straight) then left
5. If wall(left) and open(right) and wall(straight) then right
6. If wall(left) and door(right) and wall(straight) then open-door
7. If wall(right) and wall(left) and open(straight) then straight.
8. (Default) Move randomly
Model-based Reflex Agents
The agent is with memory

Goal based agents
• Knowing about the current state of the environment is not always enough to
decide what to do; additionally sort of goal information which describes
situations that are desirable is also required. This allows the agent a way to
choose among multiple possibilities , selecting the one which reaches a goal
state.
Goal-based agents
• Current state of the environment is always not enough

• The goal is another issue to achieve
● Judgment of rationality / correctness
• Actions chosen goals, based on
● the current state
● the current percept
Goal-based agents
• Conclusion
● Goal-based agents are less efficient
● but more flexible
● Agent Different goals different tasks
● Search and planning
● two other sub-fields in AI
● to find out the action sequences to achieve its goal
A model based - Goal based agent
• It keeps track of the world state and a set of goals it is trying to

achieve and picks an action that will eventually lead to the
achievement of its goal.
Goal-based agents
Utility based agents
• Goal based agents only distinguish between goal states and non-goal states.
• It is possible to define a measure of how desirable a particular state is. This
measure can be obtained through the use of a utility function which maps a
state to a measure of the utility of the state. So, utility function maps a state
onto a real number, which describes the associated degree of happiness.
• A complete specification of the utility function allows rational decisions.

Utility-based agents
• Goals alone are not enough

● to generate high-quality behavior
● E.g. meals in Canteen, good or not ?
• Many action sequences the goals
● some are better and some worse
● If goal means success,
● then utility means the degree of success (how successful it is)
• it is said state A has higher utility

● If state A is more preferred than others
• Utility is therefore a function
● that maps a state onto a real number
● the degree of success
• Utility has several advantages:

● When there are conflicting goals,
● Only some of the goals but not all can be achieved
● utility describes the appropriate trade-off
● When there are several goals
● None of them are achieved certainly
● utility provides a way for the decision-making
A model based-utility based agent
• It uses a model of the world along with a utility function that measures its
preferences among states of the world. Then it chooses an action that leads to
the best expected utility.
Learning Agents
• After an agent is programmed, can it work immediately?

● No, it still need teaching
• In AI,
● Once an agent is done
● We teach it by giving it a set of examples
● Test it by using another set of examples
• We then say the agent learns
● A learning agent
Learning Agents
• Four conceptual components
● Learning element
● Making improvement
● Performance element
● Selecting external actions
● Critic
● Tells the Learning element how well the agent is doing with respect
to fixed performance standard.
(Feedback from user or examples, good or not?)
● Problem generator
● Suggest actions that will lead to new and informative experiences.
Learning agents
• Learning has an advantage that it allows the agents to initially

operate in unknown environments and to become more
competent than its initial knowledge alone might allow.
Learning agents
• Components:-
• Learning element:- responsible for making improvements.
• Performance elements:- responsible for selecting actions.
• Critics:- provides feedback

• Problem generator:- responsible for suggesting actions that will lead to
new experiences.
Learning agents
Representation of States
Solving problems by
searching
Chapter 3
Outline
• Problem-solving agents
• Problem types
• Problem formulation
• Example problems
• Basic search algorithms
95
Problem solving agent
• The simplest agents are the reflex agents, which base their actions on a direct
mapping from states to actions. Such agents cannot operate well in
environments for which this mapping would be too large to store and would
take too long to learn.
• Goal-based agents, on the other hand, consider future actions and the
desirability of their outcomes.
• One kind of goal-based agent called a problem-solving agent.

• Problem-solving agents use atomic representations, that is, states of the world
are considered as wholes, with no internal structure visible to the problem
solving algorithms.
• Goal-based agents that use more advanced factored or structured

• Our discussion of problem solving begins with precise definitions of
problems and their solutions and give several examples to illustrate these
definitions.
• We then describe several general-purpose search algorithms that can be used

to solve these problems.
• There are several uninformed search algorithms—algorithms that are given

no information about the problem other than its definition. Although some of
these algorithms can solve any solvable problem, none of them can do so
efficiently.
• There are some Informed search algorithms which on the other hand, can do
quite well given some guidance on where to look for solutions
• A problem can be defined or formulated formally by 4 components:-

• Initial state :- Describes possible initial state from where problem solving agent
starts in.
• A set of actions and Successor Function:- Given a particular state x, Successor

Function (SF (x)) returns a set of <action, successor> ordered pairs, where each
action is one of the legal actions in state x and each successor is a state that can
be reached from x by applying the action.
Together, the initial state and successor function implicitly define the state space of
the problem i.e. the set of all states reachable from the initial state.
Initial state + SF => state space 98
Problem solving …..
State space forms a graph in which the nodes are states and the arcs between nodes are
actions. (It defines all the possible configurations of the relevant objects associated with
the problem.)
• Goal test :- It determines whether a given state is a goal state.
• Path cost :- A path in the state space is a sequence of states connected by a sequence of
actions. A path cost function assigns a numeric cost to each path. The problem-solving
agent chooses a cost function that reflects its own performance measure.
Path cost = ∑Step costs => Sum of the costs of the individual actions along the path.
(Step cost of taking action a to go from state x to state y is denoted by c(x, a, y) )
99
Problem solving…
• These four components that define a problem can be gathered together into a
single data structure that is given as input to a problem-solving algorithm.
• A solution to a problem is a path from the initial state to a goal state.

• Solution quality is measured by the path cost function, and an optimal
solution has the lowest path cost among all solutions.
Problem-solving agents
101
Example: Romania
• On holiday in Romania; currently in Arad.
• Formulate goal:
• To be in Bucharest
• Formulate problem:
• states: various cities
• actions: drive between cities
• Find solution:
• sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest 102
Romania with step costs in km
Selecting a state space
• Real world is absurdly complex
state space must be abstracted for problem solving
• (Abstract) state = set of real states
• (Abstract) action = complex combination of real actions
• e.g., "Arad Zerind" represents a complex set of possible routes, detours, rest stops, etc.
• For guaranteed realizability, any real state "in Arad“ must get to some real state "in Zerind"
• (Abstract) solution =
• set of real paths that are solutions in the real world
• Each abstract action should be "easier" than the original problem 104
Problem formulation for Toy problems
• Simple vacuum world problem

• 8 – puzzle problem (or Sliding block problem)
• 8 – queen problem
• Knuth number generation problem
Simple vacuum world problem
(State space graph)
• states?
• actions?
• goal test?
• path cost?
106
Simple vacuum world problem
(State space graph)…
• states? dirt and location

• actions? Left, Right, Suck
• goal test? no dirt at all locations
• path cost? 1 per action 107
The 8-puzzle problem
• states?
• actions?
• goal test?
• path cost?
108
The 8-puzzle problem…
• states? locations of tiles

• actions? move blank left, right, up, down
• goal test? = goal state (given)
• path cost? 1 per move
[Note: optimal solution of n-Puzzle family is NP-hard]
109
8-Queen problem
There are two main kinds of formulation. An incremental
formulation involves operators that augment the state
description, starting with an empty state; for the 8-queens
problem, this means that each action adds a queen to the state.
A complete-state formulation starts with all 8 queens on the
board and moves them around. In either case, the path cost is
of no interest because only the final state counts. The first
incremental formulation one might try is the following:
8-Queen problem…
Knuth’ s Number Generation
Problem formulation for Real world problems
• The route-finding problem is defined in terms of specified locations and transitions

along links between them.
• Route-finding algorithms are used in a variety of applications.
• Some, such as Web sites and in-car systems that provide driving directions, are
relatively straightforward extensions of the Romania example.
• Others, such as routing video streams in computer networks, military operations
planning, and airline travel-planning
• systems, involve much more complex specifications.
Airline Travel Problem
Consider the airline travel problem that must be solved

by a travel-planning Web site: • Transition model: The state resulting from taking a
• States: Each state obviously includes a location (e.g., flight will have the flight’s destination as the current
an airport) and the current time. Furthermore, because location and the flight’s arrival time as the current time.
the cost of an action (a flight segment) may depend on • Goal test: Are we at the final destination specified by
previous segments, their fare bases, and their status as the user?
domestic or international, the state must record extra
information about these “historical” aspects. • Path cost: This depends on monetary cost, waiting
time, flight time, customs and immigration procedures,
• Initial state: This is specified by the user’s query. seat quality, time of day, type of airplane,
• Actions: Take any flight from the current location, in frequent-flyer mileage awards, and so on.
any seat class, leaving after the current time, leaving
enough time for within-airport transfer if needed.
Some but not exhaustive list of Real world
problems
• Touring problems
• Traveling salesperson problem (TSP)
• VLSI layout problem
• Robot navigation
• Automatic assembly sequencing
• Protein design
Basic AI problem solving techniques
• Problem solving by searching

• Problem solving by Reasoning / Inference
• Problem solving by Matching
116
SEARCHING FOR SOLUTIONS
Having formulated some problems, we now need to solve

them. A solution is an action sequence, so search algorithms
work by considering various possible action sequences. The
possible action sequences starting at the initial state form a
search tree with the initial state at the root; the branches are
actions and the nodes correspond to states in the state space
of the problem.
Tree search example
118
Tree search example
119
Tree search example
120
Informal Tree search algorithm
• Basic idea:
• offline, simulated exploration of state space by generating
successors of already-explored states (a.k.a.~expanding states)
121
Informal Graph search algorithms
Some examples of Graph search
State vs. node
• A state is a (representation of) a physical configuration
• A node is a data structure constituting part of a search tree includes
state, parent node, action, path cost g(x), depth
• The Expand function creates new nodes, filling in the various fields
and using the SuccessorFn of the problem to create the
corresponding states.
124
Node Details
Implementation: general tree search
126
Implementation of nodes in search algorithm
• A node is a bookkeeping data structure used to represent the search tree. A state
corresponds to a configuration of the world. Thus, nodes are on particular paths, as
defined by PARENT pointers, whereas states are not. Furthermore, two different
nodes can contain the same world state if that state is generated via two different
search paths.
• Now that we have nodes, we need somewhere to put them. The frontier needs to be
stored in such a way that the search algorithm can easily choose the next node to
expand according to its preferred strategy. The appropriate data structure for this is a
queue.
Implementation of nodes in search algorithm
• The operations on a queue are as follows:
• EMPTY?(queue) returns true only if there are no more elements in the queue.
• POP(queue) removes the first element of the queue and returns it.
• INSERT(element, queue) inserts an element and returns the resulting queue.
• Queues are characterized by the order in which they store the inserted nodes.
• Three common variants are:
• FIFO queue, which pops the oldest element of the queue;
• LIFO queue (also known as a stack), which pops the newest element of the queue;
• Priority queue, which pops the element of the queue with the highest priority according to
some ordering function
Evaluating Search strategies
• Performance of search strategies are evaluated along the following dimensions:-
• Completeness: does it always find a solution if one exists?
• Time complexity: number of nodes generated
• Space complexity: maximum number of nodes in memory
• Optimality: does it always find a least-cost solution?
• Time and space complexities are measured in terms of

• b: the branching factor or maximum number of successors of any node
• d: the depth of the shallowest goal node (i.e., the number of steps along the path from the root)
129
• m: the maximum length of any path in the state space (may be ∞)
Evaluating Search strategies…
• Time is often measured in terms of the number of nodes generated during the
search, and space in terms of the maximum number of nodes stored in memory.
• For the most part, we describe time and space complexities for search on a tree; for
a graph, the answer depends on how “redundant” the paths in the state space are.
• To assess the effectiveness of a search algorithm, we can consider just the search
cost— which typically depends on the time complexity but can also include a term
for memory usage.
• Or we can use the total cost, which combines the search cost and the path cost of
the solution found (also sometimes called solution cost).
Search strategies
They are of 2 types:-
• Uninformed search / Blind search
Blind search has no additional information about the states
beyond that provided in the problem definition. All they can
do is generate successor and distinguish a goal state from a
non-goal state.
• Informed search / Heuristic search
Informed search identifies whether one non-goal state is
“more promising” than another one.
All search strategies are distinguished by the order in which nodes are expanded. 131
Uninformed search strategies
• Uninformed search strategies use only the information available in the
problem definition. Popular ones are:
• Breadth-first search (BFS)
• Uniform-cost search (UCS)
• Depth-first search (DFS)
• Depth-limited search (DLS)
• Iterative deepening search (IDS)
132
• Bidirectional search (BDS)
Breadth-first search
• It is a strategy in which the root node is expanded first, then all the successors
of the root node are expanded, then their successors. At a given depth in the
search tree, all the nodes are expanded before any node at the next level is
expanded.
• A FIFO queue is used i.e, new successors join the tail of the queue.
133
Breadth Fast Search Algorithm
Breadth-first search algorithm
• Create a variable NODE-LIST (FIFO queue) and set it to initial state.

• Until a goal state is found or the NODE-LIST is empty,
Do
A. If NODE-LIST is empty then quit.

else remove the first element from NODE-LIST and call it V(visited)
135
Breadth-first search algorithm
B. For each rule ( from the rule set ) whose L.H.S matches with the
state described in V
Do
I. Apply the rule to generate a new state.
II. If the new state is a goal state then quit and return the state.
III. Otherwise add the new state to the end of the NODE-LIST.
136
• Expand shallowest unexpanded node

• Implementation:
• fringe is a FIFO queue, i.e., new successors go at end
137

• Implementation:
138

• Implementation:
139
Properties of breadth-first search
• Complete? Yes (if b is finite)
• Time? 1+b+b2+b3+… +bd = O(bd)
• Space? O(bd) (keeps every node in memory)

• Optimal? Yes ( if path cost is a non-decreasing function of depth i.e path cost = 1 per step)
• Space is the bigger problem (more than time)

140
Breadth Fast Search
Uniform cost search (UCS)
• When all step costs are equal, breadth-first search is optimal because it always
expands the shallowest unexpanded node.
• By a simple extension, we can find an algorithm that is optimal with any

step-cost function. Instead of expanding the shallowest node, uniform-cost
search expands the node n with the lowest path cost g(n).
• This is done by storing the frontier as a priority queue ordered by g.

•
Uniform cost search (UCS)…
function UNIFORM-COST-SEARCH(problem) returns a solution, or failure
• node ←a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
• frontier ←a priority queue ordered by PATH-COST, with node as the only element
• explored ←an empty set
• loop do
• if EMPTY?( frontier) then return failure
• node←POP( frontier ) /* chooses the lowest-cost node in frontier */
• if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
• add node.STATE to explored
• for each action in problem.ACTIONS(node.STATE) do
• child ←CHILD-NODE(problem, node, action)
• if child .STATE is not in explored or frontier then
• frontier ←INSERT(child , frontier )
• else if child .STATE is in frontier with higher PATH-COST then
• replace that frontier node with child

• In addition to the ordering of the queue by path cost, there are two other
significant differences from breadth-first search.
1) The first is that the goal test is applied to a node when it is selected for
expansion rather than when it is first generated. The reason is that the first goal
node that is generated may be on a suboptimal path.
2)The second difference is that a test is added in case a better path is found to a
node currently on the frontier.
• Both of these modifications come into play in the next example where the
problem is to get from Sibiu to Bucharest in the Romania Touring problem.
• The successors of Sibiu are Rimnicu Vilcea and Fagaras, with costs 80 and 99, respectively.
• The least-cost node, Rimnicu Vilcea, is expanded next, adding Pitesti with cost 80 + 97=177.
• The least-cost node is now Fagaras, so it is expanded, adding Bucharest with cost 99+211=310.
• Now a goal node has been generated, but uniform-cost search keeps going, choosing Pitesti for
expansion and adding a second path to Bucharest with cost 80+97+101= 278.
• Now the algorithm checks to see if this new path is better than the old one; it is, so the old one is
discarded. Bucharest, now with g-cost 278, is selected for expansion and the solution is returned.
• It is easy to see that uniform-cost search is optimal in general. Uniform-cost search expands nodes in
order of their optimal path cost. (It is because step costs are nonnegative and paths never get shorter
as nodes are added.)
• Hence, the first goal node selected for expansion must be the optimal solution.
Uniform-cost search
• Expand least-cost unexpanded node
• Implementation:
• fringe = queue ordered by path cost
• Equivalent to breadth-first if step costs all equal

• Complete? Yes, if step cost ≥ ε where every action costs at least ε
• Time? No. of nodes with g ≤ cost of optimal solution, O(b1 + ceiling(C*/ ε)) where C* is the cost
of the optimal solution
• Space? No. of nodes with g ≤ cost of optimal solution, O(b1 + ceiling(C*/ ε))
• Optimal? Yes – nodes expanded in increasing order of g(n) 197
Uniform-cost search
• Uniform-cost search is guided by path costs rather than depths, so its complexity is not easily
characterized in terms of b and d. Instead, let C* be the cost of the optimal solution, and
assume that every action costs at least ε.
• Then the algorithm’s worst-case time and space complexity is O(b1 + ceiling(C*/ ε) ) ), which can
be much greater than bd. This is because uniform cost search can explore large trees of small
steps before exploring paths involving large and perhaps useful steps.
• When all step costs are equal, b1 + ceiling(C*/ ε) is just bd+1 i.e. when all step costs are the same,
uniform-cost search is similar to breadth-first search, except that the latter stops as soon as it
generates a goal, whereas uniform-cost search examines all the nodes at the goal’s depth to
see if one has a lower cost.
• Thus uniform-cost search does strictly more work by expanding nodes at depth d
unnecessarily.
Depth-first search( DFS)
• It is a strategy that expands the deepest node in the search tree.

• Here a stack is used.
201
1. Form a one element stack consisting of the root node.
2. Until the stack is empty or the goal node is found out, repeat the
following:-
1. Remove the first element from the stack. If it is the goal node announce
success, return.
2. If not, add the first element’s children if any, to the top of the stack.
3. If the goal node is not found announce failure.
202
• Depth-first search always expands the deepest node in the current frontier of the search tree.
• The progress of the search is illustrated next. (Assume A to be Initial node and M to be Goal
node.)
• The search proceeds immediately to the deepest level of the search tree, where the nodes
have no successors. As those nodes are expanded, they are dropped from the frontier, so then
the search “backs up” to the next deepest node that still has unexplored successors.
• The depth-first search algorithm is an instance of the graph-search algorithm; whereas

breadth-first-search uses a FIFO queue, depth-first search uses a LIFO queue (Stack).
• A LIFO queue means that the most recently generated node is chosen for expansion. This
must be the deepest unexpanded node because it is one deeper than its parent—which, in turn,
was the deepest unexpanded node when it was selected.
Depth-first search
• Expand deepest unexpanded node
• Implementation:
• fringe = LIFO queue, i.e., put successors at front
204
• Expand deepestDepth-first search
unexpanded node
• Implementation:
205
Depth-first search
• Implementation:
• fringe = LIFO queue, i.e., put successors at fron
206
Depth-first search
• Implementation:
207
Depth-first search

• Implementation:
208
Depth-first search

• Implementation:
209
Depth-first search

• Implementation:
210
Depth-first search

• Implementation:
211
Depth-first search

• Implementation:
212
Depth-first search

• Implementation:
213
Depth-first search

• Implementation:
214
Depth-first search

• Implementation:
215
Properties of depth-first search
• Complete? No: fails in infinite-depth spaces, spaces with loops
• We may modify the algorithm to avoid repeated states along the path
DFS is complete in finite spaces.
• Time? The number of nodes generated is of the order of O(bm) . It is terrible if m is much larger than d
• but if solutions are dense, may be much faster than breadth-first
• Space? It only stores the unexpanded nodes. So it requires 1 +b + b +b ….. m times = O(bm), i.e., linear
space!
• Optimal? No. If it makes a wrong choice, it may go down a very long path and finds a solution, where as there
may be a better solution at a higher level in the tree.
216
Recursive Depth First Search with Depth Limit
• As an alternative to the GRAPH-SEARCH-style implementation,

it is common to implement depth-first search with a recursive
function that calls itself on each of its children in turn.
• (Arecursive depth-first algorithm incorporating a depth limit is

shown under DLS)
DFS Algorithm
● DFS will continue to visit neighbors in a recursive pattern

Whenever we visit v from u, we recursively visit all unvisited neighbors of v. Then we
backtrack (return) to u.
Note: it is possible that w2 was unvisited when we recursively visit w1, but became visited
by the time we return from the recursive call.
u
v w3
w1 w2
DFS Algorithm
Flag all vertices as not
visited
Flag yourself as visited
For unvisited neighbors,

call RDFS(w) recursively
We can also record the paths using pred[ ].

Example
Adjacency List Visited Table (T/F)
0 0 F -
8 1 F -
2 F -
source 2 3 F -
9
4 F -
1
5 F -
3 7 6 F -
6 7 F -
4
5 8 F -
9 F -
Pred
Initialize visited
table (all False)
Initialize Pred to -1
Example
0 0 F -
1 F -
8 2 T -
3 F -
source 2 9 4 F -
1 5 F -
6 F -
3 7
7 F -
6
4 8 F -
5 9 F -
Pred
Mark 2 as visited
RDFS( 2 )
Now visit RDFS(8)
Example
0
0 F -
8 1 F -
2 T -
source 2 9 3 F -
1 4 F -
5 F -
3 7 6 F -
6 7 F -
4
5 8 T 2
9 F -
Pred
Mark 8 as visited
Recursive
calls RDFS( 2 )
RDFS(8) mark Pred[8]
2 is already visited, so visit RDFS(0)
Example
0
0 T 8
8 1 F -
2 T -
source 2 9 3 F -
1 4 F -
5 F -
3 7 6 F -
6 7 F -
4
5 8 T 2
9 F -
Pred
Mark 0 as visited
Recursive
calls RDFS( 2 )
RDFS(8) Mark Pred[0]
RDFS(0) -> no unvisited neighbors, return
to call RDFS(8)
Example
Back to 8
0
0 T 8
8 1 F -
2 T -
source 2 9 3 F -
1 4 F -
5 F -
3 7 6 F -
6 7 F -
4
5 8 T 2
9 F -
Pred
Recursive
calls RDFS( 2 )
RDFS(8)
Now visit 9 -> RDFS(9)
Example
0
0 T 8
8 1 F -
2 T -
source 2 9 3 F -
1 4 F -
5 F -
3 7 6 F -
6 7 F -
4
5 8 T 2
9 T 8
Pred
Mark 9 as visited
Recursive
calls RDFS( 2 )
RDFS(9)
-> visit 1, RDFS(1)
Example
0
0 T 8
8 1 T 9
2 T -
source 2 9 3 F -
1 4 F -
5 F -
3 7 6 F -
6 7 F -
4
5 8 T 2
9 T 8
Pred
Mark 1 as visited
Recursive
calls RDFS( 2 )
RDFS(9)
RDFS(1)
visit RDFS(3)
Example
0
0 T 8
8 1 T 9
2 T -
source 2 9 3 T 1
1 4 F -
5 F -
3 7 6 F -
6 7 F -
4
5 8 T 2
9 T 8
Pred
Mark 3 as visited
Recursive
calls RDFS( 2 )
RDFS(9)
RDFS(1)
RDFS(3)
visit RDFS(4)
Example
0
0 T 8
8 1 T 9
2 T -
source 2 9 3 T 1
1 4 T 3
5 F -
3 7 6 F -
6 7 F -
4
5 8 T 2
9 T 8
Pred
RDFS( 2 ) Mark 4 as visited
Recursive RDFS(8)
calls RDFS(9) Mark Pred[4]
RDFS(1)
RDFS(3)
RDFS(4) STOP all of 4’s neighbors have been visited
return back to call RDFS(3)
Example
0
0 T 8
8 1 T 9
2 T -
source 2 9 3 T 1
1 4 T 3
5 F -
3 7 6 F -
6 7 F -
4
5 8 T 2
9 T 8
Back to 3
Pred
RDFS( 2 )
Recursive RDFS(8)
calls RDFS(9)
RDFS(1)
RDFS(3)
visit 5 -> RDFS(5)
Example
0
0 T 8
8 1 T 9
2 T -
source 2 9 3 T 1
1 4 T 3
5 T 3
3 7 6 F -
6 7 F -
4
5 8 T 2
9 T 8
Pred
RDFS( 2 )
Recursive RDFS(8) Mark 5 as visited
calls RDFS(9)
Mark Pred[5]
RDFS(1)
RDFS(3)
RDFS(5)
3 is already visited, so visit 6 -> RDFS(6)
Example
0
0 T 8
8 1 T 9
2 T -
source 2 9 3 T 1
1 4 T 3
5 T 3
3 7 6 T 5
6 7 F -
4
5 8 T 2
9 T 8
Pred
RDFS( 2 )
RDFS(8)
calls
RDFS(3)
RDFS(5)
RDFS(6)
visit 7 -> RDFS(7)
Example
0
0 T 8
8 1 T 9
2 T -
source 2 9 3 T 1
1 4 T 3
5 T 3
3 7 6 T 5
6 7 T 6
4
5 8 T 2
9 T 8
Pred
RDFS( 2 )
RDFS(8)
calls
RDFS(3)
RDFS(5)
RDFS(6)
RDFS(7) -> Stop no more unvisited neighbors
Example
0 0 T 8
1 T 9
8
2 T -
3 T 1
source 2 9 4 T 3
1 5 T 3
3 7 6 T 5
7 T 6
6
4 8 T 2
5
9 T 8
Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9)
calls
RDFS(1)
RDFS(3)
RDFS(5)
RDFS(6) -> Stop
Example
0 0 T 8
1 T 9
8
2 T -
3 T 1
source 2 9 4 T 3
1 5 T 3
3 7 6 T 5
7 T 6
6
4 8 T 2
5
9 T 8
Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9)
calls
RDFS(1)
RDFS(3)
RDFS(5) -> Stop
Example
0 0 T 8
1 T 9
8
2 T -
3 T 1
source 2 9 4 T 3
1 5 T 3
3 7 6 T 5
7 T 6
6
4 8 T 2
5
9 T 8
Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9)
calls
RDFS(1)
RDFS(3) -> Stop
Example
0 0 T 8
1 T 9
8
2 T -
3 T 1
source 2 9 4 T 3
1 5 T 3
3 7 6 T 5
7 T 6
6
4 8 T 2
5
9 T 8
Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9)
calls
RDFS(1) -> Stop
Example
0 0 T 8
1 T 9
8
2 T -
3 T 1
source 2 9 4 T 3
1 5 T 3
3 7 6 T 5
7 T 6
6
4 8 T 2
5
9 T 8
Pred
RDFS( 2 )
RDFS(8)
Recursive RDFS(9) -> Stop
calls
Example
0 0 T 8
1 T 9
8
2 T -
3 T 1
source 2 9 4 T 3
1 5 T 3
3 7 6 T 5
7 T 6
6
4 8 T 2
5
9 T 8
Pred
RDFS( 2 )
RDFS(8) -> Stop
Recursive
calls
Example
0 0 T 8
1 T 9
8
2 T -
3 T 1
source 2 9 4 T 3
1 5 T 3
3 7 6 T 5
7 T 6
6
4 8 T 2
5
9 T 8
Pred
RDFS( 2 ) -> Stop
Recursive
calls
Example
0 Adjacency List Visited Table (T/F)
8 0 T 8
1 T 9
source 2 2 T -
9
3 T 1
1
4 T 3
3 7 5 T 3
6 6 T 5
4
5 7 T 6
8 T 2
9 T 8
Pred
Check our paths, does DFS find valid paths? Yes.
Try some examples.

Path(0) ->
Path(6) ->
Path(7) ->
Depth-first search
• The time complexity of depth-first graph search is bounded by
the size of the state space (which may be infinite, of course).
• A depth-first tree search, on the other hand, may generate all of

the O(bm) nodes in the search tree, where m is the maximum
depth of any node; this can be much greater than the size of the
state space.
(Note that m itself can be much larger than d (the depth of the
shallowest solution and is infinite if the tree is unbounded.)
Depth-first search
• So far, depth-first search seems to have no clear advantage over breadth-first
search, except for its space complexity.
• For a depth-path graph search, there is no advantage, if the state space is

extremely large, but a depth-first tree search needs to store only a single
path from the root to a leaf node, along with the remaining unexpanded
sibling nodes for each node on the path.
• Once a node has been expanded, it can be removed from memory as soon as
all its descendants have been fully explored.
• For a state space with branching factor b and maximum depth m, depth-first
search requires storage of only O(bm) nodes.
Depth-first search
• This has led to the adoption of depth-first tree search as the basic
workhorse of many areas of AI.
• Constraint Satisfaction (Chapter 6),

• Propositional Satisfiability (Chapter 7),
• Logic Programming (Chapter 9).
We focus primarily on the tree search version of depth-first search.
Depth-first search
• A variant of depth-first search called backtracking search uses still less
memory.
• Inbacktracking, only one successor is generated at a time rather than all

successors; each partially expanded node remembers which successor to
generate next.
• In this way, only O(m) memory is needed rather than O(bm).

• Backtracking search facilitates yet another memory-saving (and time-saving)
trick: the idea of generating a successor by modifying the current state
description directly rather than copying it first. This reduces the memory
requirements to just one state description and O(m) actions.
• For problems with large state descriptions, such as robotic assembly, these
techniques are critical to success.
Depth-limited search
• The problem with DFS is that the search can go down an infinite branch and
thus never return. Depth limited search avoids this problem by imposing a
depth limit l which effectively terminates the search at that depth. That is ,
nodes at depth l are treated as if they have no successors.
• The choice of depth parameter l is an important factor. If l is too deep , it is
wasteful in terms of both time and space. But if l < d (the depth at which
solution exists) i,e the shallowest goal is beyond the depth limit, then this
algorithm will never reach a goal state.
246
Depth-limited search
Depth-first search with depth limit l,

i.e., nodes at depth l have no successors
Recursive implementation:
247
Properties of depth- limited search
• Complete? If l >= d , then it is.
• Time? O(b l ).
• Space? O(bl), i.e., linear space.
• Optimal? No.
248
Iterative deepening search
• The problem with depth-limited search is deciding on a suitable

depth parameter, which is not always easy.
• To overcome this problem there is another search called iterative

deepening search. This search method simply tries all possible
depth limits; first 0, then 1, then 2 etc. until a solution is found.
Iterative deepening combines the benefits of DFS and BFS. It may
appear wasteful as it is expanding nodes multiple times. But the
overhead is small in comparison to the growth of an exponential
search tree. 249
250
Iterative deepening search l =0
251
252
253
254
• Number of nodes generated in a breadth first search to depth d with branching

factor b:
NBFS = b0 + b1 + b2 + … + bd-2 + bd-1 + bd
• Number of nodes generated in an iterative deepening search to depth d with

branching factor b:
NIDS = (d+1)b0 + d b1 + (d-1)b2 + … + 3bd-2 +2bd-1 + 1bd
as the nodes at the bottom level d are expanded once, the nodes at (d-1) are
expanded twice, those at (d – 2) are expanded three times and so on back to the
root.
255
• For b = 10, d = 5,
• NBFS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111
• NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456
• Overhead = (123,456 - 111,111)/111,111 = 11%
we can see that compared to the overall number of expansions , the total is not
substantially increased.
256
Properties of iterative deepening search
• Complete? Yes , like BFS it is complete when b is finite.

• Time? (d+1)b0 + d b1 + (d-1)b2 + … + bd = O(bd)
• Space? O(bd) , like DFS memory requirement is linear.
• Optimal? Yes, if like BFS path cost is a non-decreasing function of
the depth of the node, it is optimal.
In general iterative deepening is the preferred uninformed search
method when there is a large search space and the depth of the
solution is not known. 257
Summary of algorithms
262
Bidirectional Search (BDS)
BDS (contd…)
•The time complexity of bidirectional search using breadth-first searches in both
directions is O(bd/2). The space complexity is also O(bd/2). This is because search
stops in the midway as soon as any one of the search paths from initial state
(forward search) meets with any one of the search paths from goal state
(backward search).
•For the similar condition, the time complexity of breadth first search from initial
state to goal state is O(bd). The space complexity is also O(bd). It is because
searching proceeds only in one direction i.e. from initial state to goal state (only
forward search).
• The motivation is that bd/2 + bd/2 is much less than bd, or in the figure, the area of
the two small circles is less than the area of one big circle centered on the start
and reaching to the goal.
Comparing Uninformed Search Strategies
Repeated states
• Failure to detect repeated states can turn a linear problem into an

exponential one!
270
Repeated states
• In most searching algorithm, the state space generates an

exponentially larger search tree. This occurs mainly because of
repeated nodes. If we can avoid the generation of repeated nodes we
can limit the number of nodes that are created and stop the expansion
of repeated nodes.
271
Repeated states
• There are three methods having increasing order of computational

overhead to control the generation of repeated nodes:-
272
Repeated states
1. Don’t generate a node that is the same as the parent node.
2. Don’t create paths with cycles in them. To do this we can check

each ancestor node and refuse to create a state that is the same
as this set of nodes.
3. Don’t generate any state that is the same as any state generated
before. This requires that every state is kept in memory. (space
complexity is O(bd ) )
273
Graph search
274
Summary
• Problem formulation usually requires abstracting away real-world details to

define a state space that can feasibly be explored
• Variety of uninformed search strategies
• Iterative deepening search uses only linear space and not much more time than
other uninformed algorithms
275
Informed Search Strategy
(Best-first search)
Heuristic search techniques
• Blind searches (uninformed searches)are normally
very inefficient. By adding domain knowledge we can
improve the search process.
• The idea behind the heuristic search is that we explore
the node that is most likely to be nearest to a goal
state.
• A heuristic function has some knowledge about the
problem so that it can judge how close the current
state is to the goal state.
• A heuristic function h(n) = estimated cost of the
cheapest path from the state at node n to a goal state.
(Heuristic functions)
• The choice of f determines the search strategies.
• Most best first algorithms include as a component of f a heuristic function,
denoted h(n)
• h(n) = estimated cost of the cheapest path from the state at node n to a goal
state.
• h(n) takes a node as input, unlike g(n) in UCS, it depends only on the state
at that node.
• For example, in Romania, one might estimate the cost of the cheapest path
from Arad to Bucharest via the straight-line distance from Arad to
Bucharest.
Heuristic functions (contd…)
• Heuristic functions are the most common form in which additional knowledge
of the problem is imparted to search algorithm.
• For the present context, we consider these heuristic function to be arbitrary,

nonnegative, problem-specific functions, with one constraint :
If n is a goal state, then h(n) = 0.
Best-first search
• Idea: use an evaluation function f(n) for each node
• Use this to estimate the degree of "desirability“ for each node.
• Then expand the most desirable unexpanded node.
• Implementation:
Order the nodes in fringe or sequence in decreasing order of desirability.
• Two special cases of Best-first search where h(n) is used as f(n) to guide search:
• Greedy best-first search [only h(n) is used as f(n)]
• A* search [h(n) + g(n) is used as f(n)]
Greedy best-first search
• It tries to expand the node that is closest to the goal state.

• It follows a single path but switch over to a different path if it
appears to be more promising at any stage.
• A promising node is selected by applying a suitable HF

[Heuristic Function, h(n)]to each competing node.
Data structures used for best-first search
• OPEN
• It is a priority queue of nodes which have been generated
and have had the heuristic function applied to them but
which have not yet been expanded. ( priority is evaluated
by a HF value).
• CLOSED
• It contains nodes that have already been expanded. ( it is
used to ensure that the same node is not expanded more
than once.)
Greedy best-first search
• Evaluation function f(n) = h(n) (heuristic)

= estimate of cost from n to goal
• e.g., hSLD(n) = straight-line distance from n to Bucharest

• Greedy best-first search expands the node that appears to be closest to goal
Greedy best-first search algorithm
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 from OPEN.
b) Generate its successors.

Greedy best-first search algorithm (contd…)
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.
Greedy best-first search example: (Romania
example)
Greedy best-first search example (contd…)
Properties of Greedy best-first search
• Complete? No – can get stuck in loops, e.g., Iasi Neamt Iasi Neamt
….
• Time? O(bm), but a good heuristic can give dramatic improvement

• Space? O(bm) -- keeps all nodes in memory
• Optimal? No
Properties of Greedy best-first search (contd…)
*
A search
• Idea: avoid expanding paths that are already expensive

• Evaluation function f(n) = g(n) + h(n)
• g(n) = cost so far to reach n
• h(n) = estimated cost from n to goal
• f(n) = estimated total cost of path through n to goal
*
A search
• The Best first search algorithm is a simplified version of A* algorithm .

• A* uses the same f, g ,h functions as well as the lists OPEN and
CLOSED.
• A* algorithm:-
1) start with OPEN containing only the initial node. Set that node’s g
value to zero , its h value to whatever it is and its f value to h + 0 = h.
initially closed is empty.
*
A search
2. Until a goal node is found, repeat the procedure:

I. if there are no nodes on OPEN, report failure. Otherwise, pick
the node from OPEN with the lowest f value. Call it
BESTNODE. Remove it from OPEN , place it on CLOSED . If
BESTNODE is a goal node, then exit and report a solution; else
generate the successors of BESTNODE. For each such
successor, do the following:
*
A search
a) Set SUCCESSOR to point back to BESTNODE.

b) Compute g(SUCCESSOR) = g( BESTNODE) + the cost of getting
from BESTNODE to SUCCESSOR.
c) See if SUCCESSOR is the same as any node on OPEN. If so, call that
node OLD. Since this node already exists in the graph, we can throw
SUCCESSOR away and add OLD to the list of BESTNODES
successors.
*
A search
determine the parent link:- If the path just found to SUCCESSOR is

cheaper than the current best path to OLD, then reset OLD’s parent – link
to BESTNODE; else, don’t update anything.
d) if SUCCESSOR is not in OPEN but in CLOSED, call it OLD and add OLD
to the list of BESTNODE’s successors. Check to see if the new path is
better as in step (c) . If it is, then set the parent link and g and f value
appropriately. Propagate the new cost downward and determine the better
path. If required set the parent link accordingly.
*
A search
e) If SUCCESSOR is neither in OPEN nor in CLOSED , then put it on

OPEN and add it to the list of BESTNODE’s successors. Compute
f(SUCCESSOR) = g(SUCCESSOR) + h( SUCCESSOR)
*
A search example
*
A search example(Romania example)
*
A search example
*
A search example
*
A search example
*
A search example
Properties of A*
• Complete? Yes (unless there are infinitely many nodes with f ≤ f(G) )
• Time? Exponential
• Space? Keeps all nodes in memory
• Optimal? Yes if h(n) is admissible.
Admissible heuristics
• A heuristic h(n) is admissible if for every node n,
h(n) ≤ h*(n), where h*(n) is the true cost to reach the
goal state from n.
• An admissible heuristic never overestimates the cost

to reach the goal, i.e., it is optimistic
• Example: hSLD(n) (never overestimates the actual road
distance)
• Theorem: If h(n) is admissible, A* using
TREE-SEARCH is optimal
Consistent heuristics
• A heuristic is consistent if for every node n, every successor n' of n generated by any action a,
h(n) ≤ c(n,a,n') + h(n')
• If h is consistent, we have
f(n') = g(n') + h(n')

= g(n) + c(n,a,n') + h(n')
≥ g(n) + h(n)
= f(n)
• i.e., f(n) is non-decreasing along any path.

• Theorem: If h(n) is consistent, A* using GRAPH-SEARCH is optimal
Some Example Search Graphs
Some Example Search Graphs (contd…)
• In this problem the start state is S, and the goal state is G. The transition costs are next to the edges, and the heuristic
estimate, h, of the distance from the state to the goal is in the state’s node. Assume ties are always broken by choosing the
state which comes first alphabetically.
• 1. What is the order of states expanded using Depth First Search? Assume DFS terminates as soon as it reaches the goal
state.
• Answer: S, A, B, D, F ,G
• 2. What is the order of states expanded using Breadth First Search?
• Answer: S, A, B, C, D, E, F, G
• 3. What is the order of states expanded using Best First Search? Assume BFS terminates as soon as it reaches the
• goal state.
• Answer: S, B, D, F, G
• 4. What is the order of states expanded using A* search?
• Answer: S, A, B, D, C, E, F, G
• 5. What is a least cost path from S to G?
• Answer: S, A, C, F, G
A* Example
A* Example
E.g., for the 8-puzzle:
• h1(n) = number of misplaced tiles
• h2(n) = total Manhattan distance

(i.e., no. of squares from desired location of each tile)
• h1(S) = ?
• h2(S) = ?
E.g., for the 8-puzzle:
• h1(n) = number of misplaced tiles

• h2(n) = total Manhattan distance
(i.e., no. of squares from desired location of each tile)
• h1(S) = ? 8
• h2(S) = ? 3+1+2+2+2+3+3+2 = 18
8-puzzle heuristics: explanation
8-puzzle heuristics: explanation (contd…)
Beyond Classical Search
Chapter-4
Local Search Algorithms and Optimization
Problems
• Systematic Search problems:
• The search algorithms that we have seen so far are designed to explore search
spaces systematically. This systematicity is achieved by keeping one or more paths
in memory and by recording which alternatives have been explored at each point
along the path. When a goal is found, the path to that goal also constitutes a
solution to the problem (a sequence of actions from initial state to goal state).
• Local Search problems:

• These algorithms perform purely local search in the state space, evaluating and
modifying one or more current states rather than systematically exploring
paths from an initial state. These algorithms are suitable for problems in which all
that matters is the solution state, not the path cost to reach it. The path to the goal
is irrelevant.
• For example, in the 8-queens problem what matters is the final configuration of
queens, not the order in which they are added.
Problems
• The same general property holds for(contd…)
many important applications as indicated
below:
• Integrated-circuit design
• Factory-floor layout
• Job-shop scheduling
• Automatic programming
• Telecommunications network optimization
• Vehicle routing
• Portfolio management
The family of local search algorithms includes: Hill Climbing, Simulated
Problems (contd…)
• If the path to the goal does not matter, we might consider a different class of
algorithms, ones that do not worry about paths at all.
• Local search algorithms operate using a single current node (rather than multiple
paths) and generally move only to neighbors of that node. Typically, the paths
followed by the search are not retained. Although local search algorithms are not
systematic, they have two key advantages:
• (1) they use very little memory—usually a constant amount;

• (2) they can often find reasonable solutions in large or infinite (continuous) state
spaces for which systematic algorithms are unsuitable.
Problems (contd…)
• In addition to finding goals, local search algorithms are useful for solving pure
optimization problems, in which the aim is to find the best state according to an
objective function.
• Many optimization problems do not fit the “standard” search model (both
uninformed and informed).
• For example, nature provides an objective function—reproductive fitness—that

Darwinian evolution could be seen as attempting to optimize, but there is no “goal
test” and no “path cost” for this problem.
Problems (contd…)
• To understand local search, we find it useful to consider the state-space landscape. A
landscape has both “location” (defined by the state) and “elevation” (defined by the value of
the heuristic cost function or objective function).
• If elevation corresponds to cost, then the aim is to find the lowest valley—a global
minimum;
• if elevation corresponds to an objective function, then the aim is to find the highest peak—a
global maximum.
• We can convert from one to the other just by inserting a minus sign.
• Local search algorithms explore this landscape. A complete local search algorithm always
finds a goal if one exists; an optimal algorithm always finds a global minimum/maximum.
Problems (contd…)
Hill climbing
• Hill climbing ( basic or steepest-ascent) search algorithm is a
local search algorithm.
• It is often used when a good heuristic function is available for

evaluating states but when no other useful knowledge is
available. This algorithm is simply a loop that continuously
moves in the direction of increasing value i.e uphill. It
terminates when it reaches a “peak” where no neighbor has a
higher value. The algorithm doesn’t maintain a search tree, so
the current node data structure only records the state and its
objective function value. Hill – climbing doesn’t look ahead
beyond the immediate neighbors of the current state.
• This resembles trying to find the top of Mount Everest in a

thick fog while suffering from amnesia.
Basic Hill climbing algorithm
1. Evaluate the initial state (IS). If it is the goal state

(GS) , then return it and quit. Else consider IS as the
current state (CS) and proceed.
2. Loop until a solution is found or there are no new

operator (OP) to be applied to the CS.
a) Select an OP that has not yet been applied to the CS and
apply it to produce a new state (NS).
Basic Hill climbing algorithm (contd…)
b) Evaluate the NS:

I. If NS is a GS , then return it and quit.
II. If it is not a GS but better than the CS, then consider it as the
current state(i,e CS NS) and proceed.
III. If NS is not better than CS then continue in the loop by selecting

the next appropriate OP for CS.
Steepest-ascent Hill climbing algorithm
It considers all the moves from the CS and selects the
best one as the next state. It is also called gradient
search.
Algorithm
1. Evaluate the initial state (IS). If it is the goal state

(GS) , then return it and quit. Else consider IS as the
current state (CS) and proceed.
2. Loop until a solution is found or until a complete

iteration produces no change to the CS:
Steepest-ascent Hill climbing algorithm (contd…)
a) Let successor (SUCC) be a state such that any NS that
can be generated from CS is better than SUCC. [ i.e
setting SUCC to a minimum value at the beginning of an
iteration or set CS as SUCC]
b) For each operator OP that applies to the CS do:

I. Apply OP to CS and generate a NS.
II. Evaluate the NS. If it is a GS then return it and quit. If not ,

compare it with SUCC. If NS is better than SUCC, then set SUCC
to NS; else leave SUCC unchanged.
c) If the SUCC is better than CS, then set CS to SUCC [i.e

move to the next best state]
Hill-climbing search
• "Like climbing Everest in thick fog with amnesia"

• Both basic and steepest-ascent hill climbing may fail to find a

solution. Either algorithm may terminate not by finding a goal
state but by getting to a state from which no better states can be
generated.
• This will happen if the program has reached either a local

maximum or a plateau or a ridge.
Hill-climbing
• A local maximum search
is a state that is better than all its neighbors but is
not better than some other states farther away.
• Solution of local maxima:-
• Move in some arbitrary direction
• Back track to an ancestor and try some other alternatives.
• A plateau is a flat area in the search space in which all the

neighboring states have the same heuristic function value. It can be a
flat local maximum, from which no uphill exit exists, or a shoulder,
from which progress is possible. A hill-climbing search might get
lost on the plateau.
• Solution of plateau
• Expand few generation ahead to move to a different section of the search
space.
• A ridge is an area in the search space which is higher than its

surroundings but itself has slopes. It is not possible to traverse
a ridge by a single move i. e. no such operator is available.
• Solution of ridges:-
• Apply several operators before doing the evaluation
Hill-climbing search (via ridge)
• Problem: depending on initial state, can get stuck in either Local Maxima or Plateau (which also
includes Shoulder) or Ridges.
Note: 1) Plateau is also known as “Flat local maximum”.
2) Shoulder is a type of Plateau having uphill rising scope.
Hill-climbing search: 8-queens problem
• h = number of pairs of queens that are attacking each other, either directly or indirectly
• h = 17 for the above state
The best moves (or successors) having h = 12 are marked
• A local minimum with h = 1

• A local minimum with h = 0

Variants of Hill Climbing
• 1. Stochastic hill climbing: It chooses at random from among the uphill moves;
the probability of selection can vary with the steepness of the uphill move. This
usually converges more slowly than steepest ascent, but in some state landscapes,
it finds better solutions.
• 2. First-choice hill climbing: It implements stochastic hill climbing by generating

successors randomly until one is generated that is better than the current state. This
is a good strategy when a state has many (e.g., thousands) of successors.
(The hill-climbing algorithms described so far are incomplete—they often fail to
find a goal when one exists because they can get stuck on local maxima.)
• 3. Random-restart hill climbing adopts the well-known adage, “If at first you
don’t succeed, try, try again.” It conducts a series of hill-climbing searches from
randomly generated initial states, until a goal is found.
(The success of hill climbing depends very much on the shape of the state-space
landscape: if there are few local maxima and plateaus, random-restart hill climbing
Simulated Annealing
• A hill-climbing algorithm that never makes “downhill” moves toward states with
lower value (or higher cost) is guaranteed to be incomplete, because it can get
stuck on a local maximum.
• In contrast, a purely random walk—that is, moving to a successor chosen

uniformly at random from the set of successors—is complete but extremely
inefficient.
• Therefore, it seems reasonable to try to combine hill climbing with a random walk
in some way that yields both efficiency and completeness.
• Simulated annealing is such an algorithm.

• Simulated annealing was first used extensively to solve VLSI layout problems in
the early 1980s. It has been applied widely to factory scheduling and other
large-scale optimization tasks.
Simulated Annealing (contd…)
• In metallurgy, annealing is the process used to temper or harden metals and glass
by heating them to a high temperature and then gradually cooling them, thus
allowing the material to reach a low energy crystalline state.
• To explain simulated annealing, we switch our point of view from hill climbing to
gradient descent (i.e., minimizing cost) and imagine the task of getting a
ping-pong ball into the deepest crevice in a bumpy surface.
• If we just let the ball roll, it will come to rest at a local minimum. If we shake the
surface, we can bounce the ball out of the local minimum. The trick is to shake just
hard enough to bounce the ball out of local minima but not hard enough to
dislodge it from the global minimum.
• The simulated-annealing solution is to start by shaking hard (i.e., at a high

temperature) and then gradually reduce the intensity of the shaking (i.e., lower the
temperature).
Simulated Annealing Algorithm
•
Simulated Annealing Algorithm (contd…)
(The simulated annealing

algorithm, a version of
stochastic hill climbing where
some downhill moves are
allowed. Downhill moves are
• accepted readily early in the
annealing schedule and then
less often as time goes on.
The schedule input
determines the value of the
temperature T as a function of
time.)
Local Beam Search
• Keeping just one node in memory might seem to be an extreme reaction to the problem of
memory limitations.
• The local beam search algorithm, which is a path-based algorithm keeps track of k states rather than
just one. It begins with k randomly generated states.
• At each step, all the successors of all k states are generated. If any one is a goal, the algorithm halts.
Otherwise, it selects the k best successors from the complete list and repeats.
• At first sight, a local beam search with k states might seem to be nothing more than running k random
restarts in parallel instead of in sequence.
• In fact, the two algorithms are quite different.
• In a random-restart search, each search process runs independently of the others.
• In a local beam search, useful information is passed among the parallel search threads. In effect, the
states that generate the best successors say to the others, “Come over here, the grass is greener!” The
algorithm quickly abandons unfruitful searches and moves its resources to where the most progress is
being made.
Local Beam Search (contd…)
• In its simplest form, local beam search can suffer from a lack of
diversity among the k states—they can quickly become concentrated
in a small region of the state space, making the search little more
than an expensive version of hill climbing.
• A variant called stochastic beam search, analogous to stochastic

hill climbing, helps alleviate this problem. Instead of choosing the
best k from the pool of candidate successors, stochastic beam search
chooses k successors at random, with the probability of choosing a
given successor being an increasing function of its value.
• Stochastic beam search bears some resemblance to the process of

natural selection, whereby the “successors” (offspring) of a “state”
(organism) populate the next generation according to its “value”
Genetic Algorithms
• A genetic algorithm (or GA) is a variant of stochastic beam search in which
successor states are generated by combining two parent states rather than by
modifying a single state.
• The analogy to natural selection is the same as in stochastic beam search, except
that now we are dealing with mimicking the natural real life reproduction rather
than asexual reproduction as in stochastic beam search. (Later normally does not
happen in real life).
• Like beam searches, GAs begin with a set of k randomly generated states, called
the population. Each state, or individual, is represented as a string over a finite
alphabet—most commonly, a string of 0s and 1s.
• For example, an 8-queens state must specify the positions of 8 queens, each in a
column of 8 squares, and so requires 8 × log28 bits.
• Alternatively, the state could be represented as 8 digits, each in the range from 1 to
8.
Genetic Algorithms (contd…)
(Figure shows a population of four 8-digit strings representing 8-queens

states)
2 4 7 4 8 5 5 2 3 2 7 5 2 4 1 1
(24 non-attacking pairs of queens) (23 non-attacking pairs of queens)
• (a) shows a population of four 8-digit strings representing 8-queens states.
• The production of the next generation of states is shown in Figures (b)–(e).
• In (b), each state is rated by the objective function, or (in GA terminology) the fitness function. A
fitness function should return higher values for better states.
• So, for the 8-queens problem, we use the number of nonattacking pairs of queens, which has a
value of 28 for a solution.
• The values of the given four states are 24, 23, 20, and 11.
• In this particular variant of the genetic algorithm, the probability of being chosen for reproducing is
directly proportional to the fitness score, and the percentages are shown next to the raw scores.
• In Figure (c), two pairs are selected at random for reproduction, in accordance with
the probabilities in (b). It is to be noticed that one individual is selected twice and
one not at all.
• For each pair to be mated, a crossover point is chosen randomly from the
positions in the string. In Figure, the crossover points are after the third digit in
the first pair and after the fifth digit in the second pair.
• In Figure (d), the offspring themselves are created by crossing over the parent
strings at the crossover point. For example, the first child of the first pair gets the
first three digits from the first parent and the remaining digits from the second
parent, whereas the second child gets the first three digits from the second parent
and the rest from the first parent. The 8-queens states involved in this reproduction
step are shown in the next figure.
(The 8-queens states corresponding to the first two parents in Figure

(c) and the first offspring in Figure (d). The shaded columns are lost in
the crossover step and the unshaded columns are retained.)
• The example shows that when two parent states are quite different, the crossover operation can
produce a state that is a long way from either parent state.
• It is often the case that the population is quite diverse early on in the process, so crossover (like
simulated annealing) frequently takes large steps in the state space early in the search process
and smaller steps later on when most individuals are quite similar.
• Finally, in Figure (e), each location is subject to random mutation with a small independent
probability.
• One digit was mutated in the first, third, and fourth offspring.
• In the 8-queens problem, this corresponds to choosing a queen at random and moving it to a
random square in its column.
• Genetic Algorithms (contd…)
function GENETIC-ALGORITHM(population,
FITNESS-FN) returns an individual
• inputs: population, a set of individuals
• function REPRODUCE(x , y) returns an individual
• FITNESS-FN, a function that measures the fitness of an
• inputs: x , y, parent individuals
individual
• n←LENGTH(x ); c←random number from 1 to n
• repeat
• return APPEND(SUBSTRING(x, 1, c), SUBSTRING(y, c + 1, n))
• new population ←empty set
• for i = 1 to SIZE(population) do
• x ←RANDOM-SELECTION(population, FITNESS-FN)
• y ←RANDOM-SELECTION(population, FITNESS-FN)
• child ←REPRODUCE(x , y)
(A genetic algorithm. The algorithm is
• if (small random probability) then child ←MUTATE(child
the same as the one diagrammed in
)
Figure, with one variation: in this more
• add child to new population
popular version, each mating of two
• population ←new population parents produces only one offspring, not
• until some individual is fit enough, or enough time has two.)
elapsed
• return the best individual in population, according to
FITNESS-FN
Chapter 5: Adversarial
Search
In which we examine the problems that arise when

we try to plan ahead in a world where other
agents are planning against us.
Adversarial Search
■ Multi-agent environments:
■ Each agent needs to consider the actions of other agents and
how they affect its own welfare
■ The unpredictability of these other agents can introduce
possible contingencies into the agent’s problem-solving
process
■ cooperative vs. competitive multi-agents
■ Adversarial search problems (often known as Games):
Deals with competitive multi-agents which have conflicting
goals
Games vs. Search Problems
"Unpredictable" opponent
■specifying a move for every possible
opponent reply
•Time limits
■unlikely to find goal, must approximate
Go
AI and Games
■ In AI, “games” have special format:

■ deterministic, turn-taking, 2- player, zero-sum games of perfect
information
■ Zero-sum describes a situation in which a participant’s gain or loss is

exactly balanced by the losses or gains of the other participant(s)
■ Or, the total payoff to all players is the same for every instance of the game
(constant sum)
History of Game Playing
Game playing was one of the first tasks undertaken by AI

By 1950, almost as soon as computers became programmable, Chess had been tackled by
Konard Zuse, by Claude Shannon, by Norbert Wiener and by Alan Turing.
Since then, there has been steady progress in the standard of play, to the point that machines
have surpassed humans in Checkers and Othello, have defeated human champions (although not
every time) in Chess and Backgammon, and are competitive in many other games.
The main exception is Go, in which computers perform at the amateur level.
Games
Types of Games
Game Problem Formulation
■ A game with 2 players (MAX and MIN, MAX moves first, turn-taking) can be defined as a
search problem with:
■ initial state: board position

■ player: player to move
■ successor function: Returns a list of legal (move, state) pairs, each indicating a legal move and the resulting
state.
■ goal test/ terminal test: whether the game is over (States where the game has ended are called terminal states)
■ utility function: gives a numeric value for the terminal states (win, loss, draw). Example: Chess-
+1, -1, 0
•
■ Game tree of the game =
initial state + legal moves for each side
• Next slide shows an example on Game tree for tic-tac-toe (noughts and crosses)
Tic-tac–toe Game tree
• The number on each leaf node indicates the utility value of the terminal state
from the point of view of MAX.
• High values are assumed to be good for MAX and bad for MIN (which is how
the players get their names).
• It is MAX’s job to use the search tree (particularly the utility of terminal
states) to determine the best move.
Optimal strategies
• In a normal search problem, the optimal solution would be a sequence of moves
leading to goal state – a terminal state that is a win.
• In a game, on the other hand, MIN has something to say about it.
• MAX therefore must find a contingent strategy, which specifies MAX’s move in
the initial state, then MAX’s moves in the states resulting from every possible
response by MIN, then MAX’s moves in the states resulting from every possible
response by MIN to those moves, and so on.
• Roughly speaking, an optimal strategy leads to outcomes at least as good as any
other strategy when one is playing an infallible opponent.
Optimal strategies (contd…)
Optimal strategies (contd…)
Optimal strategies & Minimax Value
Minimax Value
A Partial Game Tree for Tic-Tac-Toe
Some analysis on Minimax
Some analysis on Minimax (contd…)
Some analysis on Minimax (contd…)
The Minimax algorithm
The Minimax algorithm (contd…)
The Minimax algorithm (contd…)
Properties of Minimax Algorithm
Optimal decisions in multiplayer games
(contd…)
(contd…)
(contd…)
Alpha-beta Pruning
• The problem with minimax search is that the number of game states it has
to examine is exponential in the number of moves.
• Unfortunately we can’t eliminate the exponent, but we can effectively cut
it in half.
• It is possible to compute the correct minimax decision without looking at
every node in the game tree.
• A particular pruning technique called alpha-beta pruning can eliminate
large part of the tree from consideration.
• When applied to a standard minimax tree, it returns the same move as
minimax would, but prunes away branches that can not possibly influence
the final decision.
Alpha-beta Pruning…
• Stages in the calculation of the optimal decision for the game tree in
Figure 5.2:
• (a) The first leaf below B has the value 3. Hence, B, which is a MIN node, has a value of at most 3.
• (b) The second leaf below B has a value of 12; MIN would avoid this move, so the value of B is still
at most 3.
• (c) The third leaf below B has a value of 8; we have seen all B’s successor states, so the value of B is
exactly 3. Now, we can infer that the value of the root is at least 3, because MAX has a choice worth 3
at the root.
• (d) The first leaf below C has the value 2. Hence, C, which is a MIN node, has a value of at most 2.
But we know that B is worth 3, so MAX would never choose C. Therefore, there is no point in looking
at the other successor states of C. This is an example of alpha–beta pruning.
• (e) The first leaf below D has the value 14, so D is worth at most 14. This is still higher than MAX’s
best alternative (i.e., 3), so we need to keep exploring D’s successor states. Notice also that we now
have bounds on all of the successors of the root, so the root’s value is also at most 14.
• (f) The second successor of D is worth 5, so again we need to keep exploring. The third successor is
worth 2, so now D is worth exactly 2. MAX’s decision at the root is to move to B, giving a value of 3.
A simple formula for Minimax
Basic Idea of α-β
• Consider a node n such that Player has

a choice of moving to that node.
• If Player has a better choice m either at
the parent of n or at any choice point
further up, then n will never be reached
in actual play.
• α-β pruning gets it name from the two
parameters that describe bounds on the
backed-up values
The alpha-beta search algorithm
Question:
Write the Alpha-Beta Algorithm. Explain Alpha and Beta briefly. Solve the following
example and show how alpha-beta pruning helped in pruning the search tree.
Example…
•Prove that: for every game tree, the utility obtained by

MAX using minimax decisions against a suboptimal MIN
will never be lower than the utility obtained playing
against an optimal MIN.
Solution
• Consider a MIN node whose children are terminal nodes. If

MIN plays sub-optimally, then the value of the node is greater
than or equal to the value it would have if MIN played
optimally. Hence, the value of the MAX node that is the MIN
node’s parent can only be increased. This argument can be
extended by a simple induction all the way to the root.
Example…
Consider the following game:
• Draw the complete game tree, using the following convention:
State: (Sa, Sb) where Sa and Sb denote the token locations
• Identify the terminal state in a square box and assign it a value
• Put loop states in double square boxes
• Since it’s not clear how to assign values to loop states, annotate each with a “?”
Game tree of the Example
Constraint Satisfaction
Problems
Chapter 6
Constraint Satisfaction Problems
We have so far explored the idea that problems can be solved by searching in a space of
states. These states can be evaluated by domain-specific heuristics and tested to see
whether they are goal states.
From the point of view of the search algorithm, each state is atomic, or indivisible—a
black box with no internal structure.
However, there is a way to solve a wide variety of problems more efficiently. We use a
factored representation for each state: a set of variables, each of which has a value. A
problem is solved when each variable has a value that satisfies all the constraints on the
variable.
A problem described this way is called a constraint satisfaction problem, or CSP

(contd…)
CSP search algorithms take advantage of the structure of states and

use general-purpose rather than problem-specific heuristics to enable
the solution of complex problems.
The main idea is to eliminate large portions of the search space all at
once by identifying variable/value combinations that violate the
constraints.
(contd…)
A constraint satisfaction problem consists of three components, X, D, and C:
• X is a set of variables, {X1, . . . ,Xn}.

• D is a set of domains, {D1, . . . ,Dn}, one for each variable.
• C is a set of constraints that specify allowable combinations of values.
Each domain Di consists of a set of allowable values, {v1, . . . , vk} for variable Xi.
Each constraint Ci consists of a pair <scope, rel> , where scope is a tuple of

variables that participate in the constraint and rel is a relation that defines the
values that those variables can take on.
Constraint Satisfaction Problems (contd…)
A relation can be represented as an explicit list of all tuples of values

that satisfy the constraint, or as an abstract relation that supports two
operations:
1) Testing if a tuple is a member of the relation and
2) Enumerating the members of the relation.
For example, if X1 and X2 both have the domain {A,B}, then the
constraint saying the two variables must have different values can be
written as <(X1,X2), [(A,B), (B,A)]> or as <(X1,X2), X1!= X2>.
Constraint Satisfaction Problems (Summary)
• Summary:
• Here the goal is to discover some problem state that satisfies a given set of
constraints.
•A constraint satisfaction problem (CSP) is defined by a set of variables X1,
X2,…..Xn and a set of constraints C1,C2,….Cm.
• Each variable Xi has a nonempty domain Di of possible values.
• Each constraint Ci involves some subset of the variables and specifies the allowable
combinations of values for that subset.
Constraint Satisfaction Problems(Summary)
(contd…)
• An assignment of values to some or all of the variables that does not violate
any constraints is called a consistent or legal assignment.
• A complete assignment is that in which every variable is mentioned and if it

satisfies all the constraints, then it is a solution.
Constraint Satisfaction Problems(Summary) (contd…)
• Standard search problem

• state is a "black box“ – any data structure that supports successor function, heuristic function,
and goal test
• CSP:
• state is defined by variables Xi with values from domain Di
• goal test is a set of constraints specifying allowable combinations of values for subsets of
variables
• CSP allows useful general-purpose algorithms with more power than standard
search algorithms which are mostly problem specific.
Outline: Focus on next points of discussion
• Constraint Satisfaction Problems (CSP)

• Backtracking search for CSPs
• Local search for CSPs
• Suppose that we are looking at a map of Australia showing each of its states and territories. We
are given the task of coloring each region either red, green, or blue in such a way that no
neighboring regions have the same color. To formulate this as a CSP, we define the variables to
be the regions
X = {WA, NT, Q, NSW, V, SA, T}
• The domain of each variable is the set

Di = {red, green, blue}
• The constraints require neighboring regions to have distinct colors. Since there are nine places
where regions border, there are nine constraints:
C = {SA != WA, SA != NT, SA != Q, SA != NSW, SA != V, WA != NT, NT != Q, Q
!= NSW, NSW != V}
Constraint Satisfaction Problems (contd…)
• SA != WA is a shortcut for <(SA,WA), SA != WA>, where SA != WA can be

fully enumerated in turn as
{(red , green), (red , blue), (green, red), (green, blue), (blue, red),
(blue, green)}
• There are many possible solutions to this problem, such as
{WA = red, NT = green, Q = red, NSW = green, V = red, SA = blue,
T = red}
Example: Map-Coloring
• Variables : WA, NT, Q, NSW, V, SA, T

• Domains Di = {red, green, blue}
• Constraints: adjacent regions must have different colors
• e.g., WA ≠ NT, or <(WA,NT), WA != NT> where WA != NT can be one of the
following combinations:
{(red,green),(red,blue),(green,red),(green,blue),(blue,red),(blue,green)}
Example: Map-Coloring (contd…)
• Solutions are complete and consistent assignments, e.g., WA =

red, NT = green, Q = red, NSW = green, V = red, SA = blue, T =
green
CSP vs General State Space Search
•
Constraint graph
• Binary CSP: each constraint relates two variables

• Constraint graph: nodes are variables, arcs are constraints
Example problem: Job-shop scheduling
• Factories have the problem of scheduling a day’s worth of jobs, subject to various
constraints. In practice, many of these problems are solved with CSP techniques.
• Consider the problem of scheduling the assembly of a car. The whole job is
composed of tasks, and we can model each task as a variable, where the value of
each variable is the time that the task starts, expressed as an integer number of
minutes.
• Constraints can assert that one task must occur before so many tasks can go on at
once.
• Constraints can also specify that a task takes a certain amount of time to complete.
• We now consider a small part of the car assembly, consisting of 15 tasks: install
axles (front and back), affix all four wheels (right and left, front and back), tighten
nuts for each wheel, affix hubcaps, and inspect the final assembly.
Example problem: Job-shop scheduling (contd…)
• We can represent the tasks with 15 variables:

X = {AxleF, AxleB, WheelRF, WheelLF, WheelRB, WheelLB, NutsRF, NutsLF , NutsRB,
NutsLB, CapRF , CapLF , CapRB, CapLB, Inspect} .
• The value of each variable is the time that the task starts.
Precedence constraints between individual tasks:
• Whenever a task T1 must occur before task T2, and task T1 takes duration d1 to complete, we add an
arithmetic constraint of the form:
T1 + d1 ≤ T2
• In our example, the axles have to be in place before the wheels are put on, and it takes 10 minutes to install an
axle, so we write
AxleF + 10 ≤ WheelRF ; AxleF + 10 ≤ WheelLF ;
AxleB + 10 ≤ WheelRB; AxleB + 10 ≤ WheelLB .
• Next we say that, for each wheel, we must affix the wheel (which takes 1 minute), then tighten the nuts (2
minutes), and finally attach the hubcap (1 minute, but not represented yet):
WheelRF + 1 ≤ NutsRF ; NutsRF + 2 ≤ CapRF ;
WheelLF + 1 ≤ NutsLF ; NutsLF +2 ≤ CapLF ;
WheelRB + 1 ≤ NutsRB; NutsRB + 2 ≤ CapRB;
WheelLB + 1 ≤ NutsLB; NutsLB + 2 ≤ CapLB .
Disjunctive constraint:
• Suppose we have four workers to install wheels, but they have to share one tool that
helps put the axle in place. We need a disjunctive constraint to say that AxleF and
AxleB must not overlap in time; either one comes first or the other does:
(AxleF + 10 ≤ AxleB) or (AxleB + 10 ≤ AxleF)
• This looks like a more complicated constraint, combining arithmetic and logic. But
it still reduces to a set of pairs of values that AxleF and AxleB can take on.
•
Variations on the CSP formalism
A) Discrete variables:
Discrete finite domains:
Examples: 1) Map-coloring problems
2) Job scheduling with time limits
3) 8-queens problem [This can also be viewed as a finite-domain
CSP, where the variables Q1, . . . ,Q8 are the positions of each queen in
columns 1, . . . , 8 and each variable has the domain Di = {1, 2, 3, 4, 5, 6, 7,
8}.]
[n variables, domain size d O(dn) = no. of possible complete assignments
e.g. Finite domain CSPs include Boolean CSPs, whose variables can be
either true or false. ]
Discrete variables…
• Boolean CSPs include as special cases some NP-complete problems.

• In the worst case , therefore, we can not expect to solve finite-domain CSPs in
less than exponential time.
• In most practical applications, however, general-purpose CSP algorithms can

solve problems orders of magnitude larger than those solvable via the
general-purpose search algorithms.
Variations on the CSP formalism (contd…)
Discrete infinite domains:

Examples: 1) The set of integers or strings
2) The job-scheduling problem without deadline [There
would be an infinite number of start times for each variable.]
(With infinite domains, it is no longer possible to describe constraints

by enumerating all allowed combinations of values. Instead, a
constraint language must be used that understands constraints such
as T1 + d1 ≤ T2 directly, without enumerating the set of pairs of
allowable values for (T1, T2).)
B) Continuous variables:
Continuous domains:
Constraint satisfaction problems with continuous domains are common in the real
world and are widely studied in the field of operations research.
Example: 1) Scheduling of experiments on the Hubble Space Telescope [It requires
very precise timing of observations; the start and finish of each observation and
maneuver are continuous-valued variables that must obey a variety of astronomical,
precedence, and power constraints.]
2) Linear programming problems [where constraints must be linear
equalities or inequalities. Linear programming problems can be solved in time
polynomial in the number of variables.]
C) Constraints:
Unary constraint:
• It restricts the value of a single variable.
• Example: In the map-coloring problem it could be the case that South Australians won’t
tolerate the color green; we can express that with the unary constraint <(SA),SA != green>
Binary constraint:
• It relates two variables.
• Example: SA != NSW is a binary constraint. (A binary CSP is one with only binary
constraints; it can be represented as a constraint graph).
[There are also higher-order constraints such as Ternary constraint.
Example: Asserting that the value of Y is between X and Z, with the ternary constraint
Between(X, Y, Z).]
Global Constraints:
•A constraint involving an arbitrary number of variables is called a global

constraint. (The name is traditional but confusing because it need not involve all
the variables in a problem).
• One of the most common global constraints is Alldiff , which says that all of the
variables involved in the constraint must have different values.
Examples:
• Sudoku problems (all variables in each row or column or 3 ˟ 3 matrix must

satisfy an Alldiff constraint.)
• Cryptarithmetic puzzles. (Each letter in a cryptarithmetic puzzle represents a

different digit.)
Sudoku problems
Sudoku problems (contd…)
Sudoku problems (contd…)
Cryptarithmetic Problems
Cryptarithmetic Problems (contd…)
• Variables: F T U W R O
• Domains: {0,1,2,3,4,5,6,7,8,9}
• Constraints: Alldiff (F,T,U,W,R,O)

O + O = R + 10 · C1
C1 + W + W = U + 10 · C2
C2 + T + T = O + 10 · C3
C3 = F, T ≠ 0, F ≠ 0
Cryptarithmetic Problems (contd…)
• These constraints can be

represented in a constraint
hypergraph as shown in
the figure.
• A hypergraph consists of
ordinary nodes (the circles
in the figure) and
hypernodes (the squares),
which represent n-ary
constraints.
Cryptarithmatic Problems (contd…)
Example: cryptarithmetic problem
C4 C3 C2 C1
S E N D
+ M O R E
________________
M O N E Y
1. D + E = 10 * C1 + Y
2. C1 + N + R = 10 * C2 + E
3. C2 + E + O = 10 * C3 + N
4. C3 + S + M = 10 * C4+ O
5. C4 = M = 1 (As M has to be non-zero.)

Where C1, C2, C3 and C4 can be either 0 or 1.
Other alphabets can take unique values from the set { 0,1, 2, 3, 4, 5, 6, 7, 9}
Example: cryptarithmetic problem (contd…)
C4 C3 C2 C1
S E N D
Initial state
+ M O R E
-----------------------
M O N E Y M=1 (As C4 =1)
S=8 OR 9
O=0 OR 1 O=0
N=E OR E+1 N=E+1
C2=1
D=Y+5 N+R>8
E=2
R=8 E<>9
E=5 , E = 2, 3, 4 ends with conflict
D=7
N=6 R=9
C3= 0 AND S=9 Contradiction
R=9 - C1 as S=9
C1=1
5+D=Y ORC1=0
5+D=10 + Y
Y= 2
SOLUTION: {S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2} and { C1 =1, C2 = 1, C3
=0, C4 = 1 }
One of the solutions f0r this example
C4 C3 C2 C1 1 0 1 1
-------------------- --------------------
S E N D 9 5 6 7
+ M O R E + 1 0 8 5
______________ ______________
M O N E Y 1 0 6 5 2
SOME MORE CRYPTARITHMETIC
PROBLEMS
• MATH + MYTH = HARD
• ODD + ODD = EVEN
• CROSS + ROADS = DANGER
• TWO + TWO = FOUR
• BASE + BALL = GAMES
• TOUGH + DOUGH = RHYME
• YOUR + YOU = HEART
• FOUR + ONE = FIVE
Real-world CSPs
• Assignment problems
• e.g., who teaches what class
• Timetabling problems
• e.g., which class is offered when and where?
• Transportation scheduling
• Factory scheduling
(Notice that many real-world problems involve real-valued
variables)
Real-world CSPs (contd…)
• The constraints we have described so far have all been absolute constraints, violation of
which rules out a potential solution.
• Many real-world CSPs include preference constraints indicating which solutions are
preferred.
• For example, in a university class-scheduling problem, there are absolute constraints that no
professor can teach two classes at the same time. But we also may allow preference
constraints: Prof. R might prefer teaching in the morning, whereas Prof. N prefers teaching
in the afternoon. A schedule that has Prof. R teaching at 2 p.m. would still be an allowable
solution but would not be an optimal one.
• Preference constraints can often be encoded as costs on individual variable

assignments—for example, assigning an afternoon slot for Prof. R costs 2 points against the
overall objective function, whereas a morning slot costs 1.
• With this formulation, CSPs with preferences can be solved with optimization search
methods, either path-based or local. We call such a problem a constraint optimization
problem, or COP.
Real-world CSPs (contd…)
• In regular state-space search, an algorithm can do only one thing:
search.
• In CSPs there is a choice: an algorithm can search (choose a new

variable assignment from several possibilities) or do a specific type
of inference called constraint propagation (use the constraints to
reduce the number of legal values for a variable, which in turn can
reduce the legal values for another variable, and so on.)
• Constraint propagation may be intertwined with search, or it may be

done as a preprocessing step, before search starts. Sometimes this
preprocessing can solve the whole problem, so no search is required
at all.
Local Consistency
• The key idea is local consistency.
• If we treat each variable as a node in a graph and each binary constraint as an arc, then the
process of enforcing local consistency in each part of the graph causes inconsistent values
to be eliminated throughout the graph.
• There are different types of local consistency:
1) Node Inconsistency: A single variable (corresponding to a node in the CSP network)
is node-consistent if all the values in the variable’s domain satisfy the variable’s unary
constraints. For example, in the variant of the Australia map-coloring problem where South
Australians dislike green, the variable SA starts with domain {red, green, blue}, and we can
make it node consistent by eliminating green, leaving SA with the reduced domain {red ,
blue}.
• We say that a network is node-consistent if every variable in the network is
node-consistent.
• It is always possible to eliminate all the unary constraints in a CSP by running node
consistency. It is also possible to transform all n-ary constraints into binary ones.
(Ex.6.6)
Local Consistency (Exercise: 6.6)
Local Consistency (contd…)
•
Standard search formulation (incremental)
Let's start with the straightforward approach, then fix it.
States are defined by the values assigned so far:

• Initial state: the empty assignment { }
• Successor function: assign a value to an unassigned variable that does not conflict with current assignment
fail if no legal assignments
• Goal test: the current assignment is complete
1. This is the same for all CSPs

2. Every solution appears at depth n with n variables
use depth-first search
Backtracking search
• Variable assignments are commutative, i.e.,

[ WA = red then NT = green ] same as [ NT = green then WA = red ]
• Only need to consider assignments to a single variable at each node
• Depth-first search for CSPs with single-variable assignments is called backtracking search
• Backtracking search is the basic uninformed algorithm for CSPs
• Can solve n-queens for n ≈ 24

Backtracking search…
• A variant of depth-first search called backtracking search uses still less memory.
• In backtracking, only one successor is generated at a time rather than all successors; each
partially expanded node remembers which successor to generate next. In this way, only
O(m) memory is needed rather than O(bm).
• Backtracking search facilitates yet another memory-saving (and time-saving) trick: the idea
of generating a successor by modifying the current state description directly rather than
copying it first.
• This reduces the memory requirements to just one state description and O(m) actions.
• For this to work, we must be able to undo each modification when we go back to generate
the next successor.
• For problems with large state descriptions, such as robotic assembly, these techniques are
critical to success.
Backtracking search
Backtracking search
Backtracking example
Improving backtracking efficiency
• General-purpose methods can give huge gains in speed:

• Which variable should be assigned next?
• In what order should its values be tried?
• Can we detect inevitable failure early?
Most constrained variable
• Most constrained variable:

choose the variable with the fewest legal values
• minimum remaining values (MRV) heuristic

Most constraining variable
• Tie-breaker among most constrained variables

• Most constraining variable:
• choose the variable with the most constraints on remaining variables

Least constraining value
• Given a variable, choose the least constraining value:

• the one that rules out the fewest values in the remaining variables
• Combining these heuristics makes 1000 queens feasible

Forward checking
• Idea:
• Keep track of remaining legal values for unassigned variables
• Terminate search when any variable has no legal values
Forward checking
• Idea:
Forward checking
• Idea:
Forward checking
• Idea:
Forward checking
Constraint propagation
• Forward checking propagates information from assigned to unassigned variables,
but doesn't provide early detection for all failures:
• NT and SA cannot both be blue!

• Constraint propagation repeatedly enforces constraints locally
Arc consistency
• Simplest form of propagation makes each arc consistent

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

•X Y is consistent iff
Arc consistency

• X Y is consistent iff
• If X loses a value, neighbors of X need to be rechecked

Arc consistency
• X Y is consistent iff
• If X loses a value, neighbors of X need to be rechecked

• Arc consistency detects failure earlier than forward checking
• Can be run as a preprocessor or after each assignment
Arc consistency algorithm AC-3
• Time complexity: O(n2d3)

Local Search for CSPs: 4-Queen Problem
States:
4 queens in 4 columns (44 = 256 states)
Actions:
move queen in column
Goal test:
no attacks
Evaluation:
h(n) = number of attacks
[Given random initial state, can solve

n-queens in almost constant time for
arbitrary n with high probability (e.g., n =
10,000,000)]
Minimum Conflicts Algorithm (Local Search)
In choosing a new value

for a variable, the most
obvious heuristic is to
select the value that
results in the minimum
number of conflicts with
other variables—the
min-conflicts heuristic
Summary
• CSPs are a special kind of problem:
• states defined by values of a fixed set of variables
• goal test defined by constraints on variable values
• Backtracking = depth-first search with one variable assigned per node
• Variable ordering and value selection heuristics help significantly
• Forward checking prevents assignments that guarantee later failure
• Constraint propagation (e.g., arc consistency) does additional work to constrain values and detect inconsistencies
• Iterative min-conflicts is usually effective in practice

Logical Agents
Chapter 7
Outline
• Knowledge-based agents
• Wumpus world
• Logic in general - models and entailment
• Propositional (Boolean) logic
• Equivalence, validity, satisfiability
• Inference rules and theorem proving
• forward chaining
• backward chaining
• resolution
Logical Agents (Knowledge-based agents)
Knowledge-based agents
• Knowledge is the facts and principles accumulated by

human beings.
• A k- based agent is composed of a knowledge base

and an inference mechanism to infer new sentences
and use these sentences to decide what actions to take.
• Example:- if it is raining
then take an umbrella
weather(raining) take(umbrella)
premise/antecedent conclusion/consequent
• Knowledge-based agents can accept new tasks in the form of explicitly

described goals;
• They can achieve competence quickly by being told or learning new

knowledge about the environment;
• They can adapt to changes in the environment by updating the relevant

knowledge.
Knowledge bases
• A Knowledge base is a set of sentences in a formal language.

• A KB consists of
• FACTS : Statements of truth in the application domain.
• PROCEDURAL RULES : well defined, invariant rules
• HEURISTIC : procedures to be followed when invariant procedurals are
not available.
• FACTS:
• Male(Rajiv)
• Female(Sonia)
• Male(Rahul)
• Female(Priyanka)
• Father(Rajiv, Rahul)
• Mother(Sonia, Rahul)
• RULES:
• Husband(x,y) male(x)
• Wife(x,y) female(x)
• INFERENCING:
• Husband(Rajiv , Sonia) Wife(Sonia, Rajiv)
• The central component of a knowledge-based agent is its knowledge base, or

KB. A knowledge base is a set of sentences. (Here “sentence” is used as a
technical term. It is related but not identical to the sentences of English and
other natural languages.)
• Each sentence is expressed in a language called a knowledge representation

language and represents some assertion about the world. Sometimes we
dignify a sentence with the name axiom, when the sentence is taken as given
without being derived from other sentences.
• There must be a way to add new sentences to the knowledge base and a way
to query what is known.
• The standard names for these operations are TELL and ASK respectively.
• Both operations may involve inference—that is, deriving new sentences from
old.
• Inference must obey the requirement that when one ASKs a question of the
knowledge base, the answer should follow from what has been told (or
TELLed) to the knowledge base previously.
A simple knowledge-based agent
• Like all agents, it takes a percept as input and returns an action. The agent
maintains a knowledge base, KB, which may initially contain some
background knowledge.
• Each time the agent program is called, it does three things. First, it TELLs
the knowledge base what it perceives. Second, it ASKs the knowledge base
what action it should perform. In the process of answering this query,
extensive reasoning may be done about the current state of the world, about
the outcomes of possible action sequences, and so on. Third, the agent
program TELLs the knowledge base which action was chosen, and the
• The details of the representation language are hidden inside three functions that implement
the interface between the sensors and actuators on one side and the core representation and
reasoning system on the other.
• MAKE-PERCEPT-SENTENCE constructs a sentence asserting that the agent perceived the

given percept at the given time.
• MAKE-ACTION-QUERY constructs a sentence that asks what action should be done at the
current time.
• Finally, MAKE-ACTION-SENTENCE constructs a sentence asserting that the chosen action

was executed.
• The details of the inference mechanisms are hidden inside TELL and ASK.
• The agent program shown above appears quite similar to the agents with internal state
described in earlier chapter. Because of the definitions of TELL and ASK, however, the
knowledge-based agent is not an arbitrary program for calculating actions. It is amenable to a
description at the knowledge level, where we need specify only what the agent knows and
what its goals are, in order to fix its behavior.
• For example, an automated taxi might have the goal of taking a passenger from San Francisco
to Marin County and might know that the Golden Gate Bridge is the only link between the
two locations. Then we can expect it to cross the Golden Gate Bridge because it knows that
that will achieve its goal.
• Notice that this analysis is independent of how the taxi works at the implementation level.
• It doesn’t matter whether its geographical knowledge is implemented as linked lists or pixel
maps, or whether it reasons by manipulating strings of symbols stored in registers or by
propagating noisy signals in a network of neurons.
• A knowledge-based agent can be built simply by TELLing it what it needs to
know.
• Startingwith an empty knowledge base, the agent designer can TELL

sentences one by one until the agent knows how to operate in its
environment. This is called the declarative approach to system building.
• In contrast, the procedural approach encodes desired behaviors directly as

program code.
• A successful agent often combines both declarative and procedural elements

in its design, and that declarative knowledge can often be compiled into more
efficient procedural code.
Knowledge bases
• Declarative approach to building an agent (or other system):

• Tell it what it needs to know
• Then it can Ask itself what to do - answers should follow from the KB
• Agents can be viewed at the knowledge level
i.e., what they know, regardless of how implemented
• Or at the implementation level

• i.e., data structures in KB and algorithms that manipulate them
• Performance measure
•
Wumpus World PEAS description
gold +1000, death -1000
• -1 per step, -10 for using the arrow
• Environment
• Squares adjacent to wumpus are smelly
• Squares adjacent to pit are breezy
• Glitter iff gold is in the same square
• Shooting kills wumpus if you are facing it
• Shooting uses up the only arrow
• Grabbing picks up gold if in same square
• Releasing drops the gold in same square
• Sensors: Stench, Breeze, Glitter, Bump, Scream

• Actuators: Left turn, Right turn, Forward, Grab, Release, Shoot
PEAS Specifications of Wumpus World
Dimensions of Wumpus environment
• Wumpus environment can be characterized along the various dimensions.
• Clearly, it is discrete, static, and single-agent. (The wumpus doesn’t move, fortunately.)
• It is sequential, because rewards may come only after many actions are taken.
• It is partially observable, because some aspects of the state are not directly perceivable: the
agent’s location, the wumpus’s state of health, and the availability of an arrow.
• As for the locations of the pits and the wumpus: we could treat them as unobserved parts of
the state that happen to be immutable—in which case, the transition model for the
environment is completely known; or we could say that the transition model itself is
unknown because the agent doesn’t know which Forward actions are fatal—in which case,
discovering the locations of pits and wumpus completes the agent’s knowledge of the
transition model.
• The environment is deterministic as outcomes can be exactly specified.

Wumpus world characterization
• Fully Observable No – only local perception
• Deterministic Yes – outcomes exactly specified
• Episodic No – sequential at the level of actions
• Static Yes – Wumpus and Pits do not move
• Discrete Yes
• Single-agent? Yes – Wumpus is essentially a natural
feature
Knowledge-based Wumpus Agent
• The agent’s initial knowledge base contains the rules of the environment, as described
previously; in particular, it knows that it is in [1,1] and that [1,1] is a safe square; we denote
that with an “A” and “OK,” respectively, in square [1,1].
• The first percept is [None, None, None, None, None], from which the agent can conclude
that its neighboring squares, [1,2] and [2,1], are free of dangers—they are OK. Figure 7.3(a)
shows the agent’s state of knowledge at this point.
• A cautious agent will move only into a square that it knows to be OK.
• Let us suppose the agent decides to move forward to [2,1]. The agent perceives a breeze
(denoted by “B”) in [2,1], so there must be a pit in a neighboring square. The pit cannot be in
[1,1], by the rules of the game, so there must be a pit in [2,2] or [3,1] or both. The notation
“P?” in Figure 7.3(b) indicates a possible pit in those squares.
• At this point, there is only one known square that is OK and that has not yet been visited. So
the prudent agent will turn around, go back to [1,1], and then proceed to [1,2].
• The agent perceives a stench in [1,2], resulting in the state of knowledge shown in Figure
7.4(a).
• The stench in [1,2] means that there must be a wumpus nearby. But the wumpus cannot be in
[1,1], by the rules of the game, and it cannot be in [2,2] (or the agent would have detected a
stench when it was in [2,1]). Therefore, the agent can infer that the wumpus is in [1,3]. The
notation W! indicates this inference.
• Moreover, the lack of a breeze in [1,2] implies that there is no pit in [2,2]. Yet the agent has
already inferred that there must be a pit in either [2,2] or [3,1], so this means it must be in
[3,1].
• This is a fairly difficult inference, because it combines knowledge gained at different times in
different places and relies on the lack of a percept to make one crucial step.
• The agent has now proved to itself that there is neither a pit nor a wumpus in [2,2], so it is
OK to move there.
• Agent’s state of knowledge at [2,2] has not been shown; it is just assumed that the agent turns
and moves to [2,3], giving us Figure 7.4(b).
• In [2,3], the agent detects a glitter, so it should grab the gold and then return home.
• It must be noted that in each case for which the agent draws a conclusion from the available
information, that conclusion is guaranteed to be correct if the available information is correct.
• This is a fundamental property of logical reasoning.

Exploring a wumpus world
Other Sticky Situations
• Breeze in (1,2) and (2,1)
• No safe actions
• Smell in (1,1)
• Cannot move
AI: Chapter 7: Logical Agents

Logic
• Knowledge bases consist of sentences. These sentences are expressed according to the syntax
of the representation language, which specifies all the sentences that are well formed. The
notion of syntax is clear enough in ordinary arithmetic:
• “x + y = 4” is a well-formed sentence, whereas “x4y+ =” is not.

• A logic must also define the semantics or meaning of sentences. The semantics defines the
truth of each sentence with respect to each possible world.
• For example, the semantics for arithmetic specifies that the sentence “x + y =4” is true in a
world where x is 2 and y is 2, but false in a world where x is 1 and y is 1.
• In standard logics, every sentence must be either true or false in each possible world—there is
no “in between.”
Logic…
• Knowledge bases consist of • Example:

sentences in a formal language x + 2 >= y is a sentence
• Syntax
x2 + y > is not a sentence
• Sentences are well formed
• Semantics x + 2 >= y is true iff x + 2 is not less than y
• The “meaning” of the sentence x + 2 >= y is true in a world where x = 7, y=1

• The truth of each sentence with
respect to each possible world x + 2 >= y is false in world where x = 0, y =6
(model)
Logic…
• Entailment means that one thing follows logically from another.
• If α and β are two sentences and α entails β i.e. β follows α (i.e. β follows from α),
then it is symbolized as follows:
α |= β
• α |= β iff in every model in which α is true, β is also true.
• If α is true, then β must be true. But if α is true, but β is false, then entailment relation
fails.
• The truth of β is “contained” in the truth of α.

Logic…
• Example:
Say, KB contains following two sentences:
• “Cleveland won”
• “Dallas won”
Then the sentence “Either Cleveland won or Dallas won” is entailed by KB.
• Examples:
1. x + y = 4 entails 4 = x + y
2. x = 0 entails xy = 0
Logic…
• A model is a formally structured world with respect to which truth
can be evaluated.
• If a sentence α is true in model m, we say that m satisfies α or
sometimes m is a model of α.
• We use the notation M(α) to mean the set of all models of α.
• Logical reasoning involves the relation of logical entailment

between sentences—the idea that a sentence follows logically from
another sentence. In mathematical notation, we write
• α |= β to mean that the sentence α entails the sentence β.
M(α)
• The formal definition of entailment is this: x
• α |= β if and only if, in every model in which α is true, β is also true. x x x M(KB)
x x x x x xx
Using the notation just introduced, we can write α |= β if and only if
M(α) ⊆ M(β) . x x x x x x xx x x
• (Note the direction of the ⊆ here: if α |= β, then α is a stronger
x x xxx x x x x x
assertion than β) xxx xx x x xxxx x x x
• Example: Sentence x = 0 entails the sentence xy = 0. Obviously, in xxx x x xxx xx x x x
any model where x is zero, it is the case that xy is zero (regardless of x
the value of y).
• In the diagram shown, KB |= α iff M(KB) ⊆ M(α)
Logic…
• Entailment in Wumpus World
• Situation after detecting nothing in [1,1],

moving right, breeze in [2,1]
• Consider possible models for ? assuming

only pits
• 3 Boolean choices => 2^3 (= 8) possible

models
Logic
Logic…
• KB = wumpus world rules + observations (through percepts)
• α1 = “There is no pit in [1,2].”, KB |= α1, proved by model checking

Logic…
• KB = wumpus world rules + observations (
• α2 = is “There is no pit in [2,2].”, KB ¬|= α2 proved by model checking

Logic…
• The preceding example not only illustrates entailment but also shows how the definition of entailment
can be applied to derive conclusions—that is, to carry out logical inference.
• The inference algorithm illustrated in the previous figures is called model checking, because it
enumerates all possible models to check that α is true in all models in which KB is true, that is,
• that M(KB) ⊆ M(α).

Logic…
• Inference is the process of deriving a specific sentence from a KB (where the

sentence must be entailed by the KB)
• KB |-i α = sentence α can be derived from KB by procedure i (or) i derives α from ΚΒ.
• Let us assume set of all consequences of KB as the haystack and α as the
needle. Then,
• Entailment => needle being in the haystack
• Inference => finding the needle from the haystack
Logic…
• Soundness
• i is sound if…
• whenever KB |-i α is true, KB |= α is true
• An inference algorithm that derives only entailed sentences is called sound or truth preserving.
• Completeness
• i is complete if
• whenever KB |= α is true, KB |-i α is true
• An inference algorithm is complete if it can derive any sentence that is entailed.
• If KB is true in the real world, then any sentence α derived from KB by a sound inference procedure is also true in the
real world
Logic…
Logic…
• Grounding is the connection between logical reasoning processes and the real environment
in which the agent exists. In particular, how do we know that KB is true in the real world?
(After all, KB is just “syntax” inside the agent’s head.). A simple answer is that the agent’s
sensors create the connection.
• For example, our wumpus-world agent has a smell sensor. The agent program creates a
suitable sentence whenever there is a smell. Then, whenever that sentence is in the
knowledge base, it is true in the real world. Thus, the meaning and truth of percept
sentences are defined by the processes of sensing and sentence construction that produce
them.
• What about the rest of the agent’s knowledge, such as its belief that wumpuses cause smells
in adjacent squares?
• This is not a direct representation of a single percept, but a general rule—derived, perhaps,
from perceptual experience but not identical to a statement of that experience. General rules
like this are produced by a sentence construction process called learning.
Propositional Logic
• AKA Boolean Logic

• False and True
• Proposition symbols P1, P2, etc are sentences
• NOT: If S1 is a sentence, then ¬S1 is a sentence (negation)
• AND: If S1, S2 are sentences, then S1 ∧ S2 is a sentence (conjunction)
• OR: If S1, S2 are sentences, then S1 ∨ S2 is a sentence (disjunction)
• IMPLIES: If S1, S2 are sentences, then S1 ⇒ S2 is a sentence (implication)
• IFF: If S1, S2 are sentences, then S1 ⇔ S2 is a sentence (biconditional)

546
Propositional Logic
Sentence → AtomicSentence | ComplexSentence
AtomicSentence → True | False | P | Q | R | . . .
ComplexSentence → ( Sentence ) | [ Sentence ]
| ￢Sentence
| Sentence ∧ Sentence
| Sentence ∨ Sentence
| Sentence ⇒ Sentence
| Sentence ⇔ Sentence
OPERATOR PRECEDENCE : ￢, ∧, ∨,⇒,⇔
[A BNF (Backus–Naur Form) grammar of sentences in propositional logic, along with operator precedences,
from highest to lowest.]
Propositional Logic
P Q ¬P P∧Q P∨Q P⇒Q P⇔Q
False False True False False True True
False True True False True True False
True False False False True False False
True True False True True True True

AI: Chapter 7: Logical Agents 548
Wumpus World Sentences
• Let Pi,j be True if there is a pit in [i,j]

• “Pits cause breezes in adjacent squares”
• Let Bi,j be True if there is a breeze in [i,j]

B1,1 ⇔ (P1,2 ∨ P2,1)
• ¬P1,1 B2,1 ⇔ (P1,1 ∨ P2,1 ∨ P3,1)

• ¬ B1,1
• B2,1 • A square is breezy if and only if there is an

adjacent pit

A Simple Knowledge Base

• R1: ¬P1,1
• R2: B1,1 ⇔ (P1,2 ∨ P2,1)
• R3: B2,1 ⇔ (P1,1 ∨ P2,2 ∨
P3,1)
• R4: ¬ B1,1
• R5: B2,1
• KB consists of sentences R1
through R5
(R1 ∧ R2 ∧ R3 ∧ R4 ∧
R5) AI: Chapter : Logical Agents 551
[A truth-table enumeration algorithm for deciding propositional entailment. (TT stands

for truth table.) PL-TRUE? returns true if a sentence holds within a model. The variable
model represents a partial model—an assignment to some of the symbols. The keyword
“and” is used here as a logical operation on its two arguments, returning true or false.]
PROPOSITIONAL THEOREM PROVING
(Logical Equivalence, Validity, Satisfiability)

(Logical Equivalence, Validity, Satisfiability) …
• A sentence is valid if it is true in all models
e.g. True, A ∨ ¬A, A ⇒ A, (A ∧ (A ⇒ B) ⇒ B
• Validity is connected to inference via the Deduction Theorem

KB |= α iff (KB ⇒ α) is valid
• Hence, we can decide if α |= β by checking that (α ⇒ β) is true in every

model—which is essentially what the inference algorithm does or by proving
that (α ⇒ β) is equivalent to True. Conversely, the deduction theorem states
that every valid implication sentence describes a legitimate inference.
• A sentence is satisfiable if it is True in, or satisfied by, some model.
• For example, the knowledge base KB of Wumpus World given earlier, (R1
∧ R2 ∧ R3 ∧ R4 ∧ R5), is satisfiable because there are three models in
which it is true.
• Many problems in computer science are really satisfiability problems. For

example, all the constraint satisfaction problems ask whether the constraints
are satisfiable by some assignment.
• Validity and satisfiability are of course connected: α is valid iff ￢α is

unsatisfiable; contrapositively, α is satisfiable iff ￢α is not valid.
• We also have the following useful result:
α |= β if and only if the sentence (α ∧ ￢β) is unsatisfiable.
• Proving β from α by checking the unsatisfiability of (α ∧ ￢β) corresponds

exactly to the standard mathematical proof technique of reductio ad
absurdum (literally, “reduction to an absurd thing”). It is also called proof by
refutation or proof by contradiction.
• One assumes a sentence β to be false and shows that this leads to a

contradiction with known axioms α. This contradiction is exactly what is
meant by saying that the sentence (α ∧ ￢β) is unsatisfiable.
Inference and proofs - Reasoning Patterns
• Inference Rules
• Patterns of inference that can be applied to derive chains of conclusions that lead to the desired goal.
• Modus Ponens
• Given: S1 ⇒ S2 and S1, we can derive or infer S2
• And-Elimination
• Given: S1 ∧ S2, we can derive or infer S1
• Given: S1 ∧ S2, we can derive or infer S2
• DeMorgan’s Law
• Given: ¬( A ∨ B) derive ¬A ∧ ¬B
• Given: ¬( A ∧ B) derive ¬A ∨ ¬B
Inference and proofs - Reasoning Patterns …
•All of the logical equivalences mentioned previously
can be used as inference rules.
•For example, the equivalence for biconditional
elimination yields the following two inference rules:
• 1) If α ⇔ β, we can derive or infer (α ⇒ β) ∧ (β
⇒ α)
• 2) If (α ⇒ β) ∧ (β ⇒ α), we can derive or infer α
⇔β
• .
Inference and proofs - Reasoning Patterns …
• Example Problem:
How these inference rules and equivalences can be used in the Wumpus World: We start with the knowledge base
containing R1 through R5 and show how to prove ￢P1,2, that is, there is no pit in [1,2].
• First, we apply biconditional elimination to R2 (R2: B1,1 ⇔ (P1,2 ∨ P2,1) to obtain
R6: (B1,1 ⇒ (P1,2 ∨ P2,1)) ∧ ((P1,2 ∨ P2,1) ⇒ B1,1) .
• Then we apply And-Elimination to R6 to obtain
R7: ((P1,2 ∨ P2,1) ⇒ B1,1) .
• Logical equivalence for contrapositives gives
R8: (￢B1,1 ⇒ ￢(P1,2 ∨ P2,1)) .
• Now we can apply Modus Ponens with R8 and the percept R4 (i.e., ￢B1,1), to obtain
R9 : ￢(P1,2 ∨ P2,1) .
• Finally, we apply De Morgan’s rule, giving the conclusion
R10 : ￢P1,2 ∧ ￢P2,1 .
• That is, neither [1,2] nor [2,1] contains a pit.
Evaluation of Deductive Inference
• Sound
• Yes, because the inference rules themselves are sound. (This can be proven using a
truth table argument).
• Complete
• If we allow all possible inference rules, we’re searching in an infinite space, hence not
complete
• If we limit inference rules, we run the risk of leaving out the necessary one…
• Monotonic
• If we have a proof, adding information to the DB will not invalidate the proof
Resolution
• Resolution allows a complete inference mechanism (search-based) using only
one rule of inference
• Resolution rule:
• Given: P1 ∨ P2 ∨ P3 …∨ Pn, and ¬P1 ∨ Q1 …∨ Qm
• Conclude: P2 ∨ P3 …∨ Pn ∨ Q1 …∨ Qm
Complementary literals P1 and ¬P1 “cancel out”
• Why it works:
• Consider 2 cases:
P1 is true, and P1 is false 561
Resolution in Wumpus World
• There is a pit at 2,1 or 2,3 or 1,2 or 3,2

• P21 ∨ P23 ∨ P12 ∨ P32
• There is no pit at 2,1
• ¬P21
• Therefore (by resolution) the pit must be at 2,3 or 1,2 or 3,2
• P23 ∨ P12 ∨ P32 562
Proof using Resolution
• To prove a fact P, repeatedly apply resolution until either:
• No new clauses can be added, (KB does not entail P)
• The empty clause is derived (KB does entail P)
• This is proof by contradiction: if we prove that KB ∧ ¬P derives a contradiction (empty clause) and
we know KB is true, then ¬P must be false, so P must be true!
• To apply resolution mechanically, facts need to be in Conjunctive Normal Form (CNF)
• To carry out the proof, need a search mechanism that will enumerate all possible resolutions.

CNF Example
1. B22 ⇔ ( P21 ∨ P23 ∨ P12 ∨ P32 )
2. Eliminate ⇔ , replacing with two implications

(B22 ⇒ ( P21 ∨ P23 ∨ P12 ∨ P32 )) ∧ ((P21 ∨ P23 ∨ P12 ∨ P32 ) ⇒ B22)
3. Replace implication (A ⇒ B) by ¬A ∨ B
(¬B22 ∨ ( P21 ∨ P23 ∨ P12 ∨ P32 )) ∧ (¬(P21 ∨ P23 ∨ P12 ∨ P32 ) ∨ B22)
4. Move ¬ “inwards” (unnecessary parens removed)

(¬B22 ∨ P21 ∨ P23 ∨ P12 ∨ P32 ) ∧ ( (¬P21 ∧ ¬P23 ∧ ¬P12 ∧ ¬P32 ) ∨ B22)
4. Distributive Law
(¬B22 ∨ P21 ∨ P23 ∨ P12 ∨ P32 ) ∧ (¬P21 ∨ B22) ∧ (¬P23 ∨ B22) ∧ (¬P12 ∨ B22) ∧ (¬P32 ∨ B22)
(Final result has 5 clauses)

Resolution Example
• Given B22 and ¬P21 and ¬P23 and ¬P32 , prove P12
• (¬B22 ∨ P21 ∨ P23 ∨ P12 ∨ P32 ) ; ¬P12
• (¬B22 ∨ P21 ∨ P23 ∨ P32 ) ; ¬P21
• (¬B22 ∨ P23 ∨ P32 ) ; ¬P23
• (¬B22 ∨ P32 ) ; ¬P32
• (¬B22) ; B22
• [empty clause]
Evaluation of Resolution
• Resolution is sound
• Because the resolution rule is true in all cases
• Resolution is complete
• Provided a complete search method is used to find the proof, if a proof can be
found it will
• Note: you must know what you’re trying to prove in order to prove it!
• Resolution is exponential
• The number of clauses that we must search grows exponentially…
Horn Clauses
• A Horn Clause is a CNF clause with exactly one positive literal
• The positive literal is called the head
• The negative literals are called the body
• Prolog: head:- body1, body2, body3 …
• English: “To prove the head, prove body1, …”
• Implication: If (body1, body2 …) then head
• Horn Clauses form the basis of forward and backward chaining

• The Prolog language is based on Horn Clauses
• Deciding entailment with Horn Clauses is linear in the size of the knowledge base
Reasoning with Horn Clauses
• Forward Chaining
• For each new piece of data, generate all new facts, until the desired fact is generated
• Data-directed reasoning
• Backward Chaining
• To prove the goal, find a clause that contains the goal as its head, and prove the body
recursively
• (Backtrack when you chose the wrong clause)
• Goal-directed reasoning
Forward Chaining
• Fire any rule whose premises are satisfied in the KB
• Add its conclusion to the KB until the query is found

• AND-OR Graph Forward Chaining
• multiple links joined by an arc indicate conjunction – every link must be proved
• multiple links without an arc indicate disjunction – any link can be proved

Forward Chaining

Forward Chaining

Forward Chaining

Forward Chaining

Forward Chaining

Forward Chaining

Forward Chaining

Forward Chaining

Backward Chaining
• Idea: work backwards from the query q:
• To prove q by BC,
• Check if q is known already, or
• Prove by BC all premises of some rule concluding q
• Avoid loops
• Check if new subgoal is already on the goal stack
• Avoid repeated work: check if new subgoal

• Has already been proved true, or
• Has already failed
579
Backward Chaining

Backward Chaining

Backward Chaining

Backward Chaining

Backward Chaining

Backward Chaining

Backward Chaining

Backward Chaining

Backward Chaining

Backward Chaining

Backward Chaining

Forward Chaining vs. Backward Chaining
• Forward Chaining is data driven

• Automatic, unconscious processing
• E.g. object recognition, routine decisions
• May do lots of work that is irrelevant to the goal
• Backward Chaining is goal driven

• Appropriate for problem solving
• E.g. “Where are my keys?”, “How do I start the car?”
• The complexity of BC can be much less than linear in size of the KB

K- Representation using symbolic logic
• Logic is the art of correct reasoning.

• Symbolic logic uses symbolic structures to carry out automated reasoning to
deduce facts
Logic in general
• Logics are formal languages for representing information such that conclusions can be drawn
• Syntax defines the sentences in the language

• Semantics define the "meaning" of sentences;
• i.e., define truth of a sentence in a world
• E.g., the language of arithmetic

• x+2 ≥ y is a sentence; x2+y > {} is not a sentence
• x+2 ≥ y is true iff the number x+2 is no less than the number y
• x+2 ≥ y is true in a world where x = 7, y = 1
• x+2 ≥ y is false in a world where x = 0, y = 6
Entailment
• Entailment means that one thing follows from another:

KB ╞ α
Knowledge base KB entails sentence α if and only if α is true in all
worlds where KB is true
• E.g., the KB containing “the Giants won” and “the Reds won” entails “Either
the Giants won or the Reds won”
• E.g., x+y = 4 entails 4 = x+y
• Entailment is a relationship between sentences (i.e., syntax) that is based on
semantics
Models
• Logicians typically think in terms of models, which are formally structured worlds with respect to which truth can be evaluated
• We say m is a model of a sentence α if α is true in m
• M(α) is the set of all models of α
• Then KB ╞ α iff M(KB) ⊆ M(α)
• E.g. KB = Giants won and Reds

won α = Giants won
Entailment in the wumpus world
Situation after detecting nothing in
[1,1], moving right, breeze in
[2,1]
Consider possible models for KB

assuming only pits
3 Boolean choices ⇒ 8 possible

models
Wumpus models
Wumpus models
• KB = wumpus-world rules + observations

Wumpus models

• α1 = "[1,2] is safe", KB ╞ α1, proved by model checking
Wumpus models

Wumpus models

• α2 = "[2,2] is safe", KB ╞ α2
Inference
• KB ├i α = sentence α can be derived from KB by procedure i

• Soundness: i is sound if whenever KB ├i α, it is also true that KB╞ α
• Completeness: i is complete if whenever KB╞ α, it is also true that KB ├i α
• Preview: we will define a logic (first-order logic) which is expressive enough
to say almost anything of interest, and for which there exists a sound and
complete inference procedure.
• That is, the procedure will answer any question whose answer follows from
what is known by the KB.
Propositional logic: Syntax
• Propositional logic is the simplest logic – illustrates basic idea
• The proposition symbols P1, P2 etc are sentences
• If S is a sentence, ¬S is a sentence (negation)
• If S1 and S2 are sentences, S1 ∧ S2 is a sentence (conjunction)
• If S1 and S2 are sentences, S1 ∨ S2 is a sentence (disjunction)
• If S1 and S2 are sentences, S1 ⇒ S2 is a sentence (implication)
• If S1 and S2 are sentences, S1 ⇔ S2 is a sentence (biconditional)
Propositional logic: Semantics
Each model specifies true/false for each proposition symbol
E.g. P1,2 P2,2 P3,1

false true false
With these symbols, 8 possible models, can be enumerated automatically.

Rules for evaluating truth with respect to a model m:
¬S is true iff S is false

S1 ∧ S2 is true iff S1 is true and S2 is true
S1 ∨ S2 is true iff S1is true or S2 is true
S1 ⇒ S2 is true iff S1 is false or S2 is true
i.e., is false iff S1 is true and S2 is false
S1 ⇔ S2 is true iff S1⇒S2 is true andS2⇒S1 is true
Simple recursive process evaluates an arbitrary sentence, e.g.,
¬P1,2 ∧ (P2,2 ∨ P3,1) = true ∧ (true ∨ false) = true ∧ true = true

Truth tables for connectives
Wumpus world sentences
Let Pi,j be true if there is a pit in [i, j].
Let Bi,j be true if there is a breeze in [i, j].
¬ P1,1
¬B1,1
B2,1
• "Pits cause breezes in adjacent squares"
B1,1 ⇔ (P1,2 ∨ P2,1)
B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1)
Logical equivalence
• Two sentences are logically equivalent} iff true in same

models: α ≡ ß iff α╞ β and β╞ α
Validity and satisfiability
A sentence is valid if it is true in all models,

e.g., True, A ∨¬A, A ⇒ A, (A ∧ (A ⇒ B)) ⇒ B
Validity is connected to inference via the Deduction Theorem:

KB ╞ α if and only if (KB ⇒ α) is valid
A sentence is satisfiable if it is true in some model

e.g., A∨ B, C
A sentence is unsatisfiable if it is true in no models

e.g., A∧¬A
Satisfiability is connected to inference via the following:

KB ╞ α if and only if (KB ∧¬α) is unsatisfiable
Proof methods
• Proof methods divide into (roughly) two kinds:
• Application of inference rules

• Legitimate (sound) generation of new sentences from old
• Proof = a sequence of inference rule applications

Can use inference rules as operators in a standard search algorithm
• Typically require transformation of sentences into a normal form
• Model checking
• truth table enumeration (always exponential in n)
• improved backtracking
• heuristic search in model space (sound but incomplete)

e.g., min-conflicts-like hill-climbing algorithms
Resolution
Conjunctive Normal Form (CNF)

conjunction of disjunctions of literals
clauses
E.g., (A ∨ ¬B) ∧ (B ∨ ¬C ∨ ¬D)
Resolution inference rule (for CNF):
li ∨… ∨ lk, m1 ∨ … ∨ mn
li ∨ … ∨ li-1 ∨ li+1 ∨ … ∨ lk ∨ m1 ∨ … ∨ mj-1 ∨ mj+1 ∨... ∨ mn

where li and mj are complementary literals.
E.g., P1,3 ∨ P2,2, ¬P2,2

P1,3
Resolution is sound and complete for propositional logic

Conversion to CNF
B1,1 ⇔ (P1,2 ∨ P2,1)
1. Eliminate ⇔, replacing α ⇔ β with (α ⇒ β)∧(β ⇒ α).

(B1,1 ⇒ (P1,2 ∨ P2,1)) ∧ ((P1,2 ∨ P2,1) ⇒ B1,1)
Eliminate ⇒, replacing α ⇒ β with ¬α∨ β.
(¬B1,1 ∨ P1,2 ∨ P2,1) ∧ (¬(P1,2 ∨ P2,1) ∨ B1,1)
5. Move ¬ inwards using de Morgan's rules and double-negation:
(¬B1,1 ∨ P1,2 ∨ P2,1) ∧ ((¬P1,2 ∧ ¬P2,1) ∨ B1,1)
6. Apply distributive law (∧ over ∨) and flatten:

(¬B1,1 ∨ P1,2 ∨ P2,1) ∧ (¬P1,2 ∨ B1,1) ∧ (¬P2,1 ∨ B1,1)
Now it is in CNF form.

• Modus ponens Resolution rules
α β,α
β
• And-elimination
α ∧ β
α
• Elimination of complementary literals
α ∨ β , ~α ∨ γ
β∨γ
Resolution algorithm
• Proof by contradiction, i.e., show KB∧¬α un-satisfiable

Q1. Prove that there is no pit in [1, 2].
Ans:-
Resolution example
From the KB we have:-
from observation:
R1: ~P1,1 , 4
R2: ~ B1,1
3
From rule:- 2
R3. (B1,1 ⇔ (P1,2∨ P2,1))

1
1 2 3 4
R4. (B1,1 ⇒ (P1,2∨ P2,1)) ∧ ((P1,2∨ P2,1) ⇒ B1,1)
Resolution example
Applying end elimination on R4
R5. ((P1,2∨ P2,1) ⇒ B1,1 )
Applying contra-positive law to R5 :-
R6:~ B1,1 ⇒ ~ (P1,2∨ P2,1)
Applying modus ponence to R6 and R2
R7:~ (P1,2∨ P2,1)
Applying D’morgan’s rule to R7:
R8: ~ P1,2 ∧ ~P2,1. applying end elimination to R8:
R9: ~ P1,2 and ~P2,1 are true.
So, there is no pit in either [1,2] or [2,1]
Resolution example
Q2. Prove that there is no pit in [2, 2]
and no pit in [3,1].
Ans:-
From the KB we have:-
from observation: 4
R10: B1,2 , 3
R11: S2,1
R12: ~B2,1 2
From rule:- 1
R13: (B1,2 ⇔ (P1,1∨ P2,2 ∨ P1,3 )) 1 2 3 4 R14. (B2,1 ⇔ (P1,1∨ P2,2 ∨ P3,1 ))
R15. (B2,1 ⇔ (P1,1∨ P2,2 ∨ P3,1 )) ∧ ((P1,1∨ P2,2 ∨ P3,1 ) ⇒ B2,1)
Resolution example
R16. ((P1,1∨ P2,2 ∨ P3,1 ) ⇒ B2,1)
R17:~ B2,1 ⇒ ~ (P1,1∨ P2,2 ∨ P3,1 )
R18:~ (P1,1∨ P2,2 ∨ P3,1 )
R19: ~ P1,1 ∧ ~P2,2. ∧ ~P3,1
Applying end elimination to R19:
R20: ~ P1,1 and ~P2,2 and ~P3,1 are true.
So, there is no pit in [1,1] , [2,2] or [3,1]
Ans:- from observation:-
R1: ~ S1,2
R2: S2,1
Resolution example
R3: ~ W1,1 , ~ W1,2 , ~ W2,1
From rule:-
R4: S1,2 ⇔ (W1,1∨ W2,2 ∨ W1,3)
R5: S2,1 ⇔ (W1,1∨ W2,2 ∨ W3,1)
R6: S1,2 ⇒ (W1,1∨ W2,2 ∨ W1,3) ∧ ((W1,1∨ W2,2 ∨ W1,3) ⇒ S1,2)
Resolution
Applying end elimination on R6 example
R7. ((W1,1∨ W2,2 ∨ W1,3) ⇒ S1,2)
R8:~ S1,2 ⇒ ~ (W1,1∨ W2,2 ∨ W1,3)
R9:~ (W1,1∨ W2,2 ∨ W1,3)
R10: ~ W1,1 ∧ W2,2. ∧ ~ W1,3
Applying end elimination to R10:
R11: ~ W1,1 and ~W2,2 and ~ W1,3 are true.
Applying bi-conditional elimination to R5:-
R12: (S2,1 ⇒ (W1,1∨ W2,2 ∨ W3,1) )∧ ((W1,1∨ W2,2 ∨ W3,1) ⇒ S2,1)
Resolution example
R13. A (S2,1 ⇒ (W1,1∨ W2,2 ∨ W3,1) )
R14: (W1,1∨ W2,2 ∨ W3,1)
Applying end elimination to R14 and ~ W1,1 :
R15: ( W2,2 ∨ W3,1)
Applying end elimination to R15 and ~ W2,2 :
R15: W3,1
So there is wumpus in [3,1].
Resolution by contradiction example
• Convert sentences of KB into CNF form.

• Consider (KB ∧ ¬α)
• A nil proves that α is true.
• KB = (B1,1 ⇔ (P1,2∨ P2,1)) ∧¬ B1,1, α = ¬P1,2

Forward and backward reasoning/chaining
• Forward chaining:
• It is the process of selecting the rules by matching the LHS.
• Here reasoning begins from the start or initial state.
• LHS of the rules are matched against the state description.
• The RHS of the matched rule is added to the state.
• This process is repeated until an useful conclusion is made.
• This process is also called “data-driven” inference since input data is used to guide the direction
of the inference process.
Forward chaining
• Idea: fire any rule whose premises are satisfied in the KB,
• add its conclusion to the KB, until query is found
Forward chaining algorithm
Forward chaining example
Proof of completeness
• FC derives every atomic sentence that is entailed by KB

1. FC reaches a fixed point where no new atomic sentences are derived
2. Consider the final state as a model m, assigning true/false to symbols
3. Every clause in the original KB is true in m
a1 ∧ … ∧ ak ⇒ b
Hence m is a model of KB
If KB╞ q, q is true in every model of KB, including m
Backward chaining:-
•It is the process of selection rules by

matching the RHS
.
•Reasoning begins from the goal state.
•The LHS of a selected rule becomes a sub

goal which in turn causes another sub goal
to be achieved and so on until facts are
found to match the lowest sub goal.
•This process is also called “goal-driven”

inference.
Backward chaining
Idea: work backwards from the query q:

to prove q by BC,
check if q is known already, or
prove by BC all premises of some rule concluding q
Avoid loops: check if new sub-goal is already on the goal stack

Avoid repeated work: check if new sub-goal has already been proved true, or has already failed
Backward chaining example
Forward vs. backward chaining
• FC is data-driven, automatic, unconscious processing,

• e.g., object recognition, routine decisions
• May do lots of work that is irrelevant to the goal

• BC is goal-driven, appropriate for problem-solving,
• e.g., Where are my keys? How do I get into a PhD program?
• Complexity of BC can be much less than linear in size of KB

Inference-based agents in the wumpus world
A wumpus-world agent using propositional logic:
¬P1,1
¬W1,1
Bx,y ⇔ (Px,y+1 ∨ Px,y-1 ∨ Px+1,y ∨ Px-1,y)
Sx,y ⇔ (Wx,y+1 ∨ Wx,y-1 ∨ Wx+1,y ∨ Wx-1,y)
W1,1 ∨ W1,2 ∨ … ∨ W4,4
¬W1,1 ∨ ¬W1,2
¬W1,1 ∨ ¬W1,3
…
⇒ 64 distinct proposition symbols, 155 sentences

Summary
• Logical agents apply inference to a knowledge base to derive new information and make decisions
• Basic concepts of logic:
• syntax: formal structure of sentences
• semantics: truth of sentences w.r.t models
• entailment: necessary truth of one sentence given another
• inference: deriving sentences from other sentences
• soundness: derivations produce only entailed sentences
• completeness: derivations can produce all entailed sentences
• Wumpus world requires the ability to represent partial and negated information, reason by cases, etc.
• Resolution is complete for propositional logic
Forward, backward chaining are linear-time, complete for Horn clauses
• Propositional logic lacks expressive power

AI PDF

Uploaded by

Copyright:

Available Formats

AI PDF

Uploaded by

Document Information

Original Description:

Original Title

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

AI PDF

Uploaded by

Copyright:

Available Formats

Introduction

Homo sapiens—man the wise!

• AI currently encompasses a huge variety of subfields, ranging from the

• AI is relevant to any intellectual task; it is truly a universal field.

Systems that think like Systems that think rationally

Systems that act like humans Systems that act rationally

• Predicted that by 2000, a machine might have a 30% chance of

• Anticipated all major arguments against AI in following 50 years.

"Computing Machinery and Intelligence" is a seminal paper written

2. Knowledge Representation: To store what it knows or hears;

5. Computer Vision: To perceive objects;

6. Robotics: To manipulate objects and move about;

• 1960’s "cognitive revolution": information-processing

• Three ways to do this:

• A key idea in cognitive psychology was that by

• Several Greek schools developed various forms of logic:

2. What is the purpose of thinking? What thoughts should I have?

• Rational behavior: doing the right thing

• The right thing: that which is expected to maximize goal

• Doesn't necessarily involve thinking – e.g., blinking reflex –

• Philosophy: Logic, methods of reasoning, mind as physical

• But when it comes to AI, Watson is just the tip of the

• AI has been used in a wide range of fields including medical

• Artificial neural networks are used as clinical decision

• Other tasks in medicine that can potentially be performed

• Similar techniques may be used in answering machines of call centres ,

• The AOD also uses artificial intelligence in speech recognition

• The Artificial Intelligence supported Design of Aircraft [1], or AIDA,

• 11 News and publishing

• Agents and environments

• An agent is anything that can be viewed as perceiving its

• Human agent: eyes, ears, and other organs for sensors;

• Robotic agent: cameras and infrared range finders for

• Software agent ( SoftBot : software robot ) :-

• Percept :- refers to an agents perceptual input at any given

• Percept sequence :- refers to the complete history of what an

• Action:- an agent’s choice of action at any given instant can

• Agent function:- an agent’s behavior is described by the agent

• The agent function maps from percept histories to actions: [f: P* A]

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

• An agent should strive to "do the right thing", based on what it

Rationality at any given time depends on :

• Agent’s prior knowledge of the environment.

• Rationality ; which is distinct from omniscience (all-knowing with infinite

• An agent is completely specified by the agent function which

• An agent has some internal data structures that is updated as

• The data structures are operated on by the agent’s decision

• An agent consists of an architecture plus a program that runs on

• In designing intelligent systems , there are 4 main factors to

• Task environments are problems to which rational agents are

• Consider, e.g., the task of designing an automated taxi

• Performance measure: Safe, fast, legal, comfortable trip,

• Agent: Medical diagnosis system

• Sensors: Keyboard (entry of symptoms, findings, patient's answers)

• Agent: Part-picking robot

• Agent: Interactive English tutor

1. Fully observable vs. Partially observable

2. Deterministic vs. Stochastic