Maximum thick paths in static and dynamic environments

ABSTRACT

We consider the problem of finding a maximum number of disjoint paths for unit disks moving amidst static or dynamic obstacles. For the static case we give efficient exact algorithms, based on adapting the "continuous uppermost path" paradigm. As a by-product, we establish a continuous analogue of Menger's Theorem. (In this extended abstract we only state these results.)

Next we study the dynamic problem in which the obstacles may move, appear and disappear, and otherwise change with time in a known manner; in addition, the disks are required to enter/exit the domain during prescribed time intervals. We observe that (unless P=NP), for any α,β > 0, one cannot decide in polynomial time whether there exist [αΚ] paths for disks of radius βR, where K is the maximum number of paths for radius-R disks. The problem is hard even if the obstacles are static, and only the entry/exit time intervals are specified for the disks. This motivates studying "dual" approximations, compromising on the radius of the disks and on the maximum speed of motion.

Our main result is a pseudopolynomial-time dual-approximation algorithm: if K unit disks, each with unit bound on the speed, may be routed through an environment, our algorithm finds (at least) K paths for disks of radius Ω(1) moving with speed O(1). The algorithm computes a maxflow with "forbidden pairs" in an "adaptive" grid, laid out in space-time. Although (as we show) in general finding even an approximation to the maxflow with forbidden pairs is not possible (unless P=NP), a careful choice of time discetization and a non-uniform grid of "way-points" allows us to give provable approximation guarantees on the quality of the solution produced by the algorithm. Our algorithm extends to higher dimensions and to finding paths for translational motion of arbitrary-shape objects.

REFERENCES

• 1: N. Aggarwal and K. Fujimura. Motion planning amidst planar moving obstacles. In Proc. International Conference on Robotics and Automation, pages 2153--2158, 1994.
• 2: John Canny , Ashutosh Rege , John Reif, An exact algorithm for kinodynamic planning in the plane, Discrete & Computational Geometry, v.6 n.5, p.461-484, 1991 [doi>10.1007/BF02574702]
• 3: John Canny , John Reif, New lower bound techniques for robot motion planning problems, Proceedings of the 28th Annual Symposium on Foundations of Computer Science (sfcs 1987), p.49-60, October 12-14, 1987 [doi>10.1109/SFCS.1987.42]
• 4: Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 5: K. Fujimura. Motion planning amid transient obstacles. The International Journal of Robotics Research, 13(5):395--407, 1994.
• 6: Kikuo Fujimura, Time-minimal paths amidst moving obstacles in three dimensions, Theoretical Computer Science, v.270 n.1-2, p.421-440, January [doi>10.1016/S0304-3975(00)00408-4]
• 7: K. Fujimura and H. Samet. Planning a time-minimal motion among moving obstacles. Algorithmica, 10(1):41--63, 1993.
• 8: J. Krozel, J. S. B. Mitchell, V. Polishchuk, and J. Prete. Capacity estimation for level flight with convective weather constraints. Air Traffic Control Quarterly, 15(3):209--238, 2007.
• 9: J. Krozel, J. S. B. Mitchell, V. Polishchuk, and J. Prete. Airspace capacity estimation with convective weather constraints. In Proc. AIAA Guidance, Navigation, and Control Conference, Aug 2007.
• 10: J. Krozel, S. Penny, J. Prete, and J. S. B. Mitchell. Comparison of algorithms for synthesizing weather avoidance routes in transition airspace. In Proc. AIAA Guidance, Navigation and Control Conference, Aug 2004.
• 11: Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
• 12: Zexiang Li , J. F. Canny, Nonholonomic Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1992
• 13: Joseph S. B. Mitchell, On maximum flows in polyhedral domains, Journal of Computer and System Sciences, v.40 n.1, p.88-123, February 1990 [doi>10.1016/0022-0000(90)90020-L]
• 14: Joseph S. B. Mitchell, Shortest paths and networks, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 15: Valentin Polishchuk , Joseph S.B. Mitchell, Thick non-crossing paths and minimum-cost flows in polygonal domains, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247079]
• 16: J. S. B. Mitchell, V. Polishchuk, and J. Krozel. Airspace throughput analysis considering stochastic weather. In Proc. AIAA Guidance, Navigation, and Control Conference, Aug 2006.
• 17: D. Nieuwenhuisen, J. P. van den Berg, and M. H. Overmars. Efficient path planning in changing environments. In Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems -- IROS'07, 2007.
• 18: V. Polishchuk. Thick Non-Crossing Paths and Minimum-Cost Continuous Flows in Geometric Domains. PhD thesis, Stony Brook University, Aug 2007.
• 19: J. Prete. Aircraft Routing in the Presence of Hazardous Weather. PhD thesis, Stony Brook University, Aug 2007.
• 20: J. Prete and J. S. B. Mitchell. Safe routing of multiple aircraft flows in the presence of time-varying weather data. In Proc. AIAA Guidance, Navigation and Control Conference, Aug 2004.
• 21: John Reif , Micha Sharir, Motion planning in the presence of moving obstacles, Journal of the ACM (JACM), v.41 n.4, p.764-790, July 1994 [doi>10.1145/179812.179911]
• 22: G. Strang. Maximal flow through a domain. Mathematical Programming, 26:123--143, 1983.
• 23: J. van den Berg. Path Planning in Dynamic Environments. PhD thesis, Utrecht University, 2007.
• 24: J. P. van den Berg, D. Ferguson, and J. Kuffner. Anytime path planning and replanning in dynamic environments. In Proc. International Conference on Robotics and Automation, pages 2366--2371, 2006.
• 25: J. P. van den Berg, D. Nieuwenhuisen, L. Jaillet, and M. H. Overmars. Creating robust roadmaps for motion planning in changing environments. In Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2415--2421, 2005.
• 26: J. P. van den Berg and M. H. Overmars. Prioritized motion planning for multiple robots. In Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 2217--2222, 2005.
• 27: J. P. van den Berg and M. H. Overmars. Roadmap-based motion planning in dynamic environments. IEEE Transactions on Robotics, 21(5):885--897, 2005.
• 28: J. P. van den Berg and M. H. Overmars. Planning the shortest safe path amidst unpredictably moving obstacles. In Proc. Workshop on Algorithmic Foundations of Robotics, 2006.
• 29: J. P. van den Berg and M. H. Overmars. Kinodynamic motion planning on roadmaps in dynamic environments. In Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems, 2007.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms

Keywords:
approximation algorithms, motion planning