Route Optimization for Autonomous Container Truck Based on Rolling Window

Abstract

Route optimization for autonomous container truck is one of the key problems to realize the automatic container port. An environment model for container truck is built by grid method. Considering the complex and unknown construction environment of the container port, an improved ant colony optimization (IACO) algorithm based on rolling window is proposed to achieve path planning for container truck. In the simulations, it is obvious that the IACO will not only achieve a safe collision avoidance path, the length of which is shorter than the truck's traditional route no matter how complex the environment is, but also show good analytical and disposing ability of dead ends in the path planning process. Compared with conventional ant colony optimization (ACO), the running time of IACO is shorter. The results of the simulation experiments demonstrate that the IACO is a good method which is applicable to route optimization for autonomous container truck.

Keywords

Container Truck Route Optimization Path Planning Ant Colony Optimization (ACO)Rolling Window

1. Introduction

Container transportation is the most important logistics process of the container terminal. The container terminal is mainly composed of berth, container crane, container truck, gantry crane, and container yard. The container truck plays an important role in the whole process of container horizontal transportation. It is the connection between the container crane and the gantry crane. It is also a large-scale port equipment for container loading, unloading, and transportation. According to the Statistical Bulletin of Development of Transport Industry in 2014, China's port container throughput has reached 202 million TEU (twenty-foot equivalent unit) with an increase of 6.4% over the previous year, which has ranked first in the world for several years. With the improvement of container ship loading capacity and the requirement of ship's port time minimization, it is important to improve the efficiency of the container port loading and unloading.

There are many factors that may influence the efficiency of the container port loading and unloading, such as the allocation of the resources of the equipment, the plan of yard, the assignment and allotment of berth, quayside container cranes, and container truck as well as the route of port equipment movement. Route optimization for container truck is a key joint to realize the high-efficiency automatic container port.

Route optimization is an important branch of intelligent robot in the field of navigation. Path planning of intelligent robot has been studied in many papers in recent years. For such a kind of problem, various approaches have been employed to solve it. Dijkstra algorithm is employed in ref. [1] for the maze robot path planning. Although the Dijkstra algorithm can calculate the optimal path, it needs to iterate through all the nodes and its searching efficiency is much lower. Hierarchical A-Star algorithm is used in ref. [2] to solve the problem of optimal parking path planning of the large parking lot. A-Star algorithm is a heuristic search algorithm and its evaluation function determines the searching direction and affects the searching efficiency, but its computation time will be so much long when the workspace is large or the construction environment is complex. The generalized Voronoi diagram is used in ref. [3] for planning a collision-free path for a rectangle in a planar workspace populated with polygonal obstacles. The path planning method based on Voronoi diagram ensures the safe and reliable path, but it greatly increases the path length. When the number of obstacles in the construction environment becomes large, the algorithm will be very complex. Because path planning is NP-completed problem in nature [4], that is, the computational time that is required to solve such a problem increases dramatically (usually in an exponential rate) when the size (or dimension) of the problem increases, all the above algorithms will cause huge computational cost, especially in a complex environment or in a large searching space. Therefore, these algorithms cannot meet certain mission constraints. Furthermore, all the above methods are only applicable to the known environment. However, the obstacles of construction environment for container truck are complex and unknown. Therefore, all the above methods will not apply to the path planning for container truck in container yard.

To solve the problem of path planning, some modern intelligent path planning algorithms, such as genetic algorithm (GA) [5–7], simulated annealing (SA) [8, 9], neural network (NN) [10–12], particle swarm optimization (PSO) [13, 14], and ant colony optimization (ACO) [15–18], are adopted. Among those approaches, the ACO is the only meta-heuristic approach inspired by the behaviour of the biological ants in real world. It is one of the most successful examples of swarm intelligent systems and has been applied to solve many different types of problems, such as optimizing nonlinear objective functions and network routing in telecommunication networks [19]. A new ACO algorithm with fuzzy self-adapting of parameters is proposed in ref. [17], and it introduces the concept of activity degree of city to obtain effective updating of pheromone. But the algorithm can only apply to path planning in 3-D static obstacle environment. All the obstacles’ places are known beforehand. However, the obstacles in container terminal are unknown beforehand, and the container truck is used for horizontal transportation. So the proposed algorithm in ref. [17] is not suitable for the path planning of the container truck. As conventional ACO algorithm has shortcomings such as low efficiency in the initial stage for the lack of pheromone, it needs to be modified so that its convergence rate is speeded up when the optimal route is obtained.

