Ai Unit-I

R18 B.
Tech III YEAR II SEMESTER AIML
ARTIFICIAL INTELLIGENCE
UNIT – I
Problem Solving by Search - I

INTRODUCTION to AI:
In today's world, technology is growing very fast, and we are getting in touch with
different new technologies day by day.
Here, one of the booming technologies of computer science is Artificial Intelligence

which is ready to create a new revolution in the world by making intelligent
machines. The Artificial Intelligence is now all around us. It is currently working
with a variety of subfields, ranging from general to specific, such as self-driving
cars, playing chess, proving theorems, playing music, Painting, etc.
AI is one of the fascinating and universal fields of Computer science which has a
great scope in future. AI holds a tendency to cause a machine to work as a human.
Artificial Intelligence:
Artificial Intelligence is composed of two words Artificial and Intelligence, where

Artificial defines "man-made," i.e. made or produced by human beings rather
than occurring naturally, especially as a copy of something natural and intelligence
defines "thinking power", i.e. intelligence is the ability to acquire and apply
knowledge and skills. hence AI means "a man-made thinking power."
So, we can define AI as:
"It is a branch of computer science by which we can create intelligent

machines which can behave like a human, think like humans, and able to
make decisions."
Artificial Intelligence exists when a machine can have human-based skills such as
learning, reasoning, and solving problems
1 PREPARED BY: SETTI.NARESH KUMAR,M.Tech.,

R18 B.Tech III YEAR II SEMESTER AIML
With Artificial Intelligence you do not need to pre-program a machine to do some

work, despite that you can create a machine with programmed algorithms which
can work with own intelligence, and that is the awesomeness of AI.
You can say a machine, or a system is artificially intelligent when it is equipped with
at least one and at most all intelligences in it.
What is Intelligence Composed of?
The intelligence is intangible. It is composed of:
1. Reasoning
2. Learning
3. Problem Solving
4. Perception
5. Linguistic Intelligence

Let us go through all the components briefly:
1. Reasoning: It is the set of processes that enables us to provide basis for

judgement, making decisions, and prediction.
2. Learning: It is the activity of gaining knowledge or skill by studying,

practicing, being taught, or experiencing something. Learning enhances the
awareness of the subjects of the study. The ability of learning is possessed
by humans, some animals, and AI-enabled systems.
3. Problem solving: It is the process in which one perceives and tries to arrive
at a desired solution from a present situation by taking some path, which is
blocked by known or unknown hurdles. Problem solving also includes decision
making, which is the process of selecting the best suitable alternative out of
multiple alternatives to reach the desired goal are available.
4. Perception: It is the process of acquiring, interpreting, selecting, and

organizing sensory information. Perception presumes sensing. In humans,
perception is aided by sensory organs. In the domain of AI, perception
mechanism puts the data acquired by the sensors together in a meaningful
manner.
5. Linguistic Intelligence: It is one’s ability to use, comprehend, speak, and

write the verbal and written language. It is important in interpersonal
communication.
Difference between Human and Machine Intelligence:
➢ Humans perceive by patterns whereas the machines perceive by set of rules

and data.
➢ Humans store and recall information by patterns, machines do it by
searching algorithms. For example, the number 40404040 is easy to
remember, store and recall as its pattern is simple.
➢ Humans can figure out the complete object even if some part of it is missing
or distorted, whereas the machines cannot correctly.

Types of Artificial Intelligence:

When discussing artificial intelligence (AI), it is common to distinguish between two
broad categories:
1. weak AI and
2. strong AI.
Let's explore the characteristics of each type:
1.Weak AI (Narrow AI):
Weak AI refers to AI systems that are designed to perform specific tasks and are
limited to those tasks only. These AI systems excel at their designated functions
but lack general intelligence. Examples of weak AI include voice assistants like Siri
or Alexa, recommendation algorithms, and image recognition systems. Weak AI
operates within predefined boundaries and cannot generalize beyond their
specialized domain.
2. Strong AI (General AI):
Strong AI, also known as general AI, refers to AI systems that possess human-level
intelligence or even surpass human intelligence across a wide range of tasks.
Strong AI would be capable of understanding, reasoning, learning, and applying
knowledge to solve complex problems in a manner like human cognition. However,
the development of strong AI is still largely theoretical and has not been achieved
to date.
Why Artificial Intelligence?
Before Learning about Artificial Intelligence, we should know that what is the
importance of AI and why should we learn it. Following are some main reasons to
learn about AI:

