1 Introduction

Multi-robot systems (MRS) which composed of multiple cheap robots are preferred instead of single robot systems which composed of an expensive robot. There are many applications for MRS, for example, surveillance, contamination cleanup, search and exploration, etc. In these applications, coordinated strategy takes a key role to make all teammate robots working cooperatively.

There are a lot of results to deal with the coordination of MRS, however, most of the results suffered from computational expensive problem when the MRS size is large [1, 2]. On the other hand, the coordination across a group of human being conducting a search and exploration in an environment generally is realized by a series of fuzzy rules. For example, in a searching and removing mines mission conducted by a team of sappers, all sappers enter a building from a common entrance. Then, the team is divided into two sub-teams. The operation behaviors are that one sub-team moves to left, the other moves to right; if one of them arrived at the border then they turn exploring direction; and so on. Typically, a series of zigzag trajectories are realized by the sappers. The goal is realized with little computing or without any hard computation during the exploring discourse. Moreover, no exact map of the environment is known before the exploration.

Inspired by the above fact, predicate based reasoning in artificial intelligence is utilized to realize coordination of multi-robot systems. To the best of our knowledge, this is the first paper that discusses coordination by integrating predicate reasoning and reactive behaviors. This paper is organized as follows. The next section reviews the related work. Section 3 presents preliminary for discussing our approach. Section 4 discusses exploration coordination from aspects of MRS partitioning, exploration initialization, and predicate reasoning. Section 5 presents reactive behaviors for obstacle avoidance and integration of all functions. Section 6 presents simulation results to validate our coordinated algorithm. And Sect. 7 concluded the paper.

2 Related work

Cooperative exploration for unknown environments involves dispersion of all robots over the environment, task assignments to robots, and cooperation among robots. In unknown environment exploration, the last one deals with task balance among robots. These roles are realized by coordinated algorithms.

Zigzag trajectory is an efficient way for robots to explore unknown environments [3, 4]. The work [3] presented a boustrophedon cellular decomposition strategy for known space coverage by a robot. The coverage is reduced to finding an exhaustive path on a graph that represents the adjacency relationships of the cells. Moreover, in the complete coverage path planning, a set of multi-robot coverage algorithms is presented that minimize repeat coverage [4]. However, the results have not considered task balance and cooperation among robots.

Besides being utilized by mobile robots, zigzag trajectory was used to realize coverage for unmanned aerial vehicles (UAVs) [5, 6]. Both the approaches partitioned the environment into a number of subregions, however, the former is based on a purpose of minimizing energy consumption and the latter is based on mission performance of the individual UAVs and the individual subregions widths. The subregions are assigned to different sorties of a vehicle [5] and different vehicles of the multi-vehicle system [6].

Up to now, the coordination for multi-robot systems have been realized primarily by market economy based approach and its improvements [1, 2, 7, 8]. The core of the approach is that the individual robots select navigation goals from frontier cells by maximizing the individual benefits (utility-cost). The method realizes negotiation among robots by an auction mechanism. For example, repeated auction algorithm [2] accounted for tasks won from an auctioneer before bidding on subsequent tasks from the same auctioneer. A shortage encountered in auction based algorithm is computational cost growing with the number of tasks. In order to overcome the shortage, the environment was represented by topological map and a sequential simultaneous auction protocol was proposed in the coordination [7]. In the market economy framework, the performance of MRS was improved in the case that the environment or tasks was known or partially known [8]. The purpose of this paper is to present a simple yet effective coordinated strategy for unknown environment exploration.

In addition, fuzzy logic based utility functions were used to allocate tasks through a limited lookahead control methodology from supervisory control theory of discrete event systems [9]. A decision-theoretic approach implemented coordination among robots by trading off utility and cost [10]. In the approach, dispersion of robots over the environment was realized by reducing utility value when a potential target approximating assigned targets. The result presented in [11] implemented a global dispersion by a three-level optimization based coordinated algorithm. The three levels from bottom to top functions path planning, task assignment, and global optimization, respectively. Two objectives, MINIVAR and MINWTV which are used to minimizing the variances of path costs over all robots and the variance of the waiting time of every region in workspace, respectively, are proposed. A comparative study of typical methods from aspects of exploration time and mapping quality for unknown environments was presented [12]. The predicate reasoning is the top level in the proposed algorithm.

