Abstract: Heterogeneous robot introduce a higher perception ability than single type robots in outdoor environments. One key problem is to making the 3D environmental model from the cooperated robots in real time, especially in the unstructured environment. Based on our previous work on outdoor environment registration method, in this paper, we introduce a GPU based Enhanced ICP method for large-scale heterogeneous robot registration. First, we combine the GPU-based nearest neighbor search in the traditional ICP framework. Second, we proposed a measurement and estimation model for the local minima problem. Third, we proposed a GPU-based heuristic escape method to generate the escaping transformation in real time. Experiments involving one unmanned aerial vehicle and one unmanned surface vehicle were conducted to verify the proposed technique. The experimental results were compared with those of normal ICP registration algorithms to demonstrate the performance of the proposed method.