Hızlıca keşfeden rastgele ağaç yöntemi ile insansı robot kolu yörünge planlaması
Trajectory planning of a humanoid robot arm by using rapidly-exploring randomized tree method
Yazar: BURAK BOYACIOĞLU
Danışman: PROF. DR. ŞENİZ ERTUĞRUL
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Makine Mühendisliği Ana Bilim Dalı / Sistem Dinamiği ve Kontrol Bilim Dalı
Derece: Yüksek Lisans, 2016
Konu: Makine Mühendisliği = Mechanical Engineering
Dizin: Robot manipülatörleri = Robot manipulators

Özet:
Bir robotik sistemin ya da bir otonom aracın bir konumdan bir başka konuma hangi yolu, hangi hız ve ivme profilleri ile izleyeceğinin belirlenmesi, yörünge planlama olarak tanımlanmaktadır. Yörünge planlama, robotiğin en çok çalışılan konularından biri olmakla beraber bu problem için tek, kesin ve optimum bir çözümden söz edilemez. Bu durum, küresel engellerden sakınılması gereken senaryolar için de aynen geçerlidir. Hatta problemin daha da karmaşıklaşması kaçınılmazdır.
Yörünge planlama için önerilen yöntemler temel olarak belirlenimci ve rastlantısal olarak ikiye ayrılabilir. Belirlenimci yöntemler genellikle eksiksiz olmakla birlikte, planlama uzayının boyutları arttıkça hesaplama maliyetinin artmasından muzdarip olacaktır. Öte yandan, rastlantısal yöntemler tüm olası çözümleri değerlendirmez.
Yörünge planlama için bulanık mantık kontrolden yapay sinir ağlarına, karınca kolonisinden  genetik algoritmalara çeşitli yöntemler kullanılmış; ancak rastlantısal yöntemler arasında örnekleme tabanlı sezgisel algoritmalar sade olmaları ve hesaplama maliyetlerinin düşük olması sebebiyle kabul görmüştür. Bu yöntemlerden en yaygın olanları Olasılıksal Yol Haritası, Rastgele Potansiyel Alanlar ve Hızlıca Keşfeden Rastgele Ağaç algoritmaları ve onların türevleridir.
Başlıca örnekleme tabanlı planlama algoritmaları için eksiksizlikten söz edilemez. Yani bir çözüm olmadığı takdirde, bu yöntemler ile çözümsüzlük durumu tespit edilemeyecektir. Dolayısıyla örnekleme için ya örnek sayısı ya da örnekleme süresinin sınırlandırılması gereklidir. Öte yandan yeterince örnekleme yapıldığı takdirde, uygulanabilir bir çözüm mevcut ise bunu bulmayı vaat eder yani olasılıksal olarak eksiksizdir.
Örnekleme tabanlı algoritmalar; önceden seçilecek bir ölçeve göre hangi örneklerin birbirine bağlanacağını belirlemek, başlangıç noktasından hedef noktaya hangi hız ve ivme profillerini takip ederek ulaşacağını planlamak, planlanan yol için çarpışma sınaması yapmak gibi alt fonksiyonlar ile birlikte çalışır.
Bu çalışmada, 6 serbestlik dereceli ITECH İnsansı Robot'una ait kolun küresel engellerden kaçan yörünge planlamasını yapmak üzere, öncelikle, Hızlıca Keşfeden Rastgele Ağaç yöntemi geçiş noktalarını belirlemek üzere çağrılmıştır. Planlama uzayı olarak, eklemlerin bulunduğu konfigürasyon uzayı kullanılmış olup bu sayede ters geometri ve ters kinematik hesaplarından kaçınılmıştır. Görev uzayında olan hedef noktanın da konfigürasyon uzayına aktarılması yerine, konfigürasyon uzayında oluşturulan ağacın görev uzayındaki izdüşümünün hedef noktaya yeterince yakın oluncaya dek genişlemesi istenmiştir. Bunun için, konum ve yönelim toleransları tanımlanmıştır.
Hızlıca Keşfeden Rastgele Ağaç yöntemi ile bağlanabilirlik yolu elde edildikten sonra, yerel planlayıcı alt fonksiyonu olarak her bir geçiş noktası arasına kübik yörünge eğrileri uydurulmuştur. Bunun için, manipülatörlere özgü bir çalışmadan yararlanılmıştır. Eklem konumlarının kübik eğrilerle ifade edilmesi; eklem hız profillerinin karesel, eklem ivme profillerinin ise doğrusal olması anlamına gelir. Bir başka deyişle bu yaklaşımla; konum, hız ve ivme profillerinde süreklilik sağlanmış olur.
Bir sonraki aşamada, hareketin toplam zamanının maliyet fonksiyonu olarak ele alındığı kübik eğrilerin optimizasyonu yapılmış ve bu işlem gerçekleştirilirken sadece sınır koşulları değil; hız, ivme ve sarsım sınırları da dikkate alınmıştır. Optimizasyon algoritması olarak, Nelder-Mead arama yöntemi kullanılmıştır.
Çalışma, yörünge süreklileştirmenin açıkça anlatılması, verilen geçiş noktaları için zaman optimizasyonu yapılması ve sarsımın sınırlandırılması açılarından önceki çalışmalardan farklılık gösterdiği için literatüre katkı niteliğindedir.
Süreklileştirme işlemini takiben, yörünge üzerinde çarpışma sınamaları yapılarak sadece uç eyleyicinin değil, tüm robot kolun engellere çarpmadan bir hareket sergilemesi sağlanmıştır.
Kullanılan Hızlıca Keşfeden Rastgele Ağaç algoritması, rastgeleliğe dayalı olduğu için her çalıştırılışında farklı sonuçlar vermektedir. Bu çalışmada, önceden verilen sınır koşulları ve kinodinamik kısıtlar göz önünde bulundurularak elde edilen çok sayıda uygulanabilir yörüngeden yalnız biri örnek olarak sunulmuş ve hareket görselleştirilmiştir.
Hareket için gerekli torklar, dinamik kararlılık ve manipülatörün kontrolü gibi dinamik hususlar bu çalışmanın merkezinde yer almamış olup sadece elde edilen yörüngenin robota nasıl beslenebileceğine bir örnek olarak, yaklaşık hesaplanmış tork denetleyicisinin kullanıldığı bir benzetim, sonuçlarıyla paylaşılmıştır. Benzetimde Coriolis etkileriyle viskoz ve dinamik sürtünmeler modellenmemiş olmasına karşın planlanan yörüngenin çok küçük bir hata ile takip edilebildiği görülmüştür.
Çalışmanın devamı için öneri olarak başka optimizasyon algoritmalarının denenerek sonuçların Nelder-Mead yöntemindeki ile karşılaştırılması, çalışmada kullanılan yerel planlayıcının dinamik Hızlıca Keşfeden Rastgele Ağaç yöntemine uyarlanması ve algoritmanın asimptotik olarak optimum olan sürümü için denenmesi sunulmaktadır.
Hızlıca Keşfeden Rastgele Ağaç yaklaşımının alt fonksiyonları tek tek alınacak olursa; uzaklık ölçevi olarak geleneksel olan Öklid mesafesi yerine Mahalanobis mesafesi gibi diğer seçenekler denenebilir, kullanılan en yakın komşu algoritması yerine ise yaklaşık en yakın komşu algoritmaları kullanılarak planlayıcı hesaplama süresi kısaltılabilir. Ayrıca daha yörünge süreklileştirme aşamasına geçmeden önce, görüş hattı yaklaşımlarından yararlanılarak robotik sistemin eylemi gerçekleştirme zamanı da düşük bir hesaplama maliyeti karşılığında büyük ölçüde azaltılabilir.
Çalışmada süreklileştirme için önerilen yaklaşım, Olasılıksal Yol Haritası ve Rastgele Potansiyel Alanlar gibi bağlanabilirlik yolu veren diğer algoritmalar için aymen çağrılabilir ve yöntemlere özgü olarak elde edilecek sonuçlar değerlendirilebilir.
Son olarak, montaj aşamasında olan robot kolu çalışır duruma geldiğinde geliştirilen yaklaşımın deneysel olarak da test edilmesi ve elde edilecek sonuçların benzetimden elde edilenle kaşılaştırılması planlanmaktadır. Önerilen tüm yaklaşım seçenekleri kapsamlı bir çalışma ile deneysel ve benzetim sonuçlarıyla derlenebilir.

