1

MODULE – 1

1. Introduction to AI

Artificial Intelligence (AI) is the science and engineering of making intelligent machines, especially

intelligent computer programs.

AI applications perform specialized tasks by processing large amounts of data and recognizing

patterns in them. Besides learning from experience, AI applications can recognize objects,

understand and respond to language and make decisions to solve real -world problems. AI perform

tasks that normally require human intelligence. The main focus of this technology is to build

machines and algorithms which are capable of performing computational tasks that would

otherwise require human-like brain functions.

While computers execute certain tasks like sorting, computing, memorizing, indexing , finding

patterns, etc. far better than humans, they still cannot beat human skills for identifying emotions,

recognizing faces, communication and conversation. This is where AI will play a crucial role to

enable machines achieve human capabilities.

1.1. Definition:

 From a layman’s view, artificial intelligence (AI), simply means the intelligence

demonstrated by machines that help them to mimic the actions of humans. AI simulates natural

intelligence in machines that are programmed to learn from experiences, adjust to new inputs

and perform human-like tasks.

 From a researcher’s view, AI is a set of algorithms that generates results without having to

be explicitly instructed to do so, thereby making machines capable of thinking and acting

rationally and humanely.

 NITI (National Institution for Transforming India) Aayog: The National Strategy for

Artificial Intelligence has defined AI as follows: AI refers to the ability of machines to perform

cognitive tasks like thinking, perceiving, learning, problem solving and decision-making.

Initially conceived as a technology that could mimic human intelligence, AI has evolved in ways

that far exceed its original conception. With incredible advances made in data collection,

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

2

processing and computation power, intelligent systems can now be deployed to take over a

variety of tasks, enable connectivity and enhance productivity.

2. How does AI work:

AI systems work effectively when fed with a large amount of labelled training data. This data is

thoroughly analyzed to discover correlations and patterns. These patterns are then used to make

predictions about future states.

For example, a chatbot fed with examples of text chats can learn to converse with humans in real-

world applications.

AI programming focuses on three cognitive skills: learning, reasoning and self-correction.

2.1. Learning Processes

AI programs focus on acquiring data and creating rules for turning that data into actionable

information. Rules, also known as algorithms, provide step-by-step instructions to complete a

specific task.

2.2. Reasoning Processes

Reasoning is the process of drawing conclusions or making inferences based on available

information or knowledge.

It enables an intelligent agent or human to make decisions, predict outcomes, and solve problems

logically.

There are two main types of reasoning used in Artificial Intelligence and human cognition:

 Inductive Reasoning

 Deductive Reasoning

2.2.1. Inductive reasoning

Inductive reasoning is the process of deriving general rules or conclusions from specific

observations or examples.

It moves from specific to general — that is, from data or instances to a broader generalization.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

3

Inductive Reasoning: Specific facts → General conclusion

2.2.2. Deductive reasoning

Deductive reasoning is the process of deriving specific conclusions from general statements or

known facts.

It moves from general to specific — applying a general rule to a specific case.

Deductive Reasoning: General rule → Specific conclusion

2.2.3. Difference between Inductive and Deductive reasoning

2.3. Self-Correction Processes

AI programs are designed to continually enhance their algorithms to provide the most accurate

results.

3. History and Evolution of AI

Milestones:

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

4

Turing Test:

The Turing Test, proposed by the British mathematician and computer scientist Alan Turing in

1950, is a method to determine whether a machine can exhibit human-like intelligence. It is one

of the foundational concepts in Artificial Intelligence, showing how close machines can come to

imitating human behavior and communication.

In this test, a human evaluator communicates (through text only) with both a human and a

machine, without knowing which is which.

 The evaluator asks questions to both a human and a machine

 If the evaluator cannot reliably distinguish between the human and the machine based on their

responses, then the machine is said to have passed the Turing Test.

The test focuses on how naturally and intelligently a machine can respond, rather than how fast

or accurate it is. It is a measure of Artificial Intelligence (AI) — specifically, of a machine’s ability

to think, reason, and use language like a human.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

