AI for real life: The perfect is the enemy of the good

I have seen that searching for a perfect solution is much harder than searching for a good solution. My experience is based on AI planning. You have to find a path from a start to a goal there. A perfect solution would find the shortest path.

If you need the shortest path, you have to examine all promising paths. You cannot skip a path that could be possibly shorter than the currently best known solution.

If a good solution is enough, you have more possibilities how to find the solution. For example, you could stop the search when no promising path would be X-times better. You could also be more realistic about the promising paths. It is OK to over-estimate the length of a path. That would postpone the path for later examination. A good enough solution could be found in the meantime.

The hardness of the search is seen on the International Planning Competition 2008. They have two tracks:

• The "satisficing track" is for planners searching a good solution.
• The "optimization track" is for cost-optimal planners. They are searching only for the perfect solution.

The competition uses much larger problems for the satisficing planners. The cost-optimal planners would not be able to solve the same problems in the given time.

It is also interesting that no cost-optimal planner was better than a basic breadth-first search. The breadth-first search was used as the "baseline" for the "optimization track". A planner would need prior knowledge, to carefully estimate the lengths of the paths. Otherwise it is not faster than doing the walk.

Additional reading

The prior knowledge could be, for example, knowledge of solutions to easier problems. You then know that the harder problem will take at least the same number of steps: Hierarchical A*: Searching Abstraction Hierarchies Efficiently