Unit I

Overview of AI: Introduction to AI, Importance of AI, AI and its related field, AI techniques,
Criteria for success.

Problems, problem space and search: Defining the problem as a state space search, Production
Systems and its characteristics, Issues in the design of the search programs.

Heuristic search techniques: Generate and test, hill climbing, best first search technique, problem
reduction, constraint satisfaction.

Introduction to AI

"It is a branch of computer science by which we can create intelligent machines which can
behave like a human, think like humans, and be able to make decisions."

Artificial Intelligence is composed of two words Artificial and Intelligence, where Artificial defines
"man-made," and intelligence defines "thinking power", hence AI means "a man-made thinking
power."

Importance of AI
● AI technology is important because it enables human capabilities – understanding,
reasoning, planning, communication and perception – to be undertaken by
software increasingly effectively, efficiently and at low cost.
● General analytical tasks, including finding patterns in data, that have been
performed by software for many years can also be performed more effectively using
AI.
● The automation of these abilities creates new opportunities in most business sectors
and consumer applications.
● Significant new products, services and capabilities enabled by AI include
autonomous vehicles, automated medical diagnosis, voice input for human-
computer interaction, intelligent agents, automated data synthesis and enhanced
decision-making.
● AI has numerous, tangible use cases today that are enabling corporate revenue
growth and cost savings in existing sectors.
● Applications will be most numerous in sectors in which a large proportion of time is
spent collecting and synthesising data: financial services, retail and trade,
professional services, manufacturing and healthcare. Applications of AI-powered
computer vision will be particularly significant in the transport sector.
● Use cases are proliferating as AI’s potential is understood. We describe 31 core use
cases across eight sectors: asset management, healthcare, insurance, law &
 compliance, manufacturing, retail, transport and utilities.

AI and its related field

Application of AI

Artificial Intelligence has various applications in today's society. It is becoming essential for
today's time because it can solve complex problems with an efficient way in multiple
industries, such as Healthcare, entertainment, finance, education, etc. AI is making our daily
life more comfortable and fast.

Following are some sectors which have the application of Artificial Intelligence:

1. AI in Astronomy

○ Artificial Intelligence can be very useful to solve complex universe problems. AI

technology can be helpful for understanding the universe such as how it works, origin,
etc.
2. AI in Healthcare

○ In the last, five to ten years, AI becoming more advantageous for the healthcare
industry and going to have a significant impact on this industry.
○ Healthcare Industries are applying AI to make a better and faster diagnosis than
humans. AI can help doctors with diagnoses and can inform when patients are
worsening so that medical help can reach to the patient before hospitalization.

3. AI in Gaming

○ AI can be used for gaming purpose. The AI machines can play strategic games like
chess, where the machine needs to think of a large number of possible places.

4. AI in Finance

○ AI and finance industries are the best matches for each other. The finance industry is
implementing automation, chatbot, adaptive intelligence, algorithm trading, and
machine learning into financial processes.

5. AI in Data Security

○ The security of data is crucial for every company and cyber-attacks are growing very
rapidly in the digital world. AI can be used to make your data more safe and secure.
Some examples such as AEG bot, AI2 Platform,are used to determine software
bugs and cyber-attacks in a better way.

6. AI in Social Media

○ Social Media sites such as Facebook, Twitter, and Snapchat contain billions of user
profiles, which need to be stored and managed in a very efficient way. AI can
organise and manage massive amounts of data. AI can analyse lots of data to
identify the latest trends, hashtags, and requirements of different users.

7. AI in Travel & Transport

○ AI is becoming highly demanding for travel industries. AI is capable of doing various

 travel related works such as from making travel arrangements to suggesting the
hotels, flights, and best routes to the customers. Travel industries are using AI-
powered chatbots which can make human-like interaction with customers for better
and faster response.

8. AI in Automotive Industry

○ Some Automotive industries are using AI to provide virtual assistants to their users
for better performance. Such as Tesla has introduced TeslaBot, an intelligent
virtual assistant.
○ Various Industries are currently working on developing self-driven cars which can
make your journey more safe and secure.

9. AI in Robotics:

○ Artificial Intelligence has a remarkable role in Robotics. Usually, general robots are
programmed such that they can perform some repetitive task, but with the help of
AI, we can create intelligent robots which can perform tasks with their own
experiences without being pre-programmed.
○ Humanoid Robots are the best examples for AI in robotics, recently the intelligent
Humanoid robot named Erica and Sophia has been developed which can talk and
behave like humans.

10. AI in Entertainment

○ We are currently using some AI based applications in our daily life with some
entertainment services such as Netflix or Amazon. With the help of ML/AI
algorithms, these services show the recommendations for programs or shows.

11. AI in Agriculture

○ Agriculture is an area which requires various resources, labor, money, and time for
best results. Nowadays agriculture is becoming digital, and AI is emerging in this
field. Agriculture is applying AI as agriculture robotics, solid and crop
monitoring, predictive analysis. AI in agriculture can be very helpful for farmers.
12. AI in E-commerce

○ AI is providing a competitive edge to the e-commerce industry, and it is becoming

more demanding in the e-commerce business. AI is helping shoppers to discover
associated products with recommended size, color, or even brand.

13. AI in education:

○ AI can automate grading so that the tutor can have more time to teach. AI chatbot
can communicate with students as a teaching assistant.
○ AI in the future can work as a personal virtual tutor for students, which will be
accessible easily at any time and any place.

Subsets of AI

Machine Learning
Machine Learning, a crucial subset of artificial intelligence, is the machine’s ability to learn
from experience with no need for human intervention explicitly. It is the most widely used
form of AI in the market today. Machine Learning refers to the computer programs that
are fed data, learn from them and use this experience to make intelligent decisions.
Machine Learning is used in analysis, fraud detection and GPS based predictions to
name a few.

