Volume 27 Issue 11-12 - Publication Date: 1 November 2008
Planning Time-Minimal Safe Paths Amidst Unpredictably Moving Obstacles
Jur van den Berg Department of Computer Science, University of North Carolina at Chapel Hill, Chapel Hill, NC, USA and Mark Overmars Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands
In this paper we discuss the problem of planning safe paths amidst unpredictably moving obstacles in the plane. Given the initial positions and the maximum speeds of the moving obstacles, which we assume are disk-shaped, the regions that are possibly not collision-free are disks that grow over time. We present an approach to compute the time-minimal path between two points in the plane that avoids these growing disks. The generated paths are thus guaranteed to be collision-free with respect to the moving obstacles while being executed. We present an algorithm that runs in O(n3 log n) time (n being the number of obstacles) for the case where the moving obstacles have the same maximum speed, and a fast implementation for the general case that is capable of planning paths amidst many growing disks within milliseconds.
Return to Contents