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 heuristic
1. Uses no extra information
information or additional
Knowledge about the problem; only the
knowledge to guide the
used problem definition is known.
search.

More efficient as it
Less efficient because it
2. Efficiency focuses on promising paths
explores all possibilities blindly.
using heuristics.

3. Example Breadth-First Search (BFS), Best-First Search, A*

Basis Uninformed Search Informed Search

Depth-First Search (DFS),

algorithms Algorithm, Greedy Search
Uniform Cost Search

Explores the search tree

4. Search Explores the search tree
intelligently using
direction blindly.
guidance.

5. Time and Consumes more time and Consumes less time and
space memory. 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

1. Evaluation
function h(n)to estimate start g(n) and heuristic cost to
function
the cost to the goal. goal h(n), i.e., f (n)=g(n)+ h(n).

Guaranteed to find the optimal

Not guaranteed to find
2. Optimality solution if the heuristic is
the optimal solution.
admissible.

3.
May fail to find a solution Complete, provided the
Completenes
in some cases. branching factor is finite.
s

Greedily chooses the Balances between the cost so

4. Focus node that appears far and estimated cost to goal
closest to the goal. for better decision-making.

Can be faster but may More efficient and reliable in

5. Efficiency
lead to suboptimal paths. finding 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

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

Works on AND–OR graphs,

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

Finds the shortest or

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

Uses heuristic evaluation for both

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

5. Used in pathfinding Used in problem-solving with

Applicatio and navigation multiple dependent tasks (e.g.,
n problems. planning, task 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 h(n)to estimate the cost from the current
node to the goal.

 Combines actual cost so far g(n) and estimated cost h(n)to

choose the next node:

f (n)=g(n)+ h(n)

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

f (n)=g(n)+ h(n)

where:

 g(n)= actual cost from start to current node.

 h(n)= 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 g(n)and f (n)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 g(n)= distance traveled so far.

o h(n)= 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

Feature AO*
Climbing, Best-First)*

Graph Works on simple state-space

Works on AND–OR graphs
type graphs

Goal Handles subgoals with

Usually single-goal path
structure dependencies

Finds optimal solution Depends on algorithm (A*

Optimality
considering all subgoals optimal, 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

Type Local search, Informed Informed Informed

 Best-First
Feature Hill Climbing A* AO*
Search

search for
heuristic search search AND–OR
graphs

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

Guaranteed if Guaranteed for

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

Completenes May not

May get stuck Complete Complete
s find solution

Memory
Low Medium High High
requirement

Simple Planning with

Pathfinding, Pathfinding,
Applications optimization dependent
routing navigation
problems subgoals