Learning and relearning of target decision strategies in continuous coordinated cleaning tasks with shallow coordination 1

Abstract

We propose a method of autonomous learning of target decision strategies for coordination in the continuous cleaning domain. With ongoing advances in computer and sensor technologies, we can expect robot applications for covering large areas that often require coordinated/cooperative activities by multiple robots. We focus on the cleaning tasks by multiple robots or by agents which are programs to control the robots in this paper. We assumed situations where agents did not directly exchange deep and complicated internal information and reasoning results such as plans, strategies and long-term targets for their sophisticated coordinated activities, but rather exchanged superficial information such as the locations of other agents (using the equipment deployed) for their shallow coordination and individually learned appropriate strategies by observing how much dirt/dust had been vacuumed up in multi-agent system environments. We will first discuss the preliminary method of improving the coordinated activities by autonomously learning to select cleaning strategies to determine which targets to move to clear them. Although we could have improved the efficiency of cleaning, we observed a phenomenon where performance degraded if agents continued to learn strategies. This is because so many agents overly selected the same strategy (over-selection) by using autonomous learning. In addition, the preliminary method assumed information given about which regions in the environment easily became dirty. Thus, we propose a method that was extended by incorporating the preliminary method with (1) environmental learning to identify which places were likely to be dirty and (2) autonomous relearning through self-monitoring the amount of vacuumed dirt to avoid strategies from being over-selected. We experimentally evaluated the proposed method by comparing its performance with those obtained by the regimes of agents with a single strategy and obtained with the preliminary method. The experimental results revealed that the proposed method enabled agents to select target decision strategies and, if necessary, to abandon the current strategies from their own perspectives, resulting in appropriate combinations of multiple strategies. We also found that environmental learning on dirt accumulation was effectively learned.

Keywords

Multi-robot sweeping coordination learning robot patrolling

1. Introduction

Recent advances in robotics and computer technology have enabled many robot applications in a variety of real-world environments. Some of them have worked in places and situations that are difficult for humans to work in, such as those in disaster relief, demining, nuclear plant searches, and interplanetary exploration (e.g., [8,20]), while others have fulfilled daily or commonplace functions such as cleaning, security patrols and egg collection robotics (e.g. [15,22,23]). Robots require different capabilities depending on their tasks. For example, robots for demining must be capable of searching large areas without omissions, and those for cleaning or security must maintain cleanliness/safety by continuously moving around the specified areas. Cooperation by multiple robots is required in such applications because a single robot can only cover a limited area due to speed and movement restrictions and battery capacity. Even if one or a few robots stopped due to failure, multi-robots could continue to operate by compensating for the stopped robots. We aimed at cleaning and security patrolling by multiple autonomous robots in this study.

Robots have to visit environments at different frequencies in these applications. For example, cleaning (security) robots have to frequently visit regions that easily accumulate dust (regions that should be guarded at high level of security). Furthermore, robots need to be recharged periodically to ensure continuous performance due to finite battery capacity. The optimal method for coordinated activities by multiple robots for cleaning/patrolling is not trivial in such situations. Therefore, studies on agents, which are control software residing in individual robots to navigate them in environments with appropriate strategies by taking into account the amount of remaining battery life and the locations of other robots, are crucial to maximize their efforts in multiple robot contexts.

There have been a number of studies on agents in patrolling problems using single or multiple robots. Kurabayashi et al. [15] proposed a centralized off-line method in which a single server generated the entire route for a sweeping task. However, centralized control often incurs high computational costs according to the number of robots. Chevaleyre [6] formalized the patrolling problem as the traveling salesman problem by using multiple agents, but did not take into account the fact that agents visit the locations at different frequencies. Elor and Bruckstein [10] proposed a segmentation method of covering a region by integrating ant pheromone and balloon models. Ahmadi and Stone [3] also proposed a method that segmented the region of responsibility for individual agents while exchanging boundary information and this accounted for different event generation cycles. However, segmentation by only interacting with neighboring agents results in slow convergence, especially in large systems.

Agents move around in a shared region without segmentation in our proposed method, unlike those in these studies but with different target decision strategies to determine the next places that should be cleaned, thereby coordinating activities. Locations where dirt tends to accumulate differ in individual environments and are affected by the shape of the environments, the places and the numbers of people working during the day, and the number of obstacles. This makes it impossible to determine the appropriate combination of agent strategies in the design phase of the system. Agents in our approach try out different strategies and individually identify the most effective ones by reinforcement learning.

Another feature of our approach is that we do not assume deep coordination in which agents acquire (or estimate) internal reasoning information like long- and short-term plans of actions in other agents, analyze them, or determine appropriate local plans and actions, but assume shallow coordination meaning that agents within our context only receive or exchange superficial data such as their past and current locations and do not perform complicated reasoning about others. Since they only have a few resources including CPU with limited performance, limited amounts of memory and limited battery capabilities, we should avoid sophisticated coordination. Furthermore, it is often quite difficult to maintain wireless communication accuracy, and there is a trade-off between accuracy and power consumption. Small interruptions and noise (resulting in incorrect information) in wireless communications make sophisticated coordination impossible. This assumption of shallow coordination also fits environments where agents cannot directly communicate with one another but can obtain other’s locations via broadcasting with on-site equipment (e.g., infrared emitters on the ceiling as will be explained in the next section). This enables agents to significantly conserve battery life.

The main contributions of this paper are three-fold. First, we propose and discuss a method of reinforcement learning to autonomously identify appropriate strategies from their local viewpoints. Although we already discussed and proposed strategy learning in our previous paper [25] along the lines of the purpose discussed above, we carried out more thorough additional experiments to obtain more detailed results. This will be called the preliminary method after this. During the experiments using the preliminary method for evaluation, we found that agents in certain environments overly selected the same strategy (over-selection), resulting in the gradual reduction of the entire performance over time. Second, we therefore added self-monitoring functions with which agents could individually find degraded performance. Then, if they found the degradation, they could discard the current learning results to escape from situations of over-selection. Finally, we incorporated environmental learning to identify which places were easy to make dirty into the preliminary method for a wider range of applications.

The rest of this paper is organized as follows. Section 3 describes the model of agents and the problem domain and then clarifies the issues mentioned above. We explain a number of planning stages in which they select targets and generate the paths to them in Section 4. Section 5 first presents the preliminary method in which agents individually select one from given target selection strategies to coordinate them based on the learned results. Then, we propose a method that incorporates self-monitoring and environmental learning with the proposed method of learning. Finally, we report three experimental results. The first experiment demonstrated that agents using our preliminary method could achieve better performance in terms of minimizing the cumulative existence of dirt in an environment by a comparison with uniform regimes in which all agents adopted the same strategies. The second experiment revealed that agents with the proposed method could avoid degraded performance due to over-selection. Agents in the third experiment could adaptively select appropriate target selection strategies by adding autonomous learning of their environments even if they did not have prior knowledge about which places were easy to make dirty.

