CN108170146B

CN108170146B - A Path Planning Method Based on Known Environment

Info

Publication number: CN108170146B
Application number: CN201711495089.3A
Authority: CN
Inventors: 张松涛; 李超; 曹雏清; 高云峰
Original assignee: Wuhu Hit Robot Technology Research Institute Co Ltd
Current assignee: Wuhu Hit Robot Technology Research Institute Co Ltd
Priority date: 2017-12-31
Filing date: 2017-12-31
Publication date: 2021-07-30
Anticipated expiration: 2037-12-31
Also published as: CN108170146A

Abstract

The invention discloses a path planning method based on a known environment. The method updates the adjacency matrix A by adjusting the weights of local edges in real time, so as to realize dynamic path planning, which can reduce the "locked" road sections and improve the road sections. In order to reduce the possibility of pursuit conflict between two AGVs, temporarily increase the weight (driving direction) of the side where the AGV is located to reduce the possibility of pursuit conflict (in case of Pursue conflict, there are also emergency responses).

Description

Path planning method based on known environment

Technical Field

The invention relates to the technical field of path planning, in particular to a dynamic path planning method for multiple AGVs, which can be expanded to the technical field of path planning of mobile robots.

Background

AGV (automated Guided vehicle) is an "automated Guided vehicle". The AGV is an important transportation tool for an industrial 4.0 intelligent factory, and the operation efficiency of the AGV greatly influences the production efficiency of the whole unmanned factory. Therefore, efficient, orderly and safe cooperative operation of the multiple AGVs is of great significance, and path planning and dynamic adjustment of the multiple AGVs are one of the key problems to be solved.

Since AGVs often travel on fixed tracks (i.e., only one AGV is allowed to pass through a road segment at a time), when multiple AGVs are operating simultaneously, a path needs to be dynamically adjusted, and the current adjustment strategies are generally classified into on-site waiting and detouring. The in-place waiting strategy is simple, but the working efficiency of the whole dispatching system is greatly reduced, and particularly when one or more idle AGVs (or faults) are blocked in a working route, the whole dispatching system is likely to be crashed; regarding the bypassing strategy, a time window-based scheduling method is popular at present, but the calculation amount of the whole scheduling system is greatly increased, and planning adjustment cannot be made in time for an emergency. Therefore, it is urgent to find a dynamic path planning method which has relatively small calculation amount and can improve the working efficiency of the whole dispatching system.

There are also publications disclosing methods for AGV path planning, such as a dynamic path planning that "locks" all the upcoming road segments and "unlocks" the upcoming road segments, as proposed in the patent "mobile robot path planning method based on known environment" (application No.: 201610569810.8). The method can lead the robot which receives the dispatching command to select to bypass and avoid collision, but wastes excessive paths, thereby greatly reducing the path selection space of the robot which receives the dispatching command later (particularly when the robots are more, the robot which obtains the dispatching command later is extremely likely to have no way to walk because the excessive paths are locked and can only wait in place; and the running robot has no way to walk and causes the breakdown of the whole system), and reducing the working efficiency and the stability of the whole system; in addition, the method of the patent has a default condition that all robots are constant-speed (namely, no chase collision exists), however, in an actual scene, the running speeds of all the AGVs are different, and the chase collision problem can exist.

Disclosure of Invention

The invention aims to solve the technical problem of realizing a path planning method which reduces the locked road sections, avoids the waste of the road sections and can eliminate or reduce the possibility of collision pursuit.

In order to achieve the purpose, the invention adopts the technical scheme that: a path planning method based on a known environment is disclosed, wherein a path of the known environment is an input map, and a feasible path is arranged between a node and a node on the map, and is characterized in that the path planning method comprises the following steps:

step 1, performing bidirectional assignment or update assignment on a path between nodes on a map;

step 2, generating an adjacency matrix A;

step 3, calculating a shortest distance matrix and a shortest path matrix;

step 4, obtaining the shortest path to the current terminal according to the current position of the movement device;

step 5, the moving device runs according to the shortest path and feeds back the current position in real time;

step 6, judging whether the moving device reaches a new node, if so, sending a path request again and returning to the step 4, otherwise, executing the next step;

step 7, judging whether the distance between the two moving devices is smaller than a set value or not, if not, returning to the step 5, and if so, executing the next step;

and 8, judging whether the motion directions of the two motion devices are the same, if not, stopping the two motion devices and returning to the step 1, if so, stopping the motion device positioned at the rear until the front vehicle reaches a new node, and resuming the running of the rear motion device.

The weight value of each path in the step 1 is determined by the distance omega₁Influence, angle of rotation omega₂And other road condition factors omega₃Constraint, each path one-way value ω ═ ω₁+ω₂+ω₃。

And 3, calculating a shortest distance matrix D and a shortest path matrix P by using a Floyd algorithm.

The moving device in the step 4 is an AGV or a moving robot.

And 5, feeding the current position back to a control device of the system in real time, and updating the path bidirectional assignment between the nodes on the map by the control device according to the current position of the movement device.

The method for updating the path bidirectional assignment comprises the following steps: the ith row and jth column element a (i, j) of the adjacency matrix a is ω ij, and when a certain motion device goes from the i node to the j node, a (i, j) and a (j, i) are re-assigned: a (i, j) ═ k × ω ij, a (j, i) ± ∞; if the AGV stops on the path from node i to node j, a (i, j) ═ a (j, i) + ∞.

K is an empirical value and is determined by the frequency of the road section used and the current AGV speed factor.

The k is larger than or equal to 1, and the larger the value of k is, the lower the possibility that the subsequent AGV passes through the road section is.

