Time window-based task segmentation multi-AGV path planning algorithm

Abstract

The invention relates to a path planning method, and specifically relates to a time window-based task segmentation multi-AGV path planning algorithm. The method comprises steps of first, generating anAGV working environment model; second, generating a task, and decomposing the task into multiple secondary stages according to different task types; and third, assigning the task by a task assigningmodule according to task priorities, picking the task out by a scheduling system from a high-priority queue, then determining which stage the task is in, if the task is not executed, assigning the task to closest AGV by using an improved A* algorithm, and setting the task state in first secondary stage; if the task is in the second or after stages, and planning a non-conflict shortest path for theAGV bound with the task by using the time widow algorithm by the scheduling system. Shortest and fastest paths are planned by using the improved A* algorithm and time window algorithm, so that the working efficiency is improved and calculation errors are reduced.

Description

technical field [0001] The invention relates to a path planning method, in particular to a task-segmented multi-AGV path planning algorithm based on a time window. Background technique [0002] With the wide application of flexible manufacturing systems, traditional manpower and semi-mechanized factory logistics methods can no longer meet the logistics needs of modern equipment manufacturing industries. The demand for automated guided vehicles (Automated Guided Vehicle, AGV) in domestic factories has increased significantly. AGVs commonly used in factories are mainly divided into traction type, latent type, and forklift type. In the entire automated factory system, the AGV system problem is divided into path planning, task assignment and scheduling algorithm, among which path planning becomes the primary problem to be solved. AGV path planning refers to the programming of the upper computer system by the system programmer, and the AGV carrying the task. Real-time planning o...

AI Technical Summary

Problems solved by technology

[0003] (1) The existing dynamic path planning methods based on time windows are basically based on edges, that is, one edge can only be occupied by one AGV. For AGVs in factories, the walking edges are generally longer and the efficiency is too low;

[0004] (2) The planned path has too many turns, takes a long time to run, and passes through too many nodes at the same time, which easily leads to conflicts;

[0005] (3) The time window is better estimated when the AGV is walking on the path, but the time at the loading point or unloading point is not easy to determine, and the error in calculating the time window is large

Images