Evaluation, existence and optimization of reactive strategies in motion planning with uncertainty

摘要

We study the three classic problems, evaluation, existence and optimization for the reactive motion strategies in the frame of a robot moving with uncertainty using various sensors, based on traversing colored graphs with a probabilistic transition model. We first show how to construct such graphs for geometrical scenes and various sensors. We then mention some complexity results obtained on evaluation, optimization and approximation to the optimal in the general case strategies, and at the end we give some hints about the approximability to the optimum for the case of reactive strategies.