Path planning for multiple mobile sensor platforms


Thesis Type: Postgraduate

Institution Of The Thesis: Marmara University, Institute for Graduate Studies in Pure and Applied Sciences, Turkey

Approval Date: 2011

Thesis Language: English

Student: MESUT SİFYAN

Supervisor: Haluk Rahmi Topcuoğlu

Abstract:

ÇOKLU HAREKETLİ SENSÖR PLATFORMLARI İÇİN GÜZERGAH PLANLAMA Güzergah planlama problemleri, robotik, bilgisayar destekli tasarım, üretim, animasyon ve uçuş uygulamaları gibi alanlarda incelenmektedir. Güzergah planlama algoritmaları başlangıç durumundan hedeflenen duruma çarpışmalardan kaçınarak bir grup konfigürasyonun üretilmesiyle problemleri çözmeyi hedeflemektedir. Buna karşı, kapsama tabanlı güzergah planlama probleminde sensörlerin güzergahları en kısa mesafede en yüksek görünürlüğü sağlamak hedefi ile etkin bir şekilde üretilir. Tezimizde, üç boyutlu araziler üzerinde çoklu hareketli sensör platformları için güzergah planlama problemine özgün karma bir yöntem önerilmiştir. Yöntemimiz iki aşamadan oluşmaktadır: genel güzergah planlama aşaması ve yerel güzergah planlama aşaması. Birinci aşamada olasılıksal yol haritası yöntemi ile bağlantı grafı üretilip sensörlerin güzergahlarını oluşturan kontrol noktaları bu graf üzerindeki noktalardan seçilir. İkinci aşamada ise kontrol noktalarının arasındaki ara noktaları oluşturarak sensörlerin güzergahlarını tamamlamak için yerel güzergah planlama aşamasında iki farklı yöntem geliştirilmiştir. İlk yöntemimiz, probleme özgü yöntemleri genetik algoritmalarla birleştiren bir karma evrimsel algoritma. İkinci yöntem ise yardımlı buluşsal tabanlı bir yöntemdir. Her iki yöntem de güzergahların erişilebilirliği, düzgünlüğü, sensörler tarafından kapsanan arazinin görünürlüğü ve güzergahların maliyeti kriterlerini dikkate almaktadır. Deneysel çalışmamız tasarladığımız çözümün farklı arazi ve sensör yapılarında etkinliğini göstermektedir Temmuz, 2011 Mesut SİFYAN ABSTRACT PATH PLANNING FOR MULTIPLE MOBILE SENSOR PLATFORMS Path planning problems exist in various fields including robotics, computer aided design, manufacturing, computer animation and aviation applications. Path planning algorithms aim to solve problems by computing a set of continuous configurations to reach goal positions from initial positions by avoiding collisions. On the other hand, in coverage path planning, routes of sensors are determined efficiently in order to get maximum visibility in shortest path. In this thesis, a novel hybrid method for path planning problem of multiple mobile sensor platforms on a 3-D terrain is proposed. Our method proceeds in two phases: the global path-planning phase, and the local path planning phase. The first phase constructs a connectivity graph generated by a probabilistic roadmap (PRM) method and selects the control points of sensors’ paths from the set of nodes generated by the PRM-based method. On the other hand, in the local path-planning phase, two techniques are presented to determine the intermediate points that are between control points of sensors’ paths in order to complete the paths. Our first method is a hybrid evolutionary algorithm which combines genetic algorithms with problem specific methods. The second method is based on hyper-heuristics. Both techniques consider the accessibility of control points, smoothness of each path, visibility of terrain covered by mobile sensors and the total cost of all paths (i.e. the total length of all paths). The experimental study points out the effectiveness of our solution framework for coverage path planning under various terrain and sensor characteristics July, 2011 Mesut SİFYAN