An algorithm of dividing a work area to multiple mobile robots

Proposes an algorithm of dividing a work area into small pieces in order to make multiple mobile robots cooperate efficiently. Searching of a whole work area is the most fundamental and the most essential task of mobile robots. The authors expect that the cost of searching is shared by cooperation of multiple robots. In the proposed algorithm, searching motions of robots are represented by paths. Both edges of the configuration space and the Voronoi diagram are introduced so as to compute paths in the whole area. The authors generate a tour of the paths to traverse all the paths using the algorithm of the Chinese postman problem. The cost is estimated as the total length of the paths. By means of the cost evaluation, the appropriate paths are assigned to each robot. The efficiency of the proposed algorithm is verified by simulations.