5

4. Foundations of AI

Artificial Intelligence (AI) is built on several foundational disciplines that provide methods,

models, and theories for understanding intelligent behavior. The three Foundations of AI are Logic,

Probability, and Cognitive Science.

Probability

Cognitive Science

4.1. Logic in Artificial Intelligence

Logic is the formal study of reasoning — it helps AI systems make conclusions based on facts and

rules. It provides a mathematical framework to represent knowledge and derive new information

from it.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

6

4.1.1. Importance of Logic in Artificial Intelligence

Foundation of Reasoning

 Logic provides the backbone for AI systems to “think” systematically.

 Without logic, AI cannot ensure that its conclusions are correct.

2. Knowledge Representation

 Facts about the world can be stored as logical statements.

 Example: “All humans are mortal” → ∀x (Human(x) → Mortal(x)).

3. Inference and Decision-Making

 AI uses logic to infer new knowledge from existing facts.

 Example:

 Fact: Socrates is human.

 Rule: All humans are mortal.

 Conclusion: Socrates is mortal.

4. Transparency

 o Logic-based reasoning is explainable → AI can show the steps of reasoning.

 o Important in fields like medicine, law, and safety-critical systems.

Example:

Rule: If it rains, then the ground becomes wet.

Fact: It is raining.

Inference: Therefore, the ground is wet.

4.2. Probability in Artificial Intelligence

In many real-world problems, information is incomplete or uncertain. Probability deals with

uncertainty in real-world environments. It helps AI systems make rational decisions even when

information is incomplete or noisy.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

7

 A self-driving car doesn’t know exactly what another driver will do.

 A medical diagnosis system may not be 100% sure of a disease given symptoms.

Therefore, probabilistic reasoning helps AI agents make the best possible decision with the

available information.

4.2.1. Importance of Probability in Artificial Intelligence

1. Real-World Uncertainty

 The real world is full of incomplete, noisy, or ambiguous data.

 Example: A medical test may give false positives or false negatives.

2. Decision-Making Under Uncertainty

 Logic works when facts are clear.

 But AI must often act when facts are uncertain → probability is essential.

3. Prediction

 Probability helps AI predict outcomes.

 Example: Weather forecast: “70% chance of rain.”

4. Risk Handling

 AI can weigh risks and choose the best option.

 Example: Self-driving car → probability of collision based on sensor readings.

4.3. Cognitive Science in Artificial Intelligence

Cognitive Science is the study of how humans think, learn, and solve problems. AI borrows ideas

from cognitive science to model human-like intelligence in machines. Cognitive Science combines

ideas from Psychology (human behavior and learning), Neuroscience (brain functioning),

Linguistics (language understanding), Philosophy (mind and reasoning), Computer Science

(simulation of mental processes).

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

8

4.3.1. Importance of Cognitive Science in Artificial Intelligence

1. Human Inspiration

 AI was inspired by how humans process information.

 Example: Artificial Neural Networks mimic brain neurons.

2. Understanding Intelligence

 To build intelligent machines, we first study human intelligence.

 Helps design AI that learns, reasons, and adapts like humans.

3. Improving Human–AI Interaction

 Cognitive science helps AI understand language, vision, and emotions.

 Example: Chatbots (NLP) and virtual assistants.

4. Explaining AI Decisions

 AI models inspired by cognitive processes are often more interpretable and relatable to

humans.

5. Types of Artificial Intelligence

An artificial intelligent system can be classified into following categories

5.1. Based on Capabilities

5.1.1. Narrow AI

It is also known as Weak AI and is specifically designed to perform a specific type of task. These

systems are already trained with appropriate responses to classify things accordingly. These

systems are great at doing one thing really well, but they don’t work outside their specific task.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

9

Weak AI systems operate within a limited context and are the most successful realization of

artificial intelligence to date. Weak AI has helped make many tasks easier and more efficient, and

it is the most common type of AI in use today. Application of narrow AI has resulted in significant

societal benefits.

Google search, Image recognition software, self-driving cars and IBM’s Watson are some examples

