The Obstacle Avoidance Mode of Multi AGVs Based on Electricity Suppliers Logistics Environment
Juntao Li, Xingxiang Tao, Xiaohuan Xiang
School of Information, Beijing Wuzi University, Beijing, China
To cite this article:
Juntao Li, Xingxiang Tao, Xiaohuan Xiang. The Obstacle Avoidance Mode of Multi AGVs Based on Electricity Suppliers Logistics Environment. Science Research. Vol. 4, No. 2, 2016, pp. 61-66. doi: 10.11648/j.sr.20160402.17
Received: March 16 2016; Accepted: April 5, 2016; Published: April 25, 2016
Abstract: In multi AGV (Automatic Guided Vehicle) system, the core problem is how to plan a collision free path for each AGV, to solve the conflict between AGV and ensure the path of the path is not only the premise of path planning, but also the basis of the effectiveness of the task scheduling, so for the study of AGV system, multi AGV collision problem is also the research’s hotspot and difficult problems. Based on the project background, this paper mainly studies the obstacle avoidance mode of multi AGV based on electricity suppliers logistics environment, including the storage mode of AGV, the working mode of AGV, in the static environment and in the dynamic environment AGV may encounter conflicts, these are analyzed respectively.
Keywords: AGV, The Obstacle Avoidance Mode, Electricity Suppliers Logistics
Logistics handling robots, also known as warehouse handling AGV, and it is the abbreviation of Automated Guided Vehicle. Comprehensive use of computer, sensors, automation, machinery, communications and other disciplines of technology in AGV system. It has developed through in various fields, such as the case which in the warehouses and need to repeat handling, and some special occasions environment. AGV can accomplish these tasks instead of human beings, and it is one of the hot spots in robot application areas. AGVS is multi-AGVs system , the system is composed by a plurality of AGVs. When the task is assigned, according to the task’s situation and the AGVs’ own situations, the computer will divide the task into multiple sub-tasks to several specific AGVs to implement. On the way to the target spot, AGV needs to avoid obstacles. A key indicator to measure the performance of the robot is that the AGV can avoid obstacles in real time. This thesis aims to study the obstacle avoidance mode of multi AGVs based on electricity suppliers logistics environment.
2. Collision Avoidance Planning Method of Multi-vehicle AGVs
How the predecessors resolve the problem about Collision Avoidance Planning of Multi-vehicle AGVs? There are several ways: Petri Net method, Time Window method, Area Control method, Traffic Control Method and other methods, these methods can get different levels of scheduling effect. The following will introduce several key methods.
2.1. Collision Avoidance Planning Method of AGV Based on Petri Net
Petri Net method  was presented by Carl Adam Petri in 1960. The method is suitable to describe asynchronous and concurrent computer system model, and describing the phenomenon of the concurrency in a physical light, and it can describe the dynamic performance of the system greatly. At present, the method has been used to study collision avoidance of AGV and system scheduling.
Generally, the steps of applying Petri Net method to study the issue are the next, (1) construct n-tuple for the problem, (2) construct the model  of Petri net which can describe the problem, (3) apply the relevant theory to analyze and solve the problem. In the research of Collision Avoidance Planning Method of Multi-vehicle AGVs, the application of Petri net approach to this problem has achieved very gratifying results. In 2002, in 2002, Maria  used colored Petri net method to study AGV collision avoidance of multi-vehicle AGVs, in the case of multi-vehicle AGVs, color and token in Petri net should be one-to-one correspondence between AGVs. If do not color token, then it will be difficult to distinguish different AGVs while researching the model as a whole, and makes it difficult to grasp the whole model, so in order to grasp the overall model, this paper will color tokens in different colors to distinguish the different corresponding AGV, color the token pass libraries and the transition paths on the corresponding color, thereby forming a colored Petri nets.
Coloring Petri Net(CPN) is defined below：
CPN is a directed graph, which can be expressed as a five-tuple., among which:
(1) P and T are expressed as a collection of pass libraries and transition paths, their definitions are the same with basic PN;
(2) C is expressed as a collection of the colors of pass libraries and transition paths, in particular:
collection of the colors of pass libraries:
collection of the colors of collection of the colors of:
(3) expresses from the library p to transition t of input mapping (function):
(Non-negative integer), which corresponding coloring directed arc from p to t, and the here is the matrix;
(4) expresses from the transition t to library p of output mapping (function):
(Non-negative integer), which corresponding coloring directed arc from t to p, and the here is the matrix;
If you consider the time factor to the colored Petri net method, it will constitute a timed colored Petri net (CTPN). If you place the library as a node, and the change as a side, then the essence of Petri net is a figure and of a general nature, of course, it also has a lot of qualities.
In other countries, TIWARI  and others took the factor of time into consideration of Petri net method, which constituted a timed Petri net in order to avoid collisions between the AGVs in 2001. Then in 2002, 2003, Maria, Wu  and others made a study of resource-oriented colored Petri net method to solve the problem of collision avoidance planning, and they proposed a reasonable method based on inhibition of change excitation, achieving a no-collision path to AGV. In recent years, Petri net in the AGV collision avoidance program areas focused on the application of colored Petri net approach. Petri Net is mainly focused on the case of a deadlock and the AGV collision prevention, but slightly less on real-time collision avoidance.
2.2. Collision Avoidance Planning Method of AGV Based on Game Theory Combined with Modern Control Theory
Game Theory is the study of the nature of phenomena or competitive fight mathematical theories and methods. Game theory is widely used in economic and industry, in industry, Game Theory can solve a class of problems under the background of competition well, such as the issue of collision avoidance planning of multi-vehicle AGVs. Fundamentally it can be understood as different AGVs compete for the same resources in the same time period. Sudha  and others put forward the game theory model about multi-vehicle AGVs at road intersections. Background to the issue as shown below:
Make model of AGV#A and AGV#B by using state-space method:
It can also be expressed as:
Game theory is applied to the issue of collision avoidance, and the issue as a game of two persons zero sum, in the process of collision avoidance of two AGVs, the strategy must be one AGV pass through and the other must stop and wait. It can be understood as the victory of the competition when one gets the benefit and the loser lost the benefit.
The cost function can be expressed as:
Solving the collision problem would be translated to find out one of the following conditions
Thewhich meeting the conditions can be expressed as the saddle points of the cost function. Modern control theory has the advantage of being able to accurately model for the describing physical system. And the advantage of Game theory is that it can make rational analysis of the competitive background of the described phenomenon. When the combination of them, this problem can be solved.
When we take collision problem for two-person zero sum game to solve, one party benefit, then the other will lose interest. This approach would also undermine the interoperability of systems, so the issue of collision avoidance can be seen as Nash equilibrium, it can be understood as, in the game in order to achieve the interests of the individual, each individual takes the strategy which is the optimal response of the other individuals. In other countries, in 2003, Sudha put forward a game theory combined with modern control theory, this method is mainly applied to the AGV of offline route planning.
But its real time is difficult to apply to AGVs. However, there is no research associated with this method in China.
2.3. Collision Avoidance Planning Method of AGV Based on Time Window
Time window  is each collection that constitutes a specific time of execution AGV. Time window is divided into reserved time window and free time window. Reserved time window is the time interval that AGV occupy in one of the nodes, a free time window is the time window that can schedule the other AGV within reserved time window. Spatial feasibility is that there is a path physically between two nodes, time feasibility is that the AGV can leave the node within the beginning of the next free time period. Time window method is mainly detecting whether a collision will occur between the AGVs by checking the spatial and temporal feasibility.
The next, the analysis of the two conflicts which combined with the time window is shown in the following illustration. AGV#1 moves from node i to node j, AGV#2 moves from node j to node i, this kind of conflicts will be detected by comparing the order of two nodes, when it is anti-sequence, there is a collision problem.
As shown in the following illustration, in the case of two AGV are in the uniform speed, after AGV#1 arriving at the node j, and leaving directly, and AGV#2 arrives at this time, then there will be no conflict between the two AGVs. But if AGV#1 turns around in the nod, the reserved time window, which AGV#1 occupying in this node, will be lengthened. If AGV#2 moves uniformly in accordance with the original planning path, then there will be a collision course between AGV#1 and AGV#2.
In 2002, Samia put forward a more robust performance of the algorithm on the basis of the work done by Jung, improved the traditional method of simple delay to the method that the system can be signaled in advance, which makes the issue of processing to be more perfect.
2.4. Analysis of Collision-Related Methods
The main disadvantage of Petri net method is complex modeling, and the process of analysis is very cumbersome, especially it will appear "exponential explosion" of modeling defects for large AGVs, in recent years, foreign scholars introduced colored Petri to solve this problem, making the modeling process simply, but the process of analysis becomes more complex. Petri net is mainly focused on the prevention of the case of collision avoidance planning and deadlock, but the capability of solving real time collision avoidance is insufficiency.
The method of combining optimal control theory and game theory is mainly applied to the case of variable speed operation of the AGV, and not applied to the case of keeping running. And the method of combining modern control theory and game theory is also mainly applied to the case of AGV offline programming, it is not powerful in real time.
Compared with the above several collision avoidance algorithms, the advantage of the time window method is the following: (1) It can be well combined with other effective theory; (2) it can accurately calculate each AGV collision avoidance path; (3) it can quickly respond to new tasks; (4) it can reduce computational complexity. But the time window method is mainly applied to AGVs without outside interference and under no emergency conditions.
If each AGV can arrival and departure the corresponding nodes in a certain time, and through the nodes in the order that has been set, then the AGV collision will not happen. But this method has some limitations, mainly because time constraints would make scheduling even more complex, if one AGV appears in the case of delay, the other AGVs in the multi-AGV system will have a corresponding delay, so that the production efficiency is also greatly reduced.
In a dynamic environment, AGV not only needs to avoid collision with the static obstacles whose geographic information is known, but also needs to avoid collision with the running AGVs, in this case, the method of time window mainly changes the priority level of the AGVs through the node, and then adjusts the passing sequence according the priority level, updates the running path of AGVs, to achieve the collision avoidance planning in a dynamic environment.
3. Study on the Electricity Suppliers Logistics Distribution Center Warehouse Mode
Logistics as a key link in the e-commerce process, charged with physical delivery services between businesses and customers, efficient logistics system for e-commerce enterprises to enhance service, reduce costs, enhance competitiveness play an important role. Due to business characteristics of many varieties, high frequency, small batch, making e-commerce logistics gradually with high flexibility, high efficiency and high quality of service features. This model not only led the logistics technology, the rapid development of logistics equipment and Logistics model update cycle is becoming shorter. Improve e-commerce logistics capability is the key to improving e-commerce logistics node's processing power, storage, sorting, transport and distribution, using the intelligent information systems and automation equipment, improve speed and power, currently are not delivered in time, the ultimate "timed send" "the limit of" highly flexible services. It all boils down to, e-commerce logistics has the following features: 1, information; 2, automatic; 3, networking; 4, intelligent; 5, flexible. It is these characteristics that make e-commerce logistics center operation is different from other areas.
And stored in the warehouse, as e-commerce distribution center business has more variety, characteristics of high frequency, small batch, will result in goods receipt out too frequently, so the need for warehouse storage area so that the classification of goods in the warehouse district has its own characteristics, so as to improve the efficiency of storage of the goods. For a higher degree of automation of power distribution center needs to tailor its storage model.
AGV distribution center warehouse shelves are different from the traditional model, because AGV needs to handle shelves, the shelf designed of this paper for the underside length of one meter, width of one meter module rack.
Warehouse District refers to a warehouse as a whole according to the principle of property, popularity, quantity and divided into different areas such as operations, it will not only be better for the storage of goods, but also will make the outbound and incoming frequency significantly improve to make sorting more efficient. Mainly in the following ways to partition (1) according to the type of goods and property partition storing; (2) according to the dangerous nature of the goods to the partition storing; (3) according to the dispatch of goods to the partition storing; (4) in accordance with the associated partition to store the goods.
In the warehouse handling system, the AGV plays a role function in handling system, improve storage efficiency may consider to reduce the energy consumption  of the AGV, warehouse partitions the reasonable arrangement is necessary.
4. Study on the AGV Working Mode
After early research on e-commerce distribution center, summarizing AGV vehicle distribution center work modes are as follows:
AGV needs to run and turn in a narrow space. When the AGV receives the task instructions about storage or taking goods from computer, it will run beside the shelf according to the planned path. When AGV needs to turn around, it will stop and in-situ steer, and then continue until running to the target shelf. AGV will run to the bottom of shelf after completion of turning around in the node. AGV rotates its axis to raise in the way of in-situ steering until rising to the specified height, then it returns back to the storage port or chosen port according to the original planed path. AGV will steer itself but the shelf remains undisturbed, in order to ensure stability and the shelf will not collide with other shelves, when it needs to turn around. AGVs will wait in line for picking or storage, after they carry the shelves to the target nodes. AGVs will carry the shelves to the original nodes in the same way upon completion of this operation. AGV will rotate in the same way to reduce the height of the support shaft to remove the shelf when it arrives at the target node. When there is no new task assigned to the AGV which has finished the previous task, then it will return to the waiting area to wait the next task.
AGV working mode has the following features:
(1) AGV lifts shelf in the way of in-situ steering to raise support shaft.
(2) When AGV needs to turn around without carrying shelf, it will turn around in the way of in-suit steering.
(3) When AGV needs to turn around with shelf, it will steer itself but the shelf remains undisturbed.
5. Study on the AGV Types of Conflict
AGV types of conflict can be divided into two categories according to the types of environment: (1) In a static environment and the quantity of AGV is one, the conflict which needs to be resolved is the collision between AGV and static obstacles; (2) In a dynamic environment and the quantity of AGV is greater than one, there are some conflicts including the conflict which between AGV and the others, and the conflict which between AGV and the static obstacles.
In a dynamic environment, based on environment map modeling, conflicts between AGV and the others can be divided into three basic types, including the intersection of conflict, the catching up of conflict, and the opposing of conflict. The next section will illustrate the three scenes when a conflict occurs.
1) The intersection of conflict
The intersection of conflict does not belong to the catching up of conflict and the opposing of conflict. The two AGVs which create the conflict are neither positive relative nor in the same lane, that is crossing collision. The scenario of conflict is shown in the following figure:
2) The catching up of conflict
The catching up of conflict here is not the conflict in the conventional sense, because we set the AGV to a constant speed in this study, the issue that AGV2 is slower than AGV1 in speed does not exist. In this case, when AGV2 needs to in-situ steer, it will waste more time than pass through the node straightly, then the conflict may occur. The scenario of conflict is shown in the following figure:
3) The opposing of conflict
The opposing conflict refers to the case that multi-vehicle AGVs meet head-on in the process of running. AGV1 and AGV2 are in opposite direction of movement and in the same lane. The scenario of conflict is shown in the following figure:
If there is no corresponding avoidance strategy, whether AGVs are in a dynamic or a static environment, they will collide. In the multi-AGVs dynamic environment, based on the differences in different environments and task distribution, there will be a variety of complex and diverse conflicts. But these conflicts are composed of the three most basic conflicts above. The essence of these three types of conflicts is actually the problem of temporal and spatial overlapping. It can be understood as, two AGVs occupy the same node at the same time, thus they collide. So if you want to resolve the complex conflicts in the case of multi-vehicle AGVs , ultimately these three types of conflicts should be resolved, and then in order to ensure the AGVs can move safely and smoothly.
This paper mainly studies AGV collision avoidance algorithms in detail, focusing on introducing the Petri net, Game theory and modern control theory and the method of combining time window method, and analyzes the advantages and disadvantages of the methods of collision avoidance, according to the AGV analysis results and the actual situation of the AGV, the paper researches collision avoidance plan in a dynamic environment by using the time window method. Then, the collision avoidance of multi-AGVs modes in the environment of e-commerce are studied, and the paper analyzes the warehouse storage mode and the working mode of distribution center. Finally, the paper analyzes the types of conflicts of AGVs which would occur in the static and the dynamic environment.
With the deeper studying of the subject, due to time constraints, we can not expand the topic more comprehensive, but this paper provides the basis for solving the issue about collision avoidance of multi-AGVs under the electricity supplier logistics environment. Therefore, the paper is very necessary for the follow-up study of the collision avoidance planning of multi-AGVs, and certainly there are some very important applications there too.
This paper is supported by the Funding Project for Technology Key Project of Municipal Education Commission of Beijing (ID:TSJHG201310037036); Funding Project for Beijing key laboratory of intelligent logistics system; Funding Project of Construction of Innovative Teams and Teacher Career Development for Universities and Colleges Under Beijing Municipality (ID:IDHT20130517), and Beijing Municipal Science and Technology Project (ID:Z131100005413004);Funding Project for Beijing philosophy and social science research base specially commissioned project planning (ID:13JDJGD013).