Abstract This paper addresses the problem of building a communication map of a known environment using multiple robots. A communication map encodes whether two robots are likely to be able to communicate between two arbitrary locations. Such a communication map is fundamental for reliably deploying a multirobot system to accomplish a variety of tasks, including exploration and environmental monitoring. Previous work proposed offline approaches, which did not utilize data measured by robots. This paper, utilizing Gaussian Processes, proposes methods to efficiently build a communication map with multiple robots. Specifically, the number of measurements used to update the communication map, and the number of possible candidate locations where robots should go are reduced, by exploiting communication models that can be built from the physical map of the environment. This allows robots to take fewer measurements, travel less distance, be more efficient in processing the data online, and get similar accuracy to methods that consider all the locations in the environment. Experiments with a team of TurtleBot 2 platforms validate the approach.