Otonom mobil robotlarda kümeleme yöntemi ile tam kapsama planlama
Complete coverage planning with clustering method for autonomous mobile robots
Yazar: HAMZA AYDEMİR
Danışman: PROF. DR. MEHMET TEKEREK
Kahramanmaraş Sütçü İmam Üniversitesi / Fen Bilimleri Enstitüsü / Bilişim Sistemleri Ana Bilim Dalı
Derece: Yüksek Lisans, 2021
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Elfes, özellikle araştırma ve endüstri bağlamında robotların uygulama ve yayılma alanını genişletmek için bilinmeyen ortamlarda çalışabilecek otonom mobil robot kavramının önemini vurgulamıştır. Bu doğrultuda bir robotun, bilinmeyen bir ortamda herhangi bir noktaya yerleştirildiğinde yalnızca algılayıcılarını kullanarak gezinebilmesinin sağlanması zamanla temel ister haline gelmiştir. Otonom gezinme olarak ifade edilen bu ister, robotun yol planlaması yapması ihtiyacını doğurmuştur.
Yol planlama, robotun bir başlangıç noktasından bir hedefe verimli bir şekilde hareket etmesi için yörünge planlamasıdır. Yol planlaması, otonom mobil robotun görev tanımına göre çalışma alanının tamamını gezinmeyi gerektirebilir. Bu problem alanyazında Tam Kapsama Planlama (TKP) olarak ifade edilir. TKP engellerden kaçınırken bir alanın tüm noktalarından geçen bir yol planlama görevidir.
Bu çalışmada ele alınan problem, alanyazında en yaygın kullanılan bir TKP yöntemi olan Grid Tabanlı Tam Kapsama Planlama (GTTKP)'da kısmen dolu olan hücrenin tamamen dolu olarak işlenmesidir. Bu bağlamda, GTTKP yönteminde karşılaşılan kapsama probleminin ortamın özellikleri dikkate alınarak oluşturulacak kümeleme yönteminin kullanılabilmesi araştırma sorusu olarak belirlenmiştir. Bu doğrultuda, Arthur ve Vassilvitskii tarafından 2007 yılında alanyazına kazandırılan ve yaygın olarak kullanılan bir kümeleme algoritması ve bölümleme tekniği olan K-means++ algoritmasının kullanılabilmesi önerilmiştir.
Önerilen K-means++ Tam Kapsama Planlama (Km++TKP) yöntemi simülasyon ortamında ve gerçek dünyada robot üzerinde yapılan deneyler ile doğrulanmıştır. Aynı zamanda Km++TKP yönteminin başarımı ile GTTKP yönteminin başarımı karşılaştırılmıştır. Buna göre; tüm deneylerde Km++TKP yöntemin iç mekânı kapsama başarımının GTTKP yöntemine göre daha yüksek olduğu hesaplanmıştır.
Deneylerden elde edilen bulgular incelendiğinde, önerilen Km++TKP yönteminin simülasyon ortamında iç mekânın %96,86'sını, gerçek dünya boş iç mekânın %95,97'sini ve gerçek dünya engel içeren iç mekânın ise %94,32'sini kapsadığı görülmüştür. GTTKP yönteminin simülasyon ortamında iç mekânın %89,76'sını, gerçek dünya boş iç mekânın %82,47'sini ve gerçek dünya engel içeren iç mekânın ise %77,95'ini kapsadığı gözlemlenmiştir.

Abstract:
Elfes emphasized the importance of the concept of autonomous mobile robots that can work in unknown environments to expand the application and spread of robots, especially in the context of research and industry. In this direction, it has become basic requirement over time to ensure that a robot can navigate using only its sensors when placed at any point in an unknown environment. This demand, which is expressed as autonomous navigation, has led to the need for the robot to plan a path.
Path planning is trajectory planning for the robot to move efficiently from a starting point to a destination point. Path planning may require navigating the entire workspace according to the autonomous mobile robot's job description. This problem is referred to as Complete Coverage Planning (CCP) in the literature. CCP is a path planning task that passes through all points of an area while avoiding obstacles.
The problem addressed in this thesis is to process a partially filled cell as completely full in Grid Based Complete Coverage Planning (GBCCP), which is the most widely used CCP method in the literature. In this context, the use of the clustering method, which will be created by taking into account the characteristics of the environment of the coverage problem encountered in the GBCCP method, has been determined as a research question. In this direction, it is suggested to use the K-means++ algorithm, which is a widely used clustering algorithm and partitioning technique introduced in the literature by Arthur and Vassilvitskii in 2007.
The proposed K-means++ Complete Coverage Planning (Km++CCP) method has been validated by experiments on the robot in the simulation environment and the real world. At the same time, the performance of the Km++CCP method and the performance of the GBCCP method were compared. According to this; In all experiments, it has been calculated that the indoor coverage performance of the Km++CCP method is higher than the GBCCP method.
When the findings obtained from the experiments are examined, it is seen that the proposed Km++CCP method covers 96.86% of the indoor in the simulation environment, 95.97% of the real-world obstacle-free indoor, and 94.32% of the real-world indoor with obstacles. It has been observed that the GBCCP method covers 89.76% of the indoor in the simulation environment, 82.47% of the real-world obstacle-free indoor, and 77.95% of the real-world obstacle-free indoor.