Space-time conflict constrained A* algorithm for path planning of multiple AGVS

  • A+
Categories:AGV Data
Excerpt

Abstract:To solve the path conflict problem of AGV in warehousing and logistics transportation system, an A* algorithm based on space-time grid and conflict constraint is proposed. Firstly, the time axis is added to the topological grid map to build the spatiotemporal map model. Then, according to the characteristics of spatiotemporal map and the conflict constraints, the sub node extension rules and node evaluation functions of the A * algorithm are redesigned. The improved A * algorithm is used to plan the path for each AGV according to the priority order. After planning a path, the node information in the spatiotemporal map is recorded with the mark table, and then the new path is searched with the improved A * algorithm and the mark table. The simulation results show that the algorithm can effectively avoid collision and deadlock, and can comprehensively consider the time cost of waiting and changing path conflict resolution strategies, and obtain the path with less time cost.

0 Introduction

With the rapid development of e-commerce, express delivery and new energy and other emerging industries, the overall demand of storage AGV has been greatly driven, which has injected new vitality into the research and development and application of intelligent storage system. For the large-scale task and shelf intensive storage environment, path planning algorithm plays a key role in improving the overall performance of intelligent storage system, reducing operating costs and improving enterprise profits. How to solve the path conflict between AGVs has always been one of the key issues in multi AGV path planning.[1]。

Path conflict refers to the intersection or overlapping of routes of multiple AGVs in the same period, which can be divided into intersection conflict, chasing conflict and opposite conflict [2]. Once the path conflict is not handled properly, AGV collision or deadlock will occur, which seriously affects the efficiency of multi AGV system. Generally speaking, there are two methods to solve the path conflict of AGV: (1) global planning method, namely static path planning method, which mainly uses mathematical planning method to plan collision free path for AGV in the map in advance [3-4]. This method can plan the global optimal path for the system, but the AGV running in a highly dynamic environment can not always reach the designated location in the planning time, and with the increase of the number of AGVs, there will be path conflict. (2) Local planning method, which determines the path of AGV according to the real-time state of the system, is also called dynamic planning strategy. For example, Tanaka et al. [5-10] dynamically adjusted the path of AGV according to the real-time state of the road network in order to avoid the path conflict and deadlock of AGV; Yu Henian et al. [11] proposed a multi-step forward-looking algorithm to avoid the collision, and the AGV planned the next k-step path according to the real-time status of the system. Dynamic path planning can deal with the collision between AGVs in time, but can not get the global optimal path.

Considering the advantages and disadvantages of the above two methods, many scholars propose two-stage path planning strategy. The global path planning is adopted in the offline phase, and the local adjustment is made in the online phase according to the conflict type. For example, Tai Yingpeng et al. [12-13] adopted a two-stage control algorithm based on time window. In the first stage, the global optimal path was planned for each AGV. In the second stage, the node time window of each AGV was calculated. According to the overlap of time windows, path conflict was detected, and the conflict was solved by changing paths and waiting strategies. To further reduce the burden of dynamic phase planning, he Lina et al. [14-15] ]In the off-line phase, Dijkstra algorithm is combined with time window principle to plan the collision free paths of each AGV in sequence. This method greatly reduces the probability of collision in the dynamic phase and simplifies the complex path adjustment process in the online phase. In the process of conflict resolution, the two-stage path planning strategies do not comprehensively compare the cost of waiting and Path replacement to plan the optimal path.

In this paper, in order to plan a path with less time consumption on the basis of ensuring that the path has no conflict, a * algorithm based on spatiotemporal conflict constraint is proposed. This method integrates conflict detection and avoidance into the node search process to achieve conflict free path planning, and finds the path that takes the least time by comprehensively evaluating the cost of the sub nodes after avoidance. In the process of multi AGV path planning, the improved a * algorithm is used to plan the path for each AGV according to the priority order. When a path is planned, the node information in the space-time map is recorded with the ݉ܽ table, and then the new path is searched by the improved a * algorithm combined with the ݉ mark table.。

1 A spatiotemporal map model for multi AGV path planning

This paper is based on the application background of warehousing logistics. Because the goods need to be transported to the designated place in the warehouse logistics, it is necessary to set up nodes with location information to indicate the loading point or unloading point for AGV; meanwhile, in the multi AGV path planning, it is necessary to calculate the accurate occupation time of each node, and grid is more appropriate to represent the size of nodes. In view of this situation, this paper carries out topology modeling on the basis of grid map. The key grid topology is the path node, while the ordinary grid topology is the edge to maintain the connectivity, so the topological grid map is constructed, as shown in Figure 1.

Space-time conflict constrained A* algorithm for path planning of multiple AGVS

a Topological grid map

Space-time conflict constrained A* algorithm for path planning of multiple AGVS

b Spatiotemporal map

Figure 1 map model and path display

In the topological raster map model, two-dimensional matrix can be used to record the state of each node, but the specific occupation time of each node can not be recorded. In multi AGV path planning, it is necessary to consider the specific occupation time of each node to plan the optimal path. Therefore, this paper adds a time axis on the basis of topological grid map to establish the spatiotemporal map model, as shown in Fig. 1b,


Please download the rest


Download Space-time conflict constrained A* algorithm for path planning of multiple AGVS Win All pdf 737K
Download Link

Comment

You must beto post a comment.