Contraintes du système subissant l'AO

Le problème lié au marquage des états provient de l'ignorance a priori de l'effet des actions sur le passage d'un état à l'autre (on suppose qu'on ne possède pas de modèle de la dynamique du problème). Nous allons considérer que, dans ce cadre, le choix de l'action peut être vu comme un problème de prise de décision associé à un jeu à deux joueurs: un joueur serait le système (qui possède, à chaque pas de temps, q coups possibles), alors que l'autre joueur serait la dynamique du système. À chaque instant, l'objectif du système est d'empêcher son adversaire (la dynamique) de le pousser vers l'état terminal, ce qui signifierait la perte de la partie (échec du respect des contraintes).
La propriété ( $P_{\epsilon }$) nous indique que l'adversaire ne peut utiliser qu'un coup, avec une probabilité proche de 1. Mais, la nature de ce coup est inconnue a priori: c'est l'expérience qui la précise.
Nous nous inspirons de l'algorithme minimax [Rich, 1983], dans le but de déterminer la valeur des marquages associés à chaque état. Voici l'énoncé de la contrainte d'équilibre, valable pour chaque état, à chaque pas de temps. Celle-ci précise la valeur du marquage $M_{i}$ de chaque état perceptif $e_{i}$ ainsi que le marquage $M_{i,k}$ de chaque état transitoire $e_{i,k}$, en fonction du marquage des états connectés à ces derniers:

$$\left\{ \begin{array}{c} \forall i \in \{1,...,n\},\:\:M_{i} = \... ...,q\},\:\:M_{i,k} = \alpha.\min_{j \in V(M_{i,k})}\{ M_{j}\} \end{array}\right.$$ (6)

$V(M_{i,k})$ est l'ensemble des indices des états perceptifs vers lesquels une transition issue de l'état transitoire $M_{i,k}$ aboutit. On supposera que si $V(M_{i,k})$ est vide, alors $M_{i,k}$ vaut 0. Cette supposition est importante pour que l'ensemble des marquages initiaux soient cohérents (voir la sous-section 2.2.5). Dans le cas où $\alpha < 1$, $\alpha(M_{j})$ vaut 1 lorsque $M_{j}$ est égal à -1 ou 0, est égal à $\alpha \in ]0,1]$ si $M_{j} \in \{1, \alpha, ..., \alpha^{d-1}\}$ et est égal à 0 si $M_{j} = \alpha^{d}$. Dans le cas particulier où $\alpha = 1$, on fixera $\alpha(M_{j})$ à 1, quel que soit $M_{j}$. La contrainte appliquée au graphe d'états lie les valeurs des marquages associés à des états voisins (reliés par une transition). Nous verrons qu'il existe une différence entre les algorithmes Cb1(1) et CbL($\alpha$), dans le cadre d'un problème d'atteinte d'objectif. Néanmoins, cette différence n'apparaît pas dans les propriétés essentielles de l'algorithme CbL. Donc, nous ne considérerons dans un premier temps que l'algorithme CbL(1). Les graphes d'états servant d'exemple utiliseront l'équation 2.1 en prenant $\alpha = 1$.