Geri Dön

Engellerin bulunduğu ortamda gezgin robotun en iyi yolu bulması ve izlemesi

Two-stage shortest path algorithm with obstacle avoidance for mobile robots

  1. Tez No: 216711
  2. Yazar: VOLKAN ARICI
  3. Danışmanlar: YRD. DOÇ. DR. MUSTAFA DOĞAN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Elektrik ve Elektronik Mühendisliği, Electrical and Electronics Engineering
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2008
  8. Dil: Türkçe
  9. Üniversite: Başkent Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Elektrik ve Elektronik Mühendisliği Bölümü
  12. Bilim Dalı: Elektrik-Elektronik Mühendisliği Ana Bilim Dalı
  13. Sayfa Sayısı: 96

Özet

Birçok uygulamalarda, hareketi denetlenen nesnenin (robotun) engellere çarpmadan bir başlangıç konumdan bir hedef konuma en kısa yolla gitmesinin sağlanması gerekir. Söz konusu problem, engellerden sakınma optimizasyon problemi olarak da adlandırılır. Bu çalışmada engellerin, farklı yarıçaplı daireler şeklinde ve hareketsiz oldukları varsayılır. Nesnenin noktasal boyutta olduğu kabul edilmiştir.Problemin sayısal çözümü için iki aşamalı algoritma önerilir. Birinci aşamada, bir adım için optimal yöntem uygulanmıştır. Her adımda nesnenin şu andaki konumu ile hedef konum arasında düz yol üzerindeki ilk engel, tek engel gibi düşünülmüştür. Yöntem, geometrik gösterimlere dayanarak gerçekleştirilmiştir. Birinci aşamadan elde edilen yol optimal olmayabilir, ama bu yolun uzunluğu esas alınarak optimal yolun yer aldığı bölge, bir elipsle sınırlandırılarak küçültülebilir. Elde edilen bölge bir sonraki aşamada işlem tasarrufu yapılmasını sağlamıştır.Genel algoritmanın ikinci aşamasında engeller arasındaki minimal mesafe dikkate alınarak, bölge karelere bölünmüştür. Engellerle kesişimi olan karelere geçişler yasaklanarak ayrıklaştırma yapılmıştır. Bu yolla elde edilen problem, çizge kuramında en kısa yolun bulunması problemi olarak yorumlanır ve Dijkstra algoritmasının uygulanması ile çözülmüştür. Problemin özelliklerine dayanarak Dijkstra algoritmasının daha verimli kullanımını sağlayan bazı değiştirmeler yapılmıştır.Önerilen iki aşamalı algoritmayı sınamak için sayısal benzetimler yapılmıştır. Benzetimlerde rasgele engeller oluşturulur. Bir hedef konum seçilir. Farklı başlangıç konumlar alınarak önerilen algoritma çalıştırılır. Sonuçlar, önerilen algoritmanın engellerden sakınma optimizasyon probleminin çözümü için kullanılabilir olduğunu göstermektedir.Deneysel çalışmada, deney düzeneğinden tek kamera ile alınan sayısal görüntülere, görüntü işleme teknikleri uygulanarak, dairesel kesitli engellerin konumlarının bulunması ve başlangıç konumundan bitiş konumuna yol optimizasyonu gerçekleştirilmiştir. Bulunan bu yol gezgin robot kullanılarak izlenmiştir. Deneysel olarak; bu çalışmada gezgin robotun en iyi yolu bulması ve izlemesi başarı ile gerçekleştirilmiş ve farklı boyut ve konumlardaki dairesel engeller için test edilmiştir.ANAHTAR SÖZCÜKLER: Engellerden sakınma, çizge kuramı, en kısa yol problemi, Dijkstra algoritması, Gezgin robotlar.

Özet (Çeviri)

In most of the path-planning applications, the controlled object (mobile robot) is expected to reach its predetermined target by following the shortest path and avoiding the obstacles. This navigation problem is also called optimal obstacle avoidance. In this work, obstacles are assumed to be motionless circles in different sizes. The object is supposed to be a point robot.The two-stage algorithm is proposed to find a numerical solution to the problem. At first stage, the method, which is optimal for one step, is applied iteratively. In every step of the method the first obstacle on the straight line between the current position of the object and the target is assumed to be a single obstacle. The proposed method is realized with using geometric representations. Some evaluations are made to prove that the method is convergent. The path obtained at the first stage might not be optimum. However, its length can be used to limit the feasible region through an ellipse, which contains the shortest path. Thus, the reduced search space makes the next stage more efficient and endurable for real-time applications.In the second stage of the algorithm, the elliptic region is meshed with squares the side length of which is set in agreement with the minimum distance between obstacles. It is prohibited to pass through the squares that intersect obstacles. Thus, by discretization the problem becomes the shortest path problem in a graph, and is solved by applying the Dijkstra?s algorithm.The proposed two-stage algorithm is verified with numerical simulations. Obstacles are chosen randomly. A target position is selected and fixed. For different starting points, the algorithm is tested repeatedly. The results show that the proposed algorithm can be applied to find an optimal solution for the obstacle avoidance problem.In experimental work, images were taken from an experimental set-up with a single camera. Identification of circular objects was realized by using image processing techniques. Shortest path optimization was performed by defining starting and target points. Experimentally, shortest path algorithm with obstacle avoidance for mobile robot have been designed, tested and applied successfully.KEYWORDS: Obstacle avoidance, graph theory, shortest path problem, Dijkstra algorithm, Mobile Robots.

Benzer Tezler

  1. Dinamik engellerin bulunduğu ortamda gezgin robot için hareket planlama

    Motion planning for mobil robot in enviroments where dynamic obstacles

    MEHMET LAFCI

    Yüksek Lisans

    Türkçe

    Türkçe

    2016

    Elektrik ve Elektronik MühendisliğiKarabük Üniversitesi

    Elektrik-Elektronik Mühendisliği Ana Bilim Dalı

    PROF. DR. İHSAN ULUER

  2. Derin pekiştirmeli öğrenme ile otonom gezgin robotların dinamik ortamlarda navigasyonu

    Navigation of autonomous mobile robots in dynamic environments with deep reinforcement learning

    KORAY ÖZDEMİR

    Yüksek Lisans

    Türkçe

    Türkçe

    2021

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolYalova Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ADEM TUNCER

  3. Mobil robotların davranış planlamasında pıd, bulanık ve gauss denetçilerinin başarımlarının karşılaştırılması

    Comparison of performance of pid, fuzzy and gauss controllers in behavior planning of mobile robots

    CİHANGİR HAN KAZANCI

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİnönü Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ ADNAN FATİH KOCAMAZ

  4. Omni-directional vision based environment sensing for movement control of mobile robots

    Gezgin robotların hareket kontrolü için tüm-yönlü görüntüleme tabanlı ortam algılaması

    KALİ GÜRKAHRAMAN

    Doktora

    İngilizce

    İngilizce

    2011

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolDokuz Eylül Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    PROF. DR. YALÇIN ÇEBİ

  5. Çoklu robot sistemlerinin formasyon kontrolü için dinamik engellerden kaçınma algoritmasının geliştirilmesi

    Development of dynamic obstacle avoidance algorithm for formation control of multi-robot systems

    ZEHRA TÜFEKÇİ

    Yüksek Lisans

    Türkçe

    Türkçe

    2023

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Sabahattin Zaim Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. GÖKHAN ERDEMİR