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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.