2. Related work

There have been a number of studies on cleaning and patrolling problems using single or multiple agents (robots). Ahmadi and Stone [2] formalized the problem of continuous area sweeping as a general form for a number of applications such as demining, floor cleaning, and security patrols by robots. They then also proposed a method in which an agent moved around in search of events that occurred with different probabilities. However, that study did not address collaborative movements with multiple agents. Kurabayashi et al. [15] proposed a centralized off-line method in which a single server generated the entire route for a sweeping task. The route was then divided into fragments and allocated to individual agents to minimize the working time. Stranders et al. [22] also developed a single-agent divide-and-conquer method for a continuous patrol by a team of agents. Although these approaches could generate near-optimal solutions, such centralized approaches incur high computational costs if the number of agents and/or the size of areas are large. More importantly, the failure of central components results in the standstill of all agents.

The patrolling problem can be formalized from a more theoretical perspective. For example, Chevaleyre [6] formalized the patrolling problem as a traveling salesman problem with multiple agents and then compared the number of cyclic routes and route division methods from the viewpoint of a minimal route length. Elmaliach et al. [9] proposed an algorithm that found the shortest Hamiltoniam cycle in grids that were used to patrol areas and to evenly spread agents there. However, it is costly to calculate appropriate paths in large and real-world environments. In addition, unlike ours, these studies did not consider the case of agents visiting locations at required and different frequencies.

We can consider two approaches to achieving coordinated and collaborative tasks from the multi-agent perspective. The first approach is to partition the area into subareas so that agents can divide labor. Ahmadi and Stone [3] extended their previous work [2] to cases with multiple patrolling agents. Their extended method segmented the region of responsibility for individual agents, which exchanged boundary information, and agents visiting a boundary region more frequently tended to take charge of the region. Voronoi-based techniques are also other methods that do not require graphic descriptions of environments, such as [5,7,21].

Bio-inspired computation models are also used to divide areas. For example, Elor and Bruckstein [10] proposed a method of segmentation to cover a regions by integrating ant-pheromone and balloon models; a region was segmented into subregions that were individually assigned to different agents. Each subregion was considered to be a balloon, the pressure of which represented the size of the subregion. The pressure values were then indirectly exchanged using the pheromone communication model. Ranjbar-Sahraei et al. [18] introduced indirect communication using pheromone-based stigmergic communications to identify the regions that should be covered. McCaffery [16] proposed a graph partitioning algorithm using foraging behaviors. The resulting subgraphs were allocated to agents so that they covered the whole environment. However, the implementation of pheromone communications in decentralized multiple-robot applications is not trivial. Furthermore, this method did not take into account differences in agent performance and environmental characteristics. Kato and Sugawara [14] proposed a method of area segmentation that reflected these differences, e.g., high-performance agents were allocated wider subareas as responsible regions, although it was not based on a bio-inspired model.

Another approach is where agents traverse a shared area along different/identical routes or with different exploration algorithms. For example, the theoretical approaches mentioned above [6,9] were based on this approach. Mead et al. [17] proposed team formation by local interactions with neighboring robots for search-and-rescue applications. Agmon and Peleg [1] developed an algorithm for robots to gather at a certain point. Fierro et al. [11] proposed a framework in which robot vehicles followed a prescribed trajectory while maintaining a required formation without explicit communication between them. The formation of robots is significant in a number of application domains; e.g., it can reduce omissions in search-and-rescue applications. In contrast, our approach focuses on autonomously but appropriately selected independent algorithms for their coordinated task, because robot formation is not necessarily required in our domain (continues cleaning). Sampaio et al. [19] proposed a gravity-based model in which locals that had not been visited for a long time had the stronger gravity, and thus, agents tended to visit such locations in uniform patrolling. However, our method is used to visit locations with different frequencies according to (priori given or learned) data about how easily locations become dirty.

3. Model and problem description

3.1. Application environments

Agents are on portable cleaner robots capable of autonomously deciding their actions and receiving messages in our applications. We assumed that agents knew their own and others’ locations. We consider an example system that consists of a number of agents equipped with indicators (such as infrared emission/reflecting devices) on the top and a receiver installed on the ceiling that identifies their locations and periodically broadcasts these data to all agents. Agents are periodically informed of the locations of the others so that they can identify which locations have recently been cleaned. Another example system is where the cleaner agents have communication devices but only exchange superficial data (including current and past locations). However, agents do not acquire deep knowledge such as the others’ plans and intentions because the use of these sophisticated data for reasoning requires considerable computational power and additional communications for coordination [4]. In addition, such sophisticated capabilities are often restricted due to limited CPU power and battery capacity. We call coordination using only superficial data shallow coordination.

We also assumed that agents would have a map (graph) of the environment, G. Its structure may often be unknown in real applications, but there are many algorithms to create the map (e.g., [12,24]). We introduced these assumptions because we focused on the autonomous learning of target decision strategies.

3.2. Model of agent and environment

Let $A = {1, \dots, n}$ be a set of agents. The environment in which agents move is described by graph $G = (V, E)$ , where V and E correspond to sets of nodes and edges. We introduce a discrete time with a unit that is called a tick. An agent can move between nodes and clean a node it visits. Without loss of generality, we can assume that the length of an edge in E is one (by adding dummy nodes if necessary). Thus, any agent can move from a node to another and then clean the node it arrives at in one tick. The minimum route length between $v_{i}$ and $v_{j} \in V$ is denoted by $d (v_{i}, v_{j})$ . Let $v^{i} (t) \in V$ be the location of $i \in A$ at time t. We assumed that multiple agents could stay at the same location. Of course, this may be impossible. However, a number of efficient collision avoidance algorithms have been proposed [13] and the use of one of them can simplify our model by assuming no collisions occur.

