Artificial Intelligence: Uniform Cost Search (UCS)

Uniform Cost Search (UCS) is an uninformed search algorithm used in artificial intelligence to find the optimal path from a start node to a goal node in a weighted graph or tree. It explores nodes based on the lowest cumulative path cost, ensuring the least-cost path is found if one exists. Below is a detailed explanation of UCS, its mechanics, properties, and applications.

What is Uniform Cost Search?

UCS is a graph search algorithm that generalizes Dijkstra’s algorithm for single-source shortest paths but focuses on finding a path to a specific goal node. It is considered "uninformed" because it does not use heuristic estimates of the goal’s proximity, relying solely on the actual costs of paths from the start node to the current node.

• Key Idea: Expand the node with the lowest cumulative path cost (g(n)) at each step.
• Objective: Find the path with the minimum total cost from the start node to a goal node.
• Data Structure: Uses a priority queue to store nodes, ordered by their path cost from the start node.

How UCS Works

UCS operates by maintaining a priority queue of nodes to be explored, where the priority is the cumulative cost of the path from the start node to the current node. Here’s the step-by-step process:

1. Initialization:
   • Start with the initial node in the priority queue with a path cost of 0.
   • Initialize an empty set to track explored nodes.
2. Node Selection:
   • Dequeue the node with the lowest path cost from the priority queue.
3. Goal Test:
   • If the dequeued node is the goal node, terminate and return the path and its cost.
4. Expansion:
   • If the node is not the goal, expand it by generating its child nodes (successors).
   • For each child node:
     • Calculate the cumulative path cost (cost from start to parent + edge cost to child).
     • If the child node has not been visited or a lower-cost path to it is found, update its cost and add it to the priority queue.
5. Exploration Tracking:
   • Mark the dequeued node as explored to avoid reprocessing (in graph search).
   • In tree search, this step is skipped, but cycles may lead to redundant exploration.
6. Repeat:
   • Continue until the goal is found or the priority queue is empty (indicating no path exists).

Implementing Uniform Cost Search to Solve Pathfinding Problem

Step 1: Import Required Libraries

This step imports the necessary libraries for implementing Uniform Cost Search (UCS) and visualizing the graph.

import heapq
import networkx as nx
import matplotlib.pyplot as plt​

Step 2: Define the Uniform Cost Search Function

This function implements the UCS algorithm to find the least cost path from a start node to a goal node in a weighted graph.

def uniform_cost_search(graph, start, goal):
    # Priority queue to store the frontier nodes, initialized with the start node
    priority_queue = [(0, start)]
    # Dictionary to store the cost of the shortest path to each node
    visited = {start: (0, None)}
    
    while priority_queue:
        # Pop the node with the lowest cost from the priority queue
        current_cost, current_node = heapq.heappop(priority_queue)
        
        # If we reached the goal, return the total cost and the path
        if current_node == goal:
            return current_cost, reconstruct_path(visited, start, goal)
        
        # Explore the neighbors
        for neighbor, cost in graph[current_node]:
            total_cost = current_cost + cost
            # Check if this path to the neighbor is better than any previously found
            if neighbor not in visited or total_cost < visited[neighbor][0]:
                visited[neighbor] = (total_cost, current_node)
                heapq.heappush(priority_queue, (total_cost, neighbor))
    
    # If the goal is not reachable, return None
    return None​

Step 3: Define the Path Reconstruction Function

This function reconstructs the path from the start node to the goal node by tracing back through the visited nodes.

def reconstruct_path(visited, start, goal):
    # Reconstruct the path from start to goal by following the visited nodes
    path = []
    current = goal
    while current is not None:
        path.append(current)
        current = visited[current][1]  # Get the parent node
    path.reverse()
    return path​

Step 4: Define the Visualization Function

This function visualizes the graph and the path found by UCS, using networkx for graph creation and matplotlib for visualization.

def visualize_graph(graph, path=None):
    G = nx.DiGraph()

    # Adding nodes and edges to the graph
    for node, edges in graph.items():
        for neighbor, cost in edges:
            G.add_edge(node, neighbor, weight=cost)

    pos = nx.spring_layout(G)  # Positioning the nodes

    # Drawing the graph
    plt.figure(figsize=(8, 6))
    nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000, font_size=15, font_weight='bold', edge_color='gray')
    labels = nx.get_edge_attributes(G, 'weight')
    nx.draw_networkx_edge_labels(G, pos, edge_labels=labels, font_size=12)

    if path:
        # Highlight the path in red
        path_edges = list(zip(path, path[1:]))
        nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='red', width=2.5)

    plt.title("Uniform Cost Search Path Visualization")
    plt.show()​

