UNIT I: Introduction

Introduction to AI – AI Definition, The Foundations of AI, The History of AI, The State of
the Art
Intelligent Agents – Agents and Environment, The Concept of Rationality, The Nature of
Environments, The Structure of Agents
Solving Problems by Searching – Problem-Solving Agents, Searching for Solutions,
Uninformed Search Strategies, Heuristic Search Strategies, Heuristic Functions

Artificial Intelligence is defined in four ways, each offering a different perspective on what it
means to be "intelligent." These definitions can be categorized by whether they focus on
thinking versus acting and whether the goal is to mimic humanity versus achieving
rationality.

A. Thinking Humanly: The Cognitive Modeling Approach

This approach is based on the famous Turing Test, proposed by Alan Turing in his 1950
paper, "Computing Machinery and Intelligence." The test defines intelligent behavior as a
machine's ability to exhibit human-level performance in a conversational setting, to the point
where a human interrogator cannot tell if they are conversing with a machine or another
human.

To pass the Turing Test, a machine would need to excel in several key areas:

 Natural Language Processing (NLP): To communicate successfully in a human

language.
 Knowledge Representation: To store and retrieve information effectively.
  Automated Reasoning: To use the stored information to answer questions and draw
new conclusions.
 Machine Learning: To adapt to new circumstances and detect patterns.

A "total Turing Test" would add a physical component, requiring the agent to interact with
and perceive objects in the world, which would involve Computer Vision and Robotics.

B. Thinking Rationally: The "Laws of Thought" Approach

This approach is rooted in the study of logic and the development of formal systems for
reasoning. The goal is to build intelligent systems that follow a process of "right thinking."

 Logicist Tradition: This school of thought within AI aims to use formal logic to
represent knowledge and derive new conclusions. For example, a system could use
formal logic to deduce that "Socrates is mortal" from the premises "All men are
mortal" and "Socrates is a man."
 Challenges: The main difficulty with this approach is that it is often hard to translate
real-world, informal knowledge into the precise formal language of logical notation.
Additionally, some problems can be solved without relying solely on logic.

C. Acting Humanly: The Turing Test Approach

This approach is based on the famous Turing Test, proposed by Alan Turing in his 1950
paper, "Computing Machinery and Intelligence." The test defines intelligent behavior as a
machine's ability to exhibit human-level performance in a conversational setting, to the point
where a human interrogator cannot tell if they are conversing with a machine or another
human.

To pass the Turing Test, a machine would need to excel in several key areas:

 Natural Language Processing (NLP): To communicate successfully in a human

language.
 Knowledge Representation: To store and retrieve information effectively.
 Automated Reasoning: To use the stored information to answer questions and draw
new conclusions.
 Machine Learning: To adapt to new circumstances and detect patterns.

A "total Turing Test" would add a physical component, requiring the agent to interact with
and perceive objects in the world, which would involve Computer Vision and Robotics.

D. Acting Rationally: The Rational Agent Approach

This approach is rooted in the study of logic and the development of formal systems for
reasoning. The goal is to build intelligent systems that follow a process of "right thinking."

 Logicist Tradition: This school of thought within AI aims to use formal logic to
represent knowledge and derive new conclusions. For example, a system could use
formal logic to deduce that "Socrates is mortal" from the premises "All men are
mortal" and "Socrates is a man."
  Challenges: The main difficulty with this approach is that it is often hard to translate
real-world, informal knowledge into the precise formal language of logical notation.
Additionally, some problems can be solved without relying solely on logic.

2. The Foundations of AI

AI is a modern field with deep roots in several older disciplines, which have provided the
necessary tools and ideas for its development.

 Philosophy: The concepts of the mind, the source of knowledge (empiricism vs.
rationalism), and the connection between knowledge and action are all philosophical
inquiries that directly inform AI. Key contributions include the formalization of logic
by Aristotle and the idea of the mind as a physical system.
 Mathematics: This discipline provides the formal tools for AI. Key contributions
include the development of algorithms, computability (can something be computed?),
and probability theory (for dealing with uncertainty).
 Psychology: The study of the human mind and behavior provides insights into how to
