1 Introduction

In the current study, a method for locating a target such as a patient, fire, or an enemy soldier in case of natural disaster such as earthquake or war was researched. We assumed lack of availability of general information such as satellite images, and therefore divided the process into an initial phase for acquiring general information and a later phase for searching the suspected regions. Since the communication infrastructure has been disabled, we assumed that only short-ranged wireless communication such as Wi-Fi and ZigBee is available. Using only small UAV groups communicating with such wireless technology, regions suspected to harbor the target are quickly surveyed for general information, which is used for subsequent search of the identified regions to locate the target. The two tiers will be referred to as global exploration and close search.

Global exploration involves the movement of micro UAVs and aims at acquiring the map of the whole search region and to determine the paths of the UAVs rather than locating the target. Therefore, the UAVs perform global exploration at a high altitude starting from the base station, and they come closer to the ground when performing close search after the exploration of all regions. For close search, information obtained from the global exploration is used to divide the whole region into N main regions that the target is most likely to be present, and the UAVs are divided into N groups for respective search of the regions. All UAVs are assumed to possess a camera. Images acquired during global search, which is conducted at a high altitude, has large field of view that allows for acquisition of information about a larger region but the images have low resolution and cannot be used for accurate determination of course of action, whereas images acquired during low-altitude close search convey information about a smaller region but allows accurate decision-making due to its high resolution. The UAVs are assumed to possess collective intelligence that allows them to share the information they obtained from image recognition. Discussion of the image recognition technology itself is outside the scope of this study and will not be presented.

Related works will be overviewed in Sect. 2, and the proposed method will be explained in Sect. 3. Test results will be presented in Sect. 4, followed by the Conclusion.

2 Related Works

In order to search for the target and the whole search region, UAVs must conduct the search at an altitude that is the same or higher as that of the target. Even if the target is located lower than the UAVs, UAVs may have difficulty in accurately identifying the target if the difference in altitude is large. Teuliere et al. [1] used color-based algorithm to filter and analyze the color of the object acquired by a camera at a pixel-level to identify the target. If the target can be correctly identified during the close search of the proposed method, the target can be continuously monitored even if it temporarily escapes the field of vision of the UAVs.

Novak and Seyr [2] conducted kinematic analysis of speed and movement angle of a two-wheeled robot to determine the path to a target location, while Stentz [3] and Ferguson and Stentz [4] used a four-wheeled robot with a scheme, which adds floor plan path upon each movement and determines the optimal path. These studies share in common that the robots use sensor from the initial search phase to identify obstacles and re-analyze their paths to the target. In this study, rather than two-dimensional movement and sensor for identifying obstacles, we simplified the map search process utilizing three-dimensional information, and also the path toward the target.

Pitre [5] proposed the PSO (particle swarm optimization) algorithm for close search. Foo et al. [6] identified the limitations of two-dimensional search and proposed a three-dimensional path planning using UAVs. Their goals were to identify the location with minimal threat to UAV movement, and also to minimize fuel consumption by the UAVs for increased search duration. These studies did not involve direct searching of the target and only proposed a method for optimal path determination by identifying obstacles and external threats between the UAVs and the target. The current study is different from the previous studies in that its main goal is to quickly search the regions at which the target is likely to be located using only UAVs and thereby promptly establishing communication connectivity such that the base station can quickly receive information about the target. Also, a method for returning to the original start position at the end of the search was developed, which unnecessitated the need for pre-defining the search start position of the UAVs and size of the map.

In a study by Goodrich et al. [7], a single UAV performed the role of pilot and sensor operator; their goal was directed task analysis about the target. The study minimized human involvement for task performance, and included algorithms for path generation and path-following. As in [7], we assumed that the base station is located at the top-middle location of the map instead of at the center of the map, and the search was conducted in a zig-zag manner instead of a spiral. Also, instead of visual-based search relying on a single UAV, the map analysis was conducted using multiple UAVs for global exploration to identify overall movement paths followed by directed approach toward the target.

As with Goodrich et al., Waharte and Trigoni [8] proposed a visual-based search, but the map was divided into sections beforehand by a greedy algorithm applied on satellite images, and multi UAV paths were determined using greedy heuristic method and Markov decision process. In recognizing the paths over the whole map and moving along them, UAVs maintain the distance required for communication, communicate information about the map, and analyze the information. Waharte and Trigoni [8] required efficient map analysis in a timely manner assuming that the UAVs possess finite amount of fuel. In our study, our goal was to not utilize any satellite images and use only UAVs to search the whole map, and develop a method for overall map analysis with a single search. Also, we aimed to quickly relay the information to the base station by store-and-forward by the UAVs.

To identify the location of on-ground targets, Yu et al. [9] used the UGVs (unmanned ground vehicle) as a search tool in addition to the UAVs. UGVs use their sensors to identify obstacles and secure paths on the ground, while UAVs fly to identify the location of the target. Urban area in which the target exists was divided by the dynamic occupancy grid, and the Markov chain model and Bayesian filtering were used to analyze the path of the target. In this study, we determined that search by UAVs alone would be efficient for identifying an on-ground target. Especially, we researched the method to fly the UAVs at a high altitude in order to generate a gross map.

3 Proposed Method

3.1 Initial Formation for Global Exploration

In this study, UAVs increase their altitude along the z-axis from the base station at the outset of the global exploration of the region, while attempting for a linear formation in the y-direction. In fact, the direction of the linear formation can be x-direction or y-direction. We selected y-direction for the easiness on the visualization of thinking. If x-direction formation is selected, the initial flight will be the y-axis direction. For this, UAVs positioned to the left and right of a reference UAV move simultaneously. Selection of the reference UAV is performed as follows.

In the initial linear formation, the UAVs are aware of their neighbor UAVs through continuous Wi-Fi and GPS communication, and they also know the direction of message they transmit or receive. With this assumption, the UAV located at the left end transmits a beacon message and the most current number of UAVs to the UAV capable of communication. The UAV that receives the beacon message relays the message after incrementing the number of UAVs by 1 in the same direction, but it returns the current number of UAVs to the transmitter if there are no more UAVs in the direction of original transmission. The UAV without any neighbors in the direction of transmission calculates the final number of UAVs from the received message and assigns the UAV located at the center of the group as the pivot node for initial search formation.

The UAV selected as the pivot node transmits a command for starting the search in the y-direction to its neighbor UAVs. The overall process is described by the pseudo code in Fig. 1.

Fig. 1
figure 1

Pseudo code for pivot node selection

Full size image

The pivot node UAV (PN) also transmits position numbers (PNO) and its own coordinate in the y-axis formation command. For PNO, UAVs to the left of the PN receive odd numbers while UAVs to the right of the PN receive even numbers. PNO increments by 1 in left and right directions respectively, e.g., 1, 3, and 5 to the left and 2, 4, and 6 to the right. UAVs that receive its PNO value and coordinate of the PN use the coordinate as the reference and move to a position that is located at a distance equal to the maximum communication range times the PNO (Fig. 2).

Fig. 2
figure 2

Initial formation of the UAVs for global exploration

Full size image

In Eq. 1, UN.Y is the y-coordinate of the UAVs, PN.Y is the y-coordinate of the PN, and WRD is the maximum range for Wi-Fi communication among the UAVs according to the 802.11 communication protocol. X- and z-coordinate are identical for the UAVs within a group and were not included in the equation.

$$UN.Y = (PNO \times WRD) + PN.Y$$
(1)

3.2 Global Exploration

In this study, the UAV group was assumed to know the size of the whole map to be searched beforehand. Also, the location of the base station from which the UAVs start their search was arbitrarily set to be at the top-middle of the map. In accordance of these assumptions, UAVs should avoid regions that have been already searched and minimize their movements for efficient search.

Start of UAV movement begins with a command message from the PN. UAVs except PN send the completion message of arrival to neighbor UAV, after they arrive to the initial position for the global exploration. This completion message is the beacon message. It has the counter starting from zero, which it increments by one whenever it is relayed to other UAV. When PN receives this message, it compares between the number of UAVs and the counter value of the message, if it is the same, PN sends command message of the start of exploration to other UAVs. UAVs that receive the search command begin their movement according to the rules listed in Fig. 3.

Fig. 3
figure 3

Rule for global exploration

Full size image

UAVs do not interchange their positions during the global search. There is no parabolic movement, and they only move in either the x- or y-direction. From these movements, they can conduct the search while maintaining minimal movement, but the drawback is that the movement is inflexible in cases such as Rule 4 in Fig. 3.

In cases such as Rule 4, the UAVs will determine whether to search or not before determining their paths. This process is described in Figs. 4 and 5 in a scenario format.

Fig. 4
figure 4

Transition toward the y-direction movement during global exploration

Full size image
Fig. 5
figure 5

Scenario for measuring the extra value of the map

Full size image

Figure 4 shows the transition to the y-direction movement during a normal global exploration. When the UAV group bordered by thin line moves to the position of the thick line-border group, it moves to the position of the dotted line-border group according to Rule 3. Here, the distance between the UAV groups is WRD. Figure 5 describes the situation in Rule 4. Extra value (EV) is the remaining size of the map in the y-direction, and this value is used as the reference for determining whether to continue the search.

Scenarios (1) and (2) in Fig. 5 are significantly different. The search in this study does not pass the position already searched. However, it is difficult for the UAV group in Scenario (1) to calculate the EV value and perform both the final search and return to the base. Once the group conducts search to the right in the x-axis, the group must again conduct search to the left in order to travel a distance corresponding to the EV, and during this process the group may pass locations that have been already searched. On the other hand, Scenario (2) is more flexible. The UAV group may search to the left, move in the y-direction by EV, and then search to the right before returning to the base.

Therefore, the UAV group must identify its current situation as in Fig. 5 upon changing its direction as in Fig. 4, and adjust EV and the map size to determine its future path. This process is described by the pseudo code in Fig. 6.

Fig. 6
figure 6

Pseudo code for determining future path according to the EV

Full size image

Figure 7 shows the scenario for overall global exploration. UAVs initial move to the left, and account for transition to y-direction during the search. When they recognize that the search is almost completed, all the UAVs move to the right end of the map and travel down the right edge to complete and search and return to the base station.

Fig. 7
figure 7

Scheme for global exploration

Full size image

3.3 Close Search

For close search, the regions identified as being likely to contain the target from the information acquired during global exploration are selected as N way points, and the UAVs are divided into N groups for the search. Z-coordinate altitudes for the N way points are all set to be a little above the ground. The group that detects the target returns to the base station to deliver information about the target, while other groups return to the base station to receive information about the target and move to respective positions to maintain connectivity from the base station to the target. Total of eight UAVs were deployed for the current study, and they were divided into three groups of three, three, and two UAVs. Z-coordinate altitude of the UAV groups were also set to be above the ground.

Criteria for classifying the UAVs into N groups are determined by the value transmitted by the PN and total number of UAVs. Before starting the search, the PN must prepare to transmit total of four values in its message. The algorithm for group assignment related to these values are shown in Fig. 8.

Fig. 8
figure 8

Pseudo code for determining the N way point group

Full size image

The PN transmits GC, MC, RC, and GW along with the beacon message to its neighbor UAVs. The receiving UAV first determines if GC is 0, and then if MC is 0. If both values are not 0, the UAV decreases MC by 1, checks its own GW value, and relays the message to the next neighboring UAV. GC is decreased by 1 once MC becomes 0. Once the GC does not equal its initial value, the corresponding groups are assigned MC += 1 and RC −= 1 if the RC value is not 0. This process is required to count the RC in order to also calculate the total number of UAVs within a group.

The UAV that receives the message at which GC, MC, and RC all become 0 is the last UAV within the group to receive the message, and will transmit acknowledge message to the PN indicating that the message has been received. UAVs that are thereby assigned a group initiates the search using the way point coordinate they are each assigned. First, UAV Group 1 searches the way point located at the right end of x-axis. Group 2 searches the way point at the middle of x-axis. Finally, Group 3 searches the way point at the left end of x-axis. This scenario is described in Fig. 9.

Fig. 9
figure 9

Scheme for close search

Full size image