of such systems.

5.1.2. Strong AI

Strong AI, also known as artificial general intelligence or artificial super intelligence (ASI) or

superintelligence, makes full attempt to resemble the human brain. It utilizes cognitive skills and

fuzzy logic to perform tasks for which it had not been trained earlier. Such a system needs

capability for visual perception, speech recognition, decision-making and translations between

languages.

5.1.3. Difference between Weak AI and Strong AI

5.2. Based on Functionalities

Artificial intelligence systems can also be categorized into four groups based on their functionality

5.2.1. 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.

Reactive machines are very basic machines with no memory to store and thus use past experiences

to determine future actions. They just perceive the world and react to it. Since it lacks capabilities

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

10

to store past experiences, a reactive machine cannot improve with practice. Reactive machines can

perform only a limited number of specialized tasks. Such machines are more trustworthy and

reliable as they react the same way to the same stimuli every time.

 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.

5.2.2. Limited Memory

Limited memory AI systems can remember data for a short time and use it to make decisions, but

they don’t keep data permanently. They cannot keep adding data permanently to a library of their

experiences. limited memory AI is more complex and is used for better possibilities than reactive

machines. These machines continuously train a model to analyze and utilize new data. The model

also improves using feedback received from humans or the environment and stored as data.

There are three major machine learning models that applies limited memory artificial intelligence:

 Reinforcement learning: It enables continuous learning through repeated trial-and-error to

make better predictions.

 Long Short-term Memory (LSTM): Such models use past data to help predict the next item

in a sequence. More recent information is given a higher priority for prediction than past data.

However, this does not mean that past data is not considered while making predictions.

 Evolutionary Generative Adversarial Networks (E-GAN): The ML model evolves over

time to explore new ways of utilizing previous experiences to jump formulate new decisions.

The model is continuously striving to discover a better path. It makes use of simulations and

statistics, to predict outcomes throughout its evolutionary mutation cycle.

Examples:

 Autonomous vehicles use limited memory to track information like speed of nearby cars,

distance between cars, and speed limits to navigate safely.

 AlphaGo, the AI that defeated the world champion in the game Go, also used limited memory

to play and improve during the game.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

11

5.2.3. Theory of Mind

The Theory of Mind in AI aims to create machines that can understand thoughts, emotions, and

memories—just like humans. However, such systems are only theoretical as of now but they may

become reality very soon. AI would need to understand feelings and emotions that influence

decisions. These machines would make choices by considering both reason and emotional context.

5.2.4. Self-Awareness.

Once Theory of Mind is established, then the next step would be incorporating self-awareness in

AI systems. Self-awareness in AI means machines that have a human-level consciousness—they

can understand their own existence and feelings. They could interpret user’s feelings by learning

not only what they communicate to them but also how they communicate it.

6. Agents and Environments

In Artificial Intelligence (AI), an agent is an entity that perceives its environment through sensors

and acts upon that environment through (effectors).

The combination of what the agent perceives and how it acts defines its behavior.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

12

An agent is anything that perceives its environment through sensors and acts upon it through

actuators (effectors). In simple terms, an agent is an intelligent system that makes decisions based

on the information it gathers.

AI agents act in their environment, which may include other agents.

6.1.1. Structure of an Agent

Every intelligent agent can be represented as:

Agent = Architecture + Program

 Architecture: The physical platform on which the agent runs (e.g., robot hardware or

computer system).

 Program: The logic or code that implements the agent’s behavior (decision-making process).

6.1.2. PEAS Representation

PEAS stand for Performance Measure, Environment, Actuators, and Sensors. It is used to describe

the properties and behavior of an intelligent agent in a structured manner.

Each element defines what the agent needs to achieve and how it interacts with its surroundings.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

13

6.1.3. Types of Agents

Types of agents = agent mechanisms:

1. Simple Reflex Agents – act only on current percept (if–then rules)

 Simple reflex agents choose actions based only on the current percept.

 They are rational only if they make a correct decision based on the current precept.

 Their environment is completely observable.

 They work using condition-action rule that maps a state (condition) to an action.

 If the condition is true, then the action is taken, else not.

 However, the problem with a simple reflex agent is that they succeed only when the

environment is fully observable.

 If the environment is partially observable, then the agent may get stuck in infinite loops.

 In such a situation, the agent can escape the loop only if it can randomize its actions.

Other issues with such agents are given below:

 Possess very limited intelligence

 Has knowledge of any state other than the current state.

 Any change in the environment will eventually end up updating the collection of rules

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

14

2. Model-Based Reflex Agents

 Model-based reflex agents use a model of the world to choose their actions, which requires

them to maintain an internal state.

 The internal state represents aspects of the current situation that are not directly observable

but can be inferred based on the history of percepts.

 The agent updates its internal state by understanding two things:

 How the world evolves (what happens over time in the environment).

 How the agent’s actions affect the world (the consequences of the agent's actions).

3. Goal-Based Agents

 A description of desirable situations or outcomes.

 Goal-based agents choose their actions to achieve specific goals.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

15

 Provides more flexibility than reflex agents as the decision-making knowledge is explicitly

modeled and allows modifications to adapt to changing conditions.

4. Utility-Based Agents

 It is Used when goals are conflicting or difficult to achieve.

 These agents choose actions based on a preference (utility) for each state.

 They help prioritize goals by choosing actions that lead to the most preferred outcome.

 Provides a way to handle multiple goals by considering their relative importance.

5. Learning Agent

 A learning agent learns from past experiences and adapts over time. It begins with basic

knowledge and gradually improves by learning from its environment.

Four Main Components:

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

16

 Learning Element: Responsible for making improvements by learning from the

environment.

 Critic: Provides feedback to the learning element, evaluating how well the agent is

performing against a set performance standard.

 Performance Element: Selects the external action to be taken based on the current

situation.

 Problem Generator: Suggests actions that lead to new experiences for the agent, promoting

further learning.

6.2. Environment

The environment is everything that the agent interacts with. It provides inputs (percepts) to the

agent and is affected by the agent’s actions.

Example:

 For a robot vacuum cleaner, the environment includes walls, floor area, dirt, furniture, and

charging dock.

 For a chess-playing agent, the environment is the chessboard and opponent move.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

17

6.2.1. 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: Agent 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).

c. Semi-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: Next state can be determined from current state (e.g., chess).

Non-deterministic: Uncertainty about outcomes (e.g., ludo, dice roll).

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

18

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).

7. Problem formulation

Problem formulation is the process of converting the general problem into a search problem by

defining:

 What the states are

 What actions are possible

 What the goal state is

It helps in representing the real-world situation in a way that can be solved computationally by

an AI agent.

Search
Solution / Goal
Algorithm (BFS,
Path
DFS, UCS)

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

19

8. Problem definition

A problem in AI can be defined as a situation where an agent needs to perform a sequence of actions

to achieve a specific goal.

Definition:

A problem is defined by the initial state, possible actions, transition model, goal test, and path

cost. In simple terms, problem definition means clearly specifying what the problem is and what

the desired solution looks like.

8.1. Components of Problem definition

Component Meaning Description

S Initial State The starting point of the agent.

A Actions All possible actions that can be performed.

Transition
T Describes the result of each action.
Model
G Goal Test Checks whether the goal has been achieved.
The cost of performing a sequence of actions (used to evaluate
C Path Cost
efficiency).

9. Search Strategies

AI agents use search algorithms to solve tasks and make decisions. For example, single-player

games like Sudoku and tile games use search algorithms to find optimal moves or positions.

9.1. Components of a Search Problem

 State Space: The set of all possible states the agent can reach.

 Start State: The initial state where the search begins.

 Goal Test: A function that checks if the current state is the goal state.

 Solution: A sequence of actions (plan) that transforms the start state to the goal state, achieved

using search algorithms.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

20

9.2. 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 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.

9.3. Types of Search Algorithms

