Mastering Search Algorithms for AI Pathfinding: A Romania Map Tutorial (CS6601 Style)

Introduction to AI Search Algorithms in Pathfinding

Search is a cornerstone of artificial intelligence, enabling problem-solving in domains where the solution isn't immediately obvious. From GPS navigation to game AI, search algorithms find optimal paths through state spaces. In this tutorial, we'll explore how to implement several classic search algorithms—BFS, DFS, A*, and more—using an undirected graph representing Romania's cities. This mirrors the CS6601 assignment 1 (Spring 2025) and will help you understand the trade-offs between time and space cost.

Think of this like the pathfinding in popular battle royale games like Fortnite or PUBG: your character must navigate a shrinking safe zone while avoiding obstacles. The algorithms you'll learn are the same ones that power NPC movement and route optimization in those games.

Setting Up Your Environment

Before diving into code, let's set up a Python environment. We'll use Conda to manage dependencies, similar to the assignment instructions.

conda create --name a1_env python=3.9 -y
conda activate a1_env
pip install -r requirements.txt

Your requirements.txt should include libraries like networkx, matplotlib, and numpy for graph visualization and data handling. If you're using Jupyter Notebook, launch it with:

jupyter notebook

Then open notebook.ipynb. Remember to run all cells in order; Jupyter's statefulness can cause errors if you skip around.

The Romania Graph: A Classic AI Benchmark

The Romania map is a standard testbed for search algorithms in AI courses. It consists of cities (nodes) connected by roads (edges) with distances (costs). For example, Arad is connected to Zerind, Sibiu, and Timisoara. We'll represent this as an adjacency list or using networkx.

import networkx as nx
romania_graph = nx.Graph()
romania_graph.add_edge('Arad', 'Zerind', weight=75)
romania_graph.add_edge('Arad', 'Sibiu', weight=140)
# ... add all edges

This graph is undirected, meaning travel is possible both ways. In real-world applications, graphs can be directed (one-way streets) or weighted (time, distance, or cost).

Implementing Breadth-First Search (BFS)

BFS explores the graph level by level, guaranteeing the shortest path in terms of number of edges. It uses a queue (FIFO). Let's implement it for our Romania graph to find a route from Arad to Bucharest.

from collections import deque

def bfs(graph, start, goal):
    frontier = deque([start])
    came_from = {start: None}
    while frontier:
        current = frontier.popleft()
        if current == goal:
            break
        for neighbor in graph.neighbors(current):
            if neighbor not in came_from:
                came_from[neighbor] = current
                frontier.append(neighbor)
    return reconstruct_path(came_from, start, goal)

def reconstruct_path(came_from, start, goal):
    path = []
    current = goal
    while current != start:
        path.append(current)
        current = came_from[current]
    path.append(start)
    return path[::-1]

BFS is ideal when all step costs are equal. In gaming, BFS can be used for simple enemy AI that moves toward the player without obstacles.

Depth-First Search (DFS) and Its Pitfalls

DFS uses a stack (LIFO) and explores as deep as possible before backtracking. It doesn't guarantee the shortest path but uses less memory. Implementation is similar to BFS but with pop() instead of popleft().

def dfs(graph, start, goal):
    frontier = [start]
    came_from = {start: None}
    while frontier:
        current = frontier.pop()
        if current == goal:
            break
        for neighbor in graph.neighbors(current):
            if neighbor not in came_from:
                came_from[neighbor] = current
                frontier.append(neighbor)
    return reconstruct_path(came_from, start, goal)

DFS can get stuck in infinite loops if the graph has cycles, so we track visited nodes. In real-time strategy games like StarCraft, DFS might be used for exploration when memory is limited.

Informed Search: Greedy Best-First Search

Greedy best-first search uses a heuristic to estimate the cost to the goal. For Romania, we can use straight-line distance (Euclidean) as the heuristic. It expands the node that appears closest to the goal.

import heapq

def greedy_best_first(graph, start, goal, heuristic):
    frontier = [(heuristic[start], start)]
    came_from = {start: None}
    while frontier:
        _, current = heapq.heappop(frontier)
        if current == goal:
            break
        for neighbor in graph.neighbors(current):
            if neighbor not in came_from:
                came_from[neighbor] = current
                heapq.heappush(frontier, (heuristic[neighbor], neighbor))
    return reconstruct_path(came_from, start, goal)

Heuristics are like using a crow-flies distance in a GPS app—they guide the search but can be misleading if obstacles exist. In AI chatbots like ChatGPT, heuristic search helps prioritize relevant responses.

A* Search: Combining Cost and Heuristic

A* is the gold standard for pathfinding. It uses both the actual cost from the start (g) and the heuristic estimate (h), summing them to evaluate nodes. This ensures optimality if the heuristic is admissible (never overestimates).