o With the help of AI, you can create such software or devices which can solve
real-world problems very easily and with accuracy such as health issues,
marketing, traffic issues, etc.
o With the help of AI, you can create your personal virtual Assistant, such as
Cortana, Google Assistant, Siri, etc.
o With the help of AI, you can build such Robots which can work in an
environment where survival of humans can be at risk.
o AI opens a path for other new technologies, new devices, and new
Opportunities.
Goals of Artificial Intelligence:
Following are the main goals of Artificial Intelligence:
1. Replicate human intelligence
2. Solve Knowledge-intensive tasks
3. An intelligent connection of perception and action
4. Building a machine which can perform tasks that requires human intelligence
such as:
o Proving a theorem
o Playing chess
o Plan some surgical operation
o Driving a car in traffic
5. Creating some system which can exhibit intelligent behavior, learn new
things by itself, demonstrate, explain, and can advise to its user.

Advantages of Artificial Intelligence:

Following are some main advantages of Artificial Intelligence:
o High Accuracy with less errors: AI machines or systems are prone to less
errors and high accuracy as it takes decisions as per pre-experience or

information.
o High-Speed: AI systems can be of very high-speed and fast-decision
making, because of that AI systems can beat a chess champion in the Chess
game.
o High reliability: AI machines are highly reliable and can perform the same
action multiple times with high accuracy.
o Useful for risky areas: AI machines can be helpful in situations such as
defusing a bomb, exploring the ocean floor, where to employ a human can be
risky.
o Digital Assistant: AI can be very useful to provide digital assistant to the
users such as AI technology is currently used by various E-commerce

websites to show the products as per customer requirement.
o Useful as a public utility: AI can be very useful for public utilities such as a
self-driving car which can make our journey safer and hassle-free, facial
recognition for security purpose, Natural language processing to
communicate with the human in human-language, etc.
o Enhanced Security: AI can be very helpful in enhancing security, as It can
detect and respond to cyber threats in real time, helping companies protect
their data and systems.
o Aid in Research: AI is very helpful in the research field as it assists
researchers by processing and analyzing large datasets, accelerating

discoveries in fields such as astronomy, genomics, and materials science.

Disadvantages of Artificial Intelligence:

Every technology has some disadvantages, and the same goes for Artificial
intelligence. Being so advantageous technology still, it has some disadvantages
which we need to keep in our mind while creating an AI system. Following are the
disadvantages of AI:
o High Cost: The hardware and software requirement of AI is very costly as it

requires lots of maintenance to meet current world requirements.
o Can't think out of the box: Even we are making smarter machines with AI,
but still they cannot work out of the box, as the robot will only do that work
for which they are trained or programmed.
o No feelings and emotions: AI machines can be an outstanding performer,

but still it does not have the feeling so it cannot make any kind of emotional
attachment with human and may sometime be harmful for users if the proper
care is not taken.
o Increase dependency on machines: With the increment of technology,

people are getting more dependent on devices and hence they are losing
their mental capabilities.
o No Original Creativity: As humans are so creative and can imagine some

new ideas but still AI machines cannot beat this power of human intelligence
and cannot be creative and imaginative.
o Complexity: Making and keeping AI systems can be very complicated

and need a lot of knowledge. This can make it hard for some groups or
people to use them.
o Job Concerns: As AI gets better, it might take away not just basic
jobs but also some skilled ones. This worries people about losing jobs
in different fields.

Applications of Artificial Intelligence:
Artificial intelligence (AI) has a wide range of applications across various industries
and domains. Here are some notable applications of AI:
• Natural Language Processing (NLP)
AI is used in NLP to analyze and understand human language. It powers

applications such as speech recognition, machine translation, sentiment analysis,
and virtual assistants like Siri and Alexa.
• Image and Video Analysis
AI techniques, including computer vision, enable the analysis and interpretation of

images and videos. This finds application in facial recognition, object detection and
tracking, content moderation, medical imaging, and autonomous vehicles.
• Robotics and Automation
AI plays a crucial role in robotics and automation systems. Robots equipped with AI
algorithms can perform complex tasks in manufacturing, healthcare, logistics, and
exploration. They can adapt to changing environments, learn from experience, and
collaborate with humans.
• Recommendation Systems
AI-powered recommendation systems are used in e-commerce, streaming

platforms, and social media to personalize user experiences. They analyze user
preferences, behavior, and historical data to suggest relevant products, movies,
music, or content.

• Financial Services
AI is extensively used in the finance industry for fraud detection, algorithmic

trading, credit scoring, and risk assessment. Machine learning models can analyze
vast amounts of financial data to identify patterns and make predictions.
• Healthcare
AI applications in healthcare include disease diagnosis, medical imaging analysis,

drug discovery, personalized medicine, and patient monitoring. AI can assist in
identifying patterns in medical data and provide insights for better diagnosis and
treatment.
• Virtual Assistants and Chatbots
AI-powered virtual assistants and chatbots interact with users, understand their
queries, and provide relevant information or perform tasks. They are used in
customer support, information retrieval, and personalized assistance.
• Gaming
AI algorithms are employed in gaming for creating realistic virtual characters,

opponent behavior, and intelligent decision-making. AI is also used to optimize
game graphics, physics simulations, and game testing.
• Smart Homes and IoT
AI enables the development of smart home systems that can automate tasks,
control devices, and learn from user preferences. AI can enhance the functionality
and efficiency of Internet of Things (IoT) devices and networks.

