Unit – 1 Fundamental of AI

Question 1: Define Artificial Intelligence.

Artificial Intelligence (AI) is the branch of computer science that deals with creating
machines or software capable of performing tasks that normally require human
intelligence.

Definition:

Artificial Intelligence is defined as:

“The ability of a machine to think, learn, and make decisions like humans.”

Explanation:

AI systems are designed to perceive their environment, reason about information,

learn from experience, and act intelligently to achieve specific goals.

Examples:

• Voice assistants like Siri and Alexa

• Self-driving cars

• Chatbots and recommendation systems

Question 2: What is a production system in AI?

A Production System in Artificial Intelligence (AI) is a computer program structure
used to represent and apply knowledge to solve problems. It consists of a set of rules
and a control system that determines how these rules are applied to reach a solution.

Components of a Production System:

1. Production Rules (Knowledge Base):

These are IF–THEN statements that represent knowledge.
 Example:
IF the sky is cloudy → THEN it may rain.

2. Working Memory (Database):

It stores the current situation or facts about the problem.

3. Inference Engine (Control System):

It decides which rule to apply, applies it, and updates the working memory.

Working of a Production System:

• The inference engine matches the conditions of rules with facts in the working
memory.

• When a rule matches, it is “fired” (executed), and its action part updates the
memory.

• This process continues until a goal state or solution is reached.

Example:

IF temperature < 0°C → THEN water = ice

IF temperature > 100°C → THEN water = vapor

Advantages:

• Easy to modify and expand knowledge.

• Works well for reasoning and decision-making tasks.

Question 3: List any two characteristics of production

systems.
Two characteristics of Production Systems are:

1. Knowledge-based:
A production system stores knowledge in the form of production rules (IF–THEN
statements), making it easy to represent and modify expert knowledge.
 2. Goal-oriented behaviour:
The system applies rules step-by-step using an inference engine to reach a
specific goal or solution from given facts.

Question 4: Define Heuristic.

A Heuristic is a problem-solving technique in Artificial Intelligence that uses
experience-based or rule-of-thumb methods to find solutions more quickly when an
exact or optimal solution is difficult to obtain.

Definition:

“A heuristic is a strategy or guideline that helps in solving problems faster and more
efficiently by reducing the search space.”

Example:

In a maze-solving problem, choosing the path that appears to move closer to the goal
is a heuristic approach.

Question 5: Differentiate between informed and uninformed

search.
The difference between Informed and Uninformed Search in Artificial Intelligence is
given below:

Basis Uninformed Search Informed Search

Uses no extra information about Uses heuristic information or

1. Knowledge
the problem; only the problem additional knowledge to guide
used
definition is known. the search.

More efficient as it focuses on

Less efficient because it explores
2. Efficiency promising paths using
all possibilities blindly.
heuristics.
Basis Uninformed Search Informed Search

Breadth-First Search (BFS), Depth-

3. Example Best-First Search, A* Algorithm,
First Search (DFS), Uniform Cost
algorithms Greedy Search
Search

4. Search Explores the search tree

Explores the search tree blindly.
direction intelligently using guidance.

5. Time and Consumes less time and

Consumes more time and memory.
space memory (usually).

Question 6: What is the significance of the A* algorithm?

The A* (A-star) algorithm is a popular and important informed search algorithm used
in Artificial Intelligence for finding the shortest or most efficient path from a start node
to a goal node.

Significance of A* Algorithm:

1. Combines the best of both worlds:

It uses both the actual cost from the start node (g(n)) and the estimated cost to
the goal (h(n)) to make intelligent decisions.

2. Optimal and complete:

If the heuristic function is admissible (never overestimates the cost), A* is
guaranteed to find the optimal solution.

3. Efficient pathfinding:
A* reduces the number of nodes explored, making it faster and more efficient
than uninformed searches.

4. Widely used:
Commonly used in robotics, maps, games, and navigation systems for
shortest path finding.
Question 7: Define hill climbing search technique.
Hill Climbing Search is a heuristic search technique in Artificial Intelligence that
continuously moves in the direction of increasing value (uphill) to find the best or
optimal solution.

Definition:

“Hill Climbing is a local search algorithm that starts with an initial solution and
iteratively moves to a better neighbouring state until no further improvement is
possible.”

Explanation:

• It evaluates the neighbouring states of the current state.

• If a neighbour has a better (higher) value, the algorithm moves to that state.

• The process continues until a peak (local maximum) is reached.

Example:

