Multi-AGV Path Planning Based on Improved Smooth A * Algorithm

  • A+
Categories:AGV Data

Abstract: Advances in science and technology have prompted AGV (Automated Guided Vehicle) with many advantages to gradually replace manual handling, but the multi-AGV path planning and coordination problems that have arisen have arisen at the historic moment. Aiming at the above problems, according to the driving characteristics of AGV, a Cartesian coordinate system environment is constructed, and the traditional A * algorithm is used as the basic model. By introducing 3 axes and 2 quadrants, the number of route turnings is used to eliminate invalid alternative points, and the driving path is smoothed. Minimize the time to formulate conflict judgment standards and coordination strategies for the goal to achieve the best system operating efficiency. Through example analysis, the improved A * algorithm single AGV line can reduce the maximum number of search points by 10.9% and the number of turns by 350%; the coordination strategy with the minimum time as the goal can effectively avoid the system from falling into a local optimal phenomenon due to the priority established by subjective factors .

1 introduction

With the development of science and technology, robots gradually replace manual handling. AGV is widely used because of its mission execution, accurate positioning, environmental protection and efficient, intelligent operation and other characteristics, especially in the field of cargo transportation [1], which is recognized as the best choice to realize logistics transportation [2]. The AGV system can monitor and change the operation status, geographical location and task dispatch of each AGV through the control platform. It has the characteristics of small investment, small land occupation, short construction period, safety and convenience [3]. If it is reasonably applied to workshop logistics transportation, the scientific improvement of route algorithm and system coordination strategy can effectively reduce the human demand and greatly improve the production Efficiency, reduce production loss and cost.

In order to improve the efficiency of path planning, Qin Zhen et al. [4] used bidirectional synchronization a * algorithm to realize synchronous search of path start and end points. By introducing the concept of quadrant, Li Qiang et al. [5] improved the search efficiency by screening and eliminating invalid expansion candidate points. However, due to the constraint conditions, only the expansion points with the same quadrant position as the target point are searched, which leads to a significant reduction in the universality of the method. By distinguishing the straight and turning speeds of AGV, Wang Ziyi [6] included the path turning into the estimation function of a * algorithm. It was proved that under certain circumstances, the single AGV line can reduce the turning times by more than 60%.

Most of the above methods are aimed at single AGV. Since the transportation network is shared by multiple AGVs, there will be space-time conflicts between lines during operation. Therefore, it is necessary to formulate a certain coordination strategy to avoid collision and deadlock between vehicles. Common algorithms include a * algorithm [7], genetic algorithm [8], Dijkstra algorithm [6], artificial potential field method [9] [10] [11]. Draganjac et al. [12] solved the path conflict by waiting or removing the low priority vehicles. Banaszak et al. [13] proposed a coordination strategy of resource sharing and traffic sequencing to solve conflicts and deadlocks in dynamic environments. Yuan Yang et al. [14] introduced the load optimization a * algorithm to realize the load balance of road network, effectively reduce the probability of AGV conflict, and improve the working efficiency of the system. Helina et al. [15] introduced the principle of time window into Dijkstra algorithm to realize multi AGV collision free route planning, and proved the effectiveness of entering time window by combining with an example. Xu lunhui et al. [16] set the priority in descending order according to the time sequence of tasks, and coordinated the conflict paths in order of priority from low to high. This scheme can effectively eliminate all conflicts in the road network, but only taking the task release time as the route coordination sequence standard can lead to a significant increase in the total time required for the system to complete all tasks.

Based on this, this paper constructs the Cartesian coordinate system environment according to the road network and vehicle driving characteristics; proposes an improved a * algorithm with 3-axis-2 quadrant as the screening constraint, eliminates invalid search points through constraints on the premise of universality, and improves the search efficiency by introducing the steering index to optimize the path smoothness; based on the improved algorithm, combined with the Based on the principle of time window, the corresponding coordination strategy is formulated based on the principle of the shortest total working time of the system, so as to seek the best operation efficiency of the system.

2 Building coordinate system map model

The grid method was proposed by wehowden [17]. The unit grid is used to divide the map, and the free grid and barrier grid are distinguished by combining the gray value. The size of the grid plays a decisive role in the accuracy. Reducing the grid can improve the accuracy, but it will lead to the geometric growth of the map information [18], thus reducing the efficiency of path planning. Based on the grid method, combined with the orthogonality and positioning accuracy of AGV operation line, an improved Cartesian coordinate system map model is constructed as the planning environment, that is, the first quadrant of Cartesian coordinate system is taken as the electronic map, and the accurate positioning of AGV operation is completed by using two-dimensional coordinates. This map model can also meet the requirements of orthogonality of lines and convenient calculation of path length.

3 Improved a * algorithm

3.1 Improve search efficiency

The traditional a * algorithm takes the current point as the center and traverses the points within the limited range in each direction as the expansion candidate points, which is the same as the eight code number problem. At present, most of the AGV operation paths are orthogonal lines. Based on the coordinate system map, if the eight code number traversal principle is used for path planning, the four invalid points on the diagonal (Figure 1) will still be operated first and then eliminated, thus reducing the planning efficiency.

Multi-AGV Path Planning Based on Improved Smooth A * Algorithm

Fig. 1 Schematic diagram of alternative points of traditional a * algorithm

Li Qiang et al. [5] selected and expanded the candidate points by introducing the concept of quadrant. However, because only peripheral points in the same quadrant as the target are selected, its application scope is limited. In view of this, this paper puts forward the concept of positive and negative quadrants, constructs 3-axis-2 quadrant search method to realize the selection of expansion candidate points, that is, taking the current point as the origin of the secondary axis, establishing⻟𝑦′ orthogonal coordinate system, and the unit length fixed points on the four semi axes are the search alternative sets (Fig 2) According to formula (1) - (3), determine the positive and negative quadrant relationship between the target point and the current point, eliminate the invalid search axis, and complete the selection of candidate points.

Please download the rest

Download Multi-AGV Path Planning Based on Improved Smooth A * Algorithm Win All pdf 700K
Download Link


You must beto post a comment.