UNIT-I-AI-Notes From Sathyabama University

AI Notes From Unit 1

1. September 14, 2024 1
SCSA1702-Artificial Intelligence
UNIT-I

2. September 14, 2024 2
UNIT 1 INTRODUCTION AND PROBLEM SOLVING 9 Hrs.
Introduction – Foundations of AI – History of AI – Intelligent agent – Types of
agents - Structure – Problem solving agents – Uninformed search strategies –
Breadth first search – Uniform cost search – Depth first search – Depth limited
search – Bidirectional search – Searching with partial Information

3. September 14, 2024 3

4. September 14, 2024 4

5. September 14, 2024 5

6. September 14, 2024 6

7. September 14, 2024 7
Artificial Intelligence can also be defined as the development of computer
systems that are capable of performing tasks that require human intelligence,
such as decision making, object detection, solving complex problems and so
on.
The field of artificial intelligence, or AI, is concerned with not just understanding
but also building intelligent entities—machines that can compute how to act
effectively and safely in a wide variety of novel situations.

8. September 14, 2024 8

9. September 14, 2024 9

10. September 14, 2024 10

11. September 14, 2024 11

12. September 14, 2024 12

13. Why Artificial Intelligence?
Following are some main reasons to learn about AI:
•Create software or devices which can solve real-world problems
very easily and with accuracy such as health issues, marketing,
traffic issues, etc.
•Create personal virtual Assistant, such as Cortana, Google
Assistant, Siri, etc.
•Build Robots which can work in an environment where survival
of humans can be at risk.
•AI opens a path for other new technologies, new devices, and
new Opportunities.
September 14, 2024 13

14. Goals of Artificial Intelligence
•Replicate human intelligence
•Solve Knowledge-intensive tasks
•An intelligent connection of perception and action
•Building a machine which can perform tasks that requires
human intelligence such as:
–Proving a theorem
–Playing chess
–Plan some surgical operation
–Driving a car in traffic
•Creating system which exhibit intelligent behavior, learn new
things by itself, demonstrate, explain, and can advise to its
user.
September 14, 2024 14

15. September 14, 2024 15

16. Advantages of Artificial Intelligence
•High Accuracy with less error:
–AI machines or systems are prone to less errors and high
accuracy as it takes decisions as per pre-experience or
information.
•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.
•High reliability:
–AI machines are highly reliable and can perform the same
action multiple times with high accuracy.
September 14, 2024 16

17. Advantages of Artificial Intelligence
•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.
•Digital Assistant:
–used by various E-commerce websites to show the
products as per customer requirement.
•Useful as a public utility:
–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.
September 14, 2024 17

18. Disadvantages of Artificial Intelligence
•High Cost:
–The hardware and software requirement of AI is very costly
as it requires lots of maintenance to meet current world
requirements.
•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.
•No feelings and emotions:
–Can be an outstanding performer, but still it does not have
the feeling so it cannot make any kind of emotional
attachment with human,
–harmful for users if the proper care is not taken.
September 14, 2024 18

19. Disadvantages of Artificial Intelligence
•Increase dependency on machines:
–With the increment of technology, people are getting more
dependent on devices and hence they are losing their
mental capabilities.
•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.
September 14, 2024 19

20. Application of AI
September 14, 2024 20

21. Application of AI
1. AI in Astronomy
–AI technology can be helpful for understanding the
universe such as how it works, origin, etc.
2. AI in Healthcare
–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.
–AI uses the combination of historical data and medical
intelligence for the discovery of new drugs.
September 14, 2024 21

22. Application of AI
3. AI in Gaming
–The AI machines can play strategic games like chess, where
the machine needs to think of a large number of possible
places.
–AI can be used to create smart, human-like NPCs to
interact with the players.
–To predict human behavior using which game design and
testing can be improved. The Alien Isolation games
released in 2014 uses AI to stalk the player throughout the
game. The game uses two Artificial Intelligence systems -
‘Director AI’ that frequently knows your location and the
‘Alien AI,’ driven by sensors and behaviors that
continuously hunt the player.
September 14, 2024 22

23. Application of AI
4. AI in Finance
•o 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.
•80% of banks recognize the benefits that AI can provide.
•Customers get the information they need through SMS text
messaging or online chat, all AI-powered.
•Artificial intelligence can also detect changes in transaction
patterns and other potential red flags that can signify fraud,
which humans can easily miss, and thus saving businesses and
individuals from significant loss.
•AI can also better predict and assess loan risks.
September 14, 2024 23

24. Application of AI
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 bug and cyber-attacks in a better way.
6. AI in Social Media
–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, hashtag, and
requirement of different users.
–DeepText tool, Facebook can understand conversations better. It
can be used to translate posts from different languages
automatically.
September 14, 2024 24

