Uninformed Search - Uninformed Cost Search (UCS)

UCS finds the path to the goal node with the lowest accumulated cost. It expands nodes based on the lowest cost from the start node rather than depth or breadth. It uses a priority queue that adds nodes into the queue. The node with the highest priority is removed first. If the node is the goal node, the algorithm terminates. Else, enqueue all the children of the current node to the queue, with their cumulative cost from the root as priority and the current node to the visited list. Uniform cost search is equivalent to BFS algorithm if the path cost of all edges is the same.

• Completeness: Yes, when the branching factor is finite
• Optimality: Yes

Pseudocode

UniformCostSearch(Graph, start, goal):
    1. Create a priority queue named fringe list and add (start, cost=0)
    2. Create an empty set named expanded to store visited nodes
    3. While PQ is not empty:
        a. Dequeue the node with the lowest cost (current, cost)
        b. If current is the goal, return the path and cost
        c. If current is not visited:
            i. Add current to visited set
            ii. For each neighbor (next) of current:
                - If next is not visited:
                    - Calculate new cost = cost + edge cost
                    - Add (next, new cost) to PQ
    4. If goal is not found, return failure

Example

In this example:

• The starting node (initial state) is S.
• The goal node (goal state) is G.

The fringe list is a priority queue with the least cost element as the highest priority.

graph TB;
A((S)) -->|3| B((A))
A -->|1| C((B))
A -->|8| D((C))
B -->|3| E((D))
B -->|7| F((E))
B -->|15| G((G))
C -->|20| G((G))
D -->|5| G((G))

Iteration 1

The starting node is S, add it to the fringe list.

graph TB;
A((S)) -->|3| B((A))
A -->|1| C((B))
A -->|8| D((C))
B -->|3| E((D))
B -->|7| F((E))
B -->|15| G((G))
C -->|20| G((G))
D -->|5| G((G))

style A fill:#ff9559,stroke:#ee381f,stroke-width:3px;

• Fringe list: [(S,0)]
• Expanded list: []

Iteration 2

Check the first element in the fringe list (The one with the highest priority, which is, the least cost node) - S. S is not a goal node, generate all of its children to the fringe list. Add S to the expanded list.

graph TB;
A((S)) -->|3| B((A))
A -->|1| C((B))
A -->|8| D((C))
B -->|3| E((D))
B -->|7| F((E))
B -->|15| G((G))
C -->|20| G((G))
D -->|5| G((G))

style A fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style B fill:#ebd834,stroke:#ebd834,stroke-width:3px;
style C fill:#ebd834,stroke:#ebd834,stroke-width:3px;
style D fill:#ebd834,stroke:#ebd834,stroke-width:3px;

linkStyle 0 stroke:#ee381f,stroke-width:3px;
linkStyle 1 stroke:#ee381f,stroke-width:3px;
linkStyle 2 stroke:#ee381f,stroke-width:3px;