The main purpose of this paper is to break through the shackles of the fixed route for container truck in the traditional operation process and to achieve the route optimization for autonomous container truck in unknown environment by the improved ant colony optimization (IACO) algorithm based on rolling window. The main contributions of this paper are as follows: (1) The workspace environment model of container truck is built by grid method. (2) The IACO algorithm based on rolling window is proposed and it is used to plan the path of the container truck. (3) The path planning of the container truck in the whole process of transportation is simulated successfully which meets the needs of quickness.

The structure of this paper is as follows: the background of container truck is described in Section 1 and the grid environment model is given in Section 2. Section 3 presents the process of path planning for container truck by IACO based on rolling window. Simulation experiments and results of the path planning for container truck are shown in Section 4. Finally, conclusions are drawn in Section 5.

2. Problem Formulation

Path planning consists of two subproblems: environment modelling and path search strategy. Environment modelling is the first step to solve the problem of path planning. Container trucks are used in a harbour environment to move containers between the pier and the container yard. The work environment of container terminal, as shown in Figure 1, is mainly made up of wharf, frontier, and container yard. The wharf generally refers to the quay line and mooring fittings which are prepared for docking the ship. The frontier is equipped with the quayside container crane and its orbit. The container yard is the stocking area of containers which are prepared for loading and unloading. From Figure 1, the traditional operation procedure of container-handling system is easy to be understood. In the loading process, the gantry crane transfers containers from the container yard to the container truck, then the full load truck transports containers to the frontier along the fixed route, and finally the container crane transfers containers from the truck to the ship. In the unloading process, the container crane transfers containers from the container ship to the no load truck, then the truck walks to the gantry crane's place along the fixed route, and lastly, the gantry crane transfers containers from the truck to the container yard. However, as the route of the container truck is relatively fixed, every truck usually walks for a long time along the fixed route and the truck's utilization rate is extremely low. Furthermore, it may lead to traffic jams when the number of trucks increases and the truck will slow down. It will extend the waiting time of the container crane or the gantry crane and affect the wharf working efficiency which may result in overstocking a harbour and affect the port container throughput.

Figure 1.

Workflow of container port

Because of the irrationality of the truck's traditional route, a new and shorter path needs to be planned for the container truck. Due to the dynamic properties of the container terminal environment, unexpected changes in site layout may create new obstacles for the truck that may result in collisions and accidents. In this research, the improved ant colony optimization (IACO) algorithm is proposed to realize safe and short path planning of the container truck, which considers unknown environment or unpredictable obstacles.

For the horizontal transportation process of the container truck, a corresponding environment model needs to be established. The environment model could be depicted as shown in Figure 2. The truck's movement direction that's perpendicular to the coastline is set as the Y axis, while the movement direction that is parallel to the coastline is set as the X axis. If the working area of the truck is known, the maximum longitudinal displacement can be denoted by $Y_{\max}$ and the maximum lateral displacement can be denoted by $X_{\max}$ .

Figure 2.

Environment model based on grid method

There are many methods of environment modelling, including visibility graph method, free-space method, and grid method. In this research, the grid method is used for environment modelling. It is important to select an appropriate grid cell size. The smaller the grid size, the higher the resolution of the environmental model. But if the resolution is too high, it will take up a lot of storage space and even may cause the overflow of data. In fact, the grid size is measured by the size of the container truck. Assume that the grid size is measured by $δ_{x}$ and $δ_{y}$ . If $X_{\max}$ (or $Y_{\max}$ ) is not an integral multiple of the corresponding size of the container truck, the values of $δ_{x}$ and $δ_{y}$ should be adjusted appropriately to meet the requirements.

The whole environment model is composed of two kinds of grid. Blank background grid is named free grid and grey grid is named obstacle grid. Free grid represents the area that can walk free, while obstacle grid represents the working space occupied by obstacles which cannot be reached by the truck. The main purpose of this research is to seek a safe and short path that can bypass obstacle grids and avoid collision.

There are two methods for recording the grid when creating an environmental map. One is the method of rectangular coordinate, the other method is the serial number notation. For the method of direct coordinate, each grid can be denoted by absolute coordinate (x, y) in the environment domain. For the serial number notation, each grid that records the environment information will be sorted globally and the global serial number is the label of corresponding grid. The serial number starts at 1 and increases by 1 from left to right, top to bottom. The mathematical relationship between the arbitrary grid and the corresponding grid coordinate is as follows:

g = (\frac{x}{δ_{x}} + 0.5) + n \times [m - (\frac{y}{δ_{y}} + 0.5)]

(1)