We probabilistically describe the ease of the accumulation of dirt, and $P_{v}$ for node $v \in V$ denotes the probability that one (piece of) dirt is accumulated per tick. Then, the amount of dirt at v at time t, $L_{t} (v)$ is updated as $\begin{array}{rcl} L_{t} (v) \leftarrow \{\begin{matrix} L_{t - 1} (v) + 1, & if a piece of dirt appears (with probability P_{v}) at t, \\ L_{t - 1} (v) & otherwise. \end{matrix} \end{array}$ However, if an agent has visited v at t, then $L_{t} (v) = 0$ .

We consider two cases where agents know or do not know ${P_{v} | v \in V}$ . Of course, in both cases, they do not know the actual amount of accumulated dirt, $L_{t} (v)$ , but if they know the probabilities, ${P_{v} | v \in V}$ (or their approximated probabilities), they can estimate it from ${EL}_{t} (v)$ , which is the expected value of $L_{t} (v)$ at any future time t defined as $\begin{matrix} {EL}_{t} (v) = P_{v} \cdot (t - t_{visit}^{v}), \end{matrix}$ where $t_{visit}^{v}$ is at which an agent visited and cleaned most recently for node $v \in V$ . Agents can know $t_{visit}^{v}$ because they have exchanged their locations with one another. We assumed that agents knew ${P_{v} | v \in V}$ at the beginning of this paper, but we will exclude this assumption from the final method by adding learning to identifying locations that easily become dirty.

3.3. Batteries in agents

A battery in agent i is denoted by $B^{i} = (B_{\max}^{i}, B_{dr}^{i}, k_{charge}^{i})$ , where $B_{\max}^{i} > 0$ is the maximal capacity of the battery, $B_{dr}^{i} > 0$ is the amount of battery consumption per tick, and parameter $k_{charge}^{i} (> 0)$ indicates the speed of charge. Let $b^{i} (t)$ be the remaining capacity of the battery in agent i. Then, when i moves, $b^{i} (t)$ is updated by $\begin{matrix} (1) & b^{i} (t + 1) \leftarrow b^{i} (t) - B_{dr}^{i} \end{matrix}$ every tick. When i charges its battery at its own charging base, $v_{base}^{i}$ , the required time for a full charge starting from time t, $T_{charge}^{i} (t)$ , is proportional to the consumed battery life: $\begin{matrix} (2) & T_{charge}^{i} (t) = k_{charge}^{i} \cdot (B_{\max}^{i} - b^{i} (t)) . \end{matrix}$ After this, $B_{\max} = B_{\max}^{i}$ , $k_{charge} = k_{charge}^{i}$ , and $B_{dr} = B_{dr}^{i}$ are independent of i for simplicity, but we can easily extend the formulation below without these assumptions.

3.4. Performance measure

We used the cumulative existence duration of dirt at certain intervals of time as the performance measure to evaluate our proposed method. This is defined as $\begin{matrix} (3) & D_{t_{s}, t_{e}} = \frac{\sum_{v \in V} \sum_{t = t_{s} + 1}^{t_{e}} L_{t} (v)}{t_{e} - t_{s}}, \end{matrix}$ where positive integers $t_{s}$ and $t_{e}$ are the start and end times of the interval. A smaller performance value is better, so agents try to minimize the values of $D_{t_{s}, t_{e}}$ . Note that Formula (3) indicates that if agents leave dirty locations without cleaning them, $D_{t_{s}, t_{e}}$ will increase, so agents should clean these locations as soon as possible.

4. Planning in agents

Agents create plans for their behaviors in two stages: target decision and path generation. The agent determines in the former stage which target node $v_{tar} \in V$ it should clean, and it generates the path to this target in the latter stage. There are a number of strategies to determine the targets and paths. However, we used a number of simple strategies because the main purpose of this paper was not to propose effective or sophisticated planning algorithms, but to propose the selection of an autonomous planning strategy for coordinated work.

4.1. Target decision strategies

Agents determine their target nodes by taking into account (1) which node is expected to accumulate the largest amount of dirt in the environment and (2) which node is unlikely to be shortly visited by other agents. Agent i uses one of the following strategies to select the target node, $v_{tar}^{i}$ .

4.1.1. Random selection

Agent i selects the next target node from V randomly.

4.1.2. Probabilistic greedy selection (PGS)

For positive integer $N_{g}$ and time t, let $V_{g}^{t} \subset V$ be the set of the first $N_{g}$ nodes according to ${EL}_{t} (v)$ . Agent i then randomly selects target node $v_{tar}^{i}$ from $V_{g}^{t}$ . Note that randomness is introduced in this strategy to avoid the concentration of targets by multiple agents. In fact, this dramatically improves the performance of the cleaning job by multiple agents.

4.1.3. Repulsive selection (RS)

Let $V_{rep}^{i}$ be the set of $N_{rep}$ nodes that i randomly selected from V, where $N_{rep}$ is a positive integer. Then, i decides next target $v_{tar}^{i}$ as $\begin{matrix} (4) & v_{tar}^{i} = \underset{v \in V_{rep}^{i}}{arg max} \sum_{i \in A} d (v^{i} (t), v) . \end{matrix}$ Thus, agents select the next node whose summative distance from all agents is the longest.

4.1.4. Balanced neighbor-preferential selection (BNPS)

The basic idea behind the balanced neighbor-preferential selection strategy is that, if there are dirty nodes in the neighborhood, the agent selects nearby nodes to clean, but otherwise selects farther dirtier nodes. Note that agents identify node v as dirty when ${EL}_{t} (v) > E_{th}^{i}$ , where $E_{th}^{i} (> 0)$ is the threshold and is adaptively adjusted in each agent. The details on BNPS are as follows.

For agent i and time t, we define $V_{neigh} (v^{i} (t)) = {v \in V | d (v, v^{i} (t)) < d_{th}}$ , where $d_{th} > 0$ . Then, i calculates the average value of the expected accumulated dirt in $V_{neigh} (v^{i} (t))$ : $\begin{matrix} (5) & {EV}_{t}^{i} = \frac{\sum_{v \in V_{neigh} (v^{i} (t))} {EL}_{t} (v)}{| V_{neigh} (v^{i} (t)) |} . \end{matrix}$ The value of ${EV}_{t}^{i}$ also indicates the expected value of cleaned dirt per tick if i moves around in $V_{neigh} (v^{i} (t))$ .

In BNPS, i will select the next target node $v_{tar}^{i}$ from $V_{neigh} (v^{i} (t))$ if ${EV}_{t}^{i} > E_{th}^{i}$ and will otherwise select it from V using PGS. The initial value of $E_{th}^{i}$ is ${EV}_{t}^{i}$ that is set when BNPS is used for the first time. When i has selected a target from V and has arrived at it after k ticks, $V_{neigh} (v^{i} (t + k))$ and ${EV}_{t + k}^{i}$ will be recalculated. Then, $E_{th}^{i}$ will be updated as $\begin{matrix} (6) & E_{th}^{i} \leftarrow E_{th}^{i} + α ({EV}_{t + k}^{i} - E_{th}^{i}), \end{matrix}$ where α is the parameter to adjust the threshold value. The purpose of this update is to identify the threshold value for balancing local and non-local target selections.

4.2. Path generation strategies

4.2.1. Avoiding running out of batteries

After the target decision stage, agent i generates path to the target $v_{tar}^{i}$ by taking into account the remaining capacity of its battery.

For any node $v \in V$ , i calculates the potential in advance, which is the minimal capacity of the battery to return to i’s charging base $v_{base}^{i}$ . The potential of v in i is denoted by $P (v)$ and calculated as $\begin{matrix} (7) & P (v) = d (v, v_{base}^{i}) \cdot B_{dr} . \end{matrix}$ Since agents know G, they can identify the shortest path using the well-known algorithms such as Dijkstra’s method and A* algorithm. We say that node v is safe to move for i at time t, if the following condition is satisfied: $\begin{matrix} (8) & b^{i} (t) ⩾ P (v) + d (v^{i} (t), v) \cdot B_{dr} . \end{matrix}$ Agent i has to generate a path consisting of safe nodes; if it cannot, it changes the next target to $v_{base}^{i}$ , creates a path to return there, and charges.

4.2.2. Path generation

We considered two path generation strategies. The first is where agents select the shortest path from the current position to the selected targets (if there are multiple shortest paths, agents randomly select one). The second strategy, called the gradual path generation (GPG) method, is based on the idea that agents move along the shortest path, but if there are dirty places near the shortest path, they stop there and clean them. Agents in the GPG method generate the route as follows. Suppose that i has target $v_{tar}^{i}$ selected by one of the target decision strategies and sets the 0-th sub-target nodes as $v_{0}^{i} = v^{i} (t)$ . Then, agent i recursively selects the n-th sub-target, $v_{n}^{i}$ , which is the node having the maximal value of ${EL}_{t} (v)$ from the $(n - 1)$ -th sub-target nodes, such that it satisfies the following conditions: $\begin{array}{rcl} d (v_{n - 1}^{i}, v_{n}^{i}) ⩽ d_{cl}, \\ d (v_{n}^{i}, v_{tar}^{i}) < k_{att} d (v_{n - 1}^{i}, v_{tar}), \\ d (v_{n - 1}^{i}, v_{n}^{i}) + d (v_{n}^{i}, v_{tar}) ⩽ k_{rover} d (v_{n - 1}^{i}, v_{tar}), and \\ P (v_{tar}) + B_{dr} (d (v_{n - 1}^{i}, v_{n}^{i}) + d (v_{n}^{i}, v_{tar})) ⩽ b^{i} (t), \end{array}$ where $d_{cl}$ is a positive number defining closeness to select the next sub-target and parameters $0 < k_{att} ⩽ 1$ and $1 ⩽ k_{rover} < 2$ define how long agents wander off the shortest paths. However, if $d (v_{n - 1}^{i}, v_{tar}^{i}) ⩽ d_{cl}$ , $v_{n}^{i} = v_{tar}^{i}$ , this process terminates. Then, the final path is generated by connecting $v_{n - 1}^{i}$ and $v_{n}^{i}$ with the shortest path.

We found after our experiments that GPG always outperformed the simple shortest path strategy; thus, we only used GPG in the experiments described below. Note that we only assumed shallow coordination so that agents did not take into account the plans (paths and targets) of other agents. Hence, the target of a local agent may be cleaned by other agents before it arrives there.

5. Proposed method

5.1. Autonomous strategy selection

We propose a preliminary method in which agents identify the appropriate target decision strategies for coordinated cleaning tasks from the amount of dirt vacuumed up in the past by using reinforcement learning [25]. We called the proposed method the adaptive meta target decision strategy (AMTDS). Suppose that agent i selects next target $v_{tar}^{i}$ with strategy s (one of the target decision strategies described in Section 4.1). Then, i moves to $v_{tar}^{i}$ along the path generated by the GPG method. The reward for strategy s is defined as $\begin{matrix} (9) & u_{t_{0}, t_{0} + d_{travel}}^{i} = \frac{\sum_{t_{0} < t ⩽ d_{travel}} L_{t} (v^{i} (t))}{d_{travel}}, \end{matrix}$ where $d_{travel}$ is the length of time from time $t_{0}$ when i started to time $t_{0} + d_{travel}$ when i arrived at target $v_{tar}^{i}$ ( $d_{travel}$ is also the length of the path that i moved along).2

²
The values $u_{t_{0}, t_{0} + d_{travel}}^{i}$ was calculated using ${EL}_{t} (v_{t}^{i})$ (instead of $L_{t} (v_{t}^{i})$ ) in the experiments in Reference [25] although the definition in this paper is more natural. This difference led to slight differences between the experimental results in [25] and those in Section 6.

The Q-value of s is updated as $\begin{matrix} (10) & Q (s) \leftarrow (1 - α) \cdot Q (s) + α \cdot u_{t_{0}, t_{0} + d_{travel}} . \end{matrix}$ Thus, agents with AMTDS learn to select the strategy that maximizes the amount of vacuuming-up dirt per tick. Note that agents select target decision strategies using the ε-greedy method during learning.

5.2. Monitoring of local performance and relearning

While we were conducting the experiments to evaluate AMTDS, we found a phenomenon where overall performance gradually decreased over time in a certain environment. We will explain this in detail by referring to experimental results in Section 6.3.1. It was caused by many agents selecting the same strategy and/or strategies that had similar characteristics. We called this situation over-selection. Thus, we added the ability to self-monitor their local performance to agents. Then, if they found gradually degraded performance, agents discarded current learning results to escape from the situations and start to learn again (relearning).

We introduce moving average values, which are often used to identify raising/falling tendency in stock markets, to find the gradual changes in the amount of vacuumed dirt. When agent i returns to the base at time $t_{1}$ in the l-th cleaning travel, it calculates the performance, $U_{l}^{i}$ , which indicates the average amount of vacuumed dirt during the l-th travel: $\begin{matrix} U_{l}^{i} = u_{t_{0}, t_{1}}^{i} = \frac{\sum_{t_{0} < t ⩽ t_{1}} L_{t} (v^{i} (t))}{t_{1} - t_{0}}, \end{matrix}$ where $t_{0}$ is the starting time of the l-th travel. For positive integer L, the L moving average of the amount of vacuumed dirt in i, $M_{L}^{i}$ , is defined as: $\begin{matrix} (11) & M_{L}^{i} = \frac{\sum_{k = l - L + 1}^{l} U_{k}^{i}}{L} . \end{matrix}$ For agent i to autonomously identify the trend in its performance over time, agents compare the short- and long-term moving average values. That is, we introduce three parameters of positive integers, $l_{0}$ , $l_{1}$ , and $N_{th}$ such that $l_{0} ≪ l_{1}$ (at least, $2 l_{0} ⩽ l_{1}$ ), and if condition $M_{l_{0}}^{i} < M_{l_{1}}^{i}$ consecutively holds for $N_{th}$ times, i identifies that its own performance will begin to decrease. Then, i initializes the Q values and relearns the strategies. We will call this method AMTDS with relearning by self-monitoring (AMTDS/RM), after this. Note that agents individually decide when to discard and relearn.

5.3. Learning of dirt accumulation

${P_{v} | v \in V}$ is assumed to be given in AMTDS and AMTDS/RM. Because this assumption restricted their application to real-world systems, we eliminated it and instead, we integrated the learning of ${P_{v} | v \in V}$ into AMTDS/RM. We call this method AMTDS with relearning by self-monitoring and learning of dirt accumulation probability (AMTDS/RMLD), which is the method we finally propose in this paper.

Agents learn ${P_{v} | v \in V}$ as follows. Agent i initializes $P_{v}^{i} = 0$ for all nodes in V. Suppose that i visits node v at time t with vacuumed dirt amounting to $L_{t} (v)$ . Let $J_{t}^{i} (v)$ be the time difference between $t_{visit}^{v}$ , the most recent time when a certain agent visited v and the current time, i.e., $\begin{matrix} J_{t}^{i} (v) = t - t_{visit}^{v} . \end{matrix}$ Then, $P_{v}^{i}$ is updated by $\begin{matrix} P_{v}^{i} \leftarrow (1 - α (J_{t}^{i} (v))) P_{v}^{i} + α (J_{t}^{i} (v)) \frac{L_{t} (v)}{J_{t}^{i} (v)}, \end{matrix}$ where $0 < α (x) ⩽ α_{\max}$ is the learning rate function. If observation interval $J_{t}^{i} (v)$ is wider, the estimated probability, $L_{t} (v) / J_{t}^{i} (v)$ , is more reliable and thus, $α (x)$ should be a monotonically increasing function. In this paper, we defined it as $\begin{matrix} α (x) = min (α_{ini} \cdot x, α_{\max}), \end{matrix}$ where parameters $0 < α_{ini} ≪ 1$ and $0 < α_{\max} < 1$ correspond to the base learning rate and the maximal learning rate. Hence, it increases linearly according to the width of internal $J_{t}^{i} (v)$ with the maximal value, $α_{\max}$ .

6. Experiments

6.1. Experimental environments

We evaluated AMTDS in a simulation environment. G is defined as a $51 \times 51$ grid. Node v is expressed by $(x, y)$ , where $- 50 ⩽ x, y ⩽ 50$ . The charging bases for all agents are on shared location $v_{base} = v_{base}^{i} = (0, 0)$ and they can charge at the same time.

We prepared four environments for the experiments (Fig. 1) because different but interesting coordination regimes emerged. Dirt is accumulated uniformly in Env. (a). We define $P_{v} = 0$ or $5 \times 10^{- 6}$ for any node v. These values were randomly chosen for all nodes at the beginning of all experiments. In contrast, Envs. (b)–(d) had regions that were easily contaminated. $P_{v}$ for $v \in V$ in Envs. (b)–(d) is defined as $\begin{array}{rcl} P_{v} = \{\begin{matrix} 10^{- 3} & (if v is in the red regions) \\ 10^{- 4} & (if v is in the gray regions) \\ 10^{- 6} & (otherwise) \end{matrix} \end{array}$ Note that the size of the square regions is $8 \times 8$ (i.e., 9 × 9 nodes). The coordinates of the regions are outlined in Fig. 1. Env. (b) is an environment where dirt has accumulated near the walls and Env. (d) is a more complicated environment with a number of independent regions where dirt has easily accumulated. Env. (c) has both these characteristics.

We set $B_{\max} = 900$ , $B_{dr} = 1$ , and $k_{charge} = 3$ in all the experiments. Thus, agents could continuously operate up to 900 ticks and required 2700 ticks for a full charge if the battery was flat, making the maximum cycle of operation and charge 3600 ticks. We defined these values according to the specifications of an actual robot cleaner.3

³
We assumed that one tick would approximately be 4 seconds, velocity would be 0.25 m/s, the maximum operation time would be 1 hour, and the maximum battery charging time would be 3 hours.

Table 1

Parameters for target decision strategies

Target decision strategies	Parameters	Values
PGS	$N_{g}$	5
RS	$N_{rep}^{i}$	100
BNPS	α	0.1
BNPS	$d_{th}$	15
AMTDS, AMTDS/RM and AMTDS/RMLD	α	0.1
	ε	0.05
	$(l_{0}, l_{1})$	$(5, 10)$
	$N_{th}$	5
	$α_{ini}$	$0.0001$
	$α_{\max}$	$0.1$

Fig. 1.

Experimental environments.

The agents in the experiments were assumed to be homogeneous: they always used the GPG method as a path generation strategy and used one of seven target decision strategies (R (random selection), PGS, RS, BNPS, AMTDS, AMTDS/RM, and AMTDS/RMLD). Agents in the case of R, PGS, RS, and BNPS always adopted a single target decision strategy, so we called these situations single strategy regimes. However, when they used AMTDS AMTDS/RM or AMTDS/RMLD, they independently selected one from R, PGS, RS, or BNPS based on local learning. We then compared the values of $D_{t_{s}, t_{e}}^{n}$ every 3600 ticks (the maximal operation cycle). The parameter values used in target decision strategies are listed in Table 1. Note that these values are determined by considering the size of the experimental environment and the number of agents, but are not optimal. The parameters used in the GPG method are defined as $d_{cl} = 15$ , $k_{att} = 1.0$ , and $k_{rover} = 1.2$ . The experimental values given below are the averages of 20 independent trials based on different random seeds. The length of each trial was 496,800 ticks, which is 138 maximum cycles, in Exps. 1 and 2, and 2,998,800 ticks (833 maximum cycles) in Exp. 3. We examined cases in which $| A | = 5, 10, 15$ , and $20$ to understand what effect agent populations had on overall performance.

6.2. Experiment 1: Performance improvement and regime structural analysis

6.2.1. Performance comparison

The main purpose of Exp. 1 was to evaluate the performance of cleaning by agents with AMTDS by comparing it with those under single strategy regimes and to investigate which strategies were selected in individual agents with AMTDS. Figures 2–5 plot the performance values,

D_{t_{0}, t_{0} + 3600}

, by n agents with the target decision strategy, s, where

t_{0} = 144000

. After this, we will simply express it by

D^{n} (s)

(e.g.,

D^{20} (RS)

| A | = 20

and their strategy is RS). Note that the smaller

D^{n} (s)

is better.

Table 2
Improvement ratios with 10 agents, $I^{10} (s)$

Environments	PGS	RS	BNPS	AMTDS
Env. (a)	0.827	0.843	0.807	0.805
Env. (b)	0.678	0.517	0.569	0.503
Env. (c)	0.747	0.852	0.612	0.502
Env. (d)	0.967	0.813	0.799	0.612

Table 3

Improvement ratios with 20 agents, $I^{20} (s)$

Environments	PGS	RS	BNPS	AMTDS
Env. (a)	0.891	0.896	0.845	0.823
Env. (b)	0.854	0.555	0.681	0.540
Env. (c)	0.894	0.938	0.722	0.527
Env. (d)	1.142	0.871	0.976	0.626

These graphs in Figs 2–5 indicate that while agents with the PGS, RS, or BNPS strategies outperformed those with the R strategy, AMTDS always outperformed the others. We calculated the improvement ratios of

D^{n} (s)

for

D^{n} (R)

, which is denoted and defined by

I^{n} (s) = D^{n} (s) / D^{n} (R)

to clearly understand the improvements. The results when

n = 10

, and

20

are listed in Tables 2 and 3. These tables indicate that in the uniform environment (Env. (a)),

I^{n} (s)

(

n = 10

, and

20

) are not very different in any strategies. However, in other environments, the differences became significant. For example, Tables 2 and 3 indicate that the RS strategy usually exhibited better performance in Env. (b), but not in Env. (c), in which the BNPS strategy was better (also see Figs 3 and 4). Furthermore, BNPS in Env. (d) exhibited the best performance (except for AMTDS) when

n = 10

, whereas RS was the best when

n = 20

. Of course, AMTDS was always the best of all the strategies.

Table 4

Effects of agent populations in Env. (a), $W^{5 / n} (s)$

$\| A \|$	R	PGS	RS	BNPS	AMTDS
10	0.508	0.524	0.532	0.515	0.514
15	0.337	0.359	0.363	0.353	0.349
20	0.256	0.285	0.285	0.272	0.265

Table 5

Effects of agent populations in Env. (b), $W^{5 / n} (s)$

$\| A \|$	R	PGS	RS	BNPS	AMTDS
10	0.505	0.560	0.531	0.531	0.519
15	0.341	0.431	0.368	0.396	0.364
20	0.254	0.355	0.287	0.320	0.281

Table 6

Effects of agent populations in Env. (c), $W^{5 / n} (s)$

$\| A \|$	R	PGS	RS	BNPS	AMTDS
10	0.509	0.589	0.512	0.556	0.508
15	0.336	0.432	0.369	0.395	0.353
20	0.257	0.355	0.284	0.331	0.268

Table 7

Effects of agent populations in Env. (d), $W^{5 / n} (s)$

$\| A \|$	R	PGS	RS	BNPS	AMTDS
10	0.505	0.594	0.531	0.613	0.529
15	0.348	0.438	0.377	0.457	0.359
20	0.257	0.356	0.289	0.381	0.275

Tables 4–7 summarize the effects of agent populations on overall performance. Values $W^{n / 5} (s) = D^{n} (s) / D^{5} (s)$ for $n = 10, 15$ , and $20$ are listed. In Env. (a), the number of agents was directly related to performance: the values of $W^{n / 5} (s)$ in Table 4, especially with the R and AMTDS strategies, are close to $5 / n$ . This characteristic was also observed in other environments when the agents adopted the R or AMTDS strategies, but lessened somewhat when they adopted other strategies. This indicates that agent regimes using PGS, RS, or BNPS could not fully exert their abilities through coordination if their populations were large.

Fig. 2.

Values of cumulative existence times of dirt in Env. (a).

Fig. 3.

Values of cumulative existence times of dirt in Env. (b).

We also investigated how performance improved through learning for coordination. Figure 6(1)–(4), which is the graphs of $D^{20} (AMTDS)$ in Envs. (a)–(d), indicates that their performance improved over time due to AMTDS and converged at around 150,000 ticks. First, agents did not sufficiently learn their strategies, so they could not select appropriate strategies. However, after that, the amount of dirt gradually decreased as they learned strategies. Note that the time lengths for battery charge were approximately $3 / 4$ , so even in situations in which 20 agents moved, only five agents were activated on average.

Fig. 4.

Values of cumulative existence times of dirt in Env. (c).

Fig. 5.

Values of cumulative existence times of dirt in Env. (d).

Fig. 6.

Improvement in $D_{t_{s}, t_{e}}^{20} (AMTDS)$ over time.

Fig. 7.

Number of agents with each target decision strategy ( $| A | = 20$ ).

6.2.2. Strategies adopted by agents with AMTDS

We investigated which target decision strategy agents with AMTDS selected through learning. Figures 7(1)–(4) plot the number of agents that adopted R, PGS, RS, or BNPS strategies over time when $n = 20$ . A key observation from these figures and from Fig. 6 was that under the regime with the same number of agents with different strategies in the earlier times of the experiments, agents could not achieve sufficient performance. After sufficient learning, appropriate combinations of agent strategies were identified, and thus, they could exert their capabilities in coordinated activities. Next, we will discuss the characteristics of the developments of strategies learned as the best for agents’ coordinated activities.

Fig. 7(1) that plots the strategies agents with AMTDS adopted in Env. (a) indicates that RS was selected more than the others. Because dirt was located uniformly over the entire region, agents with the RS strategy could move around separately and vacuumed up more. In contrast, the agents with PGS and BNPS decreased; because they, especially those with BNPS, could not find the dirty nodes, they could not effectively vacuumed dirt up. However, as shown in Fig. 2, the single regime with the RS strategy did not exhibited better performance. This suggested that a small number of PGS strategy improved the performance and thus, the characteristics of the single and multiple strategy regimes are different.

More agents adopted the RS strategy in Env. (b), where dirt was accumulated near the walls, as shown in Fig. 7(2). The near-the-wall dirty area is relatively wide in Env. (b), and because agents with RS tended to move around separately in this area, they could achieve better coordination than that in Env. (a). After RS, they were likely to select PGS because these agents could move toward dirty nodes where were left without cleaning by the RS agents. Instead, the agents with the R and BNPS are few. In this environment, this result is consistent with that where the RS single regime exhibited the best performance (see Fig. 3). On the other hand, BNPS was the second best in the single regime structure (Fig. 3). The combination of the RS and PGS performed better and eliminated the benefit of BNPS.

The curves in Fig. 7(3) indicate that PGS and BNPS were selected more in Env. (c) than in Env. (b). Since Env. (c) has the cingular dirty region near the walls, like Env. (b), agents with the RS strategy performed well by moving around separately. Furthermore, it also has two block-shaped, small dirty regions but the RS strategy prevented multiple agents from intensively cleaning them. We think that agents with PGS and BNPS compensated for this situation. Particularly, BNPS can clean the local dirty region and is suitable to clean the block regions.

PGS and BNPS were likely to be selected as the target decision strategies by agents with AMTDS in Env. (d) as is shown in Fig. 7(4). Because this environment has more block-shaped dirty regions, more agents with PGS and BNPS that can effectively clean the block regions were required. Other nodes seemed to be cleaned by the agents with RS separately. Such a strategy regime structure is effective to work in Env. (d).

The discussion so far indicates that the appropriate strategy when all the agents adopted the same strategy was not always identical to the one that was most used by agents with AMTDS. For example, with the single regime of PGS or BNPS, all agents congregated around the dirty rectangular-shaped regions, which may have resulted in inefficient concentrations in Env. (d). However, with the AMTDS strategy, many agents adopted PGS and BNPS and a few selected RS. In Env. (b), many agents with RS clean there in whole and a few agents with PGS covered the nodes that were left without cleaning. These combinations seemed to outperform the cleaning with the single strategy regime. Agents with AMTDS autonomously selected the strategies which they thought that were the best from their viewpoints, but such viewpoints were affected by other agent’s decisions. However, such an autonomous decision sometimes lead to a concentration to a certain strategy, as discussed in the next section.

6.3. Experiment 2: Avoidance of degradation by over-selection.

6.3.1. Over-selection of strategies

If we look at Fig. 6(4) again, we can confirm that performance in Env. (d) improved until 60000 ticks but gradually worsened after that. Thus, let us look at Tables 2 and 3 carefully. They indicate that $I^{n} (AMTDS)$ , which is the improvement ratios of $D^{n} (AMTDS)$ for $D^{n} (R)$ at the end of the experiment, in Env. (d) is slightly larger than that in Envs. (b) and (c), suggesting that performance did not sufficiently improved in Env. (d). The reason for this degradation is suggested by Fig. 7(4), which indicates that agents with AMTDS tended to finally select PGS and BNPS, but the basic schemes for these strategies were identical — proceed to the dirtiest locations. Hence, it seems that such a biased selection in AMTDS, i.e., over-selection decreased overall performance.

Such an over-selection was caused by the block-shaped dirtier regions; in such an environment agents should gathered such relatively small regions to clean and thus, strategies PGS and BNPS were appropriate. On the other hand, agents with RS did not approach to these dirty regions if another agent was there, but this is not enough to clean the dirty regions. Hence, agents tended to use PGS and BNPS over time, but this also means other nodes were left for a long time without cleaning.

Fig. 8.

Improvement in $D^{20} (s)$ with AMTDS/RM.

Fig. 9.

Strategies selected with AMTDS/RM ( $| A | = 20$ ).

6.3.2. Evaluation of AMTDS/RM

We introduced the AMTDS/RM to ease such situations of over-selection. Thus, the purpose of Exp. 2 was to investigate whether or not it really could avoid such degraded performance. Figure 8(1) and (2) plots improvements to performance ( $D_{t_{s}, t_{e}}^{20} (AMTDS/RM)$ ) in Envs. (c) and (d), when $| A | = 20$ .

First, Fig. 8(2) indicates that no degraded performance was observed; performance improved around 50000 ticks as it did in the case of AMTDS, and after that, performance was still continuing to improve until 150000 ticks and changed. Finally, the value of $D_{t_{s}, t_{e}}^{20} (AMTDS/RM)$ was 13.3% better than that of $D_{t_{s}, t_{e}}^{20} (AMTDS)$ . On the other hand, relearning by self-monitoring decreased performance (6.3%) in Env. (c) where no degraded performance was observed in Exp. 1 (see Fig. 8(1)), but its degradation is relatively small. Note that we omitted the figures for performance with AMTDS/RM in Envs. (a) and (b) but they were almost identical with those for AMTDS (so no degraded performance was observed).

We also examined how the strategy regimes changed over time in these environments. The results are provided in Fig. 9(1) and (2). By comparing these with Fig. 7(3) and (4), the orders of selected strategies were identical but AMTDS/RM could ease the bias in the strategy regimes of both environments. For example, the numbers of AMTDS/RM agents adopting PGS in Env. (c) and those adopting PGS or BNPS in Env. (d) were fewer than AMTDS agents adopting these strategies. Hence, the self-monitoring in AMTDS/RM avoided degradation by easing over-selection. Note that the R strategy was selected slightly more often with AMTDS/RM than with AMTDS in both environments because a few agents discarded the learning results in turn and the chances of selecting the R strategy increased.

Fig. 10.

Improvement in $D^{20} (s)$ with AMTDS/RMLD over time.

Fig. 11.

Strategies selected with AMTDS/RMLD ( $| A | = 20$ ).

6.4. Experiment 3: Learning of dirt accumulation probabilities

We conducted Exp. 3 to examine how AMTDS/RMLD, which is our proposed method in this paper, could contribute to improving performance by learning dirt accumulation probabilities from the amount of vacuumed dirt. We set $| A | = 20$ in Exp. 3 and the initial values of $P_{v}^{i}$ to zero for any $i \in A$ and $v \in V$ . The improvements to performance with AMTDS and AMTDS/RMLD are plotted in Fig. 10(1)–(4). Performance with AMTDS/RM in Envs. (c) and (d) has additionally been given in Fig. 10(3) and (4) for comparison.

First, we can find that initially (before 10,000 ticks), performance temporarily worsened, but soon recovered in all environments. Then, performance, $D^{20} (AMTDS/RMLD)$ , maintained the same level as those with AMTDS or AMTDS/RM. AMTDS/RMLD particularly outperformed AMTDS and AMTDS/RM in Envs. (c) and (d), respectively. We have presented the regime structures of selected strategies by agents with AMTDS/RMLD to better understand these situations; these are shown in Fig. 11(1)–(4). Note that we have plotted the changes in strategy regime structures until 3000000 ticks; the performance curves in Fig. 10 look converged before 500000 ticks, but their structures still continue to change.

Before discussing the regimes in individual environments, we can see common features in these figures: agents were initially likely to select the RS strategy. While dirt accumulation learning was insufficient, agents did not identify easy-to-dirty locations (this knowledge was important in PGS and BNPS) and assumed that the environment was uniform. Thus, the RS strategy, which made agents operate separately, could vacuum more dirt. Of course, this regime would gradually change according to progress in learning except for Env. (a), which was a really uniform environment. Hence, agents continued to adopt the RS strategy in the regime in Env. (a) (see Fig. 11(1)). This regime structure was quite different from that with AMTDS (see Fig. 7(1)) where dirt accumulation probabilities were assumed to have been given. This means that the initial increase of RS and the relearning by self-monitoring made the strategy regimes converge to other structures although their final performance was comparable.

We can also see that in the other environments, the orders of the numbers of adopted strategies with AMTDS/RMLD were identical to those with AMTDS (and AMTDS/RM), but their biased selections were avoided by relearning through self-monitoring. However, a negative effect by this relearning on their performance in Env. (c) disappeared, as seen in Fig. 10(3). Furthermore, AMTDS/RMLD outperformed the other methods in Env. (d) as shown in Fig. 10(4). We think that these improvements were caused by the side-effect of learning dirt accumulation probabilities: Dirt accumulated more in locally isolated regions in these environments and agents independently found (but not all) a number of these dirty local regions, and tended to clean there selectively. Therefore, agents unintentionally entered divisions of labor to improve task efficiency. We believe that such a division of labor occurred in other environments, but it appeared prominently in Env. (d) since it has a number of locally dirty regions. Thus, they could effectively clean although their strategy regime structure were slightly different from those by agents with AMTDS. We think that this is quite an interesting phenomenon and would like to utilize this feature; however, we need more analysis and study to control it for this purpose.

Finally, our experiments were done in the simulated environments because we want to clarify the effectiveness of our proposed methods. However, actual environments have more issues. For example, it is difficult to navigate robots exactly between adjacent grid cells without other helper equipment such as a localizer that identifying the locations of robots as mentioned in Section 3.1. Communications among agents are not always possible and packets sometimes dropped. We have to address these issues to achieve the autonomous robots that can work in the real world environments in the future.

7. Conclusion

We proposed a learning method of target decision strategies for coordination in cleaning tasks by multiple agents without direct communication. We first modeled the problem domain of continuous cleaning by multiple agents in which the locations of all agents were broadcast in the environment but they could not directly communicate with one another about their plans/targets for coordination. Then, we defined the evaluation measure as the cumulative existence duration of dirt per tick. We introduced three learning methods. First, AMTDS made agents individually identify the appropriate target decision strategies. AMTDS/RM, which is combined AMTDS and relearning with self-monitoring of local performance, could avoid the biased selection of strategies (over-selection). Finally, AMTDS/RMLD additionally used environmental learning to identify which locations were easy to make dirty. The experimental results demonstrated that the proposed methods could outperform other regimes in which agents adopted a single strategy and could generate an effective regime with appropriate combinations of multiple strategies for coordination. They also indicated that agents could avoid over-selection and could successfully learn environments.

We intend to modify the conditions of communication in future work. For example, agents can directly communicate with one another but within a limited distance and packets may sometimes drop. Such communications issues are necessary to apply the proposed method to other sweeping and patrolling applications.

References

[1]

Agmon and

Peleg, Fault-tolerant gathering algorithms for autonomous mobile robots, in: Proc. of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’04), Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2004, pp. 1070–1078.

[2]

Ahmadi and

Stone, Continuous area sweeping: A task definition and initial approach, in: Proc. of the 12th International Conference on Advanced Robotics, 2005, pp. 316–323.

[3]

Ahmadi and

Stone, A multi-robot system for continuous area sweeping tasks, in: Proc. of the 2006 IEEE International Conference on Robotics and Automation, 2006, pp. 1724–1729.

[4]

Beatriz,

Toledo and

N.R.

Jennings, Learning when and how to coordinate, Web Intelligence and Agent Systems 1(3) (2003), 203–218.

[5]

Breitenmoser,

Schwager,

J.-C.

Metzger,

Siegwart and

Rus, Voronoi coverage of non-convex environments with a group of networked robots, in: IEEE International Conference on Robotics and Automation (ICRA 2010), 2010, pp. 4982–4989.

[6]

Chevaleyre, Theoretical analysis of the multi-agent patrolling problem, in: Proc. of Intelligent Agent Technology, 2005, pp. 302–308.

[7]

Cortes,

Martinez and

Bullo, Spatially-distributed coverage optimization and control with limited-range interactions, in: ESAIM. Control, Optimisation and Calculus of Variations, 2004, pp. 691–719.

[8]

Dang,

Jun,

Oh and

Allen, Planning complex physical tasks for disaster response with a humanoid robot, in: Proc. of 2013 IEEE International Conference on Technologies for Practical Robot Applications (TePRA-13), 2013, pp. 1–6.

[9]

Elmaliach,

Agmon and

G.A.

Kaminka, Multi-robot area patrol under frequency constraints, Annals of Mathematics and Artificial Intelligence 57(3–4) (2009), 293–320.

10.

[10]

Elor and

A.M.

Bruckstein, Multi-a(ge)nt graph patrolling and partitioning, in: Proc. of the 2009 IEEE/WIC/ACM International Joint Conference on Web Intelligence and Intelligent Agent Technologies, 2009, pp. 52–57.

11.

[11]

Fierro,

Das,

Kumar and

Ostrowski, Hybrid control of formations of robots, in: Proc. of IEEE International Conference on Robotics and Automation (ICRA 2001), Vol. 1, 2001, pp. 157–162.

12.

[12]

Hahnel,

Burgard,

Fox and

Thrun, An efficient FastSLAM algorithm for generating maps of large-scale cyclic environments from raw laser range measurements, in: Proc. of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003), Vol. 1, 2003, pp. 206–211.

