# The Big Picture: An Improved Method for Mapping Shipping Activities
## 4 Improving AIS Data
### Trajectory Reconstruction  
As previously noted, sparse AIS data are problematic for vessel movement analysis, since the reconstructed trajectories from straight line segments between the positional messages do not represent the vessels' real paths. Tasks such as the creation of line-based density maps depend on the validity of these data and may in turn suffer in accuracy. In this section, a mechanism for effectively reconstructing large gaps on vessel trajectories is presented. This mechanism allows for the transformation of sparse AIS data into more detailed trajectories. The implemented technique takes advantage of historical data to discover frequently followed paths using graph theory methods. Firstly, the movement space, i.e., the sea areas of interest, is partitioned and transformed into a grid; for the purposes of accuracy, a grid cell edge length of 1 km can be selected. Furthermore, movement from historical data is modelled using vessel transitions between neighboring cells. Cells are considered to be neighboring if they have no other cells in between them, i.e., each cell has at most eight neighbors (see Figure 8). After extracting all transitions between the cells, we transform the grid into a directed weighted graph. Each graph node represents a grid cell, while the edges of the graph are used to model transitions between neighboring cells. The weight of each edge is calculated as the (Euclidean) distance between the cells. Additionally, a second weight-penalty modelling the patterns of vessel movement is assigned to each edge, from node \(n_{i}\) to node \(n_{j}\), using the formula:  
Figure 8: Each grid cell has at most eight (8) neighbours; the light blue arrows indicate all the possible transitions that may be followed by a vessel, while there cannot be a single transition to the cell with the island (represented by the red arrow). \[h_{p}(n_{i},n_{j})=\left\{ \begin{array}{cc}H_{tt},&\text{if }N(c_{i},c_{j})=0\\ 1-\frac{N(c_{i},c_{j})}{\sum_{k}N(c_{i},c_{k})},&\text{otherwise}\end{array} \right.\]  
where \(h_{p}(n_{i},n_{j})\) is the second weight between the nodes, \((c_{i},c_{j})\) are the corresponding neighbouring cells, \(N(c_{i},c_{j})\) is the number of transitions between these cells and \(\sum_{k}N(c_{i},c_{k})\) is the total number of outgoing transitions for cell \(c_{i}\). Finally, for neighboring cells with no transitions observed between them, a predefined weight-penalty equal to \(H_{tt}\) is assigned. This penalty should be a real number equal to or greater than 1, indicating that a larger price needs to be paid for such a path. Note that all other weight-penalties can be bounded by 0 and 1, with smaller values assigned to more frequent transitions. The resulting graph incorporates both historical information and spatial characteristics of the grid, through its inclusion of two weights. Thus, the generated paths are informed by past movement while also following routes of low cost, in terms of total distance covered by the vessel. This way, instances where common traffic patterns distort apparent and self-evident suggestions between AIS points, like the one depicted in Figure 9, can be easily avoided. The way each weight (historical information or spatial characteristics) affects the accuracy of the results may vary depending on the usecase. More details are provided in the following paragraphs that describe the path-finding algorithm used. This process extracts useful information regarding vessel movement in the area that can be used to generate possible paths during AIS gaps. The process of estimating a path, depicted in Figure 10 and described in the form of a pseudo-code in Algorithm 1, consists of the following steps:  
1. Identify the AIS gap within a trajectory and the two cells where the gap started and ended. 2. Use the transition graph to extract a path between these cells, through an enhanced A* algorithm [57]. 3. Transform the returned path, expressed as a series of grid cells, to a series of real coordinates. 4.