Complete Path Planning for a Tetris-Inspired Self-Reconfigurable Robot by the Genetic Algorithm of the Traveling Salesman Problem

Anh Le, Manimuthu Arunmozhi, Prabakaran Veerajagadheswar, Ping-Cheng Ku, Tran Hoang Minh, Vinu Sivanantham, Rajesh Mohan

Research output: Contribution to journalArticlepeer-review


The efficiency of autonomous systems that tackle tasks such as home cleaning, agriculture harvesting, and mineral mining depends heavily on the adopted area coverage strategy. Extensive navigation strategies have been studied and developed, but few focus on scenarios with reconfigurable robot agents. This paper proposes a navigation strategy that accomplishes complete path planning for a Tetris-inspired hinge-based self-reconfigurable robot (hTetro), which consists of two main phases. In the first phase, polyomino form-based tilesets are generated to cover the predefined area based on the tiling theory, which generates a series of unsequenced waypoints that guarantee complete coverage of the entire workspace. Each waypoint specifies the position of the robot and the robot morphology on the map. In the second phase, an energy consumption evaluation model is constructed in order to determine a valid strategy to generate the sequence of the waypoints. The cost value between waypoints is formulated under the consideration of the hTetro robot platform’s kinematic design, where we calculate the minimum sum of displacement of the four blocks in the hTetro robot. With the cost function determined, the waypoint sequencing problem is then formulated as a travelling salesman problem (TSP). In this paper, a genetic algorithm (GA) is proposed as a strong candidate to solve the TSP. The GA produces a viable navigation sequence for the hTetro robot to follow and to accomplish complete coverage tasks. We performed an analysis across several complete coverage algorithms including zigzag, spiral, and greedy search to demonstrate that TSP with GA is a valid and considerably consistent waypoint sequencing strategy that can be implemented in real-world hTetro robot navigations. The scalability of the proposed framework allows the algorithm to produce reliable results while navigating within larger workspaces in the real world, and the flexibility of the framework ensures easy implementation of the algorithm on other polynomial-based shape shifting robots.
Original languageEnglish
Number of pages21
Issue number12
Publication statusPublished - 22 Nov 2018

Bibliographical note

Copyright © 2018 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (


  • motion planning; cleaning robot; reconfigurable system; energy saving; area coverage; genetic algorithm


Dive into the research topics of 'Complete Path Planning for a Tetris-Inspired Self-Reconfigurable Robot by the Genetic Algorithm of the Traveling Salesman Problem'. Together they form a unique fingerprint.

Cite this