Step 5: Define the Graph and Execute UCS

This step defines a sample graph as an adjacency list, sets the start and goal nodes, and runs the UCS algorithm. It then visualizes the graph and the path found.

# Example graph represented as an adjacency list
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('D', 1), ('E', 3)],
    'C': [('F', 5)],
    'D': [('G', 2)],
    'E': [('G', 1)],
    'F': [('G', 2)],
    'G': []
}

# Example usage of the UCS function
start_node = 'A'
goal_node = 'G'
result = uniform_cost_search(graph, start_node, goal_node)

if result:
    total_cost, path = result
    print(f"Least cost path from {start_node} to {goal_node}: {' -> '.join(path)} with total cost {total_cost}")
    visualize_graph(graph, path)
else:
    print(f"No path found from {start_node} to {goal_node}")​

Complete Code

import heapq
import networkx as nx
import matplotlib.pyplot as plt

def uniform_cost_search(graph, start, goal):
    # Priority queue to store the frontier nodes, initialized with the start node
    priority_queue = [(0, start)]
    # Dictionary to store the cost of the shortest path to each node
    visited = {start: (0, None)}
    
    while priority_queue:
        # Pop the node with the lowest cost from the priority queue
        current_cost, current_node = heapq.heappop(priority_queue)
        
        # If we reached the goal, return the total cost and the path
        if current_node == goal:
            return current_cost, reconstruct_path(visited, start, goal)
        
        # Explore the neighbors
        for neighbor, cost in graph[current_node]:
            total_cost = current_cost + cost
            # Check if this path to the neighbor is better than any previously found
            if neighbor not in visited or total_cost < visited[neighbor][0]:
                visited[neighbor] = (total_cost, current_node)
                heapq.heappush(priority_queue, (total_cost, neighbor))
    
    # If the goal is not reachable, return None
    return None

def reconstruct_path(visited, start, goal):
    # Reconstruct the path from start to goal by following the visited nodes
    path = []
    current = goal
    while current is not None:
        path.append(current)
        current = visited[current][1]  # Get the parent node
    path.reverse()
    return path

def visualize_graph(graph, path=None):
    G = nx.DiGraph()

    # Adding nodes and edges to the graph
    for node, edges in graph.items():
        for neighbor, cost in edges:
            G.add_edge(node, neighbor, weight=cost)

    pos = nx.spring_layout(G)  # Positioning the nodes

    # Drawing the graph
    plt.figure(figsize=(8, 6))
    nx.draw(G, pos, with_labels=True, node_color='lightblue', node_size=2000, font_size=15, font_weight='bold', edge_color='gray')
    labels = nx.get_edge_attributes(G, 'weight')
    nx.draw_networkx_edge_labels(G, pos, edge_labels=labels, font_size=12)

    if path:
        # Highlight the path in red
        path_edges = list(zip(path, path[1:]))
        nx.draw_networkx_edges(G, pos, edgelist=path_edges, edge_color='red', width=2.5)

    plt.title("Uniform Cost Search Path Visualization")
    plt.show()

# Example graph represented as an adjacency list
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('D', 1), ('E', 3)],
    'C': [('F', 5)],
    'D': [('G', 2)],
    'E': [('G', 1)],
    'F': [('G', 2)],
    'G': []
}

# Example usage of the UCS function
start_node = 'A'
goal_node = 'G'
result = uniform_cost_search(graph, start_node, goal_node)

if result:
    total_cost, path = result
    print(f"Least cost path from {start_node} to {goal_node}: {' -> '.join(path)} with total cost {total_cost}")
    visualize_graph(graph, path)
else:
    print(f"No path found from {start_node} to {goal_node}")​

Output:

Least cost path from A to G: A -> B -> D -> G with total cost 4

Applications of UCS in AI

Uniform Cost Search is widely applicable in various fields within AI:

Advantages of Uniform Cost Search

Challenges with UCS