UNIT I PROBLEM SOLVING 9

Introduction to AI - AI Applications - Problem solving agents – search algorithms –

uninformed search strategies – Heuristic search strategies – Local search and
optimization problems – adversarial search – constraint satisfaction problems (CSP)

INTRODUCTION TO AI
Artificial intelligence (AI) is the intelligence exhibited by machines or software. It
is also the name of the academic field of study which studies how to create computers
and computer software that are capable of intelligent behavior. The central problems (or
goals) of AI research include reasoning, knowledge, planning, learning, natural language
processing (communication), perception and the ability to move and manipulate objects.
AI is the science and engineering of making intelligent machines, especially
intelligent computer programs. A branch of science which deals with helping machines
find solutions to complex problems in a more human-like fashion. It is a field of
computer science that seeks to understand and implement computer-based technology
that can simulate characteristics of human intelligence and human sensory capabilities to
make
● Systems that act like humans - Machines with mind in the full and literal sciences
● Systems that think like humans - Act of creating machines, that performs functions
that require
● Systems that think rationally - Study of mental facilities through the use of
computational models
● Systems that act rationally - Rationalist approach involves a combination of
mathematics and engineering
Other some definitions of AI are
AI is: “The art of creating machines that perform functions that require intelligence when
performed by people”
AI is: “The automation of activities that we associate with human thinking, activities such
as decision-making, problem solving, learning…”
AI is : The study of agents that receive percepts from the environment and perform
actions
Foundation of AI is based on
Computer Science
Engineering
Mathematics
Neuroscience
Control Theory
Linguistics
Capabilities of AI :
AI is programming the computer to have the following capabilities.
 ● Natural language processing - To enable it to communicate successfully in
English
● Knowledge representation - It is the field of AI to represent information about
the world in a form that a computer system can utilize to solve complex tasks such
as diagnosing a medical condition or having a dialog in a natural language.
● Automated reasoning - To use stored information to answer questions and to
draw new conclusions.
● Machine learning - To adapt to new circumstances that provides computers with
the ability to learn without being explicitly programmed. Machine learning focuses
on the development of computer programs that can change when exposed to new
data.
AI Techniques:
● Gaming − AI plays an important role for machines to think of a
large number of possible positions based on deep knowledge in
strategic games. For example, chess, river crossing, N-queens
problems, etc.
● Natural Language Processing − Interact with the computer that
understands natural language spoken by humans.
● Expert Systems − Machine or software provide explanation and
advice to the users.
● Vision Systems − Systems understand, explain, and describe visual
input on the computer.
● Speech Recognition − There are some AI based speech recognition
systems that have the ability to hear and express sentences and
understand their meanings while a person talks to it. For example
Siri and Google assistant.
● Handwriting Recognition − The handwriting recognition software
reads the text written on paper and recognizes the shapes of the
letters and converts it into editable text.
● Intelligent Robots − Robots are able to perform the instructions
given by a human.
Major Goals
● Knowledge reasoning
● Planning
● Machine Learning
● Natural Language Processing
● Computer Vision
● Robotics
APPLICATIONS OF AI
Business : Financial strategies, give advice
Engineering : check design, offer suggestions to create new product
Manufacturing : Assembly, inspection, maintenance
Mining : used when conditions are dangerous
Hospital : monitoring, diagnosing & prescribing
Education : In teaching
household : Advice on cooking, shopping etc.
farming : prune trees & selectively harvest mixed crops
Artificial Intelligence has various applications in today's society. It is becoming
essential for today's time because it can solve complex problems in an efficient way in
multiple industries, such as Healthcare, entertainment, finance, education, etc. AI is
making our daily life more comfortable and faster.
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 has become more advantageous for the healthcare
industry and is 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 the patient before hospitalization.
3. AI in Gaming
● AI can be used for gaming purposes. 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
organize and manage massive amounts of data. AI can analyze 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 assistance 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.

PROBLEM SOLVING AGENTS

