## 4 Proposed Path and Shape Planning Method
### A-Star Based-Zigzag Planning
However, there are some limitations in this algorithm. Firstly, the algorithm is considered for the obstacles with relatively simple shapes. Secondly, when moving to the next uncovered sub-map, if the last covered cell of a sub-map is located at a place where there are no neighboring cells from the next uncovered sub-map some cells of current subarea needs to be revisited to reach the uncovered subarea. The paths are represented by blue arrows in Figure 8d. Finally, the problem of covering the narrow space constrains is not solved in this method. This problem is inevitable for the fixed morphology robots which cannot change its morphology. Figure 8: Drawbacks of conventional A-star based methods for area coverage. (**a**) A-star with the diagonal movement, (**b**) A-star for area coverage, (**c**) uncovered narrow space by fix morphology, (**d**) subareas A-star based area coverage [8]. Figure 7: A-star shortest path searching. (**a**) Estimating A-star path, (**b**) neighboring cells. In this paper, a modified A-star based zigzag scanning is proposed to plan trajectory including a set of intermediate waypoints for a Tetris inspired self-reconfigurable robot hTetro. Specifically, the shapes and dimensions of the maps generated by SLAM algorithm in ROS environment can be set randomly or acquired dynamically in real time. Consequently, the areas needed to be covered and obstacle characteristics such as shapes and locations as well as map border are not known before creating the coverage paths. The proposed method uses features of the maps to determine the different types of waypoints including boundary waypoints, obstacle waypoints autonomously, Furthermore, unlike the traditional path planning defies only waypoints locations, the waypoints in the proposed method include both accurate locations and appropriate morphology in hTetro robot. As per the results the final objective of covering maximum areas, minimizing the issue of revisiting the areas that have been covered and the ability to navigate through narrow space constraints of the maps built on ROS system can be accomplished efficiently. The process of creating a zigzag path planning for a map is depicted in Figure 9. The trajectory represented in Figure 9 is set to start at the first waypoint and then follows the yellow path towards the last waypoint. The first waypoint is defined as the origin point located at the bottom left corner. Note that the x-axis is denoted green and the y-axis is denoted red. Since the obstacles locating randomly in the map have the arbitrary shapes and the map are segmented into grids, the grid-based A-star algorithm is used to find the shortest path to avoid the obstacles and connect each pair of auto-generated waypoints. Movement in diagonal direction in the A-star algorithm is disabled to ensure the maximum area coverage. The boundary waypoints marked as the green and obstacle waypoints marked as and red cells in Figure 9. Boundary waypoints and obstacles waypoints staying near the border of the map and obstacles respectively are the locations where zigzag scanning segments are terminated. The procedures of determining in a random map these waypoints are detailed in next sections. After the global shape and path planner has autonomously defined the waypoints, the hTetro will follow the path and perform shapeshifting that are necessary to avoid obstacles, pass through the narrow spaces and clear the waypoint. The flowchart depicted in Figure 10 describes the algorithm to identify the locations and the morphologies at intermediate waypoints to adapt to particular situations. Figure 9: Boundary waypoints and obstacle waypoints. New zigzag scanning pattern is proposed to enable the global planner in finding the paths that cover maximum free space area of the prebuild maps and reduce the issue of revisiting the already covered cells.