A Path Planning Algorithm for Mobile Robots

Publisher:诗意世界Latest update time:2010-08-11 Source: 自动化技术与应用 Reading articles on mobile phones Scan QR code
Read articles on your mobile phone anytime, anywhere

1 Introduction

The path planning problem of a mobile robot refers to finding an appropriate motion path from a given starting point to an end point in a working environment with obstacles, so that the robot can safely and collision-freely bypass all obstacles during the movement [1].

Collision-free path planning for robots in obstacle environments [2] is one of the important topics in intelligent robot research. Due to the high complexity of robot motion planning in obstacle spaces, this problem has not been well solved so far. Path planning problems can be divided into two types according to the robot's working environment model: one is model-based path planning, in which all information about the working environment is known in advance; the other is sensor-based path planning, in which all or part of the information about the working environment is unknown.

In the study of robot path planning, experts and scholars from all over the world have proposed many different path planning methods, which can be mainly divided into global path planning methods and local path planning methods. Global path planning methods include configuration space method, generalized cone method, vertex image method, grid classification method; local path planning methods mainly include artificial potential field method. These methods have their own advantages and disadvantages [3], and no one method can be applied to all occasions.

This paper proposes a shortest tangent path planning method, which involves simple theory, simple calculation and easy implementation, and can be used as a reference for readers who focus on application. The basic principle of the algorithm will be introduced in detail below, and the simulation results will be given at the end.

2 Shortest tangent path algorithm

2.1 Basic Principles of the Algorithm

(1) First, determine whether there is an obstacle between the robot and the given target position. As shown in Figure 1, B represents the target position, and its coordinates are (xB, yB), R and A represent the robot and obstacle, respectively, and their coordinates are (xR, yR) and (xA, yA). Rr and Ra represent the collision radius between the robot and the obstacle, that is, there is no danger of collision outside their radius. Here is a little explanation on the selection of the collision radius. The smaller the collision radius, the greater the risk of collision, but the shorter the tangent path; the larger the collision radius, the smaller the risk of collision, but at the same time the tangent path is longer. The collision radius should be determined according to the actual situation and control requirements. If there is no obstacle between the robot and the target position, the robot can go directly to the target position in a straight line. At this time, the equation of the straight line can be determined by the two-point formula:

written in the standard form of ax+by+c=0:

If d>Ra+Rr, the robot can reach the target point in a straight line without touching object A. In this case, object A is not an obstacle. If d<Ra+Rr, the robot may touch object A in a straight line. In this case, object A should be regarded as an obstacle.

(2) Find the tangent path. As shown in Figure 1, take point A as the center and Ra+Rr as the radius to make a collision circle, and its equation is:


k 1 ,k 2 are the slopes to be determined, and the simultaneous equations are:

The slopes of the two tangent lines can be obtained respectively, k 1 and k 2 . Obviously, k 1 and k 2 have two values, corresponding to the two tangent line equations. The two sets of tangent lines intersect each other. From the equation set

The two intersection points C1 and C2 are called the midpoints of bypassing obstacle A. Thus, two tangent paths that bypass obstacle A and reach target point B can be obtained, path 1: R→C1→B; path 2: R→C2→B. Comparing the lengths of the two paths, in Figure 1, |RC 1 |+|BC 1 |<|RC 2 |+|BC 2 |, it can be seen that path 1 is the shortest tangent path.

2.2 Multiple obstacles

For situations where there are multiple obstacles, several situations can be considered.

(1) The obstacle is located at the midpoint of the previous obstacle. In other words, the midpoint that the robot wants to reach is within the collision circle of another obstacle. If the robot reaches the midpoint, it may hit the obstacle. At this time, the coordinates of the obstacle can be used instead of the coordinates of the original obstacle to find the midpoint on this side. For the midpoint on the other side, if there is also an obstacle, the same treatment is performed; if not, the midpoint remains unchanged. Then, the lengths of the two paths are still calculated and compared, and the shortest tangent path is selected. As shown in Figure 2, the dotted line in the figure represents the original path 1. Since the midpoint is blocked by obstacle A2, path 1 moves up. At this time, |RC 1 |+|BC 1 |>|RC 2 |+|BC 2 |, the shortest tangent path should be path 2.

