大型自动化立体车库路径优化蚁群算法(英文文献)

COMPUTATIONAL METHODS IN ENGINEERING AND SCIENCE

EPMESC X, Aug. 21-23, 2006, Sanya, Hainan,China

©2006 Tsinghua University Press & Springer

Path Optimization of Large-Scale Automated Three-Dimensional Garage Based on Ant Colony Algorithm

Jianjun Meng1*, Zeqing Yang1, Zhenrui Peng2

1 Institute of Mech-Electronic Technology, Lanzhou Jiaotong University, Lanzhou, 730070 China 2 National Laboratory of Industrial Control Technology, Zhejiang University, Hangzhou, 310027 China

Email: mengjj@http://wendang.chazidian.com, yzq82@http://wendang.chazidian.com

Abstract To settle the contradiction among convergence speed and precocity and stagnation in ant colony algorithm, a new-type intellectual ant colony algorithm was developed, and then applied to the path optimization of the large-scale automated three-dimensional garage. The improved algorithm can shorten the time of taking and parking vehicles in the garage and raise the tasking efficiency. The experiment results show that the improved algorithm has higher convergence speed and stability, and it can get ideal searching result.

Key words: Ant Colony Algorithm, Three-Dimensional Garage, task, path, optimization

INTRODUCTION

Automated three-dimensional garage, which is based on modern logistics technique and automation technique, has played an important role in solving the parking problem in the cities. However, there exist some requirements for garages, including safety and quickness of taking and parking vehicles, and maintenance of continuity in garages task. So it would be desirable to optimize the path of taking and parking vehicles to improve the efficiency of garage task. And the optimization is also important for theory research and engineering application.

Many approaches have been proposed to solve the complex combined optimisation problems based on creature evolution since the middle of 1950’s, including gene algorithm, genetic algorithm and ant colony algorithm. Ant colony algorithm (ACA), one of random optimization algorithms, has been rapidly developed and applied to many combination problems to obtain better feasible solution.

In this work, a new-type intelligent ant colony algorithm (NIACA) is developed based on the comparison of basic ACA and max-min ant colony algorithm (MMACA), and its application in path optimization of the large-scale automated three-dimensional garage demonstrates the effectiveness of the NIACA.

ANT COLONY ALGORITHM

1.The principle of ant colony algorithm ACA belongs to one of simulated evolutional algorithms by imitating the behaviour of real ant colony [1-2]. Real ants can find the shortest path from nest to food source by a kind of pheromone, Because of the similarity between searching manner of ants and TSP (Travelling Salesman Problem) [3], M. Dorigo presented the ACA to solve the combination optimization problem by simulating the indirect communication behaviour of real ants.

When ants move, they will deposit pheromone on the passed path, and the others can detect the existence and concentration of pheromone to adjust their directions. Ants prefer to move towards paths with a high amount of pheromone. The behaviours of many ants behave the phenomena of positive feedback—the more ants in a path, the more probable for the others to select this path. Meanwhile, ants have the ability to adopt the environment variation. For example, ants can find a new shortest path when obstacles appear on the old shortest path.

2.The basic model of ant colony algorithm The search manners of many ACA models are essentially based on the pheromone level. We first analyze the basic ACA model and then give the comparison of MMACA with basic ACA.

__ 1033 __

TSP is the most common application background for ACA [4-5]. Ant k in city at time itchoose the next city based on

the probability

where Jk(i) is the set of cities that remain to be visited by ant k positioned on city i; is the pheromone of the path connected city i and city j at time t; ηij is the heuristic information associated with city i and city j, which is determined

based on the requirement of practical problem and in this work ηij is set with dij and dij is the distance between city i and city j; and α, β are the parameters that determine the importance of τij(t) and ηij, respectively.

ρ, Pheromone decay parameter, is introduced in ACA to weaken the influence of initial state, for the beginning state

is set randomly and the initial pheromone also has great randomness.

where is the amount sum of pheromone between city i and j city when ants locating at city i visit city j from time t to time (t+n).

ACA has been applied to the path optimization problems. However, there exist some problems such as great computation and unsatisfactory search results. While searching the best path, ants only use the local information to adjust the pheromone. When all ants completed a tour, pheromone will be adjusted again using the global updating rule. Because of its positive feedback mechanism, the computed speed is greatly accelerated and it is especially suitable for small combination problem. However, when the scale increases, the algorithm efficiency drops greatly and stagnation often occurs so to result in the trap of local optimization. MMACA was then presented to solve these problems.

3. Max-min ant colony algorithm The followings give the comparison of MMACA and ACA.

1) Updating manner of pheromone Only the best ant that constructed the shortest tour is allowed to deposit pheromone.

The updating rule of this ant is given by

bestWhere Δτij=f (sbest),f(sbest) indicates that this solution is the best one of current iteration or the global one.

