Mobile robot navigation path planning

As we all know, mobile robots are a high-quality solution for material transportation in factories, which is the best choice to improve production efficiency, reduce production costs and enhance production stability. In order to meet the needs of industrial production, an excellent mobile robot product needs to solve three major problems first:

Xiaolan (Hangzhou Blue Core Technology Co., Ltd.) is a professional solution to the navigation planning problem, and then how to achieve a good position with everyone.

Trajectory plan

The farthest distance in the world is not between life and death, but that the export is in front of us, but I have to go far in a circle. Mobile robots also need to complete the maze-like desperate task in the face of the luan (dui) luan environment.

figure 1

In order to cope with the complicated human beings and the fat ones, our witty robots have their own trajectory planning methods. That is to make you fat, to thin yourself (beautiful)! So two important assumptions were put forward (knocking on the blackboard):

The robot is a point where the obstacle expands according to the radius of the robot;

The robot is complete, ignoring the constraints of non-holonomic constraints on the pose;

Therefore, the workspace is perfectly reduced to a two-dimensional physical space (pose space), as shown in Figure 2.

figure 2

Then the path planning problem becomes the search problem of the attitude space: in the free posture space, the robot is searched for a path to develop from the initial attitude to the target attitude. After the gesture space is discretized, it can be done.

Fast Extended Random Tree Method (RRT)

The fast-expanding random tree method can be regarded as a tree-shaped algorithm. Starting from a starting configuration (for a two-dimensional graph, it is a point), the tree data is continuously extended and finally connected to the target point. The specific method is to use an initial point as the root node to generate a random expansion tree by randomly sampling the leaf nodes. When the leaf nodes in the random tree contain the target points or enter the target area, they can be found in the random tree. A path from the initial point to the target point.

image 3

The RRT algorithm also has some shortcomings. It is a pure random search algorithm that is not sensitive to the environment type. When the C-space contains a large number of obstacles or narrow channel constraints, the convergence speed of the algorithm is slow and the efficiency is greatly reduced. At the same time, one of the weaknesses of RRT is that it is difficult to find a path in an environment with narrow passages. Because the narrow passage area is small, the probability of being hit is low.

Therefore, some scholars have proposed the RRTConnect algorithm. The basic RRT searches only the fast-expanding random tree growing from the initial state point to search the entire state space. If two fast-expanding random trees are grown from the initial state point and the target state point at the same time. Searching for state space will be more efficient.

Compared with the original RRT, the algorithm establishes a second tree in the target point area for expansion. In each iteration, the starting step is the same as the original RRT algorithm, which samples random points and then expands. Then, after expanding the new node qnew of the first tree, the new target point is used as the direction in which the second tree is expanded.

Figure 4

This two-way RRT technology has good search characteristics, and has significantly improved search speed and search efficiency than the original RRT algorithm, and is widely used. First, the Connect algorithm is longer in the extended step size than the previous algorithm, making the tree grow faster. Second, the two trees are constantly expanding towards each other instead of using a random extension, especially when starting the pose and When the target pose is in the constraint area, the two trees can escape from their respective constraint areas by rapidly expanding toward each other. This heuristic extension makes the tree's extension more greedy and clear, making the dual-tree RRT algorithm more efficient than the single-tree RRT algorithm.

Unit decomposition

The basic idea of ​​the unit decomposition method is to divide the free space in the gesture space into several small areas, and treat each area as a unit. Taking a unit as a vertex and a neighboring relationship between the units as a side, a connected graph is formed. Then search for the unit in which the initial pose and the target pose are located in the connected graph, and then search for the path connecting the initial unit and the target unit. Finally, the path inside the unit can be generated according to the unit sequence of the obtained path.

Figure 5

The point of the unit decomposition method is that the robot does not need to consider its specific position in each idle unit, only need to consider how to move from one unit to the adjacent free unit, and the number of units is independent of the environment size.

However, the computational efficiency will depend greatly on the complexity of the objects in the environment. To solve this problem, a new unit decomposition method, namely grid representation, is proposed: the environment is decomposed into several grids of the same size. . This is actually an approximation of the map, without regard to the complexity of the environment and the complexity of the shape of the object.

Image 6

Artificial potential field method

The artificial potential field method uses the characteristics of the magnetic field to solve the problem of path planning. It is assumed that the target point is attractive to the robot, and the obstacle generates a repulsive force to the robot. This makes it possible to construct a robot control method based on the synthesis of forces.

Figure 7

The attraction field increases monotonically as the distance between the robot and the target point increases, and the direction points to the target point; the repulsion field has a maximum value when the robot is at the obstacle position, and increases with the distance between the robot and the obstacle. Large and monotonously decreasing, the direction points away from the obstacle. Figure 8 is a potential field diagram of the simultaneous action of the gravitational field and the repulsive field.

Figure 8

The artificial potential field method calculates the potential field force by constructing an artificial potential field, and then calculates the resultant force by force analysis to obtain the final acceleration.

Figure 9

The artificial potential field method is simple in structure, convenient for real-time control of the bottom layer, and widely used in real-time obstacle avoidance and smooth trajectory control. However, due to the small range of repulsion, the potential field method can only solve the problem of obstacle avoidance in local space. It lacks global information, so it is easy to fall into the local minimum. When the robot is at a local minimum point, the robot is prone to oscillation or stagnation. The more obstacles there are, the more likely it is that local minimum points will be produced, and the more local minimum points will be generated, which is something to be aware of during the implementation.

Through the above introduction, I think there is a doubt that you have built many units and paths (topology maps), then how to search for paths, and how to judge which path is better. In the next issue, let's discuss the path search method in the path planning algorithm and learn how the A* algorithm, the genetic algorithm and the particle filter algorithm serve us.