### 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

### Cite this

}

*IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans.*, vol. 28, no. 4, pp. 478-486. https://doi.org/10.1109/3468.686708

**Two algorithms for a reachability problem in one-dimensional space.** / Wang, Dajin; Sutner, Klaus.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Two algorithms for a reachability problem in one-dimensional space

AU - Wang, Dajin

AU - Sutner, Klaus

PY - 1998/12/1

Y1 - 1998/12/1

N2 - 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.

AB - 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.

KW - Algorithmic robotics

KW - Motion planning

KW - Obstacles

KW - Path planning

KW - Reachability

KW - Space-time

KW - Sweep-line algorithm

UR - http://www.scopus.com/inward/record.url?scp=0032121755&partnerID=8YFLogxK

U2 - 10.1109/3468.686708

DO - 10.1109/3468.686708

M3 - Article

AN - SCOPUS:0032121755

VL - 28

SP - 478

EP - 486

JO - IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans.

JF - IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans.

SN - 1083-4427

IS - 4

ER -