x = {\begin{matrix} [\mod (g, n) - 0.5] \times δ_{x} & when \mod (g, n) \neq 0 \\ (n - 0.5) \times δ_{x} & when \mod (g, n) = 0 \end{matrix}

(2)

y = [m - c e i l (\frac{g}{n}) + 0.5] \times δ_{y}

(3)

In Eq. (1)–(3), g is the serial number of grid, n is the number of grid each row and $n = \frac{X_{\max}}{δ_{x}}$ , m is the number of grid each column and $m = \frac{Y_{\max}}{δ_{y}}$ , x is the abscissa and y is the ordinate, and mod returns the modulus after division and ceil means rounding towards positive infinity.

Some approximate treatment methods will be adopted when creating the environmental map. If one grid in the map is not filled up with the barrier in practice, it can be regarded as an obstacle grid. If l is the distance between two obstacles and $l < \frac{\min (δ_{x}, δ_{y})}{2}$ , the two obstacles can be regarded as one complete obstacle. The container truck will be seen as a particle in the path planning process. This method helps to realize the path simulation. Due to the influence of the actual size of the truck, the size of obstacle needs to be expanded appropriately so that the truck will bypass the obstacles and avoid collision when walking along the path that the system generated. In the environment model, the size of expanded obstacle grid is named the safe distance that is denoted by L in practice. The mathematical relationship based on the safe distance L is as follows:

L \geq \frac{ω_{\max}}{2} + \frac{v^{2}}{2 a}

(4)

where $ω_{\max}$ is the maximum side length of the container truck, v is the resultant velocity of the truck, and a is the resultant acceleration of the truck.

The number of the grid occupied by expanded obstacles is as follows:

λ = floor (\frac{L}{δ}) + 1

where floor means rounding towards negative infinity.

In practice, it may lead to collision of the container truck with the edge of the environment map when the truck goes through the edge grid and the grid size is smaller than the truck. Therefore, the edge grid needs to be expanded in a similar way.

The set of all grids’ serial numbers G in the $m \times n$ environment map is as follows:

G = [1, 2, \dots, g], g = m \times n

In the environment model, the set of obstacle grids obstacle and the set of free grids free are as follows:

obstacle = [o b_{1}, o b_{2}, \dots, o b_{k}], obstacle \subseteq G

free = [f_{1}, f_{2}, \dots, f_{z}], free \subseteq G

The obstacle information in the unknown environment is collected by the ultrasonic sensor installed on the container truck. During the transportation process, the sensors will run together with the truck. Suppose that the effective detection range of ultrasonic sensor is the rolling window view, the radius of which is R. With every step of the truck, the information of rolling window view will be updated in real time. Therefore, the sensors can detect the change of environmental information at any time, and the change has no influence on obstacle avoidance path planning. From Figure 2, the rolling window view is the dashed circle including the detected effective information of nine grids (g=13, 14, 15, 21, 22, 23, 29, 30, 31).

3. Solutions

3.1. Conventional ant colony optimization (ACO) algorithm

ACO algorithm, which is proposed by Marco Dorigo in his doctoral dissertation in 1992, is an intelligence-optimized algorithm derived from the illumination of food-seeking behaviour by ants based on the shortest route of pheromone [20]. It is a probability-based algorithm which is used to find the optimal path in the map [21]. ACO algorithm is a simulated evolutionary algorithm which shows many good properties.

The principle of ACO can be described as follows: All the ants start looking for food on the premise that they do not know where the food is beforehand. When one ant finds the food, it releases a volatile secretion called pheromone into the environment which can attract other ants to come over. Then, more and more ants will also find the food. As time goes on, the pheromone will gradually evaporate. Some ants do not repeat the same path as other ants, and they will find other new paths. If the new path is shorter than the original path, more ants are attracted to the shorter path gradually. Finally, there may be a shortest path which is repeated by most of the ants after a period of time.

The mathematical modelling of ACO algorithm is as follows: Assume that $A_{n u m i} (t)$ is the number of ants on grid i at time t, $τ_{i j} (t)$ is the pheromone intensity between the grid i and grid j, and the pheromone intensity between each grid is equal in the beginning. If N is the number of grid, the total number of ants is $M = \sum_{i = 1}^{N} A_{n u m i} (t)$ ; the taboo table $t a b u_{k}$ is used to store the grid which the kth ant has passed through. Suppose $P_{i j}^{k} (t)$ is the probability that the kth ant transferred from grid i to grid j at time t. In the process of path search, $P_{i j}^{k} (t)$ is decided by the amount of pheromone and the heuristic information of path. It is defined as follows:

P_{i j}^{k} (t) = {\begin{matrix} \frac{{[τ_{i j} (t)]}^{α} {[η_{i j} (t)]}^{β}}{\sum_{l \in a l l o w e d_{k} (t)} {[τ_{i l} (t)]}^{α} {[η_{i l} (t)]}^{β}} & if j \in a l l o w e d_{k} (t) \\ 0 & else \end{matrix}

(5)

In Eq. (5), $η_{i j} (t)$ is a heuristic function which denotes the expectation degree of ant transferring from grid i to grid j. $a l l o w e d_{k} (t)$ denotes a set of grids that the kth ant can select in the next step at time t. α is a pheromone stimulating factor which reflects the effects of the accumulation of pheromone in the process of ant's movement. The greater the value of α, the more important the pheromone intensity $τ_{i j} (t)$ . And the interoperability among ants is also better. β is an expected heuristic factor, which denotes the importance of heuristic function. The greater the value of β, the more important the expected heuristic function $η_{i j} (t)$ . It means that the degree of influence among ants is lower and $P_{i j}^{k} (t)$ is more close to the greedy algorithm. When an ant completes the traversal of the whole grid net, part of the pheromone will be cleared so that the optimal solution can be obtained. Otherwise, heuristic information will be overwhelmed by more and more residual pheromone. After an iteration searching, every ant can construct a classification rule, and the best rule is reserved while the worse rule is gradually eliminated by adjusting the concentration of pheromone.

3.2. Path planning based on rolling window by IACO

Assume that the initial point of path is Start and the destination is Object in the environment model. The meaning of path planning in this research is to design an optimal route for the container truck while going from Start to Object. With every step of the truck, the rolling window view will be updated in real time. Assume that the truck is simplified down to point O and the ultrasonic sensor detection range is R. Then the window view is a virtual local area with centre at O and radius equal to R. It is the first step to find a local target subT in the range of the area view, and then the global target Object will be reached after t times for local path planning. The global path can be denoted as $p a t h = \sum_{t = 1}^{t} p a t h (t)$ .

3.2.1. The selection of local target in the rolling window

As the global target Object is not necessarily in the range of the rolling window view, it is necessary to seek a virtual target subT in the view which maybe has certain relationship with Object so that the local target subT can become the route guidance of view.

The grid set in the range of view is as follows:

v i e w = [v_{1}, v_{2}, \dots, v_{s}, \dots, v_{n_{v i e w}}], v_{s} \in G

where $s \in [1, 2, \dots, n_{v i e w}]$ and $n_{v i e w}$ is the total number of all grids in the view.

The coordinate values of all grids in the view are denoted as follows, which can be calculated by Eqs. (2) and (3):

X_{v i e w} = [x_{1}, x_{2}, \dots, x_{s}, \dots, x_{n_{v i e w}}], x_{s} \in X and X_{v i e w} \subseteq X

Y_{v i e w} = [y_{1}, y_{2}, \dots, y_{s}, \dots, y_{n_{v i e w}}], y_{s} \in Y and Y_{v i e w} \subseteq Y

where $0 \leq X \leq X_{\max}$ and $0 \leq Y \leq Y_{\max}$ .

Assume that the coordinate of the global target Object is $(x_{o b j e c t}, y_{o b j e c t})$ . The distance between the arbitrary grid in the view and the global target Object can be denoted as follows:

d (O b j e c t, v_{s}) = \sqrt{{(x_{o b j e c t} - x_{s})}^{2} + {(y_{o b j e c t} - y_{s})}^{2}}

(6)

It is obvious that there are eight adjacent grids for the grid g, which is shown in Figure 3. The distance between the grid g and its adjacent grid $g_{a d j}$ is shown as follows:

d (g, g_{a d j}) = {\begin{matrix} δ_{x} \\ δ_{y} \\ \sqrt{δ_{x}^{2} + δ_{y}^{2}} \end{matrix} \begin{matrix} g_{a d j} \in {g - 1, g + 1} \\ g_{a d j} \in {g - n, g + n} \\ else \end{matrix}

(7)

Figure 3.

Diagram of choosing path direction

From Figure 3, as the adjacent grid $g - n + 1$ is the obstacle grid, there are only seven path directions which can be chosen. Therefore, the set of next grids that can be reached is as follows:

s u b g r i d (g) = [g - n - 1, g - n, g - 1, g + 1, g + n - 1, g + n, g + n + 1]

Then the objective function is as follows:

{\begin{matrix} s u b T = v_{s f} \cap {\min d (O b j e c t, v_{s})} \\ s u b g r i d (s u b T) \neq [] \end{matrix}

(8)

where $v_{s f} = (f r e e \cap v i e w)$ .

When more than one subT is obtained from Eq. (8), one of them will be selected randomly.

3.2.2. Ant's state transformation rule

In the rolling window view, each ant takes the current grid g as a centre and then selects a grid for the next step from its selectable grid group $a l l o w e d_{k} (t)$ based on a given criterion. The criterion is called random proportional rule. At time t, the kth ant transfer probability from grid i to grid j can be expressed by Eq. (5). As the taboo table $t a b u_{k}$ is the set of grids that ants walk through before, $a l l o w e d_{k} (t)$ is the absolute complement of $t a b u_{k}$ in the set of $s u b g r i d (g)$ . The selectable grid group can be denoted as follows:

a l l o w e d_{k} = C_{s u b g r i d (g)} t a b u_{k}

(9)

From the objective attraction function (5), it can be seen that the ant transfer probability is a trade-off between the heuristic and pheromone factor. Roulette wheel is used for the selection of the ant's next step. According to equation (5), each individual transfer probability $p_{a}$ is obtained and $a = 1, 2, \dots, Z$ . Z is the size of population. Then a random real number q uniformly scattered in the range $[0, 1)$ is generated. The individual where r satisfies the following equation is selected as the next step $s u b g r i d [r]$ :

r = \min {b | \sum_{a = 1}^{b} p_{a} \geq q, b = 1, 2, \dots, Z}

The initial pheromone intensity for every arc in the environment map is constant $τ_{0}$ . The pheromone is adjusted constantly according to the given pheromone update rule every time after an iteration cycle is completed. The heuristic function $η_{i j} (t)$ denotes the visibility between grid i and grid j, which is defined as $η_{i j} (t) = 1 / d (i, j)$ . α and β are weight values between pheromone intensity and visibility.

With every step in the rolling window view, the grid that ant reaches will be stored in taboo table $t a b u_{k}$ . The path and path length will be also updated and recorded simultaneously.

3.2.3. Pheromone update rule

After an ant has finished all grids’ traversal, if the pheromone on a path that it passed by is simply increased, the excessive amount of pheromone will inundate the heuristic information. So it requires updating the intensity of the pheromone on a path according to a certain rule. As the work environment of the container truck is very complex and conventional ACO algorithm has shortcomings such as low efficiency in the initial stage for the lack of pheromone, the convergence speed of algorithm is relatively slow. In this paper, the conventional pheromone update rule is modified. The information positive feedback performance is enhanced and the convergence speed is improved.

With time, the amount of pheromone on a path evaporates step by step. The evaporation factor ρ ( $0 < ρ < 1$ ) denotes pheromone evaporation rate. It prevents the solution from trapping into a local optimal solution and guarantees the chance to search for new solution. The pheromone update rule is described as follows:

τ_{i j} (t + t_{0}) = (1 - ρ) τ_{i j} (t) + Δ τ_{i j} + Δ τ_{i j}^{*}

(10)

Δ τ_{i j} = \sum_{k = 1}^{m} Δ τ_{i j}^{k}

(11)

where $t_{0}$ denotes the time that all ants finish an iteration cycle, m is the number of ants in an iteration cycle, $Δ τ_{i j}$ denotes the pheromone increment on the path from grid i to grid j in the current iteration cycle, $Δ τ_{i j}^{k}$ denotes the pheromone increment of kth ant from grid i to grid j, and $Δ τ_{i j}^{*}$ denotes the pheromone increment of all elitist ants on the path from grid i to grid j in the current iteration cycle. All the pheromone values of the map are stored in a table called “pheromone table”. After the pheromone intensity is updated every iteration cycle, the latest pheromone values will be recorded in the pheromone table to provide reference for the ants in the next iteration cycle.

The expression of $Δ τ_{i j}^{k}$ has different specific method. There are three models given by Dorigo: ant-cycle system, ant-quantity system, and ant-density system. Numerous studies show that the ant-cycle model is superior to the other two models. In ant-cycle model, the pheromone laid down by the kth ant is calculated as follows:

Δ τ_{i j}^{k} = {\begin{matrix} \frac{Q}{L_{k}} & if path (i, j) belongs to the current path of the k th ant \\ 0 & else \end{matrix}

(12)

where $L_{k}$ is the length of path that the kth ant has visited in the current iteration and Q is pheromone accumulation parameter that is positive constant.

To avoid the local optimization and the slow search speed, the conventional pheromone update rule is modified by introducing the concept of “elitist ant”. Elitist ant refers to the ant path length which is the shortest in the current iteration cycle. In other words, elitist ant is the global optimal solution in the current iteration. Therefore, the intensity of pheromone laid down by elitist ant should be increased so that the convergence speed is improved. $Δ τ_{i j}^{*}$ is the additional pheromone increment of all elitist ants and is defined as follows:

Δ τ_{i j}^{*} = {\begin{matrix} σ \cdot \frac{Q}{L^{*}} & if path (i, j) belongs to current optimal path \\ 0 & else \end{matrix}

(13)

where $L^{*}$ is the length of the current optimal path in the current iteration and σ is the number of elitist ant in the current iteration cycle.

Put all ants on the start grid and start the next iteration after updating the pheromone table and recording the result of this iteration. The exploration is repeated until stop criteria are met. The stop criteria could be a preset maximum iteration times $N C_{\max}$ or a condition concerning the performance of the solution.

3.2.4. Principle of setting parameters

The initial value of pheromone $τ_{0}$ : It denotes the initial energy of the system. If the setting value is too small, it will lead that the pheromone intension on some arcs may become much smaller according to system evolvement, and the system searching is influenced. This effect will be enhanced according to the enlargement of the scale of problem.

The number of ants M: It needs to be considered from two aspects which are global searching ability and convergence rate. Its selection strategy is a trade-off between global searching ability and convergence rate. According to experience, the number of ants is similar to the scale of the environment.

Pheromone factor α: It represents the relative importance degree of the accumulated pheromone in guiding the search for ant colony. The bigger its values, the more inclined the ant colony will be to the path that is passed by other ants. It will lead that the search randomness is weakened. However, if its value is too large, the search for the ant colony will be immersed in local optimization. On the contrary, if its value is too small, the search will get a premature determinacy.

Heuristic factor β: It represents the relative importance degree of visibility for the ants in path search. The bigger its values, the higher possibility an ant will choose a local optimal path at a local point. It may lead that the search is speeded up, but the search randomness will be decreased. As a result, the transfer possibility of a grid is closer to greedy rule, which is easy to fall into local optimization.

Evaporation rate ρ: It represents the reducing degree of the pheromone on each arc, which is directly related to the global search ability and convergence speed of the algorithm. When ρ is high, the positive feedback of pheromone plays a dominant role. It leads that the search randomness becomes weak and the algorithm converges quickly, but it is easy to fall into local optimization. When ρ is low, the pheromone remained on an arc playing a dominant role. It leads that the search randomness and global searching ability become strong. However, the convergence speed becomes slow.

Pheromone accumulation parameter Q: It represents the quantity of pheromone released by an ant after a search is being finished, which is usually positive constant. When its value is large, the accumulation of pheromone is speeded up. It will lead that the positive feedback effect of the pheromone plays a dominant role and the algorithm converges quickly. When its value is small, the search randomness and the global searching ability become strong.

The above coefficients have high coupling in the ant colony algorithm; thus in practical application, it requires following the above principles to determine the optimal coefficient combination.

3.3. Whole procedure of path planning for the container truck

The above part has shown the IACO algorithm for path planning based on the rolling window. The flowchart of path planning for container truck is given in Figure 4. The whole procedure of path planning by IACO algorithm is shown as follows:

Step 1: Environmental modelling by grid method.

Step 2: Initialize the relevant parameters, such as m, α, and β.

Step 3: Put all the ants on the Start, and initialize the taboo table $t a b u_{k}$ for each ant.

Step 4: Generate rolling window view and select local target subT in the view according to (8).

Step 5: Each ant chooses the next grid in the view according to function (5) and its $t a b u_{k}$ .

Step 6: If an ant brings about an invalid path, it will be deleted; otherwise repeat Step 5 until each ant reaches subT.

Step 7: If the subT is the terminal Object, the valid path is saved, then update the pheromone on each path according to (10).

Step 8: Repeat Steps 3, 4, 5, 6, and 7 until this algorithm reaches the supposed iterative times or exceeds the maximum execution time.

Step 9: Output the optimal solution at present.

Figure 4.

Flowchart of path planning for the container truck by IACO

4. Simulation Experiments and Results

Based on the above analysis, simulations of the proposed algorithm for the path planning of container truck are performed in MATLAB. The workspace is modelled in a grid map with 32×32 grids. Initial parameters used in simulations are given in Table 1. Assume that $S t a r t = 66$ and $O b j e c t = 990$ at the beginning of simulation. In the traditional operation process of container terminal, the route of container truck from Start to Object is fixed, which is shown in Figure 5. Its length is 58 cm. Obviously, the traditional route is too long and the efficiency is low. The goal of this paper is to break through the traditional idea and seek a shorter path. As all the obstacle information is unpredictable in work environment, it can be only collected by the ultrasonic sensor installed on the container truck. Assume that the effective detection range of the sensor in the environmental grid map is the square area with 9×9 grids. The simulation results are presented in Figures 6–10. The IACO algorithm is compared with ACO algorithm in the following simulations.

Table 1.

Parameters used in simulations

Parameters	Value
Ant amount (m)	30
Iterations (NC_max)	50
Coefficient (α)	1
Coefficient (β)	3
Evaporating rate (ρ)	0.4
Coefficient (Q)	15

Figure 5.

Traditional route of container truck

Figure 6.

Optimal path by IACO algorithm

Figure 7.

Convergence curves of optimal paths by IACO algorithm

Figure 8.

Convergence curves of optimal paths by ACO algorithm

Figure 9.

Optimal path by IACO algorithm (dead end)

Figure 10.

Convergence curves by IACO algorithm (dead end)

The optimal route which is planned by IACO algorithm is shown in Figure 6, the length of which is 45.108 cm. The comparison of the optimal route with the traditional route in Figures 6 and 5 shows that the length of the former is 12.892 cm shorter than the latter. Thus, the efficiency of the container truck walking along the planned path is higher. In Figures 7 and 8, they are respectively the convergence curves of optimal paths by IACO algorithm and ACO algorithm. The horizontal axis is the iteration times NC, and the vertical axis shows the path length. The solid line represents the convergence curves of the shortest path length and the dashed line represents the convergence curves of the average path length in every iteration. It can be seen that the iteration times by IACO algorithm is approximately 20 when the system converges to a stable state, while the iteration times by ACO algorithm is approximately 40. It is obvious that the proposed IACO algorithm can find optimal paths at a higher convergence speed. The computation time is about 3.15 seconds (all the algorithms in this brief are processed in MATLAB in the same computer: dual core, 1.6GHz CPU frequency, and 1GB RAM). As actual container logistics system has a high demand of path planning solution's rapidity, the IACO algorithm will meet its demands significantly.

Sometimes, the container truck walks into a dead end because the work environment is very complex. The IACO algorithm has the ability to deal with the dead end which is shown in Figure 9. Its convergence curves are shown in Figure 10. When the truck falls into a corner, it will automatically and rapidly jump out of the corner in order to ensure the safe operation of the system. It shows good analytical and disposing ability of dead ends in the path planning process.

5. Conclusions

In this paper, an algorithm for route optimization in the unknown workspace, named IACO algorithm, has been proposed for autonomous container truck. Due to the complex construction environment of container port, the grid method is used for environment modelling. The information of the unknown environment is collected by ultrasonic sensor which is installed on the container truck. The rolling window which is the effective detection range of the sensor is introduced to realize path planning. To avoid low search efficiency and slow convergence speed, the conventional ACO algorithm is modified by introducing “elitist ant” to solve the problem, which is the proposed IACO algorithm based on rolling window. The simulation experiment results show that this approach is valid. The IACO algorithm can find optimal paths at a higher convergence speed compared with ACO algorithm. Furthermore, it shows good analytical and disposing ability of dead ends in the path planning process in the simulation.

Footnotes

6. Acknowledgements

This work was supported by the National Natural Science Foundation of China under Grant No. 61272114 and Marine Renewable Energy Special Fund Project of the State Oceanic Administration of China under Grant No. GHME2013JS01.

References

Wang

Yuan

Application of Dijkstra algorithm in robot path-planning In: Proceedings of the 2011 Second International Conference on Mechanic Automation and Control Engineering (MACE); 15–17 July 2011; Hohhot. New York: IEEE; 2011. pp. 1067–1069.

Cheng

Liu

Yan

Improved hierarchical Astar algorithm for optimal parking path planning of the large parking lot In: Proceedings of the 2014 IEEE International Conference on Information and Automation (ICIA) 28–30 July 2014; Hailar. New York: IEEE; 2014. pp. 695–698. DOI: 10.1109/ICInfA. 2014.6932742.

Takahashi

Schilling

R.J.

Motion planning in a plane using generalized Voronoi diagrams. IEEE Transactions on Robotics and Automation. 1989; 5(2):143–150. DOI: 10.1109/70.88035.

Goss

Aron

Deneubourg

J.L.

Self-organized shortcuts in the Argentine Ant. Naturwissenschaften. 1989; 76(12):579–581. DOI: 10.1007/BF00462870.

Shi

Cui

Dynamic path planning for mobile robot based on genetic algorithm in unknown environment In: Proceedings of the 22nd Chinese Control and Decision Conference (CCDC); 26–28 May 2010; Xuzhou. New York: IEEE; 2010. pp. 4325–4329. DOI: 10.1109/CCDC.2010.5498349.

Cui

Dong

Detecting robots path planning based on improved genetic algorithm In: Proceedings of the 3rd International Conference on Instrumentation & Measurement, Computer, Communication and Control (IMCCC); 21–23 September 2013; Shenyang. New York: IEEE; 2013. pp. 204–207. DOI: 10.1109/IMCCC.2013.50.

Loo

C.K.

Rajeswari

Wong

E.K.

Rao

M.V.C.

Mobile robot path planning using hybrid genetic algorithm and traversability vectors method. Intelligent Automation and Soft Computing. 2004; 10(1):51–63.

Miao

Tian

Dynamic robot path planning using an enhanced simulated annealing approach. Applied Mathematics and Computation. 2013; 222:420–437.

Miao

Tian

Robot path planning in dynamic environments using a simulated annealing based approach In: Proceedings of the 10th International Conference on Control, Automation, Robotics and Vision; 17–20 December 2008; Hanoi. New York: IEEE; 2008. pp. 1253–1258. DOI: 10.1109/ICARCV. 2008.4795701.

10.

Zhu

Huang

Yang

Dynamic task assignment and path planning of multi-AUV system based on an improved self-organizing map and velocity synthesis method in three-dimensional underwater workspace. IEEE Transactions on Cybernetics. 2013; 43(2):504–514. DOI: 10.1109/TSMCB.2012.2210212.

11.

Yang

S.X.

Bioinspired neural network for real-time cooperative hunting by multirobots in *unknown environments. IEEE Transactions on Neural Networks. 2011; 22(12):2062–2077. DOI: 10.1109/TNN.2011.2169808.

12.

Yang

S.X.

Luo

C.M.

A neural network approach to complete coverage path planning. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics. 2004; 34(1):718–725. DOI: 10.1109/TSMCB.2003.811769.

13.

Zhang

Gong

Zhang

Robot path planning in uncertain environment using multi-objective particle swarm optimization. Neurocomputing. 2013; 103:172–185. DOI: 10.1016/j.neucom.2012.09.019.

14.

Hao

Zhao

Real-time obstacle avoidance method based on polar coordination particle swarm optimization in dynamic environment In: Proceedings of the 2nd IEEE Conference on *Industrial Electronics and Applications (ICIEA 2007); 23–25 May 2007; Harbin. New York: IEEE; 2007. pp. 1612–1617. DOI: 10.1109/ICIEA.2007.4318681.

15.

Zhang

Peng

Jiang

A rescue robot path planning based on ant colony optimization algorithm In: Proceedings of the International Conference on Information Technology and Computer Science; 25–26 July 2009; Kiev. New York: IEEE; 2009. pp. 180–183. DOI: 10.1109/ITCS.2009.177.

16.

Brand

Masuda

Wehner

X.H.

Ant colony optimization algorithm for robot path planning In: Proceedings of the 2010 International Conference on Computer Design and Applications (ICCDA); 25–27 June 2010; Qinhuangdao. New York: IEEE; 2010. pp. V3–436–V3–440. DOI: 10.1109/ICCDA.2010.5541300.

17.

Zhao

Liu

Research of path planning for mobile robot based on improved ant colony optimization algorithm In: Proceedings of the 2nd IEEE International Conference on Advanced Computer Control; 27–29 March 2010; Shenyang. New York: IEEE; 2010. pp. 241–245. DOI: 10.1109/ICACC.2010.5486629.

18.

Han

Wang

Zhu

Path planning of mobile robot based on improved ant colony algorithm In: Proceedings of the 2011 International Conference on Consumer Electronics, Communications and Networks (CECNet); 16–18 April 2011; XianNing. New York: IEEE; 2011. pp. 531–533. DOI: 10.1109/CECNET.2011.5768791.

19.

Cui

Wang

Chen

Improved ant colony optimization algorithm for UAV path planning In: Proceedings of the 5th IEEE International Conference on Software Engineering and Service Science (ICSESS); 27–29 June 2014; Beijing. New York: IEEE; 2014. pp. 291–295. DOI: 10.1109/ICSESS.2014.6933566.

20.

Dorigo

Optimization, learning and natural algorithms [dissertation]. Italy: Politecnico di Milano; 1992.

21.

Dorigo

Gambardella

L.M.

Ant colony system: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation. 1997; 1(1):53–66. DOI: 10.1109/4235.585892.