Abstract: A multi-region coverage method based on cost map and minimal tree is proposed. First, the cost of cells in priori static map is determined, and then the static map is turned into a dynamic cost map. Then, the cost map is divided into several regions, which are decomposed into sub-regions using Boustrophedon cellular decomposition. Finally, a graph is built according to the adjacency relationship between the sub-regions, in which each node represents a sub-region. The sub-region planning method based on minimal tree is applied to the graph to generate a sub-region planning sequence, the algorithm based on the cost map and Dijkstra algorithm is used to plan a transfer path among different regions, and back and forth coverage strategy is applied to every sub-region to complete the coverage. The multi-region coverage method is applied to completing coverage in different environments on-line, and experimental results show that our algorithm has advantages in improving the efficiency of coverage over traditional methods.