Abstract: After coal mine disasters, the environment deteriorates and rescue tasks are complex and arduous, resulting in numerous threats to the rescue personnel. Robot participation in rescue can effectively improve rescue efficiency and safety, but existing remote sensing rescue robots suffer from problems, e.g., inability to communicate in real-time. Therefore, in response to the complex post-disaster downhole environment, a multi-robot autonomous exploration method based on the extended undirected graph is proposed, aiming at studying the collaborative search and rescue of a multi-robot autonomous exploration system to further improve rescue efficiency. Firstly, based on the characteristics of the downhole environment and the needs of post-disaster rescue, the architecture and algorithm flow of the multi-robot autonomous exploration system for coal mine rescue are constructed by combining local and global planning strategies to address the issues of computational efficiency and spatial exploration depth in autonomous exploration. Secondly, when conducting local rescue exploration, there is a special environment where narrow and open spaces coexist, making the multi-robot system difficult to quickly sample and generate local exploration paths. This situation can result in premature termination of rescue tasks. Therefore, the traveling salesman problem is integrated, where each robot performs viewpoint sampling and exploration gain calculation in the local space to construct a local map and determine the points to be visited. The A * algorithm is used to optimize the shortest exploration path in the local map. Moreover, when the local graph exploration gain is insufficient, global graph exploration is performed. Each robot shares the global maps and expands them incrementally to reduce the overall efficiency decline caused by multiple robots directly accessing the target point. The collaborative global map search algorithm solves the shortest path for each robot's global map exploration. Finally, three different models of robots are used for real experiments and compared with commonly used multi-robot autonomous exploration algorithms based on boundary point methods. The results show that the multi-robot autonomous exploration method proposed in this paper improves exploration completeness by 51% and saves exploration time by more than 58%. The proposed method can effectively achieve multi-robot autonomous exploration tasks in complex environments.