Hierarchical Oriented Genetic Algorithms for Coverage Path Planning of Multi-robot Teams with Load Balancing

ÖZKAN M., YAZICI A., Kapanoglu M., Parlaktuna O.

World Summit on Genetic and Evolutionary Computation (GEC 09), Shanghai, Çin, 12 - 14 Haziran 2009, ss.451-458 identifier identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası:
  • Doi Numarası: 10.1145/1543834.1543895
  • Basıldığı Şehir: Shanghai
  • Basıldığı Ülke: Çin
  • Sayfa Sayıları: ss.451-458
  • Eskişehir Osmangazi Üniversitesi Adresli: Evet

Özet

Multi-robot coverage path planning problems require every point in a given area to be covered by at least one member of the robot team using their sensors. For a time-efficient coverage, the environment needs to be partitioned among robots in a balanced manner. So the problem can be modeled as task assignment problem with load balancing. In this study, we propose two oriented genetic algorithms working in a hierarchical manner to deal with this problem. In the First phase, a previously proposed oriented genetic algorithm is used to find a single route with minimum repeated coverage. In the following phase, a directed genetic algorithm is used to partition the route among robots considering load balancing. The algorithm is coded in C++ and simulations are conducted using P3-DX mobile robots, in the MobileSim environment. The hierarchical oriented genetic algorithm (HOGA) is also compared to the multi-robot spanning tree coverage (STC) approach in terms of load balancing. The comparison indicates competitive results over multi-robot STC.