Uniform Cost Search

        def uniform_cost_search(start):
            cost_to_get_to_node = {}
            frontier = PriorityQueue() // Higher Priority equals Lower Cost
            expanded_nodes = Set()

            cost_to_get_to_node[start] = 0
            frontier.push((start, 0))
            expanded_nodes.add(start)

            while front.has_elements():
                u = frontier.pop()

                if is_goal(u):
                    return path(u)

                for v in u.successors:
                    if v not in expanded_nodes:
                        if v in frontier:
                            # if we already have it in the frontier, but we found a cheaper way to get there, update the cost to get here.
                            cost_to_get_to_node[v] = min(cost_to_get_to_node[v], cost_to_get_to_node[u] + u.action_cost(v))
                        else:
                            frontier.push(v)
                            cost_to_get_to_node[v] = cost_to_get_to_node[u] + u.action_cost(v))

            return Failure

In general UCS is not complete, because given an infinite number of zero-weight edges deviating away from the goal state, then UCS will follow this path forever and never find the goal. On the other hand, if there exists some $ϵ > 0$ such that every edge has at least this weight, then UCS will find the minimum cost solution, this is because it explores nodes in the search space in non-decreasing order of cost so it must find a minimum cost path to a goal before finding any higher cost paths leading to a goal.

UCS Example Graph

Show the history of the frontier and what node is selected in a table for the following graph, where UCS is called without the cycle checking.

Later Expansion means Higher Cost

Suppose that node

a

is expanded after node

b

then

c (b) \leq c (a)

Strictly Less Cost Implies Earlier Expansion Time

Let

v

be a node expanded by UCS, then for any node

x \in V

such that

c (x) < c (v)

, then

x

will be expanded before

v

will be.

UCS Produces Minimal Cost Paths

Let

p

be the first path that UCS produces that leads to some node

x

, then

p

is a minimal cost path to

x

, so long as all costs are lower bounded by some

ϵ \in R^{> 0}

Note that if we don't have the lower bound assumption, then there could exist some negative edge weights meaning that there is potential for a high cost path, to then eventually become a very low cost before getting to $x$ which would mean that UCS would find some other higher cost path to $x$ before making it over the "hump" of the other path to $x$ with lower cost. This is similar to escaping a local minimum.

Suppose that $p$ is the first path that UCS produces that leads to some node $x$ , then assume for the sake of contradiction that this path is not cost optimal, therefore there exists some other path $p^{*}$ that has lower cost, but then $p^{*}$ would be a path leading to $x$ that gets explored before $p$ but $p$ was the first one, so this is a contradiction, therefore $p$ is the minimal cost path to $x$ .

UCS Runtime

Suppose that we have a directed graph with maximum branching factor

b

with edge weights such that there exists some

ϵ > 0

such that every edge weight is at least this amount. If

s, g

are two connected in the graph and let

C^{*}

be the minimal cost a path can have that starts from

s

and goes to

g

, then the runtime and space complexity of calling UCS on

s

is given by

O (b^{⌊ \frac{C^{*}}{ϵ} ⌋ + 1})

By the above lemmas we know that UCS will expand all nodes with a cost less than $C^{*}$ and potentially (in the worst case) all nodes with cost equal to $C^{*}$ . If we know that the minimal cost to get from $s$ to $g$ is $C^{*}$ , and each edge has weight at least $ϵ$ , then the maximal number of edges in this path is given by $d = ⌊ \frac{C^{*}}{ϵ} ⌋$ , to understand why this is true, suppose that $C^{*} = 9$ and $ϵ = 5$ , $⌊ \frac{C^{*}}{ϵ} ⌋ = ⌊ \frac{9}{5} ⌋ = 1$ , but clearly we're going to need at least two edges to reach our goal, because if we had just one, we would have cost $5$ , but this path couldn't reach $g$ because any path that reaches $g$ must have cost at least $9$ , this is why the equation is $⌊ \frac{C^{*}}{ϵ} ⌋ + 1$ , which our our specific case would be equal to $2$ which makes sense.

If we isolate our attention to the subtree with depth $d$ , then in the worst case every edge inside this subtree has weight $ϵ$ , and therefore every node in a higher level in the tree has a lower cost and must be explored before we explore node $g$ .

Everything at layer $d$ has the same cost of $ϵ \cdot d$ . Then bringing our attention back to the whole tree, any node that is outside of this subtree will have cost greater than $ϵ \cdot d$ , and thus none of them will be expanded by $U C S$ while trying to find $g$ .

Let's now calculate how many nodes UCS actually has to expand Since UCS explores nodes with a lower path cost first, then the entire subtree of depth $d - 1$ will be explored before $g$ , then at depth $d$ in the worst case, every other node is expanded before $g$ , therefore in total we have to explore $b^{0} + b^{1} + \dots b^{d} - 1 = \frac{b^{d + 1} - 1}{b - 1} - 1$ nodes, therefore our runtime is given by $O (b^{d}) = O (b^{\frac{C^{*}}{ϵ} + 1})$

path	frontier	about to expand
	(S, 0)	S
S	(SP, 1), (SD, 3), (SE, 9)	(SP, 1)
(SP, 1)	(SD, 3), (SE, 9), (SPQ, 16)	(SD, 3)
(SD, 3)	(SE, 9), (SPQ, 16), (SDE, 5)	(SDE, 5)
(SDE, 5)	(SE, 9), (SPQ, 16), (SDEH, 6)	(SDEH, 6)
(SDEH, 6)	(SE, 9), (SPQ, 16), (SDEHQ, 10)	(SE, 6)
(SE, 9)	(SPQ, 16), (SDEHQ, 10), (SEH, 10)	(SEH, 10)
(SEH, 10)	(SPQ, 16), (SDEHQ, 10), (SEHQ, 14)	(SDEHQ, 10)
(SDEHQ, 10)	(SPQ, 16), (SEHQ, 14), (SDEHQG, 11)	(SDEHQG, 11)
(SDEHQG, 11)	(SPQ, 16), (SEHQ, 14)

🏗️ ΘρϵηΠατπ🚧 (under construction)

Uniform Cost Search

🏗️ $Θ ρ ϵ η Π α τ π$ 🚧 (under construction)