In a pathfinding problem, hill climbing always chooses the next step that appears to
get closer to the goal.

Question 8: What is a search space?

A Search Space in Artificial Intelligence refers to the set of all possible states or
solutions that can be explored to solve a given problem.

Definition:

“Search space is the collection of all possible states or configurations that can be
reached while solving a problem.”

Explanation:
 • Each point or node in the search space represents a possible state of the
problem.

• The search algorithm explores this space to find a path from the initial state to
the goal state.

Example:

In a maze problem, every position in the maze is a state, and all possible paths through
the maze form the search space.

Question 9: What is the role of heuristics in search

algorithms?
The role of heuristics in search algorithms is to guide the search process toward the
most promising paths, helping the algorithm find solutions faster and more efficiently.

Definition:

“A heuristic is a rule-of-thumb or an estimate used to evaluate which path is likely to

lead to the best solution.”

Roles / Functions:

1. Guides the search:

Heuristics help the algorithm decide which node to explore next based on
estimated cost or distance.

2. Reduces search time:

By focusing only on promising paths, heuristics reduce the number of nodes
explored.

3. Improves efficiency:
They make the search process faster and more goal-directed.

4. Used in informed searches:

Algorithms like A* and Greedy Best-First Search rely heavily on heuristic
functions.
Question 10: State any two applications of AI in modern
technology.
Two applications of Artificial Intelligence (AI) in modern technology are:

1. Self-Driving Cars:
AI is used in autonomous vehicles to detect objects, follow traffic rules, and
make driving decisions using sensors and machine learning algorithms.

2. Virtual Assistants:
AI powers assistants like Siri, Alexa, and Google Assistant to understand voice
commands, answer questions, and perform tasks for users.

Question 11: What is the difference between Best-First Search

and A* Search?
The difference between Best-First Search and A* Search in Artificial Intelligence is as
follows:

Basis Best-First Search A* Search

Uses only the heuristic Uses both actual cost from start
1. Evaluation
function ℎ(𝑛)to estimate the 𝑔(𝑛)and heuristic cost to goal ℎ(𝑛),
function
cost to the goal. i.e., 𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛).

Not guaranteed to find the Guaranteed to find the optimal

2. Optimality
optimal solution. solution if the heuristic is admissible.

3. May fail to find a solution in Complete, provided the branching

Completeness some cases. factor is finite.

Greedily chooses the node Balances between the cost so far and
4. Focus that appears closest to the estimated cost to goal for better
goal. decision-making.

Can be faster but may lead to More efficient and reliable in finding
5. Efficiency
suboptimal paths. the shortest path.
Question 12: What is the goal of AI?
The goal of Artificial Intelligence (AI) is to create machines or systems that can
perform tasks requiring human intelligence.

Explanation:

AI aims to enable machines to:

1. Think and reason like humans.

2. Learn from experience and improve performance.

3. Solve complex problems efficiently.

4. Understand natural language and interact with humans.

5. Perceive the environment and take appropriate actions.

Question 13: Why is AI needed in today’s world?

Artificial Intelligence (AI) is needed in today’s world because it helps humans
perform tasks faster, more accurately, and efficiently, especially in complex and
data-driven environments.

Reasons why AI is needed:

1. Automation of tasks:
AI can automate repetitive and mundane tasks, saving time and reducing
human effort.

2. Handling large data:

AI can analyze massive amounts of data quickly to extract useful insights.

3. Improved decision-making:
AI systems provide intelligent recommendations and solutions, helping in
better decisions.

4. Advanced technologies:
AI powers self-driving cars, virtual assistants, medical diagnosis systems,
and smart devices.
 5. Efficiency and accuracy:
AI reduces errors and increases productivity in industries, healthcare, finance,
and more.

Question 14: What is the difference between AO* and A*

search algorithms?
The difference between AO* and A* search algorithms is as follows:

Basis A* Search AO* Search

Solves problems with a

1. Type of Solves AND–OR graphs with multiple
single goal path (simple
problem subgoals and dependencies.
graphs or trees).

Works on AND–OR graphs, considering

2. Graph Works on state-space
both AND (all children needed) and OR
structure graphs.
(any one child) nodes.

Finds the shortest or least-

Finds optimal solution paths considering
3. Optimality cost path if heuristic is
multiple subgoals.
admissible.

Uses f(n) = g(n) + h(n) to Uses heuristic evaluation for both AND
4. Approach
evaluate nodes. and OR nodes to choose the best path.

Used in problem-solving with multiple

