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

This paper presents new heuristic search algorithms for searching combined rectilinear (L-1) and link metric shortest paths in the presence of orthogo nal obstacles. The Guided Minimum Detour (GMD) algorithm for L1 metric comb ines the best features of maze-running algorithms and line-search algorithm s. 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 conn ection 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) ti me, respectively, and O(e + N) space, where m is the total number of search ed nodes, e is the number of boundary sides of obstacles, and N is the tota l number of searched line segments. Based on the LGMD algorithm, we conside r 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 short est path in terms of the length and the number of bends.