Mobil robot navigasyon sistemi geliştirilmesi
Mobile robot navigation systems
Yazar: AYKUT ÖZDEMİR
Danışman: YRD. DOÇ. DR. VOLKAN SEZER
İstanbul Teknik Üniversitesi / Fen Bilimleri Enstitüsü / Mekatronik Mühendisliği Ana Bilim Dalı / Mekatronik Mühendisliği Bilim Dalı
Derece: Yüksek Lisans, 2016
Konu: Mekatronik Mühendisliği = Mechatronics Engineering

Özet:
Mobil 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.

Abstract:
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.