Solving Stochastic Shortest Path Problem Using Monte Carlo Sampling Method: A Distributed Learning Automata Approach

摘要

In this paper, we introduce a Monte Carlo simulation method based on distributed learning automata (DLA) for solving the stochastic shortest path problem. We give an iterative stochastic algorithm that finds the minimum expected value of set of random variables representing cost of paths in a stochastic graph by taking sufficient samples from them. In the given algorithm, the sample size is determined dynamically as the algorithm proceeds. It is shown that when the total sample size tends to infinity, the proposed algorithm finds the shortest path. In this algorithm, at each instant, DLA determine which edges to be sampled. This reduces the unnecessary sampling from the edges which don't seem to be on the shortest path and thus reduces the overall sampling size. A new method of proof (different from [2,3]) is used to prove the convergence of the proposed algorithm. The simulations conducted confirm the theory.