An agent is anything that can perceive its environment through sensors and acts
upon that environment through effectors.
● Human agent has sensory organs such as eyes, ears, nose, tongue and skin parallel
to the sensors and other organs such as hands, legs, mouth for effectors
● A robotic agent replaces cameras and infrared range finders for the sensors, and
various motors and actuators for effectors.
● A software agent has encoded bit strings and its programs and actions
AI is a rational agent. Rationality is concerned with expected actions and results
depending upon what the agent has perceived.
The reflex agents are known as the simplest agents because they directly map
states into actions. Unfortunately, these agents fail to operate in an environment where
the mapping is too large to store and learn. Goal-based agents, on the other hand,
consider future actions and the desired outcomes.
Here, we will discuss one type of goal-based agent known as a problem-solving
agent, which uses atomic representation with no internal states visible to the problem-
solving algorithms.
Problem-solving agent
The problem-solving agent performs precisely by defining problems and its
several solutions.
 According to psychology, “problem-solving refers to a state where we wish to
reach a definite goal from a present state or condition."
According to computer science, problem-solving is a part of artificial intelligence which
encompasses a number of techniques such as algorithms, heuristics to solve a problem.
Therefore, a problem-solving agent is a goal-driven agent and focuses on
satisfying the goal.
PROBLEM DEFINITION
To build a system to solve a particular problem, we need to do four things:
● Define the problem precisely. This definition must include specification of the
initial situations and also final situations which constitute (i.e.) acceptable solution
to the problem.
● Analyze the problem (i.e) important features have an immense (i.e) huge impact
on the appropriateness of various techniques for solving the problems.
● Isolate and represent the knowledge to solve the problem.
● Choose the best problem solving techniques and apply it to the particular problem.
Steps performed by Problem-solving agent
Goal Formulation: It is the first and simplest step in problem-solving. It organizes the
steps/sequence required to formulate one goal out of multiple goals as well as actions to
achieve that goal. Goal formulation is based on the current situation and the agent's
performance measure (discussed below).
Problem Formulation: It is the most important step of problem-solving which decides
what actions should be taken to achieve the formulated goal. There are following five
components involved in problem formulation:
● Initial State: It is the starting state or initial step of the agent towards its goal.
● Actions: It is the description of the possible actions available to the agent.
● Transition Model: It describes what each action does.
● Goal Test: It determines if the given state is a goal state.
● Path cost: It assigns a numeric cost to each path that follows the goal. The
problem-solving agent selects a cost function, which reflects its performance
measure.
An optimal solution has the lowest path cost among all the solutions.
Note: Initial state, actions, and transition model together define the state-space of the
problem implicitly. The state-space of a problem is a set of all states which can be
reached from the initial state followed by any sequence of actions. The state-space forms
a directed map or graph where nodes are the states, links between the nodes are actions,
and the path is a sequence of states connected by the sequence of actions.
Search: It identifies all the best possible sequence of actions to reach the goal state from
the current state. It takes a problem as an input and returns a solution as its output.
Solution: It finds the best algorithm out of various algorithms, which may be proven as
the best optimal solution.
Execution: It executes the best optimal solution from the searching algorithms to reach
the goal state from the current state.
Example Problems
Basically, there are two types of problem approaches:
Toy Problem: It is a concise and exact description of the problem which is used by the
researchers to compare the performance of algorithms.
Real-world Problem: It is real-world based problems which require solutions. Unlike a
toy problem, it does not depend on descriptions, but we can have a general formulation of
the problem.
Some Toy Problems
8 Puzzle Problem: Here, we have a 3×3 matrix with movable tiles numbered from 1 to 8
with a blank space. The tile adjacent to the blank space can slide into that space. The
objective is to reach a specified goal state similar to the goal state, as shown in the below
figure.
In the figure, our task is to convert the current state into goal state by sliding digits into
the blank space