After conducting the close search, each group is classified as a group that did or did not detect the target. The first UAV within the group to detect the target transmits the target’s coordinate to the UAVs of the same group, and returns to the base station with the UAVs that received the message. For the group that did not detect the target, UAV near the selected N way point transmits to UAVs of the same group that the target was not detected, and returns to the base station with the UAVs that received the message. This algorithm is explained in Fig. 10.

Fig. 10
figure 10

Pseudo code for returning to the base station after close search

Full size image

UAVs returning to the base differ in their arrival times depending on the distance to the way point assigned for each group as well as speed. If the group that detected the target either arrives first or last, groups that did not detect the target must move to receive information about the target from the group that detected it. Also, the group that detected the target may encounter another group for a short duration due to close proximity of the way points or may have to wait for a group because its way point is especially distant from the base station. The UAVs within the same group can communicate via Wi-Fi multi-hop connection to the base station. Although the groups acted independent of one another during close search, upon returning they can communicate via Wi-Fi with UAVs inside the WRD to exchange information. Therefore, the group that detected the target must account for the situation in which it must wait for all other groups to also return to the base station, and it must be assumed that the other groups would be able to receive the target information upon returning to the base station. Figure 11 describes this process as an algorithm, with the beacon message exchanged among the UAVs as the reference as they return to the base after the process in Fig. 10.

Fig. 11
figure 11

Algorithm for processing transmission and receiving during returning to the base station after the close search

Full size image

The PNO value in Eq. 1 is a unique value that allows for each UAV to calculate the distance between the target and the base station and determine where it should be positioned. Using this value, the UAVs can share the target’s coordinate upon detecting the target and maintain connectivity from the target to the base station. If none of the N groups detected the target and reports to the base station, the base station re-divided the map to select new way points to restart the close search process (Fig. 12).

Fig. 12
figure 12

Formation of UAVs for maintaining connectivity after the close search

Full size image

4 Results

A computer simulation was conducted to validate the performance of the proposed algorithm and protocol. Simulation was conducted using NS-2 (Network Simulator v2.34). As the simulation environment, network size was 5000 m × 5000 m, and number of UAVs was 8. Default NS-2 simulation does not support three-dimensional modelling in its animation, but update_position function that updates the coordinate within the protocol and set_destination function that reflects the destination coordinate were modified to allow output of the three-dimensional coordinate. Coordinate data were collected every 0.3 s, corresponding to the beacon message period among the UAVs. The coordinates were reconstructed as a graph using a 3D modeling tool. Initial coordinate of the target was (x, y, z) = (3500, 2500, 0), and was assumed to be above the ground. UAVs flied 120 m above the ground during the global exploration, and 20 m above the ground during close search of the target.

It was mentioned previously that the number of regions for close search and their locations were determined by the collective intelligence of the UAVs from the information acquired from the global exploration. For example, if a fire is the target, the suspected regions may be selected from those regions that have fire-related parameter values higher than the threshold. If a person is being searched, the regions may be prioritized according to higher rate of person recognition. For our simulation, the number of regions and their locations were given. Of various experiments, Fig. 13 shows the case at which there are three regions to be searched (Table 1).

Fig. 13
figure 13

Result of overall scenario performance

Full size image
Table 1 Environmental variables
Full size table

As the UAV group returned to base after completing the global exploration, the group lowered its altitude while initiating close search toward the determined way points. In the experiment, UAVs in the Group 2 were the first to identify the target. As they were returning to the base, they encountered Group 3 UAVs. Group 3 UAVs that received the target’s coordinate moved to its final location, and Group 2 UAVs waited at the base station until the Group 1 returned. Final formation of the UAVs allowed for maintained connectivity from the target to the base station.

5 Conclusion

Methods proposed in this study aimed at acquiring the map of the whole region and identifying movement routes in case of communication infrastructure failure using only UAV group to search the area at which the target is located. Global exploration is conducted by the UAVs at an increased altitude, and the close search is conducted at a lowered altitude near the ground. This method would allow for identification of enemy camp or regions afflicted by disaster using only UAVs in case of war or natural disaster. Also, the two tier search system of global exploration and close search enables fast identification of the situation and facile response. For future improvement, paths of the UAVs during global exploration may incorporate curved movements to allow more flexible motion. Research on obstacle avoidance will also be conducted.