Path planning algorithm development for unmanned aerial and ground vehicles

Abstract

The usage areas of robots are increasing day by day, mainly mobile robots, robotic arms, storage robots, robots that cook food. With this increase, more optimal and robust robots are needed in various technical subjects. We can group these needs as follows: localization, mapping, path planning, trajectory tracking, dynamic and static obstacle avoidance. If we briefly explain the general definitions, firstly, localization can be defined as the robot's estimation of its own position in variable environmental conditions with various sensor data. Map is created as a result of detecting the objects in the environment and keeping the places of these objects in memory during the vehicle movement. The other topic is road planning and it is defined as the set of locations obtained in order to travel a safe route between the starting and goal point. The other topic is the path tracking which provides control signals to be followed in order to follow the route with the minimum possible error. Finally, dynamic and static obstacle avoidance can be defined as predicting the obstacles that a robot may collide with during its movement and updating the route to be . Among the above-mentioned areas, road planning was chosen as the main thesis topic. In this context, path planning algorithms can basically be grouped under 3 categories, these are geometric based algorithms, tree search algorithms, machine learning algorithms and sampling based algorithms. The advantages and disadvantages of these algorithm groups are differentiated within themselves. In this thesis study, sampling based algorithms were studied. The RRT algorithm, which is the most basic of sampling based algorithms, was first examined. This algorithm ensures that the points are connected to each other without any cost optimization. Afterwards, the RRT* algorithm was proposed and this algorithm provides an optimal combination of points by cost optimization and is called rewiring tree. But the biggest disadvantage of this algorithm is that it examines all possible points of the map. Informed RRT* algorithm actually showed that the result can be reached much faster when possible path optimization is made in the form of ellipses on the areas of interest. However, where this algorithm is insufficient is that the ellipse created has a high eccentricity, so the ellipse area loses its meaning and covers the whole map. Then, the method we propose, the road is divided into n slices. These slices are randomly optimized with the help of the rewiring tree, which is a feature of the RRT* algorithm. Thus, even on roads with high eccentricity, it can reach the optimal result in a shorter time. Various maps were determined in the simulation and a consistent comparison was made by keeping the simulation parameters constant. As a result, a high rate of success has been achieved.