• Cybersecurity
AI helps in detecting and preventing cyber threats by analysing network traffic,

identifying anomalies, and predicting potential attacks. It can enhance the security
of systems and data through advanced threat detection and response mechanisms.
Examples of Artificial Intelligence (AI):
Artificial Intelligence (AI) has become an integral part of our daily lives,
revolutionizing various industries and enhancing user experiences. Here are
some notable examples of AI applications:
ChatGPT
ChatGPT is an advanced language model developed by OpenAI, capable of

generating human-like responses and engaging in natural language
conversations. It uses deep learning techniques to understand and generate
coherent text, making it useful for customer support, chatbots, and virtual
assistants.
Google Maps
Google Maps utilizes AI algorithms to provide real-time navigation, traffic

updates, and personalized recommendations. It analyzes vast amounts of
data, including historical traffic patterns and user input, to suggest the
fastest routes, estimate arrival times, and even predict traffic congestion.

Smart Assistants
Smart assistants like Amazon's Alexa, Apple's Siri, and Google Assistant
employ AI technologies to interpret voice commands, answer questions, and
perform tasks. These assistants use natural language processing and
machine learning algorithms to understand user intent, retrieve relevant
information, and carry out requested actions.
Snapchat Filters
Snapchat's augmented reality filters, or "Lenses," incorporate AI to

recognize facial features, track movements, and overlay interactive effects
on users' faces in real-time. AI algorithms enable Snapchat to apply various
filters, masks, and animations that align with the user's facial expressions
and movements.
Self-Driving Cars
Self-driving cars rely heavily on AI for perception, decision-making, and

control. Using a combination of sensors, cameras, and machine learning
algorithms, these vehicles can detect objects, interpret traffic signs, and
navigate complex road conditions autonomously, enhancing safety and
efficiency on the roads.
Wearables
Wearable devices, such as fitness trackers and smartwatches, utilize AI to

monitor and analyze users' health data. They track activities, heart rate,

sleep patterns, and more, providing personalized insights and

recommendations to improve overall well-being.
MuZero
MuZero is an AI algorithm developed by DeepMind that combines

reinforcement learning and deep neural networks. It has achieved
remarkable success in playing complex board games like chess, Go, and
shogi at a superhuman level. MuZero learns and improves its strategies
through self-play and planning.

Intelligent Agents
An AI system can be defined as the study of the rational agent and its environment.
In artificial intelligence, an agent is an independent computer program or system
or anything that is designed to perceive its environment, make decisions and take
actions to achieve a specific goal or set of goals. The agent operates
autonomously, meaning it is not directly controlled by a human operator.
An intelligent agent is an autonomous entity, The agents sense the environment

through sensors and act on their environment through actuators. An AI agent can
have mental properties such as knowledge, belief, intention, etc.
Sensors
Actuators
An intelligent agent may learn from the environment to achieve their goals. A
thermostat is an example of an intelligent agent.
Following are the main four rules for an AI agent:
o Rule 1: An AI agent must have the ability to perceive the environment.
o Rule 2: The environmental observations must be used to make decisions.
o Rule 3: The Decision should result in an action.

o Rule 4: The action taken by the AI agent must be rational. Rational actions
are actions that maximize performance and yield the best positive outcome.

An Agent runs in the cycle of perceiving, thinking, and acting. An agent can be:
o Human-Agent: A human agent has eyes, ears, and other organs which work
for sensors and hand, legs, vocal tract work for actuators.
o Robotic Agent: A robotic agent can have cameras, infrared range finder,
NLP for sensors and various motors for actuators.
o Software Agent: Software agent can have keystrokes, file contents as
sensory input and act on those inputs and display output on the screen.
Hence the world around us is full of agents such as thermostat, cell phone, camera,
and even we are also agents. Driverless cars and the Siri virtual assistant are
examples of intelligent agents in AI.
Before moving forward, we should first know about sensors, effectors, and
actuators.
Sensor: Sensor is a device which detects the change in the environment and sends
the information to other electronic devices. An agent observes its environment
through sensors.
Actuators: Actuators are the component of machines that converts energy into
motion. The actuators are only responsible for moving and controlling a system. An
actuator can be an electric motor, gears, rails, etc.
Effectors: Effectors are the devices which affect the environment. Effectors can be
legs, wheels, arms, fingers, wings, fins, and display screen.
Rational Agent:
A rational agent is an agent which has clear preference, models uncertainty, and
acts in a way to maximize its performance measure with all possible actions.
A rational agent is said to perform the right things. AI is about creating rational
agents to use for game theory and decision theory for various real-world scenarios.

For an AI agent, the rational action is most important because in AI reinforcement