In the above figure, our task is to convert the current(Start) state into goal state by sliding
digits into the blank space.
The problem formulation is as follows:
States: It describes the location of each numbered tile and the blank tile.
Initial State: We can start from any state as the initial state.
Actions: Here, actions of the blank space is defined, i.e., either left, right, up or down
Transition Model: It returns the resulting state as per the given state and actions.
Goal test: It identifies whether we have reached the correct goal-state.
Path cost: The path cost is the number of steps in the path where the cost of each step is
1.
Note: The 8-puzzle problem is a type of sliding-block problem which is used for testing
new search algorithms in artificial intelligence.
8-queens problem: The aim of this problem is to place eight queens on a chessboard in
an order where no queen may attack another. A queen can attack other queens either
diagonally or in the same row and column. From the following figure, we can understand
the problem as well as its correct solution.
It is noticed from the above figure that each queen is set into the chessboard in a position
where no other queen is placed diagonally, in the same row or column. Therefore, it is
one right approach to the 8-queens problem.
For this problem, there are two main kinds of formulation:
1. Incremental formulation: It starts from an empty state where the operator augments a
queen at each step.
Following steps are involved in this formulation:
States: Arrangement of any 0 to 8 queens on the chessboard.
Initial State: An empty chessboard
Actions: Add a queen to any empty box.
Transition model: Returns the chessboard with the queen added in a box.
Goal test: Checks whether 8-queens are placed on the chessboard without any attack.
Path cost: There is no need for path cost because only final states are counted.
In this formulation, there is approximately 1.8 x 1014 possible sequence to investigate.
2. Complete-state formulation: It starts with all the 8-queens on the chessboard and
moves them around, saving from the attacks.
Following steps are involved in this formulation
States: Arrangement of all the 8 queens one per column with no queen attacking the
other queen.
Actions: Move the queen at the location where it is safe from the attacks.
This formulation is better than the incremental formulation as it reduces the state space
from 1.8 x 1014 to 2057, and it is easy to find the solutions.
Some Real-world problems
Traveling salesperson problem(TSP): It is a touring problem where the salesman can
visit each city only once. The objective is to find the shortest tour and sell-out the stuff in
each city.
VLSI Layout problem: In this problem, millions of components and connections are
positioned on a chip in order to minimize the area, circuit-delays, stray-capacitances, and
maximizing the manufacturing yield.
The layout problem is split into two parts:
Cell layout: Here, the primitive components of the circuit are grouped into cells, each
performing its specific function. Each cell has a fixed shape and size. The task is to place
the cells on the chip without overlapping each other. the cells.
Channel routing: It finds a specific route for each wire through the gaps between Protein
Design: The objective is to find a sequence of amino acids which will fold into 3D
protein having a property to cure some disease.
Searching for solutions
We have seen many problems. Now, there is a need to search for solutions to solve them.
In this section, we will understand how searching can be used by the agent to solve a
problem. For solving different kinds of problems, an agent makes use of different
strategies to reach the goal by searching the best possible algorithms. This process of
searching is known as search strategy.

SEARCH STRATEGIES
There are two types of strategies that describe a solution for a given problem:
1. Uninformed Search (Blind Search)
This type of search strategy does not have any additional information about the
states except the information provided in the problem definition. They can only generate
the successors and distinguish a goal state from a non-goal state. This type of search does
not maintain any internal state, that's why it is also known as Blind search.
There are following types of uninformed searches:
● Breadth-first search
● Uniform cost search
● Depth-first search
● Depth-limited search
● Iterative deepening search
2. Informed Search (Heuristic Search)
This type of search strategy contains some additional information about the states
beyond the problem definition. This search uses problem-specific knowledge to find
more efficient solutions. This search maintains some sort of internal state via heuristic
functions (which provides hints), so it is also called heuristic search. There are following
types of informed searches:
● Best first search (Greedy search)
● A* search
Search Algorithm Terminologies:
1. Search: Searching is a step by step procedure to solve a search-problem in a given
search space. A search problem can have three main factors:
a. Search Space: Search space represents a set of possible solutions, which a system
may have.
b. Start State: It is a state from which the agent begins the search.
c. Goal test: It is a function which observes the current state and returns whether the
goal state is achieved or not.
2. Search tree: A tree representation of a search problem is called Search tree. The root
of the search tree is the root node which is corresponding to the initial state.
3. Actions: It gives the description of all the available actions to the agent.
4. Transition model: A description of what each action does, can be represented as a
transition model.
5. Path Cost: It is a function which assigns a numeric cost to each path.
6. Solution: It is an action sequence which leads from the start node to the goal node.
7. Optimal Solution: If a solution has the lowest cost among all solutions.
Properties of Search Algorithms:
Following are the four essential properties of search algorithms to compare the efficiency
of these algorithms:
● Completeness: A search algorithm is said to be complete if it guarantees to return a
solution if at least any solution exists for any random input.
● Optimality: If a solution found for an algorithm is guaranteed to be the best solution
(lowest path cost) among all other solutions, then such a solution is said to be an
optimal solution.
● Time Complexity: Time complexity is a measure of time for an algorithm to
complete its task.
● Space Complexity: It is the maximum storage space required at any point during the
search, as the complexity of the problem.

