Multi-robot systems can provide effective solutions for exploring and inspecting environments where it is unpractical or unsafe for humans, however, adequate coordination of the multi-robot system is a challenging initiative. A robust and efficient methodology for exploration of unknown environments is presented using a k-means method to improve traditional task allocation schemes. The k-means method proposed is an efficient technique due to the algorithm’s quick convergence time and its ability to segment a previously unknown map in a logical manner. In this method, a global executive receives frontiers from local robots, filters them, clusters them using the k-means method, and then reassigns them to the agents. A framework is developed in Robot Operating System (ROS) to test the effectiveness of the k-means method. The method is tested over a series of simulations and real-world tests, where it provided significant reductions in exploration time and distance travelled compared to other methods.