CN110503260A - An AGV Scheduling Method Based on Dynamic Path Planning - Google Patents

Abstract

The invention discloses an AGV scheduling method based on dynamic path planning, which belongs to the technical field of optimal scheduling. The strategy initializes the AGV work site, can realize scheduling with different precision, and initializes the working map, which can simulate the actual map and solve the problem of Multi-unit and multi-task problems in any scene; based on the adjacency matrix and distance matrix established by the Floyd algorithm, the AGV selection process and the obstacle avoidance situation of the AGV during the execution process are optimized and scheduled, and the single-step dynamic planning of the AGV is realized. Executing the route, shortening the moving time of AGV, improving work efficiency, and playing an important role in the transformation of industrial automation production to flexible production mode.

Description

An AGV Scheduling Method Based on Dynamic Path Planning

technical field

The invention relates to the technical field of optimal scheduling, in particular to an AGV scheduling method based on dynamic path planning.

Background technique

With the development of automation, the manufacturing industry has put forward higher requirements for warehouse management and logistics transportation. AGV has become the key equipment in this field due to its many advantages, and plays an irreplaceable role in automated transportation. AGV trolley is an important part of realizing flexible manufacturing system, and AGV scheduling, as the core technology of AGV design, has always been a research focus and difficulty in the field of manufacturing and automation at home and abroad. Therefore, it is of great significance to conduct research on issues such as multi-AGV scheduling methods and path planning.

For the AGV scheduling method of the multi-task system in complex scenarios, there are problems such as path conflicts and low resource utilization, which lead to deadlock in the dynamic environment. At this stage, some scholars have proposed a strategy based on speed reconciliation and geometric path adjustment for path conflicts; some scholars have established a multi-objective optimization model based on the number of AGV transport vehicles, task satisfaction, and total driving distance, and designed In terms of queuing scenarios, some scholars introduced a system scheduling model, selected queue length and waiting time as optimization indicators, and designed a scheduling strategy; in terms of path planning, some scholars proposed a bounded rational self-organization method The path planning of multiple AGVs can effectively solve the problem of local competition of task resources. Although the above method can effectively solve the problem of path conflicts and low utilization of some AGVs, it needs to establish a complex model, and the calculation cycle is long, and the optimal strategy calculated by the model may be due to improper parameter settings, resulting in only is a local optimal solution.

Contents of the invention

Aiming at the deficiencies of the prior art above, an AGV scheduling method based on dynamic path planning is provided.

The technical scheme adopted in the present invention is a kind of AGV scheduling method based on dynamic path planning, comprising the following steps:

Step 1: Initialize the AGV work site, divide the work site into a rectangular grid with a certain length and width, and the intersection of the grid lines is called a node, where the length and width of the grid can be adjusted to achieve scheduling with different precision;

Step 2: Initialize the working map, determine the AGV working nodes, and number all nodes in the map as 1, 2, ..., n, determine the number of AGVs as m, and number them as 1, 2, ..., m;

Step 3: Calculate the shortest distance between any two working nodes through the Floyd algorithm, and generate the corresponding adjacency matrix and distance matrix;

Step 4: The task list is sorted by the priority of the task, and the task with the highest priority is the current task. Obtain the starting point of the current task in the task list, and use the distance matrix to find the idle AGV closest to the starting point of the task in the work site to execute the task. The process is shown in Figure 1;

Step 4.1: Initialize the AGV position, where the position occupied by the car is the occupied node, and the rest of the points are unoccupied nodes;

Step 4.2: Obtain the starting point of the current task in the task list;

Step 4.3: Determine whether there is an idle AGV, if not, wait for an idle AGV;

Step 4.4: If there are idle AGVs, determine whether there are multiple idle AGVs;

Step 4.5: If there is currently only one idle AGV, select the AGV to perform the task;

Step 4.6: If the current number of idle AGVs is greater than 1, calculate the distance of all idle AGVs to the starting point of the task through the distance matrix established by the Floyd algorithm;

Step 4.7: Select the idle AGV with the closest calculation distance to perform this task;

Step 4.8: If the number of the nearest idle AGV is greater than 1, select the AGV with the smallest number to perform the task.

Step 5: Dynamically plan the AGV execution route, avoiding the occupied nodes, so that the AGV performing the task can reach the starting point of the task, and the process is shown in Figure 2;