13.

[13]

Hennes,

Claes,

Meeussen and

Tuyls, Multi-robot collision avoidance with localization uncertainty, in: Proc. of the 11th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2012), IFAAMAS, Vol. 1, 2012, pp. 147–154.

14.

[14]

Kato and

Sugawara, Decentralized area partitioning for a cooperative cleaning task, in: PRIMA 2013: Principles and Practice of Multi-Agent Systems,

Boella,

Elkind,

Savarimuthu,

Dignum and

Purvis, eds, Lecture Notes in Computer Science, Vol. 8291, Springer, Berlin, Heidelberg, 2013, pp. 470–477.

15.

[15]

Kurabayashi,

Ota,

Arai and

Yoshida, Cooperative sweeping by multiple mobile robots, in: Proc. on 1996 IEEE International Conference on Robotics and Automation (ICRA 96), 1996, pp. 1744–1749.

16.

[16]

McCaffrey, Graph partitioning using a Simulated Bee Colony algorithm, in: IEEE International Conference on Information Reuse and Integration (IRI 2011), 2011, pp. 400–405.

17.

[17]

Mead,

J.B.

Weinberg and

J.R.

Croxell, An implementation of robot formations using local interactions, in: Proc. of the 22nd National Conference on Artificial Intelligence (AAAI’07), Vol. 2, AAAI Press, 2007, pp. 1989–1990.