The invention can reduce the locked road sections, improve the utilization rate of the road sections, integrally improve the working efficiency of the whole system, reduce the possibility of collision pursuit and have the countermeasures for collision pursuit.

Drawings

The following is a brief description of the contents of each figure in the description of the present invention:

FIG. 1 is a topology diagram of a field environment configuration;

fig. 2 is a flow chart of a path planning method.

Detailed Description

As shown in fig. 1, taking an AGV as an example, a path planning method based on a known environment is as follows:

1) firstly, drawing topological graphs of all paths where the AGV can walk according to a field environment, as shown in FIG. 1;

2) the topology is composed of nodes (circles) and edges (double arrows);

3) the edge of each node is a bidirectional edge, i.e., the edge ω from node 1 to node 2₁₂And an edge ω from node 2 to node 1₂₁The weights of (c) may be different (infinity is assigned to edges that are not directly connected);

4) the weight omega of each edge is not only influenced by the distance omega between two nodes₁Influence, angle of rotation omega₂And other road condition factors omega₃I.e. ω ═ ω₁+ω₂+ω₃；

5) The weights of all the edges in step 2) can be represented by an adjacency matrix a, where the ith row and jth column element a (i, j) of a is ω_ij；

6) Reading the matrix A in the step 5), and calculating a shortest distance matrix D and a shortest path matrix P by using a Floyd algorithm;

7) the ith row and jth column element D (i, j) of the shortest distance matrix D represents the minimum weight from the ith node to the jth node;

8) the ith row and jth column element P (i, j) of the shortest path matrix P represents a transit point which needs to be reached first in the shortest path from the ith node to the jth node;

9) the AGV runs according to a scheduling command and feeds back the current position in real time;

10) each time an AGV arrives at a node, a scheduling command is requested;

11) the scheduling command received by the AGV is from "current node" to "transit point needed to be reached first" described in step 8);

12) sensors for feedback of current position in step 9) include, but are not limited to, StarGazer, mock's NAV350, hart's easy navigation, etc.;

13) when an AGV travels a road segment from node i to node j at a certain time, the values of a (i, j) and a (j, i) are re-assigned: a (i, j) ═ k × ω ij, a (j, i) ± ∞; if the AGV stops (or fails) on the path from the node i to the node j, a (i, j) ═ a (j, i) + ∞;

14) k in the step 13) is an empirical value, and is determined by factors such as the frequency of the used road section, the current AGV speed and the like (k is more than or equal to 1, and the probability that the subsequent AGV passes through the road section is lower if the k is larger);

15) after the weight value is updated in the step 13), updating the adjacency matrix A in real time, and updating and calculating the distance matrix D and the path matrix P in real time;

16) if the AGV reaches the new node, step 10) is performed; otherwise, judging whether the distance between the two AGVs is smaller than a threshold value S (a preset value);

17) if the distance between the two AGVs is not smaller than the threshold value S, continuing to drive according to the current path; otherwise, judging whether the two AGV moving directions are the same;

18) if the moving directions of the two AGVs are opposite, the two AGVs stop running and give an alarm; otherwise, the latter stops (the former continues to run), and when the former runs out of the road section, the former continues to run according to the current path.

The invention has been described above with reference to the accompanying drawings, it is obvious that the invention is not limited to the specific implementation in the above-described manner, and it is within the scope of the invention to apply the inventive concept and solution to other applications without substantial modification.

Claims

1. a path planning method based on a known environment, the path of the known environment is a map of input, and a feasible path is provided between the node and the node on the map, it is characterized in that, the path planning method comprises the following steps:

Step 1. Perform bidirectional assignment or update assignment to the path between nodes on the map;

Step 2. Generate an adjacency matrix A;

Step 3. Calculate the shortest distance matrix and the shortest path matrix;

Step 4. Obtain the shortest path to the current end point according to the current position of the motion device;

Step 5. The motion device travels according to the shortest path, and feeds back the current position in real time;

Step 6, determine whether the motion device has reached the new node, if so, issue the path request again and return to step 4, if otherwise, execute the next step;

Step 7, judge whether the distance between two motion devices is less than the set value, if otherwise, return to step 5, and if so, execute the next step;

Step 8. Determine whether the motion directions of the two motion devices are the same. If not, stop the two motion devices and return to step 1. If so, stop the motion device at the rear until the vehicle in front reaches the new node, and resume the driving of the rear motion device;

The size of the weight assigned to each path in the step 1 is affected by the distance ω ₁ , the rotation angle ω ₂ , and other set road condition factors ω ₃ are restricted, and the unidirectional value of each path ω = ω ₁ +ω ₂ +ω _3;

The method of updating the bidirectional assignment of the path: the element a(i,j)=ωij of the i-th row and the j-th column of the adjacency matrix A, when a moving device goes from the i node to the j node, then the a(i, j) and a(j,i) is reassigned: a(i,j)=k*ωij, a(j,i)=+∞; if the AGV stops on the path from node i to node j, then a(i,j) =a(j,i)=+∞;

The k is an empirical value, which is determined by the frequency of the road segment being used and the current AGV speed factor;

the k

1. The larger the k value, the less likely the subsequent AGV will pass through the road section.

2 . The path planning method based on a known environment according to claim 1 , wherein the step 3 uses the Floyd algorithm to calculate the shortest distance matrix D and the shortest path matrix P. 3 .

3. The path planning method based on a known environment according to claim 1 or 2, wherein the motion device in the step 4 is an AGV or a motion robot.

4. The path planning method based on a known environment according to claim 3, wherein in step 5, the current position is fed back to the control device of the system in real time, and the control device updates the nodes on the map according to the current position of the motion device Bidirectional assignment with paths between nodes.