Non-crossing Rectilinear Shortest Minimum Bend Paths in the Presence of Rectilinear Obstacles
DOI:
https://doi.org/10.26636/jtit.2018.120417Keywords:
Floyd-Warshall algorithm, rectilinear non-crossing shortest paths, rectilinear obstaclesAbstract
The paper presents a new algorithm to determine the shortest, non-crossing, rectilinear paths in a twodimensional grid graph. The shortest paths are determined in a manner ensuring that they do not cross each other and bypass any obstacles present. Such shortest paths are applied in robotic chip design, suburban railway track layouts, routing traffic in wireless sensor networks, printed circuit board design routing, etc. When more than one equal length noncrossing path is present between the source and the destination, the proposed algorithm selects the path which has the least number of corners (bends) along the path. This feature makes the path more suitable for moving objects, such as unmanned vehicles. In the author’s scheme presented herein, the grid points are the vertices of the graph and the lines joining the grid points are the edges of the graph. The obstacles are represented by their boundary grid points. Once the graph is ready, an adjacency matrix is generated and the Floyd-Warshall all-pairs shortest path algorithm is used iteratively to identify the non-crossing shortest paths. To get the minimum number of bends in a path, we make a modification to the Floyd-Warshall algorithm, which is constitutes the main contribution of the author presented herein.
Downloads
References
[1] A. Madkour, W. G. Aref, F. U. Rehman, M. Abdur Rahman, and S. Basalamah, “A survey of shortest-path algorithms” [Online]. Available: https://arxiv.org/abs/1705.02044 (accessed: 6 July 2017).
View in Google Scholar
[2] S. Eriksson-Bique et al., “Geometric k-shortest paths”, in Proc. 26th Ann. ACM-SIAM Symp. Discrete Algorithms SODA’15, San Diego, CA, USA, 2015, pp. 1616–1625.
View in Google Scholar
[3] J. S. B. Mitchell, “Geometric shortest paths and network optimization”, in Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Amsterdam: Elsevier Science B.V., 1998, pp. 633–701.
View in Google Scholar
[4] N. S. P. Hyun, P. A. Vela, and E. I. Verriest, “A new framework for optimal path planning of rectangular robots using a weighted Lp norm”, IEEE Robotics and Automation Let., vol. 2, no. 3, pp. 1460–1465, 2017.
View in Google Scholar
[5] N. Qingbin, “Research on robot obstacle avoidance and path tracking under dynamically unknown environment”, in Proc. 2017 IEEE 2nd Adv. Inform. Technol., Electronic and Automation Control Conf. IAEAC, Chongqing, China, 2017, pp. 2607–2610.
View in Google Scholar
[6] C. D. Yang, O. Z. Lee, and C. K. Wong, “On bends and lengths of rectilinear paths: A graph-theoretic approach”, Internat. J. Comput. Geom. Appl., vol. 2, no. 1, pp. 61–74, 1992.
View in Google Scholar
[7] Y.-F. Wu, P. Widmayer, M. D. E. Schlag, and C. K. Wong, “Rectilinear shortest paths and minimum spanning trees in the presence of rectilinear obstacles”, IEEE Trans. Comput., vol. C-36, no. 3, pp. 321–331, 1987.
View in Google Scholar
[8] M. de Berg, M. van Kreveld, B. J. Nilsson, and M. H. Overmars, “Shortest path queries in rectilinear worlds”, Int. J. of Computat. Geom. & Applic., vol. 2, no. 3, pp. 287–309, 1992.
View in Google Scholar
[9] D. T. Lee and F. P. Preparata, “Euclidean shortest paths in the presence of rectilinear barriers”, Networks, vol. 14, no. 3, pp. 393–410, 1984.
View in Google Scholar
[10] E. M. Arkin et al., “The shortest path to a segment and quickest visibility queries”, in Proc. 31st Int. Symp. on Computat. Geometry SoCG, Eindhoven, The Netherlands, 2015, pp. 658–673.
View in Google Scholar
[11] K. L. Clarkson, S. Kapoor, and P. M. Vaidya, “Rectilinear shortest paths through polygonal obstacles in O(n log² n) time”, in Proc. 3rd Annual ACM Sympos. Comput. Geom., Waterloo, ON, Canada, 1987, pp. 251–257.
View in Google Scholar
[12] Z. Tarapata, “Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms”, Int. J. of Applied Mathem. and Computer Science, vol. 17, no. 1, pp. 269–287, 2007.
View in Google Scholar
[13] Y. Sun and M. X. Lang, “Bi-objective optimization for multi-modal transportation routing planning problem based on Pareto optimality”, J. Ind. Eng. Manag., vol. 8, no. 4, pp. 1195–1217, 2015.
View in Google Scholar
Downloads
Submitted
Published
Issue
Section
License
Copyright (c) 2018 Journal of Telecommunications and Information Technology
This work is licensed under a Creative Commons Attribution 4.0 International License.
