Abstract
This paper suggests an obstacle avoidance scheme that enables a group of micro-UAV (Unmanned Aerial Vehicles) to avoid colliding with an obstacle that is found in the course of the flight. This scheme considers a method for UAVs to avoid colliding with such obstacles and a plan of action for when the UAVs in the group lose connectivity during flight. The main goal is for UAVs to reach the target without colliding with any obstacles. To achieve this goal, directly after the UAVs avoid the obstacle at a raised altitude above it, they fly at a higher altitude for a while and then descend to their original height. When this approach is judged to be inefficient because the height of the obstacle is too high, the UAVs divide into two groups and move to either side of it while continuing to fly at the same altitude, thereby avoiding the obstacle. Afterwards, they gather into one group again. We verify the proposed scheme and do the performance evaluation by ns-2.
1. Introduction
UAVs, which have been studied for the military purpose of detecting enemies, act as spies and can be used to communicate between friendly forces; they are expected to be used in various places and for many purposes; for example, searching for patients under circumstances in which a communication infrastructure has been destroyed or monitoring the scene of a disaster. The usefulness of UAVs is greater when several UAVs that maintain communications with each other are used compared with when only one UAV is used. In this paper, we assume that UAV is so small that the people can carry it with their hands or the general car can carry several ones. We define it as micro-UAV and we use the terms UAV with the same meaning as the micro-UAV in this paper.
When several micro-UAVs are used, we can obtain the following effects. First, when UAVs process detections, they can make the boundary of the detection wider and the time of the detection shorter. Second, when several UAVs form a communication network with one another, a rapid decision on a situation can be made because the information on the target is sent to the base station through communication between the UAVs without any communication infrastructure.
To use these advantages, this paper suggests an effective scheme in which several UAVs maintain communication connections with each other in a group, reach a target, and escape rapidly when they find a fixed obstacle. This capability can be used, for example, while investigating the scene of a disaster. We assume that the communication among UAVs can be done through short range wireless technology such as Wi-Fi or ZigBee. It will be useful that the proposed scheme is applied to the disaster environment or the wartime.
The remainder of this paper is arranged as follows. In Section 2, we describe the related works and show the differences from our work. In Section 3, we describe the process of finding obstacles, the method for transmitting the information on found obstacles, and the method of UAVs’ moving and splitting. The experiments are described and the results are discussed in Section 4. In Section 5, the conclusions are drawn, and finally, we discuss the questions that are considered in this study.
2. Related Work
There have been studies on UAV formations, on UAVs’ communication with each other, and on designs for finding obstacles with various sensors. The obstacle avoidance scheme in this paper has two methods: planning and reaction. Planning is used to plan the flight course of the UAVs, and Reaction is used to avoid an obstacle while UAVs are flying. Some examples of studies of a whole group of UAVs are mentioned below.
By means of the algorithm in [1], which ensures there is no collision, the flight course is fixed; otherwise, the UAVs would collide with each other during the flight. Richards and How [2] show a strategy with which UAVs will avoid colliding not only with obstacles but also with each other when they are flying in a group. Although the scenario in the studies of [1, 2], which involves swarms of UAVs that avoid colliding with obstacles that they detect, is similar to the scenarios addressed in this paper, these studies do not consider the communication between UAVs and they are conducted in a 2D environment. Scherer et al. [3] provide a scheme in which a micro-unmanned helicopter avoids fixed obstacles such as buildings or trees when it has a map of an area in advance. Similar to the studies in [1–3], which use the planning method of obstacle avoidance, the UAVs’ operators already had information about the obstacles’ positions, and they planned a flight course to avoid colliding with these obstacles. Therefore, these studies are different from the present paper, which suggests an immediate reaction to obstacles and an obstacle avoidance flight method.
This study is preceded by a study in which micro-unmanned flights installed with various sensors perceive obstacles and avoid them. Kwag and Chung [4] is a study in which UAVs find obstacles and avoid them by using a radar sensor. Watanabe et al. [5] uses the strategy that micro-unmanned flights equipped with 2D cameras detect obstacles and avoid them. Both papers focus more on the scheme that processes the information obtained using sensors, and they studied the plans of the flight courses in accordance with that information. Additionally, the communication between UAVs is not considered in these works, which makes these references different from the scheme that this paper proposes. Bethke et al. [6] studies a scheme that contends with a breakdown, such as running out of fuel while several UAVs are flying in a group. Although [6] also utilizes several UAVs, it focuses on methods that address an accident that occurs in the middle of a flight. Thus, its theme is different from this paper. Xu et al. [7] is a study that secures the communication connection between manned vehicles and UAVs; it proposes how to secure the communication connections between several manned vehicles and a UAV and several manned vehicles and several UAVs. Though the study in [7] may be similar to the scheme that we suggest, and it focuses on maintaining the connection between vehicles and UAVs while they are moving. However, it does not consider how to address the situation in case UAVs encounter obstacles while they are moving.
3. Proposed Method
This paper considers a scenario in which several micro-unmanned aerial vehicles that compose a group search for a site whose communication facilities were destroyed by war or disaster. It is our goal that when these UAVs discover obstacles in the middle of the searching process where there is a limited area for communicating with each other in a group, they return to the former formation after avoiding the obstacles; note that the avoidance can cause the disconnection of connection between the UAVs. The scheme that this paper proposes is reactive: when UAVs discover obstacles during their flight, they avoid the obstacles as a reaction to them.
This paper proposes two types of avoidance as follows.
One type of avoidance is the scheme that UAVs in a group climb above the obstacle and avoid it as quickly as possible while their intercommunication is maintained. The other type of avoidance is the scheme that after UAVs are divided into two parts and avoid the obstacle by moving to the two sides of it, they gather together at an appointed location and restore the communication connection between themselves. However, it is possible that their intercommunication is not maintained.
The UAVs assumed in this paper are Quadcopter types whose free flight is possible, and the fuel that the UAVs use during the flight is enough, and the effects that the obstacle has on the communications between the UAVs are not considered. Each UAV has its own index, and it can prevent the UAVs in a group from colliding with each other. And the communication range between two UAVs is 150 m in the present study. UAV has an attached device to detect an obstacle such as camera or ultrasonic sensor. Actually, we assume that UAV has the camera in this present study.
UAVs that form a group begin to search at the maximum velocity at the same searching altitude. The search is undertaken along the Y-axis, and the X-axis remains constant. The obstacles arranged in this paper have their own indexes and are considered to be in the shape of a cube, which is similar to buildings in a city. Additionally, the characteristics of these obstacles can be reflected in a simulated experiment. All of the trajectories of discovering and avoiding obstacles are recorded in the computer simulation. And an obstacle is assumed as the shape of a rectangular. The example of scenario before the obstacle is discovered and is shown in Figure 1.
The Initial State of the UAVs’ formation.
3.1. The Message Type and How to Send a Message
In this paper, the information sent in the form of a packet (i.e., the message) can be divided into two types. First, a beacon message is periodically transmitted to other UAVs to identify the neighbors (broadcast) (see Table 1 and Algorithm 1). Second, a forwarding message is used to indicate the discovery of obstacles and exchange the information. Additionally, an acknowledgement message (ACK) can be sent to check the success of forward message transmission. A forwarding message is different from a beacon message in that a forwarding message is generated and transmitted when an event occurs (see Algorithm 2).
The Messages.
The UAVs encapsulate their IDs and ( The UAVs periodically broadcast the Beacon Message A UAV receives a Beacon Message This UAV can identify its nearest neighbor and its location.
(1) Upon discovering the obstacle, (2) Transmit LN, Oposx, Oposy, Altitude and Velocity to the neighboring UAVs (3) When it receives a message that confirms information reception, It transmits the command for movement
(1) Receive LN, Oposx, Oposy, Altitude and Velocity information. (2) If self's Altitude, and Velocity value is NULL, Save Altitude and Velocity (3) If self's Altitude and Velocity values are not NULL Compare the stored and the new Altitude and Velocity (4) Update LN, Oposx, Oposy, Altitude and Velocity values for the data with a higher Altitude (5) Calculate the Altitude and Velocity for the neighboring UAVs (6) Transmit the information to neighboring UAVs (7) If the UAV does not have neighbors to its left or right, Transmit a message that confirms the information's reception.
3.2. Discovering Obstacles and Selecting and Canceling a Leader
By transmitting and receiving a beacon message periodically while the UAVs in a group are flying, each UAV recognizes the index of the neighboring UAV and its position. All of the UAVs in the group move while making a 180° observation of the direction of movement, and whenever the UAVs send a beacon message to each other, they move to the destination and confirm the existence and nonexistence of obstacles. When the UAVs and an obstacle are at a certain distance while the UAVs are moving, they discover the existence of the obstacle. The UAVs continue to move to the destination even at the time when the obstacle is discovered and before a leader has been selected.
There are three cases when a UAV discovers an obstacle as follows.
The case in which a UAV in the group discovers one obstacle. The case in which each UAV in the group discovers the same obstacle and sends the information. The case in which each UAV in the group sends information on different obstacles.
To avoid the obstacle or obstacles under conditions such as the above, the UAV that discovered the obstacle continues to inform the other UAVs in the group that it will be their leader until it receives their answers, and the task of the UAV that discovered the obstacle is as follows.
Maintain the information on the place and shape of the discovered obstacle. Decide on a suitable obstacle avoidance scheme by employing the available data. Calculate the avoidance point and the moving speed of the neighboring UAV and send the information to it.
The avoidance point is defined as a location that the UAV should fly towards to avoid an obstacle. A leader UAV calculates the avoidance point and sends it to neighbor UAVs, then neighbor UAVs calculates their avoidance point to fly. For example, in this present study, the avoidance point of the leader is calculated simply by adding 10 m to the height of the obstacle in the case that UAVs fly higher to avoid an obstacle. It is explained more latter in this paper.
The following is the process in which the UAV that discovered an obstacle while flying is selected to be the leader.
The UAV that discovered an obstacle takes the information on the UAV's position and the width and height of the obstacle and performs a calculation. This calculation is made to choose which one of the two avoidance schemes that this paper proposes will be used. After choosing an avoidance scheme, the UAV calculates the position and the speed of the other UAVs that are flying at either side of it with the avoidance algorithm that this paper proposes. After recording its identification number on the calculated value, the avoidance scheme and the leader's identification number show who the leader is. And the UAV sends this information to the UAVs on either side of it. When all of the UAVs at both ends of the group receive the information smoothly, they send their confirmation messages to the UAV that discovered the obstacle. When the UAV that discovered the obstacle receives the confirmation messages from the other UAVs in the group, it becomes the leader of the group.
When the leader is selected, all of the UAVs in the group begin to move to avoid the obstacle, and they retain the information on the leader and the obstacle until they each reach their avoidance points. When the UAVs in the group reach their avoidance points, they remove the information on the leader and the obstacle, and they manage the conditions in the same way if they discover new obstacles. If any UAV in the group discovers a new obstacle in the midst of moving to the avoidance point, this UAV does not inform the other UAVs until it reaches the avoidance point; then, this UAV informs them that it discovered a new obstacle after removing the information on the leader and the obstacle. The removal of the information on the selected leader and the obstacle are performed differently according to the scheme that this paper proposes. In the case of avoidance at a higher altitude, the UAVs keep the information until they pass the obstacle completely. This strategy is intended to prevent the UAVs from colliding with the obstacle in case they perform the avoidance at a lower altitude and then discover a new obstacle that is shorter than the former one. Additionally, if the UAVs avoid dividing their group into two parts, as soon as they reach the avoidance points they initialize the information on both the obstacle and the leader. Afterward, they contend with the next obstacle. Figure 2 shows the abstract scheme of how to decide between two methods. α means the weight value of the possibility of the communication disconnection. In SPLIT method, dividing their group into two parts, there is the possibility that UAVs cannot maintain the communication after avoiding an obstacle.
Deciding the avoidance method.
3.3. The JUMP Method
The JUMP Method is designed to avoid an obstacle by climbing to a higher altitude that is at least as high as the obstacle's height, and this method ensures that the communication connections continue between the UAVs. This approach involves the action that the UAVs in the group avoid an obstacle by rapidly moving as minimally as possible when they perform the avoidance, and they perform three types of action, which are the following (see Algorithm 3).
To avoid an obstacle, they climb to a higher altitude and move to an avoidance point. When UAVs that have reached the avoidance point find a new obstacle at the moving speed, they maintain the current obstacle information before avoiding the obstacle. The UAVs use the information on new obstacle that they had when avoiding the obstacle.
ON: ID of the obstacle Oposx, Oposy, Oheight: Coordinate of the obstacle and height
(1) Upon discovering the obstacle, (2) Get ON, Oposx, Oposy and Oheight (3) Calculate own Altitude and Velocity (4) Calculate the Altitude and Velocity by formulas (1) and (2) (5) Encapsulate the Altitude and Velocity information into a packet (6) Transmit the packets to neighboring UAVs
(1) Receive the Altitude and Velocity information. (2) If self's Altitude and Velocity value is NULL, Save Altitude and Velocity (3) If self's Altitude and Velocity value is not NULL Compare the stored and the new Altitude and Velocity Calculate the Altitude and Velocity by formulas (1) and (2) for the neighboring UAVs (4) Transmit the information to the neighboring UAVs (5) If the UAV does not have neighbors to its left or right, Transmit a message confirming the information's reception.
First, in the process of climbing to a higher altitude and moving to the avoidance point to avoid the obstacle, the action algorithm that the leader UAV performs is similar to the following.
The UAV that discovered the obstacle decides the location at which it will be situated after avoiding the obstacle while considering a safety margin distance of
The calculation of the location of the UAVs on both sides of the leader follows formula (1) as follows:
If the neighboring UAVs on both sides move using the value calculated through formula (1), when the process of avoiding the obstacle is completed, the flight distance of the UAVs on both sides becomes as minimal as possible, which ensures continuous communication between the leader UAV and the other UAVs. Although formula (1) ensures the communication connection between the UAVs in the group as much as possible, in the midst of moving for avoidance, it is difficult to ensure the communication connections between the UAVs. The reason is that their traveling distance is relatively short compared with the leader's distance, but if they move at the same speed as the leader UAV, then the distance between the leader UAV and the neighboring UAVs on both sides of it become farther compared with the time at which they start to move.
The leader decides the speeds of the neighboring UAVs on both sides of it to ensure the communication connection between them in the course of moving. This decision can prevent the communication connection from being cut, which can occur during the course of avoidance if the leader and the neighboring UAVs reach the avoidance spot at the same time.
The method of deciding the speed of the neighboring UAVs is satisfied with the following formula (θ is an angle between the avoidance point and the current position of UAV):
Because the leader moves the farthest, it rises to a higher altitude at the maximum speed and avoids the obstacle. As the leader calculates what the positions of the UAVs would be on both of its sides through formula (1), it decides its position, the neighboring UAVs’ positions, and the speed at which the neighboring UAVs will move using its speed and formula (2). Finally, the leader transmits the positions and the speeds of the neighboring UAVs, as decided through formula (1) and formula (2), using the Unicast method. The action algorithm of the UAVs that are not the leader is similar to the following: because the UAVs that are not the leader did not discover the obstacle, they move to the target spot and continually check whether there is an obstacle or not until the leader is decided. When the other UAVs receive the information about their avoidance points and moving speeds, in a process that is similar to what the leader did, they decide the avoidance points and moving speeds of their neighboring UAVs.
The UAVs at both sides of the leader each calculate the positions of the UAVs beside them. They can each decide the positions of the UAVs beside them by using formula (1); at this time, instead of the leader's avoidance point of formula (1), they use the heights that they received from the leader to determine where they will be situated.
The received moving speed decides the neighboring UAVs’ speeds by using formula (2), and the process is repeated until the last UAVs in the group receive their moving speeds. If all of the UAVs in the group receive their moving positions and speeds and perform their avoidance schemes until the moment that the process of avoiding the obstacle and reaching the destination begins, it is assured that all of the UAVs in the group avoid the obstacle and maintain the communication connection.
The UAVs of the group that arrived at the avoidance point continue moving at the same speed as before the avoidance actions and maintain the same (high) altitude. When they move to the end of the obstacle, each of the UAVs initializes the information about the leader and the obstacle that it has avoided. Lastly, the UAVs restore their formation to what it was before the avoidance. All of the UAVs descend to the avoidance points at the same speed, such as the distance of the Y-axis to which they climbed to avoid the obstacle; then, they restore the formation that was present before the obstacle avoidance action. If there is a new obstacle to avoid in the course of restoring the group's shape to its formation before the obstacle avoidance action and at the place this obstacle was discovered, the UAVs in the group perform another avoidance action through the same method after choosing the leader in the group and deciding on an avoidance scheme. The path that each UAV in the group takes to avoid the obstacle and reach the destination is similar to Figure 3.
An example of the JUMP method.
3.4. The SPLIT Method
The SPLIT method can retain the original group's shape and ensure a continuous mutual communication connection because the distance between the neighboring UAVs that are moving in the same direction as the leader is the same as the distance to the leader. The other group moving in the different direction from that of the group containing the leader maintains the communication connection between the UAVs in that group but the communication connection with the leader may be broken.
The SPLIT method performs three types of movement, which are described as follows (see Figure 4 and Algorithm 4).
The UAVs move to the appointed avoidance point, at which they divide into two groups. UAVs that have reached the avoidance point move to avoid the obstacle, but the altitude and moving speed are retained. The UAVs move to restore the former formation that was in place before avoiding the obstacle.
ON: ID of the obstacle Oposx, Oposy, Oheight: Coordinate of obstacle and height myX, myY, myZ: UAV's coordinate UAV_Interval: Interval of each UAVs
(1) Upon discovering the obstacle, (2) Get ON, Oposx, Oposy and Oheight (3) Calculate own coordinates for avoidance (4) Calculate neighbor UAV's coordinates By myX + UAV_Interval (5) Encapsulate the coordinate information into a packet (6) Transmit the packets to neighboring UAVs
(1) Receive coordinate information. (2) If coordinate information value is NULL, Save the coordinates (3) If self's coordinate value is not NULL Compare the stored and the new coordinates Calculate a new coordinate by myX + UAV_Interval for neighboring UAVs Transmit information to neighboring UAVs (4) If the UAV does not have neighbors to its left or right, Transmit a message confirming the information's reception.
An example of the SPLIT method.
First, when the UAVs move to the avoidance point and are divided into two groups to avoid an obstacle, the role of the leader UAV is as follows: the leader decides the shorter direction to avoid the obstacle from the two possible directions, and the leader considers the safety margin for preventing a collision with the ends of the left side and the right side of the obstacle. The leader that decided the avoidance direction lets the neighboring UAVs on both sides of it know their avoidance points. The avoidance points of the neighboring UAVs moving in the same direction as the leader are decided, including the distance between them to prevent them from colliding with each other at the leader's avoidance point. Because the leader knows the information about the positions of the neighboring UAVs, which was obtained through a beacon-message, the avoidance points of the neighboring UAVs are in the opposite direction from the direction the leader decided upon, which adds to the distance that the leader moves relative to the positions of the other UAVs and prevents the leader from going in the opposite direction. As a result, because the UAVs all travel the same distance, they can restore their original formation after avoiding the obstacle. If the information about the end of the left side of the obstacle is updated by the leader, then the leader informs the others of the value that was decided after considering the safety margin in the information with respect to the end of the left side of the obstacle.
The action algorithm of the UAVs that did not discover the obstacle is the following: the UAVs on both sides that received the information about the place to travel to from the UAV that discovered the obstacle inform the next neighboring UAVs about the avoidance points. To do so, they use the same method used by the UAV that discovered the obstacle, which is based on their positions. When all of the UAVs know the information about the positions that they will avoid, then they perform their avoidance at the appointed positions. The group of UAVs that has reached the avoidance points moves while observing the obstacle at the same speed as before; thus, they avoid the obstacle but maintain the same altitude. When they move to the end of the obstacle after observing it, each UAV initializes the information about the leader and the obstacle that it has. Lastly, before beginning the avoidance scheme, the UAVs return to the positions that they memorized, and they restore the formation that the group had originally had. In case the distances of the two groups that moved are the same when they performed these actions, they can restore the original formation and fly to the destination again. However, if the distances that they traveled are very different, then the condition occurs that one group goes before the other, and at worst, they reach the destination with the communication connection between the two groups having been cut.
If a new obstacle is discovered at the designated meeting place, for the UAVs to return to an original formation after avoidance, each UAV performs the same course from the action of discovering the obstacle. If the communication connection between the two groups has been cut, then the leaderless UAVs elect a new leader for the divided group and avoid the additionally observed obstacle.
Furthermore, the UAVs that have avoided the obstacle compare their positions with the positions stored when they started from the base station. At this time, if their positions are different from their original positions, to remain in the original formation, they move to the original destination by moving to the X-axis position that was stored at the beginning. The proposed method to avoid the obstacle by dividing into groups is performed when site is not efficient to adjust the altitude to avoid the obstacle because the obstacle is too tall. Additionally, the communication connection between UAVs in the group could be cut, especially when the group is divided. Thus, this method does not assume that the optimized action coincides with the core goal that the UAVs in the group avoid the obstacle promptly and maintain the communication connection with each other.
4. Experiments
4.1. Simulation Model
To evaluate the proposed method, an experiment was performed by using NS-2 (Network Simulator v.2.34) of the simulator on a Linux. We modify NS-2 objects to enable them to decide the position by themselves. And we collect the position of objects periodically and then draw the graph as a 3-demension because original NS-2 simulation does not support 3-dimension in its animation. In the simulation, 8 UAVs numbered from 0 to 7 move at 10 m/s at a height of 50 meters over a layout of land whose size is 3000 m × 3000 m. We perform the simulation to verify the proposed scheme and to do performance evaluation. We investigate to what extent the value of α has an effect on choosing an avoidance method, the height of the obstacle to avoid, and the time required to avoid the obstacle through the two methods. The specific configuration and parameters of the simulation follow Table 2, and the information on the arrangement of the obstacle follows Table 3. We arranged the obstacles as shown in Table 3 and observed the result of the movement in the first simulation. Then, we experimented with changing the value of α, the width in Table 2, and the value of Z of the first obstacle in Table 3.
The configuration and parameters of the simulation.
Information on an obstacle's position.
4.2. Analysis of the Result of the Simulation
Figure 5 shows the result of the simulation of the SPLIT Method using NS-2. Through the result, we can observe a scenario in which the proposed method works smoothly. The UAVs restore their communication connection as they restore their prior formation from before the avoidance action. The restoration occurs while the UAVs are moving to the rendezvous point that was appointed in advance, and even though the communication connection between them is cut during the course of the avoidance action, they can avoid this problem when they discover another obstacle. Figure 6 extends the simulator's actions beyond two dimensions, as motion in three dimensions is appropriate and shows the result as a trajectory. The X-axis of the graph shows the positions in which the UAVs were arranged, the Y-axis is the direction to move for detecting obstacles, and the Z-axis shows the altitude of the flight of the UAVs and the height of the fixed obstacles.
The simulation result of the SPLIT method.
The trajectory of the JUMP method.
UAV number 1 discovers a fixed obstacle and avoids it by rising to an altitude of 110 m, and at this time, the UAVs on both sides of UAV number 1 keep moving. At this time, only the speed is controlled because the UAVs can preserve their communication connection despite maintaining only the altitude of their flight. We can see that UAV number 1 avoids the first obstacle and controls the altitude to restore the original formation. Afterwards, when UAV number 3 discovers a second obstacle, if number 3 avoids it alone, it is impossible to sustain the communication connection with the other UAVs; as a result, the UAVs on both sides of number 3 also adjust their altitude and avoid the obstacle with number 3. Figure 7 is the resulting graph of the experiment, which indicates how high the obstacle avoided by the JUMP method is and what effect the change of the obstacle's width has when the value of α is applied. The X-axis of the graph shows the change of the value α, and the Y-axis shows the height that the UAVs should pass over to avoid the obstacle. A larger value of α implies a larger width of the obstacle, and thus, the height that is required for the UAVs to pass over and avoid the obstacle becomes higher. When the UAVs perform avoidance by dividing into two groups, the total distance that the leader moves is multiplied by as much as the value of α. Therefore, the larger the value of α becomes, the higher the height is for the UAVs to pass over and avoid the obstacle by performing the JUMP method. Additionally, a shorter width of the obstacle implies that there is a stronger tendency for the UAVs to divide into groups; thus, the larger the width is, the higher the height is to perform the JUMP method. Furthermore, as the value of α becomes larger, the width of the obstacle tends to become smaller. When the value of α is not considered because the moving distance is immediately affected by the width of the obstacle, the height for the avoidance action changes. However, when the width of the obstacle is small, the distance that the leader moves to avoid the obstacle is not long and the value of α is also small. Therefore, though the value of α becomes larger, the height for the avoidance makes little difference.
Resulting graph of the experiment that observes how high the obstacle avoided by the JUMP Method is and what effect the change in the obstacle's width has when the value of α is applied.
Next, we observed the operating time through two methods. Figure 8 is the graph of the time taken to reach the avoidance point through the two methods when the value of α is 1 and the height of the obstacle becomes higher. In addition, Figure 9 is the graph when the value of α is changed to 1.2. The X-axis of the graph shows the height of the obstacle, and the Y-axis shows the time taken to reach the avoidance point. Figure 8 is the graph of the case in which the penalty of the loss of the communication connection was not considered. Furthermore, because a higher height of the obstacle implies a longer flight time even though the height of the obstacle becomes only slightly higher, the UAVs show the pattern of avoiding the obstacle using the SPLIT method. Afterward, they move to the destination. Figure 9 shows that when the communication connection is maintained, the UAVs also avoid an extremely high obstacle compared with Figure 8. The two graphs show that the UAVs avoid this obstacle without any change in the avoidance time, though the height of the obstacle becomes higher when it is over a specific constant height. This scenario shows that the UAV that discovered an obstacle avoids it by choosing the SPLIT method, and at this time, the SPLIT method addresses the problem. This choice can impair a key aim, which is to move to the destination right after avoiding the obstacles because of the long avoidance time that is required to avoid all of the obstacles by using the JUMP method.
The resulting graph of the time taken to reach the avoidance point through the two methods.
Result graph when the value α is changed into 1.2.
5. Conclusions
This paper proposed a method for the process in which UAVs avoid three-dimensional, fixed obstacles. Moreover, this paper proposed a specific method to control the altitude and the velocity and to avoid obstacles while retaining the multihop connection between the UAVs during the obstacle avoidance process. Another method is proposed to restore the original formation after it has been divided into two groups that were formed to avoid both sides of an obstacle to address the problem that was in the above method. In addition, the proposed method was inspected and evaluated by using a simulation. If the proposed method is applied, it ensures that several UAVs efficiently search without colliding with any obstacle while they are searching an area about which there is little information. When we perform the SPLIT method as a research task in future work, we will research the method for avoiding obstacles and securing the communication connection between UAVs in a group.
Footnotes
Conflict of Interests
The authors declare that they have no conflict of interests regarding the publication of this paper.
Acknowledgment
This research was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT, and Future Planning (no. NRF-2011-0014740).