build intelligent systems. The shift from behaviorism (focused on stimulus-response)
to cognitive psychology (which models the mind's internal workings) was
particularly influential.
 Linguistics: The study of language structure and meaning provided the groundwork
for natural language processing (NLP). The development of formal language theory
by Noam Chomsky, for example, heavily influenced early AI.
 Computer Engineering: The invention of the modern computer in the mid-20th
century provided the essential hardware. Without the stored-program computer, AI
would be a purely theoretical field.
 Neuroscience: The study of the brain provides both inspiration and a source of data
for building AI. Concepts like neural networks and deep learning are directly inspired
by the structure of the human brain.

3. The History of AI

 Important research that laid the groundwork for AI:

 In 1931, Goedel layed the foundation of Theoretical Computer Science1920-30s: He
published the first universal formal language and showed that math itself is either
flawed or allows for unprovable but true statements.
 In 1936, Turing reformulated Goedel’s result and church’s extension thereof.

 In 1956, John McCarthy coined the term "Artificial Intelligence" as the topic of the
Dartmouth Conference, the first conference devoted to the subject.

 In 1957, The General Problem Solver (GPS) demonstrated by Newell, Shaw &
Simon
 In 1958, John McCarthy (MIT) invented the Lisp language.
 In 1959, Arthur Samuel (IBM) wrote the first game-playing program, for checkers, to
achieve sufficient skill to challenge a world champion.
 In 1963, Ivan Sutherland's MIT dissertation on Sketchpad introduced the idea of
interactive graphics into computing.
  In 1966, Ross Quillian (PhD dissertation, Carnegie Inst. of Technology; now CMU)
demonstrated semantic nets
 In 1967, Dendral program (Edward Feigenbaum, Joshua Lederberg, Bruce Buchanan,
Georgia Sutherland at Stanford) demonstrated to interpret mass spectra on organic
chemical compounds. First successful knowledge-based program for scientific
reasoning.
 In 1967, Doug Engelbart invented the mouse at SRI
 In 1968, Marvin Minsky & Seymour Papert publish Perceptrons, demonstrating limits
of simple neural nets.
 In 1972, Prolog developed by Alain Colmerauer.
 In Mid 80’s, Neural Networks become widely used with the Backpropagation
algorithm (first described by Werbos in 1974).
 1990, Major advances in all areas of AI, with significant demonstrations in machine
learning, intelligent tutoring, case-based reasoning, multi-agent planning, scheduling,
uncertain reasoning, data mining, natural language understanding and translation,
vision, virtual reality, games, and other topics.
 In 1997, Deep Blue beats the World Chess Champion Kasparov
 In 2002,iRobot, founded by researchers at the MIT Artificial Intelligence Lab,
introduced Roomba, a vacuum cleaning robot. By 2006, two million had been sold.

4. The State of the Art

AI has achieved a level of performance that was once considered science fiction.

 Robotics: AI-powered robots are used in manufacturing, medicine, and even homes.
Autonomous vehicles are an advanced application of AI in the real world. The Mars
Exploration Rover mentioned in the textbook is a prime example of an autonomous
robot.
 Game-Playing: AI has long surpassed human performance in games. IBM's Deep
Blue defeated world chess champion Garry Kasparov in 1997. More recently,
Google's AlphaGo defeated the world champion of Go, a game far more complex
than chess, in 2016. The solution of the game of checkers is another landmark
mentioned in the book.
 Natural Language Processing: Modern AI can perform high-quality machine
translation, understand human speech (e.g., Siri, Alexa), and extract information from
vast amounts of text.
 Computer Vision: Systems can now recognize faces, identify objects in images, and
power surveillance and security systems.

 Web Search and Recommender Systems: The search engines we use daily rely on
AI to rank pages, predict search queries, and provide personalized results.
Recommender systems (e.g., on Netflix and Amazon) use AI to suggest products and
content.
 Machine Learning: The field has seen considerable theoretical progress, with a focus
on modern learning algorithms.
  Vision: Computer vision has been a major area of progress, often incorporating
neurophysiological evidence into computational models.

Application of AI:
 AI algorithms have attracted close attention of researchers and have also been applied
successfully to solve problems in engineering. Nevertheless, for large and complex
problems, AI algorithms consume considerable computation time due to stochastic
feature of the search approaches
 Business; financial strategies
 Engineering: check design, offer suggestions to create new product, expert systems
for all engineering problems
 Manufacturing: assembly, inspection and maintenance
 Medicine: monitoring, diagnosing
 Education: in teaching
 Fraud detection
 Object identification
 Information retrieval
 Space shuttle scheduling
Agents and Environment

Fig 1: Agents and Environments

Agent: An Agent is anything that can be viewed as perceiving its environment through
sensors and acting upon that environment through actuators.
 A human agent has eyes, ears, and other organs for sensors and hands, legs, mouth,
and other body parts for actuators.
 A robotic agent might have cameras and infrared range finders for sensors and
various motors for actuators.
 A software agent receives keystrokes, file contents, and network packets as sensory
inputs and acts on the environment by displaying on the screen, writing files, and
sending network packets.
Percept: We use the term percept to refer to the agent's perceptual inputs at any given
instant.
Percept Sequence: An agent's percept sequence is the complete history of everything the
agent has ever perceived.
Agent function: Mathematically speaking, we say that an agent's behavior is described by
the agent function that maps any given percept sequence to an action.
Agent program: Internally, the agent function for an artificial agent will be implemented by
an agent program. It is important to keep these two ideas distinct. The agent function is an
abstract mathematical description; the agent program is a concrete implementation, running
on the agent architecture. To illustrate these ideas, we will use a very simple example-the
vacuum-cleaner world shown in Fig 2. This particular world has just two locations: squares A
and B. The vacuum agent perceives which square it is in and whether there is dirt in the
square. It can choose to move left, move right, suck up the dirt, or do nothing. One very
simple agent function is the following: if the current square is dirty, then suck, otherwise
move to the other square. A partial tabulation of this agent function is shown in Fig 3.

Fig 2: A vacuum-cleaner world with just two locations.

Fig 3: Partial tabulation of a simple agent function for the example: vacuum-cleaner world
shown in the Fig 2

Fig 3(i): The REFLEX-VACCUM-AGENT program is invoked for each new percept
(location, status) and returns an action each time
THE CONCEPT OF RATIONALITY
A rational agent is an AI that consistently "does the right thing" to achieve the best possible
outcome. This is defined not by the agent's internal state or beliefs, but by the consequences
of its actions on the environment.
  Doing the Right Thing: The "right thing" is determined by a performance measure
that evaluates the desirability of the sequence of environment states generated by the
agent's actions.
 Performance Measure: This measure is designed by the developer to evaluate the
agent's success. It should be based on the desired state of the environment, not on
how the agent thinks it is performing. This prevents an agent from "deluding" itself
into thinking it's successful when it isn't (e.g., the "sour grapes" phenomenon).

Designing an Effective Performance Measure

Creating a good performance measure is crucial and can be challenging. It's essential to
define what you actually want from the environment.

 Bad Example: If a vacuum cleaner agent's performance is measured by the amount of

dirt cleaned up in eight hours, a "rational" agent might repeatedly clean and then
dump dirt to maximize its score. This is not the desired behavior.
 Good Example: A better performance measure would be based on the cleanliness of
the floor over time. For instance, the agent could be awarded a point for each clean
square at each time step. This incentivizes the agent to keep the floor clean, which is
the actual goal.

The rationality of an agent's actions at any given moment is not a fixed quality; it's dependent
on four key factors:

1. The Performance Measure: The success criteria that define what is considered
"good" behavior.
2. Prior Knowledge: The information the agent already has about its environment
before it starts operating.
3. Available Actions: The set of actions the agent can choose from at any given time.
4. Percept Sequence: The complete history of everything the agent has perceived so far.

Defining a Rational Agent

A rational agent is an agent that, for every possible sequence of perceptions it has received,
chooses the action that is expected to maximize its performance measure. This decision is
made based on the evidence provided by its percept sequence and its built-in knowledge.

Example: The Vacuum-Cleaner Agent �

The provided text uses a simple vacuum-cleaner agent to illustrate this definition. The agent's
task is to clean a two-square environment (A and B).

 Is it Rational? The text claims that the agent is rational under a specific set of
circumstances:
o Performance Measure: One point is awarded for each clean square at each
time step.
o Knowledge: The agent knows the geography (two squares) but not the initial
dirt distribution or its starting location.
o Actions: The only actions available are Left, Right, and Suck.
o Percepts: The agent knows its location and whether the current square is dirty.
 Given these conditions, the agent's simple rule—Suck if dirty, otherwise move to the
other square—is considered rational because it will achieve the highest possible
expected score over time.

 When is it NOT Rational? The same agent can become irrational if the
circumstances change:
o If there's a penalty for moving, the agent's continuous oscillation after the
environment is clean would make it irrational. A better agent would stop
moving.
o If dirt can reappear, the agent's simple strategy of moving to the other square
might be insufficient. It would need to periodically check for new dirt.
o If the geography is unknown, the agent would need to explore its environment
rather than just switching between squares A and B.

Specifying the Task Environment

The PEAS (Performance, Environment, Actuators, Sensors) description is a method for
formally specifying an intelligent agent's task environment. It is a critical first step in
designing any agent.

1. Components of a PEAS Description

 Performance Measure: This defines the criteria for the agent's success. It should be
based on the desired state of the environment, not on the agent's internal behavior. For
example, for a taxi driver, a good performance measure would include safety, speed,
legality, and passenger comfort.
 Environment: This refers to the real or virtual world in which the agent operates. It
includes everything the agent can potentially interact with. For a taxi, this would be
roads, other traffic, pedestrians, and customers. The complexity of the environment is
a major factor in the design of the agent.
 Actuators: These are the mechanisms an agent uses to act upon the environment. For
a human, these are hands, legs, etc. For an automated taxi, they would include the
steering wheel, accelerator, brake, horn, and a display.
 Sensors: These are the tools the agent uses to perceive the environment. For a human,
these are eyes, ears, etc. For a taxi, they would include cameras, sonar, a speedometer,
and a GPS.

Examples of PEAS Descriptions

Properties of Task Environments
Task environments can be categorized along several dimensions, which largely determine the
appropriate agent design.

 Fully vs. Partially Observable:

o Fully Observable: The agent's sensors give it access to the complete state of
the environment at all times. A crossword puzzle is an example.
o Partially Observable: The agent's sensors only provide a partial view of the
environment. A taxi driver cannot see what other drivers are thinking.
 Single vs. Multi-agent:
o Single-agent: The agent operates alone in the environment (e.g., solving a
crossword puzzle).
o Multi-agent: The environment contains other agents whose behavior affects
the agent's performance. This can be competitive (e.g., chess) or cooperative
(e.g., avoiding collisions while driving).
 Deterministic vs. Stochastic:
o Deterministic: The next state of the environment is completely determined
by the current state and the agent's action.
o Stochastic: There is an element of uncertainty or randomness in the
outcomes. Most real-world situations, like taxi driving, are stochastic due to
unpredictable factors.
 Episodic vs. Sequential:
o Episodic: The agent's experience is divided into independent, self-contained
episodes. The current action has no impact on future episodes (e.g., an agent
classifying defective parts on an assembly line).
o Sequential: The current action has a long-term impact on the environment
and future actions. Chess and taxi driving are sequential.
 Static vs. Dynamic:
o Static: The environment does not change while the agent is deciding on an
action.
o Dynamic: The environment changes over time, even while the agent is
deliberating. A taxi driving environment is dynamic as other cars are
 constantly moving. A semidynamic environment is one where the agent's
performance score changes over time, even if the environment itself does not
change, like chess with a clock.
 Discrete vs. Continuous: This applies to the state of the environment, time, percepts,
and actions.
o Discrete: The state space is finite (e.g., chess).
o Continuous: The values can be on a continuous scale (e.g., the speed and
location of a taxi).
 Known vs. Unknown: This refers to the agent's knowledge of the environment's
"laws of physics" or rules.
o Known: The outcomes of all actions are given to the agent.
o Unknown: The agent must learn how the environment works through
experience.

THE STRUCTURE OF AGENTS

An agent program is the concrete implementation of the agent function, which maps a
sequence of percepts to an action. This program runs on a physical computing device called
the architecture. The relationship is summarized as:

Agent = Architecture + Program

The key difference is that the agent program takes the current percept as input, while the
agent function considers the entire history of percepts. If the agent needs to rely on past
percepts, the program must have an internal memory to store them.

Basic Types of Agent Programs

To overcome the limitations of the table-driven approach, AI research has developed more
sophisticated agent program designs. Here are four fundamental types, each adding a layer of
complexity and capability.
1. Simple Reflex Agents

These are the simplest agents, making decisions based only on the current percept. They use
a set of condition-action rules (e.g., if car-in-front-is-braking then initiate-braking) to map
percepts directly to actions.

 Strengths: They are simple and efficient.

 Weaknesses: They can only work in fully observable environments. They can easily
fall into infinite loops in partially observable environments because they lack
memory. A randomized action can sometimes help them escape a loop.

2. Model-Based Reflex Agents

To handle partial observability, these agents maintain an internal state that reflects the
unobserved parts of the environment. This internal state is updated using a model of the
world which contains knowledge about:

 How the world evolves independently of the agent's actions.

 How the agent's actions affect the world. By combining the current percept with its
internal state, the agent can create a "best guess" of the world's current state and then
use condition-action rules to decide on an action.

3. Goal-Based Agents

These agents are more flexible than reflex agents because their actions are guided by explicit
goals—descriptions of desirable future states.

 How it Works: They use their world model to determine a sequence of actions that
will lead to a goal state. This often involves search or planning algorithms.
 Advantages: They are more flexible than reflex agents because their knowledge is
explicitly represented and can be easily modified. For instance, changing the
destination of a taxi is as simple as updating the goal.
4. Utility-Based Agents

Goals provide a binary distinction between "happy" and "unhappy" states, but they don't
allow for a nuanced comparison of different outcomes. Utility-based agents use a utility
function to provide a more general performance measure, specifying a degree of preference
for different states.

 How it Works: These agents choose the action that is expected to maximize their
expected utility. This approach is essential for making rational decisions in situations
with conflicting goals (e.g., speed vs. safety) or uncertain outcomes.

5. Learning Agents: The Path to Improvement

A learning agent is an agent that can improve its own performance over time. It has four
main components:

 Performance Element: This is the core of the agent, responsible for selecting actions.
 Learning Element: This component is responsible for making improvements.
 Critic: This component provides feedback to the learning element, telling it how well
the agent is doing with respect to a fixed performance standard.
 Problem Generator: This component suggests actions that are designed to lead to
new and informative experiences, encouraging exploration over short-term
optimization.
This structure allows an agent to adapt to initially unknown environments and become more
competent through experience, moving beyond the limitations of its initial programming.
Introduction to Problem Solving, General problem solving
Problem solving is a process of generating solutions from observed data.
 a problem is characterized by a set of goals,
 a set of objects, and
 a set of operations.
These could be ill-defined and may evolve during problem solving.
Searching Solutions:
To build a system to solve a problem:
1. Define the problem precisely
2. Analyze the problem
3. Isolate and represent the task knowledge that is necessary to solve the problem
4. Choose the best problem-solving techniques and apply it to the particular problem.
Defining the problem as State Space Search:
1. The state space representation forms the basis of most of the AI methods.
2. Formulate a problem as a state space search by showing the legal problem states, the
legal operators, and the initial and goal states.
3. A state is defined by the specification of the values of all attributes of interest in the
world
4. An operator changes one state into the other; it has a precondition which is the value
of certain attributes prior to the application of the operator, and a set of effects, which
are the attributes altered by the operator
5. The initial state is where you start
6. The goal state is the partial description of the solution
Formal Description of the problem:
1. 1. Define a state space that contains all the possible configurations of the relevant
objects.
2. 2. Specify one or more states within that space that describe possible situations from
which the problem solving process may start ( initial state)
3. 3. Specify one or more states that would be acceptable as solutions to the problem. (
goal states)
4. Specify a set of rules that describe the actions (operations) available
State-Space Problem Formulation:
Example: A problem is defined by four items:
1. initial state e.g., "at Arad‖
2. actions or successor function : S(x) = set of action–state pairs
e.g., S(Arad) = {<Arad Zerind, Zerind>, … }
3. goal test (or set of goal states)
e.g., x = "at Bucharest‖, Checkmate(x)
4. path cost (additive)
e.g., sum of distances, number of actions executed, etc.
c(x,a,y) is the step cost, assumed to be ≥ 0
A solution is a sequence of actions leading from the initial state to a goal state
Example: 8-queens problem

1. Initial State: Any arrangement of 0 to 8 queens on board.

2. Operators: add a queen to any square.
3. Goal Test: 8 queens on board, none attacked.
4. Path cost: not applicable or Zero (because only the final state counts, search cost
might be of interest).
State Spaces versus Search Trees
 State Space
o Set of valid states for a problem
o Linked by operators
o e.g., 20 valid states (cities) in the Romanian travel problem
 Search Tree
– Root node = initial state
– Child nodes = states that can be visited from parent
– Note that the depth of the tree can be infinite
• E.g., via repeated states
– Partial search tree
• Portion of tree that has been expanded so far
– Fringe
• Leaves of partial search tree, candidates for expansion
Search trees = data structure to search state-space
Properties of Search Algorithms
Which search algorithm one should use will generally depend on the problem domain.
There are four important factors to consider:
1. Completeness – Is a solution guaranteed to be found if at least one solution exists?
2. Optimality – Is the solution found guaranteed to be the best (or lowest cost) solution if
there exists more than one solution?
3. Time Complexity – The upper bound on the time required to find a solution, as a
function of the complexity of the problem.
4. Space Complexity – The upper bound on the storage space (memory) required at any
point during the search, as a function of the complexity of the problem.

General problem solving, Water-jug problem, 8-puzzle problem

General Problem Solver:
The General Problem Solver (GPS) was the first useful AI program, written by Simon, Shaw,
and Newell in 1959. As the name implies, it was intended to solve nearly any problem.
Newell and Simon defined each problem as a space. At one end of the space is the starting
point; on the other side is the goal. The problem-solving procedure itself is conceived as a set
of operations to cross that space, to get from the starting point to the goal state, one step at a
time.
The General Problem Solver, the program tests various actions (which Newell and Simon
called operators) to see which will take it closer to the goal state. An operator is any activity
that changes the state of the system. The General Problem Solver always chooses the
operation that appears to bring it closer to its goal.
Example: Water Jug Problem
Consider the following problem:
A Water Jug Problem: You are given two jugs, a 4-gallon one and a 3-gallon one, a pump
which has unlimited water which you can use to fill the jug, and the ground on which water
may be poured. Neither jug has any measuring markings on it. How can you get exactly 2
gallons of water in the 4-gallon jug?
State Representation and Initial State :
We will represent a state of the problem as a tuple (x, y) where x represents the amount of
water in the 4-gallon jug and y represents the amount of water in the 3-gallon jug. Note 0 ≤x≤
4, and 0 ≤y ≤3. Our initial state: (0, 0)
Goal Predicate - state = (2, y) where 0≤ y≤ 3.
Operators -we must defi ne a set of operators that will take us from one state to another:
1. Fill 4-gal jug (x,y) → (4,y)
x<4
2. Fill 3-gal jug (x,y) → (x,3)
y<3
3. Empty 4-gal jug on ground (x,y) → (0,y)
x>0
4. Empty 3-gal jug on ground (x,y) → (x,0)
y>0
5. Pour water from 3-gal jug to 4- (x,y) →! (4, y - (4 - x))
gal jug 0 < x+y 4 and y > 0
6. Pour water from 4-gal jug to 3- (x,y) → (x - (3-y), 3)
gal-jug 0 < x+y 3 and x > 0
7. Pour all of water from 3-gal jug (x,y) → (x+y, 0)
into 4-gal jug 0 < x+y 4 and y 0
8. Pour all of water from 4-gal jug (x,y) → (0, x+y)
 into 3-gal jug 0 < x+y 3 and x 0
Through Graph Search, the following solution is found :

Gals in 4-gal jug Gals in 3-gal jug Rule Applied

0 0
4 0 1. Fill 4
1 3 6. Pour 4 into 3
1 0 4. Empty 3
0 1 8. Pour all of 4 into 3
4 1 1. Fill 4
2 3 6. Pour into 3

Control strategies
Control Strategies means how to decide which rule to apply next during the process of
searching for a solution to a problem.
Requirement for a good Control Strategy
1. It should cause motion
In water jug problem, if we apply a simple control strategy of starting each time from the top
of rule list and choose the first applicable one, then we will never move towards solution.
2. It should explore the solution space in a systematic manner
If we choose another control strategy, let us say, choose a rule randomly from the applicable
rules then definitely it causes motion and eventually will lead to a solution. But one may
arrive to same state several times. This is because control strategy is not systematic.
Systematic Control Strategies (Blind searches):

Breadth First Search

Let us discuss these strategies using water jug problem. These may be applied to any search
problem.
Construct a tree with the initial state as its root.
Generate all the offspring of the root by applying each of the applicable rules to the initial
state.

Now for each leaf node, generate all its successors by applying all the rules that are
appropriate.
8 Puzzle Problem
The 8 puzzle consists of eight numbered, movable tiles set in a 3x3 frame. One cell of the
frame is always empty thus making it possible to move an adjacent numbered tile into the
empty cell. Such a puzzle is illustrated in following diagram.
The program is to change the initial configuration into the goal configuration. A solution to
the problem is an appropriate sequence of moves, such as ―move tiles 5 to the right, move tile
7 to the left, move tile 6 to the down, etc‖.
Solution:
To solve a problem using a production system, we must specify the global database the rules,
and the control strategy. For the 8 puzzle problem that correspond to these three components.
These elements are the problem states, moves and goal. In this problem each tile
configuration is a state. The set of all configuration in the space of problem states or the
problem space, there are only 3, 62,880 different configurations o the 8 tiles and blank space.
Once the problem states have been conceptually identified, we must construct a computer
representation, or description of them . this description is then used as the database of a
production system. For the 8-puzzle, a straight forward description is a 3X3 array of matrix
of numbers. The initial global database is this description of the initial problem state.
Virtually any kind of data structure can be used to describe states.

A move transforms one problem state into another state. The 8-puzzle is conveniently
interpreted as having the following for moves. Move empty space (blank) to the left, move
blank up, move blank to the right and move blank down,. These moves are modeled by
production rules that operate on the state descriptions in the appropriate manner.
The rules each have preconditions that must be satisfied by a state description in order for
them to be applicable to that state description. Thus the precondition for the rule associated
with ―move blank up‖ is derived from the requirement that the blank space must not already
be in the top row.
The problem goal condition forms the basis for the termination condition of the production
system. The control strategy repeatedly applies rules to state descriptions until a description
of a goal state is produced. It also keeps track of rules that have been applied so that it can
compose them into sequence representing the problem solution. A solution to the 8-puzzle
problem is given in the following figure.

Example:- Depth – First – Search traversal and Breadth - First - Search traversal
for 8 – puzzle problem is shown in following diagrams.
Exhaustive Searches, BFS and DFS
Search is the systematic examination of states to find path from the start/root state to the goal
state.
Many traditional search algorithms are used in AI applications. For complex problems, the
traditional algorithms are unable to find the solution within some practical time and space
limits. Consequently, many special techniques are developed; using heuristic functions. The
algorithms that use heuristic functions are called heuristic algorithms. Heuristic algorithms
are not really intelligent; they appear to be intelligent because they achieve better
performance.
Heuristic algorithms are more efficient because they take advantage of feedback from the
data to direct the search path.
Uninformed search:Also called blind, exhaustive or brute-force search, uses no information
about the problem to guide the search and therefore may not be very efficient.
Informed Search: Also called heuristic or intelligent search, uses information about the
problem to guide the search, usually guesses the distance to a goal state and therefore
efficient, but the search may not be always possible.
Uninformed Search Methods
1. Breadth-first Search
2. Depth-first Search
3. Depth-limited Search
4. Iterative deepening depth-first search
5. Uniform cost search
6. Bidirectional Search

Breadth- First -Search

Consider the state space of a problem that takes the form of a tree. Now, if we search the goal
along each breadth of the tree, starting from the root and continuing up to the largest depth,
we call it breadth first search.

Algorithm:
1. Create a variable called NODE-LIST and set it to initial state
2. Until a goal state is found or NODE-LIST is empty do
a. Remove the first element from NODE-LIST and call it E. If NODE-LIST was
empty, quit
b. For each way that each rule can match the state described in E do:
i. Apply the rule to generate a new state
ii. If the new state is a goal state, quit and return this state
iii. Otherwise, add the new state to the end of NODE-LIST
BFS illustrated
Step 1: Initially fringe contains only one node corresponding to the source state A.

FRINGE: A
Step 2: A is removed from fringe. The node is expanded, and its children B and C are
generated. They are placed at the back of fringe.
FRINGE: B C
Step 3: Node B is removed from fringe and is expanded. Its children D, E are generated and
put at the back of fringe.

FRINGE: C D E
Step 4: Node C is removed from fringe and is expanded. Its children D and G are added to
the back of fringe.

FRINGE: D E D G
Step 5: Node D is removed from fringe. Its children C and F are generated and added to the
back of fringe.
FRINGE: E D G C F
Step 6: Node E is removed from fringe. It has no children.

FRINGE: D G C F
Step 7: D is expanded; B and F are put in OPEN.

FRINGE: G C F B F

Step 8: G is selected for expansion. It is found to be a goal node. So the algorithm returns the
path A C G by following the parent pointers of the node corresponding to G. The algorithm
terminates.
Breadth first search is:
 One of the simplest search strategies
 Complete. If there is a solution, BFS is guaranteed to find it.
 If there are multiple solutions, then a minimal solution will be found
 The algorithm is optimal (i.e., admissible) if all operators have the same cost.
Otherwise, breadth first search finds a solution with the shortest path length.
 Time complexity : O(bd )
 Space complexity : O(bd)
 Optimality :Yes
o b - branching factor(maximum no of successors of any node),
o d – Depth of the shallowest goal node
 o Maximum length of any path (m) in search space
Advantages: Finds the path of minimal length to the goal.
Disadvantages:
 Requires the generation and storage of a tree whose size is exponential the depth of
the shallowest goal node.
 The breadth first search algorithm cannot be effectively used unless the search space
is quite small.
Depth- First- Search
We may sometimes search the goal along the largest depth of the tree, and move up only
when further traversal along the depth is not possible. We then attempt to find alternative
offspring of the parent of the node (state) last visited. If we visit the nodes of a tree using the
above principles to search the goal, the traversal made is called depth first traversal and
consequently the search strategy is called depth first search.
Algorithm:
1. Create a variable called NODE-LIST and set it to initial state
2. Until a goal state is found or NODE-LIST is empty do
a. Remove the first element from NODE-LIST and call it E. If NODE-LIST was
empty, quit
b. For each way that each rule can match the state described in E do:
i. Apply the rule to generate a new state
ii. If the new state is a goal state, quit and return this state
iii. Otherwise, add the new state in front of NODE-LIST
DFS illustrated

Step 1: Initially fringe contains only the node for A.

FRINGE: A
Step 2: A is removed from fringe. A is expanded and its children B and C are put in front of
fringe.

FRINGE: B C
Step 3: Node B is removed from fringe, and its children D and E are pushed in front of
fringe.

FRINGE: D E C
Step 4: Node D is removed from fringe. C and F are pushed in front of fringe.

FRINGE: C F E C
Step 5: Node C is removed from fringe. Its child G is pushed in front of fringe.

FRINGE: G F E C
Step 6: Node G is expanded and found to be a goal node.
FRINGE: G F E C
The solution path A-B-D-C-G is returned and the algorithm terminates.
Depth first search is:
1. The algorithm takes exponential time.
2. If N is the maximum depth of a node in the search space, in the worst case the
algorithm will take time O(bd).
3. The space taken is linear in the depth of the search tree, O(bN).
Note that the time taken by the algorithm is related to the maximum depth of the search tree.
If the search tree has infinite depth, the algorithm may not terminate. This can happen if the
search space is infinite. It can also happen if the search space contains cycles. The latter case
can be handled by checking for cycles in the algorithm. Thus Depth First Search is not
complete.

Depth-Limited Search
• A depth-limited search algorithm is similar to depth-first search with a predetermined
limit.
• Depth-limited search can solve the drawback of the infinite path in the Depth-first
search.
• In this algorithm, the node at the depth limit will treat as it has no successor nodes
further.

Algorithm
Procedure DLS(node, goal, limit):
if node == goal then
return "SUCCESS"
else if limit == 0 then
return "CUTOFF"
else
cutoff_occurred ← false
for each child in Expand(node) do
result ← DLS(child, goal, limit - 1)
if result == "CUTOFF" then
cutoff_occurred ← true
else if result == "SUCCESS" then
return "SUCCESS"
end for
 if cutoff_occurred then
return "CUTOFF"
else
return "FAILURE"

Example
Suppose we want to find a path in a graph using DLS with limit = 2:
A
/|\
B C D
/\
E F

 Start at A.
 Depth limit = 2.
 Possible nodes explored: A → {B, C, D} → {E, F} (up to depth 2).
 If goal = E, DLS finds it.
 If goal = G (deeper), returns CUTOFF.

Properties
 Completeness: No (unless depth limit ≥ depth of solution).
 Optimality: No (may find a suboptimal solution).
 Time complexity: O(bl)
o where b = branching factor, l = depth limit.
 Space complexity: O(bl) (linear in depth).

Iterative deepening depth-first Search (IDDFS)

• The iterative deepening algorithm is a combination of DFS and BFS algorithms.
• This search algorithm finds out the best depth limit and does it by gradually
increasing the limit until a goal is found.

Algorithm
Procedure IDDFS(start, goal, max_depth):
for depth from 0 to max_depth do
result ← DLS(start, goal, depth)
if result == "SUCCESS" then
return "SUCCESS"
return "FAILURE"

Procedure DLS(node, goal, limit):

if node == goal then
return "SUCCESS"
else if limit == 0 then
return "CUTOFF"
else
cutoff_occurred ← false
for each child in Expand(node) do
result ← DLS(child, goal, limit - 1)
if result == "SUCCESS" then
 return "SUCCESS"
else if result == "CUTOFF" then
cutoff_occurred ← true
if cutoff_occurred then
return "CUTOFF"
else
return "FAILURE"
Properties
• Completeness: This algorithm is complete is if the branching factor is finite.
• Time Complexity: Let's suppose b is the branching factor and depth is d then the
worst-case time complexity is O(bd).
• Space Complexity: The space complexity of IDDFS will be O(bd).
• Optimality: IDDFS algorithm is optimal if path cost is a non- decreasing function of
the depth of the node.
Advantages:
• It combines the benefits of BFS and DFS search algorithm in terms of fast search and
memory efficiency.
Disadvantages:
• The main drawback of IDDFS is that it repeats all the work of the previous phase.

Uniform Cost Search (UCS)

Uniform Cost Search is a path finding algorithm that expands the least cost node first,
ensuring that the path to the goal node has the minimum cost. Unlike other search algorithms
like Breadth-First Search (BFS), UCS takes into account the cost of each path, making it
suitable for weighted graphs where each edge has a different cost.

Key Concepts of Uniform Cost Search

• Priority Queue: UCS uses a priority queue to store nodes. The node with the lowest
cumulative cost is expanded first. This ensures that the search explores the most
promising paths first.
• Path Cost: The cost associated with reaching a particular node from the start node.
UCS calculates the cumulative cost from the start node to the current node and
prioritizes nodes with lower costs.
• Exploration: UCS explores nodes by expanding the least costly node first, continuing
this process until the goal node is reached. The path to the goal node is guaranteed to
be the least costly one.
• Termination: The algorithm terminates when the goal node is expanded, ensuring
that the first time the goal node is reached, the path is the optimal one.
How Does Uniform Cost Search Work?
• Initialization: UCS starts with the root node. It is added to the priority queue with a
cumulative cost of zero since no steps have been taken yet.
• Node Expansion: The node with the lowest path cost is removed from the priority
queue. This node is then expanded, and its neighbors are explored.
• Exploring Neighbors: For each neighbor of the expanded node, the algorithm
calculates the total cost from the start node to the neighbor through the current node.
If a neighbor node is not in the priority queue, it is added to the queue with the
calculated cost. If the neighbor is already in the queue but a lower cost path to this
neighbor is found, the cost is updated in the queue.
 • Goal Check: After expanding a node, the algorithm checks if it has reached the goal
node. If the goal is reached, the algorithm returns the total cost to reach this node and
the path taken.
• Repetition: This process repeats until the priority queue is empty or the goal is
reached.
Algorithm
Procedure UCS(start, goal):
create a priority queue PQ
insert (start, path_cost=0) into PQ
create an empty set Visited

while PQ is not empty do

(node, cost) ← PQ.remove_min() // remove node with smallest cost

if node == goal then

return "SUCCESS with cost = " + cost

if node not in Visited then

add node to Visited

for each child in Expand(node) do

new_cost ← cost + step_cost(node, child)
insert (child, new_cost) into PQ
end while

return "FAILURE"

Properties
 Completeness: Yes (if step costs ≥ 0).
 Optimality: Yes (returns the least-cost solution).
 Time complexity: O(b1+⌊C∗/ε⌋)
o where C* is cost of optimal solution, and ε is minimum step cost.
 Space complexity: Exponential in worst case (stores all frontier nodes).

Bidirectional Search
• Bidirectional search algorithm runs two simultaneous searches, one form initial state
called as forward-search and other from goal node called as backward-search, to find
the goal node.
• Bidirectional search replaces one single search graph with two small sub-graphs in
which one starts the search from an initial vertex and other starts from goal vertex.
The search stops when these two graphs intersect each other.
• Bidirectional search can use search techniques such as BFS, DFS, DLS, etc.
Algorithm
Procedure BDS(start, goal):
if start == goal then
return "SUCCESS"

create two queues:

Q_forward, Q_backward
create two visited sets:
 Visited_forward, Visited_backward

enqueue start into Q_forward

enqueue goal into Q_backward
add start to Visited_forward
add goal to Visited_backward

while Q_forward is not empty AND Q_backward is not empty do

// Expand forward frontier
node_f ← Q_forward.dequeue()
for each child in Expand(node_f) do
if child in Visited_backward then
return "SUCCESS - paths meet at " + child
if child not in Visited_forward then
add child to Visited_forward
enqueue child into Q_forward

// Expand backward frontier

node_b ← Q_backward.dequeue()
for each parent in Expand(node_b) do
if parent in Visited_forward then
return "SUCCESS - paths meet at " + parent
if parent not in Visited_backward then
add parent to Visited_backward
enqueue parent into Q_backward

return "FAILURE"
Properties
• Completeness: Bidirectional Search is complete if we use BFS in both searches.
• Time Complexity: Time complexity of bidirectional search using BFS is O(bd/2).
• Space Complexity: Space complexity of bidirectional search is O(bd/2).
• Optimal: Bidirectional search is Optimal
Advantages:
• Bidirectional search is fast.
• Bidirectional search requires less memory
Disadvantages:
• Implementation of the bidirectional search tree is difficult.
• In bidirectional search, one should know the goal state in advance.

INFORMED SEARCH STRATEGIES (Heuristics Search Techniques)

• Informed search strategy is one that uses problem-specific knowledge beyond the
definition of the problem itself—can find solutions more efficiently than can an
uninformed strategy.
• Greedy Best First Search
• A* search
Greedy best-first search
• Greedy best-first search' tries to expand the node that is closest to the goal, on the
grounds that this is likely to lead to a solution quickly. Thus, it evaluates nodes by
using just the heuristic function; that is, f (n) = h(n).
 • The algorithm is called "greedy― because at each step it tries to get as close to the goal
as it can.
• Greedy Best First search using hSLD finds a solution without ever expanding a node
that is not on the solution path; hence, its search cost is minimal.
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 on OPEN
b. Generate its successors
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.
Explanation
• It proceeds in steps, expanding one node at each step, until it generates a node that
corresponds to a goal state.
• At each step, it picks the most promising of the nodes that have so far been generated
but not expanded.
• It generates the successors of the chosen node, applies the heuristic function to them,
and adds them to the list of open nodes, after checking to see if any of them have been
generated before.
• By doing this check, we can guarantee that each node only appears once in the graph,
although many nodes may point to it as a successor.
• Heuristic function h(n)= estimated as cost of the cheapest path from the state at node
n to a goal state, i.e., h(n)=straight line distance
• hsld cannot be computed from the problem description itself
• it takes a certain amount of experience to know that hSLD is correlated with
actual road distances and is, therefore, a useful heuristic.
• Its search cost is minimal(Search cost is very low but not lowest). However, it is not
optimal.
The worst-case time and space complexity for the tree version is O(dm ), where m is the
maximum depth of the search space.
Example:
• Consider the following Romania map:
• Goal is to find a path from Arad to Bucharest.
 Values of hSLD—straight-line distances to Bucharest

Advantages:

GBFS finds a solution without ever expanding a node that is not on the solution path; hence,
its search cost is minimal.

Greedy best-first search' tries to expand the node that is closest to the goal, on the grounds
that this is likely to lead to a solution quickly.

Disadvantages:

Greedy best-first tree search is incomplete even in a finite state space. For Eg., Consider the
problem of getting from Iasi to Fagaras. The heuristic suggests that Neamt be expanded first
because it is closest to Fagaras, but it is a dead end.

A* search (Best-first search)

For Minimizing the total estimated solution cost

• It evaluates nodes by combining g(n), the cost to reach the node, and h(n), the cost to
get from the node to the goal: f(n) = g(n) + h(n) .
 • Since g(n) gives the path cost from the start node to node n, and h(n) is the estimated
cost of the cheapest path from n to the goal, we have f (n) = estimated cost of the
cheapest solution through n .

• If we are trying to find the cheapest solution, a reasonable thing to try first is the node
with the lowest value of f(n)=g(n) + h(n).

• The algorithm is identical to UNIFORM-COST-SEARCH except that A* uses g + h

instead of g.

Algorithm

1. Start with OPEN containing only initial node. Set that node’s g(n) value to 0, its h(n)
value to whatever it is, and its f(n) value to h+0 or h(n). Set CLOSED to empty list.

2. Until a goal node is found, repeat the following procedure:

I. If there are no nodes on OPEN, report failure.

II. Otherwise pick the node on OPEN with the lowest f(n) value. Call it
BESTNODE.

III. Remove it from OPEN. Place it in CLOSED.

IV. See if the BESTNODE is a goal state. If so exit and report a solution.

V. Otherwise, generate the successors of BESTNODE but do not set the

BESTNODE to point to them yet.

3. For each of the SUCCESSOR, do the following:

a. Set SUCCESSOR to point back to BESTNODE. (These backwards links will

make it possible to recover the path once a solution is found.)

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 the node
OLD. See whether it is cheaper to get to OLD via its current parent or
SUCCESSOR via BESTNODE by comparing their g values. If SUCCESSOR
is cheaper, then reset OLD’s parent to point to BESTNODE, record the new
cheaper path in g(OLD) and update f’(OLD).

d. If SUCCESSOR was not on OPEN, see if it is on CLOSED. If so, call the

node on CLOSED OLD and add OLD to the list of BESTNODE’s successors.

Check to see if the new path is better. If so, set the parent link and g and f’ values
appropriately.
We must propagate the improvements to OLD’s successors. OLD points to successors. Each
successor, in turn, points to its successors, and so forth until each branch terminates with a
node that either is still on OPEN or has no successors.

So to propagate the new cost downward, do a depth-first traversal of the tree starting at OLD,
changing each node’s g value (and thus also its f’ value), terminating each branch when you
reach either a node with no successor or a node to which an equivalent or better path has
already been found.

e. If SUCCESSOR was not already on either OPEN or CLOSED, then put it on OPEN
and add it to the list of BESTNODE’s successors.

Compute

f’(SUCCESSOR) = g(SUCCESSOR) + h’(SUCCESSOR)

Example: Please refer to the PPT

MEMORY-BOUNDED SEARCH (HEURISTIC SEARCH Technique)

 The simplest way to reduce memory requirements for A* is to adapt the idea of
ITERATIVE DEEPENING to the heuristic search context, resulting in the iterative-
deepening A* (IDA*) algorithm.

 The main difference between IDA* and standard iterative deepening is that the cutoff
used is the f-cost (g + h) rather than the depth; at each iteration, the cutoff value is
the smallest f-cost of any node that exceeded the cutoff on the previous iteration.

 IDA* is practical for many problems with unit step costs and avoids the substantial
overhead associated with keeping a sorted queue of nodes.

 Two memory bound algorithms are RBFS and MA*

RECURSIVE BEST FIRST SEARCH

 Similar to standard best-first search, but using only linear space.

 Its structure is similar to that of a recursive depth-first search, but rather than
continuing indefinitely down the current path, it uses the f-limit variable to
keep track of the f -value of the best alternative path available from any
ancestor of the current node.

 If the current node exceeds this limit, the recursion unwinds back to the
alternative path.

 As the recursion unwinds, RBFS replaces the f-value of each node along the
path with a backed-up value—the best f-value of its children. In this way,
RBFS remembers the f-value of the best leaf in the forgotten sub-tree and can
 therefore decide whether it's worth re-expanding the sub-tree at some time
later.

Algorithm

Procedure RBFS(node, f_limit):

if node is goal then

return (SUCCESS, f(node))

successors ← Expand(node)

if successors is empty then

return (FAILURE, ∞)

for each s in successors do

g(s) ← g(node) + step_cost(node, s)

f(s) ← max(g(s) + h(s), f(node)) // enforce non-decreasing f-values

while true do

best ← successor with lowest f-value

if f(best) > f_limit then

return (FAILURE, f(best))

alternative ← second lowest f-value among successors

result, f(best) ← RBFS(best, min(f_limit, alternative))

if result == SUCCESS then

return (SUCCESS, f(best))

Properties

1. RBFS is an optimal algorithm if the heuristic function h(n) is admissible.

2. Its space complexity is linear in the depth of the deepest optimal solution, but its time
complexity is rather difficult to characterize: it depends both on the accuracy of the
heuristic function and on how often the best path changes as nodes are
expanded.

3. IDA* and RBFS suffer from using too little memory. Between iterations, IDA*
retains only a single number: the current f-cost limit. RBFS retains more information
in memory, but it uses only linear space: even if more memory were available, RBFS
 has no way to make use of it. Because they forget most of what they have done, both
algorithms may end up re-expanding the same states many times over.

4. They suffer the potentially exponential increase in complexity associated with

redundant paths in graphs.

MA* (memory-bounded A*) and SMA* (simplified MA*)

To use all available memory, can use two algorithms :- MA* (memory-bounded A*) and
SMA* (simplified MA*).

1. SMA proceeds just like A*, expanding the best leaf until memory is full. At this
point, it cannot add a new node to the search tree without dropping an old one.

2. SMA* always drops the worst leaf node—the one with the highest f -value. Like
RBFS, SMA* then backs up the value of the forgotten node to its parent. In this way,
the ancestor of a forgotten sub-tree knows the quality of the best path in that sub-tree.

3. With this information, SMA* regenerates the sub-tree only when all other paths have
been shown to look worse than the path it has forgotten.

4. Another way of saying this is that, if all the descendants of a node n are forgotten,
then we will not know which way to go from n, but we will still have an idea of how
worthwhile it is to go anywhere from n.

5. SMA* expands the Best leaf and deletes the worst leaf.

6. To avoid selecting the same node for deletion and expansion, SMA* expands the
newest best leaf and deletes the oldest worst leaf.

7. These coincide when there is only one leaf, but in that case, the current search tree
must be a single path from root to leaf that fills all of memory.

8. If the leaf is not a goal node, then even if it is on an optimal solution path, that
solution is not reachable with the available memory. Therefore, the node can be
discarded exactly as if it had no successors.

9. SMA" is complete if there is any reachable solution—that is, if d, the depth of the
shallowest goal node, is less than the memory size (expressed in nodes).

10. It is optimal if any optimal solution is reachable; otherwise, it returns the best
reachable solution.

11. In practical terms, SMA* is a fairly robust choice for finding optimal solutions,
particularly when the state space is a graph, step costs are not uniform, and node
generation is expensive compared to the overhead of maintaining the frontier and the
explored set.

Example: Please refer to the PPT

Heuristic Functions

• A Heuristic is a function that, when applied to a state, returns a number that is an

estimate of the merit of the state, with respect to the goal.

• In other words, the heuristic tells approximately how far the state is from the goal
state*.

• Note the term ―approximately‖. Heuristics might underestimate or overestimate the

merit of a state.

• But for reasons which we will see, heuristics that only underestimate are very
desirable, and are called admissible.

• To shed light on the nature of heuristics in general, consider Heuristics for 8-puzzle

• Slide tiles vertically or horizontally into the empty space until the configuration
matches the goal configuration

• The average solution cost for a randomly generated 8-puzzle is about 22 steps

– Average solution cost = 22 steps

• The average branching factor is about 3

– Empty tile in middle 4 possible moves;

– In a corner, (7, 4, 8, 1 in Start state) there are 2 moves;

– Along an edge (positions 2, 5, 3, 6 in Start state) 3 moves;

– So, an exhaustive search to depth 22 would look at about 322 states = 3.1*1010
states (where 3 is branching factor)

– By keeping track of repeated states, we could cut down this factor by about 1,
70, 000

– Because it is known that there are only 9!/2 = 1, 81, 440 distinct states that
are reachable

– This is a manageable number, but for 15-puzzle is roughly 1013 states

– So, a good heuristic function is needed

 • To find the shortest solutions by using A*, a heuristic function is needed with
following property

• The heuristic function should never over estimate the number of steps to the goal

• Two commonly used candidates:

– h1=the number of misplaced tiles

– h2=the sum of the Manhattan distances of the tiles from their goal positions

Note: Please refer to PPT-8 for examples