learning algorithm, for each best possible action, agent gets the positive reward
and for each wrong action, an agent gets a negative reward.
Rationality:
The rationality of an agent is measured by its performance measure. Rationality can
be judged based on following points:
o Performance measure which defines the success criterion.
o Agent prior knowledge of its environment.
o Best possible actions that an agent can perform.
o The sequence of percepts.
Structure of an AI Agent
The task of AI is to design an agent program which implements the agent function.
The structure of an intelligent agent is a combination of architecture and agent
program. It can be viewed as:
1. Agent = Architecture + Agent program
Following are the main three terms involved in the structure of an AI agent:
Architecture: Architecture is machinery that an AI agent executes on.
Agent Function: Agent function is used to map a percept to an action.
f:P* → A
Agent program: Agent program is an implementation of agent function. An agent

program executes on the physical architecture to produce function f.

PEAS Representation:
PEAS is a type of model on which an AI agent works upon. When we define an AI
agent or rational agent, then we can group its properties under PEAS
representation model. Many AI Agents use the PEAS model in their structure It is
made up of four words:
o P: Performance measure
o E: Environment
o A: Actuators
o S: Sensors
Here performance measure is the objective for the success of an agent's behavior.
PEAS for self-driving cars:

Let's suppose a self-driving car then PEAS representation will be:
Performance: Safety, time, legal drive, comfort
Environment: Roads, other vehicles, road signs, pedestrian
Actuators: Steering, accelerator, brake, signal, horn
Sensors: Camera, GPS, speedometer, odometer, accelerometer, sonar.
PEAS for Vacuum cleaner.:
• Performance: Cleanliness and efficiency
• Environment: Rug, hardwood floor, living room
• Actuator: Brushes, wheels, vacuum bag
• Sensors: Dirt detection sensor, bump sensor

Example of Agents with their PEAS representation:
Agent Performance Environment Actuators Sensors

measure
1. Keyboard
o Healthy o Patient o Tests
Medical (Entry of
patient o Hospital o Treatments symptoms)
Diagnos
e o Minimized o Staff
cost
2.
o Cleanness o Room o Wheels o Camera
Vacuum
Cleaner o Efficiency o Table o Brushes o Dirt
o Battery life o Wood floor o Vacuum detection
Extractor sensor
o Security o Carpet
o Cliff
o Various
sensor
obstacles
o Bump
Sensor
o Infrared
Wall
Sensor
3. Part -
o Percentage o Conveyor o Jointed Arms o Camera
picking
Robot of parts in belt with o Hand o Joint
correct bins. parts, angle
o Bins sensors.

How to Improve the Performance of Intelligent Agents:
When tackling the issue of how to improve intelligent Agent performances,

all we need to do is ask ourselves, “How do we improve our performance in
a task?” The answer, of course, is simple. We perform the task, remember
the results, then adjust based on our recollection of previous attempts.
Artificial Intelligence Agents improve in the same way. The Agent gets better
by saving its previous attempts and states, learning how to respond better
next time. This place is where Machine Learning and Artificial Intelligence
meet.

Types of Agents in AI
Agents are often grouped into five classes based on their degree of perceived intelligence and
capability. all these agents can improve their performance and generate better action over time.
These are given below:
• Simple Reflex Agent
• Model-Based Reflex Agent
• Goal-Based Agents
• Utility-Based Agent
• Learning Agent
Simple Reflex Agent:
o The Simple reflex agents are the simplest agents. These agents take decisions based on the current
percepts and ignore the rest of the percept history.
o These agents only succeed in the fully observable environment.
o The Simple reflex agent does not consider any part of percepts history during their decision and action
process.
o The Simple reflex agent works on Condition-action rule, which means it maps the current state to action.
Such as a Room Cleaner agent, it works only if there is dirt in the room.
Problems for the straightforward reflex agent design approach:

• They have very limited intelligence.
• They do not have knowledge of non-perceptual parts of the current state.
• Mostly too big to get and to store.

• Not adaptive to changes within the environment.
Model-Based Reflex Agent:
o The Model-based agent can work in a partially observable environment and track the situation.
o A model-based agent has two important factors:
o Model: It is knowledge about "how things happen in the world," so it is called a Model-
based agent.
o Internal State: It is a representation of the current state based on percept history.
o These agents have the model, "which is knowledge of the world" and based on the model
they perform actions.
o Updating the agent state requires information about:
a. How the world evolves
b. How the agent's action affects the world.
There are some important points that we need to remember about model-based reflex agents:
• Unlike simple reflex agents that rely solely on the current percept, model-based reflex
agents consider a broader context.
• It can adapt its behavior based on changes in the environment or new information.
• The ability to reason, plan, and consider a wider context generally leads to improved
performance compared to simple reflex agents.
Goal-Based Agent:
o The knowledge of the current state environment is not always sufficient to decide for an agent
to what to do.
o The agent needs to know its goal which describes desirable situations.
o Goal-based agents expand the capabilities of the model-based agent by having the "goal"
information.
o They choose an action, so that they can achieve the goal.
o These agents may have to consider a long sequence of possible actions before deciding
whether the goal is achieved or not. Such considerations of different scenario are called
searching and planning, which makes an agent proactive.
There are some points about goal-based agent:

