# The Big Picture: An Improved Method for Mapping Shipping Activities
## 4 Improving AIS Data
### Trajectory Reconstruction
Assign a timestamp for each generated point, based on the length of the resulting path and the overall gap interval. 5. Incorporate the resulting coordinate-timestamp pairs in the original AIS trajectory. Figure 9: Depiction of trajectory reconstruction using solely historical information. The green points represent the real AIS messages while the brown ones represent the generated paths between them. As observed, common patterns of movement may in some cases distort the trajectories created, compared to what was expected, when spatial information is not taken into account. A modified version of the A-star algorithm (A*) [57] is used to generate the possible path the vessel followed during its communication gap. Designed for obtaining the shortest path between two nodes in a directed weighted graph, the A* uses two major components: (i) the weighted graph and (ii) a heuristic function that returns an estimation of the distance required to travel from a node to another. Beginning from the'start' node, at each step of the algorithm, the neighbours of an already visited node are investigated. For each neighbour, A* combines information from both the graph and the heuristic equation, in order to update a calculated cost, in case it is part of the shortest graph. After assigning an estimated total cost to each neighbour, the current node is discarded. Then, the algorithm moves on examining the node with the smallest total cost of all previously visited nodes. The A* algorithm terminates when the 'end' node is reached, resulting in the shortest path in terms of the graph's weights. For the calculation of the estimated total cost of each neighbour, the following formula is used:  
\[f(n_{i})=[g(n_{c})+w(n_{c},n_{i})]+h(n_{i},n_{t})\]  
Figure 10: Process for improving AIS trajectories with gaps; the transition graph is exported once, using historical data (green), and is used for every identified gap. where \(g(n_{c})\) is the cumulative total cost from the start node to the current node \((n_{c})\), \(w(n_{c},n_{i})\) is the graph weight between the current node and the neighbour in question \((n_{i})\) and \(h(n_{i},n_{t})\) is the result of the heuristic function that estimates the cost from the neighbor to the target node \((n_{t})\). In our approach, we alter the A* algorithm by incorporating the knowledge extracted from the historical data within the cost functions. More precisely, a penalty function is added to the calculation of the total cost:  
\[f(n_{i})=[g(n_{c})+w(n_{c},n_{i})+p(n_{c},n_{i})]+h(n_{i},n_{t})\]  
where:  
\[p(n_{c},n_{i})=w(n_{c},n_{i})*W_{h}*h_{p}(n_{c},n_{i})\]  
with \(w(n_{c},n_{i})\) being the weight (distance) between the two nodes as above and \(h_{p}(n_{c},n_{i})\) being the weight-penalty based on historical data, \(W_{h}\) is a factor that determines the importance of the historical information during the gap-filling, normally ranging from 0 to 1. Additionally, since both are bounded by 0 and 1 (with the exception of the \(H_{n}\) penalty defined as larger than one), the \(p(n_{c},n_{i})\) function is in turn bounded by 0 and the real distance between the cells, thus providing a penalty normalized to the original graph. A high-level description of this shortest path method can also be found in Algorithm 2. ```
0: Transition grid (\(tg\)),'start' cell (\(c_{s}\)), 'end' cell (\(c_{c}\)), factor for considering historical information (\(pfact\))
0: Return the shortest path according to weights from \(c_{s}\) to \(c_{e}\) \(\triangleright\) getTransitionWeight is a function that calculates the transition cost using historical information from the graph and the distance between the cells, taking into account the factor \(pfact\).