A* and uniform-cost search are apparently incomplete

Question

Consider the following diagram of a graph representing a search space.

If we start at $B$ and try to reach goal state $E$, the lowest-cost first search (LCFS) (aka uniform-cost search) algorithm fails to find a solution. This is because, $B$ selects $A$ over $C$ to expand as $f(A)=g(A)=36 < f(C)=g(C)=70$. $f(n)$ is the cost function of node $n$, and $g(n)$ is the cost of reaching node $n$ from the start state. Continuing further, from $A$, LCFS will now select $B$ to expand, which in turn will select $A$ again over $C$. This leads to an infinite loop. This shows LCFS is incomplete (not guaranteed to find a solution, if one exists).

For A*, we define $f(n)=g(n)+h(n)$, where $h(n)$ is the expected cost of reaching goal state from node $n$. If we define Manhattan distance ($L_0$ norm) for $h(\cdot)$, books (such as Artificial Intelligence: A Modern Approach (3rd Ed) by Stuart Russell and Peter Norvig) says A* is bound to find the solution (since it exists). However, I couldn't find how. Using, A*, $B$ will still select $A$ since $f(A)=36+(h(A)=40)=76 < f(C)=70+(h(C)=30+50)=150$. You see, this means, when $A$ expands back $B$, $B$ will again select $A$, and an infinite loop ensues.

What am I missing here?

Answer 1

You forgot to calculate and take into account the costs of the actual paths. You forgot to accumulate the cost of the edges for going forward and backward multiple times!

The evaluation function of uniform-cost search (UCS) is $f(n) = g(n)$, where $g(n)$ represents the cost of the path from the start node to $n$. The evaluation function of A* is $f(n) = g(n) + h(n)$, where $h(n)$ is an admissible heuristic. UCS is a special case of A*, with the admissible heuristic $h(n) = 0, \forall n$. The evaluation function is used to choose the next node to visit from the fringe, which is the set of nodes that can potentially be visited. Whenever we visit a node, we remove it from the fringe. To expand a node $X$ means to add the children of $X$ to the fringe. Whenever you visit a node, you will also expand it.

Let's apply UCS to your specific example. Initially, we check whether $B$ is a goal node or not. It is not, so we expand $B$. We can add $B$ to a list of visited (or expanded) nodes (graph search) or not (tree search). Let's use the tree search, so we will not be keeping track of the expanded nodes, which means that we could expand a node more than once. $B$ has two children, $A$ and $C$, so we add them to the fringe, $\mathbb{F} = \{A, C\}$. Should we now visit $A$ or $C$? We will visit the one with the smallest value of the evaluation function, which is $A$, given that $f(A)=g(A)=36 < f(C)=g(C)=70$, so we remove $A$ from the fringe, which is now $\mathbb{F} = \{ C \}$. Is $A$ a goal node? No, so we expand it, but it only has one child, $B$, so we add $B$ to the fringe, so $\mathbb{F} = \{ C, B \}$. The cost of the path to reach $B$ by going first to $A$ and then to $B$ is $f(B) = 36 + 36 = 72$ (given that you go back and forward on the same edge, so you need to accumulate the cost of these trips!) and $f(C) = 70$, so we visit $C$, so we remove it from the fringe, which is now $\mathbb{F} = \{ B \}$.

You should be able to work out the remaining search (I haven't actually done it). I suggest you watch the video Uniform Cost Search, by John Levine, who shows a concrete example of how UCS and A* work.