• They choose an action, in order that they will achieve the goal.
• These agents may need to consider an extended sequence of possible actions before
deciding whether the goal is achieved or not.
• Considerations of various scenarios are called searching and planning, which makes an
agent proactive.
• Once a plan of action is selected, the goal-based agent executes the actions in the
environment.
Utility-Based Agents:
o These agents are like the goal-based agent but provide an extra component of utility
measurement which makes them different by providing a measure of success at a given state.
o Utility-based agent act based not only goals but also the best way to achieve the goal.
o The Utility-based agent is useful when there are multiple possible alternatives, and an agent
must choose to perform the best action.
o The utility function maps each state to a real number to check how efficiently each action
achieves the goals.
There are some points about utility-based agents:

• These agents act based not only on goals but also on the simplest thanks to achieving
the goal.
• These agents are beneficial when there are multiple possible alternatives, and an agent
has got to prefer to perform the simplest action.
• The utility function maps each state to a true number to see how efficiently each action
achieves the goals.
• These agents aim to make rational decisions that maximize their expected utility.
Learning Agents:
o A learning agent in AI is the type of agent which can learn from its past experiences, or it has
learning capabilities.
o It starts to act with basic knowledge and then able to act and adapt automatically through
learning.
o A learning agent has mainly four conceptual components, which are:
a. Learning element: It is responsible for making improvements by learning from
environment.
b. Critic: Learning element takes feedback from critic which describes that how well the
agent is doing with respect to a fixed performance standard.
c. Performance element: It is responsible for selecting external action.
d. Problem generator: This component is responsible for suggesting actions that will
lead to new and informative experiences.
o Hence, learning agents can learn, analyze performance, and look for new ways to improve
the performance.
The Functions of an Artificial Intelligence Agent:
The functions of an agent in artificial intelligence are as follows:
• To resolve complex issues using intelligent machines.
• To decide what to do in a specific situation.
• To make conclusions and take decisions.
• The perception of dynamic environmental circumstances.
• Using logic to interpret perceptions.
• To try to change environmental conditions.
Uses of Agents:
Artificial Intelligence agents are used in various real-life applications.
Medical Evaluation:
• The surroundings are regarded as the patient.
• The sensor that collects information on the patient's complaints is a computer

keyboard.
• The intelligent agent uses this data to determine the best plan of action.
• Actuators used in healthcare include tests and therapies.

Automatic Vehicles:
• Various sensors are used in automatic vehicles to gather data from the
surroundings.
• These consist of radar, GPS, and cameras.
• The environment in these agents could consist of people, other cars, roads, or
road signs. Actions are started using a variety of devices. For instance, the car's
brakes are used to stop it. Self-driving vehicles operate better with the assistance
of intelligent agents.
Office Works Automation:
• The monotonous workplace tasks can be resolved using AI agents.
• Customer service and sales are two functional areas that have been automated.
• To cut operating expenses, some businesses have automated a few administrative

processes.
• Office efficiency has also been increased using intelligent agents.

Agent Environment in AI
An environment is everything in the world which surrounds the agent, but it is not a part of
an agent itself. An environment can be described as a situation in which an agent is present.
The environment is where agent lives, operate, and provide the agent with something to
sense and act upon it. An environment is mostly said to be non-feministic.
Features of Environment
As per Russell and Norvig, an environment can have various features from the point of view
of an agent:
1. Fully observable vs Partially Observable

