CN118706124A

CN118706124A - AGV (automated guided vehicle) ex-warehouse navigation planning method based on digital twin storage system

Info

Publication number: CN118706124A
Application number: CN202410751101.6A
Authority: CN
Inventors: 郭烁; 杨凡; 洪悦
Original assignee: Shenyang University of Chemical Technology
Current assignee: Shenyang University of Chemical Technology
Priority date: 2024-06-12
Filing date: 2024-06-12
Publication date: 2024-09-27

Abstract

The invention discloses an AGV (automatic guided vehicle) ex-warehouse navigation planning method based on a digital twin warehouse system, and relates to a multi-AGV path planning method of a dense warehouse. The method comprises the following steps: constructing a warehouse and an AGV model by using three-dimensional modeling software, and importing the warehouse and the AGV model into a digital twin platform after light weight treatment; the platform acquires task data in real time through a database API interface, performs path planning and task scheduling by using a conflict-based search algorithm (CBS), and moves to a specified elevator and destination by AGV according to the planning execution task; AGV state is monitored through the 3D visual platform, and operation transparency and efficiency are improved. Not only solves the problem of multi-AGV path planning conflict, but also shortens the warehouse picking operation time and improves the industrial production efficiency.

Description

AGV (automated guided vehicle) ex-warehouse navigation planning method based on digital twin storage system

Technical Field

The invention relates to a dense-library multi-AGV path planning method, in particular to a digital twin-based warehouse system AGV ex-warehouse navigation planning method.

Background

With the rapid development of industrial automation and intelligent logistics, AGVs are becoming increasingly popular in warehouse management systems. An AGV is an automated guided vehicle, which is an unmanned automated vehicle that has an automated guiding device such as a magnetic stripe, a rail, or a laser, travels along a planned path, is powered by a battery, and is equipped with safety protection and various auxiliary mechanisms (e.g., a transfer mechanism and an assembly mechanism).

The AGV digital twin visualization system is an advanced management system realized by utilizing a virtual reality technology. The core technology of the system is a digital twin technology, which converts a physical model and a control model of actual AGV equipment into a digital model and displays the digital model in a virtual environment. In the system, operators can simulate a scene and plan a path of a warehouse and AGV equipment through a 3D model provided by the system, so that the optimal warehouse layout and transport path are achieved. The Chinese patent with publication number CN115713175A discloses a method for planning a transport path of an AGV trolley based on digital twinning by constructing a digital twinning factory and a digital twinning trolley corresponding to a factory environment and the AGV trolley; and acquiring an AGV trolley transportation task, simulating the trolley transportation task in the digital twin factory, and generating a planning path by applying a path planning algorithm. And optimizing the planned path in real time based on the simulated running state of the digital twin trolley and the running data of the AGV trolley so as to update the transport path of the AGV trolley. The Chinese patent with publication number CN117389229A discloses a multi-AGV scheduling planning method based on a digital twin technology, wherein a virtual AGV model is built in a Unity3D to simulate and monitor the state and the running condition of a physical AGV, and a scheduling strategy and a control module are built based on standardized scheduling resources; and managing the allocation and access rights of traffic resources through a global traffic control algorithm, determining the operation strategy of the AGV according to the application and occupation, and controlling the operation of the AGV through a control instruction. Closed-loop interaction of the physical space and the twin space is realized, and the problems of collision and deadlock are solved.

Similar to the AGV scheduling scheme based on digital twinning, the method has the advantages that the operation of an AGV system is restored through a digital twinning technology, and then the AGV path is controlled through a path planning algorithm, so that the problem of path conflict is solved. But there is no effective solution to the path planning problem for multi-AGVs across floors.

Disclosure of Invention

The invention aims to provide a digital twin-based warehouse system AGV ex-warehouse navigation planning method. The method comprises the steps of modeling a warehouse system, realizing real-time monitoring and path planning of AGVs through synchronous operation data of a digital twin platform, solving the problem of cross-layer multi-AGV scheduling, and improving warehouse operation efficiency.

The technical scheme adopted by the invention is as follows:

A digital twin-based warehouse system AGV (automated guided vehicle) ex-warehouse navigation planning method comprises the following steps:

Step one: drawing a digital three-dimensional model by combining a physical environment, namely a cargo elevator and an AGV (automatic guided vehicle) model, and dividing a cargo unloading area and a cargo loading area; exporting the constructed model into glb/gltf and fbx files through a blender, and then carrying out light weight treatment on the model through BIMface, and importing the model into a digital twin visualization platform;

Step two: the 3D visualization platform acquires a database-out task list of an upper layer system (WMS) database through an API interface, wherein the database-out task list comprises all relevant information (cargo types, target layers, target points, priorities and the like), and the information is sent to the visualization platform in a task instruction form according to a task sequence; after receiving the task form information, the system sends an Ajax request to inquire the state of the AGV through Axios every other communication period, so that the idle AGV is scheduled to execute tasks, and then path planning is carried out to solve the optimal path reaching the target point; converting the obtained path data into JSON and XML formats, extracting all moving coordinate points, and completing task animation of the AGV between the path points by using a three.js animation library according to the coordinates;

Step three: the AGV moves to the elevator position according to the assigned task, the system sends an elevator request to the PLC, the PLC inquires the state of the elevator after receiving the request and returns the state to the system, if the elevator is idle, the PLC enables the elevator to reach a designated floor, and the AGV enters the elevator to perform interlayer scheduling. After the task is completed, the AGV and the elevator are updated to be idle, and the next task is continuously waited for being received;

Step four: the operation condition of the AGV is displayed on the 3D visual platform, the multi-dimensional monitoring and management of the AGV are realized, information records such as the real-time position, the working state and the movement track of the AGV equipment can be seen in a virtual reality scene, and the task executing process is visually displayed.

Further, the digital three-dimensional model in the first step is drawn through a source-opening and free three-dimensional computer graphic software, each part of components comprise a dense-library shelf, an AGV trolley, a lifter and the like, and the digital three-dimensional model is restored according to a physical scene to build a complete digital three-dimensional platform model; BIMface is a BIM lightweight engine, which can compress the model size to the maximum and reduce the CPU/memory/display card overhead to the maximum. And finishing the development of the digital twin visual platform through three.

Further, in the second step, the platform periodically queries the database to obtain a current unfinished task list, and distributes the AGVs to execute the ex-warehouse task according to different cargo types.

Further, the starting position of each AGV is set to be a designated area, and each time the AGV completes the delivery task, the AGV automatically returns to the starting area.

Further, the path planning problem for multiple AGVs in step two can be defined as: in an undirected graph, the formula is written as: g= (V, E), where V is the set of its nodes and E is the set of edges connecting the nodes. In this definition space, n AGVs are assumed, which are represented by the set a= { a ₁,a₂,…,a_n }. For each AGV set to a _i ε A, a movement task τ= { s _i,d_i } from the start point to the target point needs to be performed, where s _i ε V represents the initial position of a _i and d _i ε V represents the target point position to which the designated AGV a _i needs to move from the corresponding s _i node. T= {0,1,2 … } represents the discretized time sequence, path l _i of a _i: T-V is a mapping from the time sequence and the set of nodes V,L _i (t) represents the position of AGV a _i at time t. The AGV may choose to stay in the current position or move to an adjacent position at any time. cost (l _i) is defined as the cost of path l _i, which is calculated in time. Definition t _s is the start time of all AGV paths in the scene,For the end time of path l _i The multi-AGV path planning is to find a feasible solution from a starting position to a target position, wherein the feasible solution refers to no conflict among paths of a plurality of AGVs, and the requirements of no conflict among all AGV paths are met, namely the following formula is satisfied:

The first explanation only allows one AGV to occupy at any moment of any node, namely, position conflict is avoided; equation two states that at any one time, two AGVs are not allowed to move toward each other's position, i.e., to avoid a collision.

The path planning of the invention uses a conflict-Based Search algorithm (Conflict-Based Search, CBS) which is a two-stage path planning framework designed to effectively resolve path conflicts when planning paths for multiple AGVs simultaneously. Searched at the upper level of the algorithm are constraint tree nodes (Constraint Tree Node, CT Node). The CBS algorithm creates a priority queue in the upper search, constraint tree nodes to be detected are stored in the queue, and each constraint tree node N comprises:

n. constraints: a set of constraints, including constraints on all AGVs in the problem;

Solution: a solution to the problem that is not necessarily valid, but where all AGVs' paths meet the constraint set for the node;

Cost: the cost of this node solution (sum of all single AGV path costs).

The CBS algorithm uses an a-algorithm to independently plan the shortest path for each AGV at the bottom level to ensure that each AGV can reach its target location at the fastest speed without any constraints. When the path planning is completed, the upper layer algorithm detects potential collisions between all paths and manages these collisions by creating a constraint tree. Whenever a collision is found between the paths, the CBS algorithm will generate two child nodes, each imposing new temporal and spatial constraints on the conflicting AGV paths, which ensure that the AGV takes a different route or time at the point of collision to avoid the collision. Thereafter, the algorithm re-plans the constrained AGV path again using the A-algorithm, taking into account the newly added constraints, until a path solution set is found without any conflicts.

The algorithm cost function a is expressed as: where f (n) =g (n) +h (n), g (n) is the actual cost from the start point to the current node n, and h (n) is the estimated lowest cost from the current node n to the target point. Distance formula commonly used in algorithm a: manhattan distance, h _Manhattan(n)＝K×(|x_a-x_b|+|y_a-y_b |), euclidean distance: Where x _a、y_a and x _b、y_b are the start point and target point coordinates, respectively, and K represents the raster map unit distance. A main body of manhattan distance route planning is limited to travel along an x-axis direction or a y-axis direction; the euclidean distance allows for arbitrary directional movement. (Manhattan distance calculation is used because the AGV needs to move up, down, left, and right), f (n) is the approximate cost of going from the start state through node n to the target node. The algorithm continuously selects the node with the lowest f (n) value for expansion, and updates the cost of the adjacent node until the target node is reached.

Further, the system assigns an AGV that performs the ex-warehouse task to the elevator in step three, automatically returning to the first tier each time the elevator completes its action.

The invention has the advantages that:

Compared with the traditional single-path planning algorithm, the method can more effectively solve the problem of path planning of multiple AGVs in the same environment, obviously reduce conflict and repeated calculation in path planning, and improve warehouse picking efficiency. According to the invention, the running states of the AGV and the lifter are shown in detail on the 3D visual platform, and an intuitive user interface is provided, so that an operator can easily monitor the running state of the whole system, and the operation decision is optimized.

Meanwhile, a user can interact with the system through an intuitive 3D interface, and commands and adjustment tasks are input in real time, and the interaction mode is more intuitive and effective than a traditional two-dimensional interface or form. The design not only improves the maintainability and expansibility of the system, but also enables the system to be easily adapted to the development of future technologies.

Drawings

FIG. 1 is a system frame diagram of a 3D visualization platform;

FIG. 2 is a logical diagram of a system architecture;

FIG. 3 is a plan layout of a warehousing system;

FIG. 4 is a flowchart of a CBS algorithm;

FIG. 5 is a flow chart of AGV and elevator task execution based on a 3D visualization platform.

Detailed Description

The technical method of the present invention will be described in further detail with reference to the accompanying drawings. In this embodiment, the problem of the power and fault of the AGV is not considered for simulating the physical simulation scene.

The invention provides a digital twin storage system AGV (automatic guided vehicle) ex-warehouse navigation planning method, wherein a system framework diagram is shown in figure 1, a digital platform is integrated with a database of a Warehouse Management System (WMS) through an API (application program interface), and detailed data of an ex-warehouse order are obtained in real time. According to the goods warehouse position appointed in the order, the platform calculates the optimal navigation path of the AGV by adopting a CBS algorithm, and the AGV and the lifter are scheduled to complete tasks. And the 3D visual platform monitors the running condition of the AGV in real time and displays the task execution process. The method specifically comprises the following steps:

Step one: and drawing a digital three-dimensional model through Blender software by combining with a physical environment, wherein the digital three-dimensional model comprises components such as a dense storehouse goods shelf, an AGV trolley, a lifter and the like. The model needs to accurately restore the actual physical scene, and ensures that the sizes and positions of all the components are consistent with the actual physical scene. And exporting the drawn three-dimensional model into a glb/gltf or fbx file format. And the BIMface is used for carrying out model light weight processing, compressing the size of the model and reducing the cost of a CPU, a memory and a display card. And importing the light model into a digital twin visualization platform. Developing a digital twin visualization platform through three.js to realize rendering and interaction of the three-dimensional model;

The intensive storehouse cargo layer of the platform is divided into A, B, C, D vertical layers, wherein a first layer A region stores heavy cargoes or large cargoes, and a second layer B region, a third layer C region and a fourth layer D region sequentially store high-frequency cargoes, secondary-frequency cargoes and general-frequency cargoes according to the cargo access frequency; multiple AGVs complete cross-layer scheduling by one elevator.

Step two: the 3D visualization platform acquires an in-out task list of a Warehouse Management System (WMS) database through an API interface, wherein the in-out task list comprises all relevant information (cargo types, starting points, target layers, priorities and the like). After receiving the task form information, the system sends an Ajax request to inquire the state of the AGV through Axios every other communication period, schedules an idle AGV to execute tasks, and then uses a CBS algorithm to carry out path planning:

Planning a lower layer path: each AGV independently uses an a-algorithm to plan the shortest path, ensuring that each AGV reaches the target position at the fastest speed without constraint. The cost function of the a-algorithm is expressed as: f (n) =g (n) +h (n), where g (n) is the actual cost of the starting point to the current node n, and h (n) is the estimated lowest cost of the current node n to the target point (calculated using manhattan distance).

Conflict detection and management: the upper layer algorithm detects potential collisions between all paths and manages these collisions by creating a constraint tree. When a conflict exists between paths, the CBS algorithm generates two child nodes, and new time and space constraints are respectively applied to the conflicting AGV paths, so that the AGVs can be ensured to take different routes or time at the conflict points to avoid the collision. The algorithm re-plans the constrained AGV path by using the A-algorithm until a collision-free path solution set is found;

Step three: after the optimal path is calculated, the system extracts the moving coordinates of JSON format path data, and the AGV is moved in an animation manner through the points by using a Tween. Js animation library, so that the operation animation of the ex-warehouse task is completed;

step four: in a virtual reality scene, information such as the current position, the working state and the motion trail of AGV equipment is displayed in real time, the task execution process is visually displayed, and operators can intuitively know the running condition of the system.

As shown in fig. 2, the logic structure of the system includes task acquisition, path planning, task execution and status updating, that is, the system periodically queries a Warehouse Management System (WMS) database through an API interface to acquire a currently unfinished job for delivery. The task list contains information such as task ID, cargo type, cargo priority, and target point. The system firstly judges the cargo type, converts the task form into a task instruction, and after the system inquires the AGV state every other communication period through the Ajax request, the system dispatches an idle AGV to execute a command, and then the system performs path planning and calculates an optimal path. After the path planning is completed, executing AGV task animation by using a Tween. Js animation library, and simultaneously displaying the running condition, the task execution process and the overall system state of the AGV in real time by using a 3D visual platform.

It should be further noted that, in the specific implementation process, task data is obtained from the database, the system first judges the cargo type, and then the system sends the task instruction generated by the task form to the AGV, and then the path planning is performed.

As shown in fig. 3, a grid map is built before planning according to a warehouse plane layout, the warehouse is divided into a plurality of grid cells, each grid cell represents a point in the environment, and the points can be marked as passable and non-passable, so that an AGV path planning model is built.

Algorithm flow chart as shown in fig. 4, the shortest path of each AGV is calculated using the a algorithm, collisions between multiple AGV paths are processed using the CBS algorithm, new constraints are generated, and the paths are re-planned until the end of finding a collision-free optimal path.

As shown in fig. 5, the system first determines the storage floor of the goods according to the type of the goods, and when the goods do not need to be processed in a cross-layer manner:

after the AGV receives the task instruction, path planning is directly carried out, and the AGV returns to the initial waiting area after moving to the target position according to the planned path;

when goods need to be processed in a cross-layer mode:

