Paper Info
Title
Finding Combined L1 and Link Metric Shortest Paths in the Presence of Orthogonal Obstacles: A Heuristic Approach
Abstract
This paper presents new heuristic search algorithms for searching combined rectilinear (L-1) and link metric shortest paths in the presence of orthogonal obstacles. The Guided Minimum Detour (GMD) algorithm for L1 metric combines the best features of maze-running algorithms and line-search algorithms. The Line-by-Line Guided Minimum Detour (LGMD) algorithm for L1 metric is a modification of the GMD algorithm that improves on 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 shortest paths. The GMD and the LGMD algorithms can be implemented in O(in + 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 in terms of the number of bends, but also the combined L-1 metric and link metric shortest path in terms of the length and the number of bends.
Year
DOI
Venue
1999
10.1155/1999/37271
VLSI DESIGN
Keywords
DocType
Volume
L-1 and link metric shortest paths,maze-running algorithms,line-search algorithms
Journal
9
Issue
ISSN
Citations 
1
1065-514X
1
PageRank 
References 
Authors
0.36
0
3
Name
Order
Citations
PageRank
Joon Shik Lim1516.39
S.S. Iyengar22923381.93
Si-Qing Zheng335741.69