2
$\begingroup$

This is a question about a nomenclature - we already have the algorithm/solution, but we're not sure whether it qualifies as utilizing heuristics or not.

feel free to skip the problem explanation:

A friend is writing a path-finding algorithm - an autopilot for an (off-road) vehicle in a computer game. This is a pretty classic problem - he finds a viable, not necessarily optimal but "good enough" route using the A* algorithm, by taking the terrain layout and vehicle capabilities into account, and modifying a direct (straight) line path to account for these. The whole map is known a'priori and invariant, though the start and destination are arbitrary (user-chosen) and the path is not guaranteed to exist at all.

This cookie-cutter approach comes with a twist: limited storage space. We can afford some more volatile memory on start, but we should free most of it once the route has been found. The travel may take days - of real time too, so the path must be saved to disk, and the space in the save file for custom data like this is severely limited. Too limited to save all the waypoints - even after culling trivial solution waypoints ('continue straight ahead'), and by a rather large margin, order of 20% the size of our data set.

A solution we came up with is to calculate the route once on start, then 'forget' all the trivial and 90% of the non-trivial waypoints. This both serves as a proof that a solution exists, and provides a set of points reaching which, in sequence, guarantees the route will take us to the destination.

Once the vehicle reaches a waypoint, the route to the next one is calculated again, from scratch. It's known to exist and be correct (because we did it once, and it was correct), it doesn't put too much strain on the CPU and the memory (it's only about 10% the total route length) and it doesn't need to go into permanent storage (restarting from any point along the path is just a subset of the solution connecting two saved waypoints).

Now for the actual question:

The pathfinding algorithm follows a sparse set of waypoints which by themselves are not nearly sufficient as a route, but allow for easy, efficient calculation of the actual route, simultaneously guarantying its existence; they are a subset of the full solution.

Is this a heuristic approach?

(as I understand, normally, heuristics don't guarantee existence of a solution, and merely suggest more likely candidates. In this case, the 'hints' are taken straight out of an actual working solution, thus my doubts.)

Improve this question
$\endgroup$

3 Answers 3

Reset to default
1
$\begingroup$

Since you mention the A* algorithm, then you are definitely using a heuristic somewhere in there, at least with the A* algorithm while solving the subproblems using the straight-line distance as your heuristic function.

Although your approach does not seem to incorporate a "shortcut mathematical formula" as a heuristic after that, it does us a precalculated heuristic table as a reference and that may qualify as a heuristic. Wikipedia page here says (although without citation) the following which does seem to describe what you are doing where your heuristic is not a fixed but a precalculated function/table:

A heuristic function, also called simply a heuristic, is a function that ranks alternatives in search algorithms at each branching step based on available information to decide which branch to follow. For example, it may approximate the exact solution.

On another note, your method also seems to have hints of dynamic programming since you use the precalculated and stored solutions to subproblems and instead of recalculating every time.

I wonder if the term approximate dynamic programming would fit this situation as a non-stochastic version with no uncertainties? Unfortunately I could not find any simple description or categorization for that term.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Good catch with A* using heuristics. $\endgroup$
    – SF.
    Oct 4, 2016 at 7:22
1
$\begingroup$

Whether or not a label fits any particular instance depends on what you're using the label for. If something specific is riding on whether this approach is a 'heuristic' or not, that context is important.

But I wouldn't call this a heuristic, because I think of that as a shortcut for solving a problem, not either storing a solution or reformulating the problem (which is how I'd think of this).

Improve this answer
$\endgroup$
1
$\begingroup$

A 'heuristic' is simply a 'rule-of-thumb', i.e. something which doesn't guarantee an optimal solution to a problem.

Beyond the above notion (certainly within the discipline of optimization), the notion of what constitutes a heuristic is not particularly strict, and could certainly include hints for constructing a new solution from parts of a previous one, as you are doing.

A related concrete example is the "nearest neighbour heuristic" for the Travelling Salesman Problem, in which a solution is constructed by starting at some random city and iteratively choosing the nearest. The resulting completed tour is then used as an initial input to some more sophisticated optimization procedure.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .