How to force a sub-optimal path

Question

I'm currently trying to develop a "Taxi-Driver" AI that intentionally makes sub-optimal pathing decisions. I need to have my driver go from point A to point B using a sub-optimal but still logical path. "Logical" in this case isn't a well-defined condition per-se but it is instead defined as a path that would make sense to a passenger (player).

Here's an example where

• Green = Optimal
• Red = Suboptimal but "logical"
• Blue = Suboptimal but "illogical"

I'm currently using A* so I tried modifying node weights but I couldn't find a way to come up with a logical value for the weight. I've also tried to sometimes pick a random open node (in the right direction) instead of calculating the closest node. However this (understandably) made the pathing look even more illogical.

If it can be done I'd like an A* solution but I'm open to other solutions as well (even non-pathfinding solutions!). It is fine if a solution doesn't always give a sub-optimal path for certain conditions (e.g. only one path possible; all paths are the same length etc).

Answer 1

Your red path follows a pretty simple decision metric.

1. At each intersection, first evaluate which paths can reach the goal, and eliminate any that can't - this stops the algorithm from getting stuck in dead ends.

2. Next, evaluate which paths lead "toward" the goal (ie. the dot product of the path direction with a vector pointing to the goal is greater than zero). If at least one path leads toward the goal, eliminate any that don't.

   At the first intersection, the goal is both north and east of us, so both the north and east roads pass this filter.

   The south road travels opposite the direction to the goal, so it is eliminated (taking this eliminated path is what makes the blue route look illogical)

3. If there are multiple paths remaining, eliminate the shortest path(s) (plural because there may be ties), making sure to retain at least one valid option in the event that all routes are tied.

   This eliminates the green route from the first intersection, leaving only one choice, the "sub-optimal but logical" red route.

4. Choose arbitrarily or randomly from the remaining options, in case you have several.

Note though that there are maps where this will still give you the shortest path, if no opportunities to pick a longer-but-still-logical path present themselves at any single intersection.

Answer 2

You can do this by forcing your A* heuristic to be inadmissible.

An admissible heuristic is any heuristic which is strictly less than the true shortest path length. An example of an admissible heuristic is the euclidean distance to the target.

Admissible heuristics guarantee the optimal solution. So how do you garauntee a sub-optimal solution? You make your heuristic over-estimate the cost to the goal. Want to also make your paths a bit random? Inject (pseudo)randomness into the heuristic.

Here's an insane heuristic that might get you what you want:

float heuristic(Node A, Node goal) {
   return Distance(A, goal) + 
          Distance(A, goal) * abs(sin(A.position.x * goal.position.y));
}

This heuristic has a big chance of overestimating the path length to the goal because it adds this crazy periodic pseudo-random infaltion to distance calculation. By increasing the magnitude of that pseudo-random signal you can force the algorithm to choose suboptimal or random looking paths.

EDIT:

Another way I can think of is this:

1. Find the optimal path with A*

2. Pick a random cell along the optimal path and disallow it.

3. Find a new optimal path with a new map given from (2)

4. If a path can't be found clear the "unallowed" cells, and repeat 2 for until you've reached K iterations. If a path can't be found after K iterations, give up and just return the optimal path.

5. Otherwise return this new (sub-optimal) path.

Answer 3

You aren't really forcing a sub-optimal path, you're optimizing for something different.

"Logical" isn't well defined because "something that would make sense to a passenger" could mean different things to different passengers. However, it seems safe to assume that all passengers would have some logic behind what they find reasonable. You could find one sub-optimal solution, or even use different algorithms for different drivers depending on your goals. Either way, the difference from an optimal solution would ideally be based in how you want this AI to be perceived by the player.

UPS famously started using computer planning for driver routes decades ago, and this article gives some good examples:

The earliest versions of Orion focused on getting the best mathematical results, with insufficient regard for the interests of the driver or the customer, who value some level of routine. For example, regular business customers who receive packages on a daily basis don’t want UPS to show up at 10 a.m. one day, and 5 p.m. the next. And a customer who is expecting a shipment of frozen food needs delivery as soon as possible, even if efficiency demands that someone gets priority.

The most well known feature is that they try and avoid left turns whenever possible due to time spent idling waiting for opposing traffic to clear. So in your example, if you introduced a penalty for left turns, the red line would instead go straight for two blocks before turning right and heading due south to the goal. Depending on the exact position of the goal, this could even appear more logical.

Other ideas you could throw into a situation like this would be areas with traffic jams, construction, or any other excuse to add a bit of higher cost to certain blocks that would nudge the pathfinder to avoid them without completely ruling them out when it makes sense.