Non-crossing Rectilinear Shortest Minimum Bend Paths in the Presence of Rectilinear Obstacles

• Autorzy: Nagaraja S.

Identyfikatory

DOI

10.26636/jtit.2018.120417

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Floyd-Warshall algorithm; rectilinear non-crossing shortest paths; rectilinear obstacles

• Wydawca: Instytut Łączności - Państwowy Instytut Badawczy
• Czasopismo: Journal of Telecommunications and Information Technology
• Rocznik: 2018
• Tom: nr 3
• Strony: 82--91
• Opis fizyczny: Bibliogr. 13 poz., rys., tab.

Twórcy

autor

Nagaraja S.

• Department of Electronics & Communication Engineering, Rastreeya Vidyalaya College of Engineering, Mysuru Road, Bengaluru 560059, Karnataka, India

Bibliografia

• [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).
• [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 (doi: 10.1137/1.9781611973730.107).
• [3] J. S. B. Mitchell, „Geometric shortest paths and network optimization", in Handbook of Computational Geometry J.-R. Sack and J. Urrutia (ed.). Amsterdam: Elsevier Science B.V., 1998, pp. 633-701 (doi: 10.1016/B978-044482537-7/50016-4).
• [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 (doi: 10.1109/LRA.2017.2673858).
• [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 (doi: 10.1109/IAEAC.2017.8054496).
• [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. , no. 1, pp. 61-74, 1992 (doi: 10.1142/S0218195992000056).
• [7] Y. E. Wu, E. 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-33, 1987 (doi: 10.1109/TC.1987.1676904).
• [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 (doi: 10.1142/S0218195992000172).
• [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 (doi: 10.1002/net.3230140304).
• [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 (doi: 10.4230/LIPIcs.SOCG.2015.658).
• [11] K. L. Clarkson, S. Kapoor, and P. M. Vaidya, „Rectilinear shortest paths through polygonal obstacles in O(n(logn)2) time", in Proc. 3rd Annual ACM Sympos. Comput. Geom., Waterloo, ON, Canada, 1987, pp. 251-257 (doi: 10.1145/41958.41985).
• [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 (doi: 10.2478/v10006-007-0023-2).
• [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 (doi: 10.3926/jiem.1562).

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).