Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: algorytm k najkrótszych ścieżek

Sortuj według:

Ogranicz wyniki do:

An exact geometry-based algorithm for path planning

Jafarzadeh H., Fleming C. H.

International Journal of Applied Mathematics and Computer Science

2018

Vol. 28, no. 3

493--504

A novel, exact algorithm is presented to solve the path planning problem that involves finding the shortest collision-free path from a start to a goal point in a two-dimensional environment containing convex and non-convex obstacles. The proposed algorithm, which is called the shortest possible path (SPP) algorithm, constructs a network of lines connecting the vertices of the obstacles and the locations of the start and goal points which is smaller than the network generated by the visibility graph. Then it finds the shortest path from start to goal point within this network. The SPP algorithm generates a safe, smooth and obstacle-free path that has a desired distance from each obstacle. This algorithm is designed for environments that are populated sparsely with convex and nonconvex polygonal obstacles. It has the capability of eliminating some of the polygons that do not play any role in constructing the optimal path. It is proven that the SPP algorithm can find the optimal path in O(nn’2) time, where n is the number of vertices of all polygons and n’ is the number of vertices that are considered in constructing the path network (n’ ≤ n). The performance of the algorithm is evaluated relative to three major classes of algorithms: heuristic, probabilistic, and classic. Different benchmark scenarios are used to evaluate the performance of the algorithm relative to the first two classes of algorithms: GAMOPP (genetic algorithm for multi-objective path planning), a representative heuristic algorithm, as well as RRT (rapidly-exploring random tree) and PRM (probabilistic road map), two well-known probabilistic algorithms. Time complexity is known for classic algorithms, so the presented algorithm is compared analytically.

Recovery using precalculated paths based routing in ATM networks

Orincsay D., Jósa B.G., Kosa D., Tamasi L.

Studia Informatica

2003

Vol. 24, nr 2A

119-128

The ATM technology serves as basis for many communication networks. The generally applied PNNI protocol enables to use sophisticated traffic engineering techniques. A progressive approach is such a routing strategy that applies precalculated paths in order minimize the reaction time for a new call request. As an advanced technique, more precalculated paths can be stored for each destination in every swith, which increase the possibility of the successful cal setup. Generally , the well-known K shortest path algorithm is used for this purpose that calculates the K cheapest paths based on an appropriate cost function. Although this method performs well in normal operation, it does not ensure that there is a bypass path among the stored ones when a network element fails along the currently used path. In this study we proposed a new path calculation concept based on algorithm of Edmonds and Karp, aiming at reducing the restoration time in case of failure. We investigate the performance of the novel method through simulations.

Technologia ATM służy jako podstawa wielu sieci komunikacyjnych. Stosowany w niej najczęściej protokół PNNI pozwala na wykorzystanie złożonych technik inżynierii ruchu. Coraz częściej stosuje się strategię wyboru drogi wykorzystującą wcześniejsze wyliczanie ścieżek, w celu zmniejszenia czasu odpowiedzi na żądanie nawiązania nowego połączenia. Rozwój techniki pozwala na zapamiętywanie w każdym węźle coraz większej liczby takich obliczonych uprzednio ścieżek, co zwiększa prawdopodobieństwo ich wykorzystania. Do ich obliczenia stosuje się dobrze znany algorytm K najkrótszych ścieżek, wykorzystujący założoną funkcję kosztów. Opisane podejście działa dobrze przy normalnej pracy sieci, nie pozwala jednak znaleźć nowych, uzupełniających ścieżek dla przełączenia ruchu, gdy zawodzi jeden z elementów aktualnie wykorzystywanej ścieżki. Niniejszy artykuł proponuje nową metodę obliczania ścieżek, opartą na algorytmie Edmondsa i Karpa, pozwalającą na zmniejszenie czasu nawiązywania nowego połączenia po upadku pracującej ścieżki. Przydatność metody jest badana za pomocą modeli symulacyjnych.