Neural Networks
Neural networks are a bunch of algorithms modelled after the neural networks that make up
the human brain. They are designed to absorb and assimilate and interpret sensory data
through labelling or clustering row input. The patterns they sense and interpret are in the form
of numerical data, a format all text, images or even sounds must be translated into for a
computer to understand. They help label, cluster and classify data based on similarities in the
input fed.

Deep Learning
Deep Learning is a technique of machine learning that uses neural networks to learn up the
way humans do – by example. And it does them accurately. It is the science behind driverless
cars that can distinguish a lamppost from a person. Deep learning requires a large
amount of labelled data sets to be able to work and effective and substantial computing
power. Deep Learning finds its applications in aerospace technology, healthcare and
driverless locomotives industry among others.

Robotics
A robot is a machine capable of sensing and interpreting and interacting with its environment.
Robots have become much smarter and intuitive, thanks to artificial intelligence. Robotics is
an interdisciplinary field of science and engineering that is powered by a consolidated
science of mechanical engineering, electrical engineering, computer science, and
algorithms. Robots are used in automobile manufacturing and used to move objects in space
or related fields.

Computer Vision
Computer Vision is the field of study that seeks to enable computers to “see” virtually like
the human eyes do. A computer learns by labelling or classifying various objects, albeit much
faster than human beings. Its goal is image classification and recognition. The Internet is
inundated with pictures and photographs. In order to search for these images, the computer
system needs to know what is in them. This is where the technology of computer visions
comes in.
So you see how vast the scope of artificial intelligence really is. It is a science unto itself. To
learn more about the science, professionals are increasingly joining artificial intelligence
training institutes across the world. DexLab Analytics, the institute that brought this article
to you, is a premiere artificial intelligence training institute in Gurgaon.
Criteria for success

The criteria for success in AI can vary depending on the specific application or task being
performed, but some general criteria include:
 - Accuracy: AI systems should be able to achieve high levels of accuracy in their
predictions or classifications. This means that their output should be consistent and
reliable.

- Speed: AI systems should be able to perform their tasks quickly, especially in real-
time applications such as autonomous vehicles or medical diagnosis.

- Robustness: AI systems should be able to handle unexpected inputs or situations

without crashing or producing incorrect results. They should be able to adapt to
changing conditions and continue to function reliably.

- Scalability: AI systems should be able to handle large volumes of data and scale up to
meet increasing demands as needed.

- Transparency: AI systems should be transparent in how they make decisions, with

clear explanations for their actions that can be easily understood by humans.

- Ethical considerations: AI systems should be developed and used in ways that are
ethical and aligned with human values, with appropriate safeguards in place to
prevent bias, discrimination, or other negative impacts.

- Generalization: AI systems should be able to apply what they have learned from one
task to new situations, without requiring extensive retraining or modification.

- Cost-effectiveness: AI systems should be developed and deployed in ways that are

cost-effective, both in terms of the resources required for development and the return
on investment they generate.

Problems, problem space and search:

A state space is a collection of all possible configurations of a problem, and the goal of the
search is to find a path from an initial state to a goal state, where each step along the path is a
valid state transition.

To define a problem as a state space search, you need to identify the following
components:

- State Space: The set of all possible configurations or states of the problem.

+ Initial State: The starting point from which the search algorithm begins its exploration
of the state space.
 - Actions: The set of valid actions or operations that can be performed on the current
state to generate a new state.

- Transition Function: A function that maps a current state and an action to a new state.

- Goal Test: A test that determines whether a given state is a goal state or not.

- Path Cost Function: A function that assigns a cost to each transition from one state to
another.

Once you have defined these components, you can use search algorithms such as Breadth-
First Search (BFS), Depth-First Search (DFS), or A* Search to find the optimal path from the
initial state to the goal state.
Production Systems and their issues:

Production systems are a type of AI architecture used to represent and automate knowledge-
based decision-making processes. They consist of a set of rules and a control strategy for
applying those rules to incoming data. The following are some characteristics of production
systems:

- Rule-based: Production systems use a set of rules to make decisions or take actions.
The rules are typically expressed as if-then statements, where the if part describes the
conditions under which the rule is applicable and the then part describes the action to
be taken.

- Modularity: Production systems are modular in design, meaning that the rules are
organized into independent modules that can be easily added, modified, or removed
without affecting the rest of the system.

- Inference engine: Production systems use an inference engine to apply the rules to
incoming data and generate new data. The inference engine uses a control strategy to
decide which rule to apply next, based on the current state of the system.

- Transparency: Production systems are transparent, meaning that the decision-making

process is easily understandable by human users. This makes it easier to debug and
modify the system.

- Scalability: Production systems can be easily scaled up or down to handle large

amounts of data or to accommodate new rules.

However, there are also issues in the design of search programs in AI. Some of these
issues are:
Search space explosion: In many search problems, the number of possible solutions is so
large that searching through all of them is not feasible. This is known as the search space
explosion problem.

- Local optima: In some search problems, the search algorithm can get stuck in a
suboptimal solution and fail to find the global optimal solution. This is known as the
local optima problem.

- Heuristics: Search algorithms often rely on heuristics to guide the search process.
However, choosing the right heuristics can be difficult, and poorly chosen heuristics
can lead to suboptimal solutions.

- Evaluation functions: In many search problems, it is necessary to evaluate the quality

of a potential solution. Designing an effective evaluation function can be challenging,
as it must take into account multiple factors and be able to accurately differentiate
between good and bad solutions.

- Trade-offs: Search algorithms often involve trade-offs between various factors, such
as speed, accuracy, and memory usage. Designing an optimal search algorithm often
requires balancing these trade-offs to achieve the best overall performance.