5. Used in pathfinding and
dependent tasks (e.g., planning, task
Application navigation problems.
decomposition).

Question 15: Explain the fundamental concepts of Artificial

Intelligence.
The fundamental concepts of Artificial Intelligence (AI) are the basic ideas that form
the foundation of AI systems and their problem-solving abilities.
1. Intelligent Agents:

An intelligent agent is an entity that perceives its environment, processes

information, and takes actions to achieve specific goals.
Example: Robots, chatbots, self-driving cars.

2. Problem-Solving:

AI systems aim to solve problems by searching for solutions in a structured manner

using techniques like search algorithms, heuristics, and optimization.

3. Knowledge Representation:

AI needs to store and use knowledge effectively. This can be done using:

• Rules (Production systems)

• Semantic networks

• Frames

• Ontologies

4. Reasoning and Inference:

AI systems draw conclusions from existing knowledge using logical reasoning.

Example: Deductive reasoning, inductive reasoning, probabilistic reasoning.

5. Learning:

AI systems can learn from experience or data to improve performance over time.
Example: Machine learning, neural networks, reinforcement learning.

6. Perception:

AI systems can interpret inputs from the environment, such as images, speech, or
sensor data.
Example: Computer vision, speech recognition.

7. Natural Language Processing (NLP):

Enables machines to understand, interpret, and generate human language.

Question 16: Write a detailed note on the history and evolution

of AI.
Artificial Intelligence (AI) is a field of computer science focused on creating machines
that can mimic human intelligence. Its development has gone through several stages:

1. Early Concepts (1940s – 1950s):

• The concept of AI started with Alan Turing (1950), who proposed the Turing Test
to determine if a machine can think like a human.

• John McCarthy coined the term “Artificial Intelligence” in 1956 at the Dartmouth
Conference, marking the formal beginning of AI as a research field.

2. Early AI Programs (1950s – 1960s):

• Simple programs were developed to solve mathematical problems and games,

like Logic Theorist (1955) and General Problem Solver (GPS).

• AI research focused on symbolic reasoning and rule-based systems.

3. Knowledge-Based Systems (1970s – 1980s):

• Development of expert systems that used production rules to mimic human

experts.

• Example: MYCIN for medical diagnosis.

• Focus shifted from simple problem-solving to domain-specific intelligence.

4. AI Winter (Late 1980s – Early 1990s):

• Reduced funding and progress due to limitations of early AI systems.

• Problems included high computational costs and lack of robust learning

methods.
5. Modern AI (1990s – Present):

• AI evolved with machine learning, neural networks, and big data analytics.

• Deep learning enabled breakthroughs in computer vision, NLP, and robotics.

• AI is now applied in autonomous vehicles, virtual assistants, healthcare, and

recommendation systems.

Question 17: What are the goals of Artificial Intelligence? How

does it contribute to modern technology?
Goals of Artificial Intelligence (AI):

The main goals of AI are to create systems that can perform tasks requiring human
intelligence. These include:

1. Reasoning and Problem Solving:

o AI aims to analyse information and make decisions to solve complex

problems efficiently.

2. Learning:

o AI systems learn from experience or data to improve performance over

time (Machine Learning, Neural Networks).

3. Perception:

o AI enables machines to perceive and interpret the environment using

sensors, cameras, or microphones (Computer Vision, Speech
Recognition).

4. Natural Language Understanding:

o AI helps machines understand, process, and generate human language

for communication (Chatbots, Virtual Assistants).

5. Autonomy:

o AI systems aim to act independently, performing tasks without human

intervention (Robotics, Self-Driving Cars).

Contribution of AI to Modern Technology:

 1. Automation:

o AI automates repetitive and time-consuming tasks, improving

efficiency in industries and services.

2. Enhanced Decision-Making:

o AI analyses large datasets to provide insights and recommendations,

aiding better business, medical, and scientific decisions.

3. Smart Devices and Services:

o AI powers virtual assistants, recommendation systems, autonomous

vehicles, and smart home technologies.

4. Healthcare Advancements:

o AI is used for medical diagnosis, drug discovery, and personalized

treatment plans.

5. Improved Accuracy and Productivity:

o AI reduces human error, speeds up processes, and increases

productivity across sectors like finance, education, and manufacturing.

Question 18: What is heuristic search? Explain with examples.

Heuristic Search in AI:

A heuristic search is a problem-solving technique in Artificial Intelligence that uses

experience-based rules or guidelines (heuristics) to find solutions more efficiently
when searching through large or complex problem spaces.

