Zhu, Gao, Zhang, Hu and Zeng (J. Mar. Sci. Eng. 2022, 10, 1536) mined multi-ship encounter situations from Automatic Identification System (AIS) data by building a ship encounter graph whose nodes are ships and whose edges are identified pairwise encounters, ranked whole-network collision risk with a weighted PageRank over this graph, and steered an artificial potential field collision-avoidance method with that risk rank. The paper's stated future work asks, verbatim, that 'the isomorphism of the graph will be further studied so that it can be used to select the same multiple ship encounter situations from the AIS data to assist collision avoidance', together with combining the risk-rank measure with collision-avoidance algorithms other than the artificial potential field and more testing. No published method retrieves historically observed multi-ship encounter situations from AIS archives by structural equivalence of encounter graphs. The problem remains open: formalize what makes two multi-ship encounter graphs 'the same situation', make retrieval from massive AIS archives computationally feasible, and demonstrate that the retrieved situations assist multi-ship collision-avoidance decisions.

Background

Collisions at sea are most dangerous and hardest to reason about when more than two ships are mutually involved. Two data sources make such situations studyable at scale. The Automatic Identification System (AIS) is the mandatory VHF/satellite broadcast by which ships report identity, position, speed and heading at short intervals, so years of traffic can be mined retrospectively. The International Regulations for Preventing Collisions at Sea (COLREGs) legally define the pairwise encounter types (overtaking, head-on, crossing) and the avoidance duties they imply, but give no delineation of multi-ship encounter situations. Pairwise risk is usually quantified from the distance at closest point of approach (DCPA) and the time to it (TCPA), often fused by fuzzy logic into a collision risk index (CRI); a ship domain is a model of the safe waters around a vessel, and the 'quaternary dynamic ship domain' used here is a four-radius (fore, aft, port, starboard) domain whose radii adapt to the ship's motion state.

The source work (Zhu et al. 2022) combined these ingredients into a network model. From AIS data it identified pairwise encounters per COLREGs (accelerated by a 'spatial-temporal companion' screen), then built a ship encounter graph network: nodes are ships carrying position, heading and speed at each moment, and edges carry the relative-motion relationship and the pairwise encounter identification result. Complex-network statistics — network average degree, average path length and average clustering coefficient, the standard summary measures of graph structure — describe how a multi-ship encounter evolves in space and time from simple to complex and back. Because a pairwise CRI cannot rank a whole interacting group, the authors applied the weighted PageRank algorithm (the centrality method originally used to rank web pages, here with encounter-risk weights on edges) to rank every ship's importance in the encounter network, identifying the 'key ship' whose coordinated action matters most. That risk rank steered an artificial potential field (APF) method — a reactive collision-avoidance scheme in which nearby ships act as repulsive force fields — producing fewer turns and smoother avoidance trajectories than the plain APF. The demonstration covered the Zhoushan water area of China.

The paper's conclusions state two pieces of future work. First, the risk-rank measure combined with collision-avoidance algorithms other than APF requires further study and more testing. Second, and centrally: 'The isomorphism of the graph will be further studied so that it can be used to select the same multiple ship encounter situations from the AIS data to assist collision avoidance.' Graph isomorphism is the question whether two labelled graphs are structurally identical up to a relabelling of vertices; applied to encounter graphs it asks whether two multi-ship encounters observed at different times, in different waters, involving different ships, are nevertheless the same situation — same pattern of encounter relations, node kinematic attributes and risk structure. Because AIS archives record years of traffic, a current multi-ship encounter matched to structurally identical historical ones would let a decision system consult how such situations actually unfolded and were resolved — an instance of case-based reasoning, the artificial-intelligence technique of solving new problems by retrieving and adapting stored past cases. The source paper names this route as one of its two envisioned coordinated collision-avoidance decision methods, but develops only the risk-rank-plus-APF branch.