2) Range limitation of pheromone The range limitation is implemented when the pheromone exceeds [τmin,τmax]. If τij>τmax, τij is set with τmax, while if τij<τmin, τij, is set with τmin. Reference [6] points out that τmax converges

at τij1?ρ)f(sopt) and τ

min has the relationship as following:

From above analysis, we can find that ACA and MMACA are essentially accordant. On the one hand, both of them enhance positive feedback to improve the search efficiency. On the other hand, some techniques are carried out to reduce the possibility of getting in local optimization snap.

Another disadvantage of ACA is that many parameters are just empirically set, and the number of ant colony is frequently adjusted based on the experimental results. So, when ACA is applied to a practical problem, some attempts are carried out in advance in order to adjust parameters based on the experimental results, and then search can be done again. The above process leads to the difficulties for the application of ACA. Furthermore, the performance is rapidly dropped especially for large-scale optimization problems. We propose a new-type intellectual ACA to solve these problems.

NEW-TYPE INTELLECTUAL ANT COLONY ALGORITHM

The proposed intellectual ACA is different in spirit from the other ACAs in that it adopts a novel dynamic pheromone updating rule, uses a particular variation scheme to optimize each searched result, and introduces artificial interference.

__ 1034 __

1. The novel dynamic pheromone updating rule Pheromone, which is the communication medium for ants, can guide search directions of ants. Local pheromone updating is utilized in many ACAs. However, we found that its effect is unsatisfactory after carrying out many experiments. More time is required because each move of ants must update pheromone, and the pheromone level in the optimized path are greater than that of other path outside the optimized path due to the local pheromone updating, especially for the upper search. So the computation time can be greatly reduced and the repeated search can be avoided if pheromone is only deposited in the global optimized path and the last optimized search path without lose of excellent performance. Based on the extent of distribution uniformity in optimized solution, we proposed a new state transition rule given by (5) while the pheromone is still updated according

to (3).

where Dij is the distance from destination to initial point and is inverse-ratio with Qij. The shorter the distance from destination to initial point is, the greater the probability of selecting this destination is. This rule can direct ant to move towards point with shorter path. Vij is the visited time of (i, j)and is inverse-ratio with Qij, too. The more the visited time of any destination is, the smaller the probability of selecting this destination is. This can direct ant search new path to avoid the problem of local optimization. And the trade-off between convergence acceleration and prevention stagnation can be obtained. This new-type dynamic pheromone updating rule has more excellent performance in convergence speed and stability compared to the common ACAs, for each ant has contribution to search during search process.

2. Inverse variation The severe disadvantage of ACA is to demand great search time. For this problem, many improved schemes have been proposed. For example, a new individual is produced using crossover operator in genetic algorithm. Namely, two individuals are randomly selected from parent population and a new individual is produced by randomly exchanging some gene section of the two ones. However, this method often destroys the conditions with which individuals may be the feasible solution. In this work, parent crossover operator is discarded and single-parent exchange operator and inversion operator are designed to produce new individuals that are applied to by inverse variation method to change the variation conditions.

Single-parent exchange operator can produce a new individual by randomly exchanging a pair of gene of parent one, and the exchanging number and position are stochastic. is just an example. The variation operator means that two positions are randomly selected in an individual with that the individual are divided into three parts, then the mid-part still maintains invariability except the order is reversed. For example, (where is inversion point), [8], a new bit string, will be produced after an inverse variation operation. Another example is given as following: . The single-parent crossover and variation operator maintain the possibility that individual becomes feasible solution and the search ability can be improved in solution space. For any individual, the single-parent crossover operator can produce a new individual by some gene exchanging operations. The variation operator can transmit effective gene section of individual to its offspring, and the important gene can be more compact and be rarely divided by crossover operator, and the computation speed is greater due to the two operators. The produced individual also needs mutation operation. Let agnate chromosome be . If the mutated variable is , then

, where function returns a value between (0, a) and converges at 0 with increment of t. And Δ(t, a) has a relationship as followings: Δ(t, a)=a(1?t), where a is a random number between (0,1); T is the largest algebra and b is just a parameter. This function makes that search uniformly distributes in solution space at the beginning of iteration and distributes in the local space to avoid destruction of excellent individuals produced at the upper iteration. After mutation operation, the length of chromosome varies along with change of path. A deletion or insertion must be done at the chromosome tail to match the corresponding path. The be a passed path by one ant, if the inserted weight is a stochastic real number. Let

is met and the time-consuming after path inversion is condition of

shorter than the one before inversion, a new path will replace the old one, otherwise the old path is still saved. This process is repeated for population until some terminated conditions are met.

The mutation number is stochastic but there is a rule that the number is increased along with the increment of path length. The performance of iteration will be improved and the time will be greatly reduced owing to this mutation operation. b

