A Hierarchical Multi Robot Coverage Strategy for Large Maps With Reinforcement Learning and Dense Segmented Siamese Network

Abstract

Complete coverage of multiple robots for a large map is an important collaborative planning task, which is widely used in disaster search and rescue, forest fire prevention, resource exploration, and other fields. It generally focuses on coverage completion with less robot (mostly drone) occupation and higher time efficiency. However, as the map becomes larger, most existing works will fail to remain near-optimal due to escalating complexity. In this letter, we formulate the problem as two levels of traveling salesman problem (TSP) to reduce the complexity, where the lower level is single-robot local coverage planning with preset TSP solutions, and the higher level is multiple TSP (mTSP) global planning executed by multiple robots. To better adapt to dynamic scenarios, we apply a distributed multi-agent reinforcement learning (MARL) framework that allows efficient online computation, and a dense segmented Siamese network (DSSN) to achieve efficient and effective solutions. We show that compared to existing advanced methods, our strategy can effectively solve the problem with coverage costs decreased by over 30<inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\%$</tex-math></inline-formula> average and the execution time reduced to seconds in large maps. Furthermore, our network DSSN achieves an additional improvement with random settings to the previous mTSP architecture. We also discuss the influence of different robot densities and separated block sizes on the results, and demonstrate the adaptability to irregular and large-scale obstacles.