Overview

Autorouting img 1

The Autorouting project, developed for Navionics , a company specialized in electronic nautical charts, implements an intelligent routing algorithm for marine navigation. Working alongside a company lead developer, we created the Dock-to-dock Autorouting system that received significant recognition in the marine navigation industry, including the SAIL’s 2016 Pittman Innovation Award and a special mention at the MESTRADE DAME Design Award in Amsterdam.

Project Duration and Skills

  • Development Time: 8 months
  • Skills Acquired:
    • Artificial Intelligence algorithms
    • Objective-C development
    • Advanced C++ programming

Project Objective

The project’s goal was to implement a marine navigation routing algorithm that could provide one or more safe navigation routes when given a starting point (or port) and destination. The system considers various parameters including:

  • Vessel dimensions
  • Navigation zone characteristics
  • Safe passage requirements

Technical Implementation

Autorouting img 2

A* Algorithm Implementation

I chose to use A* (A-star), a well-known greedy pathfinding algorithm used for finding paths through graph nodes. The algorithm:

  • Uses a heuristic approach
  • Was modified to include pre-processing and node caching
  • Delivers improved speed and performance through optimizations

Pre-processing Phase

The pre-processing involves:

  • Generating a 2D mask (screenshot) for the chosen route
  • Extracting candidate nodes for the routing algorithm’s selection
  • Creating an optimized navigation graph

Algorithm Details

  • Heuristic: Linear distance between the considered node and the goal (destination node)
  • Cost Function: Distance between the start node and the considered node (n)
  • Navigation Constraints:
    • Land areas
    • Coastal zones
    • Vessel preferences (depth, width)

Deployment and Usage

The algorithm is implemented as a C++ application layer currently used in:

  • Navionics iOS App
  • Navionics Android App
  • Navionics WebApp
  • RayMarine navigation plotters

Awards and Recognition

  • SAIL’s 2016 Pittman Innovation Award
  • Special Mention at MESTRADE DAME Design Award in Amsterdam