25. Application of AI
7. AI in Travel & Transport
–Travel arrangement 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
fast response.
8. AI in Automotive Industry
–To provide virtual assistant to their user for better
performance. Such as Tesla has introduced TeslaBot, an
intelligent virtual assistant.
–AI can be used along with the vehicle’s camera, radar, cloud
services, GPS, and control signals to operate the vehicle. AI can
improve the in-vehicle experience and provide additional
systems like emergency braking, blind-spot monitoring, and
driver-assist steering.
September 14, 2024 25

26. Application of AI
9. AI in Robotics:
–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 pre-programmed.
–Humanoid Robots are best examples for AI in robotics, Eg.
Erica and Sophia has been developed which can talk and
behave like humans.
–Robots powered by AI use real-time updates to sense
obstacles in its path and pre-plan its journey instantly.
 
–Used for carrying goods in hospitals, factories, and
warehouses, Cleaning offices and large equipment,nventory
management.
September 14, 2024 26

27. Application of AI
10. AI in Entertainment
–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 result.
–Agriculture is applying AI as agriculture robotics, solid and
crop monitoring, predictive analysis. AI in agriculture can be
very helpful for farmers.
–Identify defects and nutrient deficiencies in the soil. This is
done using computer vision, robotics, and machine learning
applications,
–AI can analyze where weeds are growing. AI bots can help to
harvest crops at a higher volume and faster pace than human
laborers.
September 14, 2024 27

28. Application of AI
12. AI in E-commerce
–Personalized Shopping- create recommendation engines
through which you can engage better with your customers-
made in accordance with their browsing history, preference,
and interests. It helps in improving your relationship with
your customers and their loyalty towards your brand.
–AI-powered Assistants-Virtual shopping assistants and
chatbots help improve the user experience while shopping
online. Natural Language Processing is used to make the
conversation sound as human and personal as possible.
–Fraud Prevention-Credit card frauds and fake reviews are
two of the most significant issues that E-Commerce
companies deal with. Many customers prefer to buy a
product or service based on customer reviews. AI can help
identify and handle fake reviews.
 
September 14, 2024 28

29. Application of AI
13. AI in education:
•Personalized Learning- to monitor students’ data thoroughly,
and habits, lesson plans, reminders, study guides, flash notes,
frequency or revision, etc., can be easily generated.
•Voice Assistants-Without even the direct involvement of the
lecturer, a student can access extra learning material or
assistance through Voice Assistants.
•Creating Smart Content-Digitization of content like video
lectures, conferences, and text book guides. Artificial
Intelligence helps create a rich learning experience by
generating and providing audio and video summaries and
integral lesson plans.
September 14, 2024 29

30. Application of AI
14. AI in Navigation
–Based on research from MIT, GPS technology can provide
users with accurate, timely, and detailed information to
improve safety.
–A combination of Convolutional Neural Network and Graph
Neural Network, which makes lives easier for users by
automatically detecting the number of lanes and road
types behind obstructions on the roads.
–AI is heavily used by Uber and many logistics companies to
improve operational efficiency, analyze road traffic, and
optimize routes.
September 14, 2024 30

31. September 14, 2024 31

32. Types of Artificial Intelligence
September 14, 2024 32

33. Type-1
September 14, 2024 33

34. Type-2
1. Reactive Machines
–Purely reactive machines are the most basic types of
Artificial Intelligence.
–Such AI systems do not store memories or past experiences
for future actions.
–These machines only focus on current scenarios and react
on it as per possible best action.
–IBM's Deep Blue system is an example of reactive machines.
Google's AlphaGo is also an example of reactive machines.
September 14, 2024 34

35. Type-2
2. Limited Memory
–Limited memory machines can store past experiences or
some data for a short period of time.
–These machines can use stored data for a limited time
period only.
–Self-driving cars are one of the best examples of Limited
Memory systems. These cars can store recent speed of
nearby cars, the distance of other cars, speed limit, and
other information to navigate the road.
September 14, 2024 35

36. Type-2
3. Theory of Mind
–Theory of Mind AI should understand the human emotions,
people, beliefs, and be able to interact socially like humans.
–This type of AI machines is still not developed, but
researchers are making lots of efforts and improvement for
developing such AI machines.
4. Self-Awareness
–Self-awareness AI is the future of Artificial Intelligence.
These machines will be super intelligent, and will have their
own consciousness, sentiments, and self-awareness.
–These machines will be smarter than human mind.
–Self-Awareness AI does not exist in reality still and it is a
hypothetical concept.
September 14, 2024 36

37. September 14, 2024 37

38. September 14, 2024 38

39. Agents in Artificial Intelligence
•An AI system can be defined as the study of the
rational agent and its environment.
•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.
September 14, 2024 39

40. Intelligent Agent
•An intelligent agent is a program that can make decisions or
perform a service based on its environment, user input and
experiences.
•These programs can be used to autonomously gather
information on a regular, programmed schedule or when
prompted by the user in real time.
•Intelligent agents may also be referred to as a bot, which is
short for robot.
September 14, 2024 40

41. •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.
September 14, 2024 41

