Geri Dön

Solution of maze path finding problem using genetic algorithm

Labirentte yol bulma probleminin genetik algoritma kullanılarak çözülmesi

  1. Tez No: 168731
  2. Yazar: UMUT TÜRKARSLAN
  3. Danışmanlar: PROF.DR. MEHMET REŞİT TOLUN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Genetik algoritmalar, özerk robotlar, robot yol bulma, labirent yol bulma, yol planlama. vi, Genetic algorithms, autonomous robots, robot navigation, maze path finding, path planning. IV
  7. Yıl: 2005
  8. Dil: İngilizce
  9. Üniversite: Çankaya Üniversitesi
  10. Enstitü: Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Bölümü
  12. Bilim Dalı: Belirtilmemiş.
  13. Sayfa Sayısı: 74

Özet

ÖZ LABİRENTTE YOL BULMA PROBLEMİNİN GENETİK ALGORİTMA KULLANILARAK ÇÖZÜLMESİ Türkarslan, Umut Yüksek Lisans, Bilgisayar Mühendisliği Bölümü Tez Yöneticisi: Prof. Dr. Mehmet Reşit Tolun Haziran 2005, 61 sayfa Bu çalışmanın amacı, labirent yol bulma probleminin genetik algoritma kullanarak çözülmesidir. Bağımsız bir mobil robot olacağı varsayılan yapay bir ajan, bir labirent içerisinde belirlenmiş iki yer arasında geçerli bir yol bulmak için rastgele yürüyüşler yapmaktadır. Labirent; engelleri, serbest alanları ve labirent duvarları ile çevrili iki boyutlu durağan bir düzlemdir. Labirentin grafik olarak basitliğine rağmen, araştırmanın emelinde yatan arama problemi oldukça karmaşıktır. Çünkü robot herhangi bir uzaktan algılama yeteneğine sahip değildir. Genetik algoritmalar, Darwin' in doğal seçilim ve genetiğin mekaniklerine dayalı rastsal arama metodlandır. Bu çalışmada, robot yol bulma probleminin çözümü için bir genetik arama metodu geliştirilmiştir. Geliştirilen metod,labirent içerisinde belirlenmiş konumlar arasında sürekli olarak geçerli ve kısa patikalar arar. Uygulamanın ana özellikleri şunlardır: labirent olarak kullanılan iki boyutlu bir dizin, robot nesnesinin sınıfı, robot nesneler, rastsal yürüyüşlerle yapılan araştırmalar, ve araştırmaya uygun bir şekilde tasarlanmış genetik operatörler. Bu çalışma, günümüzün yol bulma sistemlerine bir katkıda bulunması niyetiyle gerçekleştirilmiştir.

Özet (Çeviri)

ABSTRACT SOLUTION OF MAZE PATH FINDING PROBLEM USING GENETIC ALGORITHM Türkarslan, Umut M. Sc, Department of Computer Engineering Supervisor: Prof. Dr. Mehmet Reşit Tolun June 2005, 61 pages The purpose of this study is to solve maze path finding problem by using genetic algorithm. An artificial agent supposed to be an autonomous mobile robot randomly tries to find a valid path between two specified locations by walking through a maze which is a two-dimensional static planar environment having barriers, free spaces and maze borders. Despite graphic simplicity of a maze, the underlying search problem is quite complex, since the robot lacks any remote sensing capabilities. Genetic Algorithms (GAs) are stochastic search algorithms based on the mechanics of Darwin's natural selection and genetics. In this study a genetic search method is developed to solve the robot navigation problem. The GA mcontinuously searches for valid and short paths between the specified locations in the maze by using string representations of paths as chromosomes. The main features of the implementation include a two-dimensional array as maze, robot class, robot objects, random walk exploration, and dedicated genetic operators. This study intends to be a contribution to nowadays' path finding systems.

Benzer Tezler

  1. Combining high-level causal reasoning with low-level geometric reasoning and motion planning for robotic manipulation

    Üst-seviye nedensel akıl-yürütmenin alt-seviye geometrik akıl-yürütme ve hareket planlama ile robotik manipülasyon için kaynaştırılması

    CAN PALAZ

    Yüksek Lisans

    İngilizce

    İngilizce

    2011

    Mühendislik BilimleriSabancı Üniversitesi

    Mühendislik Bilimleri Ana Bilim Dalı

    YRD. DOÇ. DR. ESRA ERDEM

    YRD. DOÇ. DR. VOLKAN PATOĞLU

  2. İki boyutlu labirentlerde arama algoritmalarının incelenmesi

    Investigation of search algorithms in two-dimensional mazes

    MERVE MENEVŞE

    Yüksek Lisans

    Türkçe

    Türkçe

    2024

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

    Bilgisayar Bilimleri Ana Bilim Dalı

    DR. ÖĞR. ÜYESİ AYŞE ÖVGÜ KINAY

  3. Path-connecting multi-agent real-time A-star search

    Patika birleştirmeli çoklu-ajan gerçek zamanlı A-yıldız arama

    MUSTAFA KEMAL KAPLAN

    Yüksek Lisans

    İngilizce

    İngilizce

    2001

    Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve KontrolOrta Doğu Teknik Üniversitesi

    Bilgisayar Mühendisliği Ana Bilim Dalı

    DOÇ. DR. FARUK POLAT

  4. Çeşitli büyüklüklerdeki alışveriş mekanlarını aydınlatma sistemleri tasarım ilkeleri

    Designing principles of lighting systems in store designs of various types

    HALE İKİZLER

    Yüksek Lisans

    Türkçe

    Türkçe

    1996

    Mimarlıkİstanbul Teknik Üniversitesi

    Mimarlık Ana Bilim Dalı

    PROF. DR. MEHMET Ş. KÜÇÜKDOĞU