Contents I. Introduction
Path planning has always been an inevitable technology of Autonomous Underwater Vehicles (AUVs) in ocean survey missions [1]. Planning the optimal navigation path can reduce the task execution time and alleviate the problem of energy shortage, which is of great significance to the application of AUV. Coverage path planning is a branch of path planning which has been under development since the mid-1960s. In coverage path planning, an AUV must visit the whole area [2]. Methods to improve traversal efficiency have been put forward over years. Latombe proposed a exact cellular decomposition method named trapezoidal decomposition which break free space into trapezoidal cells and cover each cell with back-and-forth motions in a “mowing the lawn” manner [3]. Exact cellular decomposition method(ECDM) breaks free space down into non-overlapping regions called cells. These cells can be swept using Seed Spreader motions. An adjacency graph can be used to represent the cellular decomposition, where a node represents a cell and an edge represents an adjacency relationship between two cells. Typically, a planner based on exact cellular decomposition generates a coverage path in two steps. First, it decomposes the free space into cells and stores the decomposition as an adjacency graph. Next, it computes an exhaustive walk through the adjacency graph. The exhaustive walk determines the order in which the cells are visited to achieve complete coverage. Stanley Brown et. al. decomposes the environment into easily traversable cells by exploiting the geometric information contained in the environments straight skeleton. And apply ECDM to complex indoor environments [4].
