2019-01-10 12:52:52 8 Comments

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.

### Related Questions

#### Sponsored Content

#### 3 Answered Questions

### [SOLVED] Accurately simulating the lots of dice rolls without loops?

**2015-12-30 13:07:51****user76718****2368**View**15**Score**3**Answer- Tags: mathematics probability

#### 0 Answered Questions

### Simple Stupid Funnel Algorithm (SSFA) for 3D Navigation

**2017-08-09 21:25:45****Andriy Dzikh****261**View**1**Score**0**Answer- Tags: path-finding navmesh octree

#### 2 Answered Questions

### [SOLVED] HPA* Pathfinding, building the hierarchical graph is too slow

**2017-01-18 05:21:38****Demandooda****2381**View**1**Score**2**Answer- Tags: algorithm performance path-finding

#### 1 Answered Questions

### [SOLVED] Is A* suitable for this particular case?

**2017-01-03 21:22:50****vexe****63**View**0**Score**1**Answer- Tags: path-finding

#### 2 Answered Questions

### [SOLVED] Board Game Pathfinding - Finding optimum valid path with limited path distance?

**2016-09-18 00:13:07****Gaian Swine Helmers****182**View**1**Score**2**Answer- Tags: javascript algorithm path-finding board-game

#### 1 Answered Questions

### [SOLVED] Dijkstra's algorithm null hypothesis pathfinding without navmesh

**2016-02-16 20:05:41****drocktapiff****249**View**1**Score**1**Answer- Tags: path-finding dijkstra

#### 1 Answered Questions

### [SOLVED] Pathfinding across mutliple levels

**2015-03-18 01:44:35****fryBender****628**View**1**Score**1**Answer- Tags: path-finding

#### 2 Answered Questions

### [SOLVED] Pathfinding in non tile-based 2d map (maybe potential field)

**2014-02-01 11:16:28****Riccardo Vailati****2250**View**1**Score**2**Answer- Tags: 2d path-finding

#### 1 Answered Questions

### [SOLVED] Fastest pathfinding for static node matrix

**2012-06-12 00:47:19****Sean Martin****1129**View**3**Score**1**Answer- Tags: path-finding

#### 2 Answered Questions

### [SOLVED] Pathfollowing with acceleration - centripetal force

**2012-04-23 19:35:43****xcrypt****457**View**3**Score**2**Answer- Tags: physics path-finding

## 2 comments

## @Pikalek 2019-01-10 16:06: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:

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:

The weaknesses are:

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.

## @wondra 2019-01-10 19:45:27

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?

## @Pikalek 2019-01-10 20:03:37

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 2019-01-10 22:44:38

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,

ifthe problem yields to a Monte Carlo, it should be just as likely that some decisions will be brilliant.## @Bram 2019-01-10 17:26:22

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:

## @wondra 2019-01-10 20:00:18

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

## @Bram 2019-01-10 21:39:04

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.

## @wondra 2019-01-20 11:14:17

I am picking this answer because it is the simpler one and fits the now(edit) better formulated problem better.