Solving Belief-Driven Pathfinding Using Monte-Carlo Tree Search

This paper proposes a stochastic extension to Belief-Driven Pathfinding (BDP), a method for helping non-player characters navigate based on what they believe about the state of a map rather than its actual state. The original BDP approach represented special locations such as doors as simply open or closed; the extension, termed Stochastic BDP (SBDP), instead assigns each entrance a probability of being open, with an initial value such as 0.5. The authors frame the resulting problem as a special case of the Canadian Traveler Problem, or stochastic shortest-path problem with recourse, which can be reduced to a Markov Decision Process. Because the environment is uncertain, the character must compute a policy covering the possible outcomes rather than a single fixed path.

The proposed solution combines planning and execution phases. During execution, the character updates its beliefs through sensing, which sets an observed entrance's probability to 1 if open or 0 if closed, and through knowledge decay, a mechanism in which probabilities drift back toward 0.5 over time at a rate controlled by a decay parameter. To compute policies, the authors develop three approximate Monte Carlo Tree Search methods adapted from prior work on the Canadian Traveler Problem: Optimistic Policy, Hindsight Optimization, and Optimistic Rollout.

The work is at an early stage and is presented as a proposal with ongoing evaluation rather than a completed study. The authors state that they are investigating parameter settings that allow SBDP to perform comparably to the original BDP while producing richer behavior, and that they plan to assess ease of integration with existing pathfinding engines and the effect on player engagement. Preliminary indications suggest that the simpler Optimistic Policy and Hindsight Optimization methods may measurably improve player satisfaction and agent believability, though no quantitative results, sample sizes, or specific statistics are reported.