We studied the problem of designing optimal multi-agent trajectories to patrol an environment which is large w.r.t. the number of agents. Agents must continuously travel in order to periodically cover the whole environment but they can communicate with other agents only when "in visibility" and the inter-distance is small enough. As performance criteria for optimal patrolling we considered the worst-case time gap between any two visits of the same region and the latency for a message to be transferred from any to any robot in the group.