Problem-Solving and Search Agents

This is the first informed (heuristic) search algorithm in the course. Unlike Module 1's blind strategies, informed search uses problem-specific knowledge - a heuristic function h(n) - to estimate how close a state is to the goal, allowing the search to prioritize promising directions.

Worked Example - Romania Map Problem

Using straight-line distance to Bucharest as h(n): from Arad, the agent greedily picks the neighbor with smallest h (e.g., Sibiu, h=253), then from Sibiu picks Fagaras (h=176) over Rimnicu Vilcea (h=193), then Fagaras→Bucharest. This finds a solution fast (Arad-Sibiu-Fagaras-Bucharest, 450 km) but it is not the optimal 418 km route via Rimnicu Vilcea & Pitesti - illustrating Greedy's key weakness.

import heapq

def greedy_best_first(graph, start, goal, h):
    frontier = [(h[start], start, [start])]
    visited = set()
    while frontier:
        _, node, path = heapq.heappop(frontier)
        if node == goal:
            return path
        if node in visited:
            continue
        visited.add(node)
        for neighbor, _cost in graph.get(node, []):
            if neighbor not in visited:
                heapq.heappush(frontier, (h[neighbor], neighbor, path + [neighbor]))
    return None

Properties

Applications

• Pathfinding in video games where near-optimal (not perfect) routes are acceptable
• Web crawling prioritized by relevance score
• Quick approximate solutions in robotics navigation

A* (pronounced "A-star") is the single most important search algorithm in classical AI - it combines UCS's guarantee of optimality with Greedy Search's speed, by considering both the cost already paid and the estimated cost remaining.

Step-by-Step Working

1. Insert the start node into a priority queue ordered by f(n) = g(n)+h(n); g(start)=0.
2. Pop the node with lowest f(n).
3. If it's the goal, return the solution (this is guaranteed optimal - see proof below).
4. Otherwise expand it: for each successor, compute g(child) = g(parent) + step cost, h(child) from the heuristic, and f(child) = g+h.
5. If the child is new, or this path is cheaper than a previously found path to it, insert/update it in the frontier.
6. Repeat from step 2.

Worked Example - Romania Map (same problem, A* this time)

Notice that A* correctly finds the 418 km optimal path via Rimnicu Vilcea and Pitesti - the same route Greedy Search missed - because it never lets a low h(n) override a high accumulated g(n).

import heapq

def a_star(graph, start, goal, h):
    frontier = [(h[start], 0, start, [start])]   # (f, g, node, path)
    best_g = {start: 0}
    while frontier:
        f, g, node, path = heapq.heappop(frontier)
        if node == goal:
            return path, g
        if g > best_g.get(node, float('inf')):
            continue
        for neighbor, step_cost in graph.get(node, []):
            new_g = g + step_cost
            if new_g < best_g.get(neighbor, float('inf')):
                best_g[neighbor] = new_g
                new_f = new_g + h[neighbor]
                heapq.heappush(frontier, (new_f, new_g, neighbor, path + [neighbor]))
    return None, float('inf')

Properties of A*

A* vs Greedy vs UCS - Master Comparison Table

Applications

• GPS and map navigation (turn-by-turn routing)
• Video game pathfinding (NPC movement)
• Robotics motion planning
• Puzzle solvers (8-puzzle, 15-puzzle - Lab Experiment 5)
• Network routing optimization

Interview & Exam Questions

A* is only as good as its heuristic. This topic focuses on the standard engineering technique for designing a heuristic: relaxing the problem.

Worked Example - 8-Puzzle Heuristics

The 8-puzzle's rule is: "a tile can move from square A to square B if A is horizontally/vertically adjacent to B AND B is blank." Two classic relaxations give two classic heuristics:

Dominance - Comparing Heuristic Quality

Other Common Heuristic-Construction Techniques

• Pattern Databases - precompute exact solution costs for a sub-problem (e.g., a subset of 8-puzzle tiles) and store them in a lookup table for fast heuristic estimates.
• Combining heuristics via max() - if h1, h2, …, hk are all admissible, h(n) = max(h1(n),…,hk(n)) is also admissible and dominates each individually - never average, since averaging can break admissibility if any one heuristic is too optimistic relative to the others' combination logic; max is always safe.
• Learning heuristics from experience - using machine learning (e.g., regression) on solved instances to predict h(n) for unseen states.