42. Agent
•An Agent is anything that can be viewed as perceiving its
environment through sensors and acting upon that
environment through actuators.
–A human agent has eyes, ears, and other organs for sensors
and hands, legs, mouth, and other body parts for actuators.
–A robotic agent might have cameras and infrared range
finders for sensors and various motors for actuators.
–A software agent receives file contents, network packets,
and human input (keyboard/mouse/touch screen/voice) as
sensory inputs and acts on the environment by writing files,
sending network packets, and displaying information or
generating sounds.
September 14, 2024 42

43. Rules for an AI agent
•Rule 1: An AI agent must have the ability to perceive the
environment.
•Rule 2: The observation must be used to make decisions.
•Rule 3: Decision should result in an action.
•Rule 4: The action taken by an AI agent must be a rational
action.
September 14, 2024 43

44. Agents Terminology
•Performance Measure of Agent: It is the criteria, which
determines how successful an agent is.
•Behavior of Agent: It is the action that agent performs after
any given sequence of percepts.
•Percept: It is agent’s perceptual inputs at a given instance.
•Percept Sequence: It is the history of all that an agent has
perceived till date.
•Agent Function: It is a map from the precept sequence to an
action.
September 14, 2024 44

45. Example
•The vacuum-cleaner world, which consists of a robotic
vacuum-cleaning agent in a world consisting of squares that
can be either dirty or clean.
•The vacuum agent perceives which square it is in and whether
there is dirt in the square. The agent starts in square A.
•The available actions are to move to the right, move to the
left, suck up the dirt, or do nothing.
•One very simple agent function is the following:
if the current square is dirty, then suck; otherwise, move to the other
square.
September 14, 2024 45

46. September 14, 2024 46

47. Good Behavior: The Concept of
Rationality
•Rationality means status of being reasonable, sensible, and
having good sense of judgment.
•Rationality is concerned with expected actions and results
depending upon what the agent has perceived.
•Performing actions with the aim of obtaining useful
information is an important part of rationality.
September 14, 2024 47

48. What is Ideal Rational Agent?
•Rationality of an agent depends on the following:
1. The performance measures, which determine the degree
of success.
2. The agent’s prior knowledge about the environment.
3. The actions that the agent can carry out.
4. Agent’s Percept Sequence till now.
•An ideal rational agent is the one, which is capable of doing
expected actions to maximize its performance measure, on
the basis of:
–Its percept sequence
–Its built-in knowledge base
September 14, 2024 48

49. The Nature of Environments
•A rational agent always performs right action, where the right
action means the action that causes the agent to be most
successful in the given percept sequence.
•The problem the agent solves is characterized by Performance
Measure, Environment, Actuators, and Sensors (PEAS).
September 14, 2024 49

50. Example
September 14, 2024 50

51. Example
September 14, 2024 51

52. Properties of task environments
•To solve AI problems, we need to classify the task
environment (the environment that surrounds the agent).
•The task environments can be:
​

–Fully observable / Partially observable
​
–Single agent / Multiple agents
​
–Deterministic / Non-deterministic
​
–Episodic / Non-episodic
​
–Static / Dynamic
​
–Discrete / Continuous
​
–Known / Unknown
​
September 14, 2024 52

53. 1. Fully observable vs Partially Observable:
–If 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.
–A fully observable environment is easy as there is no need
to maintain the internal state to keep track history of the
world.
–An agent with no sensors in all environments then such an
environment is called as unobservable.
Examples: 
Chess – the board is fully observable, and so are the
opponent’s moves.
Driving – the environment is partially observable because
what’s around the corner is not known.
September 14, 2024 53

54. 2. Single-agent vs Multi-agent 
–An environment consisting of only one agent is said to be a
single-agent environment.
–An environment involving more than one agent is a multi-
agent environment.
–For example, an agent solving a crossword puzzle by itself
is clearly in a single-agent environment, whereas an agent
playing chess is a two agent environment.
–The game of football is multi-agent as it involves 11 players
in each team.
September 14, 2024 54

55. •Competitive vs Collaborative
–An agent is said to be in a competitive environment when
it competes against another agent to optimize the output.
–The game of chess is competitive as the agents compete
with each other to win the game which is the output.
–An agent is said to be in a collaborative environment when
multiple agents cooperate to produce the desired output.
–When multiple self-driving cars are found on the roads,
they cooperate with each other to avoid collisions and
reach their destination which is the output desired.
–It is also partially competitive because, for example, only
one car can occupy a parking space.
September 14, 2024 55

56. 3. Deterministic vs Stochastic:
–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.
–A stochastic environment is random in nature and cannot
be determined completely by an agent.
–In a deterministic, fully observable environment, agent
does not need to worry about uncertainty.
Examples:
Chess – there would be only a few possible moves for a coin
at the current state and these moves can be determined.
Self-Driving Cars- the actions of a self-driving car are not
unique, it varies time to time.
September 14, 2024 56

