Top > JRM > The Global Shortest Path Visualization Approach with Obstructi ...

single-rb.php

JRM Vol.27 No.5 pp. 579-585
doi: 10.20965/jrm.2015.p0579
(2015)

Paper:

Views over last 60 days: 1,397

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

Received:
April 28, 2015
Accepted:
August 31, 2015
Published:
October 20, 2015
Creative Commons License
Keywords:
NP hard problem, geometry-experiment approach (GEA), steiner minimal tree, obstacle-avoiding Steiner minimal tree (OASMT)
Abstract

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.
Cite this article as:
G. Dong, Z. Yang, L. Song, K. Ye, and G. Li, “The Global Shortest Path Visualization Approach with Obstructions,” J. Robot. Mechatron., Vol.27 No.5, pp. 579-585, 2015.
Data files:
References
  1. [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. [2] X. Y. Li, G. Calinescu, and P. J. Wan, “Distributed construction of a planar spanner and routing for ad hoc wireless networks,” The 21st Annual Joint Conf. of the IEEE Computer and Communications Societies (INFOCOM), 2002.
  3. [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. [4] M. Fampa and N. Maculan, “Using a conic formulation for finding Steiner minimal trees,” Kluwer Academic Publishers, 2004.
  5. [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. [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. [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. [8] E. N. Gilbert and H. O. Pollak, “Steiner minimal trees,” SIAM J. Appl. Math., Vol.16, pp. 323-345, 1968.
  9. [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. [10] Z. Shen, C. Chu, and Y. Li, “Efficient rectilinear Steiner tree construction with rectilinear blockages,” Proc. ICCD, pp. 38-44, 2005.
  11. [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. [12] Z. X. Yang, “Visualization device of system shortest path programming,” Chinese Patent: ZL2006201301488, 2007.
  13. [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. [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. [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. [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. [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. [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. [19] J. C. Maxwell, “A Treatise on Electricity and Magnetism,” 3rd ed., Vol.2, pp. 68-73, Oxford: Clarendon, 1892.
  20. [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. [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. [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. [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 9th Annual Conf. Magnetics Japan, p. 301, 1982).
  24. [24] M. Young, “The Technical Writer’s Handbook,” Mill Valley, CA: University Science, 1989.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Mar. 19, 2025