Introduction to AI

The word "intelligence" itself resists a single precise definition, which is why textbooks define AI along two independent axes: whether the system's internal process tries to mimic human thought or instead aims purely at rational behavior, and whether we judge it by its internal reasoning or by its external actions. Crossing these two axes produces four classical schools of thought.

The Four Views of AI (Russell & Norvig framework)

Modern AI courses - including this one - adopt the "acting rationally" view as the unifying definition, because it is mathematically precise (it can be expressed as maximizing an objective/utility function) and does not require us to first solve the philosophical problem of what human thought "really is."

Scope of Artificial Intelligence

AI is not one technique - it is an umbrella spanning multiple sub-fields, each tackling a different aspect of intelligent behavior:

• Search & Planning - finding a sequence of actions from a start state to a goal state (Module 1 & 2 of this course).
• Knowledge Representation & Reasoning - encoding facts about the world so a machine can draw new conclusions (propositional/predicate logic, covered in lab experiments 9–10).
• Machine Learning - improving performance from data and experience rather than hand-coded rules (decision trees, covered in lab experiment 11).
• Uncertainty & Probabilistic Reasoning - reasoning when information is incomplete or noisy (Bayesian networks, MDPs - Module 3).
• Game Playing & Multi-agent Systems - decision-making when other intelligent agents are involved (Module 4).
• Natural Language Processing, Computer Vision, Robotics - perception and communication sub-fields (mentioned for scope, not covered as a separate module here).
• AI Ethics & Applications - responsible deployment in finance, healthcare, law enforcement (Module 5).

Quick Interview Questions

AI's history is a story of recurring waves of optimism followed by funding droughts known as "AI winters." Understanding this timeline helps explain why modern AI (rational agents, statistical learning) looks so different from 1960s AI (pure symbolic logic).

Detailed Milestones Table

AI systems are commonly classified by the breadth of tasks they can competently perform. This classification is independent of how "smart" a system looks - a chess engine that crushes grandmasters is still classified as narrow because it cannot do anything besides play chess.

Comparison Table

A third, often-mentioned category for completeness:

Key Points to Remember

• Almost all AI in production today is Narrow AI - this is a frequently tested exam fact.
• AGI is a research aspiration, not a deployed technology.
• Classification is by breadth of competence, not by performance level.

Core Vocabulary (frequently tested)

Example: Vacuum-Cleaner World (also Lab Experiment 2)

A classic teaching example: a vacuum agent lives in a world of two locations (A and B), each either Clean or Dirty. Its percepts are [location, status]; its actions are {Left, Right, Suck, NoOp}.

Types of Agent Architectures

