Advanced search ?

Object

Download

Title: Non-crossing Rectilinear Shortest Minimum Bend Paths in the Presence of Rectilinear Obstacles, Journal of Telecommunications and Information Technology, 2018, nr 3

Creator:

Nagaraja, Shylashree

Date:

2018, nr 3

Resource Type:

artykuł

Description:

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.

Publisher:

Instytut Łączności - Państwowy Instytut Badawczy

Format:

application/pdf

Resource Identifier:

ISSN 1509-4553, on-line: ISSN 1899-8852 ; oai:bc.itl.waw.pl:2045

Source:

Journal of Telecommunications and Information Technology

Language:

ang

Rights Management:

Biblioteka Naukowa Instytutu Łączności

Subject and keywords:

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

Object collections:

Last modified:

Apr 15, 2019

In our library since:

Oct 29, 2018

Number of object content hits:

53

All available object's versions:

https://bc.itl.waw.pl/publication/2329

Show description in RDF format:

RDF

Show description in OAI-PMH format:

OAI-PMH

Edition name Date
Nagaraja Shylashree, Non-crossing Rectilinear Shortest Minimum Bend Paths in the Presence of Rectilinear Obstacles, Journal of Telecommunications and Information Technology, 2018, nr 3 Apr 15, 2019
×

Citation

Citation style:

Contact details

Address

Instytut Łączności – Państwowy Instytut Badawczy ul. Szachowa 1 04-894 Warszawa

Phone

(+48) 5128 696

E-Mail

biblioteka@il-pib.pl

Visit us!

This page uses 'cookies'. More information