Uniform Cost Search (UCS) in AI

Uniform Cost Search (UCS) is an uninformed search algorithm that searches for the path with the minimum cost between the starting and ending nodes in a weighted graph, where all edges have costs greater than or equal to zero. The UCS algorithm expands nodes according to the least path cost until now. It employs a priority queue rather than a regular queue.

In the case of UCS, path cost, not number of steps, is the criterion. A path that contains five cheap edges could be preferable to another path containing only two expensive edges.

What Is Uniform Cost Search?

Uniform Cost Search falls under the domain of uninformed search algorithms in artificial intelligence searching techniques, including BFS and DFS. Uninformed search algorithms explore a graph based on the information provided in the problem alone without estimating the distance to the goal.

Informed search algorithms like A* Search depends on the heuristic function to estimate the remaining cost. Uniform Cost Search does not make use of any heuristic. It uses the cost accumulated from the start node up to the current node.

The Core Idea: Priority Queue and Path Cost

BFS algorithm uses a FIFO Queue and assumes that all the edges have the same cost. But that will be a wrong assumption for a weighted graph as edges have varied costs.

UCS algorithm uses a priority queue instead of FIFO queue. The priority queue is based on the cumulative cost of the path from the start node to the current node.

Two sets are used in UCS to record the algorithm’s steps:

• Frontier: Set of discovered nodes, but not expanded; stored in the priority queue.
• Explored set: Set of expanded nodes.

A node having the minimum cumulative cost is always kept at the front of the priority queue.

How Uniform Cost Search Works, Step by Step

1. Insert the start node in the priority queue with a path cost of zero.
2. Remove the node that has the least cumulative cost from the priority queue.
3. If the node removed is the goal, then halt the search procedure and return the cost and path.
4. If the node removed is in the explored set, discard the node and go to step 2.
5. Otherwise, add the node to the explored set.
6. For each neighboring node, compute the cumulative cost from the start node via the present node.
7. Insert all neighbors into the priority queue with their computed costs.
8. Repeat the above steps 2 to 7 till the goal node is deleted from the priority queue or the priority queue becomes empty.

The search process halts in either of the following ways: It returns the path with least cost to the goal or it returns no solution if the priority queue becomes empty first.

A Full Worked Example

Consider a weighted graph with a start node S and a goal node G:

Edge	Cost
S → A	2
S → B	5
A → C	3
A → D	7
B → C	1
C → G	4
D → G	1

UCS traces the following sequence:

Step	Node Expanded	Cumulative Cost	Frontier After This Step
1	S	0	A (2), B (5)
2	A	2	B (5), C (5), D (9)
3	B	5	C (5), D (9)
4	C	5	D (9), G (9)
5	D	9	G (9)
6	G	9	Goal reached

UCS expands B before C at step 3 since both nodes have an accumulated cost of 5 and B has been inserted first into the priority queue. When there is a tie on cost among paths, UCS chooses the path based on their insertion time order.

Expanding B at step 4 creates a path from S to C with cost 6 (5 + 1). Since this cost is higher than the cost of 5 recorded for C, UCS will ignore this path and retain the other path to C that costs less.

The optimal path from S to G is S → A → C → G, which has a total cost of 9. The optimal path is never chosen by UCS based on the number of edges; UCS chooses the path based on the accumulated cost rather than the number of edges.

Uniform Cost Search vs. Dijkstra’s Algorithm

Both UCS and Dijkstra’s Algorithm operate through the same basic principle – expansion of the node with minimum cumulative cost from a priority queue. The algorithm was described by Edsger W. Dijkstra in 1959 (“A note on two problems in connection with graphs”).

There are two main distinctions between these approaches:

• Scope: While Dijkstra’s algorithm in its pure form solves the problem of shortest path from one source node to all other nodes in the graph, UCS halts once the goal node is dequeued.
• Origin: Dijkstra’s algorithm originates from graph theory and network routing, while UCS is the same approach used within the domain of artificial intelligence for search.

UCS is Dijkstra’s algorithm applied to a search problem between start and goal nodes.

UCS vs. BFS, DFS, and A*

Feature	UCS	BFS	DFS	A*
Search type	Uninformed	Uninformed	Uninformed	Informed
Works on weighted graphs	Yes	No (assumes equal cost)	No	Yes
Guarantees the lowest-cost path	Yes	Only if all costs are equal	No	Yes, with an admissible heuristic
Data structure	Priority queue	FIFO queue	Stack (LIFO)	Priority queue
Memory usage	High	High	Low	Moderate to high
Uses a heuristic	No	No	No	Yes

The A* algorithm implements a heuristic function in the cost-based approach implemented in UCS. The heuristic function calculates the estimated distance left to reach the goal, thus enabling A* to prune paths that are still being explored by UCS. Without the heuristic function, UCS becomes the best option.

Time and Space Complexity of UCS

The time complexity and space complexity of UCS are O(b^(1 + ⌊C*/ε⌋)), where:

• b denotes the branching factor, which is the average number of successors for each node.
• C* is the cost of the optimal solution.
• ε represents the minimum edge cost in the graph.

Consider an example to understand the magnitude of the above mentioned complexity. If there are 10 successors per node, the optimal solution cost is 20, and the minimum edge cost is 1, then the exponent would be equal to 1 + 20 = 21. The algorithm can check up to 10²¹ nodes in the worst-case scenario. This number is greater than the maximum storage available in any existing computer system.

What Happens With Negative or Zero-Cost Edges?

The optimality of UCS is guaranteed provided all edge costs are zero or positive. The algorithm makes an assumption that once the node is expanded and added to the explored nodes list, there will never be a less expensive path to this node. If there is an edge with a negative cost, this assumption is violated because there may be a path found after expanding the node that will have a smaller cost than the cost calculated using UCS.

Zero’s costs do not violate the optimality property but can slow down the termination. If the graph contains an infinite number of edges with zero cost, the accumulated cost will not grow, and thus, the algorithm will never reach a terminal state.

If the graph has negative costs on edges, then the Bellman-Ford algorithm should be used instead of UCS.

Advantages and Disadvantages of UCS

Advantages of UCS

• Optimality: UCS finds the least-cost path in cases where all edge weights are non-negative.
• Completeness: UCS always finds a solution if there is one in the search problem, provided that the branching factor is finite and there is a positive minimum edge weight.
• No heuristics needed: UCS operates without having any idea about how far the goal is from the current state.
• Suitable for weighted graphs: Unlike BFS, UCS works in cases where the actions have different costs.

Disadvantages of UCS

• Consumption of memory: UCS keeps each node generated in the priority queue; therefore, it uses more memory in case of larger graphs.
• No direction towards goal: UCS has no knowledge of the goal’s location; hence it expands nodes in those directions which may not lead towards the goal.
• Slow performance than A*: In cases where a valid heuristic is available, A* provides the optimal solution by expanding a lesser number of nodes than UCS.
• Node update problem: The cost assigned to each node may update multiple times until the node gets completed.

Real-World Applications of UCS

UCS can be applied to any cost-based path finding problem in different application areas. Four cases explain the diversity:

• Routing in networking protocols: The OSPF protocol in IP networks uses Dijkstra’s algorithm to find the shortest paths, the same way UCS algorithm works to solve search problems.
• Routing and mapping applications: In route planning applications, it finds the path having minimum cost, which could be the distance, tolls, and estimated time of arrival from one place to another.
• Robotics path planning: Here, a mobile robot will determine its path considering minimum cost, which is energy cost for turning and going straight.
• Puzzle solving: UCS is applied when we have different moves with different costs, in sliding tiles puzzles and other state space problems.

Python Implementation of Uniform Cost Search

The following implementation traces the S-to-G example above and returns the same result: cost 9, path S → A → C → G.

python
import heapq

def uniform_cost_search(graph, start, goal):
    # Each frontier entry: (cumulative_cost, node, path_so_far)
    frontier = [(0, start, [start])]
    explored = set()

    while frontier:
        cost, node, path = heapq.heappop(frontier)

        if node == goal:
            return cost, path

        if node in explored:
            continue

        explored.add(node)

        for neighbor, edge_cost in graph.get(node, []):
            if neighbor not in explored:
                total_cost = cost + edge_cost
                heapq.heappush(frontier, (total_cost, neighbor, path + [neighbor]))

    return None  # No path exists


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

result = uniform_cost_search(graph, 'S', 'G')
if result:
    total_cost, path = result
    print(f"Lowest-cost path: {' -> '.join(path)} | Total cost: {total_cost}")

Output: Lowest-cost path: S -> A -> C -> G | Total cost: 9

This implementation checks the explored set before expanding a node (line 12), which prevents the redundant re-expansion described in the Common Mistakes section below.

Common Mistakes and Exam/Interview Traps

• Confusion of UCS with Dijkstra’s algorithm as two different approaches. It is the same approach; just they differ by scope and domain of use.
• Checking the goal test at the insertion of the node instead of at the expansion step. A node that has been added to the priority queue does not contain the minimum cost yet. The optimality of UCS is verified only after the node has been popped out of the queue, but not after the insertion of it.
• Not using the explored list. Without using this list, UCS could expand the node more than once, even though there were loops on the graph, which does not change anything in the end result.
• The assumption about UCS being able to deal with negative edges. UCS fails with the negative edges because, as described earlier.
• Not specifying tie-breaking policy. In case when two paths come to one node with equal cost, it will depend on how the UCS will process the node first.

When Should You Use Uniform Cost Search?

Apply UCS only if:

• The graph contains edges with varying weights.
• There is no heuristic function for estimating the remaining cost from the current node to the goal node.
• Optimal solutions are needed.
• Sufficient memory is available for keeping the entire frontier.
• Avoid UCS when:
• A good heuristic function is available because A* gives an optimal solution in lesser number of nodes.

All edges have the same weights because BFS gives the same optimal solution with less memory requirement.

Frequently Asked Questions