A* heuristic for use with Goal Oriented Action Planner

Question

Many of the high-level descriptions I've found for GOAP and similar planners suggest using A* for their path-finding, but I'm struggling to implement it for my own planner. Specifically, I'm struggling with creating an admissible heuristic.

As a trite example, consider this set of nodes, expressed as a map of srcCoord -> dstCoord -> cost (cost is Euclidean distance with one exception):

{0, 0}:
  {-14, 0}: 14.0,
  {3, 3}: 4.242640687119285,
{-14, 0}:
  {10, 10}: 1.0, # exception here, call it a wormhole
{3, 3}:
  {6, 6}: 4.242640687119285,
{6, 6}:
  {9, 9}: 4.242640687119285,
{9, 9}:
  {10, 10}: 1.4142135623730951,

The shortest path from {0,0} to {10,10}, by 0.1421356237309501, is {0,0} -> {-14,0} -> {10,10}.

Euclidean distance is a reasonable heuristic without wormholes in the picture, but it's inadmissible here: It'd return 26 for {-14,0}->{10,10}, so it'll never expand the {-14,0} node and will end up incorrectly returning the path through {3,3}.

My planner has no connection to 2d-geometries, but it exhibits this "wormhole" behavior... an initial action doesn't appear to get us closer to our goal, but after expansion we see that it makes future actions less costly, or amplifies their effect in reaching the goal.

Here's a specific example I have in mind for amplifying the impact of future actions:

If mid-fight a better weapon (let's assume it's better in all respects) appears on the ground than the one currently equipped (likely dropped by someone who died), and it won't take longer to pick it up + finish the enemy than to finish the enemy with the current weapon, then pick it up, equip it, and use it.

How can I avoid overestimating the remaining cost after picking up the weapon? It's tempting to say "let's assume the best possible outcome will come to pass", but if there're any further options after picking up the item than equipping and using it then calculating the best outcome would require its own planning exercise, turning my A* into a DFS.

Some plausible future actions that could lower our actual cost to lower the most obvious estimate:

• wield the weapon with two hands, in order to do more damage
• cast Haste on ourselves to double our attack speed
• use a weapon-specific technique, e.g. sweeping our opponent's feet / tripping them using the haft of a polearm

Answer 1

Choosing a good heuristic is the hardest part of applying A* in novel situations.

Fortunately, it can be fairly forgiving. The "null heuristic"

float HeuristicRemainingCost(Node node) {
    return 0.0f;
}

...still gives the correct least-cost path in the end. It just falls back on Dijkstra-like behaviour, searching all paths in order of cost aimlessly, rather than accelerated toward promising directions.

Any amount of improvement on this should - in at least some situations - help speed up our algorithm. For instance, for your wormhole example, we could use...

float HeuristicRemainingCost(Node node) {
    // The best wormhole-free path can't be shorter than a straight line trip.
    float beeline = EuclideanDistance(node, goal);

    // The best wormhole-using path can't be shorter than the path to the nearest entrance
    // plus the path from the goal to its nearest exit.
    float enterWormhole = EuclideanDistance(node, GetClosestWormholeEntrance(node));
    float exitWormhold = EuclideanDistance(goal, GetClosestWormholeExit(goal));
   
    // So, the best path with or without wormhole use can't be shorter than:
    return Min(beeline, enterWormhole + wormholeCost + exitWormhole);
}

Here we've applied what's called a "relaxation" - we've "relaxed" the problem of navigating wormholes with each entrance leading to just one specific exit, to the simpler problem where any entrance can connect to any exit. This relaxation makes our estimate simpler, without increasing the estimated length of the optimal path, so it's safe.

This will beeline to a wormhole - any wormhole - if it's closer than the goal - the correct move if the wormhole actually helps and the wrong move otherwise, but it's limited in how long it will pursue those wrong moves: once it's explored the cells near dud wormholes it will revert to normal Euclidean heuristic A* behaviour in the spaces between.

You can see it's still a fairly naive estimate, but it doesn't have to be too clever - it only has to be better than return 0 to be worth a try, and as long as it's admissible (never overestimates) it won't impact correctness.

It's tempting to try to get more accurate here. Say instead of taking the shortest distance from any wormhole exit to our goal, we take the closest wormhole entrance we found above and compute the distance of its particular exit from the goal. Unfortunately, that re-introduces the possibility to over-estimate the distance, making our heuristic inadmissible. It might be the case that this wormhole takes me 1000 lightyears away from my goal, right next to the entrance to another wormhole that takes me straight to the goal. So if I fixate on just the closest wormhole I found, I could disregard fruitful paths and get a sub-optimal result. If your goal is fixed, you can solve this by pre-computing path distances from all wormholes taking other wormholes into account, but otherwise the optimistic approach above is still decent.

The other saving grace here is that, for an AI trying to make decisions that pass as an intelligent player, it doesn't have to be perfect. Humans are pretty rubbish at forecasting future events. If a new weapon randomly dropped midway through the combat that radically altered the strategy of the fight, that would probably surprise a human player too! It would be OK if the human or AI's planning up to that point didn't take that remote possibility into account. As long as they re-plan when new information becomes available, and take actions that are rationally advantageous based on the observable current situation, then they'll appear to be an intelligent and formidable adversary.

(Conversely, if they take an action that looks disadvantageous, counting on a random future event to make it an advantage later, this might make the AI appear less intelligent in the short term, or like it's cheating by using knowledge of future rolls)

So, a good policy here is to try to be optimistic, but not precognitive. It's OK if unpredicted stuff happens down the line and forces us to re-plan, as long as we're making good decisions about the predictable stuff.

So, here's one way to do that: as a pre-processing step, stack all the abilities your character has available to it, to determine the most damage it can do in a turn.

This is a good place to apply relaxations to keep your math tractable: Haste takes one turn to cast and only applies for 3 turns, and you only have enough mana to cast it twice? Well, pretend it's always active for free - this never underestimates the advantage you get, so it never overestimates the time to kill, and it's dirt simple to calculate.

More nuanced heuristics can be more true-to-life, but profile with the crude ones first to see if your performance is adequate. There's a point of diminishing returns where making your heuristic better but more expensive to compute costs more in heuristic evaluations than it saves you in cutting down the search space.

With this crude optimisticDamage in hand, your heuristic could be something like this, assuming we always deal our best possible damage every turn and never have to pay any mana for it:

float HeuristicRemainingCost(Node node) {
    float idealTurnsToKill = Ceiling(node.opponentHealth / optimisticDamage);
    return costPerTurn * idealTurnsToKill + costPerMana * 0;
}

Even if it's not reliably doing that much damage in a turn, this is still a much better estimate than return 0, for just the expense of one division and a little pre-computation. When faced with the choice between moves A and B, and A does more damage than B for the same mana cost, or does the same damage for less mana, this heuristic is already enough for A* to favour A over B and make faster progress toward promising directions, even if both moves are vastly weaker than the computed optimistic damage.