57. 4. Episodic vs Sequential:
•In an episodic environment, the agent’s experience is divided
into atomic episodes. In each episode the agent receives a
percept and then performs a single action.
•Example: Pick and Place robot, which is used to detect
defective parts from the conveyor belts. Here, every time
robot(agent) will make the decision on the current part i.e.
there is no dependency between current and previous
decisions.
•In Sequential environment, an agent requires memory of past
actions to determine the next best actions. The current decision
could affect all future decisions.
•Example: Chess and taxi driving are sequential: in both cases,
short-term actions can have long-term consequences.
September 14, 2024 57

58. 5. Dynamic vs Static 
–An environment that keeps constantly changing itself
when the agent is up with some action is said to be
dynamic.
Eg.A roller coaster ride is dynamic as it is set in motion and the
environment keeps changing every instant. Taxi driving is clearly
dynamic. Taxi driving is clearly dynamic.
–An idle environment with no change in its state is called a
static environment.
Eg.An empty house is static as there’s no change in the
surroundings when an agent enters. Crossword puzzles are
static.
–If the environment itself does not change with the passage
of time but the agent’s performance score does, then we
say the environment is Semidynamic.
Eg.Chess, when played with a clock,is semidynamic.
September 14, 2024 58

59. 6. Discrete vs. continuous:
•If an environment consists of a finite number of actions that
can be deliberated in the environment to obtain the output, it
is said to be a discrete environment.
Eg.The game of chess is discrete as it has only a finite number
of moves. The number of moves might vary with every game,
but still, it’s finite.
•The environment in which the actions are performed cannot
be numbered i.e. is not discrete, is said to be continuous.
Eg.Self-driving cars are an example of continuous
environments as their actions are driving, parking, etc. which
cannot be numbered.
September 14, 2024 59

60. 7. Known vs Unknown
 
•In a known environment, the output for all probable actions is
given.
Eg. In solitaire card games, I know the rules but am still unable
to see the cards that have not yet been turned over.
•In an unknown environment, the agent will have to learn how
it works in order to make good decisions.
Eg. In a new video game, the screen may show the entire
game state but I still don’t know what the buttons do until I
try them.
September 14, 2024 60

61. Examples
September 14, 2024 61
The hardest case is partially observable, multiagent, nondeterministic,
sequential, dynamic, continuous, and unknown. Taxi driving is hard in all
these senses, except that the driver’s environment is mostly known. Driving
a rented car in a new country with unfamiliar geography, different traffic
laws, and nervous passengers is a lot more exciting.

62. The Structure of Intelligent Agents
Agent’s structure can be viewed as:
Agent = Architecture + Agent Program
–Architecture = the machinery that an agent executes on.
–Agent Function: Agent function is used to map a percept to
an action.
f: P* → A
–Agent Program = an implementation of an agent function. An
agent program executes on the physical architecture to
produce function f.
September 14, 2024 62

63. PEAS Representation
•PEAS is a type of model on which an AI agent works upon. An
AI agent or rational agent, can group its properties under
PEAS representation model. It is made up of four words:
–P: Performance measure
–E: Environment
–A: Actuators
–S: Sensors
•The performance measure is the objective for the success of
an agent's behavior.
September 14, 2024 63

64. Types of AI Agents
•Agents can be grouped into five classes based on their degree
of perceived intelligence and capability.
–Simple Reflex Agent
–Model-based reflex agent
–Goal-based agents
–Utility-based agent
–Learning agent
September 14, 2024 64

65. Simple Reflex Agent
September 14, 2024 65
Schematic diagram of a simple reflex agent. We use rectangles to denote the
current internal state of the agent’s decision process, and ovals to represent
the background information used in the process.

66. •The Simple reflex agents are the simplest agents. These
agents take decisions on the basis of the current
percepts and ignore the rest of the percept history.
•These agents only succeed in the fully observable
environment.
•The Simple reflex agent does not consider any part of
percepts history during their decision and action process.
•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.
September 14, 2024 66

67. September 14, 2024 67
INTERRUPT-INPUT – function generates an abstracted description of
the current state from the percept.
RULE-MATCH – function returns the first rule in the set of rules that
matches the given state description.
RULE-ACTION – the selected rule is executed as action of the given
percept.
Example: Medical diagnosis system
If the patient has reddish brown spots then start the treatment for
measles.

68. Problems with Simple reflex agents are :
 
•Very limited intelligence.
•No knowledge of non-perceptual parts of the state.
•Too big to generate and store.
•If there occurs any change in the environment, then the
collection of rules need to be updated.
September 14, 2024 68

69. Model-based reflex agent
September 14, 2024 69

70. •The Model-based agent can work in a partially observable
environment, and track the situation.
•A model-based agent has two important factors:
–Model: It is knowledge about "how things happen in the
world," so it is called a Model-based agent.
–Internal State: It is a representation of the current state based
on percept history.
•These agents have the model, "which is knowledge of the world"
and based on the model they perform actions.
•Updating the agent state requires information about:
•a. How the world evolves
•b. How the agent's action affects the world.
September 14, 2024 70

71. September 14, 2024 71