Step 5.1: Select a node from the adjacent nodes that has never been passed or the node that has the longest time interval from the last time;

Step 5.1.1: mark the current position of the AGV as 1, and mark the remaining adjacent working nodes as 0;

Step 5.1.2: When the AGV chooses to move, subtract 1 from the adjacent working nodes, and then change the next node to go to 1;

Step 5.1.3: Select the node with the longest time interval from the last time, that is, the node with the smallest value, as the next node to go;

Step 5.1.4: If there are many points satisfying the conditions, calculate the sum of the distance from the AGV to the adjacent unoccupied node and the distance from the adjacent node to the starting point of the task through the adjacency matrix and the distance matrix described in claim 1;

Step 5.1.5: Select the node with the shortest sum of distances to go. At this time, mark the node to go next as occupied while selecting.

Step 5.2: Determine whether the working node obtained in step 5.1 is occupied by an AGV, and if it is occupied by an AGV, determine whether the occupied AGV is performing tasks;

Step 5.3: If the occupied AGV is in an idle state, randomly select a working node in the unoccupied reachable point for the idle AGV to execute, if all nodes are unreachable, randomly assign an unoccupied point for Idle AGV to execute, and at the same time, the AGV currently executing the task selects the adjacent working node obtained in step 5.1 to move;

Step 5.4: If the occupied AGV is in the working state, the AGV currently executing the task selects a neighboring node with a short distance to move;

Step 5.5: If the working node obtained in step 5.1 is not occupied by the AGV, select the working node to move.

Step 5.6: Repeat step 5.1 to step 5.5 to implement single-step dynamic planning of the execution route of the AGV until the adjacent node obtained in step 5.1 is the starting point of the task and stop the cycle.

Step 6: After picking up the goods from the starting point of the task, the AGV dynamically plans the execution route again, avoiding the occupied nodes, and reaching the end of the task;

Among them, the end point of the task is regarded as the starting point of the task in step 5, and the process of dynamically planning the execution route of the AGV from the pick-up point to the end point of the task is consistent with the process in step 5;

Step 7: Update the task list, add new tasks, and cancel completed tasks;

Step 8: Repeat steps 4 to 7 until the task list is empty.

The beneficial effects produced by adopting the above-mentioned technical scheme are: .

1. When choosing an AGV, give priority to idle AGVs to ensure that the frequency of use of each AGV is stable;

2. During the obstacle avoidance process, consider the driving route of the vehicle before the vehicle starts, and avoid changing the route in order to avoid other vehicles during operation.

3. The actual map can be simulated, and the scheduling strategy under different precision can be realized by adjusting the length and width of the grid;

4. It is not limited to the transportation problem in the factory, but a universal solution to the multi-unit multi-task problem in any scene, which can be applied to a wider aspect in life.

Description of drawings

Fig. 1 is AGV selection flowchart of the present invention;

Fig. 2 is the flow chart of AGV path planning of the present invention;

Fig. 3 is a sub-graph of the grid of the work site in the embodiment of the present invention;

Fig. 4 is the initializing work map in the embodiment of the present invention, carries out numbering figure to working node;

Fig. 5 is a position diagram of the working node where the AGV is located before scheduling in the embodiment of the present invention;

FIG. 6 is a diagram of the position of the working node where the AGV is located after scheduling in the embodiment of the present invention.

Detailed ways

The specific implementation manners of the present invention will be further described in detail below in conjunction with the accompanying drawings and embodiments. The following examples are used to illustrate the present invention, but are not intended to limit the scope of the present invention.

In this embodiment, an area with a size of 1600px*800px is used as a work site, and the number of AGVs in this site is 4.

The method of this embodiment is as follows:

Step 1: Initialize the work site with a size of 1600px*800px, divide the work site into a rectangular grid of 100px*100px, as shown in Figure 3, the intersection of grid lines is called a node, and the length and width of the grid Adjustable to achieve scheduling with different precision;

Step 2: Initialize the working map, determine the AGV working nodes, and number all nodes in the map as 1, 2, ..., 22, as shown in Figure 4, determine the number of AGVs as 4, and number them as 1, 2, 3,4;

Step 3: Calculate the shortest distance between any two working nodes through the Floyd algorithm, and generate the corresponding adjacency matrix and distance matrix;

Step 4: The task list is sorted according to the priority of the task, the task with the highest priority is the current task, and the task list is shown in Table 1;

