Mobil robotlarda evrimsel metotlar ile optimal hareket planlama
Optimal motion planning with evolutionary methods for mobile robots
- Tez No: 143086
- Danışmanlar: DOÇ. DR. HAKAN TEMELTAŞ
- Tez Türü: Doktora
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2003
- Dil: Türkçe
- Üniversite: İstanbul Teknik Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Elektrik Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 99
Özet
Mobil robotlarda hareket planlama standart işlemlerdendir ve bu konu üzerine son 20 yılda oldukça fazla çalışma bulmak mümkündür. Hareket planlama çalışmaları iki gruba ayrılabilir. Eğer planlama, mobil robot hareket halindeyken yapılıyorsa, bu kapalı planlamalar (gerçek-zamanda veya lokal) (1) olarak isimlendirilir. Eğer planlama hareket gerçekleştirilmeden önce yapılıyorsa bu da açık planlamalar (off line, global) (2) olarak isimlendirilir. Potansiyel alanlar ve bulanık mantık, kapalı hareket planlamalarda kullanılan iki metottur. Eğer amaç sadece istenilen konfıgürasyona ulaşmak ise, kapalı planlamalar yeterlidir. Eğer hareketin performansının optimize edilmesi istenirse veya planlanan yörüngenin belli özelliklerinden emin olmak için (optimal-zaman veya mesafe vb.) açık planlamalar kullanılmalıdır. Genellikle açık-planlamalar 3 aşamalı bir hiyerarşik yapıya sahiptirler: yol planlama, düzgünleştirme ve izleme. Açık planlamalar da, açık-aynk ve açık-sürekli olmak üzere iki gruba ayrılırlar. Açık-aynk planlamalarda bu 3 aşama sırasıyla gerçeklenmelidir. Herşeyden önce aynklaştınlmış konfıgürasyon uzayında (hücrelere ayırma, görünebilirlik grafik metodu vb.) yol planlanır, daha sonra planlanan yol düzgünleştirilir, ve en sonunda bir kontrolör düzgünleştirilmiş yolu izler. 2. aşamada, B-spline, kübik spiraller, polinomal eğriler ve klothoidler kullanılmıştır. Açık-aynk olarak planlanan yörüngelerden, global optimal bir amaç ölçüt fonksiyonu sağlanamayabilir. Açık-sürekli planlamalarda ise yörünge 2 aşamada planlanır. İlk aşamada, çalışma uzayında planlama yapılır ve bundan sonraki aşamada da bu planlanan yörünge bir kontrolör ile izlenir. Bu kısımdaki çalışmalarda genellikle varyasyonel metotlar (Lagrange çarpanlanmn nümerik çözümü) kullanılmıştır. Bu yaklaşımda, çevreden gelen engel bilgileri ve mobil robotun kısıtlamalan kullanılır ve sonuçta global-optimal çözümler elde edilebilir. Ama iki dezavantajı bulunmaktadır : 1) rasgele sağlanan başlangıç değerleri ile nümerik çözüme başlanması ve bundan dolayı bazı durumlarda doğru sonuçlann elde edilememesi. 2) planlanan yörüngenin izlenmesi için bir kontrolöre ihtiyaç duyması. Bu tezin amacı, mobil robotlar için global-zaman optimal yörünge planlanmasıdır. Bu çalışmada önerilen yöntem bazı vasıflara sahiptir: - Hiyerarşik bir yapıya sahip olmaması - Çevreden gelen kısıtlamalann kullanılması (engeller vb.) - Uygulanabilir ve global-zaman optimal sonuçlar alınması - Planlanan yörüngenin takibi için bir kontrolöre ihtiyaç duyulmaması.Bu çerçevede, aşağıda iki problem tanımlanmaktadır: Problem 1 : önceden görünebilirlik grafik metoduyla (VGM) planlanmış yol üzerinde zaman-optimal yörüngenin bulunması. Problem 2 : global-zaman optimal yörüngenin bulunması. Her iki problemde de, yörüngeler, düz kısımlar (as=0 ve vso=0) ve eğri kısımlardan (at=0 ve vt= vto )' oluşturulmuşlardır. Eğri kısımların yapılan sadece iki parametre ile belirlenmektedir (0: dönüş açısı ve vt: eğri kısımdaki öteleme hızı). Eğri kısımlar kümesi, 06 (0,7i]° ve vt [0,40] inç parametre aralığındaki olası tüm eğri kısımlardan oluşmaktadır. Daha sonra, bu küme içerisinden global-zaman optimal yörüngeyi bulmak için evrimsel bir global optimizasyon metodu olan diferansiyel evrim (DE) kullanılmıştır. Eğri kısımlar iki şekilde oluşturulmuştur: a) robot eşitliklerinin seri açılımı ile (Mclauren serileri) ve b) bulanık mantık (BM)/yapay sinir ağlan (YSA). Türev gerektirmeyen (derivative-free) optimizasyon metotu olan diferansiyel evrim bazı avantajlara sahiptir: başlangıçtaki rastgele değerlerin sonuca etki etmemesi, fonksiyonlann türev bilgisine gerek duymaması, problemin tam ifade edilebildiği eşitliklerin kullanımı ve BM ve YSA gibi modellerin kullanılabilmesi. Diğer evrimsel metotlardan daha etkili olarak, DE' de kısıtlamalar, amaç-ölçüt fonksiyonu yerine seçim aşamasında ele alınmasıdır. Bu şekildeki bir yaklaşımla deneme- yanılma metotuyla ayarlanması gereken bir çok kontrol parametresine ihtiyaç kalmamaktadır. Evrimsel metotlann en büyük dezavantajı optimizasyon sürelerinin uzunluğudur. Bir ölçüde bu problemin üstesinden gelebilmek için: Lampinen' in seçim aşamasından daha hızlı sonuç veren yeni bir seçim aşamasının önerilmiştir, Parametre üst sınırlannın BM/YS A ile belirlenmesiyle parametre arama uzayı daraltılmıştır, Ve eğri kısımlar için robot eşitliklerinin seriye açılımı yerine YSA/BM modellerinin kullanılmıştır (hesaplama süre yaklaşık olarak 1/7 ye düşürülmüştür). Özgün bir global-zaman optimal yörünge planlama metotunun önerilmesi tezdeki en önemli katkıdır. Bu çalışmada, LEDA (library of efficient data types and algorithms) ve Nomad 200' ün C*“*”kütüphaneleri kullanılarak bir yazılım geliştirilmiştir. Elde edilen sonuçlar mobil robot Nomad 200' e başanlı bir şekilde uygulanmıştır. xıı
Özet (Çeviri)
Motion planning is a standard task in the mobile robot and it is possible to find numerous works in the last two decades. The motion planning studies can be separated into two groups. If the motion plan is computed while the robot moves, it is called explicit planning (real-time or lokal) (1). If it is computed before the motion is executed, it is called implicit planning (off-line, global) (2),. Potential fields and fuzzy which are two methods used in explicit motion plannings. If the aim is only reaching the desired configuration, explicit planning is sufficient. If it is desired to optimize the performance of the motion or to make sure the certain properties of the trajectory (i.e. optimal-time or distance), implicit planning must be used. Generally, implicit planning has a hierarchical structure with 3 stages: path planning, path smoothing and path tracking. Implicit planning is also separated into two groups: implicit-discrete and implicit-continuous. The 3 stages must be done in implicit- discrete planning. First of all, the path is planned in discretized configuration space (i.e. cell decomposition, visibility graph method), then, the planned path is smoothed, after all, a controller tracks smoothed path. In the 2nd stage, B-splines, cubic spirals, polynomial curves and clothoids are used. Globally optimal objective functions cannot be getting from the planned trajectory in implicit-discrete plannings. The trajectory is planned in two stages in implicit-continuous planning. In the first stage, the path plan is done in the workspace, after that stage, the planned path is tracked by a controller. Generally, variational methods (numerical solution of the lagrange multipliers) are used in this part. In this approach, obstacle information from the environment and the constraints of the mobile robot are used and consequently global-optimal solutions can be obtained. But it has two disadvantages: 1) numerical solutions start with random supplied initial values, that's why, in some cases the correct results cannot be obtained. 2) still, there is a need for a controller. Aim of this thesis is to obtain global-time optimal trajectory planning for mobile robots. The proposed method in this study has some attributes: - Not to be hierarchical structure - Using the constraints from environment (i.e. obstacles) - Obtaining feasible global-time optimal results - No need to a controller for tracking the planned trajectory.In this frame, two problems are defined below: Problem 1 : To find time optimal trajectory on predefined path, which is found by using visibility graph method. Problem 2 : To find global-time optimal trajectory. In both problems, trajectories are composed of line segments (as=0 and vso=0) and curve segments (at=0 and vj= vto ). The structures of the curve segments are determined by only two parameters (0: turn angle and vt: translational velocity in the curve segment). Curve segments set is formed by all possible curves in parameters range 0e(O,7t]° and vt [0,40] inch. After that, differential evolution (DE), which is an evolutionary global optimization method, is used to find global-time optimal trajectory from this set. The curve segments are formed in two way: a) serial expansion of the robots equations (Mclauren series) and b) fuzzy (BM)/ artificial neural networks (YS A). A derivative free optimization method DE has some advantages: initial random values are not affect the solution, there is no need to derivatives of the objective function, it is possible to use the exact equations which defines the problem and BM/YSA models can be used. The constraints are included in the selection stage instead of objective function in the DE, which is more effective than the other evolutionary methods. In this approach, there is no need extra control parameters which are determined by trial and error method. The most important disadvantage of the evolutionary methods is long optimization time. Partially overcoming this problem: - A new selection stage faster than Lampinen's selection stage is proposed. - Parameter search space is narrowed by means of determining the parameter upper values by BM/YS A. - And YSA/BM models instead of serial expansion of the robot's equations are used to form the curve segments (the calculation time is decreased to approximately 1/7). Thesis most important contribution is to propose a novel global-time optimal trajectory planning method. In this study a program is developed by using LEDA (library of efficient data and algorithms) and Nomad 200 C1-1" libraries. The obtained results are applied to Nomad 200 successfully.
Benzer Tezler
- Quadruped locomotion reference synthesis with central pattern generators tuned by evolutionary algorithms
Dört bacaklı robotlar için evrimsel algoritmalar kullanılarak merkezi örüntü üretimi yöntemiyle yürüme referansı ayarlanması
ÖMER KEMAL ADAK
Yüksek Lisans
İngilizce
2013
Mekatronik MühendisliğiSabancı ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
DOÇ. DR. KEMALETTİN ERBATUR
- Multi – objective trajectory tracking for an autonomous mobile robot in dynamic environments using evolutionary algorithms
Dinamik ortamlarda otonom hareketli bir robot için evrimsel algoritmalar kullanarak çok amaçlı yüzey takibi
MAHYAR TEYMOURNEZHAD
Yüksek Lisans
İngilizce
2023
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Kültür ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. ÖZGÜR KORAY ŞAHİNGÖZ
- Otonom mobil robotlar için metasezgisel yöntemler kullanılarak yol planlama algoritmasının geliştirilmesi
Development of path planning algorithm using metaheuristic methods for autonomous mobile robots
YUNUS TEZEL
Yüksek Lisans
Türkçe
2024
Mekatronik MühendisliğiKocaeli ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ SUAT KARAKAYA
- Real-time simultaneous localization and mapping of mobile robots
Mobil robotlarda gerçek zamanlı eşzamanlı lokalizasyon ve haritalama
BAŞAR DENİZER
Yüksek Lisans
İngilizce
2008
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiMekatronik Mühendisliği Ana Bilim Dalı
YRD. DOÇ. DR. ERDİNÇ ALTUĞ
- Mobil robotlarda parçacık filtresi kullanarak eş zamanlı lokalizasyon ve haritalama
Simultaneous localization and mapping for mobile robots with particle filters
ALİ KULELİ
Yüksek Lisans
Türkçe
2009
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Mühendisliği Ana Bilim Dalı
PROF. DR. HAKAN TEMELTAŞ