Paper:

# The Global Shortest Path Visualization Approach with Obstructions

## Guan-Qiang Dong, Zong-Xiao Yang, Lei Song, Kun Ye, and Gen-Sheng Li

Institute of Systems Science and Engineering, Henan Engineering Laboratory of Wind Power Systems,

Henan University of Science and Technology

Luoyang 471003, China

Shortest path experiment device

The avoidance obstacle path planning problem is stated in an obstacle environment. The minimum Steiner tree theory is the basis of the global shortest path. It is one of the classic NP-hard problem in nonlinear combinatorial optimization. A visualization experiment approach has been used to find Steiner point and system’s shortest path is called Steiner minimum tree. However, obstacles must be considered in some problems. An Obstacle Avoiding Steiner Minimal Tree (OASMT) connects some points and avoids running through any obstacle when constructing a tree with a minimal total length. We used a geometry experiment approach (GEA) to solve OASMT by using the visualization experiment device discussed below. A GEA for some systems with obstacles is used to receive approximate optimizing results. We proved the validity of the GEA for the OASMT by solving problems in which the global shortest path is obtained successfully by using the GEA.

*J. Robot. Mechatron.*, Vol.27, No.5, pp. 579-585, 2015.

- [1] F. K. Hwang, D. S. Richards, and P. Winter, “The Steiner tree problem,” Annals of Discrete Mathematics, Vol.53, Elsevier Science Publishers, 1992.
- [2] X. Y. Li, G. Calinescu, and P. J. Wan, “Distributed construction of a planar spanner and routing for ad hoc wireless networks,” The 21
^{st}Annual Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM), 2002. - [3] C. Sertac and C. F. Bazlamaçcci, “A distributed heuristic algorithm for the rectilinear steiner minimal tree problem,” Institute of Electrical and Electronics Engineers Inc Vol.27, pp. 2083-2087, 2008.
- [4] M. Fampa and N. Maculan, “Using a conic formulation for finding Steiner minimal trees,” Kluwer Academic Publishers, 2004.
- [5] M. Karpinski and A. Zelikovsky, “New Approximation Algorithms for the Steiner Tree Problems,” J. of Combinatorial Optimization, Vol.1, pp. 47-65, 1997.
- [6] D. M. Warme, P. Winter, and M. Zachariasen, “Exact Algorithms for Plane Steiner Tree Problems: A Computational Study,” Technical Report DIKU-TR-98/11, 1998.
- [7] L. Luc, V. Sacha, and Z. Nicolasdesign, “An ant algorithm for the steiner tree problem in graphs,” EvoWorkshops 2007: EvoCOMNET, EvoFIN, EvoIASP, EvoINTERACTION, EvoMUSART, EvoSTOC and EvoTRANSLOG, pp. 42-51, 2007.
- [8] E. N. Gilbert and H. O. Pollak, “Steiner minimal trees,” SIAM J. Appl. Math., Vol.16, pp. 323-345, 1968.
- [9] Z. M. Fu and Z. P. Chen, “Beauty of bubble,” Science Development Monthly, Vol.29, No.11, pp. 788-796, 1990 (in Chinese).
- [10] Z. Shen, C. Chu, and Y. Li, “Efficient rectilinear Steiner tree construction with rectilinear blockages,” Proc. ICCD, pp. 38-44, 2005.
- [11] Z. X. Yang, Y. P. Gao, C. Y. Cheng et al., “A visualization approach for the Steiner minimal tree problem,” Systems engineering theory and practice, Vol.28, No.7, pp. 173-178, 2008 (in Chinese).
- [12] Z. X. Yang, “Visualization device of system shortest path programming,” Chinese Patent: ZL2006201301488, 2007.
- [13] Z. X. Yang, X. Y. Jia, J. Y. Hao, and Y. P. Gao, “Geometry-experiment algorithm for Steiner minimal tree problem,” J. of Applied Mathematics, Article ID 367107, 2013.
- [14] Y. P. Gao, B. B. Yang, Z. X. Yang et al., “Visualization Experimental Approaches for Power Grid Planning,” Power System Technology, Vol.33, No.2, pp. 51-55, 2009 (in Chinese).
- [15] Z. Feng, Y. Hu, T. Jing, X. Hong, X. Hu, and G. Yan, “An
*O(nlogn)*algorithm for obstacle-avoiding routing tree construction in the lambda-geometry plane,” Proc. ISPD, pp. 48-55, 2006. - [16] Y. Hu, Z. Feng, T. Jing, X. Hong, Y. Yang, G. Yu, X. Hu, and G. Yan, “FORst: a 3-step heuristic for obstacle-avoiding rectilinear Steiner minimal tree construction,” J. of Information and Computational Science, pp. 107-116, 2004.
- [17] Y. Shi, T. Jing, L. He, and Z. Feng, “CDCTree: novel obstacle-avoiding routing tree construction based on current driven circuit model,” Proc. ASP-DAC, pp. 630-635, 2006.
- [18] G. Eason, B. Noble, and I. N. Sneddon, “On certain integrals of Lipschitz-Hankel type involving products of Bessel functions,” Phil. Trans. Roy. Soc. London, Vol.A247, pp. 529-551, 1955.
- [19] J. C. Maxwell, “A Treatise on Electricity and Magnetism,” 3
^{rd}ed., Vol.2, pp. 68-73, Oxford: Clarendon, 1892. - [20] I. S. Jacobs and C. P. Bean, “Fine particles, thin films and exchange anisotropy,” Magnetism, Vol.3, pp. 271-350, New York: Academic, 1963.
- [21] L. Y. Wu and J. H. He, “Explosion-proof textile with hierarchical Steiner tree structure,” Thermal Science, Vol.16, No.2, pp. 343-344, 2012.
- [22] L. Y. Wu and J. H. He, “Study on the stability of steiner tree structure of explosion-proof textiles,” Mathematical and Computational Applications, Vol.15, No.5, pp. 936-939, 2010.
- [23] Y. Yorozu, M. Hirano. K. Oka, and Y. Tagawa, “Electron spectroscopy studies on magneto-optical media and plastic substrate interface,” IEEE Transl. J. Magn. Japan, Vol.2, pp. 740-741, 1987 (Digests 9
^{th}Annual Conf. Magnetics Japan, p. 301, 1982). - [24] M. Young, “The Technical Writer’s Handbook,” Mill Valley, CA: University Science, 1989.