3 Idée en vue de l'élaboration d'un algorithme de suivi d'un signal

Comme nous l'avons indiqué au début de cette section, le suivi d'un signal s'effectue en utilisant une séquence de segments associés chacun à une action interne particulière. Cette dernière est choisie dans un ensemble fini A = $\left\{\vphantom{a_{1},a_{2},...,a_{q}}\right.$a₁, a₂,..., a_q$\left.\vphantom{a_{1},a_{2},...,a_{q}}\right\}$, spécifié a priori. Chaque action permet à un segment de se déplacer selon un schéma prédéterminé, qui lui est spécifique. Par défaut, nous choisirons des actions faisant déplacer le segment selon un mouvement uniforme. Cependant, celles-ci pourraient être plus complexes et se composer d'une séquence d'actions dont chacune d'entre-elles possède un mouvement uniforme.

Définition _s   Dans la suite de ce recueil, nous appellerons focus la donnée d'un segment S et d'une action a_k, c'est-à-dire le quadruplet (l, h, i, a_k).

Par conséquent, la position d'un focus est connue parfaitement à tout instant dès qu'on a déterminé sa position d'initialisation. Donc, lorsqu'un focus est créé à un endroit précis du segment [0,1], on effectue implicitement une hypothèse sur la nature de la densité de probabilité du signal, mais aussi sur la direction et la vitesse de son déplacement, du moins localement. Tant que les contraintes associées à ce focus seront respectées, on considérera que le focus suit effectivement le signal dans son déplacement (avec une certaine marge d'erreur sur le positionnement du focus, comme nous l'avions signalé dans le paragraphe précédent).
Il est bien évident qu'un unique focus ne peut pas permettre de suivre un signal indéfiniment et qu'à un instant donné les contraintes ne seront plus satisfaites (en raison d'une des deux éventualités données dans le paragraphe précédent): c'est donc une séquence temporelle de focus qui permettra le cas échéant de suivre le signal de bout en bout. Le problème est de savoir à quel moment il faut générer un autre focus. Cependant, il est difficile de formuler un critère relatif à l'écart de position entre la valeur du signal à un instant t et le centre du focus. De plus, cela serait contraire à notre démarche: si un focus respecte ses contraintes, c'est qu'il est censé suivre le signal, sans pour autant que cela nous donne une idée de cet écart de position. Celui-ci ne peut pas être déterminé de manière certaine (avec une probabilité égale à 1 - $\epsilon$ ) à un instant donné, donc nous n'utiliserons pas cette information. D'autre part, formuler un critère signifie en fait ébaucher un algorithme de suivi de signal: là encore, cela est contraire à notre approche pour laquelle aucune connaissance a priori ne doit être introduite (voir le paragraphe 1.2.2): à moins que ce critère soit universel, il ne fonctionnera que sur une partie des signaux possibles.
Notre démarche est similaire à la démarche évolutionniste. Nous considérons un ensemble de focus initiaux, à l'instant t=0, chacun de ceux-ci possédant des caractéristiques propres. Á chaque pas de temps, le signal vient frapper ou non chacun des focus, leur permettant de respecter ou non leur contrainte individuelle. Le déplacement de chacun d'entre-eux va leur permettre ou non d'être frappé par le signal de manière à respecter leur contrainte (figure 2.24). La ``mort'' d'un focus intervient lorsque celui-ci ne respecte plus sa contrainte. Pendant la ``vie'' d'un focus, il peut, sous certaines conditions, générer d'autres focus, permettant de continuer la poursuite du suivi du signal. Un focus donne naissance à d'autres focus en leur donnant sa mémoire (données contenues dans sa file d'attente). Par conséquent, un focus ``fils'' hérite des erreurs que son père a commises (dans la limite de l'horizon de sa mémoire). Le fait qu'à un instant donné plus aucun focus n'est ``vivant'' signifie qu'on a échoué à suivre le signal.
Le problème principal réside dans la génération de nouveaux focus; intuitivement, il paraît évident qu'un focus ``mort'' ne puisse pas générer de nouveaux focus. Comme nous l'avons dit précédemment, nous n'avons aucune possibilité de savoir, parmi l'ensemble des focus ``vivants'', lequel ou lesquels sont susceptibles de générer une séquence de focus ``viables''. A contrario, si on permet à l'ensemble des focus ``vivants'' de générer un ensemble de nouveaux focus à chaque pas de temps, le nombre de focus ``vivants'' va croître exponentiellement, rendant le processus irréaliste du point de vue de sa mise en pratique. Pour donner un exemple, considérons un ensemble de focus dont le nombre limite d'erreurs est 3. Cela signifie que la durée de vie minimum de ceux-ci est de 4 pas de temps. En admettant que chacun puisse générer 10 nouveaux focus et qu'il y ait 10 focus à l'instant t=0, le nombre de focus à t=3 est 10 + 10² + 10³ = 1110. Il faut donc soumettre la possibilité de génération de focus à un critère, pour éviter l'explosion combinatoire du nombre de focus. Un algorithme allant dans ce sens est donné dans le paragraphe 2.2.5.

Figure 2.24: Évolution d'un ensemble de trois focus sur trois pas de temps.

À l'instant t=0, trois focus sont créés, dont le centre commun est l'impact du signal. Le focus (a) se déplace vers la gauche, (b) vers la droite et (c) est immobile. Chacun est supposé être configuré de manière à supporter au maximum deux ``erreurs''. Or, le focus (b) ne capte pas le signal à deux reprises (t=1 et t=2). Donc, à t=2, on sait que ce dernier ne respecte pas ses contraintes: il est éliminé.