Finding combined L sub(1) and link metric shortest paths in the presence of orthogonal obstacles: A heuristic approach

• Published in: VLSI design (Yverdon, Switzerland) Switzerland), 1999-01, Vol.9 (1), p.91-104
• Main Authors: Lim, Joon Shik, Iyengar, S Sitharama, Zheng, Si-Qing
• Format: Article
• Language: English
• ISSN: 1065-514X

This paper presents new heuristic search algorithms for searching combined rectilinear (L sub(1)) and link metric shortest paths in the presence of orthogonal obstacles. The Guided Minimum Detour (GMD) algorithm for L sub(1) metric combines the best features of maze-running algorithms and line-search algorithms. The Line-by-Line Guided Minimum Detour (LGMD) algorithm for L sub(1) 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(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 in terms of the number of bends, but also the combined L sub(1) metric and link metric shortest path in terms of the length and the number of bends.