## 4 Proposed Path and Shape Planning Method  
### A-Star Based-Zigzag Planning  
The final goal of solving area coverage problems is to cover the free space areas defined in the prebuilt map by navigating automatically and following the predefined path created by the global planner. To this end, numerous methods have been proposed. The conventional offline methods select the waypoints manually with the knowledge of maps shapes and sizes as well as obstacles shapes and positions to create the area coverage path. Besides, several cleaning robots use bump sensors to detect and follow the obstacle boundaries to form area coverage path. A-star algorithm [22] is the most popular and widely used method to compute and plan the path for the robot to navigate autonomously by avoiding the obstacles. The main idea of this algorithm is to find the shortest path between the starting point and the destination point based on the cost function. A-star algorithm is based on a grid map. The grid cells are categorized into source cell, destination cell, free space cells and obstacle cells. Figure 7a describes one such example of the algorithm to find the shortest path from cell 14 th to cell 35 th. There are eight neighboring cells around the cell in grid map as Figure 7b. In the first step of A-star, each neighboring free space cell around the source cells is assigned a corresponding cost such as horizontal and vertical neighboring cells have the cost of 10 while the diagonal neighboring cells have the cost of 14. The neighboring obstacle cells do not have any cost. Then the cost of these free space neighbors will be accumulated until the destination cell is reached. The shortest path is selected by tracing back to find the cells with the smallest value from destination cell to source cell. In the case of maximizing area coverage with the ability to avoid obstacles, zigzag scanning-based A-star approach can be used, by defining a set of waypoints locations at the boundary as in the zigzag pattern, then letting the A-star to compute the shortest path to clear these waypoints. To cover the entire area defined by the boundary of the room on the map, the trajectory is a zigzag line which is made up of evenly spaced segments. The end point of each segment is connected to the starting point of the next segment. The conventional algorithm A-star has the limitations of not covering the free space cells in the defined range and revisiting free space cells that have been already covered. Assuming that the robot width equals the length of 2 cells, the drawbacks of the A-star algorithms are depicted in Figure 8a-c. It can be observed in Figure 8a that the diagonal moving feature of A-star making the shorter path from source to destination is triggered with which some cells around the diagonal trajectory will not be covered. In Figure 8b, if an obstacle appears on the path connecting two waypoints, there are two options to choose the path in order to avoid obstacles by going up or going down. If A-star algorithm opts to move upon reaching the obstacle cells as in Figure 8b, some cells below the obstacle remain uncovered and the covered cells above the obstacles will be revisited to find the way connecting from right to left boundary waypoint. Similarly, the upper cells will not be covered and the under cells are revisited if A-star decides to go down on reaching obstacle cells. Moreover, the A-star algorithm selects a path that goes around free space defined as narrow space pixels as depicted in Figure 8c. The modified A-star based-zigzag scanning method for the area coverage problem has been proposed in the research of [30]. In this method, the map is divided into the sub-maps bordered by obstacle boundary. Then these subareas are covered by zigzag planning. After finishing each sub-area, the algorithm chooses the next uncovered area yielding the shortest distance with the current covered one. A-Star algorithm will be used to find the path to this uncovered area; this path is called way-out path as in Figure 8d.