# Pathfinding with non-deterministic transitions between nodes

Consider a map not unlike a board game, where some of the moves are made non-deterministic. For example, moving onto certain cells will require you to roll a dice to determine where you should move next. The map, I would like to navigate agents through have similar characteristics:

• Some of the map nodes have deterministic connections while others do not (e.g. rolls a dice)
• The move random events can have more than two outcomes, in fact most of them have many (e.g. move to random node in certain radius)
• there are various distances (cost) between nodes

What algorithm(s) can be used to find on average the shortest path through such map for an agent? Though not required a nice bonus would be configurable risky-ness or confidence the path will 'work'.

Some time after asking I realized the is a major problem with the question - there is no path. Because agents can stray from planned path unexpectidly, rather than ordered sequence of nodes the algorithm should find goal direction/distance from every node, much like reachability/distance output from Dijkstra's algmorithm.

• For a moment, let's factor out the non-determinism - are your maps small enough that you would be able to get acceptable performance using something as straightforward as Dijkstra's algorithm to find the desired paths? – Pikalek Jan 10 '19 at 14:35
• @Pikalek yes, the map is of reasonable size currently - 100^2 to 1000^2 nodes. – wondra Jan 10 '19 at 14:45
• I've been running through a few candidate approaches, and for each one I can find pathological cases that make it either give very bad answers or do very bad things in the process of finding them. ;) Can you give us more insight into the typical structure of your maps? There might be some patterns we can exploit to get better efficiency / reliability than we could expect from fully-general graphs. – DMGregory Jan 10 '19 at 17:24
• @DMGregory I am early in prototyping stage and it does not have a precise shape yet because I wanted to make sure I was able to make interesting AI. Not going to lie, also the fact I was not able to find satisfying algorithm to this seemingly easy problem got me intrigued - it looks like A* pruning material but cant really apply it. Anyhow, the graph is directed and mostly leading in one direction, level goal. Random events(challenges) are frequent and there should be no dynamic recalculating, in fact path finding could be part of level generation and can take a few seconds. – wondra Jan 10 '19 at 19:32
• Can you give any estimates as to the connectivity of the graph? For instance, what's the max & average number of neighbors for a given node? And what's the number of deterministic vs non-deterministic moves? – Pikalek Jan 10 '19 at 20:07

## 2 Answers

You can use "expected values" like Continuum Crowds does it.

From the Treuille et al paper:

Expected periodic field changes. A similar issue arises when the field deterministically changes over time. Consider an environ- ment with two exit doors rapidly opening and closing. An exiting crowd would continuously switch direction back and forth towards the currently open door. Similarly, when a traffic light turns red the speed field must be temporarily set to zero to prevent crossing. Individuals in our basic model would naively conclude that cross- ing is impossible, and pick another path. Here we offer a different solution. When computing the potential, we replace the actual in- verse speed with the expected inverse speed computed over a longer time period. For traffic lights, the expected inverse speed is com- puted from the percentage of time the traffic light is green during a period. Similar computations are performed for other periodic changes (e.g. opening doors). By the linearity of expectations, the optimal path cost given in equation (2) can then be interpreted as the minimizing the expected time to the goal.

The short of it: if a traffic light is 3 times more likely to be red than green, then the cost of crossing that road is the inverse of the expected speed, which is 0.25 * S + 0.75 * 0, with S being regular walking speed.

Here is a video of that mechanism, in action:

• Thanks, if I understand it correctly, the algorithm is to determinize the graph and continue as normal pathfinding. Any ideas how it handles more than 2 options (either you cross or you dont)? Can you suggest a function where some of the results would move you backwards, some forward and some were neutral (to side)? – wondra Jan 10 '19 at 20:00
• Just use a weighted average of cost. If there is a change of 10% that you are placed three steps back, then in 1 in 10 cases, traversal cost is +300%. ( 9 * 1 + 1 * 4 ) / 10 hence 1.3 instead of the normal 1.0 cost. – Bram Jan 10 '19 at 21:39
• I am picking this answer because it is the simpler one and fits the now(edit) better formulated problem better. – wondra Jan 20 '19 at 11:14

One approach is to use the Monte Carlo method. Monte Carlo methods are mainly used in three problem classes: optimization, numerical integration, and generating draws from a probability distribution. This problem falls into the intersection of the first & third class, so Monte Carlo seems like a reasonable thing to try.

The basic idea behind the Monte Carlo method is to simulate a number of random attempts, accumulate information from the results & then use that data to make a decision. So for this particular problem, you would:

• simulate multiple attempts to get from one place to another
• for each attempt keep track of the number of moves (or other resources) required
• when done simulating attempts, use things like the min, max, average, standard deviation to make a decision

As a perk, you can use the collected stats in a variety of ways to simulate different flavors of AI. A risk averse AI might seek to avoid the worst case scenarios. An optimistic AI might favor greedy, unlikely moves that have a big pay off, but are prone to failure.

The number of attempts influences the strength of the conclusions, but is subject to diminishing returns (for an illustration of this, look up a simple coding experiment for using Monte Carlo to estimate Pi). As such it may require some tuning to make sure your not wasting a lot of time while only improving results by a fraction of a percent. In terms of implementation, the number of simulated attempts can be set by time, trial count or some combination of the two; use whichever is a good fit for your game / framework.

Also, for this problem, you might need to add in a simulation 'basement'. That is to say, it seems like it might be possible for a very unlucky attempt to end up cycling infinitely (the pawn always gets moved back to the start). To guard against that, I would add some logic that automatically bins any simulated trial that takes more than X moves. You might also want to keep track of where such cases end up - looking at those groupings might indicate that some map feature is acting like a probabilistic gravity well for luck & skewing your play.

The strengths of the Monte Carlo method are:

• relatively easy to code
• they often run quickly
• if the AI gets some extra processing cycles, you can improve your results
• often times you can change the underlying game play (say by adding teleporters or some other feature) and won't need to make many changes to the simulation
• you can simulate weaker AI by reducing the number of simulations
• they are used in both real world problems & games and thus have a fair body of research to all back on

The weaknesses are:

• determining the cutoffs can take a fair bit of tuning
• the don't guarantee optimal solutions
• if your problem size scales badly, they might not be practical

Some additional notes: if possible, I would first try to calculate a best path that completely avoids the non-deterministic nodes. If you can do so, this sets a lower bound. If a given simulation takes more distance (or time or what ever you're trying to minimize) than the purely non-deterministic path, you already know that there are better options.

• Thanks for the answer, Monte Carlo seems like a good starting point, however when considering it I ran into some challenges. Namely, how to handle the decision making? If there were just random events, I could simulate it a few time to approximate the likelihood of reaching nodes using Monte Carlo but there is quite a lot of agency in picking the challenges through deterministically linked nodes (crossroad nodes). I am not sure, how to include it in Monte Carlo simulation? Maybe pick path at random even on deterministic nodes? – wondra Jan 10 '19 at 19:45
• I see your point. I know that it's been applied to situations like backgammon where each step has a uncertainty & I think there they use a x-ply limitation, but you're right in that it doesn't immediately transfer to your problem. Let me think it over & see what I come up with. – Pikalek Jan 10 '19 at 20:03
• After looking into it more, my interpretation is that strictly speaking a Monte Carlo approach would use random chance to handle the decision making. Some of the decisions will be terrible. However, if the problem yields to a Monte Carlo, it should be just as likely that some decisions will be brilliant. – Pikalek Jan 10 '19 at 22:44