Answers.Body: <p><strong>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!</strong></p>
  
  <p>The evaluation function of uniform-cost search (UCS) is <span class="math-container">$f(n) = g(n)$</span>, where <strong><span class="math-container">$g(n)$</span> represents the cost of the path from the start node to <span class="math-container">$n$</span></strong>. The evaluation function of A* is <span class="math-container">$f(n) = g(n) + h(n)$</span>, where <span class="math-container">$h(n)$</span> is an admissible heuristic. <a href="https://ai.stackexchange.com/a/9183/2444">UCS is a special case of A*</a>, with the admissible heuristic <span class="math-container">$h(n) = 0, \forall n$</span>. The evaluation function is used to choose the next node to <strong>visit</strong> from the <a href="https://ai.stackexchange.com/q/5949/2444">fringe</a>, which is the set of nodes that can potentially be <strong>visited</strong>. Whenever we <strong>visit</strong> a node, we remove it from the fringe. To <strong>expand</strong> a node <span class="math-container">$X$</span> means to add the children of <span class="math-container">$X$</span> to the fringe. Whenever you <strong>visit</strong> a node, you will also <strong>expand</strong> it. </p>
  
  <p>Let's apply UCS to your specific example. Initially, we check whether <span class="math-container">$B$</span> is a goal node or not. It is not, so we expand <span class="math-container">$B$</span>. We can add <span class="math-container">$B$</span> 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. <span class="math-container">$B$</span> has two children, <span class="math-container">$A$</span> and <span class="math-container">$C$</span>, so we add them to the fringe, <span class="math-container">$\mathbb{F} = \{A, C\}$</span>. Should we now visit <span class="math-container">$A$</span> or <span class="math-container">$C$</span>? We will visit the one with the smallest value of the evaluation function, which is <span class="math-container">$A$</span>, given that <span class="math-container">$f(A)=g(A)=36 &lt; f(C)=g(C)=70$</span>, so we remove <span class="math-container">$A$</span> from the fringe, which is now <span class="math-container">$\mathbb{F} = \{ C \}$</span>. Is <span class="math-container">$A$</span> a goal node? No, so we expand it, but it only has one child, <span class="math-container">$B$</span>, so we add <span class="math-container">$B$</span> to the fringe, so <span class="math-container">$\mathbb{F} = \{ C, B \}$</span>. The cost of the path to reach <span class="math-container">$B$</span> by going first to <span class="math-container">$A$</span> and then to <span class="math-container">$B$</span> is <span class="math-container">$f(B) = 36 + 36 = 72$</span> (given that you go back and forward on the same edge, so you need to accumulate the cost of these trips!) and <span class="math-container">$f(C) = 70$</span>, so we visit <span class="math-container">$C$</span>, so we remove it from the fringe, which is now <span class="math-container">$\mathbb{F} = \{ B \}$</span>.</p>
  
  <p>You should be able to work out the remaining search (I haven't actually done it). I suggest you watch the video <a href="https://www.youtube.com/watch?v=dRMvK76xQJI" rel="nofollow noreferrer">Uniform Cost Search</a>, by John Levine, who shows a concrete example of how UCS and A* work.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-11-25T02:41:43.283Z
Answers.LastActivityDate: 2019-11-25T03:02:01.337Z
Answers.LastEditDate: 2019-11-25T03:02:01.337Z
Answers.UserDisplayName: nbro
Body: <p>Consider the following diagram of a graph representing a search space.</p>
  
  <p><a href="https://i.sstatic.net/NgNuB.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/NgNuB.png" alt="enter image description here"></a></p>
  
  <p>If we start at <span class="math-container">$B$</span> and try to reach goal state <span class="math-container">$E$</span>, the lowest-cost first search (LCFS) (aka uniform-cost search) algorithm fails to find a solution. This is because, <span class="math-container">$B$</span> selects <span class="math-container">$A$</span> over <span class="math-container">$C$</span> to expand as <span class="math-container">$f(A)=g(A)=36 &lt; f(C)=g(C)=70$</span>. <span class="math-container">$f(n)$</span> is the cost function of node <span class="math-container">$n$</span>, and <span class="math-container">$g(n)$</span> is the cost of reaching node <span class="math-container">$n$</span> from the start state. Continuing further, from <span class="math-container">$A$</span>, LCFS will now select <span class="math-container">$B$</span> to expand, which in turn will select <span class="math-container">$A$</span> again over <span class="math-container">$C$</span>. This leads to an infinite loop. This shows LCFS is incomplete (not guaranteed to find a solution, if one exists).</p>
  
  <p>For A*, we define <span class="math-container">$f(n)=g(n)+h(n)$</span>, where <span class="math-container">$h(n)$</span> is the expected cost of reaching goal state from node <span class="math-container">$n$</span>. If we define Manhattan distance (<span class="math-container">$L_0$</span> norm) for <span class="math-container">$h(\cdot)$</span>, books (such as <a href="http://aima.cs.berkeley.edu/" rel="nofollow noreferrer">Artificial Intelligence: A Modern Approach (3rd Ed)</a> 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*, <span class="math-container">$B$</span> will still select <span class="math-container">$A$</span> since <span class="math-container">$f(A)=36+(h(A)=40)=76 &lt; f(C)=70+(h(C)=30+50)=150$</span>. You see, this means, when <span class="math-container">$A$</span> expands back <span class="math-container">$B$</span>, <span class="math-container">$B$</span> will again select <span class="math-container">$A$</span>, and an infinite loop ensues.</p>
  
  <p>What am I missing here?</p>
  
Tags: <search><a-star><norvig-russell><uniform-cost-search>
Title: A* and uniform-cost search are apparently incomplete
UserDisplayName: KGhatak
ThreadText: # A* and uniform-cost search are apparently incomplete
  
  (Asked by: username_0 on 2019-11-24)
  
  Consider the following diagram of a graph representing a search space.
  
  [![enter image description here](https://i.sstatic.net/NgNuB.png)](https://i.sstatic.net/NgNuB.png)
  
  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)](http://aima.cs.berkeley.edu/) 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?
  
  **Tags:** search, a-star, norvig-russell, uniform-cost-search
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-11-25. Score: 3 | Accepted answer
  
  **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\*](https://ai.stackexchange.com/a/9183/2444), with the admissible heuristic $h(n) = 0, \forall n$. The evaluation function is used to choose the next node to **visit** from the [fringe](https://ai.stackexchange.com/q/5949/2444), 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](https://www.youtube.com/watch?v=dRMvK76xQJI), by John Levine, who shows a concrete example of how UCS and A\* work.
  
  
  ---
  
  