magistrsko delo
Blaž Jermol (Avtor), Gregor Klančar (Mentor)

Povzetek

Načrtovanje kvalitetnih poti v okolju, zlasti v primeru večkriterijskega načrtovanja poti z ovirami, predstavlja zahtevno nalogo, kjer lahko določanje kvalitetnih rešitev postane težek izziv. Ob tem se genetski algoritem s svojo lastnostjo hevrističnega iskanja ponuja kot dobra rešitev za tovrstne probleme. V magistrskem delu predstavimo dva načina uporabe genetskih algoritmov za namen načrtovanja poti. Prvi način omogoča iskanje odsekoma linearnih poti v statičnem okolju z ovirami, pri čemer upošteva kriterij dolžine in gladkosti poti. Algoritem za svoje delovanje izkorišča a priori znanje o okolju, kar mu omogoča uporabo namenskih genetskih operatorjev, ki pripomorejo k razvoju kvalitetnejših poti. Za namen prepoznavanja ovir v okolju smo razvili namenski genetski operator, ki je zmožen popravljati pot, ki med izvajanjem genetskega algoritma pristane znotraj ovir. Ob tem smo predstavili uporabo dveh različnih mer gladkosti, ki omogočata večkriterijsko globalno iskanje poti ali razvoj odsekoma linearnih poti z višjo stopnjo gladkosti. Drugi način uporabe genetskih algoritmov opisuje optimizacijo parametrične krivulje, ki predstavlja pot v prostoru. Ob tem predstavimo dva različna načina glajenja poti in izdelavo genetskega algoritma za obe metodi glajenja. Skozi različne preizkuse smo potrdili, da oba načina uporabe razvijata kvalitetne poti. Kljub temu se zaradi obsežnosti možnih rešitev v kompleksnejših okoljih genetski algoritem sooča z zahtevami po veliki populaciji in visoki stopnji mutacije, kar vodi v dolge čase izvajanja trenutne implementacije.

Ključne besede

genetski algoritem;načrtovanje poti;optimizacija parametričnih krivulj;Bézierova krivulja;Catmull-Rom zlepek;odsekoma linearna pot;magisteriji;

Podatki

Jezik: Slovenski jezik
Leto izida:
Tipologija: 2.09 - Magistrsko delo
Organizacija: UL FE - Fakulteta za elektrotehniko
Založnik: [B. Jermol]
UDK: 004(043.3)
COBISS: 178097155 Povezava se bo odprla v novem oknu
Št. ogledov: 32
Št. prenosov: 9
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarni naslov: Smooth path planning with genetic algorithm
Sekundarni povzetek: Path planning of quality paths in the environment especially in the case of multi-objective path planning with obstacles poses a challenging task, where determining quality solutions can become a difficult challenge. Genetic algorithm and its heuristic search property offer a good solution for such problems. In the Master thesis, we present two ways of using genetic algorithms for the purpose of path planning. The first method enables the search for piecewise linear paths in a static environment with obstacles considering the objective of path length and path smoothness. The algorithm utilizes a priori knowledge of the environment, which allows the use of dedicated genetic operators that contribute to the development of quality paths. To recognize obstacles in the environment we have developed a dedicated genetic operator capable of correcting paths that land within obstacles during the searching process of genetic algorithm. We presented the use of two different smoothness measures that allows multi-objective global path searching or the development of piecewise linear paths with a higher degree of smoothness. The second method of using genetic algorithms describes the optimization of parametric curves that describe paths in space. Here we introduce two different methods for path smoothing and the genetic algorithm for both smoothing methods. Through various tests, in the end, we confirmed that both methods develop quality paths. Nevertheless, due to the extent of possible solutions in more complex environments, genetic algorithm faces the requirements for a large population and high mutation probability, which leads to long computing times for the current implementation.
Sekundarne ključne besede: genetic algorithm;path planning;parametric curve optimization;Bézier curve;Catmull-Rom spline;piecewise linear path;
Vrsta dela (COBISS): Magistrsko delo/naloga
Študijski program: 1000316
Konec prepovedi (OpenAIRE): 1970-01-01
Komentar na gradivo: Univ. v Ljubljani, Fak. za elektrotehniko
Strani: XII, 68 str.
ID: 21815779