Sensor-network-based navigation of delivery robot for baggage handling in international airport

Abstract

Automated guided vehicles (AGVs) have been regarded as a promising means for the future delivery industry by many logistic companies. Several AGV-based delivery systems have been proposed, but they generally have drawbacks in delivering and locating baggage by magnet line, such as the high maintenance cost, and it is hard to change the trajectory of AGV. This article considers using multi-AGVs as delivery robots to coordinate and sort baggage in the large international airport. This system has the merit of enlarging the accuracy of baggage sorting and delivering. Due to the inaccurate transportation efficiency, a time-dependent stochastic baggage delivery system is proposed and a stochastic model is constructed to characterize the running priority and optimal path planning for multi-AGVs according to the flight information. In the proposed system, ultra-wideband technology is applied to realize precisely positioning and navigation for multi-AGVs in the baggage distribution center. Furthermore, the optimal path planning algorithm based on time-window rules and rapidly exploring random tree algorithm is considered to avoid collision and maneuverability constraints and to determine whether the running path for each AGV is feasible and optimal. Computer simulations are conducted to demonstrate the performance of the proposed method.

Keywords

Stochastic time-dependent network automated guided vehicle delivery robot path planning baggage handling system

Introduction

With the continuous development of aviation technology and the rapid improvement of economic growth, alternative long-distance flights replace other sorts of transportation as the priority for the majority of customers who want convenient and prompt service. According to the International Air Transport Association report, global air passenger demand increased 3.6% year-on-year in terms of revenue passenger kilometers in July 2018. In terms of available seat kilometers, the monthly transportation capacity increased by 3.2%, and the passenger capacity rate increased to 85.7%.¹

There are some baggage management problems in today’s large international airports. On the one hand, three factors (the rapid growth of passengers, the shortage of staff, and the fixed capacity of the airport) lead to bear the pressure of more and more checked luggage.^1,2 On the other hand, the baggage sorting equipment has a prolonged use time, resulting in the increase of maintenance fee. These problems will lead to more extra time for baggage screening, sorting, and transportation. Therefore, the automatic baggage sorting and transportation system must be designed and upgraded to meet the requirements of a large number of checked baggage.¹

Based on the above analysis, in this article, by analyzing the characteristic of automated guided vehicle (AGV) operation, we find that traditional baggage transportation is based on the magnetic wire in the international airport; meanwhile, the lack of required AGVs,³ the limited path planning,⁴ and the traffic constraint conditions⁵ will lead to inaccurate transportation of baggage. Firstly, when the multi-AGVs start running in the baggage distribution center (BDC), three steps (the baggage security inspection, automatic sorting, and transportation by AGVs or delivery robots) are completed in order. Then, multi-AGVs identify the baggage’s barcode and collect relevant flight information (the flight number and scheduled departure time) to determine the priority and order of AGV transportation. Besides, the three ultra-wideband positioning base stations (UWB-PBSs) are placed in BDC to obtain the real-time location of multi-AGVs. Moreover, the stochastic path planning algorithm based on the time-window rules and rapidly-exploring random tree (RRT) navigation algorithm is proposed to implement the optimal trajectory of AGV in the BDC.

The main contributions of this article are as follows:

One novel baggage handling system without magnetic wine is proposed to apply multi-AGVs in a large international airport.

The three UWB-PBSs, combined with the time difference of arrival (TDoA) algorithm, are proposed to obtain the location of multi-AGVs.

As for the operation of AGV, one priority order function can be implemented to determine how multi-AGVs perform in order.

As for the collision problem, the stochastic time-dependent path planning algorithm, combined with the RRT algorithm and time window, is provided to the multi-AGVs, which makes the relatively optimal trajectory from the departure point to the baggage collection terminal (BCT).

The remainder of the article is organized as follows. In the “Related work” section, we discuss the related work about the positioning methods and optimal path planning of multi-AGVs. In the “UWB positioning method for multi-AGVs” section, the AGV dynamic system model and the UWB positioning method are introduced. The “Proposed solution for path planning in AGV navigation” section mainly describes the stochastic time-dependent path planning based on the RRT algorithm and the time-window rules. Computer simulations are demonstrated in the “Simulation results” section to show the performance of the proposed method. The last section is a brief conclusion of this article.

Related work

In this section, some related publications are reviewed first. The similarities and differences between this article and the reviewed publications are discussed to show this article’s novelty.