Key Theorem: Consistency ⟹ Admissibility

Every consistent heuristic is also admissible (the reverse is not always true). This can be shown by induction along any path to the goal: since h(goal)=0, repeatedly applying the consistency inequality back to n shows h(n) is bounded by the actual path cost, hence h(n) ≤ h*(n).

Why Consistency Matters for Graph-Search

Graph-Search A* discards a node once it has been expanded, to avoid redundant work. If h(n) is merely admissible but not consistent, it's possible to later discover a cheaper path to an already-expanded node - but since that node was discarded, A* can never use the cheaper path, breaking optimality. Consistency guarantees that the first time a node is popped from the frontier, it has already been reached via its cheapest possible path.

Key Points

• Admissible = never overestimates total remaining cost (global property).
• Consistent = obeys the triangle inequality step-by-step (local property); strictly stronger.
• Consistency ⟹ Admissibility, but not vice versa.
• Graph-Search A* needs consistency; Tree-Search A* only needs admissibility.

Interview & Exam Questions

So far, every algorithm tracked entire paths from start to goal. Local search algorithms instead operate using a single current state and move to neighboring states - useful when the path itself doesn't matter, only the final configuration (e.g., optimization, scheduling, circuit design).

Step-by-Step Working

1. Start at a randomly or heuristically chosen initial state.
2. Evaluate all neighboring states using the objective function.
3. If the best neighbor is better than the current state, move to it.
4. If no neighbor is better (a local optimum), stop and return the current state.
5. Repeat from step 2.

The Landscape Metaphor

Variants of Hill Climbing

The Four Classic Problems of Hill Climbing

• Local Maxima - a peak lower than the global maximum, where every neighbor is worse, trapping the search.
• Plateaus / Shoulders - a flat region where neighbors have equal value, giving no directional signal.
• Ridges - a sequence of local maxima very difficult to navigate using only single-step axis-aligned moves.
• Diagonal/complex landscapes - Hill Climbing has no memory or lookahead, so it can't "see" a better path that requires temporarily moving downhill.

def hill_climbing(initial_state, get_neighbors, objective):
    current = initial_state
    while True:
        neighbors = get_neighbors(current)
        best_neighbor = max(neighbors, key=objective, default=None)
        if best_neighbor is None or objective(best_neighbor) <= objective(current):
            return current          # local optimum reached
        current = best_neighbor

Properties

Applications

• Circuit/VLSI design layout optimization
• Job-shop and timetable scheduling
• N-Queens problem (minimizing conflicts)
• Neural network weight tuning (early/simple optimizers)

Simulated Annealing (SA) fixes Hill Climbing's local-optimum trap by occasionally allowing downhill (worse) moves, with decreasing probability over time - directly inspired by the metallurgical process of annealing, where metal is heated then slowly cooled to reach a low-energy, stable crystalline structure.

At high temperature T, this probability is close to 1 - the algorithm explores almost freely, like molten metal with highly mobile atoms. As T → 0, the probability of accepting a worse move shrinks toward 0, and the algorithm increasingly behaves like ordinary Hill Climbing - "freezing" into a final solution.

Step-by-Step Working

1. Initialize current state randomly; set initial temperature T to a high value.
2. For each time step, decrease T according to the cooling schedule (e.g., T ← T × 0.95).
3. Pick a random neighbor of the current state.
4. Compute ΔE = value(neighbor) − value(current).
5. If ΔE > 0 (improvement), always move to the neighbor.
6. If ΔE ≤ 0 (worse), move anyway with probability e^ΔE/T; otherwise stay.
7. Repeat until T reaches (near) zero or a stopping criterion is met.

import random, math

def simulated_annealing(initial, get_random_neighbor, objective,
                         T0=100.0, cooling_rate=0.97, min_T=1e-3):
    current, T = initial, T0
    best = current
    while T > min_T:
        neighbor = get_random_neighbor(current)
        delta = objective(neighbor) - objective(current)
        if delta > 0 or random.random() < math.exp(delta / T):
            current = neighbor
            if objective(current) > objective(best):
                best = current
        T *= cooling_rate
    return best

