Abstract: This paper studies the problem of cooperative coverage by multiple simple robots. Addressing the limitation that simple robots can only perceive the external environment using contact sensors, a multi-robot internal spiral coverage algorithm based on grid map representation is proposed for online coverage planning. This method achieves complete environmental coverage by repeatedly covering portions of the environment and setting GATE grids. Furthermore, this method ensures that coverage can be completed as long as one robot does not malfunction, thus improving system stability. Finally, simulation experiments verify the feasibility of the proposed method. Keywords: Multiple simple robots; Coverage algorithm; Complete coverage; Stability The algorithm improves system stability in the sense that coverage can be cometed if only one robot is not in catastrophic failure. Simulation experiment proves the feasibility of the algorithm. Keywords: multi-simple-robot; coverage algorithm; complete coverage; stability 1 Introduction Many application areas of robots require the use of coverage algorithms, such as detecting landmines, cleaning the ground, creating maps, etc. These application areas require robots (or robot detectors) to cover all areas in the environment that are not occupied by obstacles. In an unknown environment, the robot must use its own onboard sensors to perceive the environment and plan the coverage path. This task is called sensor-based coverage task [1]. Due to its parallelism, multi-robot systems can improve system efficiency, shorten the time to complete the task, and other robots can still complete the task when a single robot fails, thereby improving system stability. Therefore, the research on multi-robot coverage tasks has attracted more and more attention. Multi-robot coverage tasks can be divided into offline and online planning based on the knowledge of the environment. In offline planning, the robot knows the environment map in advance, so the coverage task and motion path are planned and assigned to each robot before the coverage begins, as in the literature [2]. Reference [2] is an extension of the single-robot STC (spanning tree covering) algorithm. Before covering, the covering path represented by a grid is assigned to each robot. During the covering process, each robot communicates with each other. If a robot fails and stops moving, the robot behind it will complete the task of the failed robot after completing its own task. The paper also discusses the influence of the robot's starting position on the covering efficiency. In online multi-robot covering, Rekleitis et al. studied the covering problem of multiple robots with local communication capabilities [3]. The paper uses two robots that can only communicate when they are visible to each other to explore the environment and divide the covering units. Other robots cover according to the divided units. Wagner et al. studied the multi-robot covering problem of ant colony algorithm [4]. They assumed that the robots communicate by leaving information similar to insect pheromones on the map and coordinate each robot to complete the task together. In these studies, the robots are equipped with external sensors that can perceive the environment within a certain range, or the environment map is known. This is not applicable to simple robot covering in unknown environments. Simple robots refer to robots that are only equipped with contact sensors and internal ranging sensors [5]. This paper proposes a Multi-robot Internal Spiral Coverage (MISC) algorithm for simple robots. This algorithm is implemented based on the author's proposed Internal Spiral Coverage (ISC) algorithm. 2. Introduction to the ISC Algorithm (ISC algorithm) The ISC algorithm uses a simple circular robot to cover the environment. This algorithm is an online coverage algorithm based on a grid map, assuming that the robot's global coordinates can be accurately obtained from the robot's internal ranging sensor (odometer). The ISC algorithm consists of two phases during the coverage process: a boundary exploration phase and an online coverage phase. In the boundary exploration phase, the robot starts from any vertex in the environment and moves around the environment boundary on its right side. During the exploration, the grid cell where the robot's right-side contact sensor is located is assigned a value of 0, indicating that the cell cannot be covered; the grid cell the robot has passed is assigned a value of 1, indicating that the cell has been covered; and the grid cell on the robot's left side is assigned a value of 2, indicating the grid cell to be covered in the next loop, i.e., the online planned coverage path. Therefore, after the boundary exploration phase ends, the environmental boundary is obtained, the robot completes one circle of coverage near the boundary, and plans the movement path for the next circle, then enters the online coverage phase. In the online coverage phase, the robot moves along the continuous grid with a value of 2 generated in the previous circle. During the movement, it assigns a value of 1 to the grids it has already passed (grids with a value of 2) and assigns a value of 2 to the grids to its left that have not yet been assigned a value. When the second circle of coverage ends, the coverage path for the third circle is generated, and the robot spirals inward in this way to complete the coverage of all areas. If there are obstacles inside the environment, the obstacles will block the planned path, causing the grids with a value of 2 to become discontinuous. However, the obstacle will be detected by the contact sensor in front of the robot during the next circle of coverage. The robot will still move around the obstacle by walking along the object boundary on its right side until a grid with a value of 2 reappears in front of it, at which point the robot returns to the original planned path to continue the original coverage. For common single rectangular environments, the above method can complete complete coverage by spiraling inward from the environmental boundary. However, for complex environments consisting of multiple rooms, problems will occur at the entrances of each room. Because the entrance to a room is narrower than the spaces on either side, as shown in Figure 1, when there are still uncovered areas on both sides of the entrance, this narrower area is covered first. Therefore, the concept of a GATE grid is introduced. Definition 1: If a grid is already assigned a value of 1 or 2 when its value is to be assigned a value of 2, and there are uncovered grids (grids with a value of 2) on its left, front, and back, then this grid is called a GATE grid. In Figure 1, when the robot moves from room B to room A along MN and wants to assign a value of 2 to segment PQ, segment PQ has already been planned and assigned a value of 2 during the robot's previous rotation. Therefore, a GATE grid is set in segment PQ, and then room A is completely covered. If no GATE grid is defined, the robot will cover the OQ (Obtaining Q) first and assign it a value of 1, breaking the connectivity between the uncovered parts of rooms A and B, preventing the robot from entering room A for coverage. Therefore, when a GATE grid appears, the robot records its position and first completes the coverage of one side of the GATE grid. When there are no grids with a value of 2 on that side of the GATE grid, it indicates that the side is completely covered, and the robot returns to the GATE to continue covering the other side until there are no grids with a value of 2 in the entire environment, indicating that complete coverage has been achieved, and the algorithm ends. 3. Multi-robot Intra-spiral Coverage Algorithm (MISCalgo-rithm) In multi-robot coverage tasks, each robot shares the environment map, that is, all robots share their covered and planned grid information with other robots. Suppose that k robots jointly complete the environmental coverage. 3.1 Multi-robot Collaborative Boundary Coverage Exploration: K robots are randomly distributed along the environmental boundary, moving simultaneously along the right side of the boundary and recording environmental information. The k robots divide the environmental boundary into k segments, with the shortest segment being the m-th segment, explored by robot m. When robot m reaches the initial position of the (m+1)-th robot, it will find that the grid in front of it has been assigned a value of 1, and the grid to its left front has been assigned a value of 2. Robot m then ends the boundary exploration phase and moves to the second ring of grids planned by robot m+1 to begin the online coverage phase. Similarly, other robots transition to the online coverage phase when they reach the initial position of the next robot and move along the path planned by that next robot. 3.2 Multi-robot Online Coverage After entering the online coverage phase, each robot (taking the m-th robot as an example) moves along the path planned by the next (m+1-th) robot in the previous lap, while simultaneously planning the next lap's path for the previous (m-1) robot, until the entire environment is completely covered. When obstacles appear within the environment, similar to the ISC algorithm, the robot switches to an exploration mode, moving along the obstacle boundary on the right, until a grid with a value of 2 reappears in front of the robot, at which point the robot reverts to online coverage mode. For irregularly shaped environments, as shown in Figure 2, there is a branch-like protrusion on one side of the environment. When the height CD of the uncovered part of the protrusion is greater than 3d (d is the grid side length), the planning is carried out as described above. When CD = 3d, after robot m covers B→C→D→E, the uncovered part is a T-shaped "dead end" with a height of d. Robot m-1 will move along this path to vertex C and find that there is no planned path around it. Then ml searches in the shared map for the grid with the closest value of 2 (the grid at point E) to its current position, and the robot moves to that point to continue the original coverage. If CD = 2d, when robot m reaches point C along B→C, only D→E is a planned path. If m is very close to m, and m-1 reaches point E before m completes its coverage from D to E, m-1 will also move along E to D, inevitably meeting m in segment DE. At this point, neither robot has a planned path to follow, and the robot searches for the nearest grid cell with a value of 2 (below point E). Then ml rotates 180 degrees and moves backward along D to E, while m continues to move forward (for ease of description, the numbers of robots m-1 and m are swapped so that robot m is always ahead of ml). When the new robot m reaches point E, it returns to the path planned by m+1 and continues coverage, while robot m-1 also moves along the path planned online by m. In multi-robot coverage scenarios, coverage may be completed first at the room entrance. Therefore, GATE grids are set at these locations, but each robot has its own independent GATE grid. As shown in Figure 3, when robot m enters the room along MN, it sets segment PQ as the GATE grid and completes full coverage of the room. When robot m-1 reaches point P along RP, because segment PQ is not a grid with a value of 2, but rather PS is the path planned when a robot left room A in the previous loop, robot m-1 moves along PS. After completing full coverage of the room, robot m returns to its own set GATE grid. The GATE grid is covered in reverse order. If all the GATE grids are covered and a grid with a value of 2 is found around the first GATE grid, it means that robot m-1 is far away from m and has not yet reached point P. In this case, robot m can move along PS. If there is no grid with a value of 2 nearby, it means that robot m-1 has already covered path PS and assigned it a value of 1. In this case, m stops moving because it cannot find a path. Because at least one robot will stop moving because the path at the GATE grid is covered by another robot, the MISC algorithm can achieve complete coverage of all areas. 4. Algorithm Analysis The algorithm analysis section mainly discusses the coverage completeness and system stability of the MISC algorithm. 4.1 Coverage Completeness Analysis For common rectangular environments, the MISC algorithm can achieve complete coverage by spiraling inward layer by layer. When there are no obstacles inside the environment, robot m moves continuously along the path planned by m+1 without repetition, while simultaneously planning the next loop's movement path for m~1, until a T-shaped path appears or a GATE grid appears as the coverage path spirals inward. As shown in Section 3.2, when a T-shaped path appears, robots m-1 and m can partially cover the T-shaped path to exit the T-shaped path and continue the original coverage. Furthermore, the next loop's path planned online by robot m-1 for robot m-2 is no longer affected by the T-shaped path but is a straight line. When a GATE grid appears in a narrow space, robot m enters one side of the GATE grid to cover it, while simultaneously setting the GATE grid to prevent other robots from entering that side. Therefore, this narrow area and the side covered by robot m can be covered by other robots. Treating obstacles as inaccessible (and not requiring coverage) solves the problem of uncovered path connectivity being interrupted in narrow areas. After robot m completes one side of the GATE grid and full coverage of the GATE grid, it continues coverage if a path can be found; otherwise, it stops. If an unknown obstacle exists within the environment, and robot m+1 did not detect it during the previous path planning, then the obstacle is located on the robot's movement path. When robot m reaches the obstacle, it moves around it by moving along the object boundary on its right until it returns to its original path. Simultaneously, the path planned for robot m-1 directly bypasses the obstacle and is no longer affected by it. Therefore, if no fault occurs, the robot only stops moving when it cannot find a path at the GATE grid and after full environmental coverage. However, as shown in Section 3.2, at least one robot will not stop moving due to the GATE grid. Therefore, the MISC algorithm can achieve complete environmental coverage. 4.2 System Stability Analysis Since each robot plans its next coverage path in real time during its movement, assigning a value of 2 to the grid on its left, and moving along the grid path with a value of 2 during the coverage phase, the robot is unaware of which robot planned its path, or even that multiple robots are collaborating on the coverage. The advantage of this is obvious: if a robot suddenly malfunctions and stops moving during the coverage process, it has no impact on the other robots. Assuming robot m stops moving during coverage, when robot m-1 catches up with robot m, it simply treats robot m as an obstacle, moves around it on its right, and continues executing the original movement path. Robot m has no further impact on the remaining coverage task. Similarly, adding or removing a robot during the coverage process will not affect other robots. Therefore, as long as not all robots malfunction, the MISC algorithm can achieve complete environmental coverage, improving system stability. 5. Simulation Test of Multi-robot Cooperative Coverage This paper simulates a multi-robot coverage task in an indoor environment on a simulation platform. The experiment uses a color recognition-based method to simulate contact sensors, meaning that obstacles can only be detected when a robot makes contact with an obstacle (pixel overlap). The environment is a 900×700 rectangular room divided into three smaller rooms, with the entrance narrower than the sides. A small number of obstacles are randomly distributed within the environment, covered by three 20×20 circular robots. As shown in Section 3.2, the greater the distance between two robots, the less likely the robot in front will stop moving prematurely due to the GATE grid. Therefore, the three robots are distributed as evenly as possible along the environmental boundary. In this paper, the robots are distributed at the three corners and begin boundary exploration simultaneously. As shown in Figure 4(a), when robot 2 reaches the initial position of robot 3, the online coverage phase begins. In the figure, gray grids represent grids containing obstacles, horizontal grids represent covered areas, and diagonal grids represent... The grid represents the planned path. In Figure 4(b), robot 2 enters the upper left room and sets up the GATE grid, represented by vertical grid lines. After completely covering the upper left room, robots 1 and 3 will no longer enter that room. In Figure 4(c), after robot 2 covers the upper left room and the GATE grid, robot 1 has already covered the area near the first GATE grid. Therefore, robot 2 cannot find the planned path and stops moving. Furthermore, as the coverage progresses, robot 3 first detects the triangular obstacle inside the room. The robot navigates around the obstacle boundary. Figure 4(d) shows the movement trajectories of each robot after complete coverage. The solid black line represents the movement trajectory of robot 1, the dashed black line represents robot 2, and the solid gray line represents robot 3. There are a total of 1117 coverable grids in the environment, all of which are covered. Robot 1 completed the coverage of 454 grids in 493 steps, robot 2 completed the coverage of 223 grids in 230 steps, and robot 3 completed the coverage of 440 grids in 456 steps. The coverage repetition rate of the entire system is 5.55%. 6 Conclusion This paper proposes a multi-simple robot cooperative coverage algorithm—MISC algorithm. This algorithm ensures complete coverage of the environment by repeatedly covering some areas of the environment and setting GATE grid. Since each robot only uses the shared map during online planning and does not consider the influence of other robots, the system stability is improved, ensuring that as long as one robot does not fail, the complete coverage of the environment can be completed. The algorithm is simple to implement and is suitable for simple robots with low configuration. References [1] Butler Z, Rizzi A, Hollis R. Contact sensor-based coverage of recti-linear environments[A]. Proceedings of the 1999 IEEE International Symposium on Intelligent Control／Intelligent Systems and Semi-mioties[C]. Piseataway, NJ, USA: IEEE, 1999 266—271. [2] Hazon N, Kaminka G. Redundancy, efficiency and robustness in multi robot coverage[A]. Proceedings of the IEEE International Conference on Robotics and Automation[C]. Piseataway, Nj, USA: IEEE, 2005. 1199-1205. [3]Rekleitis I, Lee-Shue V, Peng A, a1. Limited communication, multi-robot team based coverage[A]． Proceedings of'the IEEE International Conference on Robotics and Automation[C]． Pisca-taway, NJ, USA: IEEE, 2004. 3462-3468. [4]Wagner I, Lindenbaum M, Bruckstein A. Distributed covering by ant-robots using evaporating traces[J]． IEEE Transactions on Robotics and Automation, 1999, 15(5): 918-933. [5]Rekleitis I, Dudek G, Milios E. Multi-robot exploration of an un-known environment, efficiently~dueing the odometry eu'or[A]. Proceedings of the 15th International Joint Conference in Artificial Intelligence [C]. San Francisco, USA: Morgan Kaufmann Publishers Inc., 1997. 1340-1346. About the authors: Hao Zongbo (1977-), male, PhD student. Research areas: service robots, intelligent robots. Hong Bingchun (1937-), male, PhD, professor. Doctoral supervisor. Research areas: service robots, robot soccer, virtual reality.