CODEWITHSUNDEEP
algorithmartificial-intelligenceheuristicsplanning
kaisa
kaisa

Reputation: 51

Manhattan distance generalization

For a research I'm working on I'm trying to find a satisfying heuristic that is based on Manhattan distance which can work with any problem and domain as an input. Which is also known as domain-independent heuristic. For now, I know how to apply Manhattan distance on a grid based problems. Can someone give a tip how to generalize it to work on every domain and problem and not just grid based problems?

Upvotes: 3

Views: 1625

Answers (2)

Nick Larsen
Nick Larsen

Reputation: 18877

The manhattan distance heuristic is an attempt to measure the minimum number of steps required to find a path to the goal state. The closer you get to the actual number of steps, the fewer nodes have to be expanded during search, where at the extreme with a perfect heuristic, you only expand nodes that are guaranteed to be on the goal path.

For a more academic approach to generalizing this idea, you want to search around for domain independent heuristics; there was a lot of research done on this in the late 1990s early 2000s although even today, a small amount of domain knowledge can usually get you much better results. That being said, there are some good places to start:

  • delete relaxation: the expand function probably contains some restrictions, remove one or more of those restrictions and you'll end up with a much easier problem, one that can probably be solved in real time and you'll and use the value generated by that relaxed problem as the heuristic value. e.g. in the sliding tile puzzle, delete the constraint that a piece cannot move on top of other pieces and you end up with the manhattan distance, relax that a piece can only move to adjacent squares and you end up with the hamming distance heuristic.

  • abstraction: mapping every state in the real search to a smaller abstract state space that you can fully evaluate. Pattern databases are a very popular tool in this area.

  • critical paths: when you know you must pass through specific states (in either the real state space or an abstract state space) you can perform multiple searches between only the critical points to cut down greatly the number of nodes you would have to search in the full state space

  • landmarks: very accurate heuristics at the cost of typically high computation time. landmarks are specific locations in which you precompute the distance to every possible other state from (typically 5-25 landmarks are used depending on graph size) and then you compute the lower bound possible distance using those precomputed values when evaluating each node.

There are a few other classes of domain independent heuristics, but these are the most popular and widely used in classical planning applications.

Upvotes: 1

Gordon Linoff
Gordon Linoff

Reputation: 1269563

The generalization of Manhattan distance is simple. It is a metric which defines the distance between two multi-dimensional points as the sum of the distances along each dimension:

md(A, B) = dist(a1, b1) + dist(a2, b2) + . . .

The distances along each dimension are assumed to be simple to calculate. For numbers, the distance is the absolute value of the difference between the values.

This can be extended to other domains as well. For instance, the distance between two strings could be taken as the Levenshtein distance -- and that would prove to be an interesting metric in conjunction with other dimensions.

Upvotes: 3

Related Questions