Path Tracking Methodologies For Mobile Robots

Abstract

Mobil robotlar dünyasında, iç ve dış ortamda çalışabilen fazla sayıda robot çeşidi bulunmaktadır ve bu robotların yapım sistemi, tekerleklerin yapım şekli ve robot üzerinde konumu birbirinden farklı olmaktadır. Bu farklılıklar, robotların çalışma şeklinde önemli rol oynamaktadır. Tekerleklerin formu ve yapısı, robotların özgürlük derecesinin artmasına sebep olur ve özgürlük derecesi arttıkça, daha kesin ve verimli yol takip metotları çıkartmaya yardımcı olur. Ayrıca, robotların yapım şekli, örneğin tekerlek adeti, tekerlek tipi, yönlendirme kabiliyeti ve manevra yeteneği robotların davranışında çeşitli rol oynamaktadır. Dolayısıyla, çeşitli robot yapı şekilleri tanıtılacak ve tez konusu olan robot yapısını sonraki bölümlerde tanıyacağız. Birinci bölümde, robotlar dünyasına bir tanıtım gerçekleştiriyoruz ve bu konuda literatür taraması yapacağız ve sonra yapılan geliştirmeleri mercek altına alacağız. İkinci bölümde, ilk matematiksel olarak robot çerçevesi ve dünya çerçevesi arasında olan ilişkiyi anlatacağız, sonra çeşitli tekerlek yapıları ve davranışlarını tanıyacağız. Daha sonra, farklı robot yapım sistemlerini göreceğiz. Bu sistemlerden bazıları: diferansiyel tahrik robot, Ackerman tahrik robot ve Omni yönlü tahrik robot vs olmaktadır. Araştırmamızda kullanacağımız robot tipi, çift düzenlenebilir standart tekerlekli (Two Steered Standard Wheels) standart diferansiyel robot olmaktadır. Üçüncü bölümde, yol planlaması metotları tanıtılacaktır. Planlama metotları, robotu en kısa yoldan ve en hızlı şekilde başlangıç noktasından varış noktasına ulaştırmaya yardımcı olacaktır. Robotun izleyeceği yol haritası ne kadar karmaşık ise, robotun doğru yolu bulması ve varış noktasına varması daha fazla zaman alıcı olup ve neticede daha fazla batarya (pil) kullanımına yol açmaktadır. Bu engeli aşmak için, daha mantıklı ve verimli yol planlama algoritması oluşturmak gerek. Robota daha kesin bir yol planı uyguladığımızda, daha akıcı ve daha az zaman harcayarak hiçbir duvar veya engele rastlamayacak şekilde varış noktasına varacaktır. Dolayısıyla, en basit, en eski, en verimli ve en yeni algoritmalardan oluşan çeşitli yol planlama algoritmalarını tanıtıp ve sonunda bu araştırmada kullandığımız yol planlama metodunu tanıyacağız. İlk olarak Dijkstra’s ve A* metotları tanıtılacaktır. A* metodu, Djikstra’s ve Ağırlıklı Graf metotlarını kullanarak robot için en verimli yolun bulunmasına yardım etmektedir. Bu metot, hareket maliyeti olan g(n) ve h(n) parametrelerini kullanmaktadır. Robotun şimdiki konumundan başlangıç noktasına kadar olan maliyet g(n) ve h(n) şimdiki konumundan varış noktasına olan maliyet olmaktadır. Bu iki maliyeti topladığımızda, maliyet fonksiyonu olan f(n) elde edilir. f(n) robotun şimdiki konumunun etrafında olan hücrelerden en verimli hücreyi belirler. Her ne kadar maliyet az olursa, A* metodunda daha öncelikli olmaktadır. Bahsi geçen metot bilinen çevrelerde kullanılmak için çok iyi bir metot. D* metodu, buluşsal metodunu kullanarak, kısmen bilinen çevrelerde yol planlamasına yardımcı oluyor ve A* metodunu kullanarak, başlangıç noktasına geri dönmek için engelsiz ve çarpışmasız bir yol bulmak için kullanılıyor. Sonra, Görünürlük Graf metodunu tanıyacağız. Bu metot ’da ikizkenar haritası kullanarak, birbirini tanımlayabilen görünebilir noktalar yardımı ile optimum ve en kısa yol planlaması yapılıyor. Daha sonra, hücre bozuşma metodunu tanıyacağız. Bu metot ’ta robotun yapısı ve etrafındaki engeller poligon şeklinde düşünülür. Eğer robotu bir nokta farz edersek, en kısa bulduğunda hiçbir engele takılmadan rahatça çevrede dolaşabilir ve varış noktasına varır. Ama eğer robotu poligon şeklinde düşünüp ve robot üzerinde bir noktayı referans nokta olarak farz edersek, durum değişir ve robot yolu bularken engellere çarpabilir. Dolayısıyla, robot ölçülerini baz alarak, çarpmayı önlemek için engeller ve duvarlara enflasyon (şişme) uygulamak zorundayız. Daha sonra hücre dağılma metodunu tanıyacağız. Bu metot’ta tüm harita hücrelere bölünüyor ve her hücre en verimli ve kısa yolun bulunmasında mobil robota yardımcı oluyor. En son, bu araştırmada kullanılan olasılıklı yol haritası metodunu tanıyacağız. Bu metot, yapılandırma uzayında, olasılık üzere noktaları seçip ve birbirine bağlayarak robotun takip etmesi için birkaç yol belirler. Noktaların sayısı belirlenebilir. Bu metot diğer metotlara nazaran daha basit ve karmaşık çevrelerde kullanılabilir bir metot olmaktadır. Dördüncü bölümde, önceki bölümde tanıtılan yol planlama metotları en verimli yolu bulmak ve varış noktasına ulaşmak için robot üzerinde uygulanıyor. Çeşitli metotlar tanıtıldı; follow-the-carrot, Saf Takip, ve Vektör Takip metotları. Follow-the-carrot metodu, varış noktası ve ona varan noktaların koordinatlarını buluyor. Bu metot literatür ’de basit olarak biliniyor ve çok kullanışlı bir metot olmamaktadır. Bunun nedeni ise, direk olarak robotun önünde olan mesafeyi ölçerek yol planını çıkartması ve robotun takip edeceği yörüngeyi kayde almaması. Ama Saf Takip metodu, önündeki mesafeyi yolu takip etmek için kullanıyor. Bu metot’ta, robotun yolunu bulması için gerekli yay hesaplanıyor ve robot tekrar yola dönmek için bu yayı kullanıyor. Bu değerler, iki değişken ile belirlenir, birincisi varış noktasının konumu olan (x) ve diğeri robotun merkezinden varış noktasına olan (L) mesafesi. Bu iki metot, robotun yönünü varış noktasında kayda almıyorlar, hal bu ki üçüncü metot yani Vektör Takip metodu, saf takip yöntemini kullanmasının yanında, robotun yönünü de varış noktasında ayarlıyor. Vektör takip metodu, vida teorisini kullanmaktadır. Vida teorisi, 1900 yılında Sir Robert S. Ball tarafından öne sürülmüş ve katı gövde dinamiğin’de katı gövdenin merkezinde olan çizgilerin geometrisi için, kinematik ve statik olarak matematiksel formüller üretmiştir. Katı gövdenin her hareketi, merkezinden çıkan çizgilerin rotasyonu üzerinden anlatılabilir. Beşinci bölümde, MATLAB ortamında çeşitli metotların simülasyonları yapılıyor. Yol haritası çıkartılıyor ve MATLAB ortamına uygulanarak robotun yolu izlemesi ve varış noktasına varması simüle ediliyor. Lineer hız, keskin virajlarda robotun davranışlarında çok önemli rol oynamaktadır. Hız yükseltikçe, virajda aşım da yükseliyor ve robot virajda kesinliğini kaybediyor. Ama, düşük hızlarda, robot virajları daha kesin bir şekilde takip ettiğini görüyoruz. PRM metodunu kullanarak istenilen yol haritasını bulduktan sonra, en önemli nokta bulunan yolu en iyi şekilde nasıl takip edilmesidir. Önceden bahsedildiği gibi, lineer hız ve öndeki mesafe, yol takibi işleminde en önemli iki faktör olmaktadırlar. İki senaryo hakkında bahsedilecektir; Birinci senaryoda, robotun öndeki mesafesini 0.5m sabitleyip ve lineer hızı değiştirerek (0.5, 1, 1.5 ve 2m/s) çeşitli hızlarda robotun davranışlarını ve hata diyagramını, Saf Takip ve Vektör Takip Metotlarında incelenecektir. Her iki metotta, belirlediğimiz dört hız için Standart sapma hatası gösterilecektir. Sonuçlara baktığımızda, sabit ön mesafede, hız yükseldikçe Saf Takip metodunun standart sapma hatası da yükseliyor ve bu olay bu metot için bir dezavantaj olmaktadır. Mesela robot bir tepe inişinde, hızlandığında ve ya 2m/s hızını aştığı zaman hata oranı affedilmeyecek ve göz ardı edilmeyecek şekilde yüksek olacaktır. Diğer yandan, vektör takip metodunda, yolun tamamında standart sapma oranı yaklaşık olarak sabit olmaktadır ve robot kararlı bir şekilde yolu izlemektedir. İkinci senaryoda, robot hızı 1.5m/s olarak sabitlenip ve ön mesafe (0.5 , 1 , 1.3 , 1.7m) olarak değiştirilmektedir. Bu senaryoda da Saf Takip ve Vektör Takip sonuçlarına baktığımızda, Vektör Takip için standart sapma hatası yolun tamamında neredeyse sabit olmakta ama Saf Takip metodunda, ön mesafe arttıkça, hata ve aşım oranları da aşırı derecede artmaktadır. Altıncı bölümde, tez içinde yapılan araştırmaların sonuçları ve bu konu üzerine gelecekte ne araştırmalar yapılabilir belirtilmiştir. Simulink sonuçları Vektör Takip metodunun Saf Takip metoduna göre daha güçlü ve daha verimli bir metot olduğunu göstermektedir. Ayrıca, Vektör Takip metodu, robot yolu daha kesin ve pürüzsüz şekilde takip etmektedir. Vektör Takip metodunun matematiksel karmaşıklıklarına rağmen, diğer metotlara tercih edilmektedir.

