Un algorithme de prédiction de lheure darrivée de bus utilisant un système de localisation...

Un algorithme de prédiction de l’heure d’arrivée de bus utilisant

un système de localisation automatique

Le but

• Prédire en temps réel l ’heure d ’arrivée du véhicule pendant son parcours.

Les contraintes

• Le flux de données peut être discontinu.

• L ’incertitude doit être estimée.

Principe général

• Repérage du véhicule

• Estimation du temps de parcours restant

L’algorithme

Outil de reperage

=U

=y =x

Equations

Solution de Kalman

• En l’absence de données mesurées

Solution de Kalman

• Lors de l'arrivée de données

Outil de prédiction

Associer un temps restant à chaque position

Utilisation de données historiques

Traitement statistique• On définit en chaque point une variable aléatoire

représentant le temps restant.

• Chacune de ces variables a une répartition gaussienne.

• On calcule le temps restant avec la fonction On calcule le temps restant avec la fonction obtenueobtenue

Tests de performance

Les erreurs à 15mn

Conclusion

• Une application à Seattle: mybus.org

• http://mybus.org

Le filtre de Kalman

Principe

Estimer l'état d’une variable gouvernée par une équation du type:

A l’aide d’une valeur mesurée du type:

w et v sont les parties aléatoires de distribution gaussienne

Resultat:

• L’algorithme de Kalman fournit une estimation de x optimale au sens des moindres carrés.

Pour en savoir plus sur les filtres de Kalman

• http://www.cs.unc.edu/~welch/kalman/kalman_filter/kalman.html

• http://www.navtechgps.com/seminars/sem411.asp• http://www.cs.rochester.edu/users/faculty/dana/

index.html• http://www.hepl.harvard.edu/~rlee/minos/kalman/