72. Goal-based agents
September 14, 2024 72
A model-based, goal-based agent. It keeps track of the world state as well as a
set of goals it is trying to achieve, and chooses an action that will (eventually)
lead to the achievement of its goals.

73. •The knowledge of the current state environment is not always
sufficient to decide for an agent to what to do.
•The agent needs to know its goal which describes desirable
situations.
•Goal-based agents expand the capabilities of the model-based
agent by having the "goal" information. They choose an
action, so that they can achieve the goal.
•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.
September 14, 2024 73

74. Utility-based agents
September 14, 2024 74

75. •These agents are similar to 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.
•Utility-based agent act based not only goals but also the best
way to achieve the goal.
•The Utility-based agent is useful when there are multiple
possible alternatives, and an agent has to choose in order to
perform the best action.
•The utility function maps each state to a real number to check
how efficiently each action achieves the goals.
September 14, 2024 75

76. Learning agents
September 14, 2024 76

77. •A learning agent in AI is the type of agent which can learn from its
past experiences- starts to acts with basic knowledge and then
able to act and adapt automatically through learning.
•A learning agent has mainly four conceptual components, which
are:
–Learning element: It is responsible for making improvements
by learning from environment
–Critic: Learning element takes feedback from critic which
describes that how well the agent is doing with respect to a
fixed performance standard.
–Performance element: It is responsible for selecting external
action
–Problem generator: This component is responsible for
suggesting actions that will lead to new and informative
experiences.
•Hence, learning agents are able to learn, analyze performance, and
look for new ways to improve the performance.
September 14, 2024 77

78. Problem solving agents
•When the correct action to take is not immediately obvious,
an agent may need to plan ahead: to consider a sequence of
actions that form a path to a goal state.
•Such an agent is called a problem-solving agent, and the
computational process it undertakes is called search.
•Next….
•Consider only the simplest environments: episodic, single
agent, fully observable, deterministic, static, discrete, and
known.
•Distinguish between informed algorithms, in which the agent
can estimate how far it is from the goal, and uninformed
algorithms, where no such estimate is available.
September 14, 2024 78

79. There are three types of problem in artificial
intelligence:
1.Ignorable: In which solution steps can be ignored.
2. Recoverable: In which solution steps can be undone.
3. Irrecoverable: Solution steps cannot be undo.
September 14, 2024 79

80. Steps for problem-solving in AI:
The problem of AI is directly associated with the nature of
humans and their activities. So we need a number of finite
steps to solve a problem which makes human easy works.
•Problem definition: Detailed specification of inputs and
acceptable system solutions.
•Problem analysis: Analyse the problem thoroughly.
•Knowledge Representation: collect detailed information
about the problem and define all possible techniques.
•Problem-solving: Selection of best techniques.
September 14, 2024 80

81. •Intelligent agents are supposed to maximize its performance
measure. Achieving this can be simplified if the agent can adopt a
goal and aim to satisfy it.
–Goal formulation - Setting goals help the agent organize its
behavior by limiting the objectives that the agent is trying to
achieve an
–Problem formulation - Consider the agent’s goal to be a set of
states. The agent’s task is to find out actions in the present and in
the future that could reach the goal state from the present state.
–The process of deciding what actions and states to consider, given a
goal.
–Search- the agent has to look for a sequence of actions that
reaches the goal. A search algorithm takes a problem as input and
returns a sequence of actions as output.
–Execution-After the search phase, the agent has to carry out the
actions that are recommended by the search algorithm.
September 14, 2024 81
Formulate — Search — Execute

82. Problems and Solutions
•What a problem is in terms of problem solving agents?
•The problem can be defined by five components:
–Initial State
–Actions
–Transition Model
–Goal Test
–Path Cost
September 14, 2024 82

83. •Initial State: This state requires an initial state for the problem
which starts the AI agent towards a specified goal. In this state
new methods also initialize problem domain solving by a
specific class.
•Action: This stage of problem formulation works with function
with a specific class taken from the initial state and all
possible actions done in this stage.
•Transition: This stage of problem formulation integrates the
actual action done by the previous action stage and collects
the final stage to forward it to their next stage.
September 14, 2024 83

84. •Goal test: This stage determines that the specified goal
achieved by the integrated transition model or not, whenever
the goal achieves stop the action and forward into the next
stage to determines the cost to achieve the goal.
 
•Path costing: This component of problem-solving numerical
assigned what will be the cost to achieve the goal. It requires
all hardware software and human working cost.
–Solution to a problem is an action sequence that leads from the
initial state to a goal state.
–Solution quality is measured by the path cost function, and an
optimal solution has the lowest path cost among all solutions
September 14, 2024 84

85. Example-Toy Problems
•The problem-solving approach has been applied to a vast array
of task environments.
•Standardized and real-world problems.
•A standardized problem is intended to illustrate or exercise
various problem-solving methods. It can be given a concise,
exact description and hence is suitable as a benchmark for
researchers to compare the performance of algorithms.
•A real-world problem, such as robot navigation, is one whose
solutions people actually use, and whose formulation is
idiosyncratic, not standardized, because, for example, each
robot has different sensors that produce different data.
September 14, 2024 85