Different with the above results, the proposed approach utilizes a new kind of zigzag trajectory to realize exploration. Both the dispersion of all robots over the environment and task assignments are realized by initialization at the beginning of exploration. Subsequently, as a robot finished its task, the dispersion and task assignment are realized by predicate based reasoning.

In addition, the trajectory utilized in this paper combined rendezvous and classical zigzag trajectory. Rendezvous technique was used to share information among mobile robots. For example, [13] address the problem of how two robots that cannot communicate with each other over long distances can meet if they start exploring at different unknown locations in an unknown environment.

The word behavior has been used to describe the robot actions which include sense, control, and communication in the literatures [11, 14,15,16,17]. Also, it was used in supervisory control of discrete event systems and robot formation [18, 19]. Specifically, the word has been used to describe the movement actions [11]. Other representative results include [19,20,21,22,23,24,25,26,27]. In this paper, the word is used to describe obstacle avoidance actions. The proposed coordinate approach is a kind of qualitative ones which need no quantitative calculation.

3 Preliminary

Frontier cell based approach [22] is a foundation for a few of coordinated approaches, for example, the auction based approach, decision-theoretic approach, et al. However, the dispersion of all robots coordinated by the above approaches over an environment are local [11]. The result presented in [15] improved time efficiency of the exploration discourse by reducing the times that each robot takes part in task assignments. This resulted in the trajectories of robots are smoother than those of robots coordinated by traditional auction based approaches.

The exploration goal of MRS discussed in this paper is not to visit all available locations in the environment, but is to scan all available locations in a minimal time. According to the taxonomy proposed in [18, 23], all exploration tasks discussed in this paper belong to the class of single robot tasks. In addition, there is no inter-dependence between tasks, and any part of the environment can be explored by any teammate robot and modelled as a local occupancy grid map by a simultaneous localization and mapping [28, 29] module embedded in each robot.

In the proposed approach, it is assumed that all robots have no knowledge about the environment. As the exploration discourse carrying out, the information about the relative positions among robots, and information about explored part of environment become available. Also, all robots explore environment through a kind of zigzag trajectory movements. Figure 1 shows the zigzag trajectories of a robot \(r_{i}\in {{\varvec{R}}}\), where \({{\varvec{R}}}= \{r_{1}, {\ldots }, r_{n}\}\) is the MRS considered in this paper. As shown in the figure, there are horizontal and vertical line segments. For convenience, three terms to describe the trajectories are given in the following.

Fig. 1
figure 1

Sketch of zigzag exploring trajectory

Full size image

The first is an auxiliary exploring direction which is defined as any trajectory direction represented by longer line segments, and the second is a primary exploring direction which is defined as any trajectory direction represented by shorter line segment. For the scenarios shown in Fig. 1a and b, the auxiliary exploring directions are horizontal (leftward and rightwards) and vertical (upwards and downwards), respectively, and the primary exploring direction is upwards and rightwards, respectively. It is also named the robot is exploring upwards/rightwards through zigzag trajectory. For simplicity, only upwards, downwards, leftward, and rightwards are considered for auxiliary exploring direction and primary exploring direction, respectively, in the following.

The last one is the width of zigzag trajectory that is defined as the distance between two adjacent trajectories of auxiliary exploring directions. In the case of no overlapping between two adjacent strips covered, the width of zigzag trajectory is \(2d_{i}\), where \(d_{i}\) is the sensing range of the corresponding robot. In the proposed approach, the width of zigzag trajectory is fixed to \(2d_{i}\). After initialization, the primary exploring directions and each trajectory length of each auxiliary exploring direction is determined dynamically according reasoning described in the next section.

4 Coordination based on predicate reasoning

4.1 Partitioning MRS

A moderate scale MRS is considered in this paper. Nevertheless, it is difficult to consider poses of all other teammate robots simultaneously when deciding primary exploring direction for a teammate robot. To overcome the limitation, the set of MRS is partitioned into a few of subsets of robots. Then the coordination is considered between subsets. For the reason of simplicity, the number of subsets is restricted to be less than or equal to three. Since the specific shape of trajectory which will be used in the following, sizes of the subsets should be as even number as possible. When the team size is two, no partitioning is needed, when \(\hbox {n}= 3\), the MRS is partitioned into two subsets \(\{r_{1}\), \(r_{2}\}\) and \(\{r_{3}\}\). The partitioning results for MRS whose size is less than or equals 10 are shown in Table 1.

