### Abstract

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(n^{2}), where n is the complexity of obstacles in space-time. The second algorithm uses a sweep-line technique and has running time O(n log_{2} n). Besides, the latter algorithm can be easily modified to compute a collision-free trajectory, if such trajectories exist.

Original language | English |
---|---|

Pages (from-to) | 478-486 |

Number of pages | 9 |

Journal | IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans. |

Volume | 28 |

Issue number | 4 |

DOIs | |

State | Published - 1 Dec 1998 |

### Fingerprint

### Keywords

- Algorithmic robotics
- Motion planning
- Obstacles
- Path planning
- Reachability
- Space-time
- Sweep-line algorithm