Abstract
Demand for Genetic Algorithms (GA) in research and market applications has been increasing considerably. This can be explained through big data and the necessity of interpreting them in an automatic, efficient and intelligent way. In the case of intelligent systems for unmanned vehicles there are two well-defined subsystems: autonomous and robotic navigation. Despite the present day’s good development of the latter, taking the best decisions is an essential robot’s attribute that can only be acquired with the former. This work presents a fully programmed GA for a robot to walk around a planar graph G with the highest efficiency. Each robot’s action is one among five kinds of genes, and fourteen of them build a chromosome, namely a sequence of actions for the robot to walk all around G. The efficiency of a chromosome is given by the number of visited vertices and the amount of saved energy, which are both computed by a fitness function. Our GA returns near-optimal chromosomes for the robot to clean the whole reflection pool with the least energy consumption. Our Coverage Path Planning differs from others in the literature because they consider obtaining a near-optimal sequence of vertices for the robot to follow in that order. Moreover, for such a sequence they do not allow vertex repetitions, whereas in our developed algorithm the robot can pass more than once in a same vertex, with the objective of guaranteeing a lower energy consumption. This objective already makes our best chromosomes avoid repeating vertices, as we have observed in our experiments.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abramson, S., Levin, A., Levin, S., Gur, D.: Window cleaning robot. US Patent App. 15/370,209 (2016)
Roumagnac, M.: Pool cleaning robot. US Patent 7,805,792 (2010)
Garti, E.: Pool cleaning robot. US Patent App. 11/896,611 (2009)
Baek, B.K.: Vacuum cleaner robot. US Patent App. 29/294,635 (2009)
Zhang, Y., Zhang, W., Bi, J.: Recent Patents on Mechanical Engineering 10(1), 30 (2017)
Fabris, A.E., Nascimento, M.Z.d., Batista, V.R.: Revista SODEBRAS (9), 168 (2014)
Wang, C., Tang, Y., Zou, X., SiTu, W., Feng, W.: Optik-International Journal for Light and Electron Optics 131, 626 (2017)
Zampirolli, F.d.A., Quilici-Gonzalez, J.A., Ramos Batista, V.: In: 6th IASTED International Conference on Modelling, Simulation and Identification, vol. 1, pp. 25–31 (2016)
Pichon, P., Deloche, R., Blanc-Tailleur, P.: Swimming pool cleaning apparatus with extractable filtration device. US Patent 9,657,488 (2017)
Renaud, B.J., Renigar, S.D., Hayes, G.M., Osuna, O.E.: Pool cleaning device with wheel drive assemblies. US Patent 9,677,294 (2017)
van der Meijden, H.J., Moore, M.E., Harbottle, B.D., Klimas, D.A., Bauckman, M.J.: Automatic pool cleaners and components thereof. US Patent 9,611,668 (2017)
Corke, P.: Robotics, vision and control. Springer, Berlin (2013)
Mitchell, M.: Complexity: a guided tour. Oxford University Press, Oxford (2009)
Yang, S.X., Luo, C.: IEEE Trans. Syst. Man Cybern B (Cybernetics) 34(1), 718 (2004)
Luo, C., Yang, S.X.: IEEE Trans. Neural Netw. 19(7), 1279 (2008)
Nedjati, A., Izbirak, G., Vizvari, B.: J. Arkat, Robotics 5(4), 26 (2016)
Ersson, T., Hu, X.: . In: Intelligent Robots and Systems, 2001. Proceedings. IEEE/RSJ International Conference on, vol. 2 (IEEE 2001), pp. 858–864 (2001)
Giardini, G., Kalmár-Nagy, T.: Math. Probl. Eng. 2011 (2011)
Driscoll, T.A., Trefethen, L.N.: Schwarz-christoffel mapping, vol. 8. Cambridge University Press, Cambridge (2002)
Brakke, K.: Susquehanna University. Retrieved July 2013 from http://www.susqu.edu/brakke/evolver/evolver.html (2013)
Tejada, J.J., Punzalan, J.R.B.: The philippine statistician 61(1), 129 (2012)
Yates, D., Moore, M., McCabe, G.: The practice of statistics. W.H. Freeman, New York (1999)
Holland, J.H.: Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control and artificial intelligence (University of Michigan press Ann Arbor) (1975)
Goldberg, D.E.: Genetic Algorithms in Search, Optimization, and Machine Learning (Addison-Wesley) (1989)
Acknowledgements
The authors thank Prof José Artur Quilici Gonzalez, Federal University of ABC, for his assistance with the state of the art and also for valuable discussions. We are grateful with the referees’ suggestions, which helped improve our work substantially.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix
Appendix
Here we prove some important results previously cited in the text.
1.1 Preliminaries
In Section 5.2 we presented the equalisation procedure that results in G = (V, E). Each closed polygonal v1 → v2 →⋯ → vk → v1 =: ℙ ⊂ E such that the interior of ℙ has at most one element (v, e) ∈ V × E is called a cell of G. Without going into details, the equalisation will always produce G with the following properties \(\mathcal {P}_{1}\) −\(\mathcal {P}_{3}\):
- \(\mathcal {P}_{1}\)::
-
4 ≤ k ≤ 6.
- \(\mathcal {P}_{2}\)::
-
∀v ∈ V |deg(v) = 1, the unique \(w\in V | \overline {vw}=e\in E\Rightarrow deg(w)= 4\).
- \(\mathcal {P}_{3}\)::
-
if v, w and e are as in \(\mathcal {P}_{2}\), then ∃{w1,…w4}⊂ V | the polygonal w → w1 →…w4 → w has only v and e in its interior.
In the next subsection we study the special chromosome chr.
1.2 Visiting All Vertices
At the end of Section 5.3 we introduced two important exceptions \(\mathcal {E}_{1}\) and \(\mathcal {E}_{2}\), which together with Table 2 will guarantee that chr makes the robot visit all vertices in V. The proof is by contradiction. If there is v ∈ V that the robot never accesses, then take w ∈ V such that \(e=\overline {vw}\in E\). Hence w is also never accessed, because \(\mathcal {E}_{2}\) guarantees that trajectories are rewound. Since G is connected then we apply the same argument successive times until concluding that the robot never accesses any element of V, which is a contradiction. Therefore, the robot will indeed visit all vertices with chr.
But this chromosome can be quite expensive. In Fig. 12 we show G = (V, E) with |V | = 76, and the robot follows chr by starting at 1.
The robot surrounds the outer contour and reaches vertex 52 exactly at the 52nd step. Then it goes to the boundary of the shaded region, an obstacle that the robot finally surrounds completely at the 80th step. Namely, the robot repeated 80 − 76 = 4 vertices until now. Vertex number 56 is the last one the robot visits without repetition, because the 57th step is again vertex 55. The robot has not cleaned many vertices yet, so it will rewind to vertex 47 at the 112th step (the next one is indicated as 113). The robot will finish cleaning the whole pool at the 173rd step, which is precisely the vertex between numbers 1 and 2. Hence it takes a number of steps that is 173/76 ≅ 2.2763 times nv, where nv = 76.
1.3 Optimal Trajectories
Now we prove that with an optimal trajectory the robot visits all vertices with |S| < 1.25 nv. Fig. 13 depicts all topological kinds of cells that appear in G = (V, E) due to the equalisation procedure explained in Section 5.2. One of them is presented as a double-cell, two indicate (v, e) contained in their interior. Black and white bullets fit together, and one begins with either 4 or 6 vertices to re-construct G by starting from one of its cells.
In Fig. 13 the top left cell needs 2 steps to be cleaned. If we do not count the double-cell, then cleaning the others will take 4 to 5 steps each. Hence, in the worst case we need a number m of steps that is 5 times the number N of cells to clean all vertices.
If we re-construct G by starting from one cell then 4(N − 1) vertices will be added to the initial 6 in the worst case, so that nv = 4N + 2. Hence
However, this optimal trajectory can lead to a high battery consumption. This is because each cell with its interior (v, e) is completely cleaned before the robot goes to the next one. According to our scores the robot spends at most (2 + 4 + 3)J = 9J to go, clean and return from a spot. Hence we set our battery to start with at least 9 ⋅ 1.5 ⋅nv J = 13.5 nv J, where the factor 1.5 is explained in Section 5.4. But this starting value will be enough providingdev > -13.5 nv, where dev is defined in Section 5.7.
Rights and permissions
About this article
Cite this article
Batista, V.R., Zampirolli, F.A. Optimising Robotic Pool-Cleaning with a Genetic Algorithm. J Intell Robot Syst 95, 443–458 (2019). https://doi.org/10.1007/s10846-018-0953-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10846-018-0953-y