Mobile Robot Navigation Systems

Tez (Yüksek Lisans) -- İstanbul Teknik Üniversitesi, Fen Bilimleri Enstitüsü, 2016Thesis (M.Sc.) -- İstanbul Technical University, Institute of Science and Technology, 2016Mobil robotlarda hareket planlama problemi birçok birbiri ile bağlantılı problemi kapsamaktadır. Mobil robotun çevreyi algılaması, bu algılamalardan çalıştığı ortamı keşfetmesi, bu keşfettiği ortamda algılayıcılar vasıtasıyla kendi konumunu kestirmesi, başka bir konuma gitmesi için takip etmesi gereken yörüngenin hesaplanması ve bu yörüngeyi güvenli bir şekilde takip etmesi bu problemlere örnek olarak gösterilebilir. Bu sebeple farklı algılayıcı, robot ve ortam çeşitliliğine sahip robotik sistemlere özel navigasyon yöntemleri ortaya atılmıştır. Bu çalışmada ilk olarak, diferansiyel sürüş sistemine sahip mobil robot platformu ile haritanın bilindiği kapalı bir ortamda iki boyutlu derinlikli tarama bilgisi yardımıyla robotun harita üzerindeki konumunun belirlenmesi ve harita üzerindeki başka bir noktaya ulaşacak yörüngenin planlaması gerçekleştirilmiştir. Daha sonra bulunan yörüngelerin Pure Pursuit yöntemi ile takip edilmesi gerçekleştirilmiştir. Ayrıca daha sonra robotun haritada bulunmayan engellere çarpmasını önlemek amacıyla, iki boyutlu tarama bilgisi ile çalışan engelden kaçınma yöntemi geliştirilmiştir. Engelden kaçınma yönteminin yol planlama yöntemi ile birlikte uyum içinde çalışması gerçekleştirilmiştir. Robotun konumunun kestirilmesi robotun kinematik hesaplarından kaynaklanan hataları azaltmak amacıyla kullanılmıştır. Mobil robotun kendi algılayıcıları (enkoder,imu) yardımıyla elde ettiğimiz veriler, tekerleklerdeki kayma ve eylemsizlik gibi etkiler ilk olarak küçük konum belirsizlikleri oluştursa da zamanla bu belirsizlikler toplanarak artmaktadır. Konum belirsizliği, mobil robot üzerindeki Microsoft firmasına ait Kinect algılayıcısı kullanılarak konumlandırma yöntemi yardımıyla azaltılmıştır. şimdiye kadar harita üzerinde konumu bilinen bir robotun yol planlaması için çeşitli metotlar geliştirilmiştir. Karmaşık ve çok boyutlu haritalar için örnekleme tabanlı planlayıcılar önerilmiştir. Robotun kinematik kısıtlarını hesaba katıp, aynı zamanda kademeli olarak bulunan yolu kısaltmaya çalışan RRT* yöntemi popüler örnekleme tabanlı planlayıcılardan birisidir. Bu yöntem sayesinde harita üzerinde robotun takip edebileceği yumuşak geçişli yollar ile bu yolları takip etmesi için gerekli kontrol girişleri bulunabilmektedir. Fakat bu kontrol girişleri yalın haliyle mobil robota uygulanırsa robotun beklenilen yoldan saptığı ve engellere çarptığı görülecektir. Ayrıca RRT* yönteminin kademeli olarak bulunan yolu kısaltmaya çalışmasından dolayı harita üzerindeki engellere teğet yollar bulması muhtemeldir. Bu yolların takip edilmesi ise ölçüm ve hareket belirsizlikleri sebebiyle robotun engellere sürtme veya çarpmasına sebep olabilir. Bu çalışmada daha güvenli yolların planlanması için daha önce ortaya atılmış olan MR-RRT* yöntemi ile benzerlik gösteren Safe-RRT* yöntemini önerilmektedir. Bu yöntem kademeli olarak yolumuzu kısaltmaya çalışırken aynı zamanda engellere yakınlığına göre yörüngeleri cezalandırarak en kısa ve güvenli yolun seçilmesini sağlamaktadır. Alınan sonuçlar karşılaştırıldığında Safe-RRT* yöntemi ile, RRT* yöntemi kadar kısa olmasa da çok daha güvenli yollar bulunabilmektedir. MR-RRT* yönteminde sadece engellere belirli bir mesafe yakındaki yörüngelerin cezalandırılması yapılırken, Safe-RRT* yönteminde ise bütün yörüngelere engellere uzaklığı ile orantılı bir cezalandırma yapılmaktadır. Bu bahsedilen yöntemler sonucu bulunan yolun çevredeki engellerin hareket etmediği ve konumlarının kesin olarak bilindiği varsayılırsa takip edildiğinde hedef noktasına varması beklenir. Yol takip yöntemleri yardımıyla bu yolların takip edilmesi sağlanabilmektedir fakat çevredeki engellerin hareketli ve konumlarının önceden bilinemediği durumlarda engelden kaçınma yöntemlerine gereksinim duyulmaktadır. Bu yöntemler robotun sensörleri yardımıyla çevreyi algılayıp engellerden kaçınarak hedefine ulaşması için tasarlanmıştır. FGM ve DWA, farklı altyapıları kullanan ve kendilerini kanıtlamış engelden kaçınma yöntemleridir. FGM, ilk olarak alınan derinlikli tarama bilgisi yardımıyla robot çevresindeki boşlukların hesaplanmasını gerçekleştirir. Daha sonra robotu hedef noktasına ulaştırabilecek güvenli yönelimin hesaplanması gerçekleştirilir. DWA yönteminde ise ilk olarak robot dinamikleri kullanılarak engellere çarpmadan durabilen, ulaşılabilir hız kümesinin hesaplanması gerçekleştirilir. Daha sonra elde edilen bu hız kümesinden, amaç fonksiyonu sonucu en yüksek değere sahip hız çifti bulunur. FGM yönteminin güvenli yönelimi, DWA yönteminin çarpışma kontrolü ve amaç fonksiyonu içerisinden gerekli görülen özellikler birleştirilerek FGM-DW yöntemi oluşturulur. Bu yeni yaklaşım, yol planlama yöntemi ile uyumlu çalışacak şekilde tasarlanmış, böylece engellerin değişken olduğu ortamlarda güvenli şekilde hedefe ulaşabilen bir navigasyon sistemi geliştirilmiştir.Mobile robot navigation problem is a widely researched area by scientists. This problem includes perception, mapping, localization, path planning and path tracking problems. Several sensors, different kinematic structures and different environmental complexities require specific solutions. Motion planning techniques are designed to find geometrically admissible trajectory pairs connecting vehicle initial position and goal location without collisions. These methods can be divided into two major parts, namely global and reactive motion planning. Global motion planning methods use priori information of obstacles and generate trajectories between initial position and goal position inside configuration space. This type of methods presume that obstacles are static and map is not updated by means of sensory information. Probabilistic roadmaps (PRMs), rapidly-exploring random trees (RRTs), potential field methods, and cell decomposition based methods belong this category. These methods are problematic in case information of obstacles are inaccurate or not available. Moreover their execution time increases exponentially as a consequence of model and world complexities. There are many proposed methods which aim to solve path planning problem. Sampling based planners are proposed for complex and multidimensional environments. These methods solve path planning problem fast by means of its randomness. RRT* algorithm takes into account the robot's kinematic constraints also gradually optimizes the path. This method yields obstacle free paths which are smoothly connected each other. It also stores the control signals which create the trajectories between points. Although this algorithm yields necessary control sequences for reaching from initial position to goal position, collisions would occur due to the wheel slippages and inertial forces. In order to avoid from these collisions, position correction with localization and path tracking algorithms should be used. In addition, it is common that RRT* algorithm finds paths which are close to obstacles due to its optimality in terms of shortest path. If these paths are directly tracked, it is possible to meet up with dangerous maneuvers. For this reason, we propose a new approach which is called Safe-RRT* in this thesis. This approximation not only finds the near optimal paths but also safer paths. We compare RRT* and Safe-RRT* approximations according to shortest path optimality and safety criterion. From the results of the experiments, it is observed that even RRT*'s path optimality is better, our proposed method finds safer paths than RRT* method. In other words if environment model and robot motion are uncertain; consequently global motion plan becomes unrealistic from the standpoint of obstacle avoidance. Reactive motion planning methods focus on changing robot maneuvers from sensory information and goal position. These methods recursively detect obstacles and avoid from them while driving the robot toward the goal point. Their key advantage over global planners is low computational complexity since these methods use only small portion of information about the environment. Reactive motion planning methods can further be divided into two types in accordance with their final output. First type of reactive motion planning methods called directional approaches, which compute the appropriate vehicle heading angle for obstacle free navigation. Artificial Potential Field (APF), Vector Field Histogram (VFH), VFH+, Nearness Diagram (ND), Obstacle Restriction Method (ORM) and Follow the Gap Method (FGM) are popular methods in this category. Potential field and vector field methods use repulsive and attractive forces which are generated by obstacles and goal point respectively. ORM uses repulsive angle sets and sub-goals, ND and FGM methods use gap arrays located between obstacles to determine the appropriate heading angle. Although these approaches efficiently generate the direction outputs, they are not sufficient for taking into account the robot dynamics. Unlike directional approaches, velocity space approaches use robot's dynamic properties in order to perform obstacle free navigation. These methods presume that vehicle travels along arcs of circles. For instance Curvature Velocity Method (CVM) calculates possible curvatures with eliminating ones which collide with obstacles. After pruning redundant ones, most appropriate velocity pair is calculated by CVM's objective function. Velocity Obstacles method (VO) uses dynamic objects velocities in its workspace. This velocities restrict robot's current velocity space. Then final velocity vector is selected among admissible velocities due to convergence measure to goal point. Dynamic window approach (DWA) considers reachable velocities within a short time interval, named as admissible velocities. This method eliminates velocity pairs which are not able to stop the robot without collision. Remaining velocity pairs evaluated by its objective function and velocity pair which has maximum value is executed by this method. In static environments, our preconditions is map, initial position and goal position are known by robot. Navigation starts with localization on the map. Secondly, path planning finds path from robot position to goal point. Lastly, path following method tracks the path founded by path planning algorithm. Robot localization is crucial for path tracking because perception data except laser scan is not enough to solve the localization problem. Encoders and inertial measurement unit (IMU) are not enough to predict position accurately because of wheel slippages and inertial force effects. In this thesis, this uncertainty is overcome by using adaptive monte carlo localization algorithm. Adaptive monte carlo localization example works well with Microsoft's Kinect sensor's scan feature. We also use ROS (Robot Operating System) features which facilitate communication between devices. ROS also has various support (e.g., tutorials, demos, drivers) for robotic applications. "Turtlebot" robotic platform is used for experimental tests of this study. Turtlebot has ROS support and has technical and software auxiliary resources. In dynamic environments, path tracking methods faces collisions due to dynamic obstacles. Reactive motion planners solve this situation by means of sensor measurements. In this thesis, we propose another method approach named as FGM-DW which uses the strongest parts of FGM and DWA together, in order to navigate the robot in configuration space. This method retrieves final heading angle from FGM method. Then it uses admissible velocity set calculation stage used as in original DWA method. Finally, it calculates the most appropriate control signal from its new objective function. In dynamic environments, the newly proposed Safe-RRT* algorithm FGM-DW approach are combined to navigate the robot.Yüksek LisansM.Sc