I am wondering about a problem that I was given to solve:
Given circular trail divided by n segments(n>2) labeled 0..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 on same speed.
The action slow down cannot be used if 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 is given as:
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 complete and consistent.
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 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 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?