Resumo Técnico: Replanejamento Reativo Usando uma Estratégia Baseada no Estado do Alvo para Sistemas Multi-Robô Heterogêneos sob Restrições de LTL de Contagem

1. Definição do Problema

Em sistemas multi-robô heterogêneos (HMRS) dinâmicos, planos estáticos frequentemente tornam-se obsoletos devido a mudanças inesperadas nos atributos dos alvos durante a execução. Especificamente, os alvos podem sofrer deslocamentos de posição (mudanças nas coordenadas espaciais) ou atualizações de prioridade (mudanças nos níveis de urgência). Abordagens existentes tipicamente tratam essas variações como fatores independentes ou desacoplam o replanejamento da alocação de tarefas e da arbitragem de prioridade. Além disso, o planejamento padrão de Lógica Temporal Linear (LTL) tem dificuldade com restrições quantitativas de recursos exigidas para equipes heterogêneas (ex: "pelo menos $N$ robôs do tipo $j$ devem estar na região $S$").

O desafio central abordado é como incorporar conjuntamente tanto deslocamentos de posição quanto atualizações de prioridade em um framework de Programação Linear Inteira Mista (MILP) unificado para equipes heterogêneas, mantendo a viabilidade de execução online. O sistema deve satisfazer restrições de LTL de contagem (cLTL), que impõem tanto a lógica temporal quanto limites quantitativos de recursos específicos por tipo, sem violar as restrições da missão quando os alvos mudam dinamicamente.

2. Metodologia: Framework TRRS

Os autores propõem o TRRS (Target-state-driven Reactive Replanning Strategy), um framework projetado para replanejar trajetórias de forma reativa em resposta a variações no estado do alvo. A metodologia consiste em três componentes integrados:

2.1 Codificação MILP Unificada

O problema de planejamento colaborativo é formulado como um MILP que otimiza conjuntamente a alocação de tarefas e a geração de trajetórias.

• Modelo do Sistema: O espaço de trabalho é um grafo de grade discreta $G=(V, E)$. A equipe de robôs consiste em tipos heterogêneos $j \in [m]$, onde cada tipo $j$ possui um conjunto de robôs $K_j$. Os alvos $P(t)$ são variantes no tempo, possuindo coordenadas espaciais $\hat{p}_k(t)$ e níveis de prioridade $pri_k(t)$.
• Restrições:
  • Cinemática e Colisão: Os robôs movem-se entre vértices adjacentes ou permanecem estacionários. A exclusão mútua de vértices garante que dois robôs não ocupem a mesma célula simultaneamente.
  • Especificação cLTL: A missão é especificada usando cLTL, que estende a LTL padrão com predicados de contagem (ex: $tp(S, N^j)$). Esses predicados são linearizados usando técnicas de reformulação big-M para impor restrições como "pelo menos $N$ robôs do tipo $j$ na região $S$".
  • Objetivo: Minimizar o custo total de viagem (distância de grade euclidiana) sujeito às restrições cinemáticas, de colisão e de cLTL.

2.2 Mecanismo de Gatilho Sensível ao Estado

O TRRS emprega um mecanismo de gatilho diferenciado que distingue dois tipos de mudanças de alvo, aplicando regras de preempção específicas:

• Deslocamentos de Posição ($E_{pos}$): Se a localização de um alvo muda, a trajetória existente torna-se fisicamente obsoleta. O sistema aciona uma preempção imediata, abortando a tarefa atual e reatribuindo o robô ao novo alvo imediatamente.
• Atualizações de Prioridade ($E_{pri}$): Se apenas a prioridade muda, o sistema não necessariamente aborta as tarefas atuais. Em vez disso, ele reordena a fila de tarefas. Os robôs são instruídos a concluir sua tarefa atual antes de mudar para um novo alvo de maior prioridade, a menos que a mudança de prioridade ocorra em conjunto com um deslocamento de posição.
• Eventos Acoplados: Se ambos ocorrerem, uma atualização completa é realizada com preempção imediata.

2.3 Controle de Horizonte Recedente

Para garantir que o MILP permaneça tratável para execução online, o TRRS utiliza uma abordagem de horizonte recedente (janela deslizante):

• O horizonte global $T$ é dividido em janelas curtas de comprimento fixo $h$ (definido como $h=7$ nos experimentos).
• A cada rodada, o MILP é resolvido apenas para a janela atual. O estado terminal da janela atual serve como a condição inicial para a próxima.
• O replanejamento é acionado pelo detecção de variações de alvo (via mecanismo de gatilho) ou pela expiração da janela de tempo atual.

3. Principais Contribuições

1. Framework cLTL Unificado para Equipes Heterogêneas: O artigo constrói uma formulação MILP que captura tanto as variações de posição quanto de prioridade dos alvos dentro de um único framework de restrições, superando o tratamento desacoplado comum em planejamentos baseados em LTL anteriores.
2. Lógica de Preempção Diferenciada: Ao contrário de métodos existentes que tratam todas as mudanças de forma idêntica, o TRRS distingue entre deslocamentos de posição e atualizações de prioridade. Ele aplica preempção imediata para mudanças espaciais, mas permite a conclusão de tarefas para mudanças apenas de prioridade, reduzindo efetivamente a recomputação online desnecessária e o abandono de tarefas.
3. Tratabilidade Online via Horizonte Recedente: Ao adotar uma janela deslizante curta, o framework garante que as soluções MILP sejam retornadas dentro de tempos de computação limitados, adequados para implantação em tempo real.
4. Validação: A abordagem é validada através de simulações de Monte Carlo e experimentos com robôs físicos, demonstrando desempenho superior em relação às linhas de base estáticas e gananciosas (greedy).

4. Resultados Experimentais

Os autores avaliaram o TRRS em dois cenários: um ambiente de espaço aberto e um ambiente de corredor estreito, comparando-o com o S-MILP (MILP Estático) e o ET-Greedy (Reatribuição Gananciosa Baseada em Eventos).

• Desempenho de Simulação (30 execuções de Monte Carlo por cenário):
  • Taxa de Sucesso: O S-MILP falhou completamente (0,0% de sucesso) em ambos os cenários devido à sua incapacidade de se adaptar às mudanças. O ET-Greedy alcançou 99,3% de sucesso no espaço aberto, mas caiu para 29,3% em corredores estreitos devido a congestionamentos e impasses (deadlocks). O TRRS alcançou 100% de sucesso em ambos os cenários.
  • Conclusão de Tarefas: O TRRS manteve 100% de conclusão em ambos os ambientes. O ET-Greedy alcançou 99,8% no espaço aberto, mas apenas 50,9% em corredores estreitos.
  • Eficiência: No espaço aberto, o TRRS reduziu os passos médios de execução de 101,6 (ET-Greedy) para 94,6. Em corredores estreitos, o TRRS exigiu 59,4 passos, comparado às execuções truncadas ou falhas das linhas de base.
• Sobrecarga Computacional: O tempo médio para resolver o MILP para uma rodada de replanejamento acionado foi de 0,111 segundos. Com aproximadamente 9,8 rodadas de replanejamento por missão, o tempo de solução cumulativo foi de ~1,09 segundos, confirmando a adequação para execução online.
• Validação Física: Um experimento físico com dois robôs de tração diferencial validou a estratégia. Quando um alvo (um livro) foi movido manualmente e uma nova tarefa de alta prioridade (entrega de água) foi introduzida, o sistema reordenou as tarefas com sucesso, suspendeu a coleta de baixa prioridade, executou a entrega de alta prioridade e, em seguida, retomou a tarefa de coleta.

5. Significância e Alegações

O artigo afirma que o TRRS aborda uma lacuna crítica na coordenação multi-robô dinâmica: o tratamento conjunto de variações de posição e prioridade sob restrições formais de cLTL. Os autores asseguram que seu mecanismo de gatilho diferenciado equilibra efetivamente a responsividade com a eficiência computacional, evitando a "reação exagerada" de tratar todas as mudanças como preempções imediatas.

A significância do trabalho reside em sua capacidade de manter a satisfação da missão (restrições cLTL) e altas taxas de conclusão de tarefas em ambientes dinâmicos e restritos, onde planos estáticos falham e heurísticas gananciosas levam a impasses. Os autores observam que, embora a formulação MILP centralizada atual seja eficaz para os tamanhos de frota testados, ela não escala para frotas muito grandes. Consequentemente, eles identificam a decomposição de MILP distribuído e heurísticas baseadas em aprendizado como passos futuros necessários para escalonamento, juntamente com a extensão da representação de grade para espaços de trabalho contínuos e o tratamento de obstáculos dinâmicos.