• Simple reflex agents - act only on the current percept using condition-action rules; no memory of history.
• Model-based reflex agents - maintain an internal state/model of the unobserved parts of the world.
• Goal-based agents - choose actions that achieve an explicit goal, often requiring search/planning (this is where Module 1–2's search algorithms plug in).
• Utility-based agents - choose actions that maximize an expected utility function, allowing trade-offs between competing goals (links to Module 3's decision theory).
• Learning agents - improve their performance element over time using a learning element and a critic that evaluates outcomes against the performance measure.

Environment Types (PEAS & Properties)

Before designing an agent, we describe its task environment using the PEAS framework: Performance measure, Environment, Actuators, Sensors.

Interview Questions

Note the careful wording: rationality is about expected outcomes given available information - not about omniscience or guaranteed success. A rational agent that makes the statistically best bet can still lose due to bad luck; that does not make it irrational.

The Four Factors That Determine Rationality

1. Performance measure defining degree of success
2. Agent's prior knowledge of the environment
3. Actions the agent can perform
4. Agent's percept sequence up to the current instant

Rationality vs. Omniscience vs. Perfection

Related Concepts: Autonomy and Learning

A rational agent should not just act on built-in knowledge - it should also be autonomous: capable of learning from percepts to compensate for incomplete or incorrect prior knowledge. An agent that relies wholly on a designer's prior knowledge, ignoring its own percepts, lacks autonomy.

Key Points

• Rationality = maximizing expected performance, not guaranteeing success.
• Determined by 4 factors: performance measure, prior knowledge, actions, percept sequence.
• Rational agents should ideally also be autonomous (learn from experience).

Four-Step Problem-Solving Process

1. Goal Formulation - based on the current situation, decide what condition(s) define success.
2. Problem Formulation - decide what actions and states to consider, abstracting away irrelevant detail (this is also called the abstraction step).
3. Search - before taking any real action, simulate sequences of actions in the model to find one that reaches the goal; this produces a solution.
4. Execution - carry out the action sequence produced by the search, assuming the environment is static and predictable enough for an "open-loop" plan to remain valid throughout execution.

The Five Components of a Formally Defined Problem

Key Points

• Problem-solving = Goal formulation → Problem formulation → Search → Execution.
• A formally defined problem needs all 5 components: initial state, actions, goal test, path cost, state space.
• This is "offline" / open-loop search - the agent commits to a full plan before acting (contrast with online search agents, Module 2).

Once a problem is formally defined (Topic 1.6), it must be represented in a way that a search algorithm can process. The most common representation is the state-space graph.

State-Space Graph for the 8-Puzzle (excerpt)

Search Tree vs. State Space (frequently confused pair)

Key Data Structures in Representation

• Node - a data structure with: state, parent node, action taken to reach it, and path cost g(n).
• Frontier (Open list / Fringe) - the set of all generated-but-not-yet-expanded nodes, typically a queue.
• Explored set (Closed list) - the set of already-expanded states, used to avoid re-expanding and looping.

function TREE-SEARCH(problem):
    frontier ← {Node(problem.INITIAL_STATE)}
    loop:
        if frontier is empty: return failure
        node ← REMOVE-CHOICE(frontier)         # strategy-dependent
        if problem.GOAL-TEST(node.state): return SOLUTION(node)
        for each action in problem.ACTIONS(node.state):
            child ← CHILD-NODE(problem, node, action)
            add child to frontier

BFS is the first of three uninformed (blind) search strategies in this module. "Uninformed" means the algorithm has no domain-specific knowledge beyond the problem definition itself - no heuristic guesses about which direction looks promising (that's Module 2's job). All three strategies here only know: the current state, its neighbors, and whether a state is a goal.

Step-by-Step Working

1. Insert the root (initial state) into a FIFO queue.
2. If the queue is empty, return failure.
3. Dequeue the front node. If it is the goal, return success.
4. Otherwise, generate all of its children (successors) and enqueue them at the back.
5. Repeat from step 2.

Worked Example

Consider this tree, searched for goal node G:

Traversal order: A → B → C → D → E → G (search stops as soon as G is dequeued/goal-tested). Note: BFS finds G at depth 2 only after exhausting all of depth 1 and the earlier depth-2 siblings in FIFO order.

from collections import deque

def bfs(graph, start, goal):
    frontier = deque([[start]])      # queue of paths
    explored = set()
    while frontier:
        path = frontier.popleft()    # FIFO: pop from the left
        node = path[-1]
        if node == goal:
            return path
        if node not in explored:
            explored.add(node)
            for neighbor in graph[node]:
                new_path = list(path)
                new_path.append(neighbor)
                frontier.append(new_path)
    return None   # failure

graph = {'A':['B','C'], 'B':['D','E'], 'C':['G','F'], 'D':[], 'E':[], 'G':[], 'F':[]}
print(bfs(graph, 'A', 'G'))   # ['A', 'C', 'G']

Properties of BFS (the "4 properties" every search algorithm is graded on)

Applications

• Finding shortest path in an unweighted graph (e.g., social network "degrees of separation")
• Web crawlers (level-by-level crawling)
• GPS navigation systems for unweighted road networks
• Peer-to-peer networks (finding nearest peer)
• Puzzle solvers where all moves have equal cost (e.g., simplified 8-puzzle)

Interview & Exam Questions

Step-by-Step Working

1. Push the root node onto a stack.
2. If the stack is empty, return failure.
3. Pop the top node. If it is the goal, return success.
4. Otherwise, push its (unvisited) children onto the stack.
5. Repeat from step 2, always exploring the most recently pushed node next.

Worked Example (same tree as BFS, for direct comparison)

Traversal order: A → B → D (dead end, backtrack) → E (dead end, backtrack) → C → G (goal found!). Notice DFS explores the entire left subtree before even looking at C - very different from BFS's level-order visit.

def dfs(graph, start, goal, path=None, visited=None):
    if path is None: path = [start]
    if visited is None: visited = set()
    visited.add(start)
    if start == goal:
        return path
    for neighbor in graph[start]:
        if neighbor not in visited:
            result = dfs(graph, neighbor, goal, path + [neighbor], visited)
            if result:
                return result
    return None   # backtrack

graph = {'A':['B','C'], 'B':['D','E'], 'C':['G','F'], 'D':[], 'E':[], 'G':[], 'F':[]}
print(dfs(graph, 'A', 'G'))   # ['A', 'C', 'G']

Properties of DFS

Variant: Depth-Limited Search & Iterative Deepening

To fix DFS's incompleteness, Depth-Limited Search (DLS) imposes a maximum depth limit ℓ, refusing to expand nodes beyond that depth. Iterative Deepening DFS (IDDFS) repeatedly runs DLS with increasing limits (0,1,2,…) - combining DFS's low memory use with BFS's completeness and optimality (under uniform costs), at the cost of re-expanding shallow nodes multiple times.

Applications

• Maze and puzzle solving (where memory is constrained)
• Topological sorting and cycle detection in graphs
• Solving constraint satisfaction problems via backtracking (Module 4)
• Finding connected components in a graph
• Generating game trees in game-playing AI (Module 4's Minimax)

Interview & Exam Questions

UCS is essentially identical to Dijkstra's Algorithm from graph theory, applied within the search-agent framework, stopping as soon as a goal node is dequeued (rather than computing shortest paths to every node).

Step-by-Step Working

1. Insert the root with g(root) = 0 into a priority queue ordered by g(n).
2. If the queue is empty, return failure.
3. Remove the node with the smallest g(n). Perform the goal test at expansion time (not at insertion time - this distinction is crucial for correctness).
4. If it's the goal, return success.
5. Otherwise, expand it: for each child, compute g(child) = g(parent) + step cost. If the child is new, or found via a cheaper path than previously recorded, insert/update it in the priority queue.
6. Repeat from step 2.

Worked Example

UCS frontier evolves as: {S(0)} → expand S → {A(1), B(4)} → expand A (lowest g) → {B(4), G(3), C(6)} → expand G (lowest g=3, and it's the goal) → return path S→A→G, cost 3. Notice B (cost 4) was never expanded, and the algorithm correctly preferred the cheaper 2-hop path over a tempting 1-hop alternative.

import heapq

def ucs(graph, start, goal):
    # graph[node] = list of (neighbor, cost)
    frontier = [(0, start, [start])]   # (path_cost, node, path)
    explored = set()
    while frontier:
        cost, node, path = heapq.heappop(frontier)
        if node == goal:
            return path, cost
        if node in explored:
            continue
        explored.add(node)
        for neighbor, step_cost in graph.get(node, []):
            if neighbor not in explored:
                heapq.heappush(frontier, (cost + step_cost, neighbor, path + [neighbor]))
    return None, float('inf')

graph = {'S':[('A',1),('B',4)], 'A':[('G',2),('C',5)], 'B':[('G',1)]}
print(ucs(graph, 'S', 'G'))   # (['S', 'A', 'G'], 3)

Properties of UCS

BFS vs UCS - The Most-Asked Comparison

Applications

• Shortest path in weighted graphs (road networks with real distances/times)
• Network routing protocols
• Currency arbitrage / cheapest-flight-style search problems
• Lab Experiment 6(ii) of this course: "Shortest path problem using Lowest-Cost-First Search"

Interview & Exam Questions