HEURISTIC SEARCH TECHNIQUES:

(proceeding to a solution by trial and error or by rules that are only loosely defined.)
Search Algorithms
Many traditional search algorithms are used in AI applications. For complex problems, the
traditional algorithms are unable to find the solutions 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 algorithms or Brute-force algorithms, search through the search space all
possible candidates for the solution checking whether each candidate satisfies the problem’s
statement.
• Informed search algorithms use heuristic functions that are specific to the problem, apply
them to guide the search through the search space to try to reduce the amount of time spent in
searching.
A good heuristic will make an informed search dramatically outperform any uninformed search:
for example, the Travelling Salesman Problem (TSP), where the goal is to find is a good solution
instead of finding the best solution.
In such problems, the search proceeds using current information about the problem to predict
which path is closer to the goal and follow it, although it does not always guarantee to find the
best possible solution. Such techniques help in finding a solution within reasonable time and
space (memory). Some prominent intelligent search algorithms are stated below:

1. Generate and Test Search

2. Best-first Search
3. Greedy Search
4. A* Search
5. Constraint Search
The first requirement is that it causes motion, in a game playing program, it moves on the board
and in the water jug problem, filling water is used to fill jugs. It means the control strategies
without the motion will never lead to the solution. The second requirement is that it is
systematic, that is, it corresponds to the need for global motion as well as for local motion. This
is a clear condition that neither would it be rational to fill a jug and empty it repeatedly, nor it
would be worthwhile to move a piece round and round on the board in a cyclic way in a game.
We shall initially consider two systematic approaches for searching. Searches can be classified
by the order in which operators are tried: depth-first, breadth-first, bounded depth-first

There are some more algorithms. They are either improvements or combinations of these.
• Hierarchical Representation of Search Algorithms: A Hierarchical representation of most
search algorithms is illustrated below. The representation begins with two types of search:
• Uninformed Search: Also called blind, exhaustive or brute-force search, it 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, this uses information about the
problem to guide the search—usually guesses the distance to a goal state and is therefore
efficient, but the search may not be always possible.

Breadth-first search
A Search strategy, in which the highest layer of a decision tree is searched completely before
proceeding to the next layer is called Breadth-first search (BFS).
• In this strategy, no viable solutions are omitted and therefore it is guaranteed that an optimal
solution is found.
• This strategy is often not feasible when the search space is large.
Algorithm
1. Create a variable called LIST and set it to be the starting state.
2. Loop until a goal state is found or LIST is empty, Do
a. Remove the first element from the LIST and call it E. If the LIST is empty, quit.
b. For every path each rule can match the state 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 LIST.
Advantages
1. Guaranteed to find an optimal solution (in terms of shortest number of steps
to reach the goal).
2. Can always find a goal node if one exists (complete).
Disadvantages
1. High storage requirement: exponential with tree depth.
Depth-first search
A search strategy that extends the current path as far as possible before backtracking to the last
choice point and trying the next alternative path is called Depth-first search (DFS).
• This strategy does not guarantee that the optimal solution has been found.
• In this strategy, search reaches a satisfactory solution more rapidly than breadth first, an
advantage when the search space is large.
Algorithm
Depth-first search applies operators to each newly generated state, trying to drive directly toward
the goal.
1. If the starting state is a goal state, quit and return success.
2. Otherwise, do the following until success or failure is signalled:
a. Generate a successor E to the starting state. If there are no more successors, then signal failure.
b. Call Depth-first Search with E as the starting state.
c. If success is returned signal success; otherwise, continue in the loop.
Advantages
1. Low storage requirement: linear with tree depth.
2. Easily programmed: function call stack does most of the work of maintaining state of the
search.
Disadvantages
1. May find a sub-optimal solution (one that is deeper or more costly than the best solution).
2. Incomplete: without a depth bound, may not find a solution even if one exists.

2.4.2.3 Bounded depth-first search

Depth-first search can spend much time (perhaps infinite time) exploring a very deep path that
does not contain a solution, when a shallow solution exists. An easy way to solve this problem is
to put a maximum depth bound on the search. Beyond the depth bound, a failure is generated
automatically without exploring any deeper.
Problems:
1. It’s hard to guess how deep the solution lies.
2. If the estimated depth is too deep (even by 1) the computer time used is dramatically
increased, by a factor of bextra.
3. If the estimated depth is too shallow, the search fails to find a solution; all that computer time
is wasted.

Generate and Test Strategy

Generate-And-Test Algorithm
Generate-and-test search algorithm is a very simple algorithm that guarantees to find a solution if
done systematically and there exists a solution.
Algorithm: Generate-And-Test
1.Generate a possible solution.
2.Test to see if this is the expected solution.
3.If the solution has been found quit else go to step 1.
Potential solutions that need to be generated vary depending on the kinds of problems. For some
problems the possible solutions may be particular points in the problem space and for some
problems, paths from the start state.

Figure: Generate And Test

Generate-and-test, like depth-first search, requires that complete solutions be generated for
testing. In its most systematic form, it is only an exhaustive search of the problem space.
Solutions can also be generated randomly but solution is not guaranteed. This approach is what i
known as British Museum algorithm: finding an object in the British Museum by wandering
randomly.
Systematic Generate-And-Test
While generating complete solutions and generating random solutions are the two extremes there
exists another approach that lies in between. The approach is that the search process proceeds
systematically but some paths that unlikely to lead the solution are not considered. This
evaluation is performed by a heuristic function.
Depth-first search tree with backtracking can be used to implement systematic generate-and-test
procedure. As per this procedure, if some intermediate states are likely to appear often in the
tree, it would be better to modify that procedure to traverse a graph rather than a tree.
Generate-And-Test And Planning
Exhaustive generate-and-test is very useful for simple problems. But for complex problems even
heuristic generate-and-test is not very effective technique. But this may be made effective by
combining with other techniques in such a way that the space in which to search is restricted. An
AI program DENDRAL, for example, uses plan-Generate-and-test technique. First, the planning
process uses constraint-satisfaction techniques and creates lists of recommended and
contraindicated substructures. Then the generate-and-test procedure uses the lists generated and
required to explore only a limited set of structures. Constrained in this way, generate-and-test
proved highly effective. A major weakness of planning is that it often produces inaccurate
solutions as there is no feedback from the world. But if it is used to produce only pieces of
solutions then lack of detailed accuracy becomes unimportant.

