scheduler-v2: rendre le robot (un peu plus) intelligent?
Depuis nos débuts à la coupe de France de robotique, nous avons voulu rendre notre robot plus intelligent. Deux des points principaux étaient de le rendre capable de changer dynamiquement sa stratégie pendant le match en réagissant à des situations imprévues, et d’afficher correctement le nombre de points qu’il “pense” avoir obtenus.
Il y a longtemps (je suppose que ça devait être en 2018 ?), nous nous sommes assis à une table lors de la rencontre inter-UT à l’UTC et avons créé les bases d’un cadre simple pour commencer à aborder le problème. L’idée était de définir une stratégie comme une série d’actions, elles-mêmes composées de séries séquentielles de mouvements. Chaque action représente une tâche que le robot doit accomplir pendant le match, tandis que ses mouvements décrivent impérativement comment le faire. Voici un exemple de stratégie écrite en C :
ACTION_REGISTER(SOLAR1, 20, 15, false);
ACTION_REGISTER(SOLAR2, 20, 15, false);
ACTION_REGISTER(COLLECT_PLANTS, 15, 3, false);
ACTION_REGISTER(PUT_PLANTS_IN_GARDEN, 15, 8, false);
ACTION_REGISTER(BACK_TO_BASE, 5, 13, true);
La syntaxe de la macro ACTION_REGISTER est la suivante :
ACTION_REGISTER(
SOLAR1, // nom de l'action
20, // durée supposée, en secondes
15, // nombre de points
false // l'action est-elle critique ?
);
Le premier argument est le nom de l’action. Il correspond en fait au nom de la fonction qui réalise l’action dans le code. Le troisième champ est le nombre de points que l’on peut espérer si l’action est réussie.
Les deuxième et quatrième arguments sont liés à ce que nous appelons le scheduler. Les actions ci-dessus sont censées être effectuées séquentiellement, mais que se passe-t-il si en cas de problème ? Supposons que la première action échoue pour une raison quelconque, que doit-on faire ? Peut-on essayer d’effectuer l’action à nouveau, ou peut-être doit-on essayer les autres et y revenir plus tard ? Dans notre cas, le scheduler est la fonction responsable de répondre à ces questions. Le deuxième paramètre informe le scheduler de la durée attendue d’une action en secondes, et le quatrième indique si une action est critique, ce qui signifie que le scheduler doit toujours réserver suffisamment de temps pour essayer d’effectuer cette action. Cela a été mis en œuvre pour les “actions évidentes” : les actions qui sont si faciles qu’il semble essentiel de les tenter (par exemple, le retour à la base est généralement ce genre d’action).
Lorsque nous avons eu l’idée du scheduler, nous avons anticipé que nous écririons une première version simple (scheduler-v1) et que nous pourrions l’améliorer plus tard. Et c’est ce qui s’est passé ! Sauf que le simple scheduler-v1 est resté là pendant 7 ans… mais nous le remplaçons enfin par le scheduler-v2 de 2025.
Prototypage
Pour prototyper le nouveau scheduler amélioré, nous avions besoin d’un environnement de prototypage rapide, ce pour quoi le C est… assez mauvais. Nous avons donc opté pour common-lisp qui est idéal pour ce genre d’exploration (j’entends déjà tout le monde râler. “Pourquoi pas Python ??” disent-ils, horrifiés. Ce à quoi je réponds : (not (fun 'python))).
Avant de parler du nouveau scheduler amélioré, revenons au scheduler-v1. Essayez de ne pas rire en voyant son code ! Commençons d’abord par écrire quelques structures de données basiques pour imiter le code C :
;; Une "action" imitant la structure C Action
(defstruct action
(name)
(duration-s)
(reward)
(performed nil)
(tries-nb 0)
(critical))
;; Description de l'état du jeu
(defstruct game-state
(match-duration-s 100)
(time-s 0)
(earned-points 0))
Voici maintenant le scheduler, qui est une fonction qui prend l’état actuel du match et les actions disponibles, et retourne la prochaine action à effectuer :
(defun remaining-critical-actions-duration (state actions)
(apply #'+ (mapcar #'action-duration-s (remove-if-not #'action-critical actions))))
;; scheduler-v1
;; ============
(defun get-next-action (state actions)
"Retourne la prochaine action à effectuer en fonction de STATE et des
ACTIONS possibles."
(let ((remaining-duration (- (game-state-match-duration-s state)
(game-state-time-s state)))
(remaining-critical-duration
(remaining-critical-actions-duration state actions)))
(first ; < choisir la première des actions filtrées
;; on filtre les actions qui...
(remove-if
(lambda (action)
(or
;; ... ont déjà été effectuées
(action-performed action)
;; ... ont déjà été tentées 3 fois
(>= (action-tries-nb action) 3)
;; ... ne sont pas critiques et privent les actions critiques de temps
(and (not (action-critical action))
(< (- remaining-duration (action-duration-s action))
remaining-critical-duration))))
actions))))
Comme on peut le voir, la version 1 est assez naïve. Le scheduler effectue les actions dans l’ordre et, si l’une échoue, la retentera au maximum 3 fois lorsque suffisament de temps est disponible. Il essaie toujours de réserver suffisamment de temps pour les actions critiques. Qu’est-ce qui pourrait mal se passer ?
Pour commencer, essayer les actions trois fois avant d’abandonner peut faire perdre énormément de temps au robot1. Le concept d’action critique semble logique, mais si une autre combinaison d’actions était plus optimale ? On devait pouvoir faire mieux.
En écrivant la nouvelle version du scheduler, nous sommes partis des principes suivants :
- Le scheduler doit conserver l’ordre relatif des actions. Il y a souvent des raisons à cet ordre : par exemple, le retour à la base doit toujours être la dernière action pour obtenir des points. Si il serait possible d’ajouter des contraintes d’ordre, nous voulions garder un système simple pour le programmeur fatigué qui doit écrire une stratégie à 4 heures du matin.
- Le scheduler doit essayer de maximiser le score autant que possible.
Comment aborder ce problème tout en gardant un système simple ? Puisque nous voulons conserver l’ordre entre les actions, nous pouvons représenter une solution à notre problème avec une liste binaire. Par exemple :
(1 0 1 1 1)
Signifie qu’on saute la deuxième action (0), mais effectuons toutes les autres (1). Si nous avons assez de temps pour entreprendre toutes les actions, parfait! Sinon, nous pouvons rechercher dans l’espace des solutions la série d’actions optimale possible : celle qui maximise les points obtenus. Dans ce cas, cela s’apparente à une recherche dans un arbre binaire : par exemple, aller à gauche pourrait signifier sauter une action, aller à droite la conserver. Nous écrivons un algorithme récursif de backtracking pour optimiser et couper les branches qui ne sont pas réalistes (par exemple, si une série d’actions prend trop de temps compte tenu du temps restant). Le voici en lisp :
(defun todo-action-p (actions action)
"Retourne `t' si ACTION est un candidat pour être tentée, `nil' sinon."
(let ((last-performed-action-i
(position (car (last (remove-if-not #'action-performed actions))) actions))
(action-i (position action actions)))
;; L'action est candidate si...
(and
;; ... elle n'a pas encore été effectuée
(not (action-performed action))
;; ... ET elle n'a pas été tentée plus de 2 fois
(< (action-tries-nb action) 2)
;; ... ET elle n'a pas encore été sautée car l'algorithme
;; préserve l'ordre
(> action-i (if (null last-performed-action-i) -1 last-performed-action-i)))))
;; scheduler-v2
;; ============
(defun get-next-action (state actions &optional choice-list)
"Retourne la prochaine action à effectuer selon l'état STATE et les
ACTIONS possibles."
(let* ((remaining-duration (- (game-state-match-duration-s state)
(game-state-time-s state)))
(todo-actions (remove-if-not (lambda (action) (todo-action-p actions action))
actions))
(todo-actions-duration (apply #'+ (mapcar #'action-duration-s todo-actions)))
(chosen-todo-actions (loop for action in todo-actions
for choice in choice-list
when (= choice 1)
collect action))
(chosen-todo-actions-duration
(apply #'+ (mapcar #'action-duration-s chosen-todo-actions))))
(cond
;; On peut faire tenir toutes les actions dans le temps restant
;; : on procède simplement dans l'ordre pour éviter d'explorer
;; tout l'arbre des possibilités
((>= remaining-duration todo-actions-duration)
(list (+ (game-state-earned-points state)
(apply #'+ (mapcar #'action-reward todo-actions)))
(first todo-actions)))
;; La solution actuelle est impossible car elle prend trop de
;; temps : on retourne le score actuel
((< remaining-duration chosen-todo-actions-duration)
;; En dernier recours, on tente l'action même si nous
;; anticipons qu'elle ne fonctionnera pas (task_ctrl devrait
;; correctement arrêter le robot de toute façon). On incrémente
;; pas le score car il est probable que cette action ne
;; réussisse pas, pour donner la priorité aux branches qui ont
;; une meilleure chance de se terminer.
(list (game-state-earned-points state) (car (last chosen-todo-actions))))
;; On est arrivés à un nœud feuille : on retourne le score du
;; chemin
((= (length choice-list) (length todo-actions))
(list (+ (game-state-earned-points state)
(loop for action in todo-actions
for choice in choice-list
sum (* choice (action-reward action))))
nil))
;; Cas général : on explore
(t
(let* (;; On explore ce qui se passe si on saute la prochaine action
(skip-next (get-next-action state actions (append choice-list '(0))))
;; On explore ce qui se passe si on garde la prochaine action
(keep-next (get-next-action state actions (append choice-list '(1)))))
;; On garde le meilleur résultat
(if (> (first skip-next) (first keep-next))
skip-next
(list (first keep-next) (nth (length choice-list) todo-actions))))))))
Cette implémentation n’a pas de limite de profondeur, elle retournera donc toujours la série d’actions optimale en termes de score compte tenu du temps restant.
le scheduler-v2 est-il meilleur ? Une expérience simple
Le nouveau scheduler a l’air meilleur, mais l’est-il réellement ? C’est-à-dire, rapporte-t-il plus de points ? Bien sûr, on ne peut pas en être sûrs sans le tester en conditions réelles, mais on peut faire des simulations pour voir à quoi s’attendre. Pour ce faire, nous devons faire quelques hypothèses. On suppose que le programmeur détermine la durée de l’action avec une précision correcte : nous échantillonons la durée à partir d’une distribution uniforme centrée sur l’estimation du programmeur avec un écart maximal de 3 secondes. On suppose également que les actions échouent avec une probabilité de x%.
Avec ces hypothèses, nous pouvons générer plusieurs stratégies, “simuler” un match, et voir quel scheduler nous rapporte le plus de points. Nous générons des stratégies avec la fonction suivante :
(defun generate-strategy ()
(let ((i 0)
(match-duration-s 100)
(actions (list)))
(loop while (< (apply #'+ (mapcar #'action-duration-s actions))
(- match-duration-s 10))
do (progn (push (make-action :name (format nil "ACTION~A" i)
;; durées de l'action entre 10 et 30 secondes
:duration-s (+ 10 (random 21))
;; récompense entre 1 et 20
:reward (+ 1 (random 20)))
actions)
(incf i 1)))
(reverse (cdr actions))))
Nous pouvons voir qu’avec nos hypothèses ci-dessus, le scheduler-v2 l’emporte toujours. La différence entre les deux schedulers augmente à mesure que le taux d’échec augmente, avec une différence allant jusqu’à 6 points à un taux d’échec de 30 %.
Traduction du programme en C
Le scheduler lisp ci-dessus est écrit de manière récursive, car c’est la manière la plus naturelle d’écrire des algorithmes de backtracking. Pour l’inclure dans le robot en C, nous avons dû le réécrire dans un style itératif pour contrôler la mémoire de la pile plus précisément. Par exemple, nous avons ajouté une option pour contrôler la profondeur de la recherche du scheduler, au cas où il deviendrait trop gourmand pour le bien du robot.
-
Le cas s’est présenté en 2024 lors de notre match contre Coffee Machine. Notre robot a dépassé le temps imparti pendant une action en début de match, et a perdu beaucoup de temps. ↩