Stochastic motion planning with path constraints and application to optimal agent, resource, and route planning

We present algorithms for a motion planning for multiple agents whose goals are to visit multiple locations with probabilistic guarantees for achieving the goal. Though much research has been done in stochastic shortest path algorithms, the existing algorithms focus on the single-origin single-destination problem for one agent. This paper formulates a general framework for the stochastic shortest path problem with visit node constraints designed to achieve a specific goal with multiple agents, multiple resources, and multiple destinations. The constraints are defined by a set of sequences of nodes to be visited. Given predetermined constraints, our motion planning problem consists of finding the best agents, resources, and destinations, and the path through a sequence of nodes representing them. The technique in this paper solves the problem at the same level of complexity as solving the single-origin single-destination problem by parallelization. We demonstrate the algorithm by a Web-based traffic navigation guide system and evaluate the algorithm´s performance.