FR2688909A1 - Procede de trajectographie de mobiles dans un environnement bruite. - Google Patents

Abstract

L'invention concerne les procédés qui permettent de poursuivre les mobiles repérés par un ensemble de capteurs et de reconstituer leur trajectoire. Elle consiste à effectuer un maillage (101) de l'espace où peuvent se situer ces mobiles et à distribuer sur ce maillage des poids déterminés (102) à partir des mesures des capteurs. Ces poids permettent ensuite de déterminer les chemins les plus probables (103). Pour cela, on modélise l'évolution des cibles à l'aide de chaînes de Markov cachées et on construit les chemins à l'aide de l'algorithme de Viterbi. Elle permet d'effectuer une telle poursuite et une telle reconstitution de trajectoire sans hypothèse et sans modélisation préalable.

Description

PROCEDE DE TRAJECTOGRAPHIE DE MOBILES
DANS UN ENVIRONNEMENT BRUITE
La présente invention se rapporte aux procédés qui permettent de reconstituer, et éventuellement de prédire, ia trajectoire d'un mobile qui est localisé à l'aide de signaux reçus par un ensemble de capteurs. Ces signaux peuvent notamment être des signaux acoustiques reçus par des hydrophones situés dans un milieu marin.

On est souvent amené à déterminer la trajectoire d'un ou de plusieurs mobiles, en vue essentiellement d'effectuer une poursuite de ces mobiles, en utilisant un ensemble de capteurs, par exemple des hydrophones suspendus à des bouées dans le cas de mobile marin. Les signaux recus par les capteurs sont souvent fortement bruités, ce qui entraîne aussi bien de fausses alarmes que des non-détections. Les procédés permettant de mettre en oeuvre les traitements de données nécessaires pour cela doivent être capables de gérer des problèmes d'association de données permettant de rejeter les fausses alarmes, et de déterminer pour les différents capteurs quelles sont les mesures qui proviennent d'un même mobile. Les données propres à chaque mobile ayant été ainsi séparées, on peut alors déterminer les trajectoires de chacun de ces mobiles.

On connaît plusieurs stratégies permettant de résoudre ce problème
En radar, c'est-à-dire essentiellement dans la trajectographie des aéronefs, on cherche surtout à poursuivre chaque cible en temps réel. Le nombre de cibles et les données initiales des trajectoires sont généralement connus, et l'on cherche alors à prédire d'un instant de mesure au suivant l'évolution des caractéristiques de chaque mobile. Ceci étant fait, on ne prend alors en compte pour chaque mobile à l'instant suivant que les mesures qui correspondent le mieux aux caractéristiques ainsi prédites à l'instant précédent. A partir de ces mesures ainsi retenues on réajuste alors les caractéristiques de chaque mobile par rapport aux caractéristiques prévues, et l'on itère ce processus d'instant en instant.

II existe de nombreuses variantes de ce procédé, mais toutes reposent sur un certain nombre d'hypothèses a priori, portant généralement sur le nombre de mobiles connus, les paramètres initiaux des trajectoires, et les modèles retenus pour ces trajectoires, par exemple un mouvement rectiligne uniforme ou un mouvement uniformément accéléré.

En sonar, c'est-à-dire essentiellement pour la trajectographie des bâtiments navals, on cherche plutôt à créer tout d'abord au niveau de chaque capteur des "pistes" c'est-à-dire des séries de mesures correspondant à une même cible. Ceci permet de rejeter au niveau de chaque capteur les fausses alarmes. Les pistes provenant des différents capteurs sont ensuite regroupées, à l'aide de tests permettant de déterminer si elles appartiennent ou non à une même cible. A l'issue de cette étape, on obtient pour chaque cible un ensemble de mesures qui composent les pistes propres à la cible et on peut reconstituer une trajectoire à partir de cet ensemble.

Ces méthodes présentent toutefois 1' inconvénient de nécessiter une certaine part d'empirisme pour la création des pistes, et il est en outre nécessaire de formuler des hypothèses sur la trajectoire des mobiles.

D'autres méthodes sont aussi utilisées, mais toutes ces méthodes classiques reposent sur une modélisation continue de l'évolution des mobiles, ou nécessitent des hypothèses telle qu'une valeur connue a priori pour le nombre de mobiles, ces hypothèses étant très contraignantes.

Pour pallier ces inconvénients, I'invention propose un procédé de trajectographie de mobiles, principalement caractérisé par les étapes suivantes
- définition d'un maillage position/vitesse de l'espace où peut se situer le mobile
- fusion des données provenant d'un ensemble de N capteurs pour déterminer une distribution de poids sur le maillage
- association temporelle de ces donnéespour obtenir un ensemble de chemins
- poursuite du mobile par détermination du chemin le plus court correspondant à ce mobile ; et
- reconstitution de la trajectoire du mobile par détermination des caractéristiques successives les plus vraisemblables.

D'autres particularités et avantages de l'invention apparaîtront clairement dans la description suivante, faite à titre d'exemple non limitatif en regard des figures annexées qui représentent:
- la figure 1, un schéma synoptique d'un dispositif permettant de mettre en oeuvre l'invention;
- la figure 2, un schéma synoptique du dispositif 102 d'association spatiale de la figure i ; et
- la figure 3, un schéma synoptique du dispositif 103 d'association temporelle de la figure 1.

Selon l'invention, les mobiles sont caractérisés par leurs positions déterminées par exemple par leurs coordonnées X, Y dans un repère cartésien plan, et par leurs vitesses, déterminées par exemple par les composantes Vx et Vy des vecteurs vitesse dans ce même repère. On obtient ainsi un espace des cibles, correspondantes à un espace multidimensionnel représenté, toujours dans cet exemple, par ces coordonnées de position et de vitesse X,
Y, Vx, Vy.

Toujours selon l'invention, on divise cet espace caractéristique en un ensemble de cellules jointives, dont les dimensions sont connues et paramétrables. Dans l'exemple considéré, chaque cellule est donc caractérisée par son centre Xi,
Yj, Vxk, Vyk et par ses dimensions AXi, AYj, AVxk et AVyk. On appellera maillage cet ensemble de cellules.

Chaque capteur des signaux provenant d'un mobile est caractérisé par une probabilité Pd de détection d'une cible, et par un taux de fausse alarme Pfa. Pd dépend essentiellement des positions relatives du mobile et du capteur.

Le procédé selon l'invention propose un modèle de calcul de Pd et comprend deux variantes, dont l'une nécessite une connaissance a priori des taux de fausse alarme Pfa. La modélisation de Pd peut s'effectuer de manière différente suivant l'application du procédé, mais si l'on ne connaît pas une valeur exacte de ce paramètre, on calculera pour chacun des capteurs une valeur minimale de celui-ci.

Les capteurs en question peuvent fournir des mesures de différentes natures. Toutefois, pour être utilisées dans l'invention, ces mesures doivent donner un minimum d'informations sur la position des mobiles. On citera à titre d'exemple
- une mesure de distance d, qui détermine un cercle de positions possibles, centré sur le capteur et de rayon d ;
- une mesure d'azimut, qui détermine une demi-droite issue du capteur et orientée selon la valeur de cette mesure
- une mesure de temps de retard, du type plan Codar, qui détermine une hyperbole de position possible ; et
- des observations visuelles, telles que des images de satellite, ou un relevé radar, qui permettent d'obtenir directement les positions des mobiles.

Cette liste de mesures possibles n'est pas limitative, et on peut aussi utiliser des mesures dépendant à la fois de la position et de la vitesse du mobile, comme les mesures Doppler actives ou passives, qui peuvent être couplées à des mesures de distances et/ou d'azimuts. En couplant de telles mesures avec d'autres mesures déterminant uniquement la position des mobiles, on peut obtenir des informations portant uniquement sur la vitesse de ces mobiles. Ainsi, dans le cas d'une mesure Doppler, on obtient un couple Vx, Vy, qui varie par exemple selon l'équation d'une droite.

On a représenté sur la figure i I'organigramme d'un dispositif permettant de mettre en oeuvre le procédé selon l'invention.

Un premier dispositif 101, permet de définir les caractéristiques du maillage retenu c'est-à-dire les dimensions des cellules et les limites de l'espace ainsi maillé. Ces caractéristiques sont retransmises à un dispositif 102, qui permet d'obtenir la fusion des données. Pour cela, à chaque instant de mesure t on recueille une série de mesures sur N capteurs, numérotés conventionnellement de 1 à N. Les mesures recueillies à l'instant t sont donc traitées dans ce dispositif, de manière à attribuer à chaque cellule du maillage un poids représentatif de la probabilité de présence d'un mobile dans cette cellule à l'instant t considéré et en fonction des mesures effectuées à cet instant. Le fonctionnement de ce dispositif sera décrit de manière plus approfondie plus loin.

L'ensemble des données correspondant aux mailles affectées de leur poids est appliqué à un dispositif d'association temporelle de données 103, dont le fonctionnement sera décrit de manière plus approfondie plus loin. Ce dispositif permet de cumuler les informations recueillies aux différents instants de mesure, et qui déterminent les différentes cellules du maillage dans lesquelles le mobile va se trouver à ces différents instants. L'évolution des caractéristiques du mobile, c'est-à-dire généralement sa trajectoire et sa vitesse, est donc caractérisée par une succession temporelle de cellules du maillage. Ce dispositif 103 permet alors de générer et d'attribuer une longueur à des successions de cellules du maillage, ces successions étant appelées conventionnellement chemins. Cette longueur représente la probabilité qu'a une suite de cellules de représenter l'évolution des caractéristiques d'un mobile réel.

Ces successions de cellules sont générées à l'aide de l'algorithme de Viterbi qui permet, de manière connue, de construire, pour toute cellule de maillage et à chaque instant de mesure donné, le meilleur chemin aboutissant à cette cellule, et la longueur correspondante.

Le dispositif 103 délivre donc pour chaque cellule du maillage et à chaque instant de mesure, une succession de cellules aboutissant à celles-ci et une longueur représentative de la vraisemblance de cette succession de cellules.

Les données délivrées par le dispositif 103 sont alors appliquées à un dispositif 104, qui permet de poursuivre en temps réel les mobiles en déterminant, à l'instant de mesure courant, dans quelles cellules aboutissent les chemins les plus vraisemblables, c'est-à-dire ceux dont les longueurs sont les plus faibles. Les caractéristiques les plus vraisemblables des mobiles présents à cet instant sont donc associées à ces cellules. On peut éventuellement utiliser un test portant sur les poids affectés aux cellules, pour déterminer le nombre de mobiles effectivement présents.

Les données délivrées par le dispositif 103 sont également appliquées à un dispositif 105, qui permet de reconstituer les trajectoires correspondant aux meilleurs chemins.

Les cellules successives composant ces chemins permettent alors de déterminer les caractéristiques successives des mobiles les plus vraisemblables, et notamment de représenter leurs trajectoires.

En outre les données issues du dispositif 103 ont été également appliquées en rétroaction sur ce même dispositif 103 pour prendre en compte les données de l'instant t-l précédent.

On a représenté sur la figure 2 un mode de réalisation du dispositif 102 de la figure 1.

A chaque instant de mesure les N capteurs permettent d'obtenir un ensemble de détections auxquelles sont couplées des mesures. Pour chaque cellule du maillage, on divise alors les détections en deux sous-ensembles
Un premier sous-ensemble de détections pouvant correspondre à un mobile situé dans cette cellule.

Un deuxième sous-ensemble de détections ne pouvant pas correspondre à un mobile situé dans cette cellule; ces détections sont alors considérées par rapport à cette cellule comme des fausses alarmes.

De la même manière, on divise l'ensemble des capteurs en deux sous-ensembles
Un premier sous-ensemble D+ de capteurs déterminant une détection correspondant à la cellule, au sens précédent.

Un deuxième sous-ensemble D- de capteurs, ne déterminant pas de détection correspondante à cette cellule, au sens précédent.

Ceci suppose, ce qui dans la pratique est généralement vérifié pour les maillages et les situations habituelles, qu'il ne peut pas y avoir plus d'un mobile dans une cellule quelconque, et donc qu'un capteur ne peut déterminer plus d'une seule détection correspondant à une cellule donnée.

Un dispositif 112 permet donc de déterminer, pour chaque cellule du maillage à chaque instant de mesure, les sousensembles D+ et D-, ainsi que le nombre nfa de fausses alarmes correspondant à cette cellule.

Ces données issues du dispositif 112 sont alors appliquées à un dispositif 122, qui permet de calculer le poids représentatif de la probabilité de présence d'un mobile dans une cellule, ceci pour chaque cellule. On peut pour cela utiliser deux procédés distincts et indépendants pour calculer ces poids
Dans un premier procédé, on utilise un dispositif 132 qui modélise, pour chaque cellule du maillage et pour chaque capteur1 la probabilité de détection par ce capteur d'un mobile situé dans cette cellule du maillage.

Le poids ainsi attribué à cette cellule est alors calculé par la formule suivante, issue de la théorie Bayésienne des probabilités
Poids=Prob(6 / H1)
Dans cette formule 6 est l'ensemble des mesures recueillies à l'instant courant, et H1 est l'hypothèse selon laquelle il y a une cible dans la cellule considérée.

Dans le cas où tous les capteurs ont la même probabilité de fausse alarme, notée Pfa, on obtient

Dans cette formule X = N.Pfa, Pfa est la probabilité de fausses alarmes, et Pd(i) est la probabilité de détection d'une cible située dans la cellule par le capteur n i.

Dans un deuxième procédé, le poids attribué à la cellule est calculé à l'aide de la théorie de l'évidence, qui a été notamment décrite par G.Shafer dans un ouvrage intitulé A Mathematical
Theory of Evidence, Princeton University Press, 1976.

On utilise pour cela deux hypothèses de base, dénommées H1 (présence d'une cible dans la cellule), et H2 (pas de cible dans la cellule).

Ces deux hypothèses permettent de déterminer l'hypothèse complémentaire H3 = H1 ou H2 (on ne sait pas s'il y a une cible ou non dans la cellule).

On définit alors pour chaque capteur les distributions de masses suivantes en fonction de ces hypothèses - si le capteur effectue une détection dans la cellule (D+) m+ ( H1) =Pd
m+ ( H2) = O m+ ( H3) = l-Pd - si le capteur n'effectue pas de détection dans la cellule (D-)
m-(H1) = O
m- (H2) = Pd
m- (H3) = l-Pd
On fusionne ensuite les distributions de masses sur les différents capteurs selon la règle de Dempster, qui est connue dans la théorie de l'évidence citée plus haut. On obtient alors une distribution de masses unique sur les hypothèses Hi, H2 et H3 pour chacune des cellules concernées.

Le dispositif 122 permet ensuite de calculer la crédibilité et la plausibilité de l'hypothèse Hi, au sens où ces fonctions sont définies dans la théorie de l'évidence. Le poids attribué à la cellule courante est alors
poids = plausibilité de l'hypothèse H1
Que l'on utilise le premier ou le deuxième de ces procédés, le dispositif 102 permet d'obtenir sur le maillage une distribution de poids qui représente les probabilités de présence des mobiles sur les différentes cellules de ce maillage, en fonction des mesures recueillies à l'instant de mesure courant.

On a représenté sur la figure 3 un schéma plus détaillé du dispositif d'association temporelle 103. On rappelle que ce dispositif permet de relier entre elles les cellules du maillage susceptibles de représenter les caractéristiques successives des mobiles, à partir de la distribution de poids obtenue précédemment et des caractéristiques du maillage.

Un dispositif 113 permet de calculer les probabilités de transition entre les cellules du maillage entre les instants t-1 et t. On peut utiliser plusieurs techniques pour calculer ces probabilités de transition, par exemple les déduire de l'évolution prévue des caractéristiques de la cible entre l'instant t-i et l'instant t. Ces probabilités sont d'autant plus fortes que la transition est plus vraisemblable. On utilise pour ces calculs les chemins et leurs longueurs. On rappelle qu'un chemin est une succession temporelle de cellules du maillage. Si ces cellules sont symbolisées par un ensemble C, on obtient alors
C = f C1TC2t---rCM }
Dans cette formule M est le nombre total de cellules du maillage, et un chemin est donc défini par une suite
( Ci(tl),Ci(t2),...,Ci(tk) )
Dans cette suite k est le nombre d'instants de mesure, ti...tk sont les instants de mesure successifs, et i I'indice caractéristique du chemin.

La longueur du chemin est alors donnée par
K IC-1 X -Log poids(Ci(tk))+ # -Log(p(Ci(tk) oCi(tk+1) )
k=1 k=1
Dans cette formule "poids (Ci(tk))" est le poids attribué par le dispositif 102 à la cellule Ci(tk) à l'instant tk et p(Ci(tk) -- > Ci(tk+1)) est le coût de la transition entre Ci(tk) et Ci(tk+l).

Les chemins les plus vraisemblables, qui représentent les mobiles effectivement présents, seront les chemins de longueurs les plus faibles.

On peut alors modéliser le problème à l'aide d'une modélisation par chaîne de Markov cachée, telle qu'elle est connue d'un article de Rabiner et Juang, intitulé An Introduction to Hidden
Markov Models, paru dans IEEE-ASSP Magazine, Janvier 86.

En fait cela revient à faire l'amalgame entre les meilleurs chemins et les mobiles1 par l'intermédiaire de leurs caractéristiques.

A partir de ces probabilités de transition, et des distributions de poids sur le maillage, on utilise un dispositif 123 pour construire les chemins de façon itérative en utilisant l'algorithme de Viterbi, tel qu'il est par exemple décrit dans un article de G.D. Forney, intitulé The Viterbi Algorithm, paru dans
Proceedings of the IEEE, volume 61 n03 March 73. Pour cela, à chaque instant on ne retient que le meilleur chemin aboutissant dans chaque cellule du maillage. A partir des chemins ainsi construits jusqu'à l'instant t-l, on se projette à l'instant t en considérant toutes les extensions possibles des chemins entre t-l et t, en calculant leur longueur, et en ne retenant pour chaque cellule à l'instant t que le chemin de longueur la plus courte qui y aboutit, ce qui est proprement dit l'algorithme de Viterbi.

Un dispositif 133 permet ensuite de mémoriser ces chemins au fur et à mesure de leur construction, pour pouvoir les réappliquer de manière itérative au dispositif 123.

On dispose donc pour chaque cellule du maillage en sortie de ce dispositif 133 du meilleur chemin qui y aboutit et de sa longueur.

Le procédé ainsi décrit permet, sans faire aucune hypothèse sur la trajectoire ou le nombre de mobiles, et sans avoir besoin d'une initialisation préalable, de poursuivre simultanément plusieurs mobiles et de reconstituer à terme leur trajectoire. II repose, comme on l'a vu, sur la modélisation par chaînes de Markov
Cachées de l'évolution des cibles et sur l'utilisation de l'algorithme de Viterbi. Dans une variante on utilise également la théorie de l'évidence. On notera que ce procédé est plus général que certains autres procédés connus qui utilisent des modèles d'Etat nettement plus restrictifs que notre procédé.

Claims (4)

REVENDICATIONS

1. Procédé de trajectographie de mobiles, caractérisé par les étapes suivantes

- définition d'un maillage position/vitesse (101) de l'espace où peut se situer le mobile

- fusion des données (102) provenant d'un ensemble de N capteurs pour déterminer une distribution de poids sur le maillage

- association temporelle de ces données (103) pour obtenir un ensemble de chemins

- poursuite du mobile (104) par détermination du chemin le plus court correspondant à ce mobile ; et

- reconstitution de la trajectoire du mobile (105) par détermination des caractéristiques successives les plus vraisemblables.

2. Procédé selon la revendication 1, caractérisé en ce que la fusion des données est faite en déterminant les poids (132) par une formule Bayésienne.

3. Procédé selon la revendication 1, caractérisé en ce que la fusion des données est effectuée en déterminant les poids (132) par la théorie de l'évidence.

4. Procédé selon l'une quelconque des revendications 1 à 3, caractérisé en ce que l'association temporelle des données (103) s'effectue à l'aide d'une modélisation par chaînes de Markov cachées incluant un calcul des probabilités de transition entre les instants successifs, et que la construction des chemins (123) s'effectue à partir des poids issus de la fusion de données et des probabilités de transition ainsi déterminées en utilisant un algorithme de Viterbi.