PG S1 M.Sc. AI First internal examination, Introduction to Artificial Intelligence, September 2024
Solutions – Introduction to
Artificial Intelligence
Section A
1. Graphs
are collections of vertices (points) connected by edges (line segments),
forming paths and cycles. Matching in graphs can be used to identify patterns,
find optimal routes, and analyze relationships.
2.
Uninformed search techniques, also known as blind search techniques, are a
category of search algorithms that operate without any additional information
about the goal's location beyond the problem's definition. These algorithms do
not have any domain-specific knowledge or heuristic function to guide the
search. They explore the search space in a systematic way, generating all
possible states and paths to find a solution.
Here are the
names of common uninformed search techniques:
1.
Breadth-First
Search (BFS)
2.
Depth-First
Search (DFS)
3.
Uniform
Cost Search (UCS)
4.
Depth-Limited
Search (DLS)
5.
Iterative
Deepening Depth-First Search (IDDFS)
6.
Bidirectional
Search
3. Some key approaches to AI that are similar to human behavior:
1.
Cognitive Modeling Approach
The
cognitive modeling approach aims to create computational models that mimic
human cognitive processes. This approach is inspired by psychology and
neuroscience, attempting to replicate how humans think, remember, solve
problems, and make decisions. The primary goal is to build systems that think
like humans by simulating various aspects of human cognition.
- Examples:
- Expert Systems: Mimic the decision-making
ability of a human expert by using rules and logic derived from human
knowledge.
- Cognitive Architectures: Such as ACT-R (Adaptive
Control of Thought-Rational) and Soar, which are designed to model the
cognitive processes of the human mind, including memory, learning, and
problem-solving.
4. In this
approach, the agent uses logical reasoning, planning, and decision-making
strategies to choose actions that lead to its goals. It does not necessarily
mimic human behavior but instead aims to make the most rational choice in any
given situation. This approach is foundational in AI because it provides a
clear objective for creating intelligent systems: to act rationally and
efficiently in their environments.
5.
Best-First Search can be worse than BFS when the heuristic function is
misleading or not informative, when there is a risk of heuristic
overestimation, or when dealing with deceptive search spaces or uniform spaces
where heuristics provide no advantage. In such scenarios, the straightforward,
level-wise exploration of BFS can outperform the heuristic-driven approach of
Best-First Search.
Section B
7.
Depth-First
Search (DFS) is an uninformed search algorithm that explores as far as possible
along a branch before backtracking. It uses a stack (or recursion) to keep
track of the nodes to visit next.
Advantages:
1.
Memory Efficiency: DFS uses less memory compared to Breadth-First Search (BFS) because it
stores only the nodes on the current path, not all nodes at a level.
2.
Can Find Solutions Quickly: In scenarios where the solution is located deep in the tree
or graph, DFS can potentially reach it faster if it explores the correct branch
early.
3.
Suitable for Infinite Search Spaces: DFS can be used in scenarios with infinite search
spaces where BFS would be impractical due to memory constraints.
Disadvantages:
1.
Can Get Stuck in Infinite Loops: If the search space has cycles or an infinite depth, DFS
might keep exploring the same nodes or paths indefinitely.
2.
May Not Find the Shortest Path: DFS does not guarantee the shortest path or optimal
solution, as it explores nodes without considering the shortest path to the
goal.
3.
Deep Branches May Lead to High Time Complexity: If the solution is in a deep branch,
DFS might take a long time to reach it, especially if the search space is
large.
8. Heuristic search uses a heuristic function to estimate the
cost or distance to the goal, guiding the search process more efficiently than
uninformed search methods.
Heuristic Functions:
1.
Euclidean Distance:
Estimates the straight-line distance between two points in a Euclidean space.
2.
Manhattan Distance:
Measures the sum of the absolute differences in the horizontal and vertical
distances between two points.
9. Solving the Farmer, Fox, Goose, and
Cereal Problem Using BFS
1.
State Representation:
o Each state is a combination of where
the farmer, fox, goose, and cereal are (Left or Right).
2.
Initial State:
o All on the Left side: (Left, Left,
Left, Left)
3.
Goal State:
o All on the Right side: (Right, Right,
Right, Right)
4.
BFS Steps:
o Start with Initial State: Add it to the queue.
o Explore All Possible Moves:
§ Farmer moves alone or with one item
at a time.
o Check Constraints: Ensure the fox isn't left alone with
the goose, and the goose isn't left alone with the cereal.
o Generate New States: From each state, generate new states
based on valid moves.
o Repeat: Continue exploring each state in the
queue until you reach the goal state.
5.
Find Solution:
o BFS ensures that you explore all
possible ways to get to the goal and find the shortest path.
Example Solution Path:
1.
Move
the goose across.
2.
Return
alone.
3.
Move
the fox across.
4.
Return
with the goose.
5.
Move
the cereal across.
6.
Return
alone.
7.
Move
the goose across.
Section C
10. Evolution of Artificial Intelligence
(AI)
1.
Early
Foundations (1940s - 1960s):
o 1940s-50s: Conceptual groundwork laid
by Alan Turing with ideas like the Turing Test and the concept of a
"universal machine."
o 1956: The term "Artificial
Intelligence" was coined at the Dartmouth Conference, marking the formal
start of AI research. Early AI focused on symbolic reasoning and logic-based
problem-solving with programs like the Logic Theorist and General Problem
Solver.
2.
Symbolic
AI and Expert Systems (1970s - 1980s):
o 1970s: The rise of symbolic AI and
expert systems, which used rule-based systems to simulate human expertise.
Despite some initial success, these systems faced limitations such as high
development costs and difficulty handling complex, real-world data.
o 1980s: The introduction of
knowledge-based systems and expert systems like MYCIN showcased practical
applications, but the field experienced the first AI winter due to overhyped
promises and underwhelming results.
3.
Machine
Learning and the Second AI Winter (1980s - 2000s):
o Late 1980s: Shift towards machine
learning approaches, with algorithms like decision trees and support vector
machines gaining prominence. Research in neural networks also re-emerged with
the rediscovery of the backpropagation algorithm.
o 1990s-2000s: AI faced another period
of stagnation, known as the second AI winter, due to slow progress and high
expectations not being met.
4.
Deep
Learning and Modern AI (2000s - Present):
o 2010s: Major breakthroughs with deep
learning, leveraging large datasets and powerful GPUs. Key milestones include
AlexNet's success in the 2012 ImageNet competition and AlphaGo's victory over a
world champion in 2016. These advances demonstrated AI's capabilities in image
recognition, natural language processing, and game-playing.
o Present: AI is now integrated into
various applications, including healthcare, finance, and autonomous vehicles.
Research continues to focus on improving ethics, fairness, and working towards
Artificial General Intelligence (AGI).
11. AND-OR graphs are a type of graph used in AI and problem-solving to
represent states and their relationships, particularly in the context of
problems that involve both conjunctive (AND) and disjunctive (OR) conditions.
They are used to model problems where some conditions must be satisfied
together (AND) and others can be satisfied individually (OR).
Structure:
·
Nodes:
Represent states or sub-goals.
·
Edges:
o AND Edges: Indicate that all connected
sub-goals must be achieved to satisfy the parent node.
o OR Edges: Indicate that achieving any one of
the connected sub-goals is sufficient to satisfy the parent node.
Advantages
1.
Clarity
2.
Flexibility
3.
Effective
4.
Decomposable
Disadvantages
1.
Complexity
2.
Overhead
3.
Optimization
Comments
Post a Comment