INFORMED (HEURISTIC) SEARCH

Uninformed (blind) search is inefficient in most cases because they do not have any domain
specific knowledge about goal state. Heuristic Search Uses domain-dependent (heuristic)
information
beyond the definition of the problem itself in order to search the space more efficiently.
The following are some ways of using heuristic information:

Deciding which node to expand next, instead of doing the expansion in a strictly breadth-
first or depth-first order;

In the course of expanding a node, deciding which successor or successors to generate,

instead of blindly generating all possible successors at one time:
Deciding that certain nodes should be discarded, or pruned, from the search space.

Informed search algorithms use domain knowledge. In an informed

search, problem information is available which can guide the search. Informed search strategies
can find a solution more efficiently thanan uninformed search strategy. Informed search is also
called a Heuristic search.
Heuristics is a guess work, or additional information about the problem. It may miss the solution,
if wrong heuristics is supplied. However, in almost all problems with correct heuristic
information, it provides good solution in reasonable time
Informed search can solve much complex problem which could not be solved in another way.
We have the following informed search algorithm:
1. Best-First Search
2. A* algorithm
3. Iterative Deepening A*
3.7.1Strategies for providing heuristics information:
The informed search algorithm is more useful for large search space. All the informed search
algorithm uses the idea of heuristic, so it is also called Heuristic search.
“Heuristics are criteria, methods or principles for deciding which among several alternative
courses of action promises to be the most effective in order to achieve some goal”
Heuristic Function:
Heuristic information is provided in form of function called heuristic function.

Heuristic is a function which is used in Informed Search, and it finds the most promising
path.
It takes the current state of the agent as its input and produces the estimation of how close
agent is from the goal.
Heuristic function estimates how close a state is to the goal. It is represented byh(n), and it
calculates the cost of an optimal path between the pair of states.
The heuristic method, however, might not always give the best solution, but it guaranteed to
find a good solution in reasonable time.
This technique always uses to find solution quickly.
Informed Search Define a heuristic function. h(n). that estimates the “goodness" of a node n.
The heuristic function is an estimate, based on domain-specific information that is
computable from the current state description of how close we are to a goal.
Specifically, h(n) = estimated cost (or distance) of minimal cost path from state ‘n’ to a goal
state.
A heuristic function at a node n is an estimate of the optimum cost from the current node toa
goal.
Denoted by h(n)
h(n) = estimated cost of the cheapest path from node n to a goal node
For example, suppose you want to find a shortest path from Kolkata to Guwahati, then heuristic
for
Guwahati may be straight-line distance between Kolkata and Guwahati, that is
h(Kolkata) = euclideanDistance(Kolkata,Guwahati)
3.7.2 Formulation of informed (heuristic) search problem as State Space
Informed search problems can be represented as state space. The state space of a problem
includes: an Initial state, one or more goal state, set of state transition operator O (a set of rules),
used to change the current state to another state and a heuristic function h.
In general, a state space is represented by 5 tuples as follows: S: [S, s ,O, G, h]
Where S: (Implicitly specified) Set of all possible states (possibly infinite).
s : start state of the problem, s ∈ S .
O: Set of state transition operator, each having same cost. This is used to change the state from
one state to another. It is the set of arcs (or links) between nodes
G: Set of Goal state, G ⊆ S.
h(): A heuristic function, estimating the distance toa goal node.

Fig 8 State space with initial and goal node

We need to find a sequence of actions which transform the agent from the initial sate
s to Goal
state G. State space is commonly defined as a directed graph or as a tree in which each node is a
state and each arc represents the application of an operator transforming a state to a successor
state.
Thus, the problem is solved by using the rules (operators), in combination with an appropriate
control strategy, to move through the problem space until a path from initial state to a goal state
is found. This process is known as search. A solution path is a path in state space from
s (initial
sate) to G (Goal state).

We have already seen an OPEN list is used to implement an uninformed (Blind) search (section
3.2). But the problem with using only one list OPEN is that, it is not possible to keep track of the
node which is already visited. That is “how we can maintain a part of the state space that is
already visited”. To save the explicit space, we maintained another list called CLOSED. Now
we can select a node from OPEN and save it in CLOSED. Now, when we generate successor
node from CLOSED, we check whether it is already in (OPEN ∪ CLOSED).
If it is already in
(OPEN ∪ CLOSED), we will not insert in OPEN again, otherwise insert.

3.7.3 Best-First Search

Best first search uses an evaluation function f(n) that gives an indication of which node to
expand next for each node. Every node in a search space has an evaluation function (heuristic
function) associated with it. A heuristic function value h(n) on each node indicates how the node
is from the goal node. Note that Evaluation function=heuristic cost function (in case of
minimization
problem) OR objective function(in case of maximization).Decision of which node to be
expanded
depends onvalue of evaluation function. Evaluation value= cost/distance of current node from
goal node
and for goal node evaluation function value=0
Based on the evaluation function, f(n), Best-first search can be categorized into the following
categories:

1) Greedy Best first search

