A bidirectional path-finding algorithm and data structure for maritime routing
Article dans une revue avec comité de lecture
Date
2014Journal
International Journal of Geographical Information ScienceAbstract
Route planning is an important problem for many real-time applications in open and complex 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 minimizing distance and computational time.
Files in this item
Collections
Related items
Showing items related by title, author, creator and subject.
-
Communication avec acteThis paper introduces an algorithm for retrieving semantic information from a maritime corpus. The method is based on Natural Language Processing (NPL) and combines a segmentation of large documents with principles of a ...
-
Article dans une revue avec comité de lectureThe modeling of a landscape environment is a cognitive activity that requires appropriate spatial representations. The research presented in this paper introduces a structural and semantic categorization of a landscape ...
-
Communication avec acteOver the past decade, automated systems dedicated to geopositioning have been the object of considerable development. Despite the success of these systems for many applications, they cannot be directly applied to qualitative ...
-
Communication avec acteLAMOTTE, Léa; ABADIE, Nathalie; SAUX, Eric; KERGOSIEN, Eric (RNTI, 2020-01-27)Les référentiels de données géoréférencées sont de plus en plus utilisés pour permettre l'annotation spatiale de documents textuels et ainsi faciliter l'accès à leur contenu, voire son analyse spatiale. En revanche, peu ...
-
Communication avec acteRAWSTHORNE, Helen Mair; ABADIE, Nathalie; KERGOSIEN, Eric; DUCHÊNE, Cécile; ERIC, SAUX (Association française pour l'Intelligence Artificielle, 2022-06-14)Les Instructions nautiques sont une série d’ouvrages produits et publiés par le Service hydrographique et océanographique de la Marine (Shom) qui donnent aux navigateurs les informations nécessaires pour naviguer près des ...