Tez No	İndirme	Tez Künye	Durumu
143086	Bu tezin, veri tabanı üzerinden yayınlanma izni bulunmamaktadır. Yayınlanma izni olmayan tezlerin basılı kopyalarına Üniversite kütüphaneniz aracılığıyla (TÜBESS üzerinden) erişebilirsiniz.	Mobil robotlarda evrimsel metotlar ile optimal hareket planlama / Optimal motion planning with evolutionary methods for mobile robots Yazar:SERKAN AYDIN Danışman: DOÇ. DR. HAKAN TEMELTAŞ Yer Bilgisi: İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Elektrik Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:	Onaylandı Doktora Türkçe 2003 99 s.
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ıı
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.