Robottien probabilistisista reittikartta-algoritmeista
RANTANEN, MIKA (2009)
2009
Tietojenkäsittelyoppi - Computer Science
This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.
Hyväksymispäivämäärä
2009-06-26
Julkaisun pysyvä osoite on
http://urn.fi/urn:nbn:fi:uta-1-19974
http://urn.fi/urn:nbn:fi:uta-1-19974
Tiivistelmä
Robottien reitinsuunnittelun tarkoituksena on löytää robotille sellainen reitti kahden annetun päätepisteen välille, että robotti ei reitillä kulkiessaan törmää esteisiin. Reitinsuunnittelu on erittäin tärkeä osa esimerkiksi itsenäisesti toimivien robottien toimintaa, mutta sillä on monia muitakin sovelluskohteita. Reitinsuunnitteluongelma on kuitenkin laskennallisesti erittäin vaativa tehtävä ja siksi sen ratkaisemiseksi on kehitetty useita likimääräisiä algoritmeja.
Tässä tutkielmassa esitellään aluksi reitinsuunnitteluun liittyviä peruskäsitteitä, ja perehdytään sen jälkeen erityisesti probabilistisiin reittikartta-algoritmeihin. Ne ovat likimääräisiä algoritmeja, joiden avulla reitinsuunnitteluongelma on yleensä mahdollista ratkaista nopeasti. Tutkielmassa esitellään myös kokonaan uusi menetelmä, jolla probabilististen reittikartta-algoritmien toimintaa on mahdollista tehostaa entisestään.
Tutkielmassa kuvataan lisäksi kokeita, joiden avulla vertailtiin erilaisia probabilististen reittikartta-algoritmien toteutuksia keskenään. Tarkoituksena oli saada selville, onko erilaisten algoritmien välillä merkittävää eroa, ja millaiset algoritmit sopivat mihinkin tilanteeseen. Tulosten mukaan reittikartta-algoritmien eri osien toteutusmenetelmien valinta kannattaa tehdä huolellisesti, sillä sopivasti valitut menetelmät voivat tehostaa algoritmin toimintaa huomattavasti. Esimerkiksi tässä tutkielmassa esitelty deaktivointimenetelmä osoittautui erittäin käyttökelpoiseksi.
Asiasanat:reittikartta-algoritmit, reitinsuunnittelu, robotit
Tässä tutkielmassa esitellään aluksi reitinsuunnitteluun liittyviä peruskäsitteitä, ja perehdytään sen jälkeen erityisesti probabilistisiin reittikartta-algoritmeihin. Ne ovat likimääräisiä algoritmeja, joiden avulla reitinsuunnitteluongelma on yleensä mahdollista ratkaista nopeasti. Tutkielmassa esitellään myös kokonaan uusi menetelmä, jolla probabilististen reittikartta-algoritmien toimintaa on mahdollista tehostaa entisestään.
Tutkielmassa kuvataan lisäksi kokeita, joiden avulla vertailtiin erilaisia probabilististen reittikartta-algoritmien toteutuksia keskenään. Tarkoituksena oli saada selville, onko erilaisten algoritmien välillä merkittävää eroa, ja millaiset algoritmit sopivat mihinkin tilanteeseen. Tulosten mukaan reittikartta-algoritmien eri osien toteutusmenetelmien valinta kannattaa tehdä huolellisesti, sillä sopivasti valitut menetelmät voivat tehostaa algoritmin toimintaa huomattavasti. Esimerkiksi tässä tutkielmassa esitelty deaktivointimenetelmä osoittautui erittäin käyttökelpoiseksi.
Asiasanat:reittikartta-algoritmit, reitinsuunnittelu, robotit