86. •The state-space graph for the two-cell vacuum world. There are 8
states and three actions for each state: L = Left, R = Right, S = Suck.
September 14, 2024 86

87. •States:
–For the vacuum world, the objects are the agent and any
dirt.
–In the simple two-cell version, the agent can be in either of
the two cells, and each cell can either contain dirt or not, so
there are 2 *2* 2 = 8 states.
–In general, a vacuum environment with n cells has n* 2
n

states.
• Initial state: Any state can be designated as the initial state.
•Actions:
–In the two-cell world we defined three actions: Suck, move
Left, and move Right.
September 14, 2024 87

88. •Transition model:
–Suck removes any dirt from the agent’s cell; Forward
moves the agent ahead one cell in the direction it is facing,
unless it hits a wall, in which case the action has no effect.
–Backward moves the agent in the opposite direction, while
TurnRight and TurnLeft change the direction it is facing by
90.
• Goal states: The states in which every cell is clean.
• Action cost: Each action costs 1.
September 14, 2024 88

89. 8-Puzzle
September 14, 2024 89

90. Almost a solution to the 8-queens
September 14, 2024 90

91. Real-world problems
•Consider the airline travel problems that must be solved by a
travel-planning Web site:
• States: Each state obviously includes a location (e.g., an
airport) and the current time.
•Furthermore, because the cost of an action (a flight segment)
may depend on previous segments, their fare bases, and their
status as domestic or international, the state must record extra
information about these “historical” aspects.
• Initial state: The user’s home airport.
• Actions: Take any flight from the current location, in any seat
class, leaving after the current time, leaving enough time for
within-airport transfer if needed.
September 14, 2024 91

92. Real-world problems
•Transition model: The state resulting from taking a flight will
have the flight’s destination as the new location and the
flight’s arrival time as the new time.
•Goal state: A destination city. Sometimes the goal can be
more complex, such as “arrive at the destination on a nonstop
flight.”
• Action cost: A combination of monetary cost, waiting time,
flight time, customs and immigration procedures, seat quality,
time of day, type of airplane, frequent-flyer reward points,
and so on.
September 14, 2024 92

93. Examples
•The traveling salesperson problem (TSP) is a touring problem
in which each city must be visited exactly once. The aim is to
find the shortest tour.
•A VLSI layout problem requires positioning millions of
components and connections on a chip to minimize area,
minimize circuit delays, minimize stray capacitances, and
maximize manufacturing yield.
•Robot navigation-Rather than following a discrete set of
routes, a robot can move in a continuous space with an infinite
set of possible actions and states.
•Automatic assembly sequencing- the aim is to find an order in
which to assemble the parts of some object.
–If the wrong order is chosen, there will be no way to add some
part later in the sequence without undoing some of the work
already done.
September 14, 2024 93

94. A simple problem-solving agent
September 14, 2024 94

95. Search Algorithms
•A search algorithm takes a search problem as input and
returns a solution, or an indication of failure.
•Superimpose a search tree over the state space graph,
forming various paths from the initial state, trying to find a
path that reaches a goal state.
•Each node in the search tree corresponds to a state in the
state space and the edges in the search tree correspond to
actions.
•The root of the tree corresponds to the initial state of the
problem.
September 14, 2024 95

96. Search Algorithms
Distinction between the state space and the search tree.
–The state space describes the (possibly infinite) set of
states in the world, and the actions that allow transitions
from one state to another.
–The search tree describes paths between these states,
reaching towards the goal.
–The search tree may have multiple paths to any given
state, but each node in the tree has a unique path back to
the root (as in all trees).
September 14, 2024 96

97. September 14, 2024 97

98. Properties of Search Algorithms
1. Completeness –Is the algorithm guaranteed to find a
solution when there is one, and to correctly report failure when
there is not?

2. Optimality – Is the solution found guaranteed to be the best
(or lowest cost) solution if there exists more than one solution?
3. Time Complexity – How long does it take to find a solution?
This can be measured in seconds, or more abstractly by the
number of states and actions considered.
4. Space Complexity – The upper bound on the storage space
(memory) required at any point during the search, as a function
of the complexity of the problem.
September 14, 2024 98

99. Informed Search
•Informed search algorithms use domain knowledge-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
September 14, 2024 99

100. Uninformed search algorithms
•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.
•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
September 14, 2024 100

101. Breadth-first Search(BFS)
•Breadth-first search is the most common search strategy for
traversing a tree or graph. This algorithm searches breadth wise
in a tree or graph.
•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.
•The breadth-first search algorithm is an example of a general-
graph search algorithm.
•Breadth-first search implemented using FIFO queue data
structure.
September 14, 2024 101

102. Breadth-first search algorithm
September 14, 2024 102

103. Simple Steps of BFS
September 14, 2024 103