2) A* search
The following 2 list (OPEN and CLOSED) are maintained to implement these two algorithms.
1. OPEN – all those nodes that have been generated & have has heuristic function applied
to them but have not yet been examined.
2. CLOSED- contains all nodes that have already been examined.

3.7.4Greedy Best-First search:

Greedy best-first search algorithm always selects the path which appears best at that moment.
It is the combination of depth-first search and breadth-first search algorithms. It uses the
heuristic function and search. Best-first search allows us to take the advantages of both
algorithms. With the help of best-first search, at each step, we can choose the most promising
node. In the best first search algorithm, we expand the node which is closest to the goal node and
the closest cost is estimated by heuristic function, i.e.
f(n)= g(n).
Were, h(n)= estimated cost from node n to the goal.
The greedy best first algorithm is implemented by the priority queue (or to store the heuristic
function value).

Best first search algorithm:

1. Initialize: Set OPEN = {s} , CLOSED={ };
f(s) = h(s)
2.Fail:If OPEN = { }, terminate with failure.
3. Select: Select the minimum cast state a from OPEN, save n in CLOSED.
4.Terminate: If a ∈ Goal node, terminate with success and return f(n),
else
5. Expend: For each successor, m of n,
If m [OPEN ∪ CLOSED]

Set f(m) = h(m) and Insert m in OPEN

.........
6. LOOP:Goto Step 2
OR Pseudocode (for Best-First Search algorithm)
Step 1: Place the starting node into the OPEN list.
Step 2: If the OPEN list is empty, Stop and return failure.
Step 3: Remove the node n, from the OPEN list which has the lowest value of h(n),
and places it in the CLOSED list.
Step 4: Expand the node n, and generate the successors of node n.
Step 5: Check each successor of node n, and find whether any node is a goal node
or not. If any successor node is goal node, then return success and terminate the
search, else proceed to Step 6.
Step 6: For each successor node, algorithm checks for evaluation function f(n), and
then check if the node has been in either OPEN or CLOSED list. If the node has not
been in both lists, then add it to the OPEN list.
Step 7: Return to Step 2.

Advantages of Best-First search:

Best first search can switch between BFS and DFS, thus gaining the advantages of both
the algorithms.
This algorithm is more efficient than BFS and DFS algorithms.
Disadvantages of Best-First search:
Chances of getting stuck in a loop are higher.
It can behave as an unguided depth-first search in the worst-case scenario.
Consider the following example for better understanding of greedy Best-First search algorithm.
Example1: Consider the following example (graph) with heuristic function value h(n)[Fig 2]
which illustrate the greedy Best-first search. Note that in the following example, heuristic
function is defined as

hSLD = straight line distance from n to goal

Let heuristic function value h(n) for each node n to goal node G is defined as
Straight line distance
A→G=h(A)=40
B→G=h(B)=32
C→G=h(C)=25
D→G=h(D)=35
E→G=h(E)=19
F→G=h(F)=17

H→G=h(H)=10
G→G=h(G)=0
h(n)= straight line distance from node n to G
Note that h(G)=0
The nodes added/deleted from OPEN and CLOSED list using Best-First Search algorithm are
shown below.

Explanation are as follows:

Step1:initially OPEN list start with start state ‘A’ and CLOSED list with empty.
Step2: Children of A={C[25], B[32] D[35]}, so
OPEN={C[25], B[32], D[35]} therefore Best=C, so expend C node next.
Step3: Children of C={E[19],F[17]}, so
OPEN={F[17],E[19], B[32], D[35]} therefore Best=F, so expend node F next.
Step4: Children of F={G[0]}, therefore OPEN= {G[0], E[19], B[32], D[35]} Best=G, this is a
goal node
so Stop.
Finally, we got the shortest path: ACFG and cost is 44.
Example2: Consider the below search problem, and we will traverse it using greedy best-first
search. At
each iteration, each node is expanded using evaluation function f(n)=h(n) , which is given in the
below
table.
Here, we are using two lists which are OPEN and CLOSED Lists. Following are the iteration for
traversing the above example.

Initialization: Open [A, B], Closed [S]

Iteration 1: Open [A], Closed [S, B]
Iteration2: Open [E, F, A], Closed [S, B]
: Open [E, A], Closed [S, B, F]
Iteration 3: Open [I, G, E, A], Closed [S, B, F]
: Open [I, E, A], Closed [S, B, F, G]
Hence the final solution path will be S----> B----->F----> G
Evaluation of Best-First Search algorithm:
Time Complexity:
The worst-case time complexity of Greedy best first search is O(bm
).

Space Complexity:
The worst-case space complexity of Greedy best first search is O(bm

). Where, m is the maximum

depth of the search space.
Complete: Greedy best-first search is also incomplete, even if the given state space is finite.
Optimal: Greedy best first search algorithm is not optimal.

A* Algorithm

A* search is the most commonly known form of best-first search. It uses heuristic function h(n),
and cost to reach the node n from the start state g(n). It has combined features of uniform cost
search (UCS) and greedy best-first search, by which it solves the problem efficiently. A* search
algorithm finds the shortest path through the search space using the heuristic function. This
search algorithm expands less search tree and provides optimal result faster.
In A* search algorithm, we use search heuristic as well as the cost to reach the node. Hence, we
can combine both costs as following, and this sum is called as a fitness number (Evaluation
Function).

Fig 9 Evaluation function f(n) in A* Algorithm

A* algorithm evaluation function f(n)is defined as f(n) = g(n) + h(n)
Where g(n) =sum of edge costs from start state to n
And h(n) = estimate of lowest cost path from node ngoal node.
If h(n) is admissible then search will find optimal solution. Admissible means underestimates
cost of any

solution which can reached from node. In other words, a heuristic is called admissible if it
always under-
estimates, that is, we always have h(n) ≤ h (n), where h*(n) denotes
the minimum distance to a goal

