Mobile Robot Navigation (2008)
Gene Eu Jan, Ki-Yin Chang, and
"Optimal Path Planning for Mobile Robot Navigation",
IEEE/ASME Transactions on Mechatronics, Vol. 13, No. 4, pp. 451-460, 2008.
Some optimal path planning algorithms for navigatingmobile
rectangular robot among obstacles and weighted regions
are presented. The approach is based on a higher geometry maze
routing algorithm. Starting from a top view of a workspace with
obstacles, the so-called free workspace is first obtained by virtually
expanding the obstacles in the image. After that, an 8-geomerty
maze routing algorithm is applied to obtain an optimal collisionfree
path with linear time and space complexities. The proposed
methods cannot only search an optimal path among various terrains
but also find an optimal path for the 2-D piano mover’s
problem with 3 DOF. Furthermore, the algorithm can be easily extended
to the dynamic collision avoidance problem among multiple
autonomous robots or path planning in the 3-D space.
Ki-Yin Chang, Gene Eu Jan, Chien-Min Su, and
"Optimal Interceptions on
Journal of Navigation, Vol. 61, pp. 31-43, 2008.
This article presents efficient and practical methods for path planning of optimal interceptions
on two-dimensional grids with obstacles, such as raster charts or non-distorted digital
maps. The proposed methods search for optimal paths from sources to multiple movingtargets
by a novel higher geometry wave propagation scheme in the grids, instead of the
traditional vector scheme in the graphs. By introducing a time-matching scheme, the optimal
interception paths from sources to all the moving-targets are obtained among the combinations
with linear time and space complexities. Two optimal path planning methods for
multiple one-to-one interceptions, the MIN-MAX and MIN-AVG, are applied to emulate
the real routing.
Multiterminal Nets (2005)
Gene Eu Jan, Ki-Yin Chang, Su Gao, and
"A 4-Geometry Maze Router and Its
Application on Multiterminal Nets",
ACM Transactions on Design Automation of Electronic Systems, Vol. 10, No. 1, pp. 116-135, 2005.
The maze routing problem is to find an optimal path between a given pair of cells on a grid plane.
Lee’s algorithm and its variants, probably the most widely used maze routing method, fails to
work in the 4-geometry of the grid plane. Our algorithm solves this problem by using a suitable
data structure for uniform wave propagation in the 4-geometry, 8-geometry, etc. The algorithm
guarantees finding an optimal path if it exists and has linear time and space complexities.
Next, to solve the obstacle-avoiding rectilinear and 4-geometry Steiner tree problems, a heuristic
algorithm is presented. The algorithm utilizes a cost accumulation scheme based on the maze
router to determine the Torricelli vertices (points) for improving the quality of multiterminal nets.
Our experimental results show that the algorithm works well in practice. Furthermore, using the
4-geometry router, path lengths can be significantly reduced up to 12\% compared to those in the
Collision Avoidance (2003)
Ki-Yin Chang, Gene Eu Jan, and
"A Method for Searching Optimal
Routes with Collision Avoidance on
Journal of Navigation, Vol. 56, pp. 371-384, 2003.
Collision avoidance is an intensive discussion issue for navigation safety. This article introduces
a new routing algorithm for finding optimal routes with collision detection and
avoidance on raster charts or planes. After the required data structure of the raster chart is
initialized, the maze routing algorithm is applied to obtain the particular route of each ship.
Those ships that have potential to collide will be detected by simulating the particular routes
with ship domains. The collision avoidance scheme can be achieved by using the collision area
marking method with collision avoidance rules at sea. The algorithm has linear time and
space complexities, and is sufficiently fast to perform real-time routing on the raster charts.
Created April 22, 2015.
Written in HTML 4.01 and CSS 2.1 using vi.
Last updated August 25, 2015.