Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

A* admissible heuristics on a grid with teleporters?

Tags:

Suppose that you have a 2D grid of cells, some of which are filled in with walls. Characters can take a step from one square to any square that is one step horizontal or vertical from it, but cannot cross walls.

Given a start position and an end position, we can find the shortest path from the start position to the end position by using the A* algorithm with an admissible heuristic. In this current setup, the Manhattan distance would be admissible, since it never overestimates the distance to the destination.

Now suppose that in addition to walls, the world has pairs of teleporters. Stepping onto a teleporter immediately transports a character to the linked teleporter. The existence of teleporters breaks the admissible heuristic given above, since it might be possible to get to the destination faster than taking the optimal Manhattan distance walk by using a teleporter to cut down on the distance. For example, consider this linear world with teleporters marked T, start position marked S, and end position marked E:

T . S . . . . . . . . . . . . . E . T

Here, the best route is to walk to the teleporter on the left, then take two steps to the left.

My question is this: what is a good admissible heuristic for A* in a grid world with teleporters?

Thanks!

like image 330
templatetypedef Avatar asked Jan 20 '13 19:01

templatetypedef


People also ask

How is heuristic admissible calculated?

A heuristic is admissible if it never overestimates the true cost to a nearest goal. A heuristic is consistent if, when going from neighboring nodes a to b, the heuristic difference/step cost never overestimates the actual step cost.

Is straight line distance heuristic admissible?

We can use straight line distances as an admissible heuristic as they will never overestimate the cost to the goal. This is because there is no shorter distance between two cities than the straight line distance.

What is a heuristic in pathfinding?

Normally when a pathfinding search is made, a heuristic is used. The heuristic is something which gives a rough estimate on how far it is at least to the target. Usually the distance to the target is used directly since this is fast and usually gives relatively good results.

Are h1 and h2 heuristics admissible?

Consider three heuristics h1,h2,h3. The table below indicates the estimated cost to goal (h value) for each of the heuristics for each node in the search graph. h1, and h2 are admissible. h1 is also consistent.


2 Answers

If there aren't too many teleporters in your world, I would try the following heuristic, where MHD(a,b) is Manhattan distance between cell a and b and T(i) is the teleporter nearest to cell i:

h(x,y) = min( MHD(x,y), MHD(x,T(x)) + MHD(T(y),y) )
like image 196
us2012 Avatar answered Sep 18 '22 11:09

us2012


Form a graph of the teleporters:

  • You have a node for each teleporter and a node for the end position.
  • You have an edge connecting each node to each other node, forming a fully connected graph.
  • For the edge weights, use the Manhattan distance between each node's destination cell (the one you go to when you enter the teleporter) and all the other nodes.

Use Dijkstra's algorithm to calculate the shortest distance from each node to the end.

You can now use the minimum of the distance between a particular position and all the nodes plus the pre-calculated distance from the node to the end as a heuristic function. Dijkstra's algorithm only has to be run once as a pre-processing step. However, if the number of teleporters is a large perecentage of the number of cells, you may not get any benefit over using a simpler heuristic function.

like image 37
Vaughn Cato Avatar answered Sep 22 '22 11:09

Vaughn Cato