{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,21]],"date-time":"2026-02-21T03:48:26Z","timestamp":1771645706092,"version":"3.50.1"},"reference-count":35,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2020,6,3]],"date-time":"2020-06-03T00:00:00Z","timestamp":1591142400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the National Robotics R&amp;D Programme Office, Singapore","award":["RGAST1907"],"award-info":[{"award-number":["RGAST1907"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Sensors"],"abstract":"<jats:p>Completed area coverage planning (CACP) plays an essential role in various fields of robotics, such as area exploration, search, rescue, security, cleaning, and maintenance. Tiling robots with the ability to change their shape is a feasible solution to enhance the ability to cover predefined map areas with flexible sizes and to access the narrow space constraints. By dividing the map into sub-areas with the same size as the changeable robot shapes, the robot can plan the optimal movement to predetermined locations, transform its morphologies to cover the specific area, and ensure that the map is completely covered. The optimal navigation planning problem, including the least changing shape, shortest travel distance, and the lowest travel time while ensuring complete coverage of the map area, are solved in this paper. To this end, we propose the CACP framework for a tiling robot called hTrihex with three honeycomb shape modules. The robot can shift its shape into three different morphologies ensuring coverage of the map with a predetermined size. However, the ability to change shape also raises the complexity issues of the moving mechanisms. Therefore, the process of optimizing trajectories of the complete coverage is modeled according to the Traveling Salesman Problem (TSP) problem and solved by evolutionary approaches Genetic Algorithm (GA) and Ant Colony Optimization (ACO). Hence, the costweight to clear a pair of waypoints in the TSP is defined as the required energy shift the robot between the two locations. This energy corresponds to the three operating processes of the hTrihex robot: transformation, translation, and orientation correction. The CACP framework is verified both in the simulation environment and in the real environment. From the experimental results, proposed CACP capable of generating the Pareto-optimal outcome that navigates the robot from the goal to destination in various workspaces, and the algorithm could be adopted to other tiling robot platforms with multiple configurations.<\/jats:p>","DOI":"10.3390\/s20113170","type":"journal-article","created":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T04:36:09Z","timestamp":1591245369000},"page":"3170","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["Optimization Complete Area Coverage by Reconfigurable hTrihex Tiling Robot"],"prefix":"10.3390","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4804-7540","authenticated-orcid":false,"given":"Anh Vu","family":"Le","sequence":"first","affiliation":[{"name":"ROAR Lab, Engineering Product Development, Singapore University of Technology and Design, Singapore 487372, Singapore"},{"name":"Optoelectronics Research Group, Faculty of Electrical and Electronics Engineering, Ton Duc Thang University, Ho Chi Minh City 700000, Vietnam"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3843-9997","authenticated-orcid":false,"given":"Rizuwana","family":"Parween","sequence":"additional","affiliation":[{"name":"ROAR Lab, Engineering Product Development, Singapore University of Technology and Design, Singapore 487372, Singapore"}]},{"given":"Rajesh","family":"Elara Mohan","sequence":"additional","affiliation":[{"name":"ROAR Lab, Engineering Product Development, Singapore University of Technology and Design, Singapore 487372, Singapore"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7347-7446","authenticated-orcid":false,"given":"Nguyen Huu Khanh","family":"Nhan","sequence":"additional","affiliation":[{"name":"Optoelectronics Research Group, Faculty of Electrical and Electronics Engineering, Ton Duc Thang University, Ho Chi Minh City 700000, Vietnam"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6538-4875","authenticated-orcid":false,"given":"Raihan","family":"Enjikalayil Abdulkader","sequence":"additional","affiliation":[{"name":"ROAR Lab, Engineering Product Development, Singapore University of Technology and Design, Singapore 487372, Singapore"}]}],"member":"1968","published-online":{"date-parts":[[2020,6,3]]},"reference":[{"key":"ref_1","unstructured":"Markets and Markets (2020, May 24). Cleaning Robot Market by Product. Available online: http:\/\/www.marketsandmarkets.com\/Market-Reports\/cleaning-robot-market-22726569.html."},{"key":"ref_2","unstructured":"Richter, F. (2020, May 24). Infographic: Let the Robot Do the Cleaning. Available online: https:\/\/www.statista.com\/chart\/9089\/worldwide-personal-robot-sales-forecast."},{"key":"ref_3","unstructured":"Joseph, L.J., Newton, E.M., David, M.N., and Paul, E.S. (2008). Autonomous Floor Cleaning Robot. (7,448,113), U.S. Patent."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"3998","DOI":"10.1109\/LRA.2020.2983683","article-title":"Path tracking control of self-reconfigurable robot hTetro with four differential drive units","volume":"5","author":"Shi","year":"2020","journal-title":"IEEE Robot. Autom. Lett."},{"key":"ref_5","unstructured":"Edwards, T., and S\u00d6RME, J. (2018). A Comparison of Path Planning Algorithms for Robotic Vacuum Cleaners. [Ph.D. Thesis, KTH Royal Institute OF Technology]."},{"key":"ref_6","unstructured":"Gao, X., Li, K., Wang, Y., Men, G., Zhou, D., and Kikuchi, K. (2007, January 15\u201318). A floor cleaning robot using Swedish wheels. Proceedings of the IEEE International Conference on Robotics and Biomimetics, Sanya, China."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"103078","DOI":"10.1016\/j.autcon.2020.103078","article-title":"Complete coverage path planning using reinforcement learning for tetromino based cleaning and maintenance robot","volume":"112","author":"Lakshmanan","year":"2020","journal-title":"Autom. Constr."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1109\/70.59357","article-title":"Dynamic path planning in sensor-based terrain acquisition","volume":"6","author":"Lumelsky","year":"1990","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1177\/027836402320556359","article-title":"Morse Decompositions for Coverage Tasks","volume":"21","author":"Acar","year":"2002","journal-title":"Int. J. Robot. Res."},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Wang, L., Gao, H., and Cai, Z. (2009, January 19\u201320). Topological Mapping and Navigation for Mobile Robots with Landmark Evaluation. Proceedings of the 2009 International Conference on Information Engineering and Computer Science, Wuhan, China.","DOI":"10.1109\/ICIECS.2009.5366479"},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1002\/rob.20388","article-title":"Coverage path planning on three-dimensional terrain for arable farming","volume":"28","author":"Jin","year":"2011","journal-title":"J. Field Robot."},{"key":"ref_12","unstructured":"Cheng, P., Keller, J., and Kumar, V. (2008, January 22\u201326). Time-optimal UAV trajectory planning for 3D urban structure coverage. Proceedings of the 2008 IEEE\/RSJ International Conference on Intelligent Robots and Systems, Nice, France."},{"key":"ref_13","unstructured":"Luo, C., and Yang, S.X. (2002, January 30). A real-time cooperative sweeping strategy for multiple cleaning robots. Proceedings of the IEEE Internatinal Symposium on Intelligent Control, Vancouver, BC, Canada."},{"key":"ref_14","unstructured":"Zelinsky, A., Jarvis, R.A., Byrne, J., and Yuta, S. (1993, January 8\u20139). Planning paths of complete coverage of an unstructured environment by a mobile robot. Proceedings of the International Conference on Advanced Robotics, Tsukuba, Japan."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"159402","DOI":"10.1109\/ACCESS.2019.2950675","article-title":"Reconfigurable Pavement Sweeping Robot and Pedestrian Cohabitant Framework by Vision Techniques","volume":"7","author":"Le","year":"2019","journal-title":"IEEE Access"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"1729881420914441","DOI":"10.1177\/1729881420914441","article-title":"Motion planner for a Tetris-inspired reconfigurable floor cleaning robot","volume":"17","author":"Veerajagadheswar","year":"2020","journal-title":"Int. J. Adv. Robot. Syst."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1023\/A:1016639210559","article-title":"Coverage for robotics\u2014A survey of recent results","volume":"31","author":"Choset","year":"2001","journal-title":"Ann. Math. Artif. Intell."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"94642","DOI":"10.1109\/ACCESS.2019.2928467","article-title":"Graph theory-based approach to accomplish complete coverage path planning tasks for reconfigurable robots","volume":"7","author":"Cheng","year":"2019","journal-title":"IEEE Access"},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Manimuthu, A., Le, A.V., Mohan, R.E., Veerajagadeshwar, P., Nguyen, H.K.N., and Ku, P.C. (2019). Energy Consumption Estimation Model for Complete Coverage of a Tetromino Inspired Reconfigurable Surface Tiling Robot. Energies, 12.","DOI":"10.3390\/en12122257"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Le, A., Prabakaran, V., Sivanantham, V., and Mohan, R. (2018). Modified a-star algorithm for efficient coverage path planning in tetris inspired self-reconfigurable robot with integrated laser sensor. Sensors, 18.","DOI":"10.3390\/s18082585"},{"key":"ref_21","doi-asserted-by":"crossref","first-page":"88177","DOI":"10.1109\/ACCESS.2020.2992333","article-title":"System Level Modeling and Control Design of hTetrakis\u2013A Polyiamond Inspired Self-Reconfigurable Floor Tiling Robot","volume":"8","author":"Parween","year":"2019","journal-title":"IEEE Access"},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Guan, E., Fu, Z., Yan, W., Jiang, D., and Zhao, Y. (2011, January 6\u20138). Self-reconfiguration path planning design for M-lattice robot based on genetic algorithm. Proceedings of the International Conference on Intelligent Robotics and Applications, Aachen, Germany.","DOI":"10.1007\/978-3-642-25489-5_49"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"846","DOI":"10.1177\/0278364911406761","article-title":"Sampling-based algorithms for optimal motion planning","volume":"30","author":"Karaman","year":"2011","journal-title":"Int. J. Robot. Res."},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Pfotzer, L., Staehler, M., Hermann, A., R\u00f6nnau, A., and Dillmann, R. (2015, January 2\u20134). KAIRO 3: Moving over stairs unknown obstacles with reconfigurable snake-like robots. Proceedings of the 2015 European Conference on Mobile Robots (ECMR), Lincoln, UK.","DOI":"10.1109\/ECMR.2015.7324209"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Le, A.V., Ku, P.C., Tun, T.T., Nhan, N.H.K., Shi, Y.Y., and Mohan, R.E. (2019). Realization energy optimization of complete path planning in differential drive based self-reconfigurable floor cleaning robot. Energies, 12.","DOI":"10.3390\/en12061136"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"103467","DOI":"10.1016\/j.robot.2020.103467","article-title":"Roombots extended: Challenges in the next generation of self-reconfigurable modular robots and their application in adaptive and assistive furniture","volume":"127","author":"Hauser","year":"2020","journal-title":"Robot. Auton. Syst."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0925-7721(00)00015-8","article-title":"Approximation algorithms for lawn mowing and milling","volume":"17","author":"Arkin","year":"2000","journal-title":"Comput. Geom."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"3680","DOI":"10.1016\/j.asoc.2011.01.039","article-title":"Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search","volume":"11","author":"Geng","year":"2011","journal-title":"Appl. Soft Comput."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Le, A.V., Nhan, N.H.K., and Mohan, R.E. (1999). Evolutionary Algorithm-Based Complete Coverage Path Planning for Tetriamond Tiling Robots. Sensors, 20.","DOI":"10.3390\/s20020445"},{"key":"ref_30","unstructured":"Dorigo, M., and Di Caro, G. (1999, January 6\u20139). Ant colony optimization: A new meta-heuristic. Proceedings of the 1999 Congress on Evolutionary Computation-CEC99 (Cat. No. 99TH8406), Washington, DC, USA."},{"key":"ref_31","unstructured":"Thomas, B. (1996). Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford University Press."},{"key":"ref_32","unstructured":"Quigley, M., Conley, K., Gerkey, B., Faust, J., Foote, T., Leibs, J., Wheeler, R., and Ng, A.Y. (2009, January 29). ROS: An open-source Robot Operating System. Proceedings of the ICRA Workshop on Open Source Software, Kobe, Japan."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"35260","DOI":"10.1109\/ACCESS.2018.2848662","article-title":"A tiling-theoretic approach to efficient area coverage in a tetris-inspired floor cleaning robot","volume":"6","author":"Veerajagadheswar","year":"2018","journal-title":"IEEE Access"},{"key":"ref_34","unstructured":"(2020, May 24). A Polyomino Tiling Algorithm. Available online: https:\/\/gfredericks.com\/gfrlog\/99."},{"key":"ref_35","doi-asserted-by":"crossref","first-page":"496","DOI":"10.1016\/j.robot.2008.10.022","article-title":"Mobile robot localization based on ultra-wide-band ranging: A particle filter approach","volume":"57","author":"Blanco","year":"2009","journal-title":"Robot. Auton. Syst."}],"container-title":["Sensors"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1424-8220\/20\/11\/3170\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T09:35:18Z","timestamp":1760175318000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1424-8220\/20\/11\/3170"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,3]]},"references-count":35,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2020,6]]}},"alternative-id":["s20113170"],"URL":"https:\/\/doi.org\/10.3390\/s20113170","relation":{},"ISSN":["1424-8220"],"issn-type":[{"value":"1424-8220","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,3]]}}}