Module 1
Text Book :
1. Reema Thareja, Artificial Intelligence: Beyond Classical AI, Pearson Education, 2023
I. Introduction to Artificial Intelligence
[Link] of Artificial Intelligence
[Link] Does AI Work?
[Link] and Disadvantages of Artificial Intelligence
[Link] of Artificial Intelligence
[Link] of Artificial Intelligence:
[Link] AI vs. Strong AI
[Link] Machines
[Link] Memory
[Link] of Mind
e. Self-Awareness
6. Is Artificial Intelligence the Same as Augmented Intelligence and Cognitive
Computing?
7. Introduction to Machine Learning and Deep Learning
II. Machine Intelligence
[Link] Intelligence
[Link] of Intelligence
[Link] Between Human and Machine Intelligence
[Link] and Environment in AI
[Link] Algorithms:
[Link] Search Algorithms
[Link] Search Algorithms:
Pure Heuristic Search
i) Best-First Search Algorithm (Greedy Search)
ii) A* Search Algorithm
1. Definition of Artificial Intelligence
Artificial Intelligence (AI) is the science and engineering of making intelligent machines,
especially intelligent computer programs, John McCarthy (2004).
A Researcher’s Perspective: For researchers, AI refers to a set of algorithms (step-by-
step instructions) that help a machine make decisions and act without being explicitly told what
to do each time.
Historical Background: The concept of AI was first explored in 1950 by Alan Turing, a
British mathematician and computer scientist, who asked the question "Can machines think?"
This was a groundbreaking idea and led him to propose the Turing Test.
Understanding AI from a Simple View: Think of AI as machines or software that are
designed to learn from their environment, just like humans learn from their experiences. For
example, an AI program can be trained to recognize your face.
The Role of John McCarthy (2004):
Later, in 2004, John McCarthy defined AI as the science and engineering of making
intelligent machines—basically, how we can program computers to act smart like humans.
Everyday AI Examples: Some well- known examples of AI include chess- playing computers or
self-driving cars. These systems depend on deep learning (a type of AI that mimics the human
brain) and natural language processing (helping computers understand human language, like Siri
or Google Assistant).
2. How Does AI Work?
AI works by processing large datasets, recognizing patterns, and making decisions using
algorithms.
It involves learning, reasoning, and self-correction:
[Link] - AI learns from data
[Link] - AI chooses the correct algorithm
[Link]-Correction - AI refines algorithms for accuracy
[Link] and Disadvantages of AI
Advantages:
[Link] well on tasks that uses detailed data.
[Link] less time to perform tasks that needs to process huge volumes of data.
[Link] consistent and accurate results.
[Link] be used 24 X 7.
[Link] tasks by better utilizing resources.
[Link] complex processes.
7. Minimizes downtime by predicting maintenance needs.
[Link] companies to produce new products having better quality and speed.
Disadvantages:
[Link] more cost.
[Link] expertise required to develop and use AI applications.
[Link] of trained professionals.
[Link] or inaccurate data may result in disastrous results.
[Link] the capability to generalize tasks
4. History of AI
1943 - First Neural Network Model Proposed: By Warren McCullough and
Walter Pitts to lay the foundation for artificial neural networks and machine learning.
1950 - Turing Test Introduced: By Alan Turing to measure a machine's ability to
exhibit intelligent behavior indistinguishable from humans.
1956 - John McCarthy Coins the Term 'Artificial Intelligence': By John McCarthy
during the Dartmouth Conference, marking the birth of AI as a formal field.
1997 - IBM Deep Blue Defeats Chess Champion Garry Kasparov: By IBM's team
to demonstrate AI’s capability in strategic decision-making through computational
power.
2011 - Siri Introduced by Apple: By Apple to revolutionize personal assistants
using natural language processing and AI for everyday tasks.
5. Types of AI
AI can be categorized based on Capabilities:
Weak AI (Narrow AI)
● Weak AI, also known as narrow AI, is designed to do one specific task.
● Siri and Alexa are examples.
Strong AI (Artificial General Intelligence)
● Strong AI, also called Artificial General Intelligence (AGI) or Superintelligence (ASI), tries
to mimic human thinking.
● Can perform tasks it hasn’t been specifically trained for.
● Requires abilities like visual perception, speech recognition, decision-making, and
language translation.
AI can be categorized based on Functionalities:
Reactive Machines
● Reactive Machines are the simplest type of AI that react to situations based on
immediate input, but they have no memory or ability to learn from past experiences.
● Examples: IBM’s Deep Blue (chess-playing computer) is a reactive machine. It makes
decisions based on the current state of the game but doesn’t remember past games.
Limited Memory
What it is: Limited memory AI systems can remember data for a short time and
use it to make decisions, but they don’t keep data permanently.
Examples:
i) Autonomous vehicles use limited memory to track information like speed of
nearby cars, distance between cars, and speed limits to navigate safely.
ii) AlphaGo, the AI that defeated the world champion in the game Go, also used
limited memory to play and improve during the game.
These systems learn and improve continuously by analyzing new data and
adjusting based on feedback.
Key Models:
Reinforcement Learning: AI learns by trial and error, improving over time.
Long Short-Term Memory (LSTM): AI uses past data to predict the next step, but
it focuses more on recent data.
Evolutionary GANs (E-GAN): The AI evolves over time, using data and feedback
to make better decisions and predict outcomes.
Theory of Mind
The Theory of Mind in AI aims to create machines that can understand thoughts,
emotions, and memories— just like humans.
How it works: AI would need to understand feelings and emotions that influence
decisions. These machines would make choices by considering both reason and emotional
context. Current Status: This is still theoretical, meaning it’s an idea
for the future, but it could become a reality soon
Self-Awareness
What it is: Self-awareness in AI means machines that have a human-level
consciousness—they can understand their own existence and feelings.
How it works: These machines would not only understand what someone says but also
how they feel based on the way they communicate. They could learn and adapt their responses
to the emotions of others.
Current Status: Self-awareness in AI doesn’t exist yet, but it might happen in the future.
Is AI the Same as Augmented Intelligence and Cognitive Computing?
AI vs Augmented Intelligence:
Some people think AI and augmented intelligence are the same, but they are
different.
Augmented intelligence is a type of weak AI that assists humans to improve tasks
or decisions.
Example: Automatically highlighting important information in a report.
True AI / Strong AI / AGI is future AI that aims to surpass human intelligence, capable of
performing tasks that humans can do, like reasoning and decision-making.
AI in Machines: AI makes machines simulate human intelligence by learning, sensing,
processing, and reacting to information.
Cognitive Computing: This refers to systems or products that mimic human thought
processes to enhance decision-making.
Machine Learning (ML)
Machine Learning is a branch of AI that teaches machines to learn from data and make
decisions without being explicitly programmed.
How it works:
[Link] patterns: ML algorithms analyze data to identify patterns.
[Link] from experience: Machines improve automatically by learning from their past
output.
[Link]-correction: If the machine makes a mistake, it adjusts and learns to improve
accuracy over time.
Real-life examples:
Number series problem: Finding the missing number in 10, 20, 30, 40 → 50. Machines
learn patterns just → like humans do.
Relationship between Artificial Intelligence, Machine Learning, Deep Learning and Natural
Language Processing
HOW IS AI RELATED TO MACHINE LEARNING?
Traditional Programming vs Machine Learning
Key Differences:
Traditional Programming: It uses fixed logic and pre-written rules defined by the
programmer.
Machine Learning: It learns from data, automatically creates its own rules, and improves
over time based on experience.
Example:
Traditional Programming: To filter images manually, you would have to write code comparing
each pixel value in the image. This approach can be slow and inaccurate.
Machine Learning: You simply provide photos of a person, and the model learns to recognize
that person based on patterns in the images, making the task much easier and more efficient.
Machine Learning and Deep Learning
Artificially Intelligent Machine
1. Defining Intelligence,
2. Components of Intelligence,
3. Differences Between Human and Machine Intelligence
4. Agent and Environment,
5. Search,
6. Uninformed Search Algorithms,
7. Informed Search Algorithms:
1. Defining Intelligence
Linguistic Intelligence:
The ability to speak and understand language (e.g., narrators, orators).
Musical Intelligence:
The ability to create and understand music, like recognizing rhythm and pitch
(e.g., musicians, singers).
Logical-Mathematical Intelligence:
The ability to understand abstract concepts and use logic (e.g., mathematicians,
scientists).
Spatial Intelligence:
The ability to visualize and manipulate images in your mind (e.g., map readers,
astronauts).
Bodily-Kinesthetic Intelligence:
The ability to use your body to solve problems or manipulate objects (e.g.,
dancers, athletes).
Intrapersonal Intelligence:
The ability to understand your own feelings and motivations (e.g., spiritual
leaders, philosophers).
Interpersonal Intelligence:
The ability to understand other people’s feelings and intentions (e.g., mass
communicators, interviewers).
Artificial Intelligence (AI): A system or machine is said to be artificially intelligent if it can
exhibit one or more of these types of intelligence.
2. Components of Intelligence
● Reasoning
● Learning
● Problem solving
● Perception
● Linguistic intelligence
Reasoning:
Reasoning is the process used to make decisions and predictions. It involves analyzing
information and drawing conclusions based on evidence.
There are two main types of reasoning:
1. Inductive Reasoning:
What it is: Making generalizations based on specific observations or examples.
How it works: Starts with specific facts or observations and moves to a general
conclusion.
Example: If you see 10 white swans, you might conclude that all swans are white.
2. Deductive Reasoning:
What it is: Drawing a specific conclusion based on general principles or facts.
How it works: Starts with a general statement or premise, and moves to a specific
conclusion.
Example: All swans are birds. A swan is a bird. Therefore, the swan is a bird.
Learning:
Learning is the process of gaining knowledge or skills by studying, practicing, or
experiencing something. It helps humans, animals, and even AI systems to improve their
understanding of different subjects.
There are different types of learning:
[Link] Learning
[Link] Learning
[Link] Learning
[Link] Learning
[Link] Learning
[Link] Learning
[Link] Learning
[Link]-Response Learning
1. Auditory Learning:
● Learning by hearing and listening.
● Example: Listening to recorded lectures to understand a concept.
2. Episodic Learning:
● Learning by remembering events or experiences in a specific order.
● Example: Recalling what happened in a sequence, like remembering steps in a
recipe
3. Motor Learning:
● Learning through physical movement of muscles.
● Example: Learning how to pick up objects correctly.
4. Observational Learning:
● Learning by watching and imitating others.
● Example: Children learn by copying their parents’ actions.
5. Perceptual Learning:
● Learning by recognizing things that have been seen before.
● Example: Identifying objects and situations based on prior experiences.
6. Relational Learning:
● Learning by recognizing patterns in relationships between things.
● Example: Adjusting the amount of spices in a dish after remembering how much
was used last time.
7. Spatial Learning:
● Learning through visual stimuli like images, maps, and colors
● Example: Creating a mental map of a route before actually driving.
8. Stimulus-Response Learning:
● Learning by reacting to a specific stimulus.
● Example: Shouting when touching a hot pan, because it causes pain.
Problem solving:
Problem solving is the process of finding a solution to a challenge or issue.
It involves:
- Identifying the problem: Understanding the situation and recognizing the
obstacles (either known or unknown).
- Making decisions: Choosing the best approach or method to overcome the
obstacles and reach the goal.
Perception:
Perception is the process of:
● Acquiring information through the senses (like sight, hearing, etc.).
● Interpreting that information to understand what’s happening around us.
● Selecting important details and organizing them to form a clear picture.
● Humans use sensory organs (like eyes, ears) to perceive the world.
● AI systems use sensors (like cameras, microphones) to gather data and
understand their environment.
Linguistic intelligence:
It is used in in interpersonal communication and defines one’s ability to use,
comprehend, speak and write the verbal and written language
Differences Between Human and Machine Intelligence
Agent and Environment:
What is an agent in AI?
AI agents are software systems that use AI to pursue goals and complete tasks on behalf
of users.
Examples of AI agents:
It includes virtual assistants (Siri, Alexa), recommendation systems (Netflix, Amazon),
autonomous vehicles, chatbots for customer service, AI-powered writing tools, healthcare
diagnostics, autonomous drones, and fraud detection systems.
AI agents act in their environment, which may include other agents.
● They perceive (realize) their environment using sensors.
● They act upon the environment using effectors.
Types of Agents in an AI System:
1. Human Agent:
● Sensors: Sensory organs like eyes, ears, nose, skin, etc
● Effectors: Hands, legs, mouth for taking action.
[Link] Agent:
● Sensors: Cameras, infrared range finders.
● Effectors: Motors, actuators to perform actions.
[Link] Agent:
● Sensors: Uses bit strings as its programs.
● Effectors: Executes programmed actions based on those bit strings.
Key Terminology
● Performance Measure of Agent:
○ It helps determine how successful an agent is based on its actions.
● Behaviour of Agent:
○ The action performed by an agent after receiving a percept (input).
● Percept:
○ Perceptual input received by an agent at a specific moment in time.
● Percept Sequence:
○ A list of all percepts an agent has received up until now.
● Agent Function:
○ A map that connects the percept sequence to an action performed by the agent.
Rationality:
● Rationality is the ability to make responsible and sensible decisions.
● A rational agent makes decisions that maximize its performance based on:
a. Performance measure (how successful the agent is).
b. Percept sequence (the inputs it has received).
c. Prior knowledge (what the agent already knows about the environment).
d. Possible actions (what the agent can do).
● A rational agent always performs the right action to maximize its performance.
● Problem Solved by Agent (PEAS):
○ Performance measure, Environment, Actuators, and Sensors are used to define a
problem that an agent will solve.
Types of Agents:
1. Simple Reflex Agents
2. Model-Based Reflex Agents
3. Goal-Based Agents
4. Utility-Based Agents
5. Learning Agent
1. Simple Reflex Agents
Simple reflex agents choose actions based only on the current percept (the data they
receive at a specific moment).
● They are rational only if they make the correct decision based on the current percept.
● Working:
○ They use a condition-action rule that maps a state (condition) to an action.
○ If the condition is true, the agent performs the action; otherwise, it does
nothing.
● Limitations:
○ They require the environment to be fully observable (the agent must have access
to complete information).
○ If the environment is partially observable, the agent might get stuck in infinite
loops.
○ In such cases, the agent can only escape the loop if it randomizes its actions.
● Other Issues:
○ Simple reflex agents have very limited intelligence.
○ They don’t know anything about states other than the current one.
○ If the environment changes, the rules they follow might need to be updated.
2. Model-Based Reflex Agents
3. Goal-Based Agents
4. Utility-Based Agents
5. Learning Agent:
The Nature of Environments
Types of Environments
1. Discrete/Continuous:
a. Discrete: Limited, well-defined states (e.g., chess).
b. Continuous: No limitations on percepts or actions (e.g.,self-driving car).
2. Known vs Unknown:
a. Known: Agent knows results for all actions.
b. Unknown: Agents must learn how to act (e.g.,reinforcement learning).
3. Observable/Partially Observable:
a. Observable: Agent can perceive the complete state (e.g., chess).
b. Partially Observable: Agent cannot perceive everything (e.g., Kriegspiel chess).
4. Static/Dynamic:
a. Static: Environment does not change while acting (e.g., crossword puzzle).
b. Dynamic: Environment changes during action (e.g., self-driving car).
[Link]-dynamic: Environment doesn’t change, but agent’s performance can
change.
5. Single Agent/Multiple Agents:
● Single Agent: One agent in the environment (e.g., vacuum cleaner).
● Multiple Agents: More than one agent, can be competitive or cooperative (e.g.,
chess, taxi driving).
6. Accessible/Inaccessible:
● Accessible: Agent has full access to environment information (e.g., empty room).
● Inaccessible: Agent cannot get complete information (e.g., global events).
7. Deterministic/Non-deterministic:
● Deterministic: The next state can be determined from the current state (e.g.,
chess).
● Non-deterministic: Uncertainty about outcomes (e.g., ludo, dice roll).
8. Episodic/Non-episodic:
● Episodic: Each episode is independent (e.g., simple tasks).
● Non-episodic: Current actions affect future actions (e.g., long-term decision
making).
Search:
AI agents use search algorithms to solve tasks and make decisions.
Example: Single-player games like Sudoku & tile games use search algorithms to find
optimal moves or positions.
Components of a Search Problem
1. State Space: The set of all possible states the agent can reach.
2. Start State: The initial state where the search begins.
3. Goal Test: A function that checks if the current state is the goal state.
4. Solution: A sequence of actions (plan) that transforms the start state to the goal state,
achieved using search algorithms.
Types of Search Algorithms
Properties of Search Algorithms
● Completeness: A search algorithm is complete if it guarantees at least one solution for a
given input.
● Optimality: A search algorithm is optimal if it provides the best solution with the lowest
path cost.
● Time and Space Complexity:
○ Time Complexity: The amount of time an algorithm takes to complete a task.
○ Space Complexity: The amount of memory required for the search process.
○ A good search algorithm should use less time and less memory.
Uninformed Search Algorithms
● Uninformed search (or blind search) algorithms have no extra information about the
goal state other than what is provided in the problem definition.
● The algorithm blindly explores the search space without considering how close it is to
the goal.
● Key Concepts:
a. Problem Graph: Represents the problem, from the start node (S) to the goal
node (G).
b. Strategy: The path taken in the search to reach the goal.
c. Fringe: A data structure that stores all possible states (nodes) that can be
reached from the current state.
d. Tree: The path representation that the algorithm follows while searching for
the goal node.
e. Solution Plan: The sequence of nodes (states) from start node (S) to goal node
(G).
f. Path/Step Cost: Integer values that represent the cost to move from one node
to another.
1. Depth First Search (DFS)
2. Depth-Limited Search Algorithm (DLS)
3. Breadth First Search (BFS)
4. Uniform Cost Search (UCS)
5. Iterative Deepening Depth-First Search (IDDFS)
6. Bidirectional Search
1. Depth First Search (DFS)
Depth First Search (DFS) is a simple search algorithm used to explore a tree or graph by
starting from the root node and exploring as far as possible along each branch before
backtracking.
Steps of DFS:
1. Start from the root node: Begin searching from the root node (node A).
2. Explore each branch: Move from node A to its child node (B), then to the next child
(D), and continue exploring until you reach the leaf node (the last node of that branch).
3. Backtrack: If the key you're looking for isn't found at the leaf node, backtrack to the
last node with unexplored branches and explore them.
4. Repeat the process: Continue exploring each branch by backtracking and then moving
to the next unexplored branch, until the entire tree is searched or the goal is found.
Advantages of Depth First Search (DFS)
1. Less Memory Usage:
DFS stores only the nodes along the path from the root node to the current
node,requiring less memory.
2. Faster to Reach Goal:
It often takes less time to find a goal compared to Breadth First Search (BFS),
especially when the solution is deep in the tree.
Disadvantages of Depth First Search (DFS)
1. Recurring States:
Sometimes, many states repeat. In such cases, there’s no guarantee of finding
the solution.
2. Infinite Loops:
DFS may get stuck in an infinite loop when it keeps going deeper. This can be
avoided by setting an appropriate cut-off depth, but:
a) Too small a cut-off may make the algorithm fail
b) Too large a cut-off increases execution time.
3. Complexity:
The algorithm's complexity depends on the number of paths it needs to explore.
4. Duplicate Nodes:
DFS cannot check for duplicate nodes, potentially leading to inefficiency in the
search.
2. Depth-Limited Search (DLS)
Depth-Limited Search (DLS) is similar to Depth First Search (DFS), but with a
predetermined depth limit to avoid infinite paths.
When the search reaches the specified depth limit, nodes at that depth are treated as
leaf nodes (i.e., nodes with no successors).
Termination Conditions of DLS:
[Link] Solution: If the problem has no solution, it's called standard error failure.
[Link] Solution within Limit: If the solution is not found within the given depth limit, it's
called cut-off failure.
[Link] Found: If the solution is found within the depth limit, the algorithm stops.
Example:
If the depth limit is set to 2, the algorithm will not explore level 3 of the tree, so nodes E,
F, G, H won't be traversed.
Example – Searching for Node H (Limit = 2)
● Search for node H using Depth-Limited Search (DLS) with a depth limit of 2
● How DLS Works:
○ Start at root node A (level 0).
○ Explore all nodes at level 1: B, C, D, E.
Move to level 2 and explore children of B →H not found→back track.
○ Explore children of C at level 2 → H found.
● Traversal Path:
○ A → B → (children of B checked) → backtrack
A → C → H → goal found
● Key Idea:
○ DLS explores nodes up to a fixed depth limit.
○ If the goal isn’t found at the current depth, it backtracks to explore other
branches.
○ Useful when the goal depth is known or limited
3, Breadth First Search (BFS)
Example: Find the BFS traversal from node S to node G
4. Uniform Cost Search (UCS)
Example:
Find the path and cost to move from node S to node G in the graph given below.
5. Iterative Deepening Depth-First Search (IDDFS)
● IDDFS is used to search for a goal node when the depth of the goal is unknown.
● It combines the advantages of DFS (low memory use) and BFS (guaranteed shortest
path).
How It Works:
1. Start with a depth limit of 1, perform DFS up to that depth.
2. If the goal isn’t found, increase the depth limit by 1 and repeat DFS.
3. Continue increasing the depth limit until the goal is found.
Key Feature:
● Memory Efficient: Only stores nodes in the current DFS path (like DFS).
● Fast Search: Gradually explores all levels (like BFS).
● Does not generate nodes beyond the current depth limit until needed.
Best Used When:
● The search space is large.
● The depth of the goal node is unknown.
Example:
Traverse the given tree using the iterative deepening depth-first search algorithm.
Search for a goal node H using Iterative Deepening Depth-First Search (IDDFS).
How IDDFS Works:
● Performs DFS repeatedly with gradually increasing depth limits.
● Each iteration explores all nodes up to the current depth limit.
Step-by-Step Traversal:
● Iteration 1 (Depth 0): Explore node A
● Iteration 2 (Depth 1): Explore nodes B and C
● Iteration 3 (Depth 2): Explore nodes D, E, F, G
● Iteration 4 (Depth 3): Explore node H goal found
Key Features:
● Memory Efficient: Only stores nodes along the current DFS path.
● Complete: Guarantees to find the goal if it exists.
● Combines DFS depth efficiency with BFS completeness.
Complexity:
● Time Complexity: O(b^d)
● Space Complexity: O(b·d)
○ Where b = branching factor, d = depth of the goal
Key Idea:
● IDDFS gradually deepens the DFS limit until the goal is reached, balancing memory
efficiency and completeness
6. Bidirectional Search:
To find the shortest path between a start node and a goal node more efficiently.
How It Works:
1. The search happens from both directions at the same time:
a. Forward Search: From the start node toward the goal.
b. Backward Search: From the goal node toward the start.
2. The search stops when the two paths meet at a common node.
Advantage:
● Reduces the search space because each search only goes half the total distance.
● Faster than searching in a single direction.
Key Idea:
● Instead of one big search, two smaller searches meet in the middle, saving time and
memory.
Example:
Consider the graph given above and apply bidirectional search on it to reach goal node
14 from source node 0.
Find the path from source node 0 to goal node 14 using Bidirectional Search.
How Bidirectional Search Works:
● Two searches are run simultaneously:
○ Forward Search: From 0 →14
○ Backward Search: From 14 → 0
● Both searches continue until they meet at a common node.
Informed Search Algorithms
1. Best-First Search Algorithm (Greedy Search)
2. A* Search Algorithm
To find the goal node efficiently using extra information about the search space
● Key Feature:
○ Uses a heuristic function to estimate how close a node is to the goal.
● How it Works:
○ The heuristic function h(n) calculates the estimated cost from the current node n
to the goal.
○ The agent uses this information to choose the most promising path, reducing
unnecessary exploration.
● Advantages:
○ Explores fewer nodes than uninformed search (DFS, BFS).
○ Reaches the goal faster in large search spaces.
● Guarantee:
○ Heuristic may not always give the absolute best path, but it finds a good solution
in reasonable time.
● Key Idea:
○ Informed search = smarter search because it “knows” which directions are likely
better.
Pure Heuristic Search
To solve problems with a large number of possible states efficiently by using
problem-specific knowledge.
● Key Idea:
Expands nodes based on their heuristic value h(n) (an estimate of distance to the goal).
● How it Works:
Maintains two lists:
OPEN list: Nodes yet to be expanded.
CLOSED list: Nodes already expanded.
● Process:
○ Apply heuristic to child nodes.
○ Add child nodes to OPEN list based on their heuristic value.
○ Keep shorter paths, discard longer ones.
○ Repeat until the goal state is reached.
● Benefit:
Reduces unnecessary exploration and focuses on the most promising paths.
Examples:
Greedy Best-First Search
A* Search Algorithm
1. Best-First Search Algorithm (Greedy Search):
● Implementation:
○ Usually uses a priority queue, giving priority to nodes with lowest heuristic value.
● Benefit:
○ Finds the goal faster by focusing on promising paths rather than exploring all
nodes.
● Key Idea:
○ Greedy because it always picks the node that looks best now, but it may not
always find the shortest path.
Example:
Consider the tree given below and traverse it using the greedy best first search
algorithm.
● Traverse the tree from node S to find the goal node using the Greedy Best-First Search
Algorithm.
Problem : Apply greedy best first search algorithm on the below graph to Reach node I from
node S (S —---> I)
Solution:
Step-1: Add node S in the CLOSED list and place its successors in the OPEN list
Open [A, B, C]
Closed [S]
Step-2: Remove A from the OPEN list as it has minimum h(n), place it in CLOSED list and
put its successors in the OPEN list.
Open [B, C, E, D]
Closed [S, A]
Step-3: Remove C from the OPEN list as it has minimum h(n), place it in CLOSED list and
put its successors in the OPEN list.
Open [B, E, D, H]
Closed [S, A, C]
Step-4: Remove B from the OPEN list as it has minimum h(n), place it in CLOSED list and
put its successors in the OPEN list.
Open [E, D, H, F, G]
Closed [S, A, C, B]
Step-5: Remove H from the OPEN list as it has minimum h(n), place it in CLOSED list and
put its successors in the OPEN list. Since I is the successor of node H, the algorithm
returns success.
Open [E, D, F, G, I, J]
Closed [S, A, C, B, H]
Advantages:
1. It takes advantage of both BFS and DFS algorithms.
2. Best first search algorithm is more efficient than BFS and DFS
algorithms
Disadvantages:
1. In some worst-case scenarios, best first search can behave as an unguided depth-first
search.
2. Like DFS, best first search algorithm can get stuck in a loop.
3. Best first search algorithm is not an optimal algorithm.
2. A* Search Algorithm:
● The A search algorithm, best-known form of best first search, uses heuristic function
h(n), and g(n)
● It solves the searching problem efficiently by expanding less search tree to find shortest
path and give an optimal result faster
● The A search algorithm, uses search heuristic as well as the cost to reach the node. Sum
of both the costs gives a number known as a fitness number.
At each point in the search space, nodes having the minimum f(n) are expanded. The
algorithm terminates when the goal node is found.
The steps of this algorithm can therefore be summarized as given below.
Step1: Put the starting node in the OPEN list.
Step 2: If the OPEN list is empty then return failure and stop.
Step 3: From the OPEN list, choose the node having minimum value of f(n). If this node
is the goal node, then return success and stop.
Step 4: Expand the node selected in Step 3 and generate its successors. Put the node in
the closed list. For each successor, check if it is present in the OPEN or CLOSED list. If it is
not present in either then compute its f(n) and place it into Open list.
Step 5: Else if the successor node is already in OPEN or CLOSED list, then attach it to the
back pointer reflecting the lowest g(n’) value.
Step 6: Return to Step 2.
Example: Consider the graph given below and traverse it using the A* algorithm.
Example: Consider the graph given below and traverse it from node S to G using A* algorithm.
● In the graph, the cost to reach node A from node S is 3 + 5 = 8, the cost to reach node B
from S is 6 + 4 = 10 and the cost to reach C is 2 + 10 = 12. Undoubtedly, node A is
processed further. Now,
○ {(S--> A, 8), (S--> B, 10), (S-->C, 12)}
● In the next iteration, node is found to be reached from A with a
○ total cost of 3 + 10 = 13.
○ {(S--> A --> G, 13), (S--> B, 10), (S-->C, 12)}
● Now, traversing the S -> B path to reach G, we get total cost = 11 (6 + 5). Therefore,
■ {(S--> A --> G, 13), (S--> B-->G, 11), (S-->C, 12)}
● The final path to G from S is thus, S--> B-->G with a cost of 11.
Advantages
● It is better than all other search algorithms.
● A searchalgorithmisoptimalandcomplete.
● The algorithm can be used to solve very complex problems.
● It is used by many games and web-based maps to find the shortest path efficiently.
Disadvantages
● It may not always produce the shortest path since it is based on heuristics and
approximation.
● A* search algorithm is more complex than other search algorithms
● It uses more memory as it keeps all generated nodes in the memory. This makes it
difficult to use for large-scale problems.
● At times, A* algorithm returns the path which occurred first, and ignores searching all
other paths.
● The efficiency of A* algorithm depends on the quality of heuristic.
Knowledge Representation:
● Introduction,
● Knowledge Representation,
● Knowledge-Based Agent,
● Types of Knowledge.
Introduction:
● People have always been interested in artificial intelligence (AI) technology.
● Many movies and books show robots that can think and act like humans.
● Making machines behave exactly like humans is very difficult.
● Humans have a conscience that grows with learning and experience.
● To give machines something similar, we need to put knowledge into them.
Knowledge Representation:
● Knowledge is essential for intelligence:
To act intelligently, an AI system or agent must have knowledge or experience about the
real world.
● How intelligent agents work:
An intelligent agent observes (senses) its surroundings and then uses its knowledge to
decide what action to take.
● Without knowledge, intelligence fails:
If the agent doesn’t have knowledge, it cannot understand the environment correctly or
make good decisions.
● Knowledge and intelligence are connected:
Knowledge helps intelligence function effectively—without it, intelligent behavior is not
possible.
What is Knowledge?
● Knowledge is what helps us understand things logically and make better decisions.
● We gain knowledge from experience, facts, data, and situations.
● A person with more knowledge can perform tasks more effectively.
Types of Knowledge
1. Meta Knowledge:
○ It means “knowledge about knowledge.”
○ It helps us understand what we know and how we know it.
2. Heuristic Knowledge:
○ It is experience-based knowledge about a specific subject.
○ It comes from experts’ experiences or practical understanding.
○ It gives general rules (“rules of thumb”) that usually work well but are not always
guaranteed to be perfect.
3. Procedural Knowledge:
○ It is knowledge of how to do something.
○ It includes steps, rules, and methods used to complete a task.
○ Example: Knowing how to solve a math problem or cook a recipe.
4. Declarative Knowledge:
○ It is knowledge about facts, objects, or concepts.
○ It helps us describe things — what something is, its features, or its meaning.
○ Example: Knowing that Paris is the capital of France.
5. Structural Knowledge:
○ It helps us connect and relate different pieces of information.
○ It explains how concepts are linked — for example, how a “car” is a type of
“vehicle,” or how “engine” is a part of a “car.”
○ It is useful for solving complex problems by understanding relationships
Knowledge-Based Agent (KBA)
● In AI, a Knowledge-Based Agent is an intelligent agent that uses knowledge and
reasoning to make smart decisions like a human.
● It stores information, reasons about it, learns from new data, and acts accordingly.
● In simple words, A Knowledge-Based Agent learns from its environment, stores facts,
reasons logically, updates its knowledge, and acts intelligently.
Functions of a Knowledge-Based Agent
1. Maintains knowledge about its environment (states, actions, etc.)
2. Uses reasoning to make decisions
3. Updates knowledge when new information is received
4. Takes actions based on updated knowledge
Architecture of a Knowledge-Based Agent
A KBA has two main parts:
1. Knowledge Base (KB):
● Stores facts and information about the world.
● Uses a knowledge representation language (not normal English).
2. Inference Engine (IE):
● Uses logic to derive new knowledge from existing facts.
● Helps in decision-making by interacting with the KB.
Steps in Working:
1. Perceives input from the environment.
2. Inference engine processes the input.
3. Interacts with the knowledge base to make decisions.
4. Learns and updates the KB regularly.
Operations Performed by KBA
1. TELL:
Adds or updates knowledge in the knowledge base.
2. ASK:
Queries the knowledge base to decide which action to take.
3. PERFORM:
Executes the chosen action.
END OF MODULE - 1