Wyniki wyszukiwania - BazTech

1

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

EN

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.

2

Heurystyczna metoda poszukiwania bezkolizyjnej ścieżki robota mobilnego

Skrzypczyk K.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2001

|

z. 133

143-159

PL

Przedstawiona praca porusza problem planowania ścieżki robota mobilnego w środowisku pomieszczeń zamkniętych, bazujący na geometrycznej reprezentacji otoczenia. Przedstawiono algorytm wyznaczania bezkolizyjnej ścieżki, wykorzystujący ideę dekompozycji przestrzeni. Główny nacisk położono na heurystyczne metody wyznaczania segmentów ścieżki zbliżającej robot do zadanego punktu.

EN

Path planning problem for a mobile robot operating in a human-made environment is considered in this paper. Collision free path search algorithm based on space decomposition method is described. Heuristic methods of goal approaching are discussed.

3

Planowanie ścieżki bezkolizyjnej dla robota mobilnego z zastosowaniem zmodyfikowanej transformaty odległości.

Kreczmer B.

Prace Naukowe Instytutu Cybernetyki Technicznej Politechniki Wrocławskiej. Konferencje

|

1998

|

Vol. 98, nr 44

283-290

PL

W referacie przedstawiono modyfikację transformaty odległości. Wykorzystywana ona jest do wyznaczania heurystycznej oceny kosztu osiągnięcia stanu docelowego przy planowaniu ścieżki bezkolizyjnej dla robota z ograniczonym kątem skrętu. Planowanie ścieżki zrealizowane jest w oparciu o dyskretyzację przestrzeni stanów robota i zbiór elementarnych przemieszczeń przeprowadzających robota w poszczególne stany. Wspomniana modyfikacja umożliwia bardziej wiarygodną ocenę kosztu osiągnięcia celu i w efekcie końcowym bardziej pożądany kształt ścieżki, co zademonstrowane jest na przedstawionych przykładach

EN

The paper presents a modified distance transform. This transform is applied to determine heuristic evaluation of a cost which is needed to reach the goal state. The evaluation is used in a method of path planning for a car-like robot. A collision-free path is planned by applying discretization of robot state space and a set of elementary movements. The modified distance transform allows to obtain more reliable evaluation and finally better paths which are presented by examples in the paper.