__ 1035 __

3. Artificial interference The basic ACA easily runs into local optimization if there exists repeated path. When the information from garage gate to vacant vehicle position is ultimately equal, ants will search these paths with equal probability. Then oscillation may occur in some paths. So, we introduce artificial interference to delete some paths that will block the vehicle entrance. All optimized paths are dynamic due to the dynamic change of vehicle position.

OPTIMIZATION PROBLEM OF LARGE-SCALE AUTOMATED THREE-DIMENSIONAL GARAGE

1. System structure of automated three-dimensional garage The garage task system consists of monitoring server and PLC (Programmable Logic Controller). And the task mainly involves two processes—card-number identification and movement of stacker. When entering the garage, users must take out a card that is scanned by the server. The server identifies the card-number and automatically sends the task instruction to PLC system. Then the PLC system moves stacker into the appointed position by the decision instruction. When parking vehicle, driver is guided by indicator light. The parking indicator light will be lightening when the vehicle parks the correct position. The garage gate will be automatically closed after completing the parking task. Many signal detections, including over-length detection, position detection, urgent parking detection and etc, are implemented for correctly moving stacker. If stacker doesn’t reach the correct position or the vehicle length exceeds the limitation, the stacker wouldn’t do any operation. If the urgent parking instruction is detected, any operation won’t be carried out. Moreover, control software can select some protected operations. For example, time protection can ensure the safety of equipment and vehicle when system can’t detect any signal due to the hardware malfunction. The path of stacker getting in or out garage has decisive influence on task efficiency.

2.The mode of getting in or out of garage based on NIACA We apply NIACA to the optimization problem of large-scale automated three-dimensional garage. Stacker, which can move vertically and horizontally, takes charge of moving vehicles between vacant position and gate. The three-dimensional garage structure is illustrated in Fig.1. X-axis denotes the parking position and y-axis denotes the storey number of parking position. The garage is divided into n parts. In each part, a stacker is mainly responsible for the task of this part. If one stacker fails to work, adjacent stacker will take over the work of the one with malfunction. The time from gate to the i-th position is obtained as

following:

where L and H are the length and height of parking position, respectively. There is a relationship νx=3νy and (xi, yi) is the coordinate of the i

-th position.

Figure 1: The three-dimensional garage structure

The following are some statements in algorithm.

(1) All ants set out from source point (garage gate) with equal speed in all directions, and finally reach the destination (vacant parking position).

(2) After reaching destination, ants return immediately, and randomly select path according to pheromone until they reach the source point, and then set out again. This process is repeated until some terminated conditions are met.

(3) Ants have memory and visit any point only one time.

The algorithm steps are given as following:

Step1: Initializing pheromone, ants begin to search from gate. Each ant transfers to the next position with probability given by (1).

Step2: One search is completed when ant reaches vacant parking position. When all ants completed a search, the new dynamic pheromone-updating rule will be carried out. The number of ant colony m and the length passed by each ant

____ 1036

are recorded.

Step3: During the optimized process, gene exchange and inverse variation operation are carried out to maintain the diversity of population. If new path is shorter than old one, then the new one will replace the old path, otherwise still reserve it.

Step4: If pheromone is equal in adjacent regions, artificial interference is introduced, and the path with smaller energy consuming is selected. The state of parking position is detected at any moment during the process. When the state of parking position changes, optimized path will be gained by dynamic adjustment.

Step5: The algorithm is terminated if some conditions are met. i.e. the optimized number reaches the set time or latest iteration performance maintain nearly invariable.

Step6: Outputting the result.

EXPERIMENTAL RESULTS

We have experimented with three ACAs for the optimization problem of taking and parking vehicles in garage, and Table.1 reported the performance comparison of three ACAs. The 6-storey garage is divided into four sections. In each part, a stacker takes charge of the task. We implement the basic ACA, MMACA and NIACA to this problem, respectively. The parameters were set as following: ρ=0.4, α=1, β=5, and ant number is equal with the number of vacant positions. Each algorithm ran 30 times with 300 iterations.

Table 1 indicates that the new-type intellectual ACA outperforms the two other ACAs, and the time-consuming of NIACA is least. Fig. 2 and Fig. 3 illustrate the simulated result at 50 iterations and 100 iterations, respectively. The path is dynamically changed due to artificial interference.

Table 1

The performance comparison of three ACAs

Figure 2: The parking position after 50 iterating

Figure 3: The parking position after 100 iterating

Fig.4 shows the time-consuming performance of ACA with and without artificial interference. The method of artificial interference is illustrated as follows: one ant is randomly selected, and its eyeable region and adjacent region are both set with D0. When a vehicle appears in the D0, the ant can pass this region (this principle is similar to the one of the eddy current sensor, adopted in the anticollision device of robot. The principle of eddy current is that when conductor

____ 1037