Improving Probabilistic Roadmap Methods for Fast Motion Planning

Abstract

Reitinsuunnittelun nopeuttaminen reittikarttamenetelmiä parantamalla

Tutkimuksessa tarkastellaan reitinsuunnittelua, joka on erityisesti robotiikassa keskeinen ongelma. Reitinsuunnittelussa tarkoituksena on löytää robotille sellainen reitti kahden annetun päätepisteen välille, että robotti voi liikkua reitillä törmäämättä ympäristössä oleviin esteisiin. Robotiikan lisäksi reitinsuunnittelulla on myös muita tärkeitä sovelluskohteita. Sitä voidaan hyödyntää esimerkiksi animoinnissa tai tietokonepeleissä pelihahmojen ohjauksessa.

Reitinsuunnittelu on vaikea tehtävä. Tarkat menetelmät sen ratkaisemiseksi ovat yleensä liian hitaita, jotta niitä olisi mielekästä käyttää. Ongelman ratkaisemiseksi on kuitenkin esitetty myös likimääräisiä menetelmiä, joiden avulla tehtävän ratkaiseminen onnistuu nopeammin. Tällaisia ovat esimerkiksi probabilistiset reittikarttamenetelmät, joihin tässä väitöskirjassa keskitytään. Reittikarttamenetelmien toiminta perustuu reittikarttaan, jota hyödyntämällä robotti voi turvallisesti kulkea törmäämättä esteisiin. Valmiin reittikartan käyttö on helppoa, mutta sellaisen rakentaminen voi kuitenkin usein olla hidasta ja hankalaa.

Tämä väitöstutkimus koostuu viidestä artikkelista, joista jokainen käsittelee reittikarttojen rakentamista. Artikkeleissa esitetään uusia keinoja, joiden avulla rakentamista voi tehostaa eri tavoin. Kolmessa artikkelissa keskitytään pääasiassa keinoihin, joiden avulla reittikarttojen rakentamista voi nopeuttaa. Yhdessä artikkelissa esitetään menetelmä, jolla reittikartan koko on mahdollista pitää pienenä. Lisäksi yhdessä artikkelissa tarkastellaan menetelmää, jolla reittikartta voidaan rakentaa sellaiseksi, että se toimii hyvin myös muuttuvissa ympäristöissä. Kaikkia esiteltyjä keinoja testattiin simuloidussa ympäristössä ja niitä verrattiin muihin yleisesti käytössä oleviin menetelmiin. Tulokset osoittavat, että reittikarttojen rakentamista on mahdollista parantaa merkittävästi väitöskirjassa esiteltyjen menetelmien avulla.

The goal of motion planning is to find a collision-free path for a robot that moves among obstacles. The problem originates from robotics where it is a fundamental part of autonomous robots. However, motion planning can be used in many other application areas as well, for example, in computer games and molecular simulations.

Motion planning is a difficult problem and exact algorithms are rarely useful in practice. Therefore, many approximate algorithms have been proposed to solve it. One promising approach is to use probabilistic roadmap planners that work by constructing a roadmap for a robot. This roadmap uses information from static obstacles and it contains simple, collision-free path segments that are combined together. The robot can then use it as a guide while moving. Probabilistic roadmap planners can work remarkably well even in complex environments with robots that have many degrees of freedom but still there are cases where their performance can be poor.

This thesis investigates these planners and tries to find ways to enhance their performance. Five different methods to improve them are proposed and tested experimentally in simulated environments. Three of them concentrate on speeding up the construction of roadmaps in various ways. One proposed method tries to build a roadmap in such a way that it works well in changing environments where all obstacles are not known in advance. The last method can be used to reduce the size of roadmaps. Results from the experiments show that the suggested methods work well and can indeed lead to better planners.