(2) There are obstacles on the tangent path. The task of bypassing multiple obstacles to reach the final position can be divided into several subtasks, each of which requires bypassing one obstacle. In this way, one subtask is equivalent to the situation where there is only one obstacle in front. Bi and Ci represent the target point and the midpoint of the ith subtask respectively. When executing the ith subtask, if there is an obstacle on the path to Bi, then add the i+1th subtask, and the target point Bi+1 is Bi; if there is an obstacle on the path to Ci, then add the i+1th subtask, and the target point Bi+1 is Ci. Similarly, find the tangent path until you reach the given final target position, and calculate the sum of the shortest tangent paths to be the optimal path. Figure 3 shows the walking path of the robot bypassing two obstacles and reaching the target position. 

3 Practical Application

(1) Transport Robot For mobile transport robots in factory workshops, the tangent path planning method is a feasible and practical method. First, the positions of the robot and obstacles can be measured in real time, and the obstacles are generally fixed; second, the number of obstacles is fixed, and the shape and size are predictable; third, the efficiency of transport requires the robot to have the shortest walking path, and walking in a straight line is more efficient than walking in a curve.
(2) Soccer Robot Mirosot Soccer Robot is a two-wheel drive robot. In a robot soccer game, the coordinates of the two robots and the ball are identified by a camera hanging above the court and transmitted to the computer. During the game, the robot must kick the ball into the opponent's goal to score. The robot must first avoid other robots and catch the ball. According to the algorithm, the coordinates of the ball are used as the target position, and other robots that block its path are used as obstacles to perform real-time path planning. Since the purpose is only to avoid collisions, not to completely avoid collisions (in fact, collisions are inevitable in the game), the collision radius can be selected as small as possible, just enough to cover the robot. Although this increases the risk of collision, the tangent path can be shortened as much as possible.

4 Simulation Results

Figure 4 shows the simulation results obtained by programming and running the strategy using the algorithm on the Simurosot 5-on-5 robot soccer simulation competition platform. It should be noted that, for the convenience of observation, the ball and obstacles are set to be fixed in the example. But this does not mean that this algorithm cannot be applied to sports competitions. The coordinates in the algorithm are measured in real time, the path is calculated in real time, and the results obtained should be real-time and effective. However, due to the rapid changes in movement during the game, the actual effect can only be seen through long-term experimental observation, and the quality of the effect depends not only on the advancement of the algorithm, but also to a large extent on the level of the programmer's software.

5 Conclusion

There are many methods for mobile robot path planning, each with its own advantages and disadvantages, and no one method can be applied to all occasions. As a result, various new algorithms continue to emerge. On the one hand, they enrich the means of solving problems, and suitable algorithms can always be found in different situations; on the other hand, they continue to absorb new theories and promote the continuous development of the subject. It is worth mentioning that some new algorithms, regardless of whether they are practical or not, use some newly studied theoretical results in order to keep up with the trend. These theories are either too complicated or not mature, resulting in lengthy and difficult to understand algorithms, impractical, and impossible to implement. Some algorithms sacrifice speed and time in order to make the robot walk out a smooth and perfect curve, which is not desirable. It should be said that a good algorithm does not lie in the high depth of the theory it contains, but in its practicality; on the contrary, algorithms with simple theories and fast calculations are more likely to be accepted. The key is to see the final effect. The tangent path algorithm introduced in this article is a geometric method. It does not have a profound theory, is easy to understand, easy to implement, and has simple calculations, which can improve operating efficiency. However, the final operating effect still depends on the programming level.

Reference address:A Path Planning Algorithm for Mobile Robots

Previous article:Humanoid robot motion control system based on CAN bus and dual sensors
Next article:Principle and practice of robot line following algorithm

Latest Embedded Articles
Change More Related Popular Components

EEWorld
subscription
account

EEWorld
service
account

Automotive
development
circle

About Us Customer Service Contact Information Datasheet Sitemap LatestNews


Room 1530, 15th Floor, Building B, No.18 Zhongguancun Street, Haidian District, Beijing, Postal Code: 100190 China Telephone: 008610 8235 0740

Copyright © 2005-2024 EEWORLD.com.cn, Inc. All rights reserved 京ICP证060456号 京ICP备10001474号-1 电信业务审批[2006]字第258号函 京公网安备 11010802033920号