💻 computer science

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

Este artigo apresenta o UDAQ, um framework de iteração Q unificado e orientado por recompensa que se adapta autonomamente a espaços de estados em evolução dinâmica para otimizar simultaneamente o planejamento de trajetória ponto a ponto e a exploração eficiente do ambiente, superando significativamente planejadores e estratégias de exploração convencionais em ambientes desconhecidos sem conhecimento prévio do mapa.

Autores originais: Nasr Abdalmanan, Kamarulzaman Kamarudin, Muqri Zinal, Mohd Rizal Manan, Victor Bennetts

Publicado 2026-07-30

📖 8 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Nasr Abdalmanan, Kamarulzaman Kamarudin, Muqri Zinal, Mohd Rizal Manan, Victor Bennetts

Artigo original sob licença CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine um robô deixado em um labirinto totalmente escuro que ele nunca viu antes. Suas únicas ferramentas são um par de "olhos" (sensores) que conseguem enxergar alguns passos à frente e um cérebro que precisa descobrir duas coisas ao mesmo tempo: "Como eu chego àquele ponto específico logo ali?" e "Como eu mapeio todo o quarto escuro para não me perder?". Este é o cotidiano de um robô autônomo, um campo da ciência chamado robótica móvel. Para um robô sobreviver no mundo real, ele precisa de planejamento de trajetória (desenhar uma linha segura do ponto A ao ponto B) e exploração (verificar sistematicamente áreas desconhecidas para construir um mapa mental). Tradicionalmente, os engenheiros tratam essas tarefas como dois trabalhos separados, contratando um "programa" para decidir para onde ir e outro "programa" para descobrir como chegar lá. Mas em um mundo que muda conforme você o observa, manter esses trabalhos separados pode gerar confusão, como um motorista que pede direções a um passageiro enquanto o passageiro ainda está tentando ler o mapa.

Apresentamos o UDAQ (Unified Dynamic and Adaptive Q-iteration), um novo framework proposto pelos pesquisadores Nasr Abdalmanan e sua equipe da Universiti Malaysia Perlis e da Örebro University. Pense no UDAQ não como um robô com dois cérebros separados, mas como um navegador único e superadaptável que aprende a fazer tudo através de um jogo de "quente ou frio". Em vez de alternar entre diferentes modos, o UDAQ usa um único conjunto de regras (um sistema de recompensa) para ensinar o robô a se comportar. Se o robô precisa encontrar uma porta específica, o "jogo" o recompensa por chegar mais perto dessa porta. Se o robô precisa mapear um prédio inteiro, o "jogo" o recompensa por encontrar cantos novos e inexplorados. O truque de mágica é que este sistema ajusta automaticamente suas próprias configurações de dificuldade à medida que o robô descobre mais do mundo. Se o labirinto ficar maior, o UDAQ aumenta as recompensas para que o robô não fique desanimado ou confuso. Em uma série de simulações de computador, esta abordagem provou ser uma maneira mais rápida, suave e eficiente para robôs navegarem em espaços desconhecidos em comparação com os métodos padrão usados atualmente na indústria.

O Problema: A "Personalidade Dividida" do Robô

Imagine que você está tentando explorar uma caverna gigante e escura. Você tem uma lanterna que ilumina apenas um pequeno círculo ao seu redor. Para chegar à saída, você precisa conhecer o caminho. Para construir um mapa, você precisa vagar pela escuridão. A navegação de robôs do estilo antigo costuma dividir essas tarefas em duas equipes separadas. Uma equipe, o Explorador, diz: "Vá encontrar a borda do mundo conhecido!". A outra equipe, o Planejador, diz: "Ok, agora desenhe uma linha até essa borda".

O problema é que essas duas equipes não se comunicam bem. O Explorador pode escolher um alvo que parece próximo, mas que na verdade está atrás de uma parede, e o Planejador tem que perder tempo calculando um desvio. Ou, o mapa pode mudar enquanto o Planejador está trabalhando, tornando o plano antigo inútil. É como tentar dirigir um carro onde o GPS e o volante são controlados por duas pessoas diferentes que estão discutindo sobre o destino.

A Solução: Um Cérebro, Muitos Humores

Os pesquisadores por trás do UDAQ decidiram parar de dividir a equipe. Eles construíram um sistema onde o robô tem um único cérebro que lida tanto com a exploração quanto com o planejamento, mas ele muda seu "humor" dependendo do que você quer que ele faça. Eles chamam isso de um framework de Unified Dynamic and Adaptive Q-iteration.

Veja como funciona, usando uma analogia simples:

O Jogo de "Quente ou Frio"
Imagine que o robô está jogando um videogame onde ele ganha pontos (recompensas) por se mover.

Humor 1: O Caçador de Objetivos. Se você disser ao robô: "Vá até a porta vermelha", o jogo dá a ele uma enorme pilha de pontos por chegar mais perto da porta. Também dá pequenas penalidades por andar em círculos. O robô aprende a correr em direção à porta, mas se bater em uma parede, ele recalcula instantaneamente o melhor caminho ao redor dela.
Humor 2: O Criador de Mapas. Se você disser ao robô: "Explore tudo", o jogo muda. Agora, o robô ganha os maiores pontos por encontrar fronteiras — as bordas nebulosas onde o mapa conhecido encontra a escuridão desconhecida. Ele ignora a porta vermelha e, em vez disso, corre para o canto inexplorado mais próximo.
Humor 3: O Explorador Direcional. Você pode até dizer ao robô: "Explore, mas vá principalmente para o Norte". O robô ainda buscará novas áreas, mas priorizará aquelas que estão ao Norte, criando um padrão específico de exploração.

A genialidade do UDAQ é que ele não precisa trocar de software para mudar de humor. Ele apenas muda as regras do jogo (a configuração de recompensa) mantendo o mesmo cérebro funcionando.

O Ingrediente Secreto: A Recompensa "Elástica"

Existe um problema complicado nesses jogos. Se o robô estiver em uma sala minúscula, uma recompensa de "10 pontos" pode parecer enorme. Mas se o robô subitamente descobrir um salão imenso, esses mesmos "10 pontos" podem parecer pequenos demais para motivar o robô a atravessar todo o salão. O robô pode ficar confuso e parar de tentar, ou pode tomar decisões ruins porque a matemática não faz mais sentido.

O UDAQ resolve isso com um mecanismo Dinâmico e Adaptável. Pense nisso como uma régua elástica.

O robô mede constantemente o tamanho do espaço que descobriu até o momento. Ele calcula o caminho mais longo possível que poderia percorrer através do mapa conhecido (o "diâmetro geodésico").
Com base nesse tamanho, ele reescala as recompensas automaticamente. Se a sala for enorme, os pontos valem mais. Se a sala for pequena, os pontos valem menos.
Isso garante que o robô sempre sinta os sinais de "quente ou frio" corretamente, não importa o quão grande o labirinto se torne. Isso evita que o robô fique "travado" ou tome decisões ruins apenas porque o ambiente mudou.

O Que as Simulações Mostraram

Os pesquisadores testaram o UDAQ em três mundos virtuais diferentes, variando de um simples armazém aberto a um edifício complexo com corredores estreitos e muitas salas. Eles o compararam com os métodos padrão usados na indústria (como o planejador ROS 2 NavFn) e outras estratégias de exploração (como "seguir a parede" ou "caminhada aleatória").

1. Ir de A para B (Planejamento de Trajetória)
Quando o robô precisava ir de um ponto de partida a um ponto de destino em um ambiente desconhecido:

O UDAQ encontrou caminhos que foram de 8 a 12% mais curtos do que o planejador padrão.
Ele terminou a viagem de 20 a 30% mais rápido.
Mesmo sem conhecer o mapa previamente, os caminhos do UDAQ foram quase tão bons quanto o caminho "perfeito" que um humano poderia desenhar se soubesse todo o mapa desde o início.

2. Explorar Todo o Quarto (Exploração)
Quando o robô tinha que mapear todo o ambiente:

O UDAQ foi o vencedor claro. Ele percorreu uma distância 36 a 44% menor do que o método tradicional baseado em "fronteiras" (que é a abordagem tradicional mais avançada atualmente).
Ele terminou a exploração de 48 a 59% mais rápido.
No mapa mais complexo (Mapa C), o método de "caminhada aleatória" padrão ficou preso em um corredor estreito e falhou em concluir a tarefa, enquanto o UDAQ navegou suavemente e completou a missão.

3. O Teste "Direcional"
Em um experimento, os pesquisadores disseram ao robô para explorar o edifício complexo, mas com um viés para uma direção específica (como "principalmente para o Sul").

Quando a direção coincidia com o layout do edifício (como o Sul), o robô foi incrivelmente eficiente, pegando o caminho mais curto.
Quando a direção estava "errada" (como o Oeste), o robô fez uma rota mais longa e sinuosa.
Isso provou que o UDAQ pode ser "guiado" para explorar em uma ordem específica, o que pode ser útil se você sabe que certas salas são mais importantes que outras.

A Ressalva: Ainda é uma Simulação

Embora os resultados sejam impressionantes, os pesquisadores ressaltam cuidadosamente que todos esses testes foram feitos em simulações de computador. Os robôs viveram em um mundo digital perfeito onde os sensores nunca falharam, as rodas nunca derraparam e os mapas estavam sempre precisos. No mundo real, os robôs enfrentam problemas caóticos, como iluminação ruim, pisos escorregadios e sensores ruidosos. O artigo sugere que o UDAQ é um forte candidato para uso no mundo real, mas ainda não foi testado em um robô físico. Os autores planejam levar este céreção "elástico" do computador para o mundo real em trabalhos futuros.

A Conclusão

O UDAQ é um passo em direção a robôs que são menos como máquinas rígidas seguindo uma lista de verificação e mais como exploradores adaptáveis. Ao unificar o planejamento de trajetória e a exploração em um único sistema autoajustável, ele permite que os robôs naveguem pelo desconhecido com um nível de eficiência e suavidade que os robôs de sistemas divididos tradicionais têm dificuldade em igualar. É um lembrete de que, às vezes, a melhor maneira de resolver um problema complexo não é construir mais ferramentas, mas construir uma maneira mais inteligente de usar a que você já tem.

Resumo Técnico: UDAQ – Iteração Q Dinâmica e Adaptativa Unificada para Planejamento de Trajetória e Exploração em Ambientes Desconhecidos

Definição do Problema
A navegação autônoma em ambientes desconhecidos apresenta um desafio duplo: o robô deve realizar simultaneamente o planejamento de trajetória ponto a ponto eficiente e a exploração confiável de todo o ambiente sem conhecimento prévio do mapa. Arquiteturas tradicionais tipicamente desacoplam essas tarefas, separando a exploração (determinar para onde ir) do planejamento de trajetória (determinar como chegar lá). Essa separação frequentemente leva a comportamentos subótimos, pois a camada de exploração seleciona objetivos sem considerar a complexidade do caminho ou a incerteza do mapa, enquanto a camada de planejamento opera sobre instantâneos de mapa potencialmente desatualizados. Além disso, aplicar a iteração de valor clássica ou programação dinâmica em ambientes desconhecidos é desafiador porque o espaço de estados navegáveis se expande dinamicamente à medida que novas regiões são descobertas. Magnitudes de recompensa fixas e representações de espaço de estados estáticas costem falhar em manter a propagação estável de valor em tais ambientes em evolução, levando a uma convergência pobre e à degradação do desempenho da política.

Metodologia
O artigo propõe o UDAQ (Iteração Q Dinâmica e Adaptativa Unificada), um framework que unifica o planejamento de trajetória local, a exploração completa do ambiente e a exploração orientada dentro de uma formulação de Processo de Decisão de Markov (MDP) única, baseada em recompensas.

Formulação de MDP Unificada: O problema é modelado como um MDP $(S, A, P, R, \gamma, \pi)$ onde o espaço de estados $S$ é derivado de uma grade de ocupação gerada por SLAM, segmentada em blocos quadrados. Os estados são classificados como livre, ocupado, fronteira (limite entre conhecido/desconhecido), objetivo ou desconhecido. O espaço de ações consiste em oito movimentos discretos (cardinais e intercardinais).
Funções de Recompensa Configuráveis: O UDAQ emprega um framework de iteração de valor único onde diferentes comportamentos são induzidos pela reconfiguração da função de recompensa $R(s, a, s')$ $R (s, a, s^{'})$ :
1. Planejamento Ponto a Ponto: Recompensa transições em direção a um objetivo específico, escaladas pela proximidade euclidiana, enquanto penaliza obstáculos e passos desnecessários.
2. Exploração de Ambiente: Remove recompensas específicas de objetivos, atribuindo altas recompensas uniformes aos estados de fronteira para incentivar a cobertura sistemática.
3. Exploração Orientada: Introduz um "objetivo imaginário" fora do limite do ambiente para enviesar a exploração em uma direção específica.
Espaço de Estados Dinâmico e Escalonamento de Recompensa Adaptativo: Uma inovação técnica central é o tratamento do espaço de estados em evolução dinâmica. À medida que o mapa SLAM se expande, o UDAQ emprega um mecanismo de escalonamento de recompensa adaptativo. Ele estima o diâmetro geodésico ( $L$ ) do atual espaço de estados transitável usando um esqueleto de eixo medial e uma transformada de distância de Chebyshev. As magnitudes das recompensas (penalidades de passo, penalidades de obstáculo e recompensas de objetivo/fronteira) são então automaticamente escalonadas em relação a $L$ e ao fator de desconto $\gamma$ . Isso garante que a propagação da função de valor permaneça estável e significativa, independentemente do tamanho do ambiente ou da complexidade estrutural, evitando a degradação da política conforme o mapa cresce.
Operação de Malha Fechada: O sistema opera como um processo de malha fechada totalmente autônomo. Ele integra continuamente atualizações de SLAM, atualiza classificações de estados, recalcula recompensas com base no diâmetro atual do mapa, realiza a iteração Q até a convergência e gera comandos de navegação sem intervenção humana.

Principais Contribuições

Framework Unificado: Demonstra que diversos comportamentos autônomos (navegação, exploração, exploração orientada) podem ser alcançados dentro de uma formulação única através da configuração de recompensa, eliminando a necessidade de planejadores separados ou heurísticas específicas de tarefa.
Adaptação de Espaço de Estados Dinâmico: Introduz um método para a iteração de valor operar em um espaço de estados em expansão, ajustando dinamicamente as magnitudes de recompensa com base no diâmetro geodésico estimado da área transitável.
Escalonamento de Recompensa Adaptativo: Propõe uma estratégia de ajuste automático que garante backups de Bellman estáveis e qualidade de política consistente conforme o ambiente é progressivamente revelado, abordando o problema de recompensas fixas tornando-se ineficazes em mapas maiores e em evolução.

Resultados Experimentais
O método foi avaliado em simulações ROS 2 em três ambientes de complexidade crescente (Simples, Moderado, Complexo) e comparado contra o planejador ROS 2 NavFn (para navegação) e estratégias baseadas em fronteira, seguimento de parede e caminhada aleatória (para exploração).

Navegação Ponto a Ponto: O UDAQ superou consistentemente o planejador NavFn. Reduziu a distância média de viagem em aproximadamente 8–12% e a duração da viagem em 20–30% em todos os casos de teste, aproximando-se de soluções globalmente ótimas apesar da falta de conhecimento prévio do mapa. Também demonstrou replanejamento dinâmico robusto quando novos obstáculos foram introduzidos.
Exploração de Ambiente: O UDAQ superou significativamente todos os métodos de base. Comparado à exploração baseada em fronteira (a base clássica mais forte), o UDAQ reduziu a distância de viagem em 36–44% e o tempo de exploração em 48–59% em todos os ambientes. Também excedeu substancialmente o desempenho das estratégias de seguimento de parede e caminhada aleatória. Em ambientes complexos, o UDAQ manteve trajetórias suaves e terminação autônoma, enquanto outros métodos frequentemente sofriam com travessia ineficiente ou falha em cobrir totalmente o mapa.
Exploração Orientada: Experimentos com oito configurações direcionais mostraram que o viés direcional influencia significamente a eficiência da exploração. Configurações alinhadas com a topologia do ambiente (ex: Sul no mapa testado) minimizaram a redundância de travessia e reduziram o tempo de conclusão, enquanto configurações desalinhadas aumentaram a redundância do caminho.

Significância e Alegações
O artigo afirma que o UDAQ fornece uma solução robusta, eficiente e flexível para a navegação autônoma em ambientes desconhecidos. Sua principal significância reside na unificação de múltiplos comportamentos de navegação dentro de um único framework baseado em recompensas, permitindo que o comportamento emerja da configuração de recompensa em vez da troca de planejadores. Ao operar como um sistema de malha fechada totalmente autônomo que se adapta a espaços de estados que evoluem dinamicamente, o UDAQ aborda as limitações estruturais das arquiteturas de exploração e planejamento desacopladas.

Os autores reconhecem que os resultados baseiam-se em simulações ROS 2 assumindo percepção idealizada e estimativa de estado. Consequentemente, embora o framework demonstre eficácia sob condições controladas, o artigo afirma que trabalhos futuros são necessários para validar a robustez em plataformas robóticas físicas sob incertezas do mundo real, como ruído de sensores, imprecisões de atuadores e deriva de localização.