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.
A.E.Brouwer, A.M.Cohen and A.Neumaier, Distance-Regular Graphs, Springer-Verlag, 1989.
2.
F.Bullo, J.Cortes and S.Martinez, Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms, Princeton University Press, 2009.
3.
M.Chatterjee, S.K.Das and D.Turgut, WCA: A weighted clustering algorithm for mobile ad hoc networks, Cluster Computing5 (2002), 193–204.
4.
W.Chin and S.Ntafos, Optimum watchman routes, in: Proc. of the Second Annual Symposium on Computational Geometry, 1986, pp. 24–33.
5.
J.Cortes, S.Martinez, T.Karatas and F.Bullo, Coverage control for mobile sensing networks, IEEE Transactions on Robotics and Automation20 (2004), 243–255.
6.
J.Cortez, S.Martinez and F.Bullo, Spatially-distributed coverage optimization and control with limited-range interactions, ESIAM: Control, Optimisation and Calculus of Variations11 (2005), 691–719.
7.
J.Czyzowicz, L.Gasieniec, A.Kosowski and E.Kranakis, Boundary patrolling by mobile agents with distinct maximal speeds, in: Proc. of 19th European Symposium on Algorithms, 2011, pp. 701–712.
8.
A.Davoodi, P.Fazli, P.Pasquier and A.K.Mackworth, On multi-robot area coverage, in: Proc. of the 7th Japan Conference on Computational Geometry and Graphs, 2009, pp. 75–76.
9.
K.Easton and J.W.Burdick, A coverage algorithm for multi-robot boundary inspection, in: Proc. of the IEEE International Conference on Robotics and Automation, 2005, pp. 727–734.
10.
S.Eidenbenz, Inapproximability results for guarding polygons without holes, Lecture Notes in Computer Science1533 (1998), 427–436.
11.
L.Erickson and S.M.LaValle, An art gallery approach to ensuring that landmarks are distinguishable, in: Proc. Robotics: Science and Systems, 2011, pp. 1–5.
12.
L.Erickson and S.M.LaValle, How many landmark colors are needed to avoid confusion in a polygon? in: Proc. of IEEE International Conference on Robotics and Automation, 2011, pp. 1–5.
13.
L.Erickson and S.M.LaValle, Navigation among visually connected sets of partially distinguishable landmarks, in: Proc. of IEEE International Conference on Robotics and Automation, 2012, pp. 1–8.
14.
M.R.Garey and D.S.Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979.
15.
A.Gorbenko, M.Mornev and V.Popov, Planning a typical working day for indoor service robots, IAENG International Journal of Computer Science38 (2011), 176–182.
16.
A.Gorbenko, M.Mornev, V.Popov and A.Sheka, The problem of sensor placement for triangulation-based localisation, International Journal of Automation and Control5 (2011), 245–253.
17.
A.Gorbenko, M.Mornev, V.Popov and A.Sheka, The problem of sensor placement, Advanced Studies in Theoretical Physics6 (2012), 965–967.
18.
A.Gorbenko and V.Popov, The set of parameterized k-covers problem, Theoretical Computer Science423 (2012), 19–24.
19.
A.Gorbenko and V.Popov, Task-resource scheduling problem, International Journal of Automation and Computing9 (2012), 429–441.
20.
A.Gorbenko and V.Popov, Programming for modular reconfigurable robots, Programming and Computer Software38 (2012), 13–23.
21.
A.Gorbenko and V.Popov, The far from most string problem, Applied Mathematical Sciences6 (2012), 6719–6724.
22.
A.Gorbenko and V.Popov, On the problem of sensor placement, Advanced Studies in Theoretical Physics6 (2012), 1117–1120.
23.
A.Gorbenko and V.Popov, SAT solvers for the problem of sensor placement, Advanced Studies in Theoretical Physics6 (2012), 1235–1238.
24.
A.Gorbenko and V.Popov, Clustering algorithm in mobile ad hoc networks, Advanced Studies in Theoretical Physics6 (2012), 1239–1242.
25.
A.Gorbenko and V.Popov, The problem of selection of a minimal set of visual landmarks, Applied Mathematical Sciences6 (2012), 4729–4732.
26.
A.Gorbenko and V.Popov, A real-world experiments setup for investigations of the problem of visual landmarks selection for mobile robots, Applied Mathematical Sciences6 (2012), 4767–4771.
27.
A.Gorbenko and V.Popov, Computational experiments for the problem of selection of a minimal set of visual landmarks, Applied Mathematical Sciences6 (2012), 5775–5780.
28.
A.Gorbenko and V.Popov, On the problem of placement of visual landmarks, Applied Mathematical Sciences6 (2012), 689–696.
29.
A.Gorbenko, V.Popov and A.Sheka, Localization on discrete grid graphs, Lecture Notes in Electrical Engineering107 (2012), 971–978.
30.
N.Hazon, F.Mieli and G.A.Kaminka, Towards robust on-line multi-robot coverage, in: Proc. of the IEEE International Conference on Robotics and Automation, 2006, pp. 1710–1715.
31.
L.Jiao and Z.Tang, A visibility-based algorithm for multi-robot boundary coverage, International Journal of Advanced Robotic Systems5 (2008), 63–68.
32.
J.King and E.Krohn, Terrain guarding is NP-hard, SIAM Journal on Computing40 (2011), 1316–1339.
33.
D.Lee and A.Lin, Computational complexity of art gallery problems, IEEE Transactions on Information Theory32 (1986), 276–282.
34.
S.P.Lloyd, Least squares quantization in PCM, IEEE Transactions on Information Theory28 (1982), 129–137.
35.
A.N.Nazif, A.Davoodi and P.Pasquier, Multi-agent area coverage using a single query roadmap: A swarm intelligence approach, in: Advances in Practical Multi-Agent Systems, 2011, pp. 95–112.
36.
Neato Robotics web page. [Online]. Available, http://www.neatorobotics.com/.
37.
J.O’Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987.
O.Tekdas and V.Isler, Sensor placement for triangulation based localization, IEEE Transaction on Automation Science and Engineering7 (2010), 681–685.
40.
D.Turgut, S.K.Das, R.Elmasri and B.Turgut, Optimizing clustering algorithm in mobile ad hoc networks using genetic algorithmic approach, IEEE Global Telecommunications Conference1 (2002), 62–66.
41.
K.Williams and J.Burdick, Multi-robot boundary coverage with plan revision, in: Proc. of the IEEE International Conference on Robotics and Automation, 2006, pp. 1716–1723.
42.
X.Zheng, S.Koenig, D.Kempe and S.Jain, Multi-robot forest coverage for weighted and unweighted terrain, IEEE Transactions on Robotics26 (2010), 1018–1031.
43.
X.Zhong and Y.Zhou, Maintaining wireless communication coverage among multiple mobile robots using fuzzy neural network, in: IEEE/ASME International Conference on Mechatronics and Embedded Systems and Applications, 2012, pp. 35–41.
