Graph Theory-Based Approach to Accomplish Complete Coverage Path Planning Tasks for Reconfigurable Robots

Abstract

Extensive studies regarding complete coverage problems have been conducted, but a few tackle scenarios where the mobile robot is equipped with reconfigurable modules. The reconfigurability of these robots creates opportunities to develop new navigation strategies with higher dexterity; however, it also simultaneously adds in constraints to the direction of movements. This paper aims to develop a valid navigation strategy that allows tetromino-based self-reconfigurable robots to perform complete coverage tasks. To this end, a novel graph theory-based model to simulate the workspace coverage and make use of dynamic programming technique for optimal path searching and adaptive robot morphology shifting algorithms is proposed. Moreover, the influence of algorithms starting variables on workspace coverage outcome is analyzed thoughtfully in this paper. The simulation results showed that the proposed method is capable of generating navigation paths throughout the workspace, which ensures complete workspace coverage while minimizing the total number of actions performed by the robot.

Keywords

• Complete coverage path planning
• self-reconfigurable robots
• graph theory
• dynamic programming
• Dijkstra algorithm