1. Introduction

Searching for targets within an unknown environment is a traditional task for mobile robots. Robots are usually equipped with sensors to detect targets and they need robust strategies to explore the search area as fast as possible [1]. Performance is further improved by employing a team of mobile robots instead of a single robot, this decreases the time needed to complete the search task and increases robustness to failures. Robotic search is especially preferable when the search area is either hazardous or inaccessible to humans. Such applications may include planetary exploration, finding victims in devastated area after a disaster, locating mines [2]. Despite the fact that search has been intensively investigated in the past [3], using a team of mobile robots for search is a more recent development and has not yet been studied extensively. There are two general approaches of target searching in a given area based on the coordination among robots. In the first approach, the robots (robots) are completely coordinated through different strategies or algorithms. These strategies employ strict rules to govern the behavior of the individual robots. The second approach employs randomized algorithms; these algorithms minimize explicit control of the robot’s actions and instead behave in a directed random fashion. Generally, the first approach tends to accomplish their goals quicker than the randomized approach. However, the randomized approach is simpler and easier to design and more immune for failure of one or more of its agents. The first approach, where strict algorithms are employed, is used in this paper. The work presented in this paper is an extension of the work presented in [4]. The main difference is that the proposed technique, in this paper, employs completely different search techniques as compared to [4]. Moreover, it is performed in more realistic indoor environments. Searching of an unknown environment is much related to the art gallery problem, where the problem is to find the positions for static robots to fully cover an unknown area [5]. Several researchers investigated the problem of searching for targets in a given area. For example Isler et al. [6] triangulated the search space, abstracted it into a graph and also suggested using stationary robots to reduce more complex environments to simple polygons. In [7], Hollinger et al., examined the problem of locating a mobile, non-adversarial target in an indoor environment using multiple robots. He assumes a known environment and chooses robot paths most likely to intersect with the path taken by the target. This technique is referred as Multi-robot Efficient Search Path Planning (MESPP).

Other authors have proposed different approaches to model probabilistic coordinated search problem. In [8], Adler et al. investigated the expected capture time to pursuit-evasion by examining the hunter and rabbit problem. They were interested in the number of rounds for the hunter to catch the rabbit. In [9], Ferris et al. suggest using Gaussian Processes to estimate the position of a moving target that propagates wireless signal strength. They depend on the strength and the direction of the wireless signal to estimate position with the aid of particle filter.

In summary, the problem of robot search has been investigated by many authors. In most approaches, robots are coordinated to find partially observable targets. In other words, there are some indications or signs that help the robots to find or capture their targets. For example, these signs might be wireless signals propagated by the targets. Another example might include the case when it is assumed that the targets move against the robots to avoid capturing by the robots. In this paper, we investigate the problem of multi-robot search in an unknown indoor environment. The aim is to find a stationary target as fast as possible. There is no direct or indirect communications between the target and the robots. The target is expected to be located at any point in the environment. There are no indications or signs to guide the robots to the target. Also, the environment is not known to the robots.

As the assumption of no pre-information is existed about the target location and the environment before the mission starts, the mission would be seen as an exploration task. The aim is to proceed in exploring until the target is detected and not to fully explore the environment.

2. Search Techniques

Mobile robots need a map to effectively navigate in their environment. In search missions where targets are fixed, such as the work in this paper, the map is important to avoid searching the same area more than once. It is also beneficial to guide the robots towards the yet unsearched areas. The ability of mobile robots to autonomously move in an unknown environment to gather the sensory information required to build a map is called autonomous exploration. As the robots move to unexplored new areas, these areas are then included in the map. The main challenge in autonomous exploration is how robots plan the order to visit the remaining unexplored areas while minimizing the total elapsed time [10, 11].

Most of the published multi-robot exploration techniques are based on the use of “frontier cells”, e.g. [12-14]. The concept of frontier cells was introduced by Yamauchi [15]. He stated that “To gain the most new information about the world, move to the boundary between open space and uncharted territory”. He presented a technique to build grid maps by which the environment is represented by evenly-spaced grids (2D map). Each grid cell has a numeric value that indicates the presence of an obstacle in the corresponding region of the environment. The robots exchange information about the map that is continuously updated whenever new information sets come through sensors. To discover the environment, each robot moves towards the closest frontier cell. A frontier cell is a free cell that lies on the edge between explored and unexplored area. When a robot is directed to such a cell, it is expected that it gain information about the unexplored area when it gets there. Because a map may contain more than one unexplored area, the main challenge is how to plan the exploration mission by choosing the most appropriate frontier cell. When more than one robot is involved in the exploration, it is important to avoid the possibility of more than one is exploring the same cell.

Each robot builds a grid-based map; this map includes the data about the free, occupied, and yet unexplored cells. When one of the robots gets a new patch of data by its sensors, it would be redistributed to the other robots. This data may include the status of the cell, free or occupied, in addition to the cell coordination. Each robot uses its own map to find the locations of the frontier cells which are on the border line between explored and unexplored areas. The two search techniques under consideration are presented in the following two subsections.

2.1. Standard Frontier-based Search Technique

In this paper, standard frontier-based exploration [15] is used as a search technique as follows. The environment E can be represented as

(1)

where

E: Set of all environment cells.

C: Set of environment cells that are explored by any robot and found to be free.

U: Set of environment cells that are not yet explored by any robot.

O: Set of environment cells that are explored by any robot and found to be occupied.

The standard frontier-based technique can be formulated as follows

1. Integrate the current sensor measurement and update the map.

2. Determine the set of frontier cells F by checking for every cell in the candidate set C if it is adjacent to, at least, one unknown cell:

3. Use the Breath-First algorithm to find the closest reachable frontier cell fg. This cell is the goal cell for the robot.

4. The robot plan the path to reach the goal cell fg, and it starts moving toward it.

5. Once the robot reaches it goal cell fg, the cycle is repeated from step 1 again.

2.2. Reduced Overlap Frontier Search

In this technique, to reduce the potential overlap, the robot chooses the closest frontier cell but not within a sensor range of any other robots. This leads to spread the robots over the environment in order to decrease the search time. This technique can be formulated as follows:

1. Integrate the current sensor measurement and update the map.

2. Determine the set of frontier cells F by checking for every cell in the candidate set C if it is adjacent to, at least, one unknown cell:

3. Use the Breath-First algorithm to find the closest reachable frontier cell fc. If fc is not in the sensor range of any other robot, then this fc is the goal cell fg. Otherwise if fc is in the sensor range of any other robot, the robot continues with Breath-First algorithm until it finds a frontier cell not within the sensor range of any other robot.

4. The robot plan the path to reach the goal cell fg, and it starts moving toward it.

5. Once the robot reaches it goal cell fg, the cycle is repeated from step 1 again.

3. Experimentation and Results

The two search techniques presented in the previous sections were tested with different environments as shown in Figure 1. As seen in Figure 1, there are three testing environments (floorplans) through which the robots maneuver. There are the home floorplan 1, office floorplan 2, and hotel or apartment floorplan 3 [16]. Each environment is presented as 100-by-100 cells. These environments were selected to signify different indoor settings; to obtain general conclusions.

Robots are represented in the simulation environment (Netlogo 5.0.4 [17]) by black small turtles that can move from a cell centre to an adjacent cell centre. Each robot senses in eight directions (every 45° about the robot’s center). These directions are identical to the standard directions of a compass (N, NW, W, SW, S, SE, E, NE). Each robot can detect the presence of obstacles within its sensing range which is set to 20 cells. The search task is finished immediately when one of the robots finds the target. The search process is evaluated through recording the time required to find the target. Finding multiple targets is kept for future work.

For each experiment run, the target is randomly located in the environment. The experimentation started with home floorplan environment shown in Figure 1 (a) and with the standard frontier-based search technique presented in subsection 2.1. At first one robot is deployed in the environment and it starts searching for the target until it finds it. The search time is recorded. The same experiment is repeated 20 times, the time for each experiment is recorded. Same procedure is repeated with two, three, four, five and six robots. The same procedure is repeated with the reduced overlap frontier-based search technique presented in subsection 2.2. Finally, the whole above mentioned procedure is repeated with the office floorplan shown in figure 1 (b) and with hotel floorplan shown in figure 1(c). The results of these experiments are shown in Figure 2. The deployment of six robots in this search practice is justified with the assumption that no significant results are obtained if more robots were considered in the given settings. Knowing that the starting position is a very important issue, in this proposed work the robots were positioned to start from the same lower left environment corner. This is justified in most former applications [11, 12, 15]. For example, when the search task is required to find humans, in a hotel or a house, under difficult conditions such as fire or gas leak, it would be more practical to deploy the robots from a window or a door rather than wasting valuable time distributing them to different environment locations.

Figure 1. Environment Floorplans: (a) home floorplan 1, (b) office floorplan 2, and (c) hotel/apartment complex floorplan 3

Figure 2, illustrates a search time comparison between the Reduced Overlap Frontier-based Search technique and the Standard Frontier-based Search technique. It can be concluded that using the former method optimizes searching time as compared to the latter. This experiment was repeated as many as 20 times. The relatively high standard deviation values obtained may be assumed due to the realization of different search time in each trial.

Figure 2. (a): Search time (steps) versus number of robots for the home floorplan environment shown in Figure 1 (a) (b): Search time (steps) versus number of robots for the office floorplan environment shown in Figure 1 (b) (c): Search time (steps) versus number of robots for the hotel floorplan environment shown in Figure 1 (c)

4. Conclusions & Future Work

In this paper, the problem of finding a target by multiple robots in an unknown indoor environment is investigated. It is argued that the search problem can be dealt with as an exploration problem where the idea is to keep on exploring the environment until the target is detected. The searching robots exchange data and coordinate their actions during the search mission. Two search techniques are evaluated to solve the problem of target search. In the first technique each robot is directed to the closest frontier cell. That means that more than one robot might go to the same area. This leads to increase the overlap. In the second technique, each robot is directed to the closest frontier that is not in the sensor range of any other robot. This led to significant reduction in the overlap. As a conclusion, the second technique led to more promising results as compared to the first. Such a result is reasonable since as in exploration tasks, the overlap among robots should be taken into account in the search missions.

Figure 3 shows different simulation snapshots for the robots trajectories in addition to the searched area. The searched area is in white and the black circle is the target. Figure 3 (a), (c), & (e) shows simulation snapshots when searching with the first technique: Standard frontier-based search with 3, 4 & 5 robots respectively, while Figure 3 (b), (d), & (f) shows simulation snapshots when searching with the second technique: Reduced-overlap frontier-based search with 3, 4 & 5 robots respectively. Clearly, searching with the second technique leads to a better distribution of the robots which means less overlap and consequently, less search time. On the other hand, the trajectories of the first technique are not effectively distributed and two or more robots are expected to try visiting the same cell at the same time, this leads to more robot collisions and larger search time.

Figure 3. (a), (c), & (e) simulation snapshots with robots’ trajectories when searching with the Standard frontier-based search technique with 3, 4 & 5 robots respectively; (b), (d), & (f) simulation snapshots with robots’ trajectories when searching with the Reduced-overlap frontier-based search with 3, 4 & 5 robots respectively

As a future work, a potential field of research is to investigate the use of Voronoi Graph to model the environment and simultaneously using this model to guide the robots during their mission to find the targets [18-21].