Answers.Body: <p>Welcome to AI.SE @hpr16!</p>
  
  <p>Your understanding of when a heuristic is admissible is correct, but your heuristic is inadmissible. An admissible heuristic must always underestimate the cost to move from a given <em>state</em> to a goal state. </p>
  
  <p>Notice that states in the search are <em>not</em> the same as positions on the circle in your problem. A state needs to capture all the information about the current environment the agent is in. In your problem, agents have a speed as well as a position. A state must, therefore, contain both.</p>
  
  <p>To see why your heuristic is inadmissible because the agent can move (n-z) segments in less than n-z steps: it can speed up, and do them in, for example, (n-z)/2 steps, by moving with speed 2. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-03-26T20:36:19.383Z
Answers.LastActivityDate: 2019-03-26T20:36:19.383Z
Answers.UserDisplayName: John Doucette
Body: <p>I was given the following problem to solve.</p>
  
  <blockquote>
    <p>Given a circular trail divided by <span class="math-container">$n&gt; 2$</span> segments labeled <span class="math-container">$0 \dots n-1$</span>. In the beginning, an agent is at the start of segment number <span class="math-container">$0$</span> (the edge between segments <span class="math-container">$n-1$</span> and <span class="math-container">$0$</span>) and the agent's speed (<span class="math-container">$M$</span>) is <span class="math-container">$0$</span> segments per minute.</p>
    
    <p>At the start of each minute the agent take one of three actions:</p>
    
    <ul>
    <li><strong>speed up</strong>: the agent's speed increases by <span class="math-container">$1$</span> segment per minute.</li>
    <li><strong>slow down</strong>:  the agent's speed decreases by <span class="math-container">$1$</span> segment per minute.</li>
    <li><strong>keep the same speed</strong>: stay at the same speed.</li>
    </ul>
    
    <p>The action <strong>slow down</strong> cannot be used if the current speed is <span class="math-container">$0$</span> segments per minute.</p>
    
    <p>The cost of each action is <span class="math-container">$1$</span>.</p>
    
    <p>The goal of the agent is to drive around the trail k times (<span class="math-container">$1 \leq k$</span>)  and then park in the beginning spot (at speed 0 of course). The agent needs to do that in the minimum amount of actions.</p>
    
    <p>The heuristic given is: <em>If agent is in segment <span class="math-container">$z$</span> then: <span class="math-container">$n-z$</span> if <span class="math-container">$z \not = 0$</span> or <span class="math-container">$0$</span> if <span class="math-container">$z=0$</span></em>.</p>
  </blockquote>
  
  <p>I need to find if the given heuristic is admissible (or complete) and consistent.</p>
  
  <p>I think:</p>
  
  <ul>
  <li><p>Regarding consistency: A heuristic is consistent if its estimate is always <span class="math-container">$\leq$</span> estimated distance from any given neighbour vertex to goal plus cost of reaching a goal. So, in the given problem, it is consistent because (<span class="math-container">$n&gt;2$</span>), so heuristic function is well defined and because of circular trail divided by <span class="math-container">$n$</span> segments with a constant price of <span class="math-container">$1$</span> for each action, then the given definition of consistency holds because estimated distance from any given neighbour vertex to goal can be looked on as a difference between segments until reaching a goal and it is consistent because again the function is well defined.</p></li>
  <li><p>Regarding admissibility: An admissible heuristic is one that the cost to reach goal is never more than the lowest possible cost from the current point to reach the goal. I am not sure if the given heuristic is admissible because it does not help much to know the difference between trail size (<span class="math-container">$n$</span> = segment size) and current place. But it does not create flaws, so it is probably admissible. I am not sure this is a proof.</p></li>
  </ul>
  
  <p>Is my idea correct? How could I write it as a proof?</p>
  
Tags: <search><proofs><heuristics><admissible-heuristic><consistent-heuristic>
Title: How do I find whether this heuristic is or not admissible and consistent?
UserDisplayName: hpr16
ThreadText: # How do I find whether this heuristic is or not admissible and consistent?
  
  (Asked by: username_0 on 2019-03-26)
  
  I was given the following problem to solve.
  
  > Given a circular trail divided by $n> 2$ segments labeled $0 \dots n-1$. In the beginning, an agent is at the start of segment number $0$ (the edge between segments $n-1$ and $0$) and the agent's speed ($M$) is $0$ segments per minute.
  >
  > At the start of each minute the agent take one of three actions:
  >
  > * **speed up**: the agent's speed increases by $1$ segment per minute.
  > * **slow down**: the agent's speed decreases by $1$ segment per minute.
  > * **keep the same speed**: stay at the same speed.
  >
  > The action **slow down** cannot be used if the current speed is $0$ segments per minute.
  >
  > The cost of each action is $1$.
  >
  > The goal of the agent is to drive around the trail k times ($1 \leq k$) and then park in the beginning spot (at speed 0 of course). The agent needs to do that in the minimum amount of actions.
  >
  > The heuristic given is: *If agent is in segment $z$ then: $n-z$ if $z \not = 0$ or $0$ if $z=0$*.
  
  I need to find if the given heuristic is admissible (or complete) and consistent.
  
  I think:
  
  * Regarding consistency: A heuristic is consistent if its estimate is always $\leq$ estimated distance from any given neighbour vertex to goal plus cost of reaching a goal. So, in the given problem, it is consistent because ($n>2$), so heuristic function is well defined and because of circular trail divided by $n$ segments with a constant price of $1$ for each action, then the given definition of consistency holds because estimated distance from any given neighbour vertex to goal can be looked on as a difference between segments until reaching a goal and it is consistent because again the function is well defined.
  * Regarding admissibility: An admissible heuristic is one that the cost to reach goal is never more than the lowest possible cost from the current point to reach the goal. I am not sure if the given heuristic is admissible because it does not help much to know the difference between trail size ($n$ = segment size) and current place. But it does not create flaws, so it is probably admissible. I am not sure this is a proof.
  
  Is my idea correct? How could I write it as a proof?
  
  **Tags:** search, proofs, heuristics, admissible-heuristic, consistent-heuristic
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-03-26. Score: 2
  
  Welcome to AI.SE @username_0!
  
  Your understanding of when a heuristic is admissible is correct, but your heuristic is inadmissible. An admissible heuristic must always underestimate the cost to move from a given *state* to a goal state.
  
  Notice that states in the search are *not* the same as positions on the circle in your problem. A state needs to capture all the information about the current environment the agent is in. In your problem, agents have a speed as well as a position. A state must, therefore, contain both.
  
  To see why your heuristic is inadmissible because the agent can move (n-z) segments in less than n-z steps: it can speed up, and do them in, for example, (n-z)/2 steps, by moving with speed 2.
  
  
  ---
  
  