Table 1 Exemplify of MRS partitioning
Full size table
Fig. 2
figure 2

Initialization of a MRS with team size is four

Full size image

4.2 Initialization of exploration discourse

It is assumed that all robots start their exploration discourses from a common initial location. Also, it is a default that all robots explore environment through zigzag trajectories with vertical auxiliary directions and horizontal primary directions. To start with, the initialization strategy for a MRS with team size four will be discussed in an obstacle free environment. It is a foundation of our further results. As shown in Table 1, the MRS is partitioned into \(\{r_{1}\), \(r_{2}\}\), and \(\{r_{3}\), \(r_{4}\}\). If all robots cannot detect environment boundary from initial locations, then the primary exploring directions of the two subsets are leftward and rightwards, respectively. If the robots can detect environment boundary from the initial locations, then the primary exploring directions are rightwards and most rightwards, respectively. Figure 2 demonstrated the initialization of exploration discourse of the four robots. The strategy realizes dispersion of all robots over the environment. The behaviors of robots under a case that right boundary can be detected at initial locations is a flip of Fig. 2b. In addition, behaviors of under cases that upper and down boundaries can be detect are rotations of the trajectories shown in Fig. 2b, respectively. For the reason of simplicity, they are not shown in this paper.

In order to balance tasks between the two subsets, robots \(\{r_{3}\), \(r_{4}\}\) move to the most right, then they begin to explore from right to left, as shown in Fig. 2b. It is obvious that all the four robots finish their exploring tasks at the same time when the two subsets robots meeting together in the middle of the environment. However, in the scenario shown in Fig. 2a, robots \(\{r_{3}\), \(r_{4}\}\) will finish their tasks before \(\{r_{1}\), \(r_{2}\}\). So \(\{r_{3}\), \(r_{4}\}\) need be assigned tasks. This is the concern of next subsection.

For cases that \(n <4\), for example, \(n= 2\), the corresponding behaviors are given by the trajectories label by \(\{r_{1}\), \(r_{2}\}\) in Fig. 2. Similar for the case the team size is three.

Table 2 Event and state meanings
Full size table

A remained issue is to extend the above results to adapt to cases that the team size is more than four, i.e., \(n >4\). For the case shown in Fig. 2a, the MRS is partitioned into three subsets. Their primary exploring directions are leftward, rightwards and most rightwards, respectively. For the case shown in Fig. 2b, only two subsets are needed. Therefore, the concept of buddy system [27] is adopted, i.e., two \(r_{i}\) and \(r_{j}\) are combined into a compound robot \(r_{ij}\), where \(j = \hbox {mod}(i,4) (i= 5, \ldots , n)\). A compound robot explores the environment as if a single robot behaves, and two compound robots cooperatively explore the environment by the way of two original robots. In each compound robot, the two original robots are kept to a fixed form by formation control technology [17]. An important difference between an original robot and a compound robot is that the width of zigzag trajectories is \(4d_{i}\) instead of \(2d_{i}\). Moreover, a compound robot maybe consists of three or more original robots. So the algorithm proposed has no restriction on the robot team size.

4.3 Predicate based reasoning for coordination

The exploring directions determined previously have a property that if robots of two subsets are exploring a common unknown subregion of the environment, then the auxiliary exploring directions of robots belonging to the two subsets must be parallel to each other. A robot keep its primary exploring direction and auxiliary exploring directions of zigzag exploration trajectories except the subregion has been scanned. Then, all robots belonged to the two subsets will be assigned new tasks.

Predicate based reasoning [30] was utilized to realize coordination among robots. In order to simplify the coordination, the auxiliary exploring directions were used to explore the unknown environment, and the primary exploring directions were used to assign tasks to robots and to implement cooperative exploration among robots. So, the coordination is considered from a one-dimensional point of view although the environment is two dimensional. The following predicate calculus were established to realize reasoning about the primary exploring direction for a robot \(r_{i}\) which maybe either a robot or a compound robot.

$$\begin{aligned}&(\forall r_i )(\exists r_j )Identical(r_i ,r_j ,current\_dir_i ,current\_dir_j )\nonumber \\&\quad \wedge \, Sensed(r_j ,unknown,current\_dir_j )\nonumber \\&\quad \Rightarrow Keep(r_i ,current\_dir_i ) \end{aligned}$$
(1)

where \(Identical(r_{i}, r_{j}, current\_dir_{i}, current\_dir_{j})\) mean that robots \(r_{i}\) and \( r_{j}\) have the same primary exploring direction, \({Sensed}(r_{j}, unknown, current\_dir_{j})\) means that \(r_{j}\) sensed unknown region along current direction \({current\_dir}_{j}\), and \({Keep}(r_{i}, current\_dir_{i})\) means that \(r_{i}\) keeps current direction.

$$\begin{aligned}&(\forall r_i )(\forall r_j )Identical(r_i ,r_j ,current\_dir_i ,current\_dir_j )\nonumber \\&\quad \wedge \, (\lnot Sensed(r_j ,unknown,current\_dir_j )\nonumber \\&\quad \wedge Near(r_{i,} r_j )\vee Sensed(r_j ,boundary,current\_dir_j ))\nonumber \\&\quad \Rightarrow Change(r_i ,current\_dir_i ) \end{aligned}$$
(2)

where \({Near}(r_{i}, r_{j})\) mean that the distance between \(r_{i}\) and \( r_{j}\) is less than or equal to the width of zigzag trajectory, \({Change}(r_{i}, { current\_dir}_{i})\) means that \(r_{i}\) changed direction to \({ current\_dir}_{i}\). Since only two primary exploring directions are considered, the calculus mean that \(r_{i}\) move to the opposite boundary to continue its exploration. If two robots met, one of them need to change its direction. The corresponding calculus is

$$\begin{aligned}&(\forall r_i )(\forall r_j )\lnot Identical(r_i ,r_j ,current\_dir_i ,current\_dir_j )\nonumber \\&\quad \wedge \, Near(r_i ,r_j )\nonumber \\&\quad \Rightarrow Change(r_i ,current\_dir_i )\nonumber \\&\quad \vee \, Change(r_j ,current\_dir_j ) \end{aligned}$$
(3)
$$\begin{aligned}&\quad (\exists r_i )(\forall r_j )Identical(r_i ,r_j ,current\_dir_i ,current\_dir_j )\nonumber \\&\quad \wedge \lnot Near(r_i ,r_j )\wedge \nonumber \\&\quad Sensed(r_j ,unknown,current\_dir_j )\nonumber \\&\quad \wedge \lnot Sensed(r_j ,boundary,current\_dir_j )\nonumber \\&\quad \Rightarrow Keep(r_i ,current\_dir_i )\nonumber \\&\quad \wedge Until(Sensed(r_i ,boundary,current\_dir_i )) \end{aligned}$$
(4)

where \(Until(Sensed(r_i ,boundary,current\_direction))\) is a second predicate calculus which means keep current exploring direction until the robot sensed the opposite boundary of the environment.

Predicates (1) and (4) are used to realize to keep primary exploring direction, and (2) and (3) are used to change primary exploring direction.

5 Reactive behaviors for obstacle avoidance

The coordination discussed previously is only suitable for obstacle free environments. It is desirable that the results are suitable for sparsely occupied environments. Therefore, a few of events are defined to deal with appearances of different objects. The events are listed in Table 2. These events are used to fire different behaviors to avoid obstacles, for example, the behavior of passing through a convex obstacle was called when event \(\alpha _{1}\) occurred. For each occurrence of an event, a corresponding reactive behavior to deal with the event is called. These behaviors are listed in Table 2 too.

Besides sensing different objects, an event \(\alpha _{4}\) is defined to represent no obstacle is sensed by a robot. then it realizes exploration by the behavior described in previous section.

To adapt formal representation of the above reactive behavior, a set of exploring modes corresponding to different events are defined. They are named as states and are represented by \({{\varvec{S}}}= \{s_{1},{\ldots },s_{4}\}\). State \(s_{1}\) is used to represents the trajectory after a convex object is scanned. If a convex object is scanned when a robot is on its primary exploring direction, then the robot moves along edge of the object anticlockwise. As soon as a distance of passing round trajectory curve on the primary direction is \(2d_{i}\), the robot turns to its auxiliary exploring direction and continues exploring; elseif the object is scanned when a robot is on its auxiliary direction, then the robot will restore its auxiliary direction exploration after passing round a part of the object and reached the opposite location of the objected. If a concave object is scanned and the robot is located in front of entry of the object, then no matter the robot is on its primary or auxiliary exploring directions, the robot enters the inner of the object and explores along inner edge anticlockwise until the robot return to the entry. After scanned the inner of the object, the object is treated as a convex. Else, if the concave object located on the side of primary or auxiliary exploring directions, then list the frontier cell of the object on the unfinished job list [22]. It is used to share environment information across robots, and is updated by all robots.

Fig. 3
figure 3

Desired behavior of a robot \(r_{i}\)

Full size image
Fig. 4
figure 4

Comparison of exploration performance for different approaches in a blank environment

Full size image

A state \(s_{i}(i= 1,\ldots , 4)\) of a robot can be transferred to the other state \(s_{j}({j \ne i})\) or stay at \(s_{i}\) after an event \({\alpha }_{i}(i = 1, \ldots , 4)\) happened. So, we can describe above relation between states and events by an automaton from computer science. Based on the results of supervisory control of discrete event systems [19], the desired behavior of a robot can be described by the finite state machine shown in Fig. 3. It is straightforward that the language generated by the automaton shown in the figure is prefix closed. The sensing results of a robot are not controllable, so all the events listed in Table 2 are uncontrollable. Since no event is prevented from occurring at each state, according to the definition of language controllability, the language generated by the automaton is controllable. So there exists a supervisor to realize the behavior.

6 Simulations

The proposed predicated reasoning based approach (PRBA) is compared with repeated auction algorithm (RAA) [2], decision-theoretic approach (DTA) [10], and supervisory control based coordination (SCC) [15] from time efficiency in Matlab 7.1 environment. The simulations are executed on a personal computer which has an Intel®  \(\hbox {Core}^\mathrm{TM}\) i7 2.93 GHz processor and 8 GB RAM.

It is assumed that the sensing radius of all robots are 4 m, and the moving speed of all robots is 0.1 m/s. All robots located at a common position initially. The initial locations are randomly selected from unoccupied cells over a 100 m \(\times \) 100 m environment. The robot team size is a variable that ranges from 2 to 6. For each team size, the simulations are conducted 100 runs. When the team size is bigger than 5, time efficiency improvement of the corresponding MRSs are hard to differentiate. Exploration time and idle time with different team sizes for the obstacle free environment are shown in Fig. 4, respectively. It is obvious from the results shown in Fig. 4a that the proposed algorithm improved exploration efficiency over the other approaches. The improvements are resulted from minimizing the idle time for each teammate, as shown in Fig. 4b. It is concluded from the simulations that the exploration time for each run is determined by the initial location of all robots. For example, if the robots do not locate nearby boundaries initially, then their exploring efficiency are identical before sensing a boundary. Thus, the exploration for a MRS that a distance from its initial location to boundary is an integral multiple of zigzag width is the most efficient.

Fig. 5
figure 5

A sparsely occupied environment and its corresponding exploring times

Full size image

In order to validate the proposed approach for sparsely occupied environments, a simulated environment shown in Fig. 5a is considered. Figure 5b displays means of exploration times for different team sizes for the four algorithms. The exploration times are related to the initial locations of robots as discussed above. Moreover, if robots located initially nearby obstacles on the environment, then the corresponding explorations are time inefficient. The reason is that round a obstacle need more time than passing by the obstacle. Figure 6 shows the distribution of initial locations for all robots in our simulations.

Fig. 6
figure 6

Initial positions distribution of MRS

Full size image

7 Discussions and conclusions

In the proposed approach, the dispersion of all robots over the environment is realized by initialization of exploration discourse, meanwhile task assignments are dealt with. As a robot finished its exploration task, dispersion and task assignment is dealt with by predicates based reasoning. The cooperation between two robots that have the same primary direction is realized by exploring unknown environment from opposite direction. So a balanced and sustained exploration for MRS is obtained. In addition, a perfect communication is necessary only in the initialization and reasoning period. No matter how the robot team size is, the MRS is divided into at most three subsets of robots to explore unknown environments.

A novel coordinated approach for MRS exploring unknown environment has been proposed in this paper. The approach consists of three parts. The first part is the partitioning of MRS, the second part is initialization of exploration discourse for each robot, and the final part is predicate reasoning. To avoid obstacles, a few of reactive behaviors are integrated to lower level of hierarchical architecture of each robot. The simulation results verified the improvement of exploration efficiency of the proposed approach over traditional approaches. However, the result is suitable for obstacle free and sparsely occupied environments. A future work is making the result to suitable for more occupied and structured environments. In practice, uncertainty exists in sensor data and locations for all robots. So the other future work is making the coordinated strategy robust to uncertainty in sensing and acting.