Methods, apparatus, systems, and computer-readable media are provided for selectively deploying robots to performing mapping based on added cost. In various implementations, a measure of interest in mapping an area of an environment may be determined. A cost associated with a robot performing a task may also be determined. Then, an added cost associated with the robot mapping the area of the environment while performing the task may be determined. The robot may be selectively deployed to map the area while performing the task in response to a determination that the measure of interest justifies the added cost.