In the positioning applications using multi-AGVs, the coverage performance is a key system metric. Several interesting problems have been studied. The destination coded vehicles (DCV) system developed by Vanderlande company was used in the traditional extensive BDC. DCV can only transport according to the fixed line and cannot optimize the path of DCV according to the real-time baggage transportation information.² The problem of planning paths for unicycle robots⁶ (with constant speed and bounded angular velocity) was considered to visit a set of sensor nodes in a sensing field with obstacles while minimizing the path lengths. An advanced UWB method was used to navigate the AGV to the vicinity of the working position. Then, computer vision technology was used to accurately determine the position of the vehicle, thereby establishing a high-precision AGV self-localization method.⁷ The nonoptical-based method was informed about localizing AGVs in the indoor environment via channel state information.⁸ A combination of indoor UWB wireless positioning sensors and ultrasonic sensors for obstacle distance measurement and avoidance was used to build optimized AGV robots that can efficiently implement indoor navigation.⁹ Based on the inertial navigation system (INS)/UWB integrated model, an interactive multiple model algorithm was proposed in AGV indoor location.¹⁰ The accuracy of positioning using UWB radio signals and TDoA method and extended Kalman filter algorithm is in the indoor navigation system.¹¹ The authors assumed that the AGV position was unknown, using an autonomous receiver to measure the received signal strength, locating its position, and sharing the information with other receivers nearby.^12
–14 A distributed algorithm was proposed to detect the optimal local coverage by the unmanned aerial vehicle.¹⁵ Cellular networks were proposed in the monitoring equipment.¹⁶ A novel positioning method was described in mobile targets.^17,18

The coverage problem related to AGVs has also been studied in the application of multi-AGV path planning. There are various constraints in multi-AGV path planning, such as collision-free constraints and time-window constraints. Path planning involves scheduling, scheduling, and task routing.¹⁹ Similar to the traveling salesman problem (TSP), the multi-AGV path planning problem was challenging to find the shortest path (time) due to the ample search space.²⁰ TSP algorithm based on the generation of competent individuals was proposed.²¹ The discrete Drosophila optimization algorithm²² was developed for TSP. Moreover, a reliable path planning algorithm²³ was proposed, which can accommodate the stochastic and time-dependent public transportation network, and an extremum seeking algorithm²⁴ was developed for a robot using the topology map of a wireless sensor network. An online 3D trajectory optimization approach²⁵ was proposed to secure the communication between a moving ground node and an unmanned flying robot in the presence of stationary or mobile eavesdroppers. The trajectory of the unmanned robot²⁶ was optimized in threat environments, such that the unmanned flying robot can fly to a destination with the minimum threat.

UWB positioning method for multi-AGVs

Consider a simulated baggage handling scenario, where m stationary ground nodes talk to each other via legitimate links, i AGV locates in the BDC. UWB indoor two-dimensional positioning technology based on the TDoA algorithm is applied to locate the multi-AGVs. The positioning system includes an active UWB tag installed at the top of AGVs, and three UWB-PBSs installed on the ground (see Figure 1). The following AGV model is considered for the AGVs in equation (1)

