Orta Doğu Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Elektrik-Elektronik Mühendisliği Anabilim Dalı
A comparative study of quadtree decomposition and constrained delaunay triangulation using mdp and artificial potential field based path planning
Dördün ağaç ayrıştırması ve kısıtlandırılmış delaunay üçgenleştirmesinin markov karar süreci ve yapay potansiyel alan tabanlı yol planlaması kullanılarak karşılaştırmalı bir çalışması
Başer Kandehir - 2019Teze Git (tez.yok.gov.tr)
Özet:
The general purpose of a mobile robot is moving from one point to another and perform certain tasks. To do so, it first computes a motion strategy and then tries to execute it. This is not feasible most of the time unless uncertainties of the real world is taken into account. Markov decision processes (MDPs) provide a mathematical system to deal with uncertainties of planning and execution stages. MDPs require finite set of states. Therefore, continuous space of the real world must be discretized. In this study, two widely used space discretization methods, namely quadtree decomposition (QD) and constrained Delaunay triangulation (CDT), are compared in terms of path length, travel time, two safety measures, planning time, number of iterations, and number of states to find out which one of these discretization methods is better in the context of MDP and planar motion planning. MDP framework is used as high-level planner, and value iteration is used to obtain the optimal policy. Then, artificial potential field (APF) method is used for low-level execution. Results showed that QD and CDT are both suitable in the context of MDP and planar path planning with APF. QD results in longer paths but requires less travel time whereas CDT results in shorter paths but requires more travel time. QD and CDT perform almost equally in terms of safety. QD has clear disadvantages compared to CDT in terms of planning time, number of iterations, and number of states. QD and CDT might be preferable for different applications. Thus, it is best to optimize parameters for preferred metrics on a specific problem.
Summary:
Bir mobil robotun genel amacı bir noktadan diğerine hareket etmek ve belli görevleri yerine getirmektir. Bunu yapmak için, önce bir hareket planı hesaplar ve daha sonra bunu uygulamaya çalışır. Gerçek dünyanın belirsizlikleri dikkate alınmadıkça bu çoğu zaman uygulanabilir değildir. Markov karar süreçleri (MKSler) hem planlama hem uygulama aşamasında bu belirsizliklerin üstesinden gelmek için matematiksel bir sistem sağlar. MKSler sonlu sayıda durum gerektirir. Bundan dolayı, gerçek dünyanın devamlı uzayı ayrıklaştırılmalıdır. Bu çalışmada, dördün ağaç ayrıştırması (DAA) ve kısıtlandırılmış Delaunay üçgenleştirmesi (KDÜ) olarak adlandırılan iki sık kullanılan uzay ayrıklaştırma metodu, MKS ve düzlemsel hareket planlama bağlamında bu ayrıklaştırma metodlarından hangisinin daha iyi olduğunu anlamak için, yol uzunluğu, yolculuk zamanı, iki güvenlik ölçüsü, planlama zamanı, iterasyon sayısı, ve durum sayısı cinsinden karşılaştırılıyor. MKS sistemi yüksek düzey planlayıcı olarak kullanılıyor, ve değer iterasyonu en iyi planı elde etmek için kullanılıyor. Daha sonra, yapay potansiyel alan (YPA) metodu alt düzey uygulama için kulllanılıyor. Sonuçlar gösterdi ki, hem DAA hem KDÜ, MKS ve YPA ile düzlemsel hareket planlama bağlamında uygundur. DAA daha uzun yollarla sonuçlanıyor ama daha az yolculuk zamanı gerektiriyorken KDÜ daha kısa yollarla sonuçlanıyor ama daha fazla yolculuk zamanı gerektiriyor. DAA ve KDÜ güvenlik açısından neredeyse aynı davranıyor. DAA, KDÜ ile karşılaştırıldığında planlama zamanı, iterasyon sayısı, ve durum sayısı cinsinden belirgin dezavantajlara sahip. DAA ve KDÜ farklı uygulamalar için tercih edilebilir. Bundan dolayı, en iyisi parametreleri belli bir problem üzerinde tercih edilen ölçüler için optimize etmektir.