Table 1 List of tasks sorted by priority

priority mission starting point mission end 1 3 twenty two 2 4 18 3 14 20 4 13 11

Obtain the starting point of the current task in the task list, and use the distance matrix to find the idle AGV closest to the starting point of the task in the work site to execute the task. The process is shown in Figure 1;

Step 4.1: Initialize the AGV position. The positions of the four AGVs are shown in Figure 5, where the positions occupied by the cars are occupied nodes, and the rest are unoccupied nodes;

Step 4.2: Obtain the starting point of the current task in the task list;

Step 4.3: Determine whether there is an idle AGV, if not, wait for an idle AGV;

Step 4.4: If there are idle AGVs, determine whether there are multiple idle AGVs;

Step 4.5: If there is currently only one idle AGV, select the AGV to perform the task;

Step 4.6: If the current number of idle AGVs is greater than 1, calculate the distance of all idle AGVs to the starting point of the task through the distance matrix established by the Floyd algorithm;

Step 4.7: Select the idle AGV with the closest calculation distance to perform this task;

Step 4.8: If the number of the nearest idle AGV is greater than 1, select the AGV with the smallest number to perform the task.

Step 5: Dynamically plan the AGV execution route, avoiding the occupied nodes, so that the AGV performing the task can reach the starting point of the task, and the process is shown in Figure 2;

Step 5.1: Select a node from the adjacent nodes that has never been passed or the node that has the longest time interval from the last time;

Step 5.1.1: mark the current position of the AGV as 1, and mark the remaining adjacent working nodes as 0;

Step 5.1.2: When the AGV chooses to move, subtract 1 from the adjacent working nodes, and then change the next node to go to 1;

Step 5.1.3: Select the node with the longest time interval from the last time, that is, the node with the smallest value, as the next node to go;

Step 5.1.4: If there are many points satisfying the conditions, calculate the sum of the distance from the AGV to the adjacent unoccupied node and the distance from the adjacent node to the starting point of the task through the adjacency matrix and the distance matrix described in claim 1;

Step 5.1.5: Select the node with the shortest sum of distances to go. At this time, mark the node to go next as occupied while selecting.

Step 5.2: Determine whether the working node obtained in step 5.1 is occupied by an AGV, and if it is occupied by an AGV, determine whether the occupied AGV is performing tasks;

Step 5.3: If the occupied AGV is in an idle state, randomly select a working node in the unoccupied reachable point for the idle AGV to execute, if all nodes are unreachable, randomly assign an unoccupied point for Idle AGV to execute, and at the same time, the AGV currently executing the task selects the adjacent working node obtained in step 5.1 to move;

Step 5.4: If the occupied AGV is in the working state, the AGV currently executing the task selects a neighboring node with a short distance to move;

Step 5.5: If the working node obtained in step 5.1 is not occupied by the AGV, select the working node to move.

Step 5.6: Repeat step 5.1 to step 5.5 to implement single-step dynamic planning of the execution route of the AGV until the adjacent node obtained in step 5.1 is the starting point of the task and stop the cycle.

Step 6: After picking up the goods from the starting point of the task, the AGV dynamically plans the execution route again, avoiding the occupied nodes, and reaching the end of the task;

Among them, the end point of the task is regarded as the starting point of the task in step 5, and the process of dynamically planning the execution route of the AGV from the pick-up point to the end point of the task is consistent with the process in step 5;

As shown in Figure 6, select the AGV numbered 1 to execute the task with priority 1, pick up the goods from the initial node 1 to the task starting point 3, and deliver the goods to the task end point 22, and the task is being executed; select the AGV numbered 3 Execute a task with a priority of 3. After picking up the goods from the initial node 15 to the task node 14, deliver the goods to the task end point 20. The task is being executed.

Step 7: Update the task list, add new tasks, and cancel completed tasks;

Step 8: Repeat steps 4 to 7 until the task list is empty.

Claims (7)

1. a kind of AGV dispatching method based on active path planning, it is characterised in that include the following steps:

Step 1: the work-yard AGV being initialized, work-yard is divided into the rectangular mesh with certain length and width, grid The crosspoint of line is known as node, and wherein the length and width of grid are adjustable, to realize the scheduling of different accuracy；

Step 2: initial work map determines AGV working node, and it is 1,2 that all nodes, which are numbered, in map ..., N determines that AGV quantity is m, and it is 1,2 that it, which is numbered, ..., m；

