I percorsi del navigatore

I percorsi del navigatore

Questo post nasce da una riflessione assolutamente personale nata una sera chiacchierando con una mia carissima amica, con cui ho studiato e condiviso gioie e disperazioni della facoltà di ingegneria informatica. Sedute in macchina discutevamo di quanto spesso tutti noi ci scordiamo del lavoro e del tempo speso da ricercatori nel settore pubblico e privato che hanno contribuito allo sviluppo di strumenti e tecnologie utilizzate quotidianamente e date ormai per scontate.

Un esempio? In questo periodo viaggi o semplicemente fughe di fine settimana sono (auspicabilmente) comuni e cosa faremmo senza il nostro fido navigatore, che sia su smartphone o cablato nella nostra automobile? Certo, potremmo ricorrere alle buone vecchie mappe, ma quanto è più comodo avere tutto sul nostro cellulare? Per questo e per tanti altri motivi vorrei darvi un brevissimo scorcio di quali sono le pietre miliari che hanno portato, spesso inconsapevolmente, al navigatore così come lo conosciamo oggi. Mi scuso per l’eccessiva sintesi e per eventuali inaccuratezze, mi rendo conto di non essere “specialista” del mestiere, tuttavia ho pensato che lo scopo del post potesse in qualche modo farmi perdonare dagli occhi più esperti che leggeranno questo post.

Non me ne vogliano le persone che hanno duramente lavorato sul rendering dei navigatori, ma, almeno per ora, ho scelto di soffermarmi sui primi due punti essenziali, senza i quali di sicuro i navigatori non esisterebbero: la localizzazione e il calcolo del percorso.
Dove sono? Breve storia del GPS

1972 – 1985 – Iniziano gli esperimenti. Nel 1972 la USAF (United States Air Force) sviluppa i primi prototipi  con dei satelliti GPS “a terra” (in inglese “ground based”) . Nel 1975 viene lanciato il primo satellite ed entro il 1985 si arriva a 10 satelliti GPS.

1982 – la Texas Instruments e nello specifico Phillip W. Ward, progetta il primo navigatore GPS per uso commerciale: TI 4100 NAVSTAR Navigator. Nel 2008 Phillip Ward riceve il Kepler award.

1986 – 1993 – Vengono lanciati altri satelliti arrivando a 24 satelliti operativi nel 1993.  Il sistema di localizzazione GPS, basato sulla cosiddetta trilaterazione, viene sviluppato dal Dipartimento della Difesa Americana (USDOD) e utilizzato per la prima volta durante la Guerra del Golfo (’90-‘91). Per chiarirci la trilaterazione calcola la posizione dell’oggetto a partire dal tempo impiegato da un segnale radio a percorrere la distanza satellite-ricevitore. A fine 1993 grazie all’utilizzo di orologi atomici, precisi al miliardesimo di secondo, viene migliorata la precisione di calcolo.

1994 – 2000 – Continuano i lanci satellitari ma soprattutto il governo degli Stati Uniti dichiara che il sistema satellitare per la localizzazione deve diventare anche un bene per i civili. Inizia un percorso che terminerà nel 2000 con lo spegnimento del sistema di “Selective Availability” che impediva l’apertura dei segnali GPS

2004 – la Qualcomm annuncia i primi successi di dispositivi di localizzazione tramite GPS assistito da reti cellulari

Oltre 2004 – proseguono i lanci dei satelliti e le ricerche per migliorare la precisione e l’affidabilità del posizionamento
Come ci arrivo? Breve storia degli algoritmi per il calcolo del percorso

1959 – Edsger Dijkstra fisico teorico / informatico pubblica “A note on two problems in connexion with graphs” il primo algoritmo del calcolo del percorso più breve dati due nodi su un grafo (reference).

1969 – Ira Pohl matematico / informatico pubblica “Bi-directional and heuristic search in path problems” miglioramento all’algoritmo di Dijkstra rendendolo meno oneroso in termini computazionali (in pratica ci si mette di meno a calcolare il percorso)

A questo punto si susseguono teorie sperimentali per gestire situazioni complesse (grandi centri abitati con mappe fitte).

Intanto nel 1999 viene rilasciato dalla Benefon (società finlandese) il primo cellulare con GPS integrato e nel 2001 il primo TomTom.

2005 – Sanders e Schultes applicano il concetto di gerarchia e portano l’algoritmo ad un ulteriore livello di ottimizzazione.

Dal 2006 al 2008 sono state sviluppate combinazioni di algoritmi basati su gerarchie con logiche euristiche, in inglese “goal directed”. In pratica la ricerca del percorso viene “guidata” passo passo da regole specifiche (dette euristiche) per evitare fondamentalmente che ogni volta si controlli ogni possibile percorso. A questo punto la creatività ha dato particolare sfogo generando una decina di diversi algoritmi.

Thanks to: al gruppo di ricercatori e amici dell’Università Tor Vergata che lavorano sull’ardua impresa di ottimizzare i percorsi del trasporto pubblico in Italia.