Answers.Body: <p>Let's consider a problem where all edge costs are greater than zero, but not above some <span class="math-container">$\epsilon$</span>:</p>
  <p>Image a problem where we have an infinite path where the first edge is cost <span class="math-container">$\frac{1}{2}$</span>, the next is <span class="math-container">$\frac{1}{4}$</span>, the following is <span class="math-container">$\frac{1}{8}$</span>, and so on forever. Every edge is greater than zero, meeting the condition being proposed in the question. However, this path overall has finite cost (1) even through there are an infinite number of states on that path. So, on this problem UCS will never reach paths with cost greater than 1. Thus, if the solution cost is 2, UCS will not find any solution to this problem, and thus it would not be a complete algorithm. So, all edges being greater than zero is not sufficient.</p>
  <p>For most search algorithms to be complete, there must be a finite number of states with any given cost. (To be slightly more precise, there must exist some fixed <span class="math-container">$\epsilon$</span> such that in each range size <span class="math-container">$\epsilon$</span> there are a finite number of states.)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-09T22:58:44.693Z
Answers.LastActivityDate: 2020-11-09T23:26:59.480Z
Answers.LastEditDate: 2020-11-09T23:26:59.480Z
Answers.UserDisplayName: Nathan S.
Body: <p>I was reading <a href="https://rads.stackoverflow.com/amzn/click/com/0136042597" rel="nofollow noreferrer" rel="nofollow noreferrer">Artificial Intelligence: A Modern Approach 3rd Edition</a>, and I have reached to the UCS algorithm.</p>
  <p>I was reading the proof that UCS is complete.</p>
  <p>The book state that:</p>
  <blockquote>
  <p>Completeness is guaranteed provided the cost of every step exceeds some small positive constant <span class="math-container">$\epsilon .$</span></p>
  </blockquote>
  <p>And that's because UCS will be stuck if there is a path with an infinite
  sequence of zero-cost actions.</p>
  <p>Why the step cost must exceed <span class="math-container">$\epsilon$</span>? Isn't enough for it to be greater than zero?</p>
  
Tags: <search><uniform-cost-search><completeness>
Title: Why is the completeness of UCS guaranteed only if the cost of every step exceeds some small positive constant?
UserDisplayName: Kais Hasan
ThreadText: # Why is the completeness of UCS guaranteed only if the cost of every step exceeds some small positive constant?
  
  (Asked by: username_0 on 2020-11-09)
  
  I was reading [Artificial Intelligence: A Modern Approach 3rd Edition](https://rads.stackoverflow.com/amzn/click/com/0136042597), and I have reached to the UCS algorithm.
  
  I was reading the proof that UCS is complete.
  
  The book state that:
  
  > Completeness is guaranteed provided the cost of every step exceeds some small positive constant $\epsilon .$
  
  And that's because UCS will be stuck if there is a path with an infinite
  sequence of zero-cost actions.
  
  Why the step cost must exceed $\epsilon$? Isn't enough for it to be greater than zero?
  
  **Tags:** search, uniform-cost-search, completeness
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-11-09. Score: 6 | Accepted answer
  
  Let's consider a problem where all edge costs are greater than zero, but not above some $\epsilon$:
  
  Image a problem where we have an infinite path where the first edge is cost $\frac{1}{2}$, the next is $\frac{1}{4}$, the following is $\frac{1}{8}$, and so on forever. Every edge is greater than zero, meeting the condition being proposed in the question. However, this path overall has finite cost (1) even through there are an infinite number of states on that path. So, on this problem UCS will never reach paths with cost greater than 1. Thus, if the solution cost is 2, UCS will not find any solution to this problem, and thus it would not be a complete algorithm. So, all edges being greater than zero is not sufficient.
  
  For most search algorithms to be complete, there must be a finite number of states with any given cost. (To be slightly more precise, there must exist some fixed $\epsilon$ such that in each range size $\epsilon$ there are a finite number of states.)
  
  
  ---
  
  