2. Static vs Dynamic
3. Discrete vs Continuous
4. Deterministic vs Stochastic
5. Single-agent vs multi-agent
6. Episodic vs sequential
7. Known vs Unknown.
8. Accessible vs Inaccessible
1. Fully observable vs Partially Observable:
o For an agent sensor can sense or access the complete state of an environment at
each point of time then it is a fully observable environment, else it is partially
observable.
o A fully observable environment is easy as there is no need to maintain the internal
state to keep track history of the world.
o An agent with no sensors in all environments then such an environment is called
as unobservable.
2. Deterministic vs Stochastic:
o If an agent's current state and selected action can completely determine the next
state of the environment, then such environment is called a deterministic
environment.
o A stochastic environment is random in nature and cannot be determined completely
by an agent.
o In a deterministic, fully observable environment, agent does not need to worry about
uncertainty.
3. Episodic vs Sequential:
o In an episodic environment, there is a series of one-shot actions, and only the current
percept is required for the action.
o However, in Sequential environment, an agent requires memory of past actions to
determine the next best actions.
4. Single-agent vs multi-agent
o If only one agent is involved in an environment, and operating by itself then such an
environment is called single agent environment.
o However, if multiple agents are operating in an environment, then such an
environment is called a multi-agent environment.
o The agent design problems in the multi-agent environment are different from single
agent environment.
5. Static vs Dynamic:
o If the environment can change itself while an agent is deliberating then such
environment is called a dynamic environment else it is called a static environment.
o Static environments are easy to deal because an agent does not need to continue
looking at the world while deciding for an action.
o However, for dynamic environment, agents need to keep looking at the world at
each action.
o Taxi driving is an example of a dynamic environment whereas Crossword puzzles are
an example of a static environment.
6. Discrete vs Continuous:
o If in an environment there are a finite number of percepts and actions that can be
performed within it, then such an environment is called a discrete environment else
it is called continuous environment.
o A chess game comes under discrete environment as there is a finite number of
moves that can be performed.
o A self-driving car is an example of a continuous environment.
7. Known vs Unknown
o Known and unknown are not actually a feature of an environment, but it is an agent's
state of knowledge to perform an action.
o In a known environment, the results for all actions are known to the agent. While in
unknown environment, agent needs to learn how it works to perform an action.
o It is quite possible that a known environment to be partially observable and an
Unknown environment to be fully observable.
8. Accessible vs Inaccessible
o If an agent can obtain complete and accurate information about the state's
environment, then such an environment is called an Accessible environment else it
is called inaccessible.
o An empty room whose state can be defined by its temperature is an example of an
accessible environment.
o Information about an event on earth is an example of Inaccessible environment.
Turing Test in AI
o In 1950, Alan Turing introduced a test to check whether a machine can think like a
human or not, this test is known as the Turing Test. In this test, Turing proposed that
the computer can be said to be an intelligent if it can mimic human response under
specific conditions.
o Turing Test was introduced by Turing in his 1950 paper, "Computing Machinery and
Intelligence," which considered the question, "Can Machine think?"
The Turing test is based on a party game "Imitation game," with some modifications. This
game involves three players in which one player is Computer, another player is human
responder, and the third player is a human Interrogator, who is isolated from other two
players and his job are to find that which player is machine among two of them.
Consider, Player A is a computer, Player B is human, and Player C is an interrogator.
Interrogator is aware that one of them is machine, but he needs to identify this based on
questions and their responses.
The conversation between all players is via keyboard and screen so the result would not
depend on the machine's ability to convert words as speech.
The test result does not depend on each correct answer, but only how closely its responses
like a human answer. The computer is permitted to do everything possible to force a wrong
identification by the interrogator.
The questions and answers can be like:
Interrogator: Are you a computer?
PlayerA (Computer): No
Interrogator: Multiply two large numbers such as (256896489*456725896)
Player A: Long pause and give the wrong answer.
In this game, if an interrogator would not be able to identify which is a machine and which
is human, then the computer passes the test successfully, and the machine is said to be
intelligent and can think like a human.
"In 1991, the New York businessman Hugh Loebner announces the prize competition,
offering a $100,000 prize for the first computer to pass the Turing test. However, no AI
program to till date, come close to passing an undiluted Turing test".
Chatbots to attempt the Turing test:
ELIZA: ELIZA was a Natural language processing computer program created by Joseph
Weizenbaum. It was created to demonstrate the ability of communication between machine
and humans. It was one of the first chatterbots, which has attempted the Turing Test.
Parry: Parry was a chatterbot created by Kenneth Colby in 1972. Parry was designed to
simulate a person with Paranoid schizophrenia(most common chronic mental disorder).
Parry was described as "ELIZA with attitude." Parry was tested using a variation of the Turing
Test in the early 1970s.
Eugene Goostman: Eugene Goostman was a chatbot developed in Saint Petersburg in

2001. This bot has competed in the various number of Turing Test. In June 2012, at an event,
Goostman won the competition promoted as largest-ever Turing test content, in which it
has convinced 29% of judges that it was a human.Goostman resembled as a 13-year old
virtual boy.
The Chinese Room Argument:
There were many philosophers who really disagreed with the complete concept of Artificial
Intelligence. The most famous argument in this list was "Chinese Room."
In the year 1980, John Searle presented "Chinese Room" thought experiment, in his paper
"Mind, Brains, and Program," which was against the validity of Turing's Test. According to
his argument, "Programming a computer may make it to understand a language, but
it will not produce a real understanding of language or consciousness in a computer."
He argued that Machine such as ELIZA and Parry could easily pass the Turing test by
manipulating keywords and symbol, but they had no real understanding of language. So it
cannot be described as "thinking" capability of a machine such as a human.
Features required for a machine to pass the Turing test:
o Natural language processing: NLP is required to communicate with Interrogator in

