Route planning is an important problem for many real-time applications in open andcomplex environments. The maritime domain is a relevant example of such environments where dynamic phenomena and navigation constraints generate difficult route finding problems. This paper develops a spatial data structure that supports the search for an optimal route between two locations while minimizing a cost function. Although various search algorithms have been proposed so far (e.g. breadth-first search, bidirectional breadth-first search, Dijkstra’s algorithm, A*, etc.), this approach provides a bidirectional dynamic routing algorithm which is based on hexagonal meshes and an iterative deepening A* (IDA*) algorithm, and a front to front strategy using a dynamic graph that facilitates data accessibility. The whole approach is applied to the context of maritime navigation, taking into account navigation hazards and restricted areas. The algorithm developed searches for optimal routes while minimizingdistance and computational time.
展开▼
机译：对于开放和复杂环境中的许多实时应用程序而言，路由规划是一个重要问题。海域是这种环境的相关示例，在这种环境中，动态现象和导航约束会产生困难的路线查找问题。本文开发了一种空间数据结构，该结构在最小化成本函数的同时，支持在两个位置之间搜索最佳路线。尽管到目前为止已经提出了各种搜索算法（例如，广度优先搜索，双向广度优先搜索，Dijkstra算法，A *等），但是该方法提供了一种基于六边形网格和迭代加深的双向动态路由算法。 A *（IDA *）算法，以及使用动态图的从前到前的策略，可促进数据可访问性。考虑到航行危险和限制区域，整个方法适用于海上航行。开发的算法在最小化距离和计算时间的同时搜索最佳路线。
展开▼
