Distributed Stochastic Search Algorithm for Multi-ship Encounter Situations
Distributed Stochastic Search Algorithm for Multi-ship Encounter Situations
复制标题
DOI：
10.1017/s037346331700008x
复制
发表时间：
2017-03
影响因子：
2.4
通讯作者：
Donggyun Kim;K. Hirayama;Tenda Okimoto
中科院分区：
文献类型：
--
作者：
Donggyun Kim;K. Hirayama;Tenda Okimoto
船舶避碰包括帮助船舶找到最能避免碰撞的路线。当两艘以上的船只相遇时，程序变得更加复杂，因为一艘船的轻微改变航向可能会影响其他船只的未来决策。针对这一问题，已经发展了两种分布式算法：分布式局部搜索算法（DLSA）和分布式禁忌搜索算法（DTSA）。它们共同的缺点是需要相对大量的信息来协调船只的行动。这可能是致命的，特别是在紧急情况下，需要迅速作出决定。在本文中，我们引入了分布式随机搜索算法（DSSA），该算法允许每艘船在接收到目标船的所有意图后立即以随机方式改变其意图。我们还提出了一个新的成本函数，考虑了这些分布式算法的安全性和效率。我们的经验表明，对于4艘和12艘船的基准测试，DSSA需要的信息要少得多，并且对于来自多佛海峡自动识别系统（AIS）的真实数据也能正常工作。
Ship collision avoidance involves helping ships find routes that will best enable them to avoid a collision. When more than two ships encounter each other, the procedure becomes more complex since a slight change in course by one ship might affect the future decisions of the other ships. Two distributed algorithms have been developed in response to this problem: Distributed Local Search Algorithm (DLSA) and Distributed Tabu Search Algorithm (DTSA). Their common drawback is that it takes a relatively large number of messages for the ships to coordinate their actions. This could be fatal, especially in cases of emergency, where quick decisions should be made. In this paper, we introduce Distributed Stochastic Search Algorithm (DSSA), which allows each ship to change her intention in a stochastic manner immediately after receiving all of the intentions from the target ships. We also suggest a new cost function that considers both safety and efficiency in these distributed algorithms. We empirically show that DSSA requires many fewer messages for the benchmarks with four and 12 ships, and works properly for real data from the Automatic Identification System (AIS) in the Strait of Dover.