In this paper we consider the problem of searching an unknown number of targets in static environment by a team of robots. As the targets positions and distribution are uncertain; the goal is to minimize the overall exploration time. Using cell maps, the key problem can be solved choosing the suitable cell for the individual robots so that they simultaneously explore different regions of the environment. We present an intelligent approach for the coordination of multiple robots, in which contrast to previous approaches, able to perform task allocations taking into account the trade-off between the costs of reaching the cell and its utility. This utility function has been modeled using neural networks and optimized with genetic algorithms. Besides, if the task produces some conflict between robots, a negotiation algorithm is used to collision avoidance. The proposed approach has been implemented in real-world experiments and its performance tested in simulation runs. The results given in this paper demonstrate that our coordination mechanism significantly reduces the exploration time and increase the effectiveness compared to previous approaches.