10. Uninformed Search

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:

 Problem Graph: Represents the problem, from the start node (S) to the goal node (G).

 Strategy: The path taken in the search to reach the goal.

 Fringe: A data structure that stores all possible states (nodes) that can be reached from the

current state.

 Tree: The path representation that the algorithm follows while searching for the goal node.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

21

 Solution Plan: The sequence of nodes (states) from start node (S) to goal node (G).

 Path/Step Cost: Integer values that represent the cost to move from one node to another.

10.1. Depth First Search (DFS)

Depth First Search (DFS) is a graph traversal 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.

10.1.1. 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.

Note:

1. Backtracking is a key feature of DFS, meaning it explores as far as possible along each branch

before going back to previous nodes to try other paths.

2. DFS uses a stack (Last-In-First-Out or LIFO structure) to keep track of nodes to visit next.

10.1.2. Advantages of Depth First Search (DFS)

 Less Memory Usage: DFS stores only the nodes along the path from the root node to the

current node, requiring less memory.

 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.

10.1.3. Disadvantages of Depth First Search (DFS)

 Recurring States: Sometimes, many states repeat. In such cases, there’s no guarantee of

finding the solution.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

22

 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:

o Too small a cut-off may make the algorithm fail.

o Too large a cut-off increases execution time.

 Complexity: The algorithm's complexity depends on the number of paths it needs to explore.

 Duplicate Nodes: DFS cannot check for duplicate nodes, potentially leading to inefficiency

in the search.

10.1.4. Example: Finding Path to Node g

 Start at node a, Goal is node g.

 Explore node b, then node d, then node h (leaf node).

 Since h is a leaf and the key aren’t found, backtrack to node b and explore node e, then node i

(leaf node).

 Backtrack again to explore node j and other branches of node b.

 Once all branches of node b are explored, move to node c, then node f, node k, and finally node

g.

Path Found: a → b → d → h → e → i → j → c → f → k → g

OR

 Start at Node a, Goal is node g

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

23

o Start at a → go to b

o From b → go to d

o From d → go to h

o h has no unvisited child → Backtrack to d

o From d → go to e

o From e → go to i

o i has no unvisited child → Backtrack to e

o From e → go to j

o j has no unvisited child → Backtrack to e → then to b → then to a

o From a → go to c

o From c → go to f

o From f → go to k

o k has no unvisited child → Backtrack to f → then to c

o From c → go to g

 Goal is Achieved

Path Found: a → b → d → h → e → i → j → c → f → k → g

Question: Finding Path to Node G

Solution:

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

24

 Start at node S, goal is node G.

 Step-by-Step Traversal

o Start at S → go to A

o From A → go to B

o From B → go to C

o From C → go to G

 Goal node (G) found (Goal is Achieved)

Path Found: S → A → B → C → G

10.2. Breadth First Search (BFS)

Breadth First Search (BFS) is a graph traversal search algorithm that explores all the nodes at

the present depth level before moving on to the nodes at the next depth level.

It starts from the root node and explores all its neighboring nodes first, then moves on to explore

their children.

10.2.1. Steps of BFS:

1. Start from the root node: Begin searching from the root node.

2. Traverse level by level: First, visit the immediate children of the directly connected to the

root node

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

25

3. Move to next level: After visiting all neighbors (children) of current level, the search moves

to the next level and explore all children of that level.

4. Continue level-wise traversal: The algorithm continues this process, exploring all neighbor

nodes (children) at each level before moving deeper.

Note:

1. BFS explores nodes level by level, ensuring that the shortest path (in terms of number of edges)

is found if all edges have equal weight.

2. BFS uses a Queue (First-In-First-Out or FIFO structure) to keep track of nodes that are yet to

be visited.

3. BFS always visits all nodes at a particular depth before moving deeper.

4. BFS is complete (it will always find a solution if one exists) and optimal for equal edge costs.

5. BFS always finds the shallowest solution (fewest number of nodes in path).

10.2.2. Advantages of Breadth First Search (BFS)

 Guaranteed to Find the Shortest Path: If all edges have equal cost, BFS finds the shortest

