## 4 Proposed Path and Shape Planning Method
### Proposed A-Starbased Path Planning Strategy  
Each segment of the zigzag pattern of the path will be created by adding a set of \(W_{n}^{i}\) to connect any two, boundary and obstacle waypoints with these two waypoints are the start and end points of this segment. In particular, if there is no any obstacle waypoint on the line \(y=y_{n}^{hl}\) connecting two boundary waypoints \(W_{n}(bl)\) and \(W_{n}(br)\) as cells marked 1, 5, 6, 7 in Figure 11(a) the global planner adds set of cells \(W_{i}\) along the line \(y=y_{n}^{hl}\) and generating by A-star path searching to connect these two waypoints. The path generated by A-star is same as zigzag scanning. In the cases of existing obstacle between waypoints at cells 2, 3, 4 in Figure 11(a), firstly the path planning creates zigzag lines to cover the left boundary waypoints and the left obstacle waypoints. Specially, assuming that at present, zigzag trajectory moves from left to right and meet the first obstacle, the height of the obstacle is estimated by the following condition. From the obstacle pixel, the set of obstacle pixels of this obstacle object in a known map can be found by finding the linking neighboring pixels, which have the pixel value of 100. The value corresponding to the highest y value denoted as \(y_{o}^{hl}\) is set to the height of this obstacle object. The range of left and right boundary waypoints having y value in a range \([0:M_{w_{n}},y_{n}^{hl}:y_{o}^{hl}+w_{m}]\) denoted at \([W_{n}(bl):\)\(W_{n+o}(bl)]\) and \([W_{n}(br):\)\(W_{n+o}(br)]\). The range of left and the right obstacle waypoints having the \(y\) coordinate value in the range of \([0:M_{w_{n}},y_{n}^{hl}:y_{o}^{hl}+w_{m}]\) are also identified and denoted as \([W_{n}(ol_{i}):\)\(W_{n+o}(ol_{i})]\) and \([W_{n}(or_{i}):\)\(W_{n+o}(or_{i})]\) with \(s\) is the obstacle number \(i\). The \(w_{m}\) is added to make the safety distance which ensures the planned path can avoid the obstacle. After the range of obstacle waypoints have been indented, instead of going to boundary waypoints \(W_{n}(br)\) from the boundary waypoint \(W_{n}(bl)\) by the conventional A-staralgorithm, the zigzag scanning technique will be applied to clear the area defined by waypoints \([W_{n}(bl):W_{n+o}(bl)]\) and \([W_{n}(o_{1}):W_{n+o-1}(o_{1})]\). The scanning order by A-star path searching will execute from left waypoint to right waypoint then move to upper right waypoint to scan left waypoint on the same line until the last waypoint has been cleared as in Figure 12a. After creating zigzag lines to clear left boundary waypoints and left obstacle waypoints, then the shortest trajectory including grid cells with red arrows as in Figure 12a generated by A-star connects the leftmost boundary waypoint \(W_{n+o}(bl)\) marked as a green cell with number 4 to the first right obstacle waypoint \(W_{n}(or_{1})\) marked a blue cell with number 2. As one can observe, the shortest path by A-star will follow the obstacle boundary cells. If there is another \(W_{n}o_{l+1}\) of obstacle number \(i+1\) located on the right side of \(W_{n}or_{i}\), the same zigzag scanning strategy will clear the area defined by waypoints \([W_{n}(or_{i}):W_{n+o-1}(or_{i})]\) and \([W_{n}(ol_{i+1}):W_{n+o-1}(o_{l+1})]\). In case if there is no \(W_{n}o_{l+1}\), the final segment defined by waypoints \([W_{n}(or_{i}):W_{n+o}(or_{i})]\) and \([W_{n}(br):W_{n+o}(br)]\) will be covered by the same zigzag scanning strategy as Figure 12a. Note that, to reduce the problem of revisiting the cells at the right side of obstacle boundary when zigzag scanning moves from left to right, the right obstacle waypoint from \(W_{n+1}(or_{1})\) to \(W_{n+o}(or_{1})\) is shifted to the right by the number of cells equal to robot width \(w_{m}\) by assuming the width between obstacle \(i\) and obstacle \(i+1\) is larger than \(2\times w_{m}\). The right waypoint is shifted and then marked as blue cells with number 3 in Figure 12a.