BoB: an online coverage approach for multi-robot systems

摘要

Online complete coverage is required in many applications, such as in floor cleaning, lawn mowing, mine hunting, and harvesting, and can be performed by single- or multi-robot systems. Motivated by the efficiency and robustness of multi-robot systems, this study proposes a solution to provide online complete coverage through a boustrophedon and backtracking mechanism called the BoB algorithm. This approach designs robots in the system according to a market-based approach. Without a central supervisor, the robots use only local interactions to coordinate and construct simultaneously non-overlapping regions in an incremental manner via boustrophedon motion. To achieve complete coverage, that is, the union of all covered regions in the entire accessible area of the workspace, each robot is equipped with an intelligent backtracking mechanism based on a proposed greedy A* search (GA*) to move to the closest unvisited region. The robots complete the coverage task when no more backtracking points are detected. Computer simulations show that the BoB approach is efficient in terms of the coverage rate, the length of the coverage path, and the balance of the workload distribution of robots.