Skip to main content
Journal cover image

Movement planning in the presence of flows

Publication ,  Journal Article
Reif, JH; Sun, Z
Published in: Algorithmica (New York)
February 1, 2004

This paper investigates the problem of time-optimum movement planning in two and three 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 meso-scale and micro-scale robots that have been constructed recently, 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 an optimum path for the 2D 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 3D version of this problem; we show the problem is PSPACE hard. We give the first known decision algorithm for the 2D flow path problem, but this decision algorithm has very high computational complexity. We also give the first known efficient approximation algorithms with bounded error. © 2004 Springer-Verlag New York, Inc.

Duke Scholars

Published In

Algorithmica (New York)

DOI

ISSN

0178-4617

Publication Date

February 1, 2004

Volume

39

Issue

2

Start / End Page

127 / 153

Related Subject Headings

  • Computation Theory & Mathematics
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Reif, J. H., & Sun, Z. (2004). Movement planning in the presence of flows. Algorithmica (New York), 39(2), 127–153. https://doi.org/10.1007/s00453-003-1079-5
Reif, J. H., and Z. Sun. “Movement planning in the presence of flows.” Algorithmica (New York) 39, no. 2 (February 1, 2004): 127–53. https://doi.org/10.1007/s00453-003-1079-5.
Reif JH, Sun Z. Movement planning in the presence of flows. Algorithmica (New York). 2004 Feb 1;39(2):127–53.
Reif, J. H., and Z. Sun. “Movement planning in the presence of flows.” Algorithmica (New York), vol. 39, no. 2, Feb. 2004, pp. 127–53. Scopus, doi:10.1007/s00453-003-1079-5.
Reif JH, Sun Z. Movement planning in the presence of flows. Algorithmica (New York). 2004 Feb 1;39(2):127–153.
Journal cover image

Published In

Algorithmica (New York)

DOI

ISSN

0178-4617

Publication Date

February 1, 2004

Volume

39

Issue

2

Start / End Page

127 / 153

Related Subject Headings

  • Computation Theory & Mathematics