How do I find whether this heuristic is or not admissible and consistent? I was given the following problem to solve.


  Given a circular trail divided by $n&gt; 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&gt;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?
Welcome to AI.SE @hpr16!

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.