After receiving a task instruction of goods delivery, the system determines a target goods level (A area, B area, C area and D area) according to the goods type, then sends the task instruction to the AGV, the AGV directly moves to a waiting position of the AGV after receiving the delivery task instruction, the AGV returns to a 'arrived' state of the system, the system sends a request to the PLC after acquiring the arrived state, inquires whether the state of the elevator is idle, when the elevator is idle, the AGV enters the elevator, the elevator conveys the AGV to a designated floor, and the AGV moves to the target position through a coordinate point planned by a system path; otherwise, the AGV enters a waiting state until the elevator is idle. After the AGV reaches the appointed layer, the AGV moves to a corresponding target position according to a pre-planned path to execute cargo taking-out operation; after the AGV gets the goods, feeding back to a system signal, re-planning a path by the system, sending an instruction to the AGV to enable the AGV to return to a waiting area of the lifter, returning the AGV to an arrived state by the system after the AGV arrives at the waiting area, sending a request to inquire the state of the lifter to the PLC after the system receives the signal, and conveying the AGV to a bottom layer by the lifter; after the AGV drives off the elevator and then transports the goods to the outgoing picking station, the AGV returns to the starting area of the AGV and waits for the next command of the system. At this point the elevator status becomes "idle" and returns status to the PLC, the system reads the idle status of the PLC and reassigns the next AGV to use the elevator schedule. It should be further noted that, in the implementation, the state management and synchronization mechanism of the AGV and the elevator includes:

The system communicates with the PLC to obtain the status of the elevator. The AGV and the lifter regularly report the current position and the current state (idle, action, waiting for the lifter and picking up goods) to the system, and the system writes the state information of the AGV and the lifter into a data table and synchronizes the state information to a 3D visual platform for display;

When the AGV or elevator is in use, the status is marked as "active". When the AGV or elevator is in an idle state, the state is marked as "idle". All real-time state information is synchronized on the 3D platform so as to realize real-time monitoring and management of the running condition of the system;

when multiple AGVs simultaneously request use of the elevator, the system schedules on a priority basis. Higher priority AGVs or AGVs that first requested an elevator prefer to use an elevator, and other AGVs enter a waiting state. That is, the AGV1 needs to be transported out by using the elevator in the area D, at this time, the AGV2 also has a delivery task to go to the area B, and according to the task priority, the elevator should transport the AGV1 to the first floor before executing the transport task of the AGV 2. The system ensures efficient scheduling and execution of tasks by periodically querying state information in the database.

The foregoing is only a specific embodiment of the application to enable those skilled in the art to understand or practice the application. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the application. Thus, the present application is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

Claims

1. The AGV ex-warehouse navigation planning method based on the digital twin warehousing system is characterized by comprising the following steps of:

Step two: the 3D visualization platform acquires a database-out task list of an upper layer system (WMS) database through an API interface, wherein the database-out task list comprises all relevant information (cargo types, target layers, target points and priorities) and the information is sent to the visualization platform in a task instruction form according to a task sequence; the system receives the task form information, then sends an Ajax request to inquire the state of the AGV, schedules an idle AGV to execute tasks, and then performs path planning to solve the optimal path reaching the target point;

Step three: the AGV moves to the position of the lifter according to the allocated task, the system sends a lifter request to the PLC, the PLC inquires the state of the lifter after receiving the request and returns the state to the system, if the lifter is idle, the PLC enables the lifter to reach a designated layer, and the AGV enters the lifter to perform interlayer scheduling; after the task is completed, the AGV and the elevator are updated to be idle, and the next task is continuously waited for being received;

2. The AGV (automated guided vehicle) ex-warehouse navigation planning method based on the digital twin storage system according to claim 1, wherein the digital three-dimensional model in the first step is drawn by a three-dimensional computer graphic software blueder which is open in source and free, and each part of components comprises a dense storage shelf, an AGV trolley and a lifter, and is restored according to a physical scene to build a complete digital three-dimensional platform model; BIMface is a BIM lightweight engine, which can compress the size of the model to the maximum extent and reduce the CPU/memory/display card overhead to the maximum extent; and finishing the development of the digital twin visual platform through three.

