The Mobile robots are increasingly being used to perform tasks in unknown environments. The potential of robots to undertake such tasks lies in their ability to intelligently and efficiently search in an environment. An algorithm has been developed for robots which explore the environment to measure the physical properties (dust in this paper). While the robot is moving, it measures the amount of dust and registers the value in the corresponding grid cell. The robot moves from local maximum to local minimum, then to another local maximum, and repeats. To reach the local maximum or minimum, simple gradient following is used. Robust estimation of the gradient using perturbation/correlation, which is very effective when analytical solution is not available, is described. By introducing the probability of each grid cell, and considering the probability distribution, the robot doesn’t have to visit all the grid cells in the environment still providing fast and efficient sensing. The extended algorithm to coordinate multiple robots is presented with simulation results.