Two algorithms for a reachability problem in one-dimensional space

Dajin Wang, Klaus Sutner

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)

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

Original languageEnglish
Pages (from-to)478-486
Number of pages9
JournalIEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans.
Volume28
Issue number4
DOIs
StatePublished - 1 Dec 1998

Fingerprint

Trajectories
Directed graphs
Motion planning

Keywords

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

Cite this

@article{5e632f0644634f4698eafc00d7136085,
title = "Two algorithms for a reachability problem in one-dimensional space",
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(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.",
keywords = "Algorithmic robotics, Motion planning, Obstacles, Path planning, Reachability, Space-time, Sweep-line algorithm",
author = "Dajin Wang and Klaus Sutner",
year = "1998",
month = "12",
day = "1",
doi = "10.1109/3468.686708",
language = "English",
volume = "28",
pages = "478--486",
journal = "IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans.",
issn = "1083-4427",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "4",

}

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

In: IEEE Transactions on Systems, Man, and Cybernetics Part A:Systems and Humans., Vol. 28, No. 4, 01.12.1998, p. 478-486.

Research output: Contribution to journalArticleResearchpeer-review

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

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 -