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.