Scalable Coverage Path Planning for Cleaning Robots Using Rectangular Map Decomposition on Large Environments

 

ABSTRACT

The goal of coverage path planning is to create a path that covers the entire free space in a given environment. Coverage path planning is the most important component of cleaning robot technology, because it determines the cleaning robot’s movement. When the environment covered by a cleaning robot is extremely large and contains many obstacles, the computation for coverage path planning can be complicated. This can result in signi_cant degradation of the execution time for coverage path planning. Not many studies have focused on the scalability of coverage path planning methods. In this paper, we propose a scalable coverage path planning method based on rectangular map decomposition. The experimental results demonstrate that the proposed method reduces the execution time for coverage path planning up to 14 times when compared with conventional methods.

EXISTING SYSTEM :

For the past two decades, coverage path planning (CPP) has been regarded as an important research issue in the intelligent robot community for popular applications that include demining robots, lawn mowers , and harvesting robots. The goal of CPP is to create a path that covers the entire free space in a given known or unknown environment . Although the goal of covering the entire free space can be achieved by employing the well-known random walk process because the random walk-based direction control suffers from path repetition , many researchers have dedicated efforts to developing more efficient and effective CPP methods. For example, a cleaning robot, which is a popular robotic application, can extend cleaning time unnecessarily and waste its battery by cleaning the same locations multiple times if unplanned direction control is involved. To overcome this drawback, many strategic CPP methods have been proposed for indoor/outdoor cleaning scenarios. A basic CPP procedure can be described as follows. First, the cleaning robot attempts to identify the boundary of the given environment by following the outermost wall (or obstacle). After returning to its initial position, the robot creates a map representing the environment. Next, the robot begins cleaning map using a coverage path such as spiral or zigzag . At the cleaning process, the robot can be surrounded by previously cleaned space; the current position of the robot at this moment is known as a blind alley. To escape the blind alley situation, a path planning method such as the Dijkstra algorithm  is invoked to identify the robot’s next cleaning position. Finally, these tasks are repeated until there is no uncleaned space. The majority of CPP methods use strategies based on grid information gathered in the process of cleaning. However, grid-based strategies require significant computational cost, which increases thetotal execution time. Recently, demands have emerged from industrial communities for efficient and effective cleaning robots that can cover significantly larger environments such as libraries, warehouses, stadiums, and airports. When conventional CPP methods are used in these large-spaced environments, the results are unsatisfactory because of the large number of grids used in the process. To efficiently address these, the CPP method to control the cleaning robots must be scalable to the size of any given environment. However, to the best of our knowledge, there remains a lack of studies focused on the scalability of CPP methods

PROPOSED SYSTEM :

we propose a scalable coverage path planning method based on rectangular map decomposition. The experimental results demonstrate that the proposed method reduces the execution time for coverage path planning up to 14 times when compared with conventional methods. It is a scalable CPP method for extremely large environments based on rectangular sub-map and boundary edges to accelerate the CPP process. To achieve this, we developed a new map decomposition method that uses a spiral path for large, unknown environments.

CONCLUSION :

In this paper, we proposed a scalable CPP method for extremely large environments based on rectangular sub-map and boundary edges to accelerate the CPP process. To achieve this, we developed a new map decomposition method that uses a spiral path for large, unknown environments. The experimental results on large maps demonstrated that the proposed method created the final coverage path without expending excessive computational resources for path planning, resulting in a significant acceleration of the cleaning process. Conversely, the conventional methods required considerably greater execution times on large maps than the proposed method, indicating that the proposed method is considerably more scalable than conventional CPP methods for sizable environments. Specifically, CPP using the proposed method was up to 14 times faster than CPP using conventional methods. A possible extension of this study could focus on the map selection process that selects the next cleaning submap by Euclidean distance from a set of created sub-map. Alternatively, the proposed approach could lengthen the final coverage path compared to conventional methods because the proposed method uses boundary and decomposition edges as opposed to diagonal edges, which can’t shorten the final coverage path. The proposed method could solve some of the problems of conventional studies. However, its limitations include battery shortage when applying the method on a larger map with a single cleaning robot and sudden malfunctions. To solve these problems, we plan to expand the method into a multi cleaning robot system and test the method in real environments.