ESTE TEXTO AINDA ESTÁ EM CONSTRUÇÃO
O Problema do Caixeiro Viajante (TSP) permanece como um problema proeminente e extensivamente explorado em otimização combinatória. No TSP, o objetivo é determinar a rota mais curta possível para um vendedor que deve visitar um conjunto de cidades e retornar ao início, otimizando para a menor distância total percorrida. Reconhecido como NP-difícil, o TSP não possui um algoritmo eficiente para soluções ótimas; entretanto, por meio de engenharia de algoritmos avançados, agora é possível resolver instâncias relativamente grandes até a otimização.
Ao contrário do TSP, onde os destinos são pontos explícitos, muitos problemas de percurso geométrico requerem áreas de visitação ou um conjunto de áreas, em vez de pontos específicos. Além disso, estes problemas muitas vezes exigem considerações que vão além da mera minimização da distância. Fatores como os custos de mudança de direção, que se acumulam quando se muda a direção da viagem, tornam-se cruciais nestes cenários.
Neste projeto estou me aprofundando em diversos problemas de percurso geométrico, abrangendo cenários com e sem custos de giro. O objectivo é alargar a nossa compreensão e estratégias de solução para além do TSP clássico, acomodando os desafios únicos colocados pelas visitas regionais e factores de custo adicionais.
TSP com custos de turno em gráficos de grade
Ao enfrentar o desafio de cobrir uma região designada, uma estratégia comum é transformar a área num gráfico de grelha e depois aplicar-lhe o quadro do Problema do Caixeiro Viajante (TSP). Embora esta abordagem possa parecer simples, ela ignora um aspecto significativo em muitas aplicações práticas: os custos de produção. Os custos de mudança de direcção são fundamentais em actividades como cortar relva, limpeza, pintura ou vigilância, onde as despesas incorridas na mudança de direcção – devido à necessidade de desacelerar, virar e depois acelerar novamente – são muitas vezes significativamente mais elevadas do que mover-se em linha recta. Um exemplo identificável é o esforço extra envolvido na manobra de um cortador de grama no final de cada fileira enquanto se corta a grama.
Este desafio, inerentemente NP-difícil, foi sublinhado na nossa investigação. A complexidade do seu relaxamento da cobertura do ciclo, uma questão aberta de longa data apontada como Problema 53 no Projeto Problemas Abertos, foi abordada em nosso trabalho apresentado em (Fekete & Krupke, 2019). Aqui, não apenas provamos a dureza NP do problema, mas também desenvolvemos um novo algoritmo de aproximação baseado em programação linear.
Outros avanços em nossa pesquisa foram apresentados em (Fekete & Krupke, 2019), onde refinamos o algoritmo para maior eficiência e o implementamos em C++. Nossos experimentos demonstraram uma lacuna de otimização inferior a 10% para instâncias com dezenas de milhares de vértices. Além disso, nosso modelo de Programação Inteira superou significativamente os anteriores, permitindo a solução ideal de instâncias com até 1.000 vértices. Também estendemos nossa pesquisa à variante do problema que coleta prêmios, enriquecendo ainda mais o escopo do nosso estudo.
Planejamento de caminho de cobertura parcial
Neste projeto, nos concentramos na criação de um otimizador de rondas de cobertura para ambientes com formas poligonais, adaptado para acomodar a dinâmica de movimento específica dos robôs. Um aspecto fundamental da nossa abordagem foi a capacidade de permitir uma cobertura parcial, concentrando-se particularmente em áreas importantes. O estágio inicial envolveu um processo metódico de conversão da área alvo em uma grade ou estrutura de malha ideal. Esta tarefa foi crucial para garantir que as vias de cobertura traçadas fossem eficientes e eficazes.
Com base nas bases estabelecidas na parte anterior, estendemos o algoritmo de aproximação projetado para grades quadradas regulares para se adequar a estruturas de malha arbitrárias. Esta adaptação não foi simples e exigiu uma consideração cuidadosa dos desafios únicos colocados pelas redes não uniformes.
Além disso, incorporamos várias otimizações adicionais para melhorar o desempenho do algoritmo. Essas melhorias tiveram como objetivo refinar os caminhos de cobertura, tornando-os mais práticos e eficientes para aplicações do mundo real.
O resultado deste projeto é uma estrutura abrangente que não apenas otimiza as trajetórias de cobertura em ambientes poligonais, mas também o faz com uma base teórica sólida. Esta estrutura representa um avanço na otimização da cobertura robótica, oferecendo uma solução que é praticamente viável e teoricamente sólida. Ele demonstra nossa capacidade de preencher a lacuna entre algoritmos teóricos complexos e sua implementação prática em cenários dinâmicos do mundo real.
Estamos pensando em usar uma grade mais fina, por exemplo, reduzindo pela metade o tamanho das células. Isso permitiria apenas visitar cada segunda linha e daria mais flexibilidade para obter melhores soluções, ao mesmo tempo em que teria os benefícios de um ambiente de otimização discreto. No entanto, isso pode tornar a otimização significativamente mais difícil.
O problema de corte de grama busca encontrar o percurso mais curto que cobre uma determinada área poligonal usando uma ferramenta circular. Ao contrário dos problemas anteriores, o movimento da ferramenta não é restringido pelo ambiente. Nosso foco principal está no cálculo de soluções ótimas para pequenas instâncias sem qualquer discretização.
Um insight importante é que este problema pode ser visto como uma instância específica do Problema do Caixeiro Viajante Perto o Suficiente (CE-TSP) com um conjunto infinito de discos unitários. Aproveitando os solucionadores CE-TSP existentes, calculamos com sucesso as primeiras soluções ótimas comprováveis ​​para instâncias muito pequenas do problema de corte de grama.
Em nosso projeto em andamento, Solucionadores Exatos com Variantes TSPN), estamos dedicados a desenvolver solucionadores CE-TSP mais eficientes, adaptados a este problema e já fizemos alguns progressos notáveis. Esses avanços nos permitirão calcular soluções ideais para instâncias moderadamente maiores, permitindo-nos estudar mais profundamente a estrutura do problema e desenvolver melhores heurísticas para instâncias maiores.
Como podemos calcular percursos ótimos ou quase ótimos para instâncias maiores do problema de corte de grama?
Podemos usar uma combinação do Puzzle Solver (para uma trajetória inicial) e do Solver baseado em CE-TSP (para ajustar a trajetória via LNS) para calcular soluções de alta qualidade para instâncias de médio porte?
Corte de grama com custos de giro
Assim que tivermos um bom algoritmo para o TSP Close-Enough com custos de giro, podemos aplicá-lo ao problema de corte de grama. O objetivo é encontrar percursos ideais ou quase ótimos para cortar grama com custos de rotação em instâncias pequenas. Isso pode então ser usado para entender mais sobre a estrutura do problema e desenvolver heurísticas para instâncias maiores.
Como podemos calcular percursos ótimos ou quase ótimos para pequenas instâncias do problema de corte de grama com custos de giro?
Fresagem (corte de grama com obstáculos)
Uma outra questão é o cálculo de percursos ótimos para o Problema de Fresamento, onde a ferramenta não pode cruzar com obstáculos. Este problema é significativamente mais difícil de resolver, mas temos algumas ideias sobre como abordá-lo.
Como podemos calcular percursos ótimos ou quase ótimos para pequenas instâncias do Problema de Fresamento? Como primeiros passos, veremos como fazer isso para o problema de corte de grama com obstáculos convexos.
Pesquisa em grandes bairros por problemas geométricos
Large Neighborhood Searches (LNS) são uma técnica poderosa para otimizar muitos problemas combinatórios até quase a otimização. Um componente chave do LNS é a estrutura de vizinhança, que define o conjunto de soluções que podem ser alcançadas a partir de uma determinada solução por uma única operação. Para problemas geométricos, a geometria geralmente oferece muita estrutura que pode ser explorada para definir uma vizinhança eficaz para LNS. Já utilizámos esta abordagem no ESA 2023 e no ALENEX 2024 com grande sucesso. Estou planejando explorar ainda mais essa abordagem no futuro e aplicá-la a outros problemas geométricos.
Podemos explorar a geometria desses problemas para projetar otimizadores poderosos baseados em Large Neighborhood Search? Nossos solucionadores (quase) ideais seriam um elemento-chave para tal técnica.
- Planejamento de caminho de cobertura quase ideal com custos de giro em 2024 Anais do Simpósio de Engenharia e Experimentos de Algoritmos (ALENEX), 2024
- Um corte mais detalhado: computando passeios de corte de grama quase ideaisEm 2023 Anais do Simpósio sobre Engenharia de Algoritmos e Experimentos (ALENEX), 2023
- O problema do corte de grama: da álgebra aos algoritmosIn 31º Simpósio Europeu Anual de Algoritmos (ESA 2023), 2023
- Cobrindo passeios e coberturas de ciclo com custos de giro: dureza e aproximação em algoritmos e complexidade - 11ª Conferência Internacional, CIAC 2019, Roma, Itália, 27 a 29 de maio de 2019, Anais, 2019
- Métodos práticos para calcular grandes passeios de cobertura e coberturas de ciclo com custo de giroIn Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, CA, EUA, 7 a 8 de janeiro de 2019, 2019