Adjacent literature stops short of structural retrieval. Hwang and Youn (2021) hierarchically clustered navigation situations from a year of AIS data to build test scenarios for autonomous-ship collision-avoidance algorithms, using feature-based clustering rather than graph structure. Later work advanced identification and recognition of multi-ship encounters — Louvain community detection (a standard algorithm that partitions a network into densely connected groups) on encounter networks (Li et al. 2025), velocity-obstacle identification (the velocity-obstacle method marks, for each ship, the set of its velocities that would lead to collision with another) of complex multi-vessel scenarios with COLREGs-based decision modelling (Lyu et al. 2024), and graph- and learning-based recognition frameworks (e.g. the same group's spatio-temporal edge- and node-attention graph convolutional network — a neural network that operates directly on graph-structured data — Gao et al. 2024, which learns interaction features from AIS for decision-making) — and extended network risk ranking (WVoteRank, a vote-accumulation centrality method for identifying influential nodes; improved vessel conflict ranking operators; graph-convolutional risk prediction). Case-reuse approaches retrieve similar cases by fuzzy similarity over scalar features (Gai et al. 2024), by multi-scale trajectory-similarity matching between vessel pairs (Chen et al. 2019), or generate encounter scenarios from AIS for algorithm testing (Wang et al. 2024). No published method defines or exploits an isomorphism relation on encounter graphs to select the same multi-ship situations from AIS archives.

Problem Statement

Develop and validate the graph-isomorphism route that Zhu et al. (2022) left open for multi-ship encounter situation graphs mined from AIS data. Concretely: (1) Formalize what it means for two multi-ship encounter situations to be 'the same' situation — an isomorphism notion (or a principled structural-similarity refinement of it) on the ship encounter graphs whose nodes carry ship kinematic attributes and whose edges carry the pairwise encounter identification result and collision-risk weight. The formalization must state exactly which node labels, edge labels and edge weights enter the relation, which invariances it enforces (absolute position and absolute heading of the situation, ship identity, rotation and translation of the geometry, alignment of the temporal evolution), and how much AIS noise and irregular sampling it tolerates, so that the relation is faithful to the navigational semantics of encounter situations under COLREGs. (2) Provide a computationally feasible method that, given a currently unfolding multi-ship encounter situation, selects the same — or most similar — historically observed multi-ship encounter situations from large AIS archives, and demonstrate its retrieval quality at realistic archive scale — concretely, on an AIS archive covering at least one year of records from a busy waterway. (3) Demonstrate that the retrieved historical situations assist multi-ship collision-avoidance decision-making, concretely on at least one waterway beyond the source's single Zhoushan demonstration. The source's companion future-work item — combining the network risk-rank measure with collision-avoidance algorithms other than the artificial potential field method, with further testing — is a separate open item and is not required to resolve this task, whereas deliverables (1)-(3) above are. These three deliverables jointly serve one objective: turning the encounter-network situation-awareness framework into a reusable base of structurally matched multi-ship encounter experience that decision systems — human officers or autonomous-ship algorithms — can consult when resolving current encounters.

References

  1. Zhu, Jixiang; Gao, Miao; Zhang, Anmin; Hu, Yingjun; Zeng, Xi. Multi-Ship Encounter Situation Identification and Analysis Based on AIS Data and Graph Complex Network Theory. Journal of Marine Science and Engineering, 2022, 10(10), 1536. DOI: 10.3390/jmse10101536. URL: https://doi.org/10.3390/jmse10101536 (source paper)
  2. Gao, Miao; Liang, Maohan; Zhang, Anmin; Hu, Yingjun; Zhu, Jixiang. Multi-ship encounter situation graph structure learning for ship collision avoidance based on AIS big data with spatio-temporal edge and node attention graph convolutional networks. Ocean Engineering, 2024, 301, 117605. DOI: 10.1016/j.oceaneng.2024.117605. URL: https://doi.org/10.1016/j.oceaneng.2024.117605 (same-group follow-up)
  3. Li, Yuejin; Yang, Fengkai; Chen, Pengfei; Chen, Linying; Mou, Junmin. Multi-ship Encounter Identification Using Community Detection of Complex Network. TransNav, the International Journal on Marine Navigation and Safety of Sea Transportation, 2025, 19(3), 887-892. DOI: 10.12716/1001.19.03.23. URL: https://doi.org/10.12716/1001.19.03.23
  4. Lyu, Hongguang; Ma, Xiaoru; Tan, Guifu; Yin, Yong; Sun, Xiaofeng; Zhang, Lunping; Kang, Xikai; Song, Jian. Identification of Complex Multi-Vessel Encounter Scenarios and Collision Avoidance Decision Modeling for MASSs. Journal of Marine Science and Engineering, 2024, 12(8), 1289. DOI: 10.3390/jmse12081289. URL: https://doi.org/10.3390/jmse12081289
  5. Tong, Yanting; Zhen, Rong; Dong, Han; Liu, Jialun. Identifying influential ships in multi-ship encounter situation complex network based on improved WVoteRank approach. Ocean Engineering, 2023, 284, 115192. DOI: 10.1016/j.oceaneng.2023.115192. URL: https://doi.org/10.1016/j.oceaneng.2023.115192
  6. Gai, Xudong; Zhang, Qiang; Hu, Yancai; Wang, Gang. A Fuzzy Fusion Method for Multi-Ship Collision Avoidance Decision-Making with Merchant and Fishing Vessels. Journal of Marine Science and Engineering, 2024, 12(10), 1822. DOI: 10.3390/jmse12101822. URL: https://doi.org/10.3390/jmse12101822
  7. Hwang, Taewoong; Youn, Ik-Hyun. Navigation Situation Clustering Model of Human-Operated Ships for Maritime Autonomous Surface Ship Collision Avoidance Tests. Journal of Marine Science and Engineering, 2021, 9(12), 1458. DOI: 10.3390/jmse9121458. URL: https://doi.org/10.3390/jmse9121458
  8. Wang, Shipeng; Gang, Longhui; Liu, Tong; Lan, Zhixun; Li, Congwei. Analysis of the Characteristics of Ship Collision-Avoidance Behavior Based on Apriori and Complex Network. Journal of Marine Science and Engineering, 2025, 13(1), 35. DOI: 10.3390/jmse13010035. URL: https://doi.org/10.3390/jmse13010035
  9. Chen, Shuzhe; Zhang, Chong; Wu, Lei; Wang, Ziwei; Wu, Wentao; Li, Shimeng; Gao, Haotian. Collision Avoidance Behavior Mining Model Considering Encounter Scenarios. Applied Sciences, 2025, 15(5), 2616. DOI: 10.3390/app15052616. URL: https://doi.org/10.3390/app15052616
  10. Wang, Jie; Liu, Shijie; Zhang, Yan. A Graph Learning-Driven Method for Multi-Ship Collision Risk Prediction in Complex Waterways. Journal of Marine Science and Engineering, 2026, 14(7), 658. DOI: 10.3390/jmse14070658. URL: https://doi.org/10.3390/jmse14070658
  11. Wang, Weiqiang; Huang, Liwen; Liu, Kezhong; Zhou, Yang; Yuan, Zhitao; Xin, Xuri; Wu, Xiaolie. Ship encounter scenario generation for collision avoidance algorithm testing based on AIS data. Ocean Engineering, 2024, 291, 116436. DOI: 10.1016/j.oceaneng.2023.116436. URL: https://doi.org/10.1016/j.oceaneng.2023.116436
  12. Chen, Peng; Shi, Guoyou; Liu, Shuang; Gao, Miao. Collision Avoidance Situation Matching with Vessel Maneuvering Actions Identification from Vessel Trajectories. International Journal of Performability Engineering, 2019, 15(6), 1499-1507. DOI: 10.23940/ijpe.19.06.p1.14991507. URL: https://doi.org/10.23940/ijpe.19.06.p1.14991507 (closest situation-matching work: pairwise collision-avoidance situations matched by multi-scale trajectory similarity)
  13. Lee, Jae-Yong; Namgung, Ho; Kim, Joo-Sung. Development of collision-case-based testing scenarios for validating autonomous ship collision-avoidance algorithms. Brodogradnja, 2026, 77(2), 77204. DOI: 10.21278/brod77204. URL: https://doi.org/10.21278/brod77204
  14. Chen, Lijia; Tian, Xiaobin; Liu, Kezhong; Zou, Chun; Chen, Zhennan. Spatiotemporal graph-based identification and classification of dynamic multi-ship encounter scenarios. Ocean Engineering, 2026, 356, 125410. DOI: 10.1016/j.oceaneng.2026.125410. URL: https://doi.org/10.1016/j.oceaneng.2026.125410
  15. Wang, Zhiyuan; Zhou, Lei; He, Wei; Lei, Jinyu; Yu, Chengqiang. A two-stage hybrid learning framework for ship encounter recognition based on AIS data. Ocean Engineering, 2026, 356, 125192. DOI: 10.1016/j.oceaneng.2026.125192. URL: https://doi.org/10.1016/j.oceaneng.2026.125192
  16. Zhang, Xinsheng; Chen, Pengfei; Mou, Junmin; Chen, Linying; Huang, Liwen. A multi-ship encounter risk assessment model based on an improved vessel conflict ranking operator. Ocean Engineering, 2026, 357, 125568. DOI: 10.1016/j.oceaneng.2026.125568. URL: https://doi.org/10.1016/j.oceaneng.2026.125568