# 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> 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?