18.

[18]

Ranjbar-Sahraei,

Weiss and

Nakisaee, A multi-robot coverage approach based on stigmergic communication, in: Multiagent System Technologies,

Timm and

Guttmann, eds, Lecture Notes in Computer Science, Vol. 7598, Springer, Berlin, Heidelberg, 2012, pp. 126–138.

19.

[19]

P.A.

Sampaio,

Ramalho and

Tedesco, The gravitational strategy for the timed patrolling, in: Proc. of the 2010 22nd IEEE International Conference on Tools with Artificial Intelligence, ICTAI’10, Vol. 1, IEEE Computer Society, Washington, DC, USA, 2010, pp. 113–120.

20.

[20]

Santana,

Barata,

Cruz,

Mestre,

Lisboa and

Flores, A multi-robot system for landmine detection, in: Proc. of the 10th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA 2005), 2005, pp. 721–728.

21.

[21]

Schwager,

Rus and

J.-J.

Slotine, Unifying geometric, probabilistic, and potential field approaches to multi-robot deployment, The International Journal of Robotics Research 30(3) (2011), 371–383.

22.

[22]

Stranders,

E.M.

de Cote,

Rogers and

N.R.

Jennings, Near-optimal continuous patrolling with teams of mobile information gathering agents, Artificial Intelligence 195 (2013), 63–105.

23.

[23]

B.A.

Vroegindeweij,

G.L.

van Willigenburg,

P.W.G.

Koerkamp and

E.J.

van Henten, Path planning for the autonomous collection of eggs on floors, Biosystems Engineering 121 (2014), 186–199.

24.

[24]

D.F.

Wolf and

G.S.

Sukhatme, Mobile robot simultaneous localization and mapping in dynamic environments, Autonomous Robots 19(1) (2005), 53–65.

25.

[25]

Yoneda,