20.500.12556/RUL-121196 Optimizirano iskanje poti z RRT-metodami in generiranje gladke poti Optimized path planning using RRT methods and smooth path generation 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. 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. RRT ciljno usmerjeni RRT povezovalni RRT graf prehajanja stanj vzvratno iskanje reduciranje poti Bezierjevi polinomi časovne nadgradnje RRT goal biased RRT bidirectional RRT state transition graph inverse path tracking path reduction Bezier polynomials time upgrades true false false Slovenski jezik Angleški jezik Magistrsko delo/naloga 2020-10-01 08:00:12 2020-10-01 08:00:17 2022-09-01 04:02:02 0000-00-00 00:00:00 2020 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 1970-01-01 51141 Kotnik_Klemen_-_Optimizirano_iskanje_poti_z_RRT-metodami_in_generiranje_gladke_poti.pdf Kotnik_Klemen_-_Optimizirano_iskanje_poti_z_RRT-metodami_in_generiranje_gladke_poti.pdf 1 FE847F42A97D11252A3677DB4C73C873 7e2f9cb03a5ec7de452e1ca312a6d7ab7ddaa04c972e462f2fc354714848c2f7 418823e2-a1ba-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=136090 Fakulteta za elektrotehniko 0 0 0