0
\$\begingroup\$

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"

example of suboptimal vs optimal path

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).

\$\endgroup\$
  • \$\begingroup\$ How about just taking a a wrong node every 3 or so? \$\endgroup\$ – dot_Sp0T Oct 20 '17 at 19:20
  • 1
    \$\begingroup\$ @dot_Sp0T The blue path makes only two wrong turns (assuming U-turns are forbidden): one at the first intersection, and one four turns later. So it doesn't take a high ratio of random wrong turns in order to fall into the "illogical" symptom that OP asks us to avoid. \$\endgroup\$ – DMGregory Oct 20 '17 at 19:54
4
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.