UNINFORMED SEARCH ALGORITHMS

Uninformed search is a class of general-purpose search algorithms which operates
in brute force-way. Uninformed search algorithms do not have additional information
about state or search space other than how to traverse the tree, so it is also called blind
search.
Following are the various types of uninformed search algorithms:
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:
● Breadth-first search is the most common search strategy for traversing a tree or
graph. This algorithm searches breadthwise in a tree or graph, so it is called
breadth-first search.
● The BFS algorithm starts searching from the root node of the tree and expands all
successor nodes at the current level before moving to nodes of the next level.
● The breadth-first search algorithm is an example of a general-graph search
algorithm.
● Breadth-first search implemented using FIFO queue data structure.
Advantages:
● BFS will provide a solution if any solution exists.
● If there are more than one solutions for a given problem, then BFS will provide the
minimal solution which requires the least number of steps.
Disadvantages:
● It requires lots of memory since each level of the tree must be saved into memory
to expand the next level.
● BFS needs lots of time if the solution is far away from the root node.
Example:
In the below tree structure, we have shown the traversing of the tree using BFS
algorithm from the root node S to goal node K. BFS search algorithm traverse in layers,
so it will follow the path which is shown by the dotted arrow, and the traversed path will
be:
1. S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
Time Complexity: Time Complexity of BFS algorithm can be obtained by the number of
nodes traversed in BFS until the shallowest Node. Where the d= depth of shallowest
solution and b is a node at every state.

Space Complexity: Space complexity of BFS algorithm is given by the Memory size of
frontier which is O(bd).
Completeness: BFS is complete, which means if the shallowest goal node is at some
finite depth, then BFS will find a solution.
Optimality: BFS is optimal if path cost is a non-decreasing function of the depth of the
node.
DEPTH-FIRST SEARCH
● Depth-first search is a recursive algorithm for traversing a tree or graph data
structure.
● It is called the depth-first search because it starts from the root node and follows
each path to its greatest depth node before moving to the next path.
● DFS uses a stack data structure for its implementation.
● The process of the DFS algorithm is similar to the BFS algorithm.
Note: Backtracking is an algorithm technique for finding all possible solutions using
recursion.
Advantage:
● DFS requires very less memory as it only needs to store a stack of the nodes on the
path from root node to the current node.
● It takes less time to reach the goal node than the BFS algorithm (if it traverses in
the right path).
Disadvantage:
 ● There is the possibility that many states keep re-occurring, and there is no
guarantee of finding the solution.
● DFS algorithm goes for deep down searching and sometime it may go to the
infinite loop.
Example:
In the below search tree, we have shown the flow of depth-first search, and it will
follow the order as:
Root node--->Left node ----> right node.
It will start searching from root node S, and traverse A, then B, then D and E, after
traversing E, it will backtrack the tree as E has no other successor and still goal node is
not found. After backtracking it will traverse node C and then G, and here it will
terminate as it found the goal node.