• Fringe list: [(B,1), (A,3), (C,8)]
• Expanded list: `[(S,0)]

Iteration 3

Check the first element in the fringe list - B. B is the least cost node in the fringe list, remove B from the list, add it to the expanded list. Since B is not the goal node, generate the children of B and add them with their cumulated costs to the fringe list.

graph TB;
A((S)) -->|3| B((A))
A -->|1| C((B))
A -->|8| D((C))
B -->|3| E((D))
B -->|7| F((E))
B -->|15| G((G))
C -->|20| G((G))
D -->|5| G((G))

style A fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style B fill:#ebd834,stroke:#ebd834,stroke-width:3px;
style C fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style D fill:#ebd834,stroke:#ebd834,stroke-width:3px;
style G fill:#ebd834,stroke:#ebd834,stroke-width:3px;

linkStyle 0 stroke:#ee381f,stroke-width:3px;
linkStyle 1 stroke:#ee381f,stroke-width:3px;
linkStyle 2 stroke:#ee381f,stroke-width:3px;
linkStyle 6 stroke:#ee381f,stroke-width:3px;

• Fringe list: [(A,3), (C,8), (G,21)]
• Expanded list: [(S,0), (B,1)]

Iteration 4

A is the least cost node in the fringe list, remove A from the list, add it to the expanded list. Since A is not the goal node, generate the children of A and add them with their cumulated costs to the fringe list.

graph TB;
A((S)) -->|3| B((A))
A -->|1| C((B))
A -->|8| D((C))
B -->|3| E((D))
B -->|7| F((E))
B -->|15| G((G))
C -->|20| G((G))
D -->|5| G((G))

style A fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style B fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style C fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style D fill:#ebd834,stroke:#ebd834,stroke-width:3px;
style G fill:#ebd834,stroke:#ebd834,stroke-width:3px;
style E fill:#ebd834,stroke:#ebd834,stroke-width:3px;
style F fill:#ebd834,stroke:#ebd834,stroke-width:3px;


linkStyle 0 stroke:#ee381f,stroke-width:3px;
linkStyle 1 stroke:#ee381f,stroke-width:3px;
linkStyle 2 stroke:#ee381f,stroke-width:3px;
linkStyle 3 stroke:#ee381f,stroke-width:3px;
linkStyle 4 stroke:#ee381f,stroke-width:3px;
linkStyle 5 stroke:#ee381f,stroke-width:3px;
linkStyle 6 stroke:#ee381f,stroke-width:3px;

• Fringe list: [(D,6), (C,8), (E,10), (G,18), (G,21)]
• Expanded list: [(S,0), (B,1), (A,3)]

Iteration 5

D is the least cost node in the fringe list, remove D from the list, add it to the expanded list. Since D is not the goal node, generate the children of D. D does not have any child, do nothing.

graph TB;
A((S)) -->|3| B((A))
A -->|1| C((B))
A -->|8| D((C))
B -->|3| E((D))
B -->|7| F((E))
B -->|15| G((G))
C -->|20| G((G))
D -->|5| G((G))

style A fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style B fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style C fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style D fill:#ebd834,stroke:#ebd834,stroke-width:3px;
style G fill:#ebd834,stroke:#ebd834,stroke-width:3px;
style E fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style F fill:#ebd834,stroke:#ebd834,stroke-width:3px;


linkStyle 0 stroke:#ee381f,stroke-width:3px;
linkStyle 1 stroke:#ee381f,stroke-width:3px;
linkStyle 2 stroke:#ee381f,stroke-width:3px;
linkStyle 3 stroke:#ee381f,stroke-width:3px;
linkStyle 4 stroke:#ee381f,stroke-width:3px;
linkStyle 5 stroke:#ee381f,stroke-width:3px;
linkStyle 6 stroke:#ee381f,stroke-width:3px;

• Fringe list: [(C,8), (E,10), (G,18), (G,21)]
• Expanded list: [(S,0), (B,1), (A,3), (D,6)]

Iteration 6

C is the least cost node in the fringe list, remove C from the list, add it to the expanded list. Since C is not the goal node, generate the children of C and add them with their cumulated costs to the fringe list.

graph TB;
A((S)) -->|3| B((A))
A -->|1| C((B))
A -->|8| D((C))
B -->|3| E((D))
B -->|7| F((E))
B -->|15| G((G))
C -->|20| G((G))
D -->|5| G((G))

style A fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style B fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style C fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style D fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style G fill:#ebd834,stroke:#ebd834,stroke-width:3px;
style E fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style F fill:#ebd834,stroke:#ebd834,stroke-width:3px;


linkStyle 0 stroke:#ee381f,stroke-width:3px;
linkStyle 1 stroke:#ee381f,stroke-width:3px;
linkStyle 2 stroke:#ee381f,stroke-width:3px;
linkStyle 3 stroke:#ee381f,stroke-width:3px;
linkStyle 4 stroke:#ee381f,stroke-width:3px;
linkStyle 5 stroke:#ee381f,stroke-width:3px;
linkStyle 6 stroke:#ee381f,stroke-width:3px;
linkStyle 7 stroke:#ee381f,stroke-width:3px;

• Fringe list: [(E,10), (G,13), (G,18), (G,21)]
• Expanded list: [(S,0), (B,1), (A,3), (D,6), (C,8)]

Iteration 7

E is the least cost node in the fringe list, remove E from the list, add it to the expanded list. Since E is not the goal node, generate the children of E. E does not have any child, do nothing.

graph TB;
A((S)) -->|3| B((A))
A -->|1| C((B))
A -->|8| D((C))
B -->|3| E((D))
B -->|7| F((E))
B -->|15| G((G))
C -->|20| G((G))
D -->|5| G((G))

style A fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style B fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style C fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style D fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style G fill:#ebd834,stroke:#ebd834,stroke-width:3px;
style E fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style F fill:#ff9559,stroke:#ee381f,stroke-width:3px;


linkStyle 0 stroke:#ee381f,stroke-width:3px;
linkStyle 1 stroke:#ee381f,stroke-width:3px;
linkStyle 2 stroke:#ee381f,stroke-width:3px;
linkStyle 3 stroke:#ee381f,stroke-width:3px;
linkStyle 4 stroke:#ee381f,stroke-width:3px;
linkStyle 5 stroke:#ee381f,stroke-width:3px;
linkStyle 6 stroke:#ee381f,stroke-width:3px;
linkStyle 7 stroke:#ee381f,stroke-width:3px;

• Fringe list: [(G,13), (G,18), (G,21)]
• Expanded list: [(S,0), (B,1), (A,3), (D,6), (C,8), (E,10)]

Iteration 8

G is the least cost node in the fringe list, remove G from the list, add it to the expanded list. Since G is the goal node, return the path using path reconstruction function and return the cumulated cost.

graph TB;
A((S)) -->|3| B((A))
A -->|1| C((B))
A -->|8| D((C))
B -->|3| E((D))
B -->|7| F((E))
B -->|15| G((G))
C -->|20| G((G))
D -->|5| G((G))

style A fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style B fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style C fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style D fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style G fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style E fill:#ff9559,stroke:#ee381f,stroke-width:3px;
style F fill:#ff9559,stroke:#ee381f,stroke-width:3px;


linkStyle 0 stroke:#ee381f,stroke-width:3px;
linkStyle 1 stroke:#ee381f,stroke-width:3px;
linkStyle 2 stroke:#ee381f,stroke-width:3px;
linkStyle 3 stroke:#ee381f,stroke-width:3px;
linkStyle 4 stroke:#ee381f,stroke-width:3px;
linkStyle 5 stroke:#ee381f,stroke-width:3px;
linkStyle 6 stroke:#ee381f,stroke-width:3px;
linkStyle 7 stroke:#ee381f,stroke-width:3px;

• Fringe list: [(G,18), (G,21)]
• Expanded list: [(S,0), (B,1), (A,3), (D,6), (C,8), (E,10), (G,13)]

Program output

Path: S -> C -> G
Cost: 13

Time complexity

The time complexity of UCS is difficult to characterise in terms of branching factor (b) and depth (d), because UCS does not expand nodes purely based on depth, it expands nodes in order of cumulative cost. This introduces variability in the number of nodes expanded.

Measure complexity with $C^{\ast }$ and $ϵ$

Definition

• $C^{\ast }$: The total cost of the optimal path from the start node to the goal
• $ϵ$: The smallest possible edge cost in the graph

Complexity analysis

• Since UCS expands nodes based on cumulative path cost, it will explore all nodes with cost $<C^{\ast }$ before reaching the goal (explores nodes in increasing order of path cost).
• The lowest possible increase in path cost when moving to a new node is $ϵ$ (the smallest edge cost in the graph). This means that no two paths will have a cost difference smaller than $ϵ$.

Thus, the set of possible path costs can be thought of as discrete cost levels: $0,ϵ,2ϵ,3ϵ,\dots ,kϵ$ Where $k$ is some integer.

The maximum number of such nodes (cost $<C^{\ast }$) is approximately: $\frac{C^{\ast }}{ϵ}$ Because the smallest possible cost increment is $ϵ$ .

This means UCS may explore up to $1+\frac{C^{\ast }}{ϵ}$ cost levels (include the goal itself) to find the optimal goal. In each level, UCS can expand up to $b$ new nodes. Thus, the total number of nodes expanded is approximately: $O(b^{1+\frac{C^{\ast }}{ϵ}})$ Typically, $O(b^{1+\frac{C^{\ast }}{ϵ}})$ is greater than $O(b^d)$.

Space complexity

The space complexity of UCS can be measured as: $O(b^{1+\frac{C^{\ast }}{ϵ}})$

---

Back to parent page: Problem Solving and Search

AI AI_Algorithm Problem_Solving Uninformed_Search UCS