general human language like English.
o Knowledge representation: To store and retrieve information during the test.
o Automated reasoning: To use the previously stored information for answering the
questions.
o Machine learning: To adapt new changes and can detect generalized patterns.
o Vision (For total Turing test): To recognize the interrogator actions and other
objects during a test.
o Motor Control (For total Turing test): To act upon objects if requested.
PROBLEM SOLVING AGENTS
PROBLEM-SOLVING APPROACH IN ARTIFICIAL INTELLIGENCE PROBLEMS
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 agent, on the other hand, considers
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 perfoms precisely by defining problems and its severalsolutions.
• According to psychology, “a problem-solving refers to a state where we

wish to reach toa definite goal from a present state or condition.”
• According to computer science, a problem-solving is a part of artificial
intelligence whichencompasses several 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:
(i) Define the problem precisely. This definition must include specification of
theinitial situations and also final situations which constitute (i.e) acceptable
solution to the problem.
(ii) Analyze the problem (i.e) important features have an immense (i.e) huge impact
onthe appropriateness of various techniques for solving the problems.
(iii) Isolate and represent the knowledge to solve the problem.
(iv) Choose the best problem – solving techniques and apply it to the
problem.
Steps performed by Problem-solving agent
• Goal Formulation: It is the first and simplest step in problem-solving. It organizesthe

steps/sequence required to formulate one goal out of multiple goals as well as
actions toachieve that goal. Goal formulation is based on the current situation and
the agent’sperformance 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. Remember, 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
problemimplicitly. State-space of a problem is a set of all states which can be reached from the
initial statefollowed by any sequence of actions. The state-space forms a directed map or graph
where nodesare 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 fromthe current state. It takes a problem as an input and returns
solution as its output.
• Solution: It finds the best algorithm out of various algorithms, which may be
proven as thebest optimal solution.
• Execution: It executes the best optimal solution from the searching algorithms
to reach thegoal 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 toyproblem, 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 theblank space.
In the above figure, our task is to convert the current(Start) state into goal state by
sliding digitsinto the blank space.
The problem formulation is as follows:

• States: It describes the location of each numbered tiles 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 testingnew 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 diagonallyor in 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 same row or column. Therefore, it is one right
approach tothe 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 queenat 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 themaround, 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 otherqueen.
• 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 x1014 to 2057, and it is easy to find the solutions.
Some Real-world problems
• Traveling salesperson problem (TSP): It is a touring problem where thesalesman

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 connectionsare
positioned on a chip 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 placethe cells on the chip without overlapping each other.
• Channel routing: It finds a specific route for each wire through the gaps between
the cells.
• 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 problem, an agent makes use of different strategies to
reach thegoal by searching the best possible algorithms. This process of searching is known
as search strategy.
Search Algorithms in Artificial Intelligence
Search algorithms are one of the most important areas of Artificial Intelligence. This topic will explain
all about the search algorithms in AI.
Problem-solving agents:
In Artificial Intelligence, Search techniques are universal problem-solving methods. Rational
agents or Problem-solving agents in AI mostly used these search strategies or algorithms to solve
a specific problem and provide the best result. Problem-solving agents are the goal-based agents
and use atomic representation. In this topic, we will learn various problem-solving search algorithms.
Search Algorithm Terminologies:
o 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 where agent begins the search.
c. Goal test: It is a function which observe the current state and returns whether the
goal state is achieved or not.
o Search tree: A tree representation of search problem is called Search tree. The root of the
search tree is the root node which is corresponding to the initial state.
o Actions: It gives the description of all the available actions to the agent.
o Transition model: A description of what each action do, can be represented as a transition
model.
o Path Cost: It is a function which assigns a numeric cost to each path.
o Solution: It is an action sequence which leads from the start node to the goal node.
o 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 for 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.
Types of search algorithms
Based on the search problems we can classify the search algorithms into uninformed (Blind search)
search and informed search (Heuristic search) algorithms.
Uninformed/Blind Search:
The uninformed search does not contain any domain knowledge such as closeness, the location of
the goal. It operates in a brute-force way as it only includes information about how to traverse the
tree and how to identify leaf and goal nodes. Uninformed search applies a way in which search tree
is searched without any information about the search space like initial state operators and test for
the goal, so it is also called blind search. It examines each node of the tree until it achieves the goal
node.
It can be divided into five main types:
o Breadth-first search
o Uniform cost search
o Depth-first search
o Iterative deepening depth-first search
o Bidirectional Search
Informed Search
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
than an uninformed search strategy. Informed search is also called a Heuristic search.
A heuristic is a way which might not always be guaranteed for best solutions but guaranteed to find
a good solution in reasonable time.
Informed search can solve much complex problem which could not be solved in another way.
An example of informed search algorithms is a traveling salesman problem.
1. Greedy Search
2. A* Search
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
1. Breadth-first Search:
o 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.
o BFS algorithm starts searching from the root node of the tree and expands all successor node
at the current level before moving to nodes of next level.
o The breadth-first search algorithm is an example of a general-graph search algorithm.
o Breadth-first search implemented using FIFO queue data structure.
Advantages:
o BFS will provide a solution if any solution exists.