In the world of robots, there are several types of mobile robots that are able to work in indoor or outdoor environments. Their structure are different from each other as the type of wheels or their architecture of positioning on the robot differs. In chapter one, an introduction of robot world and what is done in literature survey is discussed and the development that is done in this plane is introduced. In chapter two, firstly the position of the robot`s frame with respect to the world frame is defined with its related formulation, then a brief introduction of different kinds of wheels and their behavior is introduced. Later on some different kind of robots are introduced such as differential drive robots, Ackerman drives, omni directional drives and so on. In chapter three, path planning methods are introduced. These methods helps the robot to find the most optimize and short path to reach its final destination from its current initial point. Using a suitable method and the most optimized one is a main factor in path planning. The more complicated the path planning is, much time is used for the robot to reach its destination and therefore it will be a time consuming procedure and the percentage of battery usage will increase. To overcome these drawbacks one should think of a logical path planning algorithm to implement to the robot and lead it in a smooth and time saving way to the destination without colliding any obstacles or walls in its way. So some algorithms from the most simple and old one to the most recent and optimized ones are introduces and at the last part the path planning that is used in this thesis will be presented. First Dijkstra`s and A* methods are introduced. A* used Dijkstra`s method and uses weighted graphs to help robot through the most efficient path. It uses the movement costs g(n) and h(n) which are the cost from the current position of the robot to the initial point and the cost from the current position of the robot to the goal point respectively. Summing up these costs leads to cost function f(n) which determines the most efficient node to select among the cells which are around robot`s current location. The less the cost is the more priority it has in A* method. The previous method was good in known environments. D* method uses heuristic method in partially known or unknown environments in path planning and uses A* method backwards from destination to the current point in each step to find an obstacle free or no collision with walls, way. After that visibility graph method is introduced which uses Trapezoidal map to find an optimum short path using visible nodes who see each other. In this method the shape of robot and obstacle are also considered as polygons. If we consider our robot as a point robot then the robot can move freely in our space by defining the shortest path and will never collide the obstacles. However, if our robot is a polygon robot, and we have considered a point in the robot as a reference point, then there is a change that the robot collides with obstacles in this path. So due to the dimensions of the robot, an inflation should be implement to the walls and obstacles to avoid the collision. Afterwards, cell decomposition method introduces a method that separates the whole map into cells and uses those cells to find a suitable road map for the mobile. At the end the probabilistic road map method which is used in this thesis is introduced. This method uses probabilistic node selection in configuration space and by connecting these nodes together finds a bunch of roadmaps for the robot to follow. The number of nodes can be selective. This method is less complicated with respect to other methods so it can be used in much complex environments. In chapter three, path planning methods are introduced. These methods helps the robot to find the most optimize and short path to reach its final destination from its current initial point. First Dijkstra`s and A* methods are introduced. A* used Dijkstra`s method and uses weighted graphs to help robot through the most efficient path. Then previous method were good in known environments. D* method uses heuristic method in partially known or unknown environments in path planning and uses A* method backwards from destination to the current point in each step to find an obstacle free or no collision with walls, way. After that visibility graph method is introduced which uses Trapezoidal map to find an optimum short path using visible nodes who see each other. Afterwards, cell decomposition method introduces a method that separates the whole map into cells and uses those cells to find a suitable road map for the mobile. In chapter four, the robot uses path planning method introduced in the previous chapter for path tracking and reach its destination. Different kinds of methods have been introduced namely; follow-the-carrot, pure pursuit and vector pursuit methods. Follow the carrot method finds the coordination of final point and points directly toward it. This method is a simple method in literature and it is not so practical because it follows the look ahead distances directly with a straight line, without considering the trajectory to be followed. Pure pursuit method, however, uses look ahead distance for following the trajectory. It computes the arc necessary for the robot to find its ways and come back to the road. This values depends on two elements, first one, the x position of the goal point and the second one distance from center of robot to the goal point ,L.These two methods does not consider the orientation of the robot at the goal point, however the third method, vector pursuit, obeys from pure pursuit method but also considers the orientation of the look-ahead distance of robot. Vector pursuit uses screw theory which was introduced by Sir Robert S.Ball in 1900, the method is developed for applications in kinematics and statics of rigid body and provides a mathematical formulation for the geometry of lines which are central to rigid body dynamics. Any motion of the rigid body can be described as a rotation about a line in space with an associated pitch. In chapter four, the robot uses path planning method introduces in the previous chapter to for path tracking and reach its destination. Different kinds of methods have been introduced namely; follow-the-carrot, pure pursuit and vector pursuit methods. Follow the carrot method finds the coordination of final point and points directly toward it. Pure pursuit method, however, uses look ahead distance for following the trajectory. These two methods does not consider the orientation of the robot at the goal point, however the third method, vector pursuit, obeys from pure pursuit method but also considers the orientation of the robot at its destination. In chapter five, simulations have done in MATLAB using path tracking method, a road map has been constructed, later on the robot pursuits that path using MATLAB codes and find destination. The linear velocity in path tracking has an important impact on the behavior of the robot in sharp corners. As speed increases the overshoot in corners also increase and robot has a less accuracy in sharp corners. However, for the low speeds, it can be seen that the robot pursuits the corners in a more accurate way. Using PRM method and finding desired roadmap, the main problem now is to pursue this road in a most perfect way. As mentioned the impact of linear velocity and look ahead distance has a major role in path tracking. Two scenarios are discussed here. The first scenario is considering a constant look ahead distance of 0.5 meter and changing the linear velocity of the robot ( 0.5, 1, 1.5 and 2 m/s) to see the difference between them and approach the diagram of error between these velocities for both pure pursuit and vector pursuit methods. The standard deviation error of these four velocities for two methods of pure pursuit and vector pursuit are depicted. The results Show that by increasing velocity of the robot for a constant look-ahead distance the standard deviation error for he pure pursuit increases, and this is a flaw for this method because imagining a more increased velocity for the robot as coming down the hill and gaining velocities more than 2 m/s the results of the error will be very dramatic and un unneglectable. On the other hand, for vector pursuit method Standard deviation error is almost constant all over the road and much stability can be seen during following the path. The second scenario in considering a constant velocity of 1.5 m/s and changing look-ahead distances as 0.5, 1, 1.3 and 1.7 meters. Sketching standard deviation error for pure pursuit and vector pursuit methods for this scenario also results that for vector pursuit method standard deviation error remains almost constant all over the road, on the other hand large overshoots and errors appear by increasing the look-ahead distance. In chapter five, simulations have done in MATLAB using path tracking method, a road map has been constructed, later on the robot pursuits that path using MATLAB codes and find destination. The linear velocity in path tracking has an important impact on the behavior of the robot in sharp corners. As speed increases the overshoot in corners also increase and robot has a less accuracy in sharp corners. However, for the low speeds, it can be seen that the robot pursuits the corners in a more accurate way. In chapter 6, conclusion is made of what is done in this thesis and what can be done in future studies is mentioned. The simulink results shows that the pure pursuit method Works weaker than vector pursuit method in path tracking methodologies, and results in higher errors but vector pursuit method is much smoother and the accuracy of following the path for this method is higher. Despite the complexity of mathematical calculations of the vector pursuit, this method is preferred to other ones.