The multi-robot forest coverage for weighted terrain1

Article type: Research Article

Authors: Gorbenko, Anna | Popov, Vladimir^{; *}

Affiliations: Department of Intelligent Systems and Robotics, Ural Federal University, Lenin st., 51, 620083 Ekaterinburg, Russian Federation, Tel.: 73433507579; Fax: 73433507579. E-mail: gorbenko.aa@gmail.com

Correspondence: [*] Corresponding author. E-mail: popovvvv@gmail.com.

Abstract: Different multi-robot solutions are very important for intelligent environments. Robots can perform various physical tasks and provide us with information, communication, and entertainment. Frequently, the effective usage of robotic systems requires solutions of different hard problems. The multi-robot forest coverage is one of such problems. This paper is devoted to the consideration of efficient algorithms for the problem of the multi-robot forest coverage for weighted terrain. In particular, it is considered an explicit reduction from the decision version of the problem of the multi-robot forest coverage for weighted terrain to the satisfiability problem. For different satisfiability algorithms, the results of computational experiments with the real-world data, the synthetic terrains with the real-world weights, and the special hard terrains are presented. Also, a genetic algorithm for the direction solution to the problem of the multi-robot forest coverage for weighted terrain is proposed.

Keywords: Multi-robot forest coverage, NP-complete, satisfiability problem, genetic algorithms

DOI: 10.3233/AIS-150352

Journal: Journal of Ambient Intelligence and Smart Environments, vol. 7, no. 6, pp. 835-847, 2015