state from state n.

A* search begins at root node and then search continues by visiting the next node which has the
least
evaluation value f(n).
It evaluates nodes by using the following evaluation function
f(n) = h(n) +g(n) = estimated cost of the cheapest solution through n.
Where,
g(n): the actual shortest distance traveled from initial node to current node, it helps to avoid
expanding
paths that are already expansive
h(n): the estimated (or “heuristic”) distance from current node to goal, it estimates which node is
closest
to the goal node.
Nodes are visited in this manner until a goal is reached.
Suppose s is a start state then calculation of evaluation function f(n) for any node n is shown in
following
figure 10.

f(n) = g(n) + h(n)

Estimated cost of the

cheapest solution.

Cost to reach node n

from start state.

Cost to reach from node

n to goal node.
Note that, the implementation of A* Algorithm involves maintaining two lists- OPEN and
CLOSED. The list OPEN contains those nodes that have been evaluated by the heuristic
function but have not expanded into successors yet and the list CLOSED contains those nodes
that have already been visited.
See the following steps for working of A* algorithm:
Step-1: Define a list OPEN. Initially, OPEN consists of a single
node, the start node S.
Step-2: If the list is empty, return failure and exit.
Step-3: Remove node n with the smallest value of f(n) from OPEN
and move it to list CLOSED.
If node n is a goal state, return success and exit.
Step-4: Expand node n.
Step-5: If any successor to n is the goal node, return success and the
solution by tracing the path from goal node to S.
Otherwise, go to Setp-6.
Step-6: For each successor node,
Apply the evaluation function f to the node.
If the node has not been in either list, add it to OPEN.
Step-7: Go back to Step-2.

Working of A* algorithm
Example1: Let’s us consider the following graph to understand the working of A* algorithm.
The numbers written on edges represent the distance between the nodes. The numbers written on
nodes represent the heuristic value. Find the most cost-effective path to reach from start state A
to final state J using A* Algorithm.

Step-1:
We start with node A. Node B and Node F can be reached from node A. A* Algorithm
calculates f(B) and f(F). Estimated Cost f(n) = g(n) +h(n) for Node B and Node F is:
f(B) = 6+8=14
f(F) = 3+6=9
Since f(F) < f(F), so it decides to go to node F.
Closed list (F)
Path- A →F
Step-2: Node G and Node H can be reached from node F.
A* Algorithm calculates f(G) and f(H).
f(G) = (3+1)=5=9
f(H) = (3+7) +5=13
Since f(G) < f(H), so it decides to go to node G.
Closed list (G)
Path- A→F→G
Step-3: Node I can be reached from node G.
A* Algorithm calculates f(I).
f(I)=(3+1+3)+1=8; It decides to go to node I.
Closed list (I).
Path- A→F→G→I
Step-4: Node E, Node H and Node J can be reached from node I.
A* Algorithm calculates f(E), f(H), f(J).
f(E) = (3+1+3+5) + 3 =15
f(H) = (3+1+3+2) + 3 = 12
f(J) = (3+1+3+3) +0 = 10
Since f(J) is least, so it decides to go to node J.
Closed list (J)
Shortest Path - A→F→G→I→J
Path Cost is 3+1+3+3=10

Example 2:Consider the following graph and apply A* algorithm and find the most cost-
effective path to reach from start state S to final stateG. The heuristic function value of each

node n is defined in the table given.

Solution:
S→A=1+3=4
S→G=10+0=10
S→A→B=1+2+4=7
S→A→C=1+1+2=4
S→A→C→D=1+1+3+6=11
S→A→C→G=1+1+4=6
S→A→B→D=1+2+5+6=14
S→A→C→D→G=1+1+3+2=7
S→A→B→D→G=1+2+5+2=10
3.8.2 Advantages and disadvantages of A* algorithm
Advantages:
A* search algorithm is the best algorithm than other search algorithms.
A* search algorithm is optimal and complete.
This algorithm can solve very complex problems.
Disadvantages:
It does not always produce the shortest path as it mostly based on heuristics and
approximation.
A* search algorithm has some complexity issues.
The main drawback of A* is memory requirement as it keeps all generated nodes in the
memory, so it is not practical for various large-scale problems.

Problem Reduction Search

Problem reduction search is broadly defined as a planning how best to solve a problem that can
be recursively decomposed into subproblems in multiple ways. There are many ways to
decompose a problem, we have to find the best decomposition, which gives the quality of
searching or cost is minimum.
We already know about the divide and conquer strategy, a solution to a problem can be obtained
by decomposing it into smaller sub-problems. Each of this sub-problem can then be solved to get
its sub solution. These sub solutions can then be recombined to get a solution as a whole. That is
called is Problem Reduction. This method generates arc which is called as AND arcs. One
AND arc may point to any number of successor nodes, all of which must be solved for an arc to
point to a solution.
When a problem can be divided into a set of sub problems, where each sub problem can be
solved separately and a combination of these will be a solution, AND-OR graphs or AND - OR
trees are used for representing the solution. The decomposition of the problem or problem
reduction generates AND arcs. Consider the following example to understand the AND-OR
graph (figure-11).
The figure-11 shows an AND-OR graph. In an AND-OR graph, OR node represents a choice
between possible decompositions, and an AND node represents given decomposition. For
example, to Get a bike, we have two options, either:
1.(Steal a bike)
OR

Goal = Get a bike

Goal : Steal
a bike

Goal : Get
some money

Goal : Buy a
bike
AND Arc

AND

OR

2. Get some money AND Buy a Bike.