o If there are more than one solution for a given problem, then BFS will provide the minimal
solution which requires the least number of steps.
Disadvantages:
o It requires lots of memory since each level of the tree must be saved into memory to expand
the next level.
o 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.
T (b) = 1+b2+b3+.......+ bd= O (bd)
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.
2. Depth-first Search
o Depth-first search isa recursive algorithm for traversing a tree or graph data structure.
o 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.
o DFS uses a stack data structure for its implementation.
o The process of the DFS algorithm is like the BFS algorithm.
Advantage:
o 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.
o It takes less time to reach to the goal node than BFS algorithm (if it traverses in the right
path).
Disadvantage:
o There is the possibility that many states keep re-occurring, and there is no guarantee of
finding the solution.
o DFS algorithm goes for deep down searching and sometimes 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 goal node.
Completeness: DFS search algorithm is complete within finite state space as it will expand every
node within a limited search tree.
Time Complexity: Time complexity of DFS will be equivalent to the node traversed by the algorithm.
It is given by:
Completeness: DFS search algorithm is complete within finite state space as it will expand every
node within a limited search tree.
Time Complexity: Time complexity of DFS will be equivalent to the node traversed by the algorithm.
It is given by:
T(n)= 1+ n2+ n3 +.........+ nm=O(nm)
Where, m= maximum depth of any node and this can be much larger than d (Shallowest
solution depth)
Space Complexity: DFS algorithm needs to store only single path from the root node, hence space
complexity of DFS is equivalent to the size of the fringe set, which is O(bm).
Optimal: DFS search algorithm is non-optimal, as it may generate many steps or high cost to reach
to the goal node.

Ai Unit-I

Uploaded by

Copyright:

Available Formats

Ai Unit-I

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Ai Unit-I

Uploaded by

Copyright:

Available Formats

R18 B.

Tech III YEAR II SEMESTER AIML

Problem Solving by Search - I

Here, one of the booming technologies of computer science is Artificial Intelligence

Artificial Intelligence is composed of two words Artificial and Intelligence, where

So, we can define AI as:

"It is a branch of computer science by which we can create intelligent

1 PREPARED BY: SETTI.NARESH KUMAR,M.Tech.,

With Artificial Intelligence you do not need to pre-program a machine to do some

What is Intelligence Composed of?

The intelligence is intangible. It is composed of:

2 PREPARED BY: SETTI.NARESH KUMAR,M.Tech.,

Let us go through all the components briefly:

1. Reasoning: It is the set of processes that enables us to provide basis for

2. Learning: It is the activity of gaining knowledge or skill by studying,

4. Perception: It is the process of acquiring, interpreting, selecting, and

5. Linguistic Intelligence: It is one’s ability to use, comprehend, speak, and

Difference between Human and Machine Intelligence:

➢ Humans perceive by patterns whereas the machines perceive by set of rules

3 PREPARED BY: SETTI.NARESH KUMAR,M.Tech.,

Types of Artificial Intelligence:

Let's explore the characteristics of each type:

1.Weak AI (Narrow AI):

2. Strong AI (General AI):

Why Artificial Intelligence?

4 PREPARED BY: SETTI.NARESH KUMAR,M.Tech.,

Goals of Artificial Intelligence:

Following are the main goals of Artificial Intelligence:

1. Replicate human intelligence

2. Solve Knowledge-intensive tasks

3. An intelligent connection of perception and action

o Plan some surgical operation

o Driving a car in traffic

5 PREPARED BY: SETTI.NARESH KUMAR,M.Tech.,

Advantages of Artificial Intelligence:

errors and high accuracy as it takes decisions as per pre-experience or

o High-Speed: AI systems can be of very high-speed and fast-decision

action multiple times with high accuracy.

o Useful for risky areas: AI machines can be helpful in situations such as

o Digital Assistant: AI can be very useful to provide digital assistant to the

users such as AI technology is currently used by various E-commerce

o Enhanced Security: AI can be very helpful in enhancing security, as It can

o Aid in Research: AI is very helpful in the research field as it assists

researchers by processing and analyzing large datasets, accelerating

6 PREPARED BY: SETTI.NARESH KUMAR,M.Tech.,

Disadvantages of Artificial Intelligence:

o High Cost: The hardware and software requirement of AI is very costly as it

o No feelings and emotions: AI machines can be an outstanding performer,

o Increase dependency on machines: With the increment of technology,

o No Original Creativity: As humans are so creative and can imagine some

o Complexity: Making and keeping AI systems can be very complicated

7 PREPARED BY: SETTI.NARESH KUMAR,M.Tech.,

Applications of Artificial Intelligence:

• Natural Language Processing (NLP)

AI is used in NLP to analyze and understand human language. It powers

• Image and Video Analysis

AI techniques, including computer vision, enable the analysis and interpretation of

• Robotics and Automation

AI-powered recommendation systems are used in e-commerce, streaming