Cooling Schedules

Properties

Applications

• VLSI circuit design and chip layout
• Traveling Salesman Problem (TSP) approximations
• Image processing / denoising
• Scheduling and resource allocation problems

Interview Questions

Hill Climbing and Simulated Annealing track a single current state. Genetic Algorithms (GAs) instead maintain an entire population of candidate solutions simultaneously, evolving them generation by generation using principles borrowed from biological evolution: selection, crossover, and mutation.

Core GA Vocabulary

Step-by-Step GA Cycle

1. Initialize - generate a random initial population of N chromosomes.
2. Evaluate - compute the fitness of every chromosome in the population.
3. Select - probabilistically choose parent pairs, favoring higher-fitness individuals.
4. Crossover - combine each parent pair at a random crossover point to produce two children.
5. Mutate - with small probability, randomly flip/alter genes in the offspring.
6. Replace - form the new generation from offspring (and optionally elite parents).
7. Repeat from step 2 until a stopping criterion (max generations, fitness threshold) is met.

Visual Walkthrough - 8-Bit Chromosome Crossover

import random

def genetic_algorithm(pop_size, gene_len, fitness_fn, generations=200, mutation_rate=0.01):
    population = [[random.randint(0,1) for _ in range(gene_len)] for _ in range(pop_size)]

    for gen in range(generations):
        fitnesses = [fitness_fn(ind) for ind in population]
        new_population = []
        for _ in range(pop_size // 2):
            p1, p2 = random.choices(population, weights=fitnesses, k=2)   # selection
            point = random.randint(1, gene_len - 1)
            c1 = p1[:point] + p2[point:]                                  # crossover
            c2 = p2[:point] + p1[point:]
            for child in (c1, c2):
                for i in range(gene_len):                                 # mutation
                    if random.random() < mutation_rate:
                        child[i] = 1 - child[i]
                new_population.append(child)
        population = new_population
    return max(population, key=fitness_fn)

Properties

Applications

• Feature selection and hyperparameter tuning in machine learning
• Scheduling, timetabling, and resource allocation
• Evolving neural network architectures (neuroevolution)
• Engineering design optimization (antenna shapes, aerodynamics)

Particle Swarm Optimization (PSO) is another population-based metaheuristic, inspired this time by the collective, decentralized behavior of bird flocks and fish schools - rather than evolution, it models social information sharing.

w = inertia weight  |  c₁,c₂ = cognitive & social coefficients  |  r₁,r₂ = random values in [0,1]

Interpreting the Velocity Update

Step-by-Step Working

1. Initialize a swarm of particles with random positions and velocities.
2. Evaluate the fitness of each particle's position.
3. Update each particle's pbest if its current position is better than its recorded pbest.
4. Update the swarm's gbest if any particle's pbest beats the current gbest.
5. Update each particle's velocity and position using the formula above.
6. Repeat from step 2 until convergence or max iterations.

import random

def pso(fitness_fn, dim, n_particles=30, iterations=100,
        w=0.7, c1=1.5, c2=1.5, bounds=(-10, 10)):
    positions = [[random.uniform(*bounds) for _ in range(dim)] for _ in range(n_particles)]
    velocities = [[0.0]*dim for _ in range(n_particles)]
    pbest = [p[:] for p in positions]
    pbest_val = [fitness_fn(p) for p in positions]
    gbest = max(pbest, key=fitness_fn)

    for _ in range(iterations):
        for i in range(n_particles):
            for d in range(dim):
                r1, r2 = random.random(), random.random()
                velocities[i][d] = (w*velocities[i][d]
                    + c1*r1*(pbest[i][d] - positions[i][d])
                    + c2*r2*(gbest[d] - positions[i][d]))
                positions[i][d] += velocities[i][d]
            if fitness_fn(positions[i]) > pbest_val[i]:
                pbest[i] = positions[i][:]
                pbest_val[i] = fitness_fn(positions[i])
        gbest = pbest[pbest_val.index(max(pbest_val))]
    return gbest

GA vs PSO - Comparison

Applications

• Neural network training (weight optimization)
• Engineering design optimization (antenna design, structural optimization)
• Power system/economic load dispatch optimization
• Robot path planning in continuous space

So far, every algorithm assumed the environment is deterministic: taking action a in state s always leads to exactly the same resulting state. Real environments are rarely this clean - a robot's wheel might slip, a vacuum's "suck" might fail to pick up all dirt. This topic extends search to handle non-deterministic (uncertain) action outcomes.

Key Shift: From a Solution Path to a Contingency Plan

Because the agent cannot know in advance which outcome will result from an action, a single fixed sequence of actions ("plan") is no longer sufficient. Instead the agent must compute a conditional plan (also called a contingency plan) - a tree-shaped plan with branches for each possible percept/outcome, e.g.: "Suck; if dirt remains, Suck again; else move Right."

AND-OR Search Trees

AND-OR-GRAPH-SEARCH (Conceptual Algorithm)

function AND-OR-SEARCH(problem):
    return OR-SEARCH(problem.INITIAL_STATE, problem, [])

function OR-SEARCH(state, problem, path):
    if problem.GOAL-TEST(state): return empty plan
    if state in path: return failure          # cycle check
    for each action in problem.ACTIONS(state):
        plan ← AND-SEARCH(RESULTS(state, action), problem, [state] + path)
        if plan ≠ failure:
            return [action] + plan
    return failure

function AND-SEARCH(states, problem, path):
    for each si in states:
        plan_i ← OR-SEARCH(si, problem, path)
        if plan_i == failure: return failure   # must succeed on EVERY outcome
    return {if outcome is si then follow plan_i, for each si}

Key Points

• Non-deterministic actions return a set of possible result states, not a single state.
• Solutions become conditional plans, represented as AND-OR trees.
• OR nodes = agent's choice; AND nodes = environment's choice - plan must succeed on every AND branch.

A further complication: what if the agent cannot even fully perceive the current state? This is the partially-observable case, requiring the agent to reason over its uncertainty about which state it's actually in.

Two Extreme Cases

Updating a Belief State

A belief state update after taking action a, then receiving percept e, has two component steps:

1. Prediction - compute the set of possible states reachable by applying a to every state currently in the belief state: b′ = ⋃_{s ∈ b} RESULTS(s,a).
2. Update (Observation) - filter b′ down to only the states consistent with the just-received percept e: b″ = {s ∈ b′ : PERCEPT(s) = e}.

Properties & Challenges

Applications

• Robot localization with noisy/limited sensors
• Medical diagnosis under incomplete patient information
• Card games with hidden information (opponent's hand)
• Autonomous exploration of unknown/unmapped terrain

Every algorithm so far has been offline: the agent computes a complete solution before taking any real action, assuming it has full knowledge of the state space in advance. Online search drops this assumption - the agent must act, observe, and decide interleaved in real time, often with an initially unknown map of the environment.

Offline vs Online Search - Direct Comparison

Online DFS Agent

A straightforward online strategy: behave like DFS, but discover ACTIONS(s) only upon actually visiting state s (since the map is unknown in advance), and maintain a "result" table of what's been learned so far. When all actions from the current state have been tried, backtrack using the agent's own physical movement (not just an algorithmic pointer) - since the agent must physically retrace its steps in the real world.

LRTA* - Learning Real-Time A*

function LRTA*-AGENT(s′):                     # s′ = percept (current state)
    if GOAL-TEST(s′): return stop
    if s′ is a new state: H[s′] ← h(s′)
    if s (previous state) is not null:
        result[s, a] ← s′
        H[s] ← min over b in ACTIONS(s) of (cost(s,b) + H[result[s,b]] if known else h(s))
    a ← argmin over b in ACTIONS(s′) of (cost(s′,b) + H[result[s′,b]] if known else h(result[s′,b]))
    s ← s′
    return a

The Exploration vs Exploitation Trade-off

Properties

Applications

• Autonomous robot exploration (Mars rovers, warehouse robots)
• Real-time game AI navigating procedurally-generated or fog-of-war maps
• Network routing in dynamically changing topologies
• Foundational concepts for reinforcement learning agents

Interview & Exam Questions