In this graph we are given two choices, first Steal a bike or get some money AND Buy a Bike.
When we have more than one choice and we have to pick one, we apply OR condition to choose
one.(That's what we did here).
Basically, the ARC here denotes AND condition.
Here we have replicated the arc between the Get some money and buy a bike because by getting
some money possibility of buying a bike is more than stealing.
AO* search algorithm is based on AND-OR graph, so it is called AO* search algorithm. AO*
Algorithm basically based on problem decomposition (Breakdown problem into small pieces).
The main difference between the A*(A star) and AO*(AO star) algorithms is that A* algorithm
represents an OR graph algorithm that is used to find a single solution (either this or that).
Butan AO* algorithm represents an AND-OR graph algorithm that is used to find more than
one solution by ANDing more than one branch.
A* algorithm guarantees to give an optimal solution while AO* doesn’t since AO* doesn’t
explore all other solutions once it got a solution.

3.9.1 Problem definition in AND-OR graph:

Given [G, s, T]
Where G: Implicitly specified AND/OR graph
s: Strat node of the AND/OR graph
T: Set of terminal nodes (called SOLVED)
h(n): Heuristic function estimating the cost of solving the sub
problem at n.
Example1:
Let us see one example with the presence of heuristic value at every node (see fig 2) . The
estimated heuristic value is given at each node. The heuristic value h(n) at any node indicates
“from this node at least h(n) value (or cost) is required to find solution”. Here we assume the
edge cost value (i.e., g(n) value) for each edge is 1. Remember in OR node we always mark that
successor node which indicates best path for solution.

Note that, the graph given in fig 2, there are two paths for solution from start state S: either S-A-
B or S-C. To calculate the cost of the path we use the formula f(n)=g(n)+h(n) [note that here g(n)

value is 1 for every edge].

Path1: f(S-A-B)=1+1+7+12=21
Path2: f(S-C)=1+13=14
Since min(21,14) = 14; so, we select successor node C, as its cost is minimum, so it indicates
best path for solution.
Note that C is a AND node; so, we consider both the successor node of C. The cost of node C is
f(C-F-G)=1+1+5+7=14; so, the revised cost of node C is 14 and now the revised cost of node S
is f(S-C)=1+14=15 (revised).
Note that once the cost (that is f value) of any node is revised, we propagate this change
backward through the graph to decide the current best path.
Now let us explore another path and check whether we are getting lessor cost as compared to this
cost or not.
F(A-D)=1+5=6 and f(A-E)=1+6=7; since A is an OR node so best successor node is D since
min(6,7)=6. So revised cost of Node A will be 6 instead of 7, that is f(A)=6 (revised). Now next
selected node is D and D is having only one node H so f(D-H)=1+2=3, so the revised cost of

node D is 3, so now the revised cost of node A, that is f(A-D-H)=4. This path is better than f(A-
E)=7. So, the final revised cost of node A is 4. Now the final revised cost of f(S-A-
B)=1+1+4+12=18 (revised).

Thus, the final revised cost for

Path1: f(S-A-B)=18 and
Path2: f(S-C)=15
So optimal cost is 15.

AO* algorithm
Our real-life situations cannot be exactly decomposed into either AND tree or OR tree but is
always combination of both. So, we need an AO* algorithm where O stands for 'ordered'. Instead
of two lists OPEN and CLOSED of A* algorithm, we use a single structure GRAPH in AO*
algorithm. If represents a part of the search graph that has been explicitly generated so far. Please
note that each node in the graph will point both down to its immediate successors and to its
immediate predecessors. Also note that each node will have some h'(n) value associated with it.
But unlikeA* search, g(n) is not stored. It is not possible to compute a single value of g(n) due to
many paths to the same state. It is not required also as we are doing top-down traversing along
best-knownpath.
This guarantees that only those nodes that are on the best path are considered for expansion
Hence, h'(n) will only serve as the estimate of goodness of a node.
Next, we develop an AO* algorithm.

Algorithm AO*
3.9.3 Advantage of AO* algorithm
Note that AO* will always find a minimum cost solution if one exists ifh’(n) < h(n)and that all
arc
costs are positive. The efficiency of this algorithm will depend on how closelyh’(n)
approximates h(n).
Also note that AO* is guaranteed to terminate even on graphs that have cycles.
Note: When the graph has only OR node then AO* algorithm works just like A* algorithm.

Constraint Satisfaction Search

A constraint search does not refer to any specific search algorithm but to a layer of
complexity added to existing algorithms that limit the possible solution set. Heuristic and
acquired knowledge can be combined to produce the desired result a constraint satisfaction
problem is a special kind of search problem in which states are defined by the values of a set
of variables and the goal state specifies a set of constraints that the value must obey. There
are many problems in AI in which the goal state is not specified in the problem and it requires
to be discovered according to some specific constraint. Examples of some constraint
satisfaction search include design problem, labeling graphs, robot path planning and
cryptarithmatic problem etc.

that subset. The search space of CSPS is often exponential. Therefore a number of different
approaches to the problem have been proposed to reduce the search space and find a feasible
solution in a reasonable time based on the search space exploring and variable selection
heuristics different algorithms and can be developed for a CSP problem. The algorithms can
be divided into two major categories such as complete and incomplete algorithm.

Complete algorithms seek any solution or solutions of a CSP or they try to prove that no
solution into the categories like constraint propagation techniques which tries to eliminate
values that are consistent with some constraints and systematic search techniques. Which
explores systematically the whole search space. But on the other hand incomplete search
methods do not explore the whole search space. They search the space either non-
systematically or in a systematic manner, but with a limit on some resource.

They may not provide a solution but their computational time is reasonably reduced. They
cannot be applied to find all solutions or to prove that no solution exists. Let us look an
algorithm to solve a constraint satisfaction problem.
Algorithm:

1) Open all objects that must be assigned values in a complete solution.

2) Repeat until all objects assigned valid values.

3) Select an object and strengthen as much as possible. The set of constraints that
apply to object.

