Journal
INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH
Volume 27, Issue 11-12, Pages 1274-1294Publisher
SAGE PUBLICATIONS LTD
DOI: 10.1177/0278364908097581
Keywords
Motion planning; moving obstacles; shortest paths
Categories
Ask authors/readers for more resources
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(n(3) 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available