izpis_h1_title_alt

Optimizirano iskanje poti z RRT-metodami in generiranje gladke poti
ID Kotnik, Klemen (Author), ID Klančar, Gregor (Mentor) More about this mentor... This link opens in a new window

.pdfPDF - Presentation file, Download (3,77 MB)
MD5: FE847F42A97D11252A3677DB4C73C873

Abstract
Problematika določevanja optimalne ali kvalitetne poti v prostoru je zahtevna naloga. Ima veliko možnih praktičnih aplikacij, pri čemer je pogosto zahtevan hiter izračun. Računska kompleksnost narašča v odvisnosti od povečevanja števila parametrov, njihovih vrednosti in zahtevnostjo postavitve ovir. Magistrsko delo temelji na uporabi RRT-metod z lastnostjo hitre predstavitve neoptimalnega gibanja po prostoru v obliki grafa prehajanja stanj. Znotraj katerega se določi najboljša pot z uporabo vzvratne metode iskanja poti. Z nadaljnjim reduciranjem odvečnih zavojev oziroma delov poti se pridobljeni poti izboljša kvaliteta. Z Bezierjevimi polinomi se v obliki zvezno gladke poti predstavi reducirana pot za možnost takojšnega sledenja. Izkoristi se hitro določanje neoptimalnega grafa prehajanja stanj z RRT-metodami, z nadaljnjo obdelavo se izboljša pomanjkljivost hitre gradnje s končnim produktom kvalitetne hitro pridobljene poti. V luči pohitritve gradnje RRT-dreves so implementirani nadgrajeni postopki posameznih korakov. S predhodnim definiranjem konfiguracijskega prostora vplivamo na hitrejše preverjanje veljavnosti točk oziroma trka z ovirami, na možnost uporabe iskanja najbližje točke le znotraj želenega dela okolice z namenom zmanjšanja števila preverjenih točk ter na upoštevanje oblike ovire pri ponovnem določanju nove točke, če prvotna točka ali njena povezava leži na oviri. Slednje omogoča učinkovitejše širjenje drevesa ob oviri ali v ozkih prehodih. Eksperimenti potrjujejo učinkovitost uporabe preprostih RRT-metod, brez naknadnega povezovanja bližnjih stanj, v kombinaciji z nadaljnjo obdelavo poti, kar omogoča hiter izračun kvalitetne poti.

Language:Slovenian
Keywords:RRT, ciljno usmerjeni RRT, povezovalni RRT, graf prehajanja stanj, vzvratno iskanje, reduciranje poti, Bezierjevi polinomi, časovne nadgradnje
Work type:Master's thesis/paper
Organization:FE - Faculty of Electrical Engineering
Year:2020
PID:20.500.12556/RUL-121196 This link opens in a new window
Publication date in RUL:01.10.2020
Views:1043
Downloads:170
Metadata:XML DC-XML DC-RDF
:
Copy citation
Share:Bookmark and Share

Secondary language

Language:English
Title:Optimized path planning using RRT methods and smooth path generation
Abstract:
The problem of determining the optimal or suboptimal path in space is a demanding task with multiple applicability as well as necessity for fast calculation. The computational complexity increases depending on the increase in the number of parameters or their values and the complexity of obstacles arrangement. The master’s thesis is based on the use of RRT-methods with the fast presentation feature of possible non-optimal movement through space in the form of a state transition graph, within which the best path is determined by using the reverse path tracking method. The acquired path quality is further improved by reducing redundant turns and represented with Bezier polynomials in the continuous smooth path form for the possibility of immediate tracking. Therefore with the use of RRT-methods, a non-optimal state transition graph is rapidly yielded and in combination with further processing, of improving the disadvantage of fast construction, a high quality path outcome is thus quickly acquired. In the light of speeding up the construction of RRT-trees, upgraded procedures of individual steps are implemented, such as predefining the configuration space for faster tree node collision checking with a possible nearby obstacle, the choice of using the search for the nearest node only within the interesting part of the area in order to reduce the number of checked nodes and taking into account the obstacle shape when redefining a new node. The latter allows more efficient tree spreading along an obstacle or narrow passages. Experiments confirms the effective use of simple RRT methods, without subsequently linking of nearby states, in combination with further path processing, which allows fast calculation of quality path.

Keywords:RRT, goal biased RRT, bidirectional RRT, state transition graph, inverse path tracking, path reduction, Bezier polynomials, time upgrades

Similar documents

Similar works from RUL:
Similar works from other Slovenian collections:

Back