Finding Rectilinear ( L1 ) , Link Metric , and Combined Shortest Paths with an Intelligent Search Method


The Transactions of the Korea Information Processing Society (1994 ~ 2000), Vol. 3, No. 1, pp. 43-54, Jan. 1996
10.3745/KIPSTE.1996.3.1.43,   PDF Download:

Abstract

This paper presents new heuristic search algorithms for searching rectilinear(L1), link metric, and combined shortest paths in the presence of orthogonal obstacles. The GMD(Guided Minimum Detour) algorithm combines the best features of maze-running algorithms and line-search algorithms. The LGMD(Line-by-Line Guided Minimum Detour) algorithm is a modification of the GMD algorithm that improves efficiency using line-by-line extensions. Our GMD and LGMD algorithms always find a rectilinear shortest path using the guided A* search method without constructing a connection graph that contains a shortest path. The GMD and the LGMD algorithms can be implemented in O(m - e log e N log N)and O(e log e N log N) time, respectively, and O(e N) space, where m is the total number of searched nodes, e is the number of boundary sides of obstacles, and N is the total number of searched line segments. Based on the LGMD algorithm, we consider not only the problems of finding a link metric shortest path is terms of the number of bends, but also the combined L1 metric and link metric shortest path in terms of the length and the number of bends.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
L. J. Shik, "Finding Rectilinear ( L1 ) , Link Metric , and Combined Shortest Paths with an Intelligent Search Method," The Transactions of the Korea Information Processing Society (1994 ~ 2000), vol. 3, no. 1, pp. 43-54, 1996. DOI: 10.3745/KIPSTE.1996.3.1.43.

[ACM Style]
Lim Joon Shik. 1996. Finding Rectilinear ( L1 ) , Link Metric , and Combined Shortest Paths with an Intelligent Search Method. The Transactions of the Korea Information Processing Society (1994 ~ 2000), 3, 1, (1996), 43-54. DOI: 10.3745/KIPSTE.1996.3.1.43.