Two algorithms are proposed to solve a reachability problem among time-dependent obstacles in one-dimensional (1-D) space. In the first approach, the motion planning problem is reduced to a path existence problem in a directed graph. The algorithm is very simple, with running time O(n2), where n is the complexity of obstacles in space-time. The second algorithm uses a sweep-line technique and has running time O(n log2 n). Besides, the latter algorithm can be easily modified to compute a collision-free trajectory, if such trajectories exist.
|Number of pages||9|
|Journal||IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans.|
|State||Published - 1 Dec 1998|
- Algorithmic robotics
- Motion planning
- Path planning
- Sweep-line algorithm