4) If set of constraints is different from previous set then open all objects that share
any of these constraints. Remove selected objects.

5) If union of constraints discovered above defines a solution, return solution.

6) If union of constraints discovered above defines a contradiction, return failure.

7) Make a guess in order to proceed. Repeat until a solution is found.

8) Select an object with a number assigned value and try strengthen its constraints.

Constraint Satisfaction Problems in Artificial Intelligence

Constraint satisfaction problems are problems in Artificial Intelligence which concern

themselves with strictly the goal state. They take advantage of general state representation.

Intuition
States — represent them as a vector of feature values (a set of k variables), each variable has

a domain of unique values. The state is specified by assigning values to all the variables, and

a partial state is the assignment of a value to some of the variables

Goal — conditions on the vector of feature values

To solve a CSP we find a set of values for the features to satisfy the conditions.
A formal definition:

A CSP consists of

● A set of variables V1, …Vn;

● A(finite)domain of values Domain[Vi] ;

● A set of constraints C1, …, Cm

Each constraint has a scope or a set of variables that can be operated on.

The goal is to satisfy the constraint by assigning the right values. A CSP is cannot be satisfied

if no solution exists.

A CSP problem can be defined as a search problem where the initial state is an empty

assignment to a variable, the function is assigning values to variables and the goal test is to

see if the assignments are correct(no constraint violations) and complete.

Backtracking Search
Since CSPs do not require finding a path to a goal, they just require the correct configurations

to the goal. We can solve these best by backtracking from the goal or reverse engineering the

problem.

Method:

1. Find partial assignments

2. Decide on a value for one variable at a time (order agnostic)

3. If a constraint fails just reject it

Implementation:

You can complete backtracking recursively.

If the variables are set, then terminate the recursion

Else:

1. Pick an unassigned variable V and assign it a value

2. Test the constraints of V and all other variables that were assigned
2. If a constraint fails than return, else keep recursing.

Constraint Propagation
There might be variables that have no possible values, but backtracking does not detect this

until it tries to assign them a value.

We can look ahead at the unassigned variables trying to detect the failures.

Propagation has to be applied to the search and almost if not all every nodes in the tree. Since

propagation is an inference, it takes a lot long to calculate the next step.

We can propagate using two ways:

Forward Checking and Generalized Arc Consistency.

Forward Checking:
When instantiating a variable V, do the following for all constraints C that have only one not

instantiated variable X remaining:

● Check all the values of X;

● Prune those values that violate C.

Then backtrack again.

As we backtrack, we have to restore the values that were pruned.

Properties:
CSP problems are NP-complete (nondeterministic polynomial time) in that they find a

solution in polynomial time and that can be tested.

The worst case run time is exponential. Forward checking is often 100 times faster since it

solves for sub problems but it can do much worse.

Decrease time complexity:

You can also decrease the time by dynamically choosing the ordering of a variables using a

heuristic.

Select the variable that is involved in the largest number of constraints on other unassigned

variables.

If a variable has only one value left, we propagate its consequences immediately.

Generalized Arc Consistency

The goal is to remove a value d on a variable V that is not consistent with assignments to

other variables. d is said to be Arc Inconsistent. We can remove d from the domain of the

variable as the value does not produce a solution.

For example.

Given C(X,Y) where we want X > Y

Dom[X] = (2, 7, 13) Dom[Y] =(4, 11, 19)

We remove 2 from domain of X and 19 from domain of Y

So that X > Y.

All constraints must be GAC at every node of the search space. We do this by removing these

inconsistent variables. Every time we assign a value to a variable, we check all the constraints

and remove the inconsistent variables. We have to do this until everything is consistent.

Properties
When all constraints are consistent:

Each domain has a single value, at least a domain is empty, some may have more than one

value that needs to be solved that have to be reduced.

The complexity is O(cd³)

With higher order constraints:

The complexity is O(d^k * T(c)) where T is the number of forbidden values.

Conclusions
Plain backtracking offers the advantage of checking a constraint when it has zero unassigned

variables

Forward Checking checks a constraint only when it has one unassigned variables

GAC checks all constraints, leading to removing more incorrect values. (During the initial

state, the preprocessing, directly, and during search)

GAC does not find a solution unless we do search while we enforce GAC.

Thus constraint satisfaction problems can be improved using GAC, checking and

backtracking.

Advantages:

Flexibility: Constraint satisfaction is a flexible problem-solving approach that can be used to

model a wide range of problems in various fields, including scheduling, planning,

optimization, and design.

Modularity: Constraint satisfaction allows for the representation of a problem as a set of

independent constraints. This modularity makes it easier to add, remove or modify constraints

as needed.

Efficiency: Constraint satisfaction algorithms can be designed to be highly efficient and can

solve problems quickly and accurately. This makes it ideal for real-time applications, such as

robotics and game development.

Heuristics: Constraint satisfaction algorithms can be enhanced with heuristic techniques, such

as variable and value ordering, to improve the efficiency of the search.

Disadvantages:

Limited applicability: Constraint satisfaction is not suitable for all types of problems,

especially those that do not have a clear set of constraints or that involve continuous

variables.

Complexity: Constraint satisfaction problems can be complex and difficult to solve,

especially when the number of variables and constraints is large. The search space can

become very large, which can make it difficult to find a solution in a reasonable amount of

time.

Scalability: Constraint satisfaction problems can become exponentially more difficult to solve

as the number of variables and constraints increases. This can make it difficult to solve very

large problems.

Trade-off between accuracy and efficiency: Constraint satisfaction algorithms can be

designed to prioritise accuracy or efficiency, but it can be difficult to strike the right balance

between the two. Some algorithms may sacrifice accuracy for efficiency, while others may

take too long to find a solution.