path to the goal.

 Completeness: BFS is complete; it will always find the goal node if it exists.

 Systematic Exploration: Nodes are explored in increasing order of their depth, ensuring no

node is skipped.

10.2.3. Disadvantages of Breadth First Search (BFS)

 High Memory Usage: BFS stores all nodes at the current level and the next level in the queue,

which consumes a large amount of memory.

 High Time Complexity: BFS may take a long time for deep or large graphs since it explores

every node level by level.

 Not Suitable for Infinite or Very Large Graphs: If the search space is infinite or extremely

large, BFS cannot handle it efficiently.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

26

10.2.4. Example: Finding Path to Node g

Consider the graph shown below, where the goal is to find Node G starting from Node A.

 Start at node a, Goal is node g

 Visit its children: nodes b and c.

 After visiting nodes at level 1, move to level 2: nodes d, e, f, and g.

 Then, visit level 3: nodes h to k.

Path Found: a → c → g

OR

 Start at Node a, Goal is node g

o Start at A (Root Node)

o From a → visit b, c (all at level 1)

o From b → visit d, e

o From c → visit f, g

o G is found → Goal Achieved

 Goal is Achieved

Path Found: a → c → g

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

27

Question: Finding Path to Node G

Solution:

 Start at node S, goal is node G.

 Step-by-Step Traversal

o Start at S → go to A & D

o From A → go to B

o From D → go to G

 Goal node (G) found (Goal is Achieved)

Path Found: S → D → G

10.3. Uniform Cost Search (UCS)

Uniform Cost Search (UCS) is a search algorithm that expands the least-cost node first. It is

similar to Breadth First Search (BFS), but instead of exploring nodes level by level, UCS explores

nodes based on their path cost (g(n)) — the total cost from the start node to the current node.

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

28

UCS guarantees finding the optimal (least-cost) path to the goal if all step costs are positive.

10.3.1. Steps of Uniform Cost Search (UCS):

1. Start from the root node: Begin at the starting node with a total path cost of 0.

2. Use a Priority Queue: Store nodes in a priority queue (min-heap) based on their cumulative

cost (g(n)). The node with the lowest path cost is expanded first.

3. Expand the lowest-cost node: Select the node with the smallest cost and expand it by

generating all possible successors.

4. Update Costs: For each successor, calculate the new path cost:

g(new) = g(current) + cost (current → successor)

 If the successor has not been visited or has a lower cost, update its cost in the queue.

5. Goal Check: If the goal node is selected for expansion, the algorithm stops — this path is

guaranteed to be the optimal (least-cost) one.

Note:

1. UCS is a cost-based search, not depth-based.

2. It is complete (if step costs are positive) and optimal (finds the minimum-cost path).

3. UCS is an extension of BFS that works with non-uniform edge costs.

10.3.2. Advantages of Uniform Cost Search (UCS)

 Optimal Solution: UCS always finds the path with the lowest total cost from the start node

to the goal.

 Complete Algorithm: It will find a solution if one exists, provided all step costs are greater

than zero.

 Handles Varying Costs: UCS performs efficiently in problems where edge costs are not

uniform (unlike BFS).

10.3.3. Disadvantages of Uniform Cost Search (UCS)

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla

29

 High Memory Usage: The algorithm may need to store multiple paths in the priority queue,

consuming significant memory.

 Slow for Large Graphs: As UCS explores many possible paths, it can be slower than other

algorithms, especially when the search space is large.

 Sensitive to Cost Differences: If edge costs vary widely, the algorithm may spend more time

re-evaluating paths with slightly different costs.

Question: Finding Path to Node G

 Step-by-Step Traversal:

 Start at S → check child nodes A and other options.

 Choose A because it has the lowest cumulative cost.

 From A, explore B → cost is still lowest.

 From B, reach G → goal reached with least total cost.

Path Found:

S→A→B→G

Total Cost: 5

INTRODUCTION TO AI AND APPLICATIONS | Dr. Venkata Madhava Ram Tatabhatla