Планирање путање робота базирано na D* Lite алгоритму и аутономној претрази окружења

Abstract

Предмет истраживања дисертације су on-line frontier-based стратегије за претрагу окружења, код којих је примењен D* Lite алгоритам за планирање путање робота и које за избор следеће позиције користе методе вишекритеријумског одлучивања (ВКО). Као критеријуми за избор следеће позиције из скупа кандидата користе се: дужина путање до кандидата, информативни потенцијал кандидата и удаљеност кандидата од базне станице. За меру ефикасности претраге примењен је просечан пређени пут робота у односу на више стартних позиција за потребе реализације претраге 90% окружења. Симулацијама у Матлабу, доказано је да у дефинисаним условима TOPSIS обезбеђује ефикаснију претрагу комплексних окружења у односу на друге две анализиране методе ВКО (SAW и COPRAS), као и у односу на 4 класичне стратегије из литературе. Ово се објашњава тиме да TOPSIS при одабиру алтернативе максимизује Еуклидову удаљеност од хипотетички најлошијег решења, чиме се минимизује ризик у одлучивању који је изражен код комплексних окружења. Кључни резултати су верификовани у Gazebo 3D симулатору, користећи Robot Operating System. У дисертацији се, такође, предлажу 2 приступа за унапређење планирања путање робота у мисијама трагања и спасавања. Први приступ је примена D* Lite алгоритма у комбинацији са фази логиком. Фази логика се користи за дефинисање тежина ћелија мапе намењене за планирање путања робота, како оне не би имале бинарне вредности. Тиме је постигнуто да претрага окружења покрива објекте према приоритету, као и да роботи за мапирање при кретању не ометају друге роботе. Други приступ је примена D* Lite алгоритма у комбинацији са on-line учењем. Овим је скраћен пређени пут робота за мапирање и минимизована су његова ризична кретања, јер се маневар у циљу избегавања препрека изводи пре потенцијалног сусрета.

The subject of the research in the dissertation are on-line frontier-based strategies for exploration of environment, which have applied D* Lite algorithm for robot path planning and which use the multi-criteria decion making (MCDM) methods for selecting the next position. The criteria used in the process of decion making are: the length of a collision free path, the expected information gain and the distance from the base station. To measure the efficiency of the exploration, the average travelled robot path was applied in relation to several starting positions for the needs of the 90% environment explored. By simulations in Matlab, it was proved that in defined conditions the TOPSIS provides more efficient exploration of complex environment in relation to other two analzyed MCDM methods (SAW and COPRAS), as well as in relation to 4 classical strategies from the literature. This is explained in a way that, in selecting the alternative, the TOPSIS maximizes Euclidean distance from the hypothetically worst solution, by which a risk in decision making, emphasized in complex environment, is minimized. Key results were verified in the Gazebo 3D simulator, using the Robot Operating System. The dissertation, also, proposes 2 approaches for improving the robot path planning in search and rescue missions. The first approach is the application of D* Lite algorithm in combination with fuzzy logics. The fuzzy logics is used to define the map cell cost used for robot path planning, so they do not have the binary values. This has made the exploration cover the objects according to the priority, as well as that robots for mapping do not interfere with other robots during movement. The second approach is the the application of D* Lite algorithm in combination with online learning. This has made the mapping robot path shortened and its risky movement has been minimized, since the maneuvre with the aim of avoiding the obstacles is performed before a potential encounter.