104. Example
•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:
S---> A--->B---->C--->D---->G--->H--->E---->F---->I---->K
September 14, 2024 104

105. Example-Graph
September 14, 2024 105

106. Breadth-first Search(BFS)
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.
September 14, 2024 106

107. Properties of BFS
•Completeness: If there is a solution, BFS is guaranteed to find
it. If there are multiple solutions, then a minimal solution will
be found.
•Optimality : Yes
•Time complexity : O(b
d
)
•Space complexity : O(b
d
)
–b - branching factor(maximum no of successors of any
node),
–d – Depth of the shallowest goal node
Maximum length of any path (m) in search space
September 14, 2024 107

108. Depth First Search (DFS)
•Depth-first search is a recursive algorithm for traversing a tree
or graph data structure.
•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.
September 14, 2024 108

109. Simple Algorithm of DFS
1. Create a variable called NODE-LIST and set it to initial state
2. Until a goal state is found or NODE-LIST is empty do
a. Remove the first element from NODE-LIST . If NODE-LIST
was empty, quit
b. For each way that each rule can match the state do:
i. Apply the rule to generate a new state
ii. If the new state is a goal state, quit and return this
state
iii. Otherwise, add the new state in front of NODE-LIST
September 14, 2024 109

110. Example
September 14, 2024 110
•Traversal of depth-first search follows :
Root node--->Left node ----> right node
•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.
S---> A--->B---->D--->E---->C--->G

111. Depth First Search (DFS)
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 to the goal node than 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.
September 14, 2024 111

112. Properties of DFS
•Completeness: For finite state spaces DFS is efficient and
complete, In infinite state spaces, DFS is not systematic, it can
get stuck into an infinite path. Thus, depth-first search is
incomplete.
•Optimality : Depth-first search is not cost-optimal; it returns
the first solution it finds, even if it is not cheapest.
•Time complexity : O(b
d
)
•Space complexity : O(bm )
–b - branching factor(maximum no of successors of any
node),
–m – Maximum Depth of the tree.
September 14, 2024 112

113. Depth-limited search (DLS)
•A depth-limited search algorithm is similar to depth-first
search with a predetermined limit.
•Depth-limited search can solve the drawback of the infinite
path in the Depth-first search.
•The node at the depth limit will treat as it has no successor
nodes further. Depth-limited search can be terminated with
two Conditions of failure:
–Standard failure value: It indicates that problem does not
have any solution.
–Cut off failure value: It defines no solution for the problem
within a given depth limit.
September 14, 2024 113

114. Algorithm
September 14, 2024 114

115. Example
September 14, 2024 115

116. When depth limited search fails
•Ignore Node 6 as it is below level limit. So, what would
happen if the desired node was 6?
–This is known as a cutoff failure. Our target exists, but it is
too deep for us to traverse.
•Suppose level limit was 3, and the desired node is 7. We could
traverse the whole tree without finding our result. This is
known as standard failure.
September 14, 2024 116

117. Properties of DLS
•Completeness: DLS search algorithm is complete if the
solution is above the depth-limit. Unfortunately, if we make a
poor choice for ℓ the algorithm will fail to reach the solution,
making it incomplete.
•Time Complexity: Time complexity of DLS algorithm is O(b
ℓ
).
ℓ-Depth Limit
•Space Complexity: Space complexity of DLS algorithm is
O(b×ℓ).
•Optimality: Depth-limited search can be viewed as a special
case of DFS (ℓ=∞) , and it is also not optimal even if ℓ>d.
September 14, 2024 117

118. Depth-limited search
Advantages:
•Depth-limited search is Memory efficient.
Disadvantages:
•Depth-limited search has a disadvantage of incompleteness.
•It may not be optimal if the problem has more than one
solution.
September 14, 2024 118

119. Uniform-cost Search Algorithm(UCS)
•Used for traversing a weighted tree or graph- comes into play
when a different cost is available for each edge.
•To find a path to the goal node which has the lowest
cumulative cost - expands nodes according to their path costs
from the root node.
•It can be used to solve any graph/tree where the optimal cost
is in demand.
•Implemented by the priority queue – It gives maximum
priority to the lowest cumulative cost.
•Uniform cost search is equivalent to BFS algorithm if the path
cost of all edges is the same.
•This algorithm is also known as Dijkstra‟s single-source
shortest algorithm.
September 14, 2024 119

120. Example
September 14, 2024 120

121. Example
September 14, 2024 121
Solution in next slide

122. Algorithm
September 14, 2024 122

123. Example
September 14, 2024 123

124. Properties
•Completeness:
–Uniform-cost search is complete, such as if there is a
solution, UCS will find it.
•Time Complexity:
–The worst-case time complexity of Uniform-cost search is
O(b
c/ε
).
–where,
 
ϵ -> is the lowest cost, c -> optimal cost
•Space Complexity:
–The same logic is for space complexity so, the worst-case
space complexity of Uniform-cost search is O(b
c/ε
).
•Optimal:
–Uniform-cost search is always optimal as it only selects a
path with the lowest path cost.
September 14, 2024 124

