Movement planning in the presence of flows


Conference Paper

© Springer-Verlag Berlin Heidelberg 2001. This paper investigates the problem of time-optimum movement planning in d = 2, 3 dimensions for a point robot which has bounded control velocity through a set of n polygonal regions of given translational flow velocities. This intriguing geometric problem has immediate applications to macro-scale motion planning for ships, submarines and airplanes in the presence of significant flows of water or air. Also, it is a central motion planning problem for many of the mesoscale and micro-scale robots that recently have been constructed, that have environments with significant flows that affect their movement. In spite of these applications, there is very little literature on this problem, and prior work provided neither an upper bound on its computational complexity nor even a decision algorithm. It can easily be seen that optimum path for the d = 2 dimensional version of this problem can consist of at least an exponential number of distinct segments through flow regions. We provide the first known computational complexity hardness result for the d = 3 dimensional version of this problem; we show the problem is PSPACE hard. We give the first known decision algorithm for the d = 2 dimensional problem, but this decision algorithm has very high complexity. We also give the first known efficient approximation algorithms with bounded error.

Full Text

Duke Authors

Cited Authors

  • Reif, J; Sun, Z

Published Date

  • January 1, 2001

Published In

Volume / Issue

  • 2125 /

Start / End Page

  • 450 - 461

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

International Standard Book Number 10 (ISBN-10)

  • 3540424237

International Standard Book Number 13 (ISBN-13)

  • 9783540424239

Digital Object Identifier (DOI)

  • 10.1007/3-540-44634-6_41

Citation Source

  • Scopus