Abstract:
The determination of the motion of a robotic system or an autonomous vehicle from one position to another following which path, what velocity and acceleration profiles is defined as trajectory planning. Although trajectory planning is one of the issues of robotics that is most studied on, it is not possible to talk about a unique and optimum solution for this problem. This also goes for scenarios that necessitate avoiding global obstacles. In fact, the problem inevitably becomes more complex.
A wide range of studies exists in path planning including both deterministic and stochastic approaches. Deterministic ones such as evaluating all possible configurations in discretized configuration space are available and they are generally complete which means they give an exact solution in a finite amount of time. However, these methods are usually computationally inefficient for high-dimensional spaces and as a matter of fact, they often fail since they generally give one possible solution which can be infeasible.
Different methods have been used for trajectory planning, such as fuzzy logic control, neural networks, ant colony optimization, genetic algorithms; but among stochastic methods, sampling-based heuristic algorithms have been accepted due to the fact that they are simple and the cost of calculation is low. The most common ones of these methods are Probabilistic Roadmap Method, Randomized Potential Fields and Rapidly-exploring Randomized Tree algorithms and their derivatives.
We cannot talk about completeness for the main sampling-based planning algorithms. In other words, unless there is a solution, it won't be possible to determine a no-solution-situation with these methods. Therefore, for sampling, it will be necessary to limit either the number of samples or the period of sampling. On the other hand, if enough number of samplings is done, a feasible solution -if there is one-, will be found; meaning, it is probabilistically complete.
Sampling-based algorithms work together with sub-functions, such as determining which samples will connect with each other according to a pre-selected metric, planning the velocity and acceleration profiles it will use to go from the starting point to the target point and making collision checks for the planned path.
In this study, first of all, Rapidly-exploring Randomized Tree method has been called upon for the obstacle avoided trajectory planning of the six-degree-of-freedom ITECH Humanoid Robotic arm.
As planning space, the configuration space where the joints are, have been used, thus the calculations of inverse geometry and inverse kinematic have been avoided. And instead of transferring the target point from the task space to the configuration space, it should be determined that the projection of the expanding tree in the configuration space onto the task space is near enough to the target position. In order for this to occur, position and orientation tolerances have been defined.
After obtaining the connectivity path through Rapidly-exploring Randomized Tree method, cubic polynomial joint trajectories have been calculated between each viapoint as a local planner sub-function. For this, a study carried out for manipulators has been used as a reference. The expression of joint positions with cubic splines means that joint velocity profiles are quadratic whereas joint acceleration profiles are linear. That is to say, with this approach, position, velocity and acceleration profiles are continuous.
In the next step, the optimization of the cubic trajectories, where the total time of the motion has been dealt with as the cost function, was done; and during this process not only boundary conditions but also velocity, acceleration and jerk limits were considered. Nelder-Mead search method was used as an optimization algorithm.
This study is a contribution to the literature due to the fact that smoothing of the trajectory given by Rapidly-exploring Randomized Tree method is clearly defined, time optimization for the given viapoints is done and jerk is limited.
Following the smoothing process, collision checks are done on the trajectory in order to enable both the end-effector and the whole robotic arm to move without hitting obstacles.
The Rapidly-exploring Randomized Tree algorithm that has been used, gives different results every time it is called upon as it is based on randomness. In this study, the pre-given boundary conditions and kinodynamic constraints have been taken into consideration, and from the many feasible trajectories only one has been presented as an example, and the motion has been visualised.
Dynamic issues such as the torques that are necessary for the motion, dynamic stability and the control of the manipulator have not taken place at the center of this study. In order to show how the obtained trajectory can be fed into the robot; the simulation results, where an approximate torque controller has been used, were shared. In the simulation, although Coriolis effects and viscous and dynamic frictions have not been modelled, it has been observed that the planned trajectory can be tracked with a very small position error.
For the future studies, it has been suggested that other optimization algorithms be called and the results compared with those of the Nelder-Mead method, the local planner used in the study be adapted to the dynamic Rapidly-exploring Randomized Tree method, and the algorithm be called for the asymptotically-optimal version of the method.
If the sub-functions of the Rapidly-exploring Randomized Tree approach were to be dealt with one by one; instead of the traditional Euclidean distance, other alternatives such as Mahalanobis distance can be tried, and instead of the nearest neighbour algorithm that has been used, approximate nearest neighbour algorithms can be used to reduce the calculation time of the planner.
Additionally, before the smoothing phase, line-of-sight approaches can be used and thus the time required for the robot to carry out the action can be greatly reduced with a low calculation cost.
The approach suggested in the study for the smoothing, can be called in a similar way for other algorithms such as Probabilistic Roadmap Method and Randomized Potansiyel Fields that give connectivity path, and specific results that will be obtained by these methods can be evaluated.
Lastly, when the robotic arm, which is at the assembly stage, is working, we plan to test the approach that has been developed and compare the results with those obtained by simulation. All the approach alternatives suggested can be compiled with experimental and simulation results in a comprehensive study.