125. Uniform-cost Search Algorithm
Advantages:
–Uniform cost search is optimal because at every state the
path with the least cost is chosen.
Disadvantages:
–It does not care about the number of steps involve in
searching and only concerned about path cost. Due to
which this algorithm may be stuck in an infinite loop.
September 14, 2024 125

126. Iterative deepening depth-first Search
•The iterative deepening algorithm is a combination of DFS and
BFS algorithms.
• This search algorithm finds out the best depth limit and does
it by gradually increasing the limit until a goal is found.
•This algorithm performs depth-first search up to a certain
"depth limit", and it keeps increasing the depth limit after each
iteration until the goal node is found.
•The iterative search algorithm is useful uninformed search
when search space is large, and depth of goal node is
unknown.
September 14, 2024 126

127. Example
•IDDFS algorithm performs various iterations until it does not
find the goal node.
 
•1'st Iteration-----> A
2'nd Iteration----> A, B, C
3'rd Iteration------>A, B, D, E, C, F, G
4'th Iteration------>A, B, D, H, I, E, C, F, K, G
In the fourth iteration, the algorithm will find the goal node.
September 14, 2024 127

128. Example
September 14, 2024 128

129. Properties
•Completeness:
This algorithm is complete is if the branching factor is finite.
•Time Complexity:
Suppose b is the branching factor and depth is d then the
worst-case time complexity is
 
O(b
d
).
•Space Complexity:
The space complexity of IDDFS will be
 
O(bd).
•Optimal:
IDDFS algorithm is optimal if path cost is a non- decreasing
function of the depth of the node.
September 14, 2024 129

130. Iterative deepening depth-first Search
Advantages:
–It combines the benefits of BFS and DFS search algorithm
in terms of fast search and memory efficiency.
Disadvantages:
–The main drawback of IDDFS is that it repeats all the work
of the previous phase.
September 14, 2024 130

131. Algorithm
September 14, 2024 131

132.  Bidirectional Search Algorithm
•Bidirectional search algorithm runs two simultaneous
searches, one form initial state called as forward-search and
other from goal node called as backward-search, to find the
goal node.
•Bidirectional search replaces one single search graph with two
small subgraphs in which one starts the search from an initial
vertex and other starts from goal vertex. The search stops
when these two graphs intersect each other.
•Bidirectional search can use search techniques such as BFS,
DFS, DLS, etc.
September 14, 2024 132

133. Example
September 14, 2024 133
•This algorithm divides one graph/tree into two sub-graphs. It
starts traversing from node 1 in the forward direction and starts
from goal node 16 in the backward direction.
•The algorithm terminates at node 9 where two searches meet.

134. Bidirectional Search Algorithm
Advantages:
–Bidirectional search is fast.
–Bidirectional search requires less memory
Disadvantages:
–Implementation of the bidirectional search tree is difficult.
–In bidirectional search, one should know the goal state in
advance.
September 14, 2024 134

135. Properties
•Completeness: 
Bidirectional Search is complete if we use BFS
in both searches.
•Time Complexity: 
Time complexity of bidirectional search
using BFS is
 
O(b
d
).
•Space Complexity: 
Space complexity of bidirectional search
is
 
O(b
d
).
•Optimal: 
Bidirectional search is Optimal.
September 14, 2024 135

136. Questions?
1. Who is known as the -Father of AI"?
a. Fisher Ada
b. Alan Turing
c. John McCarthy
d. Allen Newell
2. The state-space of the problem includes
a. Initial state
b. Action
c. Transition model
d. All the above
3. An AI system is composed of
a. Agent
b. Environment
c. Agent and Environment
d. None of the above
September 14, 2024 136

137. Questions?
4. Agents can be grouped into classes based on their degree of perceived
a. Intelligence
b. Capability
c. Intelligence and capability
d. Performance
5. Which agent can work in a partially observable environment, and track the
situation?
a) Simple Reflex Agent
b) Model-based reflex agent
c) Goal-based agents
d) Utility-based agent
6. Which type of agent acts not only for goals but also for the best way to achieve the
goal?
a. Simple Reflex Agent
b. Model-based reflex agent
c. Goal-based agents
d. Utility-based agent
September 14, 2024 137

138. 7. Which agent is useful when there are multiple possible alternatives?
a. Simple Reflex Agent
b. Model-based reflex agent
c. Goal-based agents
d. Utility-based agent
8. Which type of agent works on Condition-action rule?
a. Simple Reflex Agent
b. Model-based reflex agent
c. Goal-based agents
d. Utility-based agent
9. Rationality can be judged on the basis of
a. Performance measure which defines the success criterion.
b. Agent prior knowledge of its environment.
c. The sequence of percepts.
d. All the above
10. Which device detects the change in the environment and sends the information to other
electronic devices?
a. Sensors
b. Actuators
c. Effectors
d. All the above
September 14, 2024 138

139. September 14, 2024 139
Thank You !!