OPTIMAL ROBUST PATH PLANNING IN GENERAL ENVIRONMENTS

We address robust path planning for a mobile agent in a general enviro nment by finding minimum cost source-destination paths having prescrib ed widths. The main result is a new approach that optimally solves the robust path planning problem using an efficient network flow formulat ion. Our algorithm represents a significant departure from conventiona l shortest-path or graph search based methods; it not only handles env ironments with solid polygonal obstacles, but also generalizes to arbi trary cost maps that may arise in modeling incomplete or uncertain kno wledge of the environment. Simple extensions allow us to address highe r dimensional problem instances and minimum-surface computations; the latter is a result of independent interest. We use an efficient implem entation to exhibit optimal path-planning solutions for a variety of t est problems. The paper concludes with open issues and directions for future work.