Step 3: calculating the shortest distance of any two working node by Freud's algorithm, generate corresponding adjacency matrix And distance matrix；

Step 4: in task list obtain current task starting point, by distance matrix job search place from task starting point Nearest idle AGV executes this task；

Step 5: Dynamic Programming AGV executes route, avoids occupied node, the AGV of execution task is made to can reach task starting point；

Step 6: after task starting point picking, Dynamic Programming executes route to AGV again, avoids occupied node, reaches task Terminal；

Step 7: updating task list, new work task cancels the task for having executed completion；

Step 8: repeating step 4 to step 7, until task list is sky.

2. a kind of AGV dispatching method based on active path planning according to claim 1, it is characterised in that: the step Task list is ranked up by the priority of task in rapid 4, and the task of highest priority is current task.

3. a kind of AGV dispatching method based on active path planning according to claim 1, it is characterised in that: the step Rapid 4 process is as follows:

Step 4.1: the initialization position AGV, wherein trolley engaged position is occupied node, remaining point is unoccupied node；

Step 4.2: the starting point of current task is obtained in task list；

Step 4.3: judging whether available free AGV, if waiting idle AGV without if；

Step 4.4: if available free AGV, judging whether there is multiple free time AGV；

Step 4.5: if currently only 1 free time AGV, selects the AGV to execute task；

Step 4.6: if current idle AGV quantity is greater than 1, the distance matrix established by Freud's algorithm is calculated Available free AGV reach the distance of task starting point；

Step 4.7: selection calculates the nearest idle AGV of distance and executes this task；

Step 4.8: if being greater than 1 apart from nearest idle AGV quantity, selecting to number the smallest AGV and go execution task.

4. a kind of AGV dispatching method based on active path planning according to claim 1, it is characterised in that: the step Process in rapid 5 is as follows:

Step 5.1: selecting one once unbeaten node or to pass by time interval longest apart from last time from adjacent node Node；

Step 5.2: whether the working node that judgment step 5.1 obtains is occupied by AGV, if occupied by AGV, judges occupancy Whether AGV has in execution task；

Step 5.3: if the AGV occupied is in idle condition, selecting a work in unappropriated reachable point at random It allows idle AGV to go to execute as node, if all nodes are all unreachable, are randomly assigned a unappropriated point and allow the free time AGV goes to execute, while the operated adjacent node motion that the current AGV selection step 5.1 for executing task obtains；

Step 5.4: if the AGV occupied is in running order, the current AGV selection one for executing task is apart from close adjacent segments Point movement；

Step 5.5: if the working node that step 5.1 obtains is not occupied by AGV, selecting the working node mobile；

Step 5.6: the execution route that step 5.1 realizes single step Dynamic Programming AGV to step 5.5 is repeated, until step 5.1 Obtained adjacent node is task starting point, stops circulation.

5. a kind of AGV dispatching method based on active path planning according to claim 4, it is characterised in that: the step Rapid 5.1 process is as follows:

Step 5.1.1: the current location AGV is labeled as 1, remaining adjacent working node is labeled as 0；

Step 5.1.2: when AGV selects mobile, adjacent working node is all subtracted 1, then by next section that will be gone Point is changed to 1 again；

Step 5.1.3: the longest node of the time interval i.e. the smallest node of numerical value that selects to pass by apart from last time it is next walk Node；

Step 5.1.4: if there are many point for meeting condition, pass through adjacency matrix described in claim 1 and distance matrix meter It calculates AGV and reaches the distance of adjacent unoccupied node and the sum of the distance of adjacent node arrival task starting point；

Step 5.1.5: the selection shortest node of sum of the distance is walked, at this time by the vertex ticks to be walked in next step while selection To have occupied.

6. a kind of AGV dispatching method based on active path planning according to claim 1, it is characterised in that: the step Task terminal in rapid 6 is considered as the task starting point in step 5, reaches task terminal Dynamic Programming AGV from picking point and executes route Process it is consistent with the process in step 5 described in claim 1.

7. a kind of AGV dispatching method based on active path planning according to claim 4, it is characterised in that: the step If the AGV occupied is in running order in rapid 5.4, and the occupied working node is that current the executing task AGV of the task rises Point then currently executes the AGV selection one of task after close adjacent node movement, comes back to task starting point.