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

Abstract

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.

Keywords

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

Data

Language: Slovenian
Year of publishing:
Typology: 2.09 - Master's Thesis
Organization: UL FE - Faculty of Electrical Engineering
Publisher: [B. Jermol]
UDC: 004(043.3)
COBISS: 178097155 Link will open in a new window
Views: 32
Downloads: 9
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary title: Smooth path planning with genetic algorithm
Secondary abstract: 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.
Secondary keywords: genetic algorithm;path planning;parametric curve optimization;Bézier curve;Catmull-Rom spline;piecewise linear path;
Type (COBISS): Master's thesis/paper
Study programme: 1000316
Embargo end date (OpenAIRE): 1970-01-01
Thesis comment: Univ. v Ljubljani, Fak. za elektrotehniko
Pages: XII, 68 str.
ID: 21815779