\{\begin{cases} {\dot{x}}_{i} (t) = v_{i} (t) cos (θ_{i} (t)), \\ {\dot{y}}_{i} (t) = v_{i} (t) sin (θ_{i} (t)), \\ {\dot{θ}}_{i} (t) = u_{i} (t) \end{cases}

where $θ_{i} (t)$ is the heading of AGV with respect to the x axis, and $v_{i} (t)$ and $u_{i} (t)$ are the linear and angular speeds on the linear and angular speeds on the horizontal plane, respectively. $V_{i}^{max}$ and $U_{i}^{max}$ denote the constants, and $0 \leq v_{i} (t) \leq V_{i}^{max}$ and $0 \leq u_{i} (t) \leq U_{i}^{max}$ .

Figure 1.

AGV UWB positioning. AGV: automated guided vehicle; UWB: ultra-wideband.

TDoA technology is a method that employs at least five communications between the UWB tags and PBSs to locate multi-AGVs. By comparing the time difference between the signal sent by the UWB tags and the three UWB-PBSs to calculate the distance difference between the signal and each BS. Therefore, it is not necessary to detect the signal transmission time, and the system’s requirements for time synchronization are significantly reduced.

The most important challenge is the calculation of the intersection between the three UWB-PBSs. This intersection can be found by writing the mathematical formulation of each base station based on the coordinates of AGVs and these exit an intersection positioning signal among three UWB-PBSs. Assume that the positioning base station uses the line-of-sight channel. $[x_{i}, y_{i}, 0] (i = 1, 2, 3, \dots, i)$ denotes the coordinates of the position of i AGV, and m denotes the number of UWB-PBSs. $[x_{m}, y_{m}, z_{m}]$ denotes the coordinates of the position of UWB-PBSs. $r_{im} (t)$ denotes the distance between i AGV and m PBSs at time t. During the experiment, the signal will be transmitted from three UWB-PBSs and intersects in one point; therefore, this intersection point is the position of the AGV, as shown in Figure 1. $τ_{s 1}$ denotes the time difference between the two UWB-PBSs. Then, the distance difference between the s’th (s = 1, 2, 3) signal and the received signal of the AGVs can be calculated with $r_{s 1} = r_{s} - r_{1} (s = 2, 3, \dots, s)$ . Therefore, the coordinates of AGVs can be calculated by the equation of the transmission distance difference. According to the geometric meaning, the relationship between AGVs and UWB-PBSs is described from equations (2) to (4)

{(x_{m} - x_{i})}^{2} + {(y_{m} - y_{i})}^{2} + z_{i}^{2} = r_{im}^{2}

r_{s}^{2} = {(r_{s 1} + r_{1})}^{2} = r_{s 1}^{2} + 2 r_{s 1} r_{1} + r_{1}^{2}

{(x_{i} - x_{s})}^{2} + {(y_{i} - y_{s})}^{2} + z_{s} ​^{2} = r_{s 1}^{2} + 2 r_{s 1} r_{1} + r_{1}^{2}

Substituting equation (2) into equation (4), let $k_{S} = x_{m}^{2} + y_{m}^{2} + z_{m}^{2}$ and $x_{s S} = x_{s} - x_{S}$ , the simplified equation (5) can be considered, and equation (6) is shown when S = 3

2 r_{s 1} r_{1} +2 x_{s 1} x_{i} + 2 y_{s 1} y_{i} = k_{s}^{2} - k_{1}^{2} - r_{s 1}^{2}

[\begin{matrix} x_{i} \\ y_{i} \end{matrix}] = - r_{1} [\begin{matrix} r_{21} \\ r_{31} \end{matrix}] {[\begin{matrix} x_{21} & y_{21} \\ x_{31} & y_{31} \end{matrix}]}^{- 1} + \frac{1}{2} [\begin{matrix} k_{2} - k_{1} - r_{21}^{2} \\ k_{3} - k_{1} - r_{31}^{2} \end{matrix}] {[\begin{matrix} x_{21} & y_{21} \\ x_{31} & y_{31} \end{matrix}]}^{- 1}

where $r_{1} = \sqrt{{(x_{i} - x_{1})}^{2} + {(y_{i} - y_{1})}^{2} + {(z_{i} - z_{1})}^{2}}$ . The coordinate of multi-AGVs can be solved by equation (6) when all parameters are positive.

In terms of the problem of equation (2), the estimated distance between the multi-AGVs and three UWB-PBSs exits the distance estimation error caused by γ that exits in the simulated environment, which results in the problem that the intersection does not meet at one point. We want to minimize the distance estimation error, so the position error correction method based on Newton–Raphson iterative algorithm is proposed. The distance relationship between actual position of i AGV and m PBSs is shown in Figure 2.

Figure 2.

Distance relationship between actual position of i AGV and m base stations. AGV: automated guided vehicle.

Aiming at minimizing the position error and based on the assumption, we assume the real estimated distance in equation (7), and equation (8) shows a new function related to the relationship between p and p+1 Newton–Raphson iterations (p = 1,…, p). Therefore, the final iterative estimation error makes the maximum estimated value in the proposed system

r_{im} \pm γ = ‖{(x_{m} - x_{i})}^{2} + {(y_{m} - y_{i})}^{2} + z_{i}^{2}‖

where $‖•‖$ denotes norm

f (r_{im}^{k + 1}) = f (r_{im}^{k}) + \dot{x} d x_{i} + \dot{y} d y_{i} + \dot{z} d z_{i} + \dot{γ} d γ = 0

where $\dot{x} = \frac{\partial f (r_{im})}{\partial x_{i}}, \dot{y} = \frac{\partial f (r_{im})}{\partial y_{i}}, \dot{z} = \frac{\partial f (r_{im})}{\partial z_{i}}, \dot{γ} = \frac{\partial f (r_{im})}{\partial γ}$ .

The steps of error correction algorithm are as follows:

Step 1: Select the initial point of iteration;

Step 2: Calculate function using equation (7);

Step 3: Calculate $r_{im}^{k + 1}$ using equation (8);

Step 4: Return to step 2 for iteration until convergence.

To select the proposed positioning method, we compare the proposed system and other existing localization schemes (RSSI, Wi-Fi, and Zigbee) in terms of the localization estimation error. The result is shown in Figure 3. It shows that the maximum estimation error for the proposed method is around 0.52 m within 100% accuracy. However, the estimation error for the other three technologies (RSSI, Wi-Fi, and Zigbee) is above 0.8 m, particularly Zigbee approaches around 3.2 m in 100% accuracy. Therefore, it can be proven that the UWB positioning method is well than the others, and its performance is excellent in the simulated environment.

Figure 3.

Performance comparison of UWB and other three technologies in terms of the localization estimation error (RSSI, Wi-Fi, and Zigbee). AGV: automated guided vehicle; UWB: ultra-wideband.

Proposed solution for path planning in AGV navigation

To solve the problem in path planning for multi-AGVs, we propose one path planning method combined with the time-window algorithm and the RRT algorithm. Based on the principle of the time window and the RRT algorithm, the optimal path of each AGV is planned in sequence. Each AGV can obtain its running time window and passing priority through the k tasks. Moreover, we determine the priority for multi-AGVs to avoid collisions caused by time-window conflicts between multi-AGVs. There are M check-in counters, N BCT, and i multi-AGVs in the simulated BDC, and these three parameters need t_s , satisfying $i \geq M > > N$ .

Path planning contributes to seeking the optimal path without collisions for each AGV. Firstly, we need to define a safe distance for each AGV, which can initially avoid collisions between multi-AGVs. Then, the time-window algorithm is applied in the multi-AGVs to prevent collision further. Moreover, although the time-window rules can solve simple collision problems, the RRT algorithm also needs to be implemented to get the optimal path for each AGV. Finally, after we obtain the optimal path planning for each AGV, the multi-AGV performance needs to be implemented according to their priority, so the priority of each AGV is in the final stage.

The external interference and unpredictable factors can affect the performance fluctuations, and conflicts could occur. Assume that the volume of each AGV is 1 m/s, $d_{safe} = 1 m$ denotes the safety distance between any two AGVs, each pair of vehicles must meet the minimum safety distance at any time; therefore, the designed safety area is shaped as a circular area with the AGV as the center and 1 m as the radius.

Although the safety distance or the safety area can solve the collision problem, the proposed path planning based on the time-window algorithm is possible to construct the optimal path for each AGV. Firstly, we introduce the time-window algorithm. The time window is a period from the initial position to the baggage handling termination for each i AGV. The time window is divided into two time periods: reserved time-window (RTW) and free time-window (FTW). $R_{i} (k, t)$ denotes the RTW occupied by one AGV in motion and $F_{i} (k, t)$ denotes the FTW that is the interval time in the RTW, and it is used to plan the motion paths of other AGVs, as shown in equation (9), and the structure of time-window for AGV is shown in Figure 4

\{\begin{matrix} R_{i} (k, t) = [t_{a}^{i} (k), t_{b}^{i} (k)] \\ F_{i} (k, t) = [t_{c}^{i} (k), t_{d}^{i} (k)] \end{matrix}

where $[R_{i} (k, t), F_{i} (k, t)] \in t$ and $F_{i} (k, t) \in R_{i} (k, t)$ . In the RTW, $t_{a}^{i} (k)$ is the time for i AGV when it implements k tasks and $t_{b}^{i} (k)$ is the time for i AGV that completes the current task k; in the FTW, $t_{c}^{i} (k)$ is the time for i AGV when the others start their task, and $t_{d}^{i} (k)$ is the time when they complete their tasks.

Figure 4.

The structure of time window.

The time-window algorithm mainly solves the same-direction conflict and the deflection conflict between two AGVs. We use one example with two different AGVs (the black line represents AGV1 and the red line represents the AGV2) to explain the time-window algorithm in Figure 5. The two AGVs start running within [0, t]. Figure 5(a) shows the overall time-window for all multi-AGVs. If the two vehicles run together, the time-window is shown in Figure 5(b); if the two AGVs run toward the opposite direction in [4t, 6t], the time-window is shown in Figure 5(c) and cross each other in [5t, 7t], as shown in Figure 5(d). Using the RTW and FTW is to calculate the running time in k’th task.

Figure 5.

Time window for two AGVs. AGV: automated guided vehicle.

Moreover, we propose the RRT algorithm combined with a time-window algorithm to make the optimal trajectory for multi-AGVs in this article. The RRT algorithm is a sampling of a position-based motion-planning algorithm that connects a series of random sampling points from the barrier-free space to establish a path from the check-in to BCT. Compared with the traditional path planning methods (cellular method²⁷ and potential field method²⁸), the RRT algorithm provides computational savings by avoiding building obstacles in the state space. Before using the RRT algorithm to get the relative optimal path of multi-AGVs, the exact location of multi-AGVs should be obtained. The circular area of AGV can be treated as the center of mass due to the definition of safety distance.

When one AGV runs independently, the other AGVs based on the time-window algorithm start to calculate their trajectories. In the actual application scenario, the trajectory exits the deflection angles (more than 90°) during the AGV running in the BDC, which makes it difficult for multi-AGVs to achieve motion angle adjustment and motion attitude adjustment. Since each AGV has two control variables $v_{i} (t)$ and $u_{i} (t)$ , the solution space of the considered problem is $O (2^{n})$ during the interval if the solution space remains unchanged, which may result in the unsatisfied trajectory performance, and the realization of locating multi-AGVs may bring high probability. Thus, $v_{i} (t)$ and $u_{i} (t)$ are expected to vary during the interval $[k t, (k + 1) t]$ to improve the trajectory performance, which leads to a solution space that is much larger than $O (2^{n})$ and makes the considered problem more complex. Therefore, to address this challenging problem, an optimization method based on the RRT algorithm is proposed to construct the AGV trajectories more efficiently.

The time interval can be discretized $[k t, (k + 1) t]$ into L small slots with equal lengths τ, such as, $t = L τ$ . When AGV moves in each t, it predicts the trajectory in the next time slot to change the whole RRT path, its deflection angle is reduced, and the total length of AGV is also shortened. Without loss of generality, it is to take the trajectory planning for the interval $[0, t]$ seriously. The objective function is proposed to minimize and make an optimal path planning, which is shown in equation (10). The AGV dynamic model can also be discretized and simplified in equation (11), and this simplification makes it easy to control the multi-AGVs

J = min (\sum_{i = 1}^{a} \sum_{j = 1}^{n} \sum_{l = 1}^{L} f (p_{i j} (l τ)))

\{\begin{cases} x_{i} (l τ) = x_{i} ((l - 1) τ) + v_{i} (t) cos (θ_{i} ((l - 1) τ)), \\ y_{i} (l τ) = y_{i} ((l - 1) τ) + v_{i} (t) sin (θ_{i} ((l - 1) τ)), \\ θ_{i} (l τ) = θ_{i} ((l - 1) τ) + u_{i} ((l - 1) τ), \\ u_{i} \in {0, U_{i}^{max}}, \\ v_{i} \in {0, V_{i}^{max}} \end{cases}

where l = 0, 1, 2,…, L. Compared to equation (1), $v_{i} (t)$ and $u_{i} (t)$ are fixed in equation (11). $u_{i} ((l - 1) τ)$ remains the same option in the slot $(l - 1) τ$ . The trajectory of multi-AGVs is planned by repeatedly minimizing the cost function, subject to equation (10) for L time intervals. Specifically, having the starting points and BCTs for multi-AGVs, a set of trajectories for one interval (with L slots) are constructed. With the positions and deflection angle at the end of the L’th slot, which are the initial status of another time interval, the trajectories for L slots are constructed. Therefore, the planned trajectory for L slots is the core of constructing the whole path planning.

Suppose there are k tasks assigned to i AGVs, and each AGV needs to implement one task during their operation. Therefore, how to determine their priority is significant. According to the takeoff time of the plane and the optimal path for each AGV, we design the priority algorithm for each AGV, that is, $AG V_{1} > AG V_{2} > ... > AG V_{i - 1} > AG V_{i}$ (i is real). Then, the RRT algorithm is used to conduct optimal path planning for the AGV with the highest priority, and the time of its entry and departure in the current task interval is obtained, that is, the RTW.

At this moment, we need to determine which AGV has the highest priority. When all i multi-AGVs located at the check-in counters are equipped with luggage, it will continue the path planning and priority judgment for each AGV. It is not accurate for multi-AGVs to design the path planning at different times, which leads to the accumulation and redundancy of the planned trajectory. In addition, according to the daily management of flights, planes start checking in 180 min before departure and stop checking in half an hour before departure. We divide the 150 min into periods of 30 min. Since the scheduled departure time of the flight and the check-in time for passengers are the most important factors in the baggage handling system and there are no planes taking off at the same time in one international airport, so $t_{sch}$ denotes the scheduled departure time and $t_{AGV}$ denotes the check-in time, and $t_{ξ}$ denotes the priority decision parameter in equation (12). It is the product of the absolute value of the time difference between the time of baggage check-in $t_{AGV}$ and the scheduled time for flight departure $t_{sch}$ and the objective function J in equation (10). Therefore, these two parameters $t_{sch}$ and $t_{ξ}$ are used as the time priority decision weights to design the priority for each AGV

t_{ξ} = J |t_{AGV} - t_{sch}|

When all i multi-AGVs at the check-in counter are loaded with luggage, we consider two occasions: the same flight and the different flights. As for the same flight, the priority of multi-AGVs can be determined using $t_{sch}$ . When the check-in time is close to the time that the counters are closed, the priority for this AGV needs to be determined first. For the other time from before 3 h to before 2.5 h, the check-in time earlier causes a higher priority. However, we need to consider a complex occasion. Due to the different scheduled takeoff time $t_{sch}$ for different flights, there is a clear difference in the priority of the AGV corresponding to the check-in luggage. Therefore, $t_{sch}$ is used to obtain initially the priority in the same flight, which sorts the same flight occasion. Then, another priority decision parameter $t_{ξ}$ is used to obtain others priority for those flights, which are not very close to the scheduled departure time, $t_{ξ}$ is smaller than the AGV has the higher priority. Based on the above analysis, the priority for the same flight and different flights can be obtained. Table 1 provides the priority for occasions on the same flight and different flights.

Table 1.

Priority for occasions in the same flight and different flights.

AEST time	AGV1	AGV2	AGV3
10:00:00	QF24	QF5	QF31
10:00:30	QF5	QF24	QF24
10:01:00	QF31	QF24	QF5
10:01:30	QF5	QF5	QF24
10:02:00	QF31	QF24	QF31
10:02:30	QF24	QF31	QF5
10:03:00	QF31	QF31	QF24

AEST: Australian Eastern Standard Time; AGV: automated guided vehicle.

Three planned flights are used as an example in the simulation. QF24 takes off at 12:30:00 (AEST), QF5 takes off at 12:40:00 (AEST), and QF31 takes off at 12:50:00 (AEST). From 10:00:00 (AEST) to 10:00:30 (AEST), it can be seen from Table 1 that QF24 will take off firstly, then QF5, and the last one is QF31, so the priority of AGV can be obtained according to the close scheduled flight time with AGV1 > AGV2 > AGV3. From 10:00:30 (AEST) to 10:01:00 (AEST), the table shows that QF24 will take off firstly, then QF5, so AGV2 and AGV3 have higher priority than AGV1, but AGV2 and AGV3 will run to the same BCT, so the priority of these two AGVs is used the cost function J to obtain. If the total of AGV2 is less than AGV3, the priority of AGV2 is higher than AGV3 and vice versa. The other time periods are as the same analysis.

Based on the above analysis, this article puts forward the principle of the time window and RRT algorithm linked to the priority. There is no inspection planning of AGV path conflicts, and the path planning works in real time so that the realization of dynamic path planning of multi-AGVs can be made in BDC.

Simulation results

In this section, the computer simulation results of the proposed algorithm are collected and analyzed as follows. An experimental simulation area is set up with a length of 100 m and a width of 60 m. The maximum linear speed meets 1 m/s for all i multi-AGVs. According to the requirement of this simulation, three start points for multi-AGVs and three BCTs are put in the simulation area. D ₁, D ₂ and D ₃ denote the total path for AGV1, AGV2, and AGV3, respectively. The simulation for this case with k = 10 intervals is conducted, and each interval is divided into L = 100 consecutively, and there are nonoverlapping slots, which means each slot is 1 s. Therefore, an RRT trajectory can have up to 1000 intervals, and the number of subtrajectories selected from each RRT is 100. The number of combinations tested is 100 for each interval.

In the simulation, the length of the path obtained by the RRT algorithm should be measured first starting from a simple case with single AGV in the initial position [10,0] and a single BCT in [100,50]. Before running, the maximum linear speed of AGV is set up to 1 m/s. The total path length can be obtained. The traditional RRT trajectory and after RRT optimization trajectory are operated to perform the performance of AGV. Figure 6 compares the performance with the proposed method of one AGV with that of the nonproposed method. It can be seen from Figure 6 that the original total path for the AGV D ₁ is 112.2721 m (shown in the blue line), and the blue line is applied to the proposed method with 111.3338 m. Compared with the two simulation results, it can be proven that the proposed method is better for all multi-AGVs.

Figure 6.

The comparison pictures between the original path planning and after RRT and time-window optimization.

Now, we consider a complex example with an extra AGV using two AGVs. Let these two AGVs start from two different initial points with the coordinates in [10,0] and [20,0] and the same BCT in [100,50]. Both AGVs have the same maximum linear speed with 1 m/s. It can be seen from Figure 7 that $AG V_{2}$ (its optimal path is 106.672 m) has the highest priority than $AG V_{1}$ with 111.6199 m.

Figure 7.

The simulation scene with two check-in counters and one baggage collection counter.

We consider a case with three AGVs and three BCTs in the same BDC, as shown in Figure 8. These three AGVs have the same maximum linear speed with 1 m/s. In Figure 8, the priority of three AGVs is $AG V_{2} > AG V_{3} > AG V_{1}$ . The blue line represents the $AG V_{2}$ with the highest priority, and its total running trajectory is 88.7638 m, then the red one $AG V_{3}$ with 97.5334 m, the lowest priority is the black one $AG V_{1}$ with 109.3403 m. Adding one AGV makes the trajectories more complex.

Figure 8.

The simulation scene with three check-in counters and three baggage collection counters.

Now, focusing on the impact of these five parameters (D ₁, D ₂, D ₃, i, and m) on the performance over 100 intervals for each parameter configuration, it has a significant influence on mitigating the influence of randomness. Therefore, the total distance in D ₁, D ₂ and D ₃ is essential to be considered. Except D ₁, D ₂, and D ₃, all the other system parameters remain the same as the above case with three AGVs and three BCTs in BDC, as shown in Figure 9. It is clear that when intervals increase, the total distance decreases for these three AGVs. With the increasing number of multi-AGVs, the total distance also decreases. It can be proven that the increase in intervals leads to a feasible movement space for multi-AGVs, which is more likely to result in a better performance.

Figure 9.

Impacts of intervals on trajectory performance. (a) Distance of single AGV, (b) distance of two AGVs, and (c) distance of two AGVs.

Finally, the computer time of the proposed method is analyzed for different parameters on a laptop with Intel (R) Core (TM) i5-8250U CPU@1.60 GHz 1.80 GHz and 8.00Gb RAM. As discussed in the “Proposed solution for path planning in AGV navigation” section, the computation time depends on L, i, and m. The computation time is measured for evaluating 1000 combinations under some configurations (see Table 2), from which it is obvious that the proposed method can be implemented fast and more accurate. The goal is to find better trajectories for multi-AGVs to improve their positioning performance; more combinations can be tested as long as the overall computation time is smaller than the considered interval. When the circle is constructed, the preliminary work of the RRT algorithm is finally obtained. The flight information (scheduled takeoff time and baggage weight) can be identified according to the baggage tag on the AGV. Then, according to the starting counters and the locations of BCTs, the relative optimal path of multi-AGVs can be obtained by the RRT algorithm and the time-window rules.

Table 2.

Computation time for evaluating the performance of AGVs.

m = 1, E = 1	L	25	50	75	100
	Time (s)	140.3	134.4	121.5	111.2
E = 1, L = 100	M	0	1	2	3
	Time (s)	0	111.6	116.5	122.9
E = 2, L = 100	M	0	1	2	3
	Time (s)	0	92.4	106.7	125.4
E = 3, L = 100	M	0	1	2	3
	Time (s)	0	90.3	95.1	98.2

AGV: automated guided vehicle; E: number of endpoints for the plane.

Conclusion

In this article, AGVs as delivery robots are employed to realize the quick and accurate sorting of baggage at the international airport. Multi-AGVs run in a stochastic time-dependent network. One new indoor location measure is proposed to formulate a new optimization problem that maximizes the performance of the multi-AGVs operation simultaneously. A randomized method based on the RRT algorithm and time-window rules to construct the trajectories is developed. Computer simulation shows the effectiveness of the proposed method.

Footnotes

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iD

Chen Li

References

Association TIAT. IATA releases 2018 airline safety performance, https://www.iata.org/en/pressroom/pr/2019-02-21-01 (accessed 12 March 2020).

Le-Anh

De Koster

. Multi-attribute dispatching rules for AGV systems with many vehicles, 2004; 1(1): 1–23.

Evers

JJM

Koppers

SAJ

. Automated guided vehicle traffic control at a container terminal. Transport Res A Pol Pract 1996; 30(1): 21–34.

Majdi

Deldar

Barzamini

, et al. AGV path planning in unknown environment using fuzzy inference systems. In: Proceedings of the 2006 1st IEEE international conference on e-learning in industrial electronics, 18–20 December 2006, Hammamet, Tunisia, pp. 64–67.

Huang

Hallam

. Spring-based negotiation for conflict resolution in AGV scheduling. In: Proceedings of the 1995 IEEE international conference on systems, man and cybernetics. Intelligent systems for the 21st century, 22–25 October 1995, Vancouver, BC, Canada, pp. 789–794.

Huang

Savkin

. Viable path planning for data collection robots in a sensing field with obstacles. Comput Commun 2017; 111: 84–96.

Ding

Bai

, et al. Development of a high precision UWB/vision-based AGV and control system. In: 2020 5th international conference on control and robotics engineering (ICCRE), 24–26 April 2020, Osaka, Japan, pp. 99–103.

Khoi Huynh

Anh Nguyen

. A research on automated guided vehicle indoor localization system via CSI. In: 2019 international conference on system science and engineering (ICSSE), 20–21 July 2019, Dong Hoi, Vietnam, pp. 581–585.

Sbîrnă

L-S

. Optimization of indoor localization of automated guided vehicles using ultra-wideband wireless positioning sensors. In: 2019 23rd international conference on system theory, control and computing (ICSTCC), 9–11 October 2019, Sinaia, Romania, pp. 504–509.

10.

Shen

, et al. INS/UWB integrated AGV localization employing Kalman filter for indoor LOS/NLOS mixed environment. In: 2019 international conference on advanced mechatronic systems (ICAMechS), 26–28 August 2019, Kusatsu, Shiga, Japan, pp. 294–298.

11.

Pudlovskiy

Chugunov

Kulikov

. Investigation of impact of UWB RTLS errors on AGV positioning accuracy. In: 2019 international russian automation conference (RusAutoCon), 8–14 September 2019, Sochi, Russia, pp. 1–5.

12.

Savkin

Huang

. Range-based reactive deployment of autonomous drones for optimal coverage in disaster areas. IEEE Trans Syst Man Cybern Syst 2019; 1(1): 1–5.

13.

Savkin

Huang

. A method for optimized deployment of a network of surveillance aerial drones. IEEE Syst J 2019; 13(4): 4474–4477.

14.

Savkin

Huang

. Deployment of unmanned aerial vehicle base stations for optimal quality of coverage. IEEE Wireless Commun Lett 2019; 8(1): 321–324.

15.

Huang

Savkin

Ding

, et al. Optimized deployment of autonomous drones to improve user experience in cellular networks. J of Net and Comp Appl 2019; 144: 49–58.

16.

Huang

Savkin

. An algorithm of efficient proactive placement of autonomous drones for maximum coverage in cellular networks. IEEE Wireless Commun Lett 2018; 7(6): 994–997.

17.

Huang

Savkin

. An algorithm of reactive collision free 3-D deployment of networked unmanned aerial vehicles for surveillance and monitoring. IEEE Trans Ind Inform 2020; 16(1): 132–140.

18.

Savkin

Huang

. Navigation of a network of aerial drones for monitoring a frontier of a moving environmental disaster area. IEEE Syst J 2020; 1(1): 1–4. DOI:10.1109/ JSYST.2020.2966779.

19.

Francis

SLX

Anavatti

Garratt

. Real time cooperative path planning for multi-autonomous vehicles. In: Proceedings of the 2013 international conference on advances in computing, communications and informatics (ICACCI), 22–25 August 2013, Mysore, India, pp. 1053–1057.

20.

Han

Wang

Feng

, et al. Multi-AGV path planning with double-path constraints by using an improved genetic algorithm. PLoS One 2017; 12(7): e0181747.

21.

Wang

Ersoy

, et al. Multi-offspring genetic algorithm and its application to the traveling salesman problem. Appl Soft Comput 2016; 43: 415–423.

22.

Jiang

Yang

. A discrete fruit fly optimization algorithm for the traveling salesman problem. PLoS One 2016; 11(11): 1–15.

23.

Huang

Savkin

Huang

. Reliable path planning for drone delivery using a stochastic time-dependent public transportation network. IEEE Trans Intell Transport Syst 2020; 1(1): 1–10.

24.

Gunathillake

Huang

Savkin

. Sensor-network- based navigation of a mobile robot for extremum seeking using a topology map. IEEE Trans Ind Inform 2019; 15(7): 3962–3972.

25.

Savkin

Huang

. Securing UAV communication in the presence of stationary or mobile eavesdroppers via online 3D trajectory planning. IEEE Wireless Commun Lett 2020; 1(1): 1–1.

26.

Savkin

Huang

. Optimal aircraft planar navigation in static threat environments. IEEE Trans Aerosp Electr Syst 2017; 53(5): 2413–2426.

27.

Behring

Bracho

Castro

, et al. An algorithm for robot path planning with cellular automata. In: Bandini

Worsch

(eds) Theory and practical issues on cellular automata, London: Springer, pp. 11–19.

28.

Chen

, et al. Path planning and prototype design of an AGV. Math Comput Modell Int J 1999; 30(7–8): 147–167.