Panoramica

Autorouting img 1

Il progetto Autorouting, sviluppato per Navionics , azienda specializzata in carte nautiche elettroniche, implementa un algoritmo di routing intelligente per la navigazione marina. Lavorando insieme a un lead developer interno all’azienda, abbiamo creato il sistema Dock-to-dock Autorouting che ha ricevuto importanti riconoscimenti nell’industria della navigazione marina, tra cui il SAIL’s 2016 Pittman Innovation Award e una menzione speciale al MESTRADE DAME Design Award ad Amsterdam.

Durata del Progetto e Competenze

  • Tempo di Realizzazione: 8 mesi
  • Conoscenze Acquisite:
    • Algoritmi di intelligenza artificiale
    • Sviluppo in Objective-C
    • Approfondimento C++

Obiettivo del Progetto

Il fine del progetto è stato l’implementazione di un algoritmo di routing per la navigazione marina che, scelto un punto di partenza (o un porto) e uno di destinazione, fornisse una o più route di navigazione sicura. Il sistema considera vari parametri tra cui:

  • Dimensioni dell’imbarcazione
  • Caratteristiche delle zone di navigazione
  • Requisiti di passaggio sicuro

Implementazione Tecnica

Autorouting img 2

Implementazione Algoritmo A*

Ho scelto di usare A* (A-star), un algoritmo di pathfinding (greedy) famoso in letteratura e usato per trovare un percorso su nodi di un grafo. L’algoritmo:

  • Fa uso di un’euristica
  • È stato modificato per avere una fase di pre-processing e caching dei nodi
  • Offre migliore velocità e performance grazie alle ottimizzazioni

Fase di Pre-processing

Il pre-processing consiste in:

  • Generazione di una maschera bidimensionale (screenshot in 2D) per il percorso scelto
  • Estrazione dei nodi candidati per la scelta dell’algoritmo di routing
  • Creazione di un grafo di navigazione ottimizzato

Dettagli dell’Algoritmo

  • Euristica: Distanza lineare fra il nodo considerato e il goal (nodo di destinazione)
  • Funzione di Costo: Distanza fra il nodo di partenza e quello considerato (n)
  • Vincoli di Navigazione:
    • Zone di terra
    • Zone costiere
    • Preferenze dell’imbarcazione (profondità, larghezza)

Distribuzione e Utilizzo

L’algoritmo fa parte di uno strato applicativo in C++ utilizzato attualmente su:

  • App iOS Navionics
  • App Android Navionics
  • WebApp Navionics
  • Plotter di navigazione RayMarine

Premi e Riconoscimenti

  • SAIL’s 2016 Pittman Innovation Award
  • Menzione Speciale al MESTRADE DAME Design Award ad Amsterdam

Sorgenti sotto NDA forniti parzialmente.