## 4 Proposed Path and Shape Planning Method
### Narrow Spaces Detection and Covering  
Covering the narrow spaces involves significant challenges for the robots with fixed morphology. When this scenario come to hTetro, it can move through narrow spaces effectively by changing its morphology. The I and O shapes of hTetro are used to demonstrate the transformation ability of hTetro to cover the narrow space and build the path planning. The narrow space is defined so that its width is smaller than current hTetro morphology width \(w_{m}\). Note that the fix morphology robots consider the narrow spaces are the parts the solid obstacles that make it impossible to cover areas over narrow spaces. By identifying narrow spaces in random map, if the current location of the zigzag path offsets the distance of the current robot width \(w_{m}\) with the nearest narrow space, the hTetro morphology with the width size smaller than narrow space width is assigned to the shape plan. After changing to morphology with the smaller width, hTetro will consider the narrow space is the typical free space. Then the path created by A-star is added to path planner will guide the robot to cover over the narrow space. To navigate through narrow space constraints, the global shape planner must possess a capability of identifying narrow areas in the map for each specific robot configuration as Figure 13. An Algorithm 3 for determining the narrow space areas in the entire prebuilt map is presented as follows. Specifically, to find the narrow space pixels on the vertical direction, considering one free space pixel \((x,y)\) with value \(M(x,y)=0\) on the map, the locations of the first obstacle pixel with value = 100 on the left and the first obstacle pixel with value = 100 on the right this free space pixel is defined and denoted as \((x+v_{l},y)\) and \((x-v_{l},y)\) respectively. If the value of \(v_{l}+v_{r}\) is lower than a narrow space threshold \(nth_{m}\) and larger than \(0.5\times nth_{m}\) with \(m\) representing a specific hTetro morphology as in Equation (5), this free space pixel is set to belong in a narrow space area. The value \(nth_{m}\) is chosen so that it is smaller than the width \(w_{m}\) of the robot. In this paper, we set \(nth_{m}=0.8w_{m}\). The similar algorithm as in Equation (6) can be applied to find the narrow space pixel on the horizontal direction where, \(h_{a}\) is the offset value on the above side and \(h_{b}\) is the offset value on the below side. The narrow pixel is denoted as \((x_{ns},y_{ns})\) and the narrow space pixel values \(M(x_{ns},y_{ns})\) will be assigned a value of 200 to distinguish them from other pixels of the map. \[ \begin{split} 0.5\times nth_{m}<v_{l}+v_{r}<nth_{m},\\ \text{where }M(x,y)=0,\ M(x+v_{l},y)=100,\ M(x-v_{l},y)=100\\ 0.5\times nth_{m}<h_{a}+h_{b}<nth_{m},\\ \text{where }M(x,y)=0,\ M(x,y+h_{a})=100,\ M(x,y-h_{b})=100\\ \end{split}  \tag{5}\]Once the narrow space pixels have been determined, the global planner will start its process of finding the intermediate \(W_{n}^{i}\) waypoints passing through the narrow spaces connecting between boundary waypoint \(W_{n}(bl)\) and boundary waypoint \(W_{n}(br)\). The path planning algorithm will decide the path by finding the nearest narrow pixel with the current waypoint \(W_{n}^{i}\). In order to archive it, the narrow space pixel in a window \(\Omega\) with its center at \(W_{n}^{i}\) and size of \(2\times w_{m}\) and yields shortest  
Figure 13: Narrow space pixels estimation. (**a**) Defining horizontal vertical narrow pixel, (**b**) defining horizontal narrow pixel. distance to the current location \(W_{n}^{i}\) is defined. The window \(\Omega\) size is selected to ensure the safety distance to prevent the robot from colliding with the obstacles. The nearest narrow pixel \((\hat{x}_{ns},\hat{y}_{ns})\) corresponding with \(W_{n}^{i}\) can be found by using Equation (7). \[(\hat{x}_{ns},\hat{y}_{ns})= \underset{ \begin{subarray}{c}(x_{ns},y_{ns})\in\Omega\\ M(x_{ns},y_{ns})=200\end{subarray}