def a_star(graph, start, goal, heuristic):
    frontier = [(0, start)]
    came_from = {start: None}
    cost_so_far = {start: 0}
    while frontier:
        _, current = heapq.heappop(frontier)
        if current == goal:
            break
        for neighbor in graph.neighbors(current):
            new_cost = cost_so_far[current] + graph[current][neighbor]['weight']
            if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
                cost_so_far[neighbor] = new_cost
                priority = new_cost + heuristic[neighbor]
                heapq.heappush(frontier, (priority, neighbor))
                came_from[neighbor] = current
    return reconstruct_path(came_from, start, goal)

A* powers navigation in apps like Google Maps and in game AI for titles like The Legend of Zelda: Breath of the Wild. It's also used in robotics for autonomous navigation.

Comparing Algorithm Performance

Let's test these algorithms on the Romania graph to find a path from Arad to Bucharest. We'll measure nodes expanded and path cost.

# Example heuristic (straight-line distances to Bucharest)
heuristic = {
    'Arad': 366, 'Bucharest': 0, 'Craiova': 160, 'Dobreta': 242,
    'Eforie': 161, 'Fagaras': 176, 'Giurgiu': 77, 'Hirsova': 151,
    'Iasi': 226, 'Lugoj': 244, 'Mehadia': 241, 'Neamt': 234,
    'Oradea': 380, 'Pitesti': 100, 'Rimnicu Vilcea': 193, 'Sibiu': 253,
    'Timisoara': 329, 'Urziceni': 80, 'Vaslui': 199, 'Zerind': 374
}

print("BFS path:", bfs(romania_graph, 'Arad', 'Bucharest'))
print("DFS path:", dfs(romania_graph, 'Arad', 'Bucharest'))
print("Greedy path:", greedy_best_first(romania_graph, 'Arad', 'Bucharest', heuristic))
print("A* path:", a_star(romania_graph, 'Arad', 'Bucharest', heuristic))

You'll notice BFS finds a path with fewer nodes expanded than DFS, but A* often finds the shortest path with the least cost. In practice, A* is preferred for weighted graphs.

Visualizing the Search Process

Visualization helps understand how each algorithm explores the graph. Using matplotlib and networkx, we can animate the frontier.

import matplotlib.pyplot as plt

def visualize_search(graph, algorithm, start, goal):
    pos = nx.spring_layout(graph)
    plt.figure(figsize=(10, 8))
    # Run algorithm and capture visited nodes
    visited = []
    frontier = [start]
    came_from = {start: None}
    while frontier:
        # ... (algorithm-specific logic)
        visited.append(current)
        # draw graph with colors
        nx.draw(graph, pos, with_labels=True, node_color='lightgray')
        nx.draw_networkx_nodes(graph, pos, nodelist=visited, node_color='blue')
        nx.draw_networkx_nodes(graph, pos, nodelist=frontier, node_color='red')
        plt.show()

This is similar to how AI training visualizations show the agent exploring its environment, like in reinforcement learning demos for autonomous driving.

Extending to the Atlanta Graph (Race Mode)

In the CS6601 assignment, there's an optional Atlanta graph for a race. This graph is larger and more realistic, representing a city's road network. The same algorithms apply, but performance matters more. You might implement bidirectional search or IDA* to handle larger state spaces.

Bidirectional search runs two simultaneous searches—one from the start, one from the goal—and meets in the middle. This can drastically reduce the search space.

def bidirectional_bfs(graph, start, goal):
    frontier_start = deque([start])
    frontier_goal = deque([goal])
    came_from_start = {start: None}
    came_from_goal = {goal: None}
    while frontier_start and frontier_goal:
        # Expand one step from start
        current = frontier_start.popleft()
        for neighbor in graph.neighbors(current):
            if neighbor not in came_from_start:
                came_from_start[neighbor] = current
                frontier_start.append(neighbor)
                if neighbor in came_from_goal:
                    return merge_paths(came_from_start, came_from_goal, neighbor)
        # Expand one step from goal
        current = frontier_goal.popleft()
        for neighbor in graph.neighbors(current):
            if neighbor not in came_from_goal:
                came_from_goal[neighbor] = current
                frontier_goal.append(neighbor)
                if neighbor in came_from_start:
                    return merge_paths(came_from_start, came_from_goal, neighbor)
    return None

This technique is used in Google Maps to provide fast route calculations.

Common Pitfalls and Jupyter Tips

When working in Jupyter Notebook, remember to re-run all cells after opening a notebook. Variable state can persist unexpectedly. Use Run All from the Cell menu to avoid errors.

Also, ensure your heuristic is admissible for A* to guarantee optimality. A common mistake is using a heuristic that overestimates, which can lead to suboptimal paths.

Conclusion

Implementing search algorithms on the Romania graph is a classic AI exercise that builds intuition for pathfinding. Whether you're building a game AI, a GPS app, or a chatbot that plans responses, these algorithms are fundamental. Practice with different heuristics and graph sizes to see how performance changes. For the CS6601 assignment, focus on passing the custom tests like search_basic_tests.py and search_romania_tests.py. Good luck!