Sage Journals: Discover world-class research

Abstract

This article studies the problem of painting an obstacle free rectangular region by a swarm of mobile robots. Initially the robots are deployed randomly within the target area subject to the condition that the distribution is d*-dense, where $d * = \frac{\sqrt{3 d}}{2}$ , and a robot can view up to a distance d. By d*-dense, it is meant that if all the robots are projected on a horizontal line, then the distance between two consecutive robots must be less than or equal to d*. Non-consideration of the popular CORDA (computational) model in the field of area coverage by swarm robots has been addressed here. The proposed algorithm assumes CORDA model. The robots follow a completely distributed algorithm to paint the region. The robots do not need to be synchronous, but they are assumed to have equal velocities. However, the proposed algorithm supports the robots with different speed. In that case, if r is the given upper bound on the ratios of the speeds of any two robots, then the initial distribution has to be D*-dense, where $D * = \frac{d}{4} \sqrt{(3 - r) (r + 5)} 1 \leq r < 3$ .

Keywords

Distributed algorithm robot swarm limited visibility painting

Introduction

The concept of swarm mainly emphasizes on the collective, cooperative and coordinated behaviour of a group of insects for performing a particular task. This concept of swarm is blended with the concepts of distributed algorithm to generate several applications for multi-robot coordination where the members of the swarm are identical. Together with the development of these physical robots, the research interests have been shifted towards the development of suitable algorithms that are capable of handling the coordination among multiple robots to perform large tasks. Among various applications of swarm of robots, research interest is gearing up in the field of area coverage. A swarm of mobile robots will achieve complete coverage of an area if and only if every location of the area is reached or scanned by at least one robot in the swarm. One of the applications of multi-robot area coverage is searching and rescuing of victims¹ in various hazardous or hostile environments. Moreover, the concept of area coverage may also be used in various applications² such as car body painting, area painting, lawn mowing and milling, sweeping, terrain exploration and mapping. Since covering an area is same as painting an area, from now onwards painting and covering are used interchangeably throughout this article.

This article addressed the problem of coverage or painting of a known obstacle-free rectangular area by robots with limited visibility range. Previous research works on multi-robot area coverage^3,4

–7 consider that the robots are having unlimited visibility, where each robot in the swarm can see the entire space. However, the visibility range of a robot depends on the power of the sensor or camera attached to it. To reduce the cost of mass production of robots in a swarm, the robots are intentionally made very simple with limited capacity. In this scenario, a robot having unlimited visibility is quite unnatural. In this article, we assume the robots to have limited visibility, so that they can view up to a fixed distance.

We have assumed that a swarm of N robots are deployed randomly inside the rectangular area, and each robot is having a visibility capacity up to a fixed distance d. However, it is assumed that the initial distribution is d*-dense, where $d * = \frac{\sqrt{3 d}}{2}$ . By d*-dense, we mean that if all the robots are projected on a horizontal line, then the distance between two consecutive robots must be less than or equal to d*. The whole area is partitioned into a number of non-overlapping cells or strips by the robots in a distributed way. The sizes of the strips may not be same. Each strip is assigned to exactly one robot for painting. Distribution of these strips among the robots is done by the robots themselves. A robot determines the boundaries of its strip to be painted by itself, based on the positions of the visible neighbours on its left, right, bottom and above. When each of the robots completes painting of its assigned strip, the overall painting is completed. Each robot performs its task in a completely distributed manner. Using the Player/Stage robotic simulator, this algorithm is simulated. The algorithm is capable of handling the robots with different speeds caused due to non-plane surfaces of the region. However, for a given upper bound $r (1 \leq r < 3)$ on the ratio of the velocities of any two robots, the initial distribution has to be D*-dense, where $D * = \frac{d}{4} \sqrt{(3 - r) (r + 5)}$ .

The proposed algorithm is based on CORDA⁸ model or wait–observe–compute–move model. CORDA is a theoretical model. It is a step towards real-life movements. In this model, a robot’s action (throughout the algorithm) can be viewed (and hence programmed) as a sequence of computational cycles when each cycle consists of four phases, namely wait (optional), observe, compute and move. Whatever a robot observes in observe phase is used to compute the next destination in compute phase and finally moves to the computed destination in move phase. These phases are non-overlapping, and each of these phases are carried out sequentially by each robot. It can be pointed out here that a robot observes its surroundings according to its local system. These features make the robots easier to program and thus make the solution cheaper. In most of the previous works found in the literature (except one), regarding coverage problem, CORDA model has not been considered. In those algorithms a robot can carry out all types of actions, such as viewing their surroundings, computing, moving, and communicating with teammates, all at a time, that is, simultaneously over a continuous period of time. These are features of a more powerful robot. Interestingly, in the domain of other problems than coverage, such as gathering and partitioning,^2,9 researchers consider only CORDA model because of its simplicity. The only work on coverage problem using CORDA reported in the literature are based on unlimited visibility. In the proposed algorithm, the robots are assumed to follow full-compass model in which they agree on the direction and orientation of their local axes. They are also assumed to be asynchronous.

Most of the previous works^{4

–7,10
–12} in this area have considered the presence of obstacles within the area and as a result, the existing algorithms involve large amount of complex calculations for a relatively weak model. However, covering an area without obstacle using the same complex calculations takes unnecessary extra time and make the solution more complicated. The robots used in these algorithms are not simpler as they need a large amount of memory with great computational ability. Moreover, active communication among the robots and prior information of the environment are also necessary in some of the existing solutions.

Getting a solution to the coverage problem becomes challenging when robots are assumed to be very simple with respect to computation and communication power, availability of memory and so on. The algorithm that we are going to propose here shows that the solution of the coverage problem can be achieved using a more realistic and relatively stronger model with simpler robots. In the proposed algorithm, the robots are neither controlled by any central authority nor any external body. The robots are assumed to be oblivious or memoryless in a restricted manner as they need to retain only a very small amount of information. The memory requirement is comparatively low. In addition to that, our aim is to design a solution, with these robots, which minimizes the cost as much as possible. Thus, an efficient solution would restrict redundant work done by the robots. By this, we mean that in an ideal situation any portion of the area should not be covered by more than one robot. Under the circumstances, direct communication among the robots seems to be absolutely necessary. When the robots work in a team, communication among the team members is also required. Most of the algorithms present in the literature assume that robots can communicate among themselves while covering the region. In the proposed solution, instead of direct communication, only a passive communication among the robots is assumed which further makes the solution less costly and simpler compared to the existing ones. By passive communication we mean the mode of communication is only through observing others without any kind of message passing or so. However, it is not expected that two robots observe their surroundings simultaneously at the same time. In the proposed solution, repeated coverage is avoided, though the robots perform their task independently without having any active communication with other robots.

Second section discusses the related research works. Third section includes the problem definition, models and assumptions in detail. Fourth section has two subsections. The first one discusses the painting algorithm and in the second subsection, the correctness of the algorithm is established. In the fifth section, the completion time of phase I is calculated. The simulation of the proposed algorithm is discussed in sixth section, and we conclude the article in the seventh section.

