Hareketli etmenler için arama algoritmaları
Search algorithms for moving agents
Yazar: AYŞEGÜL MUT
Danışman: DOÇ. NAFİZ ARICA
Deniz Harp Okulu Komutanlığı / Deniz Bilimleri ve Mühendisliği Enstitüsü / Bilgisayar Mühendisliği Bölümü / Bilgisayar Mühendisliği Ana Bilim Dalı
Derece: Yüksek Lisans, 2012
Konu: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control

Özet:
Bu tezde, gerçek zamanlı ilerleyen etmenler için sabit ve hareketli hedef güzergah planlamasında kullanılan artımsal ve gerçek zamanlı yaklaşımlar karşılaştırılmaktadır. Ayrıca sabit ve hareketli çoklu hedefler için güzergah planlamasında hedef sıralamasının belirlenmesine yönelik algoritmalar geliştirilmektedir. Bu maksatla, etmen sadece sensör menzili içini gözlemleyecek ve ortam içerisinde ilerledikçe önceki gözlemlerini saklayarak ortam hakkındaki bilgilerini güncelleyecek şekilde modellenmektedir.Sabit hedef arama problemi için kullanılan artımsal ve gerçek zamanlı yaklaşımların literatürdeki en iyi örnekleri olan sırasıyla D* Lite, RTAA*(Real Time Adaptive A*) ve LSS-LRTA* (Local Search Space-Learning Real Time A*) algoritmaları belirli bir sensör menziline sahip etmen modeli için kullanılabilecek şekilde uygulanmaktadır. Sabit etmenler için tasarımlanan ilk artımsal yaklaşımlardan LPA* (Lifelong Planning A*) algoritması genişletilerek hareketli etmenler için güzergah planlaması yapacak şekilde geliştirilmektedir.Hareketli hedef arama probleminde ise her iki yaklaşımın en iyi örneklerinden MT-D*Lite (Moving Target D*Lite), MTS (Moving Target Search), MTSd (MTS deliberation) algoritmaları, farklı benzetim ortamlarında ve sensör menzillerinde karşılaştırılmaktadır. Ayrıca sabit hedef arama problemi için geliştirilen LSS-LRTA* algoritması genişletilerek hareketli hedef arama probleminde kullanılmaya uygun hale getirilmektedir.Çoklu hedef güzergah planlamasında hedef seçimi için tasarlanan en iyileme probleminin çözümünde genetik algoritmalar kullanılmaktadır. Ortamda hareketli hedefler bulunduğunda kullanılmak üzere artımsal genetik algoritma önerilmektedir.Sabit ve hareketli hedef arama probleminin çözümü için yapılan benzetim deneylerinde artımsal ve gerçek zamanlı algoritmaların değişik sensör menzillerinde farklı davranışlar sergilediği ve birbirlerine göre avantajlar sağladıkları gözlenmektedir. Ayrıca ortamda birden fazla hareketli hedef olduğunda, hedef sayısı arttıkça genetik algoritmayı yeniden çalıştırmak yerine artımsal genetik algoritma kullanmanın daha avantajlı olacağı görülmektedir.

Abstract:
In this thesis, we compare the real time and incremental heuristic search methods used in path planning for real time situated agents. In addition, we develop algorithms for determining the order in which the targets are visited, when there exist multiple stationary and moving targets. The agents are assumed to be equipped with a sensor having a specific range and to interleave planning with movement.Three well known representatives of incremental and real time approaches for stationary target search problem, namely D* Lite, RTAA* (Real Time Adaptive A*) and LSS-LRTA* (Local Search Space-Learning Real Time A*) algorithms respectively, are modified to be used for an agent model with a specific sensor range. LPA* (Lifelong Planning A*), one of the first incremental approaches designed for stationary agents, is improved to perform route planning for moving agents.In moving target search problem, well known representatives of both approaches, MT-D*Lite (Moving Target D*Lite), MTS (Moving Target Search) and MTSd (MTS deliberation) are compared in various simulation environments and sensor ranges. In addition, LSS-LRTA*, used for a stationary target search problem, is improved to do path planning for moving targets.We use genetic algorithms for multiple target search problem. Incremental genetic algorithm is developed to be used when the targets are moving in the environment.The simulation show that the algorithms behave differently and have advantages over each other as the sensor range changes. Lastly, it is observed that employing incremental genetic algorithm is more advantageous than re-planning the genetic algorithm at each step of multiple target search problem.