💻 computer science

UDAQ: Unified Dynamic and Adaptive Q-iteration for Unknown Environment Path Planning and Exploration

Cet article introduit UDAQ, un cadre d'itération Q unifié et piloté par la récompense qui s'adapte de manière autonome à l'évolution dynamique des espaces d'états afin d'optimiser simultanément la planification de trajectoires de point à point et l'exploration efficace de l'environnement, surpassant de manière significative les planificateurs conventionnels et les stratégies d'exploration dans des environaux inconnus sans connaissance préalable de la carte.

Auteurs originaux : Nasr Abdalmanan, Kamarulzaman Kamarudin, Muqri Zinal, Mohd Rizal Manan, Victor Bennetts

Publié 2026-07-30

📖 9 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Nasr Abdalmanan, Kamarulzaman Kamarudin, Muqri Zinal, Mohd Rizal Manan, Victor Bennetts

Article original sous licence CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un robot lâché dans un labyrinthe plongé dans le noir total qu'il n'a jamais vu auparavant. Ses seuls outils sont une paire d'« yeux » (capteurs) capables de voir quelques pas devant lui et un cerveau qui doit résoudre deux problèmes à la fois : « Comment atteindre ce point précis là-bas ? » et « Comment cartographier toute la pièce sombre pour ne pas me perdre ? » C'est le quotidien d'un robot autonome, un domaine de la science appelé la robotique mobile. Pour qu'un robot puisse survivre dans le monde réel, il a besoin de la planification de trajectoire (tracer une ligne sûre du point A au point B) et de l'exploration (vérifier systématiquement les zones inconnues pour construire une carte mentale). Traditionnellement, les ingénieurs ont traité ces tâches comme deux métiers distincts, engageant un « programme » pour décider où aller et un autre pour déterminer comment s'y rendre. Mais dans un monde qui change à mesure qu'on le regarde, garder ces fonctions séparées peut mener à la confusion, comme un conducteur qui demande son chemin à un passager alors que celui-ci est encore en train de lire la carte.

Entrez en scène UDAQ (Unified Dynamic and Adaptive Q-iteration), un nouveau cadre proposé par les chercheurs Nasr Abdalmanan et son équipe de l'Université de Perlis et de l'Université d'Örebro. Considérez UDAQ non pas comme un robot doté de deux cerveaux distincts, mais comme un navigateur unique et super-adaptatif qui apprend à tout faire grâce à un jeu de « chaud et froid ». Au lieu de basculer entre différents modes, UDAQ utilise un ensemble unique de règles (un système de récompense) pour enseigner au robot comment se comporter. Si le robot doit trouver une porte spécifique, le « jeu » le récompense pour s'être rapproché de cette porte. Si le robot doit cartographier un bâtiment entier, le « jeu » le récompense pour avoir trouvé de nouveaux coins inexplorés. Le tour de magie réside dans le fait que ce système ajuste automatiquement ses propres niveaux de difficulté à mesure que le robot découvre le monde. Si le labyrinthe s'agrandit, UDAQ augmente l'échelle de ses récompenses pour que le robot ne soit ni découragé ni confus. Dans une série de simulations informatiques, cette approche s'est révélée être une méthode plus rapide, plus fluide et plus efficace pour permettre aux robots de naviguer dans des espaces inconnus par rapport aux méthodes standards actuellement utilisées dans l'industrie.

Le Problème : La « Personnalité Splitée » du Robot

Imaginez que vous exploriez une immense grotte obscure. Vous avez une lampe de poche qui n'éclaire qu'un petit cercle autour de vous. Pour atteindre la sortie, vous devez connaître le chemin. Pour construire une carte, vous devez errer dans le noir. La navigation robotique classique sépare souvent ces tâches en deux équipes distinctes. Une équipe, l'Explorateur, dit : « Va trouver la limite du monde connu ! ». L'autre équipe, le Planificateur, dit : « D'accord, maintenant trace une ligne vers cette limite ».

Le problème est que ces deux équipes ne communiquent pas bien entre elles. L'Explorateur peut choisir une cible qui semble proche mais qui se trouve en réalité derrière un mur, et le Planificateur doit alors perdre du temps à calculer un détour. Ou encore, la carte peut changer pendant que le Planificateur travaille, rendant l'ancien plan inutile. C'est comme essayer de conduire une voiture où le GPS et le volant sont contrôlés par deux personnes différentes qui se disputent sur la destination.

La Solution : Un Seul Cerveau, Plusieurs Humeurs

Les chercheurs derrière UDAQ ont décidé de ne plus diviser l'équipe. Ils ont construit un système où le robot possède un seul cerveau qui gère à la fois l'exploration et la planification, mais qui change d'« humeur » selon ce que vous voulez qu'il fasse. Ils appellent cela un cadre de Unified Dynamic and Adaptive Q-iteration.

Voici comment cela fonctionne, en utilisant une analogie simple :

Le Jeu du « Chaud et Froid »
Imaginez que le robot joue à un jeu vidéo où il gagne des points (récompenses) en se déplaçant.

Humeur 1 : Le Chasseur d'Objectifs. Si vous dites au robot : « Va vers la porte rouge », le jeu lui donne une énorme pile de points pour chaque pas vers la porte. Il lui inflige aussi de petites pénalités s'il marche en rond. Le robot apprend à se précipiter vers la porte, mais s'il heurte un mur, il recalcule instantanément le meilleur chemin pour le contourner.
Humeur 2 : Le Cartographe. Si vous dites au robot : « Explore tout », le jeu change. Désormais, le robot reçoit les plus gros points lorsqu'il trouve des frontières — ces contours flous où la carte connue rencontre l'obscurité inconnue. Il ignore la porte rouge et se précipite plutôt vers le coin inexploré le plus proche.
Humeur 3 : L'Explorateur Directionnel. Vous pouvez même dire au robot : « Explore, mais dirige-toi principalement vers le Nord ». Le robot cherchera toujours de nouvelles zones, mais il donnera la priorité à celles qui sont au Nord, créant ainsi un schéma d'exploration spécifique.

Le génie de UDAQ est qu'il n'a pas besoin de changer de logiciel pour changer d'humeur. Il change simplement les règles du jeu (la configuration des récompenses) tout en gardant le même cerveau en fonctionnement.

La Recette Secrète : La Récompense « Élastique »

Il existe un problème délicat avec ces jeux. Si le robot se trouve dans une petite pièce, une récompense de « 10 points » peut sembler énorme. Mais si le robot découvre soudainement un immense hall, ces mêmes « 10 points » peuvent paraître trop faibles pour motiver le robot à traverser toute la pièce. Le robot pourrait être confus et arrêter d'essayer, ou prendre de mauvaises décisions parce que les calculs ne sont plus cohérents.

UDAQ résout cela avec un mécanisme Dynamique et Adaptatif. Pensez-y comme à une règle extensible.

Le robot mesure constamment la taille de l'espace qu'il a découvert jusqu'à présent. Il calcule le chemin le plus long qu'il pourrait parcourir dans la carte connue (le « diamètre géodésique »).
En fonction de cette taille, il recale la valeur des récompenses automatiquement. Si la pièce est immense, les points valent plus. Si la pièce est petite, les points valent moins.
Cela garantit que le robot perçoit toujours correctement les signaux du « chaud et froid », peu importe la taille du labyrinthe. Cela l'empêche de rester « bloqué » ou de prendre de mauvaises décisions simplement parce que l'environnement a changé.

Ce que les Simulations ont Montré

Les chercheurs ont testé UDAQ dans trois mondes virtuels différents, allant d'un simple entrepôt ouvert à un bâtiment complexe avec des couloirs étroits et de nombreuses pièces. Ils l'ont comparé aux méthodes standards utilisées dans l'industrie (comme le planificateur ROS 2 NavFn) et à d'autres stratégies d'exploration (comme le « suivi de mur » ou la « marche aléatoire »).

1. Aller de A à B (Planification de Trajectoire)
Lorsqu'il fallait que le robot aille d'un point de départ à un point d'arrivée dans un environnement inconnu :

UDAQ a trouvé des chemins 8 à 12 % plus courts que le planificateur standard.
Il a terminé le trajet 20 à 30 % plus vite.
Même sans connaître la carte au préalable, les trajectoires de UDAQ étaient presque aussi bonnes que le chemin « parfait » qu'un humain pourrait tracer s'il connaissait toute la carte dès le début.

2. Explorer toute la pièce (Exploration)
Lorsqu'il fallait que le robot cartographie l'intégralité de l'environnement :

UDAQ a été le grand vainqueur. Il a parcouru une distance 36 à 44 % moindre que la méthode standard basée sur les « frontières » (qui est l'approche traditionnelle la plus performante actuellement).
Il a terminé l'exploration 48 à 59 % plus rapidement.
Dans la carte la plus complexe (Carte C), la méthode standard de « marche aléatoire » est restée coincée dans un couloir étroit et n'a pas pu terminer la tâche, tandis que UDAQ a navigué avec fluidité et a accompli sa mission.

3. Le Test de la « Direction »
Dans une expérience, les chercheurs ont demandé au robot d'explorer le bâtiment complexe mais avec un biais vers une direction spécifique (comme « principalement vers le Sud »).

Lorsque la direction correspondait à la disposition du bâtiment (vers le Sud), le robot était incroyablement efficace, prenant le chemin le plus court.
Lorsque la direction était « mauvaise » (vers l'Ouest), le robot empruntait un itinéraire plus long et sinueux.
Cela a prouvé que UDAQ peut être « piloté » pour explorer dans un ordre spécifique, ce qui peut être utile si l'on sait que certaines pièces sont plus importantes que d'autres.

Le Bémol : Ce n'est encore qu'une Simulation

Bien que les résultats soient impressionnants, les chercheurs précisent que tous ces tests ont été effectués dans des simulations informatiques. Les robots vivaient dans un monde numérique parfait où les capteurs ne buggaient jamais, les roues ne glissaient pas et les cartes étaient toujours précises. Dans le monde réel, les robots font face à des problèmes complexes comme un mauvais éclairage, des sols glissants et des capteurs bruyants. L'article suggère que UDAQ est un candidat très sérieux pour une utilisation réelle, mais qu'il n'a pas encore été testé sur un robot physique. Les auteurs prévoient de sortir ce cerveau à « règle extensible » de l'ordinateur pour l'amener dans le monde réel lors de travaux futurs.

Ce qu'il faut retenir

UDAQ est un pas vers des robots qui sont moins des machines rigides suivant une liste de contrôle et plus des explorateurs adaptables. En unifiant la planification de trajectoire et l'exploration dans un système unique et auto-ajustable, il permet aux robots de naviguer dans l'inconnu avec un niveau d'efficacité et de fluidité que les robots traditionnels à systèmes divisés peinent à égaler. C'est un rappel que, parfois, la meilleure façon de résoudre un problème complexe n'est pas de construire plus d'outils, mais de construire une manière plus intelligente d'utiliser celui que l'on possède déjà.

Résumé Technique : UDAQ – Q-itération Unifiée, Dynamique et Adaptative pour la Planification de Trajectoire et l'Exploration en Environnement Inconnu

Énoncé du Problème
La navigation autonome dans des environnements inconnus présente un double défi : le robot doit simultanément effectuer une planification de trajectoire point à point efficace et une exploration complète de l'environnement sans connaissance préalable de la carte. Les architectures traditionnelles découpent généralement ces tâches, séparant l'exploration (déterminer où aller) de la planification de trajectoire (déterminer comment y aller). Cette séparation conduit souvent à des comportements sous-optimaux, car la couche d'exploration sélectionne des objectifs sans tenir compte de la complexité du chemin ou de l'incertitude de la carte, tandis que la couche de planification opère sur des instantanés de carte potentiellement obsolètes. De plus, l'application de la valeur itérative classique ou de la programmation dynamique à des environnements inconnus est complexe car l'espace d'états navigable s'étend dynamiquement à mesure que de nouvelles régions sont découvertes. Des magnitudes de récompense fixes et des représentations d'espace d'états statiques échouent souvent à maintenir une propagation de valeur stable dans de tels environnements évolutifs, entraînant une convergence médiocre et une dégradation de la performance de la politique.

Méthodologie
L'article propose UDAQ (Unified Dynamic and Adaptive Q-iteration), un cadre qui unifie la planification de trajectoire locale, l'exploration complète de l'environnement et l'exploration orientée au sein d'une formulation unique de processus de décision de Markov (MDP) pilotée par les récompenses.

Formulation MDP Unifiée : Le problème est modélisé comme un MDP $(S, A, P, R, \gamma, \pi)$ où l'espace d'états $S$ est dérivé d'une grille d'occupation générée par SLAM, segmentée en tuiles carrées. Les états sont classés comme libres, occupés, frontières (limite entre connu et inconnu), objectifs ou inconnus. L'espace d'actions consiste en huit mouvements discrets (cardinaux et inter-cardinaux).
Fonctions de Récompense Configurables : UDAQ utilise un cadre unique d'itération de valeur où différents comportements sont induits par la reconfiguration de la fonction de récompense $R(s, a, s')$ $R (s, a, s^{'})$ :
1. Planification Point à Point : Récompense les transitions vers un objectif spécifique, pondérées par la proximité euclidienne, tout en pénalisant les obstacles et les étapes inutiles.
2. Exploration de l'Environnement : Supprime les récompenses spécifiques à l'objectif, attribuant des récompenses uniformes élevées aux états de frontière pour encourager une couverture systématique.
3. Exploration Orientée : Introduit un « objectif imaginaire » en dehors des limites de l'environnement pour biaiser l'exploration dans une direction spécifique.
Espace d'États Dynamique et Mise à l'Échelle de Récompense Adaptative : Une innovation technique centrale est la gestion de l'évolution dynamique de l'espace d'états. À mesure que la carte SLAM s'étend, UDAQ emploie un mécanisme de mise à l'échelle de récompense adaptatif. Il estime le diamètre géodésique ( $L$ ) de l'espace d'états traversable actuel en utilisant un squelette d'axe médian et une transformée de distance de Chebyshev. Les magnitudes de récompense (pénalités de pas, pénalités d'obstacles et récompenses d'objectif/frontière) sont ensuite automatiquement mises à l'échelle par rapport à $L$ et au facteur de remise $\gamma$ . Cela garantit que la propagation de la fonction de valeur reste stable et significative quel que soit la taille ou la complexité structurelle de l'environnement, empêchant la dégradation de la politique à mesure que la carte croît.
Fonctionnement en Boucle Fermée : Le système fonctionne comme un processus complet en boucle fermée. Il intègre continuellement les mises à jour SLAM, met à jour les classifications d'états, recalcule les récompenses basées sur le diamètre actuel de la carte, effectue la Q-itération jusqu'à convergence et génère des commandes de navigation sans intervention humaine.

Contributions Clés

Cadre Unifié : Démontre que divers comportements autonomes (navigation, exploration, exploration orientée) peuvent être accomplis au sein d'une formulation unique via la configuration des récompenses, éliminant ainsi le besoin de planificateurs distincts ou d'heuristiques spécifiques à la tâche.
Adaptation de l'Espace d'États Dynamique : Introduit une méthode permettant à l'itération de valeur d'opérer sur un espace d'états en expansion en ajustant dynamiquement les magnitudes de récompense en fonction du diamètre géodésique estimé de la zone traversable.
Mise à l'Échelle de Récompense Adaptative : Propose une stratégie de réglage automatique qui assure des mises à jour de Bellman stables et une qualité de politique cohérente à mesure que l'environnement est progressivement révélé, répondant au problème des récompenses fixes devenant inefficaces dans des cartes plus vastes et évolutives.

Résultats Expérimentaux
La méthode a été évaluée dans des simulations ROS 2 à travers trois environnements de complexité croissante (Simple, Modéré, Complexe) et comparée au planificateur ROS 2 NavFn (pour la navigation) ainsi qu'aux stratégies basées sur les frontières, le suivi de mur et la marche aléatoire (pour l'exploration).

Navigation Point à Point : UDAQ surpasse systématiquement le planificateur NavFn. Il a réduit la distance de voyage moyenne d'environ 8 à 12 % et la durée de voyage de 20 à 30 % sur l'ensemble des cas de test, approchant des solutions globalement optimales malgré l'absence de connaissance préalable de la carte. Il a également démontré une capacité robuste de replanification dynamique lors de l'introduction de nouveaux obstacles.
Exploration de l'Environnement : UDAQ surpasse significativement toutes les méthodes de référence. Comparé à l'exploration basée sur les frontières (la base de référence classique la plus forte), UDAQ a réduit la distance de voyage de 36 à 44 % et le temps d'exploration de 48 à 59 % dans tous les environnements. Il a également largement dépassé les performances des stratégies de suivi de mur et de marche aléatoire. Dans les environnements complexes, UDAQ maintient des trajectoires fluides et une terminaison autonome, là où les autres méthodes souffrent souvent de traversées inefficaces ou d'un échec de couverture totale de la carte.
Exploration Orientée : Les expériences avec huit configurations directionnelles ont montré que le biais directionnel influence considérablement l'efficacité de l'exploration. Les configurations alignées avec la topologie de l'environnement (par exemple, le Sud dans la carte testée) minimisent les traversées redondantes et réduisent le temps d'achèvement, tandis que les configurations mal alignées augmentent la redondance des chemins.

Signification et Revendications
L'article affirme que UDAQ fournit une solution robuste, efficace et flexible pour la navigation autonome dans des environnements inconnus. Sa principale signification réside dans l'unification de multiples comportements de navigation au sein d'un cadre unique piloté par les récompenses, permettant au comportement d'émerger de la configuration des récompenses plutôt que du changement de planificateur. En opérant comme un système complet en boucle fermée qui s'adapte aux espaces d'états évoluant dynamiquement, UDAQ répond aux limitations structurelles des architectures de découpage entre exploration et planification.

Les auteurs reconnaissent que les résultats sont basés sur des simulations ROS 2 supposant une perception et une estimation d'état idéalisées. Par conséquent, bien que le cadre démontre son efficacité dans des conditions contrôlées, l'article précise que des travaux futurs sont nécessaires pour valider la robustesse sur des plateformes robotiques physiques soumises aux incertitudes du monde réel telles que le bruit des capteurs, les imprécisions des actionneurs et la dérive de localisation.