Knowledge base: Warsaw University of Technology

Settings and your account

Back

Scientific review of path planning methods for a mobile robot

Piotr Konowrocki

Abstract

The topic of this thesis is scientific review of path planning methods for mobile robot. A strong emphasis is placed on comparison of broad spectrum of methods based on the cost of generated path and computational complexity of individual algorithms. Thesis consists of three parts. The first one motivates necessity of looking through various path planning algorithms, as this problem shows up more often due to robotization of modern industry, as well as everyday life. Moreover, this part shows basic information about ways modern robots interact with environment, methods of modeling and representing environment in which robot works. This part also contains a strict definition of path planning problem. This part covers short characteristic of planning systems and their properties. The next part presents individual algorithms of path planning. Firstly, the graph methods, as it is the most popular group of path planning algorithms. Example of a classic A* algorithm shows impact of heuristic on paths length and computational complexity. There is also described Theta* algorithm, as a direct development of A* method for complete graphs, as well as the efficient algorithm of checking connectivity between two points on a maps. The next group of methods described in the thesis are probabilistic methods. Algorithms based on rapidly-exploring random trees are used as examples of these methods. The last group of described methods are so called nonlinear methods - a set of algorithms based on machine learning and broadly defined neural networks. Third, and the last part of this thesis is dedicated to studying individual methods and analysis of the results. Algorithms described in the previous part are compared in computational complexity and cost of generated paths
Diploma type
Engineer's / Bachelor of Science
Diploma type
Engineer's thesis
Author
Piotr Konowrocki (FPAE) Piotr Konowrocki,, Faculty of Power and Aeronautical Engineering (FPAE)
Title in Polish
Przegląd metod planowania ścieżki robota mobilnego
Supervisor
Andrzej Chmielniak (FPAE/IAAM) Andrzej Chmielniak,, The Institute of Aeronautics and Applied Mechanics (FPAE/IAAM)Faculty of Power and Aeronautical Engineering (FPAE)
Certifying unit
Faculty of Power and Aeronautical Engineering (FPAE)
Affiliation unit
The Institute of Aeronautics and Applied Mechanics (FPAE/IAAM)
Study subject / specialization
, Automatyka i Robotyka (Automation and Robotics)
Language
(pl) Polish
Status
Finished
Defense Date
11-02-2019
Issue date (year)
2019
Pages
52
Internal identifier
MEL; PD-4989
Reviewers
Marek Wojtyra (FPAE/IAAM) Marek Wojtyra,, The Institute of Aeronautics and Applied Mechanics (FPAE/IAAM)Faculty of Power and Aeronautical Engineering (FPAE) Andrzej Chmielniak (FPAE/IAAM) Andrzej Chmielniak,, The Institute of Aeronautics and Applied Mechanics (FPAE/IAAM)Faculty of Power and Aeronautical Engineering (FPAE)
Keywords in Polish
ścieżka, planowanie, heurystyka, A*, Theta*, RRT, iteracja wartości, komórkowe sieci neuronowe, sieci neuronowe
Keywords in English
path, pathfinding, planning, heuristic, A*, Theta*, RRT, value iteration, cellular neural network, neural network
Abstract in Polish
Tematem niniejszej pracy jest przegla˛d metod planowania s´ciez˙ki dla robotów mobilnych. Najwi ˛ekszy nacisk został poło˙zony na porównanie jak najszerszego przekroju metod pod wzgl ˛edem długo´sci generowanej ´scie˙zki oraz czasowej zło˙zono´sci obliczeniowej poszczególnych algorytmów. Praca składa si ˛e z trzech cz˛e´sci. W pierwszej z nich umotywowano zasadno´s´c rozpatrywania zagadnienia planowania s´ciez˙ki, jako problemu, który z powodu cia˛głej robotyzacji pojawia si ˛e coraz cz˛e´sciej zarówno we współczesnym przemy´sle jaki i ˙zyciu codziennym. Ponadto przedstawione podstawowe informacje na temat sposobów interakcji współczesnych robotów z otoczeniem, metod modelowania i reprezentacji otoczenia w którym pracuje robot. Został tak˙ze ´sci´sle zdefiniowany problem planowania ´scie˙zki w przestrzeni. Przedstawiona została te˙z krótka charakterystyka systemów planowania wraz z ich własno´sciami. Kolejna, zasadnicza cz˛e´s´c pracy po´swi˛econa jest przedstawieniu poszczególnych metod planowania. W pierwszej kolejnos´ci opisuje ona algorytmy grafowe, jako z˙e sa˛ to najpopularniejsze metody rozwia˛zywania problemu poszukiwania s´ciez˙ki. Na przykładzie klasycznego algorytmu A* przedstawiony jest wpływ heurystyki na długo´s´c ´scie˙zki oraz złoz˙onos´c´ obliczeniowa˛ metody. Opisany jest takz˙e algorytm Theta* jako bezpo- ´srednie rozwini˛ecie algorytmu A* na grafy pełne, wraz z przedstawieniem wydajnej metody sprawdzania widoczno´sci mi˛edzy dwoma punktami na mapie. Kolejnym opisywanym typem metod planowania sa˛ metody probabilistyczne. Jako przykład takich metod słuz˙a˛ algorytmy oparte o iteracyjne budowanie drzewa - RRT (Rapidly-exploring random tree) i RRT*. Ostatnia˛ z przedstawionych grup sa˛ tak zwane metody nieliniowe - zbiór algorytmów opartych na uczeniu maszynowym oraz szeroko poj˛etych sieciach neuronowych. Ostatnia, trzecia cz˛e´s´c pracy po´swi˛econa jest badaniu poszczególnych metod oraz analizie wyników. Przedstawione w poprzedniej cze˛s´ci pracy metody sa˛ porównywane pod wzgl ˛edem zło˙zono´sci obliczeniowej oraz kosztu generowanej ´scie˙zki
File
  • File: 1
    279138-Piotr_Konowrocki-23012019.pdf
Request a WCAG compliant version
Local fields
Identyfikator pracy APD: 31190

Uniform Resource Identifier
https://repo.pw.edu.pl/info/bachelor/WUT4fc701736f1c4d3bb590c8fd5bf8cd59/
URN
urn:pw-repo:WUT4fc701736f1c4d3bb590c8fd5bf8cd59

Confirmation
Are you sure?
Report incorrect data on this page