3. The AGV ex-warehouse navigation planning method based on the digital twin storage system according to claim 1, wherein in the second step, the platform periodically queries the database to obtain a current unfinished task list, and dispatches the AGVs according to different cargo types to complete cargo ex-warehouse tasks.

4. The method of claim 3, wherein the starting position of each AGV is set to be a designated area, and the AGV automatically returns to the starting area of the AGV vehicle each time the AGV completes the delivery task.

5. The digital twin warehousing system AGV ex-warehouse navigation planning method according to claim 1, wherein in the second step, the multi-AGV path planning problem is defined as: in an undirected graph, the formula is written as: g= (V, E), where V is the set of its nodes and E is the set of edges connecting the nodes; in this defined space, n AGVs are assumed, denoted by the set a= { a ₁,a₂,…,a_n }; for each AGV set to a _i ε A, a movement task τ= { s _i,d_i } from the start point to the target point needs to be performed, where s _i ε V represents the initial position of a _i and d _i ε V represents the target point position to which the designated AGV a _i needs to move from the corresponding s _i node; t= {0,1,2 … } represents the discretized time sequence, path l _i of a _i: T-V is a mapping from the time sequence and the set of nodes V,L _i (t) denotes the position of AGV a _i at time t; the AGV can choose to stay at the current position or move to the adjacent position at any moment; cost (l _i) is defined as the cost of path l _i, which is calculated in time; definition t _s is the start time of all AGV paths in the scene,For the end time of path l _i The multi-AGV path planning is to find a feasible solution from a starting position to a target position, wherein the feasible solution refers to no conflict among paths of a plurality of AGVs, and the requirements of no conflict among all AGV paths are met, namely the following formula is satisfied:

The first explanation only allows one AGV to occupy at any moment of any node, namely, position conflict is avoided; the second explanation is that at any moment, two AGVs are not allowed to move towards each other, namely, opposite collision is avoided;

The path planning uses a conflict-Based Search algorithm (Conflict-Based Search, CBS) which is a two-stage path planning framework and aims to effectively solve path conflicts when planning paths for a plurality of AGVs simultaneously; searching at the upper layer of the algorithm is constraint tree nodes (Constraint Tree Node, CT Node); the CBS algorithm creates a priority queue in the upper search, constraint tree nodes to be detected are stored in the queue, and each constraint tree node N comprises:

cost: the cost of the node solution (sum of all single AGV path costs);

The CBS algorithm uses an a-algorithm to independently plan the shortest path for each AGV at the lower level to ensure that each AGV can reach its target location at the fastest speed without any constraints; when the path planning is completed, the upper layer algorithm detects potential conflicts between all paths and manages the conflicts by creating a constraint tree; whenever a collision is found between the paths, the CBS algorithm will generate two child nodes, respectively imposing new time and space constraints on the conflicting AGV paths, which ensure that the AGV takes a different route or time at the collision point to avoid the collision; thereafter, the algorithm re-plans the constrained AGV path again using the A-algorithm, taking into account the newly added constraints, until a path solution set is found without any conflicts.

6. The digital twin warehousing system AGV ex-warehouse navigation planning method according to claim 5, wherein the algorithm cost function A is expressed as: f (n) =g (n) +h (n), where g (n) is the actual cost from the starting point to the current node n, and h (n) is the estimated lowest cost from the current node n to the target point; distance formula commonly used in algorithm a: manhattan distance, h _Manhattan(n)＝K×(|x_a-x_b|+|y_a-y_b |), euclidean distance: Wherein x _a、y_a and x _b、y_b are the coordinates of a starting point and a target point respectively, and K represents the unit distance of the grid map; a main body of manhattan distance route planning is limited to travel along an x-axis direction or a y-axis direction; the Euclidean distance allows any direction of movement; (Manhattan distance calculation is used because the AGV needs to move up, down, left, and right), f (n) is the approximate cost of going from the start state through node n to the target node; the algorithm continuously selects the node with the lowest f (n) value for expansion, and updates the cost of the adjacent node until the target node is reached.

7. The digital twinning-based warehouse system AGV out navigation planning method according to claim 1 wherein the system assigns the AGV performing the out-of-warehouse task to the elevator in step three and automatically returns to the first floor each time the elevator completes the action.