Definition:

“Heuristic search is a method of searching for solutions in which heuristic functions

guide the search towards the goal, reducing the time and effort compared to exhaustive
search.”

Key Points:

1. Guided Search: Uses heuristics to choose the most promising path.

2. Efficiency: Reduces the number of states or nodes explored.

 3. Approximate Solutions: May not always guarantee the optimal solution but
provides good solutions quickly.

Example 1: Maze Problem

• Problem: Find the shortest path from start to goal in a maze.

• Heuristic: Choose the next step that appears closest to the goal (e.g., based on
straight-line distance).

• This avoids exploring all possible paths blindly.

Example 2: A* Algorithm

• Uses a heuristic function ℎ(𝑛)to estimate the cost from the current node to the
goal.

• Combines actual cost so far 𝑔(𝑛)and estimated cost ℎ(𝑛)to choose the next
node:

𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛)

• Efficiently finds the shortest path in navigation and routing problems.

Question 19: Explain the working of Hill Climbing algorithm

with its advantages and limitations.
Hill Climbing is a heuristic search algorithm that starts from an initial state and
iteratively moves to the neighbour with the highest value (closest to the goal), aiming
to reach a peak or optimal solution.

Working Steps:

1. Start with an initial solution/state.

2. Evaluate the neighbouring states.

3. Move to the neighbour with the best evaluation (highest value or lowest cost).

4. Repeat steps 2–3 until:

 o No neighbour is better (local maximum), or

o Goal state is reached.

Advantages:

• Simple and easy to implement.

• Requires less memory as it stores only the current state.

• Efficient for problems with well-defined heuristics.

Limitations:

• Can get stuck at local maxima instead of reaching the global maximum.

• Fails at plateaus where all neighbours have the same value.

• May not explore all possible solutions.

Example:

• In a maze, always choosing the next step that brings you closer to the exit is an
example of hill climbing.

Question 20: Describe the A* search algorithm in detail. Give a

suitable example.
Definition:
A* is an informed search algorithm that finds the shortest path from a start node to a
goal node using:

𝑓(𝑛) = 𝑔(𝑛) + ℎ(𝑛)

where:

• 𝑔(𝑛)= actual cost from start to current node.

• ℎ(𝑛)= estimated cost from current node to goal (heuristic).

Working Steps:

1. Place the start node in the open list.

 2. Select the node with the lowest f(n) from the open list.

3. Expand the selected node (generate its neighbours).

4. Update 𝑔(𝑛)and 𝑓(𝑛)for neighbors.

5. Repeat until the goal node is selected.

Example:

• Finding the shortest route on a map from city A to city B.

o 𝑔(𝑛)= distance traveled so far.

o ℎ(𝑛)= straight-line distance to goal.

Advantages:

• Guarantees optimal solution if heuristic is admissible.

• Efficient and less time-consuming than uninformed search.

Question 21: Explain the AO* search algorithm and how it

differs from other search techniques.
Definition:
AO* (AND–OR search) is a heuristic search algorithm designed for AND–OR graphs,
where some nodes require all child nodes (AND) to be solved, while others require any
one child (OR) to be solved.

Working Steps:

1. Start at the initial node.

2. Evaluate OR nodes by selecting the child with the minimum cost.

3. Evaluate AND nodes by summing costs of all children.

4. Expand the most promising node using heuristics.

5. Continue until the goal state is reached.

Difference from other searches:

Other Searches (A, Hill Climbing,

Feature AO*
Best-First)*

Works on simple state-space

Graph type Works on AND–OR graphs
graphs

Goal Handles subgoals with

Usually single-goal path
structure dependencies

Finds optimal solution Depends on algorithm (A* optimal,

Optimality
considering all subgoals Hill Climbing may not)

Question 22: Compare and contrast the various search

strategies: Hill Climbing, Best-First Search, A*, and AO*.
Best-First
Feature Hill Climbing A* AO*
Search

Informed search
Local search, Informed
Type Informed search for AND–OR
heuristic search
graphs

Yes, evaluates Yes, uses Yes, evaluates

Heuristic usage Yes, uses h(n)
neighbors g(n)+h(n) AND & OR nodes

Guaranteed if Guaranteed for

Not
Optimality Not guaranteed heuristic is AND–OR
guaranteed
admissible problems

May not find

Completeness May get stuck Complete Complete
solution

Memory
Low Medium High High
requirement

Simple Planning with

Pathfinding, Pathfinding,
Applications optimization dependent
routing navigation
problems subgoals