Related work

Various research works that dealt with multi-robot coverage problems have been reported. In the existing works, the problem definition varies in a way that the area to be covered may or may not contain obstacles. Moreover, the robots may have different capabilities with respect to visibility range, limited or unlimited. With all these variations, the main approaches that are followed in the existing algorithms are classified into two categories, team-based approach^5,6 and individual approach.^3,4,7 In the team-based approach, multiple robots move and perform their task in a team. Depending on different situations, a team can be subdivided into two teams and then after achieving their targets, the teams unite again and proceed further as a single team. Individual approaches are based on the concept of virtually dividing the whole area into a number of disjoint cells, and each robot is assigned the job of covering at least one such cell. In this approach, the robots usually work independently from each other.

The algorithms proposed in previous works^4

–7 consider the presence of obstacles in the area and the robots with unlimited visibility. Kong et al.⁴ used a distributed approach to solve the problem. They followed the ‘boustrophedon cellular decomposition approach’ to divide the whole region into some cells. Full-compass and asynchronous models are assumed. Moreover, the robots need to maintain and share among themselves the adjacency graphs that are generated by each of them separately, to represent covered and uncovered cells. This results in a requirement of a large amount of memory and computational power of the robots. Latimer et al.⁵ provided a fully synchronous team-based solution. They assumed full-compass model. The robots within a team always maintain communication, coordination and synchronization with each other which make the solution expensive and unrealistic. Moreover, the algorithm may result in repeated coverage. Rekletis et al. designed a team-based solution⁶ and a distributed solution.⁷ In the study by Rekletis et al.,⁶ the models used are full-compass and fully synchronous. There are two types of robots in a team: explorers, to explore the cell boundaries, and coverers, to cover the cell explored by the explorers. Throughout the algorithm, the explorers need to communicate among themselves which once again increase the overhead. Moreover, coverers may result repeated coverage by covering the area which is already covered by the explorers. On the other hand, in the study by Rekletis et al.,⁷ the model assumed is also full-compass but asynchronous. The algorithm uses the concept of building Reeb graphs by each robot and then sharing and updating of the same among themselves. This makes the algorithm complex. In addition to that, another limitation of the algorithm is its assumption of a special type of initial distribution of the robots, where robots are deployed in regular interval along the lower boundary of the region.

Very less works have been reported for the coverage problem with limited visibility and obstacle-free area. Although an algorithm that is meant for areas with obstacles is also applicable in an obstacle-free case, however, complex solution for a simpler problem makes the solution unnecessarily complicated. Das et al.³ presented a completely distributed simple algorithm to paint/cover a region without obstacle by following the basic CORDA model. They have considered, rather a stronger model, direction-only and asynchronous, for the solution. There is only passive communication among the robots in which the robots do not exchange information among themselves. The robots take the decisions regarding any type of movement based on the location of other neighbouring robots. The algorithm is able to successfully cover the whole region without repeated coverage and collision among the robots. Considering the presence of obstacles, Fazli et al.^10,11 proposed an offline coverage algorithm where the robots were initially aware of the entire environment including static obstacles. The authors here assumed that the robots are of limited visibility capability. However, the assumption of known environment dilutes most of the challenges faced in case of limited visibilities. Moreover, this algorithm demands the presence of a significant amount of memory in each of the robots. The robots here cannot be oblivious. Jiao et al.¹² proposed a decomposition algorithm for boundary coverage problem in case of a single robot as well as multiple robots. These algorithms assume the existence of polygonal obstacles. The robots are assumed to have unlimited visibility. However, their line of sight might be obstructed by the presence of obstacles.

The proposed algorithm shows that the coverage problem can be solved in a more realistic manner. In the proposed work, although the robots know the dimension of the region, they are completely unaware of the environment beyond its visibility range. If a robot does not see any of the boundaries, it is even completely unaware of its position within the area. Moreover, there is only passive communication among the robots. The robots are completely autonomous, and they are able to work independently from each other. As the communication and computational overheads are less, simple robots are used in place of complex robots. With respect to the existing algorithms, the proposed one is based on comparatively stronger model as it is designed by following the standard CORDA model, asynchronous and full-compass model. Most of the previous works have not considered the standard CORDA model⁸ for designing the algorithms. The algorithm is also capable enough to accommodate the robots with different speeds, caused due to non-plane surfaces. The algorithm takes finite amount of time to solve the problem without any collision and repeated coverage.

Problem definition, assumptions and models

Our problem is to paint an obstacle-free rectangular area by a swarm of robots. The area is bounded on all sides. Assuming that no two robots can occupy the same position, the robots are randomly distributed over the region subject to the condition that the distribution is d*-dense. If vertical lines (hypothetical) are drawn through each robot then in d*-dense distribution, the distance between two consecutive vertical lines should be less than or equal to d*. In this article, we assume that $d * = \frac{\sqrt{3 d}}{2}$ , d is the visibility range of the robots. It is assumed that both the left and the right boundary of the rectangular area must be viewed by at least one robot. The characteristics of the robots and the models assumed are as follows:

(a) Robots are identical and homogeneous with respect to their computational power. (b) They are autonomous in the sense that there is no central control. All the robots execute the same algorithm independently of the others to achieve the goal in a completely distributed way. (c) Robots have passive communication among themselves. The robots do not exchange any kind of information with others. (d) All robots are allowed to move on a plane. (e) Robots are having limited visibility. Each robot can view only those robots that are located at the most at a fixed distance d from it. So, the area of visibility for each robot can be measured by a circle (known as circle of visibility) with radius d (known as visibility radius). (f) Full-compass: Each robot has its own local coordinate system in which they are placed at the origin. The robots agree on directions and orientations of their local axes. (g) The robots are assumed to follow CORDA model. A computational cycle is defined to be a sequence of observe, compute and move steps. Each of the robots executes same instructions in all the computational cycles. Once a robot completes one computational cycle, it starts executing the next one. This process is repeated until the whole job is completed. The actions taken by a robot in compute and move steps, entirely depend on the observe step. In some situations, an observation might lead a robot not to change its position in move step. In such cases, the robot seems to be idle, though it is actually executing all the three steps. The duration of a computational cycle is the total time taken by the robot to execute observe, compute and move steps in one cycle. In each move step, a robot moves at the most $\frac{d}{2}$ distance, where d is the radius of the circle of visibility. If the velocity of the robot is v, the time taken in move step is at the most $\frac{d}{2 v}$ . The time taken by a robot to complete observe and compute steps is much less compared to the time taken in move step. Let us assume that T₀ be the maximum time taken by a robot to execute observe and compute steps. We assume that T₀ is same for all the robots. Hence, to complete a computational cycle, a robot takes at the most $(T_{0} + \frac{d}{2 v})$ time, where v is the velocity of the robot. We can also say that the time gap between two consecutive observe steps of a robot is at the most $(T_{0} + \frac{d}{2 v})$ (approximately). (h) Robots are not completely oblivious (memoryless) but possess a small amount of memory (O(1)) to retain the values of a few variables, throughout the execution of the algorithm. (i) Asynchronous model: The robots operate on independent computational cycles. They do not share any common clock and are active in every cycle. We only assume that the robots start executing the algorithm at the same time. If the velocities of the robots are equal, the robots act in almost synchronous way because of the above assumptions. However, if the robots have different velocities, then asynchronicity of the robots become obvious. (j) The velocities of the robots are assumed to be equal. In case of robots with different velocities, we assume that the initial distribution is D*-dense, where $D * = \frac{d}{4} \sqrt{(3 - r) (r + 5)}$ , when it is given that the ratio between the velocities of two robots can be at the most r, $1 \leq r < 3$ . (k) The painting operation is assumed to be an Atomic operation. Once a robot starts painting the assigned cell, it completes its job without any further interruption.

Coverage algorithm

The first part describes the proposed algorithm. The correctness of the algorithm is proved in the second part.

Description of the algorithm

The basic idea of the algorithm is to divide the whole region into a number of disjoint parallel vertical strips. Each robot will be assigned one strip for painting. The robots have limited view of their neighbours. Based on the gathered information in the observe step, a robot calculates its own strip boundaries. The robots retain the information regarding strip boundaries using some variables that are updated during the execution of the algorithm. Let us first discuss some terminologies that will be used later. (a) Nearest right neighbour (nrn)/nearest left neighbour (nln): For a robot R, the nearest right (left) neighbour is the robot R′ such that (i) R′ is on the right (left) of R, (ii) $h d i s t [R, R^{'}]$ is minimum among all robots which are on the right (left) of R. It is not necessary that initially R′ is visible to R. (b) Nearest visible right neighbour (nvrn)/nearest visible left neighbour (nvln): At a particular instant of time, among all the visible robots which are on the right (left) of R, the one whose hdist from R is minimum is called as the nearest visible right neighbour at that instant of time.

In the first phase of the algorithm, a robot calculates the boundaries of the strip which is to be painted by itself and in the second phase, the robot actually paints the strip. From the position where the robots are deployed initially, each of the robots moves in the upward direction (according to their own local coordinate system) first until it reaches the upper boundary of the region. It then moves in the vertically downward direction to reach the lower boundary of the region. While traversing this route, the robot finalize its strip boundaries, left, right, bottom and top. After reaching the lower boundary of the strip to be painted (in general, the lower boundary of the region), the robot starts painting from the bottom left-most corner of the strip. It is assumed that movements of the robots are not instantaneous.

A robot finally fixes its right and left boundaries at a distance $\frac{d_{R}}{2}$ and $\frac{d_{L}}{2}$ from itself where d_R and d_L are the horizontal distances of the robot from its nearest right neighbour (nrn) and nearest left neighbour (nln), respectively. Since nearest neighbours (right/left) may not be visible initially, robots initially set the left and right boundaries at a distance of d from itself. To finalize the positions of the boundaries, a robot computes the distance of its nearest visible neighbours in every computational cycle, throughout the first phase of the algorithm. Based on those distances, it estimates the position of the right and left boundaries. It then compares the estimated one with the stored one, whichever is nearer, it accepts that as the tentative position of the boundaries and stores it. Lemmas I, II and IV assure that during the first phase of the algorithm each robot must observes its nearest right and left neighbours at least once. Generally, the upper and the lower boundaries of the strips are same as that of the whole region, if there is only one robot within a strip. In case, more than one robots are located on the same vertical line, the upper and the lower boundaries of their strips are computed in a different way. In that case, whenever a robot finds another robot positioned vertically upward or downward (having the same x coordinate), it calculates the upper boundary or lower boundary of its strip, through the midpoint of the line joining them.

Algorithm Paint

Phase I: All the variables used in this algorithm are listed in Table 1 along with their description and initial values.

Table 1.

Variables to be considered by the robots R together with their descriptions and initial values.

Variables	Descriptions	Initial values	Does robot retain the current value?
UB	Upper boundary of the assigned strip	Not seen	Yes
LoB	Lower boundary of the assigned strip	Not seen	Yes
LB	Left boundary of the assigned strip	−d	Yes
RB	Right boundary of the assigned strip	d	Yes
state	Direction of robot’s movement	Upward	Yes
$(X_{d}, Y_{d})$	Co-ordinate of the next destination	(0, 0)	No
$Y_{u p}$	Ordinate of the immediate neighbour seen vertically above	∞	Yes
$Y_{l o w}$	Ordinate of the immediate neighbour seen vertically below	−∞	Yes
Phase I completed	Completion of first phase	False	Yes
Wait	Robot is waiting	False	Yes
Timer	Waiting time of the robot	0	Yes
$(X_{L}, Y_{L})$ )	Coordinate of the nearest left neighbour of R	–	No
$(X_{R}, Y_{R})$	Coordinate of the nearest right neighbour of R	–	No

Observe

According to the local co-ordinate system, the robot R first observes the position of the neighbours within its area of visibility. Suppose, the robot R have $n - 1$ number of visible neighbours. Let their co-ordinates be $(a_{1}, b_{1})$ , $(a_{2}, b_{2})$ ,…., $(a_{n - 1}, b_{n - 1})$ and its own coordinate be (0, 0). If any one of the two boundaries (left/right) is visible to R, it observes the distance of the boundary from itself. Let the distance be k. If robot R finds any other robot(s) on the same vertical line, it identifies the coordinates of the nearest upper robot P (if any) and the nearest lower robot Q (if any) as $(0, p)$ and $(0, q)$ , respectively.

Compute

Table 2.

Destination Coordinate $(X_{d}, Y_{d})$ based on UB, LoB and state values.

UB	LoB	Wait	state	$(X_{d}, Y_{d})$
Not seen	Not seen	False	Upward	$(0, \frac{d}{2})$
Seen	Not seen	False	Downward	$(0, - \frac{d}{2})$
Not seen	Seen	False	Upward	$(0, \frac{d}{2})$
Seen	Seen	False	Downward	$(0, min (\frac{d}{2}, y))$ (When lower boundary is at a vertical distance y from R)
Seen	Seen	True	Painting	$(0, 0)$
Seen	Seen	False	Painting	$(L B, 0)$

UB: upper bound; LoB: lower bound

Move

In this step, the robot moves to the destination point $(X_{d}, Y_{d})$ as calculated in the compute step. After reaching the destination, if $s t a t e = P a i n t i n g$ and $W a i t = F a l s e$ , the robot sets $P h a s e I C o m p l e t e d = T r u e$ . This signifies that phase I is completed, and the robot can start painting the assigned area, from the current position.

Phase II: In this phase, the robot executes the painting operation. Within a finite amount of time, robot R completes the job successfully, without any interruption as painting is an atomic operation.

Correctness proof

Observation I: As discussed in ‘Problem definition, assumptions and models’ section, the time required to complete one computational cycle is approximately $(T_{0} + \frac{d}{2 v})$ . Therefore, we can say that the time gap between two consecutive observe steps of a robot is at the most $(T_{0} + \frac{d}{2 v})$ , where v is the velocity of the robot. Hence, regarding observation, as if the whole time domain is discretized for the robots.

Suppose, R₁ and R₂ be two robots, moving with velocity v₁ and v₂, respectively, such that initially $h d i s t [R_{1}, R_{2}] \leq D *$ . Let, initially R₁ and R₂ are at a vertical distance x, such that $x > d$ . That is, initially R₁ and R₂ are not visible to each other. Moreover, let us assume R₁ is closer to the upper boundary than R₂. In the beginning of the algorithm R₁ and R₂ both move in the upward direction, that is, in the same direction. There may arise three possible cases: (1) R₁ and R₂ with the same velocity, that is, $v_{1} = v_{2}$ , (2) R₁ is moving faster than R₂, that is, $v_{1} > v_{2}$ , but $v_{1} \leq r v_{2}$ , (3) R₂ is moving faster than R₁, that is, $v_{2} > v_{1}$ , but $v_{2} \leq r v_{1}$ . In case (1), the vertical distance of R₁ and R₂ would remain same, that is, x as long as they move in the same direction. R₁ observes the upper boundary earlier and starts moving in the downward direction while R₂ still moving in the upward direction. This time, their vertical distance would reduce gradually and in due course they will see each other once they fall in the visibility range of each other, as discussed in lemma I. In case (2) also, R₁ observes the upper boundary earlier than R₂. In case (3), R₂ may observe the upper boundary earlier than R₁. However, both the cases (2) and (3) can be explained in a similar way as explained in lemma II. However, in cases (2) and (3), initial distribution must satisfy a condition as stated in lemma II.

Lemma I

If the robots move with equal speed, during the first phase of the algorithm, a robot observes its nearest left and right neighbours at least once.

Proof

When two consecutive robots, say R₁ and R₂ (nearest left and right neighbours of each other), move in opposite directions they must pass through the visibility circle of each other. In case, a robot has more than one nearest neighbour (left or right) on the same vertical line, at least one of them would pass through the visibility circle of the robot. We consider the following two cases separately.

Case (I): When R₁ and R₂ are moving in the same direction (say upward direction).

In this case, since they are moving with the same velocity, the vertical distance between them remain same as long as they move in the same direction. Hence, initially if they are not visible to each other, as long as they move in the same direction, they do not become visible to each other.

Case (II): When R₁ and R₂ are moving in the opposite direction.

Figure 1(a) describes this situation when R₁ and R₂ are moving in the opposite direction. When R₁ is at A, let R₂ be at B. R₁ takes the snapshot of its surroundings at A and then at A′. By the time R₁ reaches A′, R₂ reaches B′ passing through the visibility range of R₁. We are to prove that either R₁ from A observes R₂ at B or R₁ from A′ observes R₂ at B′.

Figure 1.

Illustrations for the proof of lemma I.

Here, $A A^{'} = B B^{'} = \frac{d}{2}$ . At A, if R₁ cannot see R₂, then $A B > d$ . In the parallelogram $A^{'} B B^{'} A$ , if the other diagonal is less than d, then R₁ observes R₂ at B′. In a parallelogram, if both the diagonals become equal, then it becomes a rectangle. Thus, in the worst case, we assume that $A^{'} B B^{'} A$ is a rectangle, with a diagonal d as shown in Figure 1(b). In this case, B is visible from A and B′ is visible from A′. However, if R₂ is just outside the visibility range of R₁ at A, say R₂ is at B₁, where $A B_{1} > d$ , then in the parallelogram $A A^{'} B_{1} {B^{'}}_{1}$ , the other diagonal must be less than d. Hence, the position ${B^{'}}_{1}$ is visible from A′. Thus, if R₂ (at B) is not visible to R₁ at A, then R₂ must be visible to R₁ at A′, and vice versa, provided the horizontal distance between R₁ and R₂ is at the most $A^{'} B = \sqrt{d^{2} - {(\frac{d}{2})}^{2}} = \frac{\sqrt{3} d}{2} = d *$ .

It can be noted here that a parallelogram with two opposite hands (of size $\frac{d}{2}$ ) on the lines L₁ and L₂ can have both the diagonals greater than d. However, in that case, the path $B B^{'}$ is entirely outside the visibility range of R₁ as shown in Figure 1(c).

According to our initial assumption the initial distribution of robots is d*-dense. Hence R₁ must see R₂ either from A or from A′. Now, if R₂ halts at B and B′ for taking snapshot, the same argument holds for R₂ also. Otherwise, if at B, R₂ is in motion, then it must halt somewhere in between B and B′ from where it observes R₁ on $A A^{'}$ since $A A^{'}$ is then entirely within the visibility range of R₂. Hence, the result. □

Lemma II

If it is given that the ratio between the velocities of two robots can be at the most r, a robot observes its nearest left and right neighbours at least once if the initial distribution is D*-dense, where, $D * = \frac{d}{4} \sqrt{(3 - r) (r + 5)}$ , d is the visibility range of the robots.

Proof

Herein, we consider the two cases separately when two consecutive robots move in the same direction or opposite.

Case (I): Let us first consider the case when two consecutive (horizontally) robots R₁ and R₂, which are the nearest left and right neighbours to each other, are moving in the opposite direction along the vertical line passing through their initial position and they pass through each other’s visibility range. Let us assume that R₂ is moving faster than R₁.

Let A and A′ denote the positions of the robot R₁ in two successive computational cycles from where R₁ takes the snapshot of the surroundings in the observe step as shown in Figure 2. Let R₂ be at the horizontal distance $d - k$ from R₁. When R₁ is at A, let R₂ be at a position just above B, from where it is not visible to A. By the time R₁ reaches A′ in time $\frac{d v_{2}}{2 v_{1}}$ (v₁ is the velocity of R₁), R₂ should not cross the distance $B B^{'}$ to be in the visibility range of R₁ at A′. $ε < d v_{2} 2 v_{1} \leq B B^{'} + ε$ , where R₂ is at a height ε from B when R₁ is at A. Hence, it is sufficient to consider $\frac{d v_{2}}{2 v_{1}} \leq B B^{'}$ . Now, $B B^{'} = B C + C C^{'} + C^{'} B^{'} = 2 \sqrt{k (2 d - k)} - \frac{d}{2}$ . Hence

\frac{v_{2}}{v_{1}} \leq \frac{4 \sqrt{k (2 d - k)}}{d} - 1

Figure 2.

Illustrations for the proof of case I of lemma II.

It is required to be pointed out here that when we consider $B B^{'} > A A^{'} = \frac{d}{2}$ , that is, R₂ is moving through a distance greater than $\frac{d}{2}$ , it undergoes more than one, say m number of computational cycles. Hence, there is an overhead of $m T_{0}$ halting time over the time required by R₂ to cross $B B^{'}$ . In the above calculation this overhead is not considered and hence lowered the upper bound of the relative velocity without hampering the purpose.

From lemma I and our initial assumption, k cannot be less than $d (1 - \frac{\sqrt{3}}{2})$ . Now, (as right side of equation (1) is an increasing function of k) the minimum value of the right side of equation (1) occurs when k is minimum, that is, when $k = d (1 - \frac{\sqrt{3}}{2})$ . When $k = d (1 - \frac{\sqrt{3}}{2})$ , $B B^{'}$ becomes equal to $A A^{'}$ and hence, $\frac{v_{2}}{v_{1}}$ becomes 1, that is, $v_{2} = v_{1}$ . This, once again shows the validity of lemma I.

From equation (1), we can say that the upper bound of $\frac{v_{2}}{v_{1}}$ depends on the value of k. The permissible upper bound of $\frac{v_{2}}{v_{1}}$ inversely varies with the horizontal distance between R₂ and R₁, that is, $d - k$ . In an alternative way, we can view the situation as follows:

Suppose, it is given that $\frac{v_{2}}{v_{1}}$ is at the most r. The proposed algorithm is valid for such a situation, when initial configuration is D*-dense, where $r \leq \frac{4 \sqrt{(d - D *) (2 d - d + D *)}}{d} - 1 \Rightarrow D * \leq \frac{d}{4} \sqrt{(3 - r) (r + 5)}$ .

Case (II): When R₁ and R₂ are moving in the same direction.

A situation may arise, when two robots R₁ and R₂ never move in the same direction. In particular, say R₁ is initially on the top boundary, R₂ is on the lower boundary of the region and they move with equal speed. Thus, they never move in the same direction provided there are no other robots on their vertical lines. Hence, case II should not be considered in drawing any conclusion.

Hence, on the basis of case I, we can conclude that when it is given that the ratio between the velocities of two robots can be at the most r, the proposed algorithm is valid for D*-dense initial distribution, where $D * = \frac{d}{2} \sqrt{(3 - r) (r + 5)}$ . □

Corollary

Since D* is real and greater than 0, r cannot be more than 3 in any case. Thus, $1 \leq r < 3$ and when $r = 1$ , D* reduces to d*.

Now, in case more than one robots are on the same vertical line initially, these robots need to compute the upper and/or lower boundaries of their strips without any conflict.

Lemma III

After viewing a robot on the same vertical line, to make a total agreement with it regarding the common boundary between them, a robot have to wait a maximum of $(\frac{r d}{2 v} + 3 T_{0})$ time, where v is the velocity of the robot, r is a given upper bound on the ratios of the velocities of any two robots: $1 \leq r < 3$ , and T₀ is the maximum time required by a robot to complete the observe and compute step.

Proof

We assume that two robots R₁ and R₂ are deployed on the same vertical line and let v₁ and v₂ be the velocities of R₁ and R₂, respectively. They may or may not view each other initially. Suppose R₁ finds R₂ on the same vertical line during the vertical movement in phase I. To come to a total agreement with R₂, regarding the common boundary, R₁ has to ensure that R₂ observes R₁ in its current position. Thus, in the absence of direct communication, the only option for R₁ is to wait at that position for some time to make itself visible to R₂. The same reason holds for R₂ also. Thus, if a robot finds another robot on the same vertical line, it does not change its position for few computational cycles. R₁ waits at the same position until it observes R₂ at the same position for two consecutive observe phases to understand that robot R₂ is not changing its position. Moreover, it has to wait there for some more time to give R₂ an opportunity that R₂ also observes R₁ in the same position for two consecutive observe phases. When the robots do not move, the time gap between its two consecutive observe steps is T₀.

Figure 3 shows the timelines of two robots R₁ and R₂, which are initially deployed on the same vertical line. Suppose R₁ first observes R₂ on the same vertical line at the time instance A. At time A, the distance between R₁ and R₂ is less than d. However, if R₂ is not in its observe step, R₂ does not see R₁ at time A. In the worst case, after $\frac{d}{2 v_{2}}$ time (maximum time for a move phase of R₂) R₂ observes R₁ on the same vertical line if their distance is still less than d. Let that instance be B. Meanwhile, during the time period from A to B, R₁ observes R₂ (their distance is still less than d) in different positions because of $R_{2}'s$ motion. Now R₂ stays at the same position and carry out only observe step to finalize the common boundary. In the next observe step, at time B₁, R₂ observes R₁ in the same position second time as it was at the time instance B. At B₁, R₂ records the position of R₁. However, after B₁, R₂ does not move, it stays in the same position for one more computational cycle to let R₁ observe its identical positions at the time instances A₁ and A₂. At time A₂, R₁ records the position of R₂ and wait in the same position for one more cycle, till A₃. Thus, the maximum waiting time for R₁ is $\frac{d}{2 v_{2}} + 3 T_{0}$ . As R₁ has no idea about v₂, it assumes that R₂ is very slow and in the worst case, $v_{2} = \frac{v_{1}}{r}$ as it is mentioned in the given condition. Thus, the maximum waiting time for a robot is $(r d 2 v_{1} + 3 T_{0})$ . If the robots have equal velocities, this upper bound is reduced to $(\frac{d}{2 v} + 3 T_{0})$ , v is the velocity of the robot.

Figure 3.

Timelines for R₁ and R₂. Black dots on the timelines indicate the instances of when R₁ and R₂ are passing through observe state.

During the time between A and B, R₁ observes R₂ on the same vertical line if their distance is less than d. During that period, R₁ updates the position of R₂ staying in the same position. If R₂ goes beyond the distance d, R₁ goes back to its normal action resuming vertical movement. □

Lemma IV

For successfully identifying the proper right and left boundary of the strip to be painted, a robot must wait T_w amount of time on the lower boundary of its strip before starting phase II, where $T_{w} = (⌈ \frac{4 L}{d} ⌉ + 6) T_{0} + [(1 + r) ⌈ \frac{2 L}{d} ⌉ + r] \frac{r d}{v} .$

Proof

By lemmas I and II, we can say that if two neighbouring robots (their hdist is less than D*) traverse the whole path from their initial positions to the upper boundary of the region and then to the lower boundary, then during their journey they must recognize each other provided they do not move more than r times faster than each other. However, if the robots are initially deployed in such a way that more than one robot fall on the same vertical line, then they do not need to traverse the whole path.

One such situation is described in Figure 4, where robots R₁ and R₂ are on the same vertical line initially and R₃ is the nearest right neighbour (nrn) of them. According to our algorithm, in this case, R₂ observes R₁ on the same vertical line, it fixes the upper boundary and then start moving in the downward direction to reach lower boundary to start painting. Similarly R₁ also fixes its lower boundary following the same rule and then start moving towards upper boundary of the region. Thus, R₁ and R₂ do not traverse the whole path from their initial positions to upper boundary and then to the lower boundary of the region. The question may arise here that: Do they $(R_{1} and R_{2})$ recognize R₃ during their movement in phase I of the algorithm to fix their right boundary? Let us consider a situation where initially R₁ and R₂ are visible to each other and R₃ is occupying a position just outside the circle of visibility of robot R₂. In phase I, R₂ does not need to traverse in the upward direction. In that case, it may be possible that R₂ completes its journey in phase I and reach the lower boundary without observing its nearest right neighbour (nrn) R₃. Because of this fact, before starting phase II, every robot should wait for some time to identify its unique nearest right (nrn) or left (nln) neighbour.

Figure 4.

Illustrations for the proof of lemma IV.

For calculating the waiting time, let us consider Figure 4. Let us assume that R₂ is initially at a height h from the lower boundary of the region. As we have assumed that initially R₁ is visible to R₂, R₂ fixes its upper boundary in the very beginning and in phase I R₂ needs to move only in the downward direction to get ready for painting. However, if we assume that R₃ is not visible to R₂ initially, then R₂ cannot start painting until it observes R₃, that is, until R₃ reaches the lower boundary.

Initially R₃ is at least at a distance of $(h + d sin θ + ε)$ (as indicated in Figure 4) from the lower boundary of the region, where ε is a very small positive quantity and $0 \leq θ < 90 °$ . So to reach the lower boundary, R₃ has to traverse a distance of $2 L - (h + d sin θ + ε)$ , where L is the length of the region. To traverse this distance, R₃ takes $⌈ \frac{(2 L - h - d sin θ - ε)}{\frac{d}{2}} ⌉ (T_{0} + \frac{d}{2 v_{3}})$ unit of time, since in one computational cycle R₃ moves a distance of $\frac{d}{2}$ with velocity v₃ and time taken in each computational cycle is $(T_{0} + \frac{d}{2 v_{3}})$ . In this time calculation, we assume that R₃ does not wait anywhere during this movement. Considering the situation described in lemma III, R₃ may need to wait somewhere during its vertical movement for computing its upper boundary. In the worst case, R₃ may need to wait at the most $\frac{r d}{2 v_{3}}$ amount of time between every consecutive move. And finally, it needs at the most $2 [\frac{r d}{2 v_{3}} + 3 T_{0}]$ time to finalize both its upper and lower boundaries, if required. Hence, the total waiting time is $[⌈ \frac{2 (2 L - h)}{d} ⌉] \cdot \frac{r d}{2 v_{3}} + 2 \frac{r d}{2 v_{3}} + 6 T_{0},$ since maximum number of computational cycles could be $⌈ \frac{2 (2 L - h)}{d} ⌉ .$ Therefore, maximum time required by R₃ to reach the lower boundary is $⌈ \frac{(2 L - h - d sin θ - ε)}{\frac{d}{2}} ⌉ (T_{0} + \frac{d}{2 v_{3}}) + ⌈ \frac{2 (2 L - h)}{d} ⌉ \frac{r d}{2 v_{3}} + \frac{r d}{v_{3}} + 6 T_{0} .$

However, minimum value of v₃ as expected by R₂ is $\frac{v_{2}}{r}$ , where v₂ is the velocity of R₂. Moreover, waiting time would be maximum when $h + d sin θ + ε = 0$ . Hence, before starting painting, every robot should wait $⌈ \frac{4 L}{d} ⌉ (T_{0} + \frac{d}{2 v_{3}}) + ⌈ \frac{4}{L d} ⌉ \frac{r d}{2 v_{3}} + \frac{r d}{v_{3}} + 6 T_{0} \leq (⌈ \frac{4}{L d} ⌉ + 6) T_{0} + [(1 + r) ⌈ \frac{4 L}{d} ⌉ + 2 r] \frac{d}{2 v_{3}} \leq (⌈ \frac{4 L}{d} ⌉ + 6) T_{0} + [(1 + r) ⌈ \frac{2 L}{d} ⌉ + r] \frac{r d}{v} = T_{w}$ amount of time, where v is the velocity of the robot.

The expression for T_w shows that for a faster robot, waiting time is less compared to a slower one. However, it can be noted that the upper bound derived here is quite a loose upper bound. Depending on all possible variations in initial distribution and speed, the worst case is considered. For example, for the robots that are placed on the same vertical line, to fix the upper and lower boundaries (at least one) they require at the most six extra computational cycles. However, in that case they do not need to traverse the whole of 2L distance. □

Theorem I

The whole region is painted by the robots without any overlapping, and the process is completed within a finite amount of time.

Proof

In the initial distribution, a robot may not observe its nearest neighbours. In those cases, robots determine its strip boundaries on the basis of the positions of its visible nearest neighbours. Thus, the initial formation may result in overlapping strips. During the movement of a robot in phase I, first towards upper boundary and then towards lower boundary, robots, being able to observe the position of their nearest neighbours at least once (by lemmas I, II and IV), can uniquely and unanimously determine the strip boundaries (left and right). Lemma III shows that the upper and lower boundaries are also computed without any conflict. Hence, the strips defined by the robots are non-overlapping. Moreover, as we have assumed that the boundaries of the region are visible to at least one robot initially, all the strips defined by the robots cover the whole region.

That is, the set of all strips determined by the robots defines a partition over the whole region. Thus, the whole region is painted by the robots without any repeated painting, provided the initial distribution of robots over the given region is d*-dense, where $d * = \frac{\sqrt{3} d}{2}$ and velocities of all robots are equal. In case of variable velocities, the initial distribution has to be D*-dense, where $D * = \frac{d}{4} \sqrt{(3 - r) (r + 5)}$ and r is a given upper bound on the ratios of the velocities of two robots.

Theorem II

The movement of the robots are collision free.

Proof

In phase I of the algorithm, each robot moves only in the vertical direction (first upward and then downward) along the line passing through their initial position. Since no two robots can occupy the same position, their lines of movement are distinct, except for those robots whose initial positions are on the same vertical line. If two or more robots are located on the same vertical line, they are always able to view the robot(s) just above and/or below it, once they fall in the visibility range of each other (by lemma III). It can be pointed out here that in each computational cycle, they can see up to a distance d but moves through a distance at the most $\frac{d}{2}$ . Once a robot is able to view any such robot it does not move anymore. Rather, both wait for some amount of time to find the common boundary between them. Once both of them make an agreement on the common boundary they do not move beyond it. So, there is also no chance for collision.

Time calculation

Let us once again ‘mention’ the parameters that would influence the total time taken by a robot for completion of phase I: (i) L: vertical length of the rectangular area, (ii) d: visibility radius, T₀: maximum time taken by a robot to execute observe and compute steps and (iv) v: velocity of the robot.

Now, as discussed in lemma IV, if all the robots start their computation at the same time, then the maximum time required to reach the lower boundary is $(⌈ \frac{4 L}{d} ⌉ + 6) T_{0} + [(1 + r) ⌈ \frac{4 L}{d} ⌉ + 2 r] \frac{d}{2 v}$ . Moreover, after reaching the lower boundary, a robot has to wait T_w amount of time, as shown in lemma IV. Hence, the total time required by a robot to complete phase I is

T = 2 (⌈ \frac{4 L}{d} ⌉ + 6) T_{0} + [(1 + r) ⌈ \frac{2 L}{d} ⌉ + r] (1 + r) \frac{r d}{v}

where v is the velocity of the robot, r is a given upper bound on the ratios of the velocities of any two robots; $1 \leq r < 3$ , T₀ is the maximum time required by a robot to complete the observe and compute step. Therefore, T is maximum when v is the velocity of the slowest robot. However, when all robots complete their phase I and phase II, the job of painting the area is completed.

Thus, the total time of completion depends on the computational capacity (affecting T₀), hardware (affecting v) and accessories (can influence d) used by the robots. An e-puck robot, that is used for educational purposes, uses Microchip dsPIC microcontroller with 8 kb RAM and 144 kb flash memory, two miniature stepper motors having speed of 1000 steps/s (controls the robot wheels), proximity sensors with 10–100 Hz capacity (measures the distance of an obstacle from the robot), a colour CMOS camera with resolution 640 × 480 colour pixels, and so on.¹³ However, a Koala 2.5, a mid-sized robot designed for real-world applications, uses Dual Core Intel Atom N2800, 1.86 GHz with hyper threading, 4 GB RAM, 40 GB SSD, 2 DC brushed motors with incremental encoders with speed 0.6 m/s (max) and 0.011 m/s (min), 9× ultrasonic sensors that measures distance to the object (range 25–250 cm).¹⁴

Simulation and experimental results

With the help of Player [version 3.2.2]/Stage [version 3.0.2] multi-robot simulation software, the first phase of the proposed algorithm has been simulated to show that the strips are computed correctly within a finite amount of time. It is quite obvious that if a robot can successfully complete phase I within the finite amount of time it would definitely be able to paint the assigned strip within finite time. However, painting procedure and required time of phase II depends on the accessories used by the robots to paint the area which depends on actual implementation. Moreover, the simulation shows that their movements are collision-free.

Simulation environment

For simulation the Player/Stage multi-robot simulation software is used, which is configured on Ubuntu 10.04 (Lucid Lynx) platform. Intel Core2Duo Processor with 3.00 GHz speed and 2.00 GB RAM provided as a hardware support to the Player (version 3.2.2) and Stage (version 3.0.2) software. Several robots are randomly positioned within an obstacle-free rectangular region with fixed boundaries and known dimensions.

The simulation uses 15 green coloured robots with $(1 \times 1 \times 1 unit)$ dimension randomly distributed within a rectangular area surrounded by a red coloured wall of width 1 unit. The breadth of this rectangular field is kept fixed at 35 unit with varying length. The initial locations of these robots are generated in such a way that the distribution is d*-dense. Although the proposed algorithm is meant for point robots only, we have to consider dimension for simulation since Player/Stage does not provide any option for point robots. The robots are loaded with the following devices: (i) Infrared Laser sensors of varying range, attached at the left and right sides of the robots, (ii) Sonar ranger sensors of varying range, attached at the front of the robot, (iii) Blobfinders: attached at the left and right side of the robot to make it capable to recognize red and green colours. Every robot executes a controller program that implements the proposed algorithm, written in C++ language. The library $l i b p l a y e r c + +$ is used to connect the player with the Stage. The observe–compute–move steps are executed sequentially by the controller program. To make a robot able to execute the controller program independently from others, the robots are programmed as different threads.

The local coordinate systems of each robots have identical direction and orientation as the global system and thus full-compass. The robots have equal speed since Player/Stage supports neither unequal speed for the robots nor asynchronicity among them. Thus, in effect, the algorithm has been simulated for a synchronous system. In the changed scenario, the time calculated in ‘Time calculation’ section is no more a good upper bound. A tighter bound can be calculated in a straight forward way as $⌈ \frac{4 L}{d} ⌉ + 6$ , as $⌈ \frac{4 L}{d} ⌉$ number of cycles are required to travel a distance of $2 L$ and a robot may need to wait (if required at all) at the most two times, each for a duration of 3 cycles to fix its upper and lower boundaries.

Results

We have represented the results according to two different categories of the parameters involved in the simulation. In the first category, in Table 3, simulation results are shown by varying the values of L and d, keeping the ratio $\frac{L}{d}$ fixed. Table 4 compares the results for varied $\frac{L}{d}$ ratio. In all these cases, the other dimension (breadth) of the region and the number of robots are kept fixed. Both the tables include scenarios for three different $(L, d)$ pairs. For each $(L, d)$ pair, four tests are conducted by varying the initial distribution of the robots. Table 5 shows the initial distribution of all the 15 robots in each of the four tests corresponding to the second entry of Table 4.

Table 3.

$\frac{L}{d}$ is fixed.

Sl. no.	No. of robots	L	d	$\frac{L}{d}$	Observed $M a x_{cycles}$				Theoretical upper bound of $M a x_{cycles}$
Sl. no.	No. of robots	L	d	$\frac{L}{d}$	Test 1	Test 2	Test 3	Test 4	Theoretical upper bound of $M a x_{cycles}$
1	15	32	4	8	24	28	27	22	32 + 6
2	15	40	5	8	28	29	30	21	32 + 6
3	15	48	6	8	29	28	26	29	32 + 6

L: length; d: visibility range.

Table 4.

$\frac{L}{d}$ is not fixed.

Sl. no.	No. of robots	L	d	$\frac{L}{d}$	Observed $M a x_{cycles}$				Theoretical upper bound of $M a x_{cycles}$
Sl. no.	No. of robots	L	d	$\frac{L}{d}$	Test 1	Test 2	Test 3	Test 4	Theoretical upper bound of $M a x_{cycles}$
1	15	40	4	10	30	35	32	29	40 + 6
2	15	30	5	6	22	22	23	18	24 + 6
3	15	33	6	$\frac{11}{2}$	21	21	20	22	22 + 6

L: length; d: visibility range.

Table 5.

Initial distribution of the robots corresponding to the second row of Table 4 with L = 30, d = 5.

Robot	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	Max _cycles
Test 1	(−14, −8)	(−10, −5)	(−10, 2)	(−7, −1)	(−14, 4)	(−3, 2)	(0, 13)	(2, 3)	(4, −2)	(4, 7)	(4, 12)	(7, 2)	(10, −2)	(15, −1)	(15, 4)	22 + 6
Test 2	(−14, 0)	(−12, 4)	(−10, 6)	(−10, −14)	(−6, 4)	(−6, −12)	(−3, 0)	(−3, −8)	(0, −4)	(3, 0)	(6, 3)	(8, 0)	(8, 7)	(12, −3)	(15, −6)	22 + 6
Test 3	(−13, −12)	(−9, −14)	(−9, −9)	(−7, 8)	(−5, 8)	(−5, −12)	(−2, 4)	(0, −12)	(3, −8)	(11, 7)	(7, −5)	(7, 1)	(7, 7)	(7, 12)	(11, −2)	23 + 6
Test 4	(−16, −4)	(−11, −4)	(−7, −4)	(−3, −1)	(−1, 3)	(−5, 6)	(−9, 6)	(−14, 6)	(1, −1)	(3, 3)	(8, 3)	(13, 3)	(5, −4)	(10, −4)	(15, −4)	18 + 6

L: length; d: visibility range.

In each of the cases, we compared the observed value of $M a x_{c y c l e s}$ with the upper bound computed theoretically. In all the cases, the computed values are well within the theoretical upper bound. We have also included the case, when more than one robots are lying on the same vertical line, which is dealt specially in the proposed algorithm. For example, test 3 of Table 4, shows that robots 11, 12, 13 and 14 are on the same vertical line. Robots 10, 15 and robots 2, 3 are also on the same vertical line. On the other hand, initial distribution of test 4 shows none of the robots are on the same vertical lines. As expected in general, completion time of test 3 is more than test 4. In all the tests, the controller program was successfully completed within a finite amount of time. All the robots successfully completed phase I after fixing its strip boundaries and reached the lower boundary of the corresponding strips without any collision.

Conclusion

This article presents an algorithm to paint a known rectangular region by a swarm of identical, simple, autonomous robots with limited visibility. The robots do not have any type of information exchange among themselves. The only information a robot gets about its visible neighbours is their positions as observed in definite time interval. The solution of the algorithm is designed for asynchronous robots following the basic CORDA model. The robots have full-compass local coordinate system. The algorithm guarantees complete coverage of the given region within a finite amount of time without any repetition. The proposed algorithm is valid only for a D*-dense initial distribution, where $D * = \frac{d}{4} \sqrt{(3 - r) (r + 5)}$ , where r is a given upper bound on the ratios of the velocities of two robots, $1 \leq r < 3$ . This is definitely a limitation of the proposed solution. Although, in case of limited visibility, without any visibility restriction, it is difficult to avoid repeated coverage if the already covered areas are not identifiable. Finally, the algorithm has been simulated when the robots have equal velocities using Player/Stage robotic simulator. The observed results of the simulation tally with the estimated bound on time. As a future research, one can think of painting a region of different shape (both concave and convex). The problem can also be extended by considering the presence of obstacles inside the region. Several different models can also be examined for suitability to design a solution.

Footnotes

Authors’ note

This article is a revised and expanded version of the paper entitled ‘Painting an Area by Swarm of Mobile Robots with Limited Visibility’,¹⁵ presented at 6th International Conference on Information Processing at Bangalore, Karnataka, India during 10–12 August 2012.

Acknowledgements

The authors are grateful to the anonymous reviewers whose concern and suggestions help in improving the presentation and correctness of the article.

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Stormont

. Autonomous rescue robot swarms for first responders. In: Proceedings of IEEE international conference on computational intelligence for homeland security and personal safety (CIHSPS ‘05), Orlando, FL, 31 March–1 April 2005, pp. 151–157. New York: IEEE.

Tan

(ed). Handbook of research on design, control, and modeling of swarm robotics, 1st ed. Hershey, PA: IGI Global, 2016, p. 854. DOI: 10.4018/978-1-4666-9572-6.

Das

Mukhopadhyaya

. An algorithm for painting an area by swarm of mobile robots. Int J Inform Proc 2013; 7(3): 1–15.

Kong

Peng

Rekletis

. Distributed coverage with multi-robot system. In: Proceedings of IEEE international conference on robotics and automation (ICRA ‘06), Orlando, FL, 15 – 19 May 2006, pp. 2423–2429. IEEE.

Latimer

Srinivasa

Lee-Shue

. Toward sensor based coverage with robot teams. In: Proceedings of IEEE international conference on robotics and automation (ICRA ‘02), Washington, DC, USA, 11 – 15 May 2002, pp. 961–967. IEEE.

Rekletis

Lee-Shue

New

. Limited communication, multi-robot team based coverage. In: Proceedings of IEEE international conference on robotics and automation (ICRA ‘04), New Orleans, LA, USA, 26 April – 1 May 2004, pp. 3462–3468. IEEE.

Rekletis

New

Rankin

. Efficient boustrophedon multi-robot coverage: an algorithmic approach. Ann Math Artificial Int 2008; 52(2–4): 109–142. DOI: 10.1007/s10472-009-9120-2.

Prencipe

. Corda: distributed coordination of a set of autonomous mobile robots. In: Proceedings of 4th European research seminar on advances in distributed systems (ERSADS, ‘01), Bertinoro, Italy, 14–18 May 2001, pp. 185–190.

Flochinni

Prencipe

Santoro

. Gathering of asynchronous robots with limited visibility. Theor Comput Sci 2005; 337(1–3): 147–168.

10.

Fazli

Davoodi

Pasquier

. Fault-tolerant multi-robot area coverage with limited visibility. In: Proceedings of ICRA 2010 workshop on search and pursuit/evasion in the physical world: efficiency, scalability and guarantees, Anchorage, Alaska, USA, 3–8 May 2010.

11.

Fazli

Davoodi

Pasquier

. Complete and robust cooperative robot area coverage with limited range. In: Proceedings of IEEE/RSJ international conference on intelligent robotics and systems (IROS ‘10), Taipei, Taiwan, 18–22 October 2010, pp. 5577–5582. IEEE.

12.

Jiao

Tang

. A visibility-based algorithm for multi-robot boundary coverage. Int J Adv Robot Syst 2008; 5(1): 63–68. DOI: 10.5772/1.

13.

Mondada

Bonani

Raemy

. The e-puck, a robot designed for education in engineering. In: G Paulo

T Paulo

A Carlos

(eds) Proceedings of conference of autonomous robot systems and competitions, Castelo Branco, Portugal, 7 May 2009, pp. 59–65. Portugal: Instituto Politécnico de Castelo Branco (IPCB).

14.

Koala 2.5 User Manual. 2016. http://ftp.k-team.com/koala2.5/UserManual/Koala2.5_User_Manual.pdf (accessed 25 April 2016).

15.

Das

Mukhopadhyaya

. Painting an area by swarm of mobile robots with limited visibility. In: Venugopal

Patnaik

(eds) Proceedings of international conference on information processing (ICIP ‘12), Bangalore, India, 10 – 12 August 2012, pp. 446–455. CCIS Springer. Berlin, Heidelberg: Springer.

Distributed algorithm for painting by a swarm of randomly deployed robots under limited visibility model

Abstract

Keywords

Introduction

Related work

Problem definition, assumptions and models

Coverage algorithm

Description of the algorithm

Observe

Move

Correctness proof

Lemma I

Proof

Lemma II

Proof

Corollary

Lemma III

Proof

Lemma IV

Proof

Theorem I

Proof

Theorem II

Proof

Time calculation

Simulation and experimental results

Simulation environment

Results

Conclusion

Footnotes

Authors’ note

Acknowledgements

Declaration of conflicting interests

Funding

References