A Complete-Coverage Path-Planning Algorithm Based on Local Path Cost

Resumo Técnico: Um Algoritmo de Planejamento de Trajetória de Cobertura Completa Baseado em Custo de Caminho Local (CCPP-LPC)

Definição do Problema
O Planejamento de Trajetória de Cobertura Completa (CCPP) é uma tecnologia crítica para robôs móveis autônomos e veículos de superfície não tripulados (USVs), com a tarefa de gerar trajetórias livres de colisões que atravessem todas as células de grade alcançáveis em um espaço de trabalho. Embora os planejadores existentes baseados em metaheurísticas e inteligência de enxame (ex: Otimização por Colônia de Formigas, Algoritmos Genéticos) tenham avançado o campo, eles frequentemente enfrentam dificuldades em ambientes complexos e de grande escala. As limitações específicas incluem taxas de convergência lentas, uma tendência a ficar preso em ótimos locais devido à falta de orientação direcional na evolução da população e a geração de caminhos com manobras de curva excessivas. Essas ineficiências levam a comprimentos de caminho subótimos, maior consumo de energia e redução da eficiência operacional.

Metodologia
O artigo propõe o algoritmo CCPP-LPC, que se baseia em uma estrutura anterior (CCPP-TPLP), mas introduz um novo mecanismo para guiar o processo de busca evolutiva. A metodologia central envolve três componentes primários:

1. Modelo de Avaliação de Custo de Caminho Local:
   Em vez de depender da estratificação da população baseada no fitness global, o CCPP-LPC constrói um modelo de avaliação local. Para cada nó em uma sequência de caminho, o algoritmo calcula um "custo de caminho local" ($c_k$). Esta métrica representa o custo de distância média do subcaminho de dois saltos formado pelo nó e seus predecessor e sucessor imediatos.

   • Matematicamente, $c_k$ quantifica a contribuição negativa marginal de um nó específico para o comprimento total do caminho.
   • Nós com custos locais mais altos indicam baixa conectividade local e são identificados como tendo alto potencial de otimização.

2. Estratégia de Seleção de Nó de Perturbação de Dupla Orientação Adaptativa:
   Para superar a cegueira dos operadores de mutação tradicionais, o algoritmo deriva duas distribuições de probabilidade distintas dos custos de caminho local para selecionar os nós de perturbação:

   • Distribuição Orientada à Otimização: Esta distribuição atribui probabilidades de seleção mais altas a nós com altos custos locais (especificamente, os pesos são calculados como $(c_k - 1 + \epsilon)^\beta$). Isso direciona os operadores evolutivos para priorizar o refinamento de segmentos que inflam significativamente o comprimento total do caminho.
   • Distribuição Orientada à Diversidade: Esta distribuição atribui probabilidades de exploração de base a todos os nós (pesos calculados como $c_k^\beta$). Ao não subtrair o valor base de 1, ela garante que mesmo os nós com baixos custos locais mantenham uma chance não negligenciável de seleção, preservando assim a diversidade da população e evitando a convergência prematura.
   • O algoritmo utiliza a seleção por roleta baseada nessas distribuições para escolher dois nós de perturbação ($I$ e $J$) para cada indivíduo.

3. Atualização de Indivíduo e Seleção Elitista:
   Uma vez que os nós $I$ e $J$ são selecionados, um dos três operadores de variação (Troca, Reversão ou Inserção) é aplicado estocasticamente para gerar descendentes. O algoritmo emprega uma estratégia de seleção elitista, fundindo as populações de pais e descendentes e retendo os $N$ melhores indivíduos com base no fitness. Isso elimina a necessidade de definir manualmente as razões de divisão hierárquica da população, simplificando o ajuste de parâmetros.

Principais Contribuições
O artigo identifica duas contribuições principais:

1. Construção de um Modelo de Avaliação de Custo de Caminho Local: Este modelo quantifica adaptativamente a urgência de otimização de cada ponto de passagem medindo o custo de seu subcaminho de dois saltos. Isso permite a identificação precisa de segmentos de "baixa qualidade" sem a necessidade de estratificação de população ou configurações manuais de parâmetros relativos à divisão hierárquica.
2. Design de uma Estratégia de Perturbação de Dupla Orientação Adaptativa: Ao combinar distribuições de probabilidade orientadas à otimização e orientadas à diversidade, o algoritmo alcança um equilíbrio entre o refinamento local (visando segmentos de alto custo) e a busca global (mantendo a diversidade genética). Isso fornece uma direcionalidade explícita ao processo evolutivo, abordando a aleatoriedade inerente aos operadores de mutação anteriores.

Resultos Experimentais
O desempenho do CCPP-LPC foi avaliado contra cinco algoritmos de estado da arte (ACO, ALNS, CCPP-TPLP, DTSA, DJAYA) em quatro mapas de grade simulados de diferentes escalas e complexidades, bem como em três cenários de aplicação física do mundo real (Lago Yuhua, Lago Wisdom/Rio Qiulian e um ambiente de operação de trator).

• Desempenho de Simulação: O CCPP-LPC superou consistentemente os algoritmos de comparação em todas as métricas: comprimento total do caminho, número de curvas, razão de cobertura repetida e eficiência computacional. A lacuna de desempenho aumentou conforme a complexidade do ambiente crescia. Notavelmente, o CCPP-LPC demonstrou os menores desvios padrão no comprimento do caminho e na razão de cobertura repetida, indicando uma estabilidade de solução superior.
• Validação no Mundo Real: Em cenários práticos, incluindo ambientes de lagos irregulares e um ambiente de trator 2.5-D com restrições de elevação, o CCPP-LPC alcançou comprimentos de caminho mais curtos, menos curvas e menores razões de cobertura repetida em comparação com os métodos existentes. No cenário do trator, também alcançou um valor de fitness mais alto (indicando menor consumo de energia).
• Estudos de Ablação: A análise de sensibilidade sobre o parâmetro $\beta$ determinou que um valor de 0,5 oferecia o melhor equilíbrio para o tempo de computação, enquanto a estratégia de atualização de população proposta foi verificada como superior tanto ao ACO quanto à estrutura CCPP-TPLP anterior.

Significância e Alegações
O artigo afirma que o CCPP-LPC oferece uma abordagem praticamente valiosa para a otimização de cobertura completa em ambientes complexos e com múltiplas restrições. Ao mudar de uma busca cega para uma evolução guiada baseada em custos de caminho local, o algoritmo melhora significativamente a eficiência computacional e a qualidade do caminho. Os autores enfatizam que o método reduz efetivamente o número de curvas e a cobertura redundante, que são críticos para minimizar o consumo de energia e a complexidade de controle de movimento em implantações do mundo real. Embora o trabalho atual se concentre no planejamento de agente único, os autores reconhecem que trabalhos futuros abordarão o planejamento cooperativo de múltiplos agentes para aumentar ainda mais a eficiência do sistema.