Roteamento
Inteligente

Visão Geral

Nossa solução de roteamento de última geração suporta campos arbitrariamente complexos, navegação de cabeceiras e muitas outras opções configuráveis. Nesta página você encontrará exemplos e explicações dos diversos recursos de roteamento, além de protótipos experimentais novos e empolgantes.

Modelagem de Curvas

Suportamos vários tipos de curva, escolhidos automaticamente de acordo com uma combinação da geometria do campo e das características dos equipamentos. Se duas faixas estiverem a menos de 3 larguras de passagem uma da outra, tentaremos conectá-las diretamente com uma curva. Se as faixas estiverem mais afastadas, ou se não couber nenhuma curva, realizaremos o que chamamos de travessia de cabeceira, explicada com mais detalhes abaixo.

Conectores Faixa-Faixa

Para conexões diretas de faixa a faixa, suportamos os seguintes tipos de curva:

Curva em U

Quando o raio de curva é inferior a 50% da largura de passagem, curvas em U como esta serão geradas para faixas adjacentes. Há uma opção para estender o segmento reto até a cabeceira, dando mais espaço para realizar a curva e minimizando o pisoteio.

Curva em U Perfeita

Quando o raio de curva é exatamente 50% da largura de passagem, curvas em U perfeitas como esta serão geradas para faixas adjacentes, sem segmento reto intermediário.

Curva em Bulbo

Quando o raio de curva é superior a 50% da largura de passagem, uma curva em bulbo é usada para conectar duas faixas adjacentes. Este tipo só seria utilizado se uma curva em U não coubesse.

Curva em P

Se a cabeceira estiver em um ângulo agudo em relação à curva e o raio de curva for suficientemente grande, suportamos curvas em P para minimizar a quantidade de direção necessária.

Conectores Faixa-Cabeceira

Quando uma conexão direta não é possível, conectamos a uma cabeceira próxima, realizando uma ou mais travessias de cabeceira para unir duas faixas. Isso nos permite criar caminhos entre quase quaisquer duas faixas do campo inteiro sem cruzar o campo de forma inválida fora de uma zona de cabeceira.

Conectores em Arco

Por padrão, tentamos usar conectores em arco, que têm curvatura constante e raio de curva pelo menos tão grande quanto o raio mínimo de viragem. Isso permite uma transição suave da faixa para a cabeceira sem movimentos bruscos. A curva pode ser encurtada automaticamente se não houver espaço suficiente para completá-la sem que o veículo ultrapasse o limite do campo.

Conectores Dubins

Se um conector em arco falhar, é realizada uma busca para conectar um conector Dubins a vários pontos da cabeceira na direção de deslocamento desejada, até encontrar um válido que minimize a variação total de ângulo.

Conector de Reserva

Como último recurso, criamos um conector de reserva que simplesmente une os dois pontos diretamente (seja entre duas faixas ou faixa-cabeceira) e aparece na interface como uma grande linha vermelha. O usuário deve realizar essa curva manualmente antes de continuar a rota.

Encurtamento de Curvas

Se uma curva não couber de uma faixa para outra ou para uma cabeceira sem que alguma parte do veículo ultrapasse o limite do campo, e se a configuração "Encurtar Faixas" estiver ativada, a curva será encurtada, ou seja, iniciará antes do fim da faixa para conseguir realizá-la. Infelizmente isso causa uma área perdida, a menos que seu veículo consiga recuar antes de fazer a curva (trabalhos futuros suportarão essa funcionalidade se houver demanda). Se você notar que muita área está sendo perdida, provavelmente não há cabeceiras suficientes com base no raio de curva do seu veículo, e pode ser necessário replanejar com mais cabeceiras. No roadmap está a sugestão automática de número de cabeceiras com base no seu campo e equipamento.

Extensão de Curvas

Em algumas situações, pode ser desejável estender as curvas mais fundo na cabeceira. Isso pode ser ativado pela configuração "Estender Curvas nas Cabeceiras". Se a curva couber, ela será estendida até tocar a cabeceira mais externa. Isso oferece mais espaço para curvar e endireitar, minimizando o pisoteio. Trabalhos futuros incluem sempre latar nas cabeceiras quando possível para minimizar ainda mais o pisoteio.

Conexões de Cabeceira Encurtadas

Curvas adjacentes encurtadas para caber na cabeceira serão convertidas em travessias de cabeceira quando possível. Isso pode ser ativado pela configuração "Preferir Conexões de Cabeceira Encurtadas". Trabalhos futuros incluem habilitar isso para todas as conexões faixa-faixa.

Sem Configuração

A curva é encurtada para apenas tocar a cabeceira, mas não percorre ao longo dela.

Com Configuração

As conexões são feitas ao longo da cabeceira entre conectores adjacentes, minimizando o pisoteio.

Navegação de Cabeceiras

Quando uma curva direta de faixa a faixa não é possível, a solução de roteamento alterna para o modo de navegação de cabeceiras. Conectores das faixas para as cabeceiras são criados, seguidos de uma série de travessias e conectores entre cabeceiras.

Travessias Completas de Cabeceira

Trabalhe automaticamente todas as cabeceiras do seu campo com planejamento adicional: encontramos eficientemente um caminho de ida e volta para cada cabeceira de um grupo, minimizando a distância não trabalhada percorrida e preservando o tráfego de rodas. Nosso algoritmo pode partir de qualquer faixa inicial ou final na cabeceira. O algoritmo evita curvas que possam colidir com obstáculos, garantindo segurança.

Preferir Cabeceira Mais Externa

Ao realizar travessias de cabeceira, o algoritmo por padrão se conecta à cabeceira exterior mais central, pois oferece um bom equilíbrio entre espaço para curvar e endireitar. Ativar "Preferir Cabeceira Mais Externa" fará com que ele se conecte à cabeceira mais externa.

Comportamento Padrão

As travessias de cabeceira se conectam naturalmente à cabeceira mais central.

Curvas Conectadas à Cabeceira Mais Externa

Com "Preferir Cabeceira Mais Externa" ativado, todas as travessias de cabeceira se conectam à cabeceira exterior mais externa quando possível.

Roteamento de Múltiplas Faixas Internas

Exemplo de uma situação complexa em que o solver de rota encontra um caminho por múltiplas cabeceiras, trabalhando-as, bem como todas as faixas internas.

Cruzamentos de Cabeceira

Se um ângulo for muito agudo em uma cabeceira ou faixa curva e o objetivo for minimizar a área perdida, suportamos um fluxo de trabalho de cruzamento: estendemos as linhas e as conectamos com um arco que respeita o raio de curva do veículo. Trabalhos futuros incluem estender ainda mais a curva para que o veículo inteiro se endireite antes de recuar.

Cabeceiras Direcionáveis

Se uma mudança de ângulo supera determinado limite em uma cabeceira ou faixa curva, marcamos o ponto como necessitando de suavização. Em seguida, inserimos inteligentemente círculos com o raio de curva do veículo de modo a minimizar a área perdida entre as passagens. Após a suavização, obtemos uma passagem de cabeceira que respeita as restrições de curvatura do veículo e minimiza a área perdida. Trabalhos futuros incluem uma decisão mais inteligente entre suavizar ou usar cruzamentos em um canto.

Antes da Suavização

Resultados de exemplo de um algoritmo de deslocamento padrão. Embora haja maior cobertura, o veículo não consegue fisicamente realizar curvas tão fechadas.

Após a Suavização

Após a suavização ter sido aplicada. Curvas que o algoritmo não conseguiu suavizar são convertidas em cruzamentos. Todas as curvas suavizadas respeitam o raio mínimo de viragem.

Algoritmos / Padrões

Algoritmo Padrão

Por padrão, modelamos o problema como uma instância do Problema de Roteamento Agrícola (ARP), que é a versão agrícola do bem conhecido Problema de Roteamento de Veículos. É o que se conhece como NP-difícil, ou seja, não existem algoritmos que possam resolver eficientemente todas as instâncias possíveis do problema de forma perfeita. Por isso desenvolvemos um solver meta-heurístico personalizado para resolver o ARP, codificando os padrões dos produtores na própria matriz de custos, gerando uma rota capaz de navegar pelos campos mais complexos em questão de minutos ou até segundos.

Nosso solver de roteamento calcula as distâncias de/para cada par possível de faixas no campo, usando rotas exatas para faixas na mesma área e estimativas inteligentes para faixas no lado oposto do campo. Isso cria o que se chama de matriz de distâncias, que é então alimentada ao nosso solver proprietário para otimizar um caminho que percorra cada faixa e cabeceira, minimizando a distância não trabalhada. Nenhuma suposição prévia é feita sobre o padrão de trabalho; os resultados são baseados exclusivamente nas distâncias calculadas entre elas. Isso permite que o solver tenha uma visão notável em certos momentos, pulando uma ou mais faixas que não são imediatamente óbvias para o usuário, apenas para usá-las depois para sair eficientemente de uma situação em que uma abordagem tradicional ficaria presa.

Evitar Pular Passagens

Quando ativado, o custo de deslocamento para uma faixa adjacente é reduzido à metade. Isso encoraja (mas não força) um padrão mais reto, ao custo potencial de maior distância não trabalhada ou, no caso abaixo, maior área perdida. No exemplo abaixo, outra cabeceira pode ser preferível para que as curvas caibam.

Faixas Contínuas (Boustrophedon)

Um padrão predefinido de ida e volta, começando de um lado do campo e indo até o outro. Ótimo para campos simples e aqueles com pequenos obstáculos.

Se você notar que há travessias de cabeceira em excesso, recomendamos executar nosso algoritmo padrão e ativar "Evitar Pular Passagens". Isso evitará casos extremos de travessias de cabeceira, ao custo de perder a uniformidade.

Espiral Agrupada

Um padrão predefinido que impõe sempre ao menos um salto de N faixas em um padrão de avançar e depois retornar. Funciona melhor em campos simples e com pequenos obstáculos.

Cobra

O padrão cobra cobre o campo pulando uma faixa a cada curva e depois retornando pelas faixas não cobertas. Reduz o número de curvas acentuadas.

Roteamento por Capacidade

Se o usuário especificar capacidade e vazão para seu veículo, poderá acessar nossos diversos recursos de roteamento por capacidade. Atualmente temos dois fluxos de trabalho separados para isso. O primeiro é Veículo Único, que é o tipo de rota mostrado acima, sem área de preparo e apenas um veículo trabalhando. O outro é Múltiplos Veículos com Capacidade, em que um ou mais veículos partem de uma área de preparo e podem trabalhar faixas até atingirem sua capacidade, momento em que retornarão ao depósito de preparo pelas cabeceiras.

Múltiplos Veículos com Área de Preparo

Atualmente é uma configuração experimental em desenvolvimento. As rotas podem não estar bem otimizadas e podem se comportar de forma estranha ou até mesmo travar até que as desenvolvamos mais.

Se ativado, uma área de preparo será determinada estendendo primeiro a faixa mediana do campo e escolhendo um ponto no limite que a intercepte. A ideia é ter uma área de preparo aproximadamente central, mas trabalhos futuros incluem a opção de definir uma ou mais áreas de preparo possíveis para retorno. As áreas de preparo são definidas atualmente como um único ponto no limite.

A rota agora começará e terminará na área de preparo e, quando necessário, o veículo realizará uma travessia de cabeceira de volta para reabastecimento/descarga. O otimizador considera o custo de ir e vir da área de preparo, o que é diferente dos métodos acima, que são realizados como pós-processamento de uma rota regular sem capacidade. Na literatura acadêmica, isso é conhecido como Problema de Roteamento de Veículos com Capacidade, ou CVRP.

Experimental

Uma coleção de funcionalidades futuras e experimentais em que a equipe Verge está trabalhando. Entre em contato conosco para dúvidas ou sugestões do que você gostaria de ver a seguir.

Plano de Percurso por Dados de Log

Usando dados de log da sua máquina, podemos recriar o trajeto percorrido pelo seu veículo, permitindo reprodução de rota, análise e, em breve, planejamento a partir de dados de log. Isso permite cobrir exatamente a mesma área que uma operação anterior, ou funcionalidades mais complexas, como semeadura entre fileiras ou tratamento de fileiras com lacunas. Algoritmos inteligentes utilizam dados de log para reconstruir com precisão as faixas mesmo quando há dados ausentes.
Atualmente estamos experimentando suporte ao John Deere e ao Trimble PTx FarmENGAGE, mas se você utiliza um formato específico, ficaremos mais do que felizes em trabalhar juntos para acomodá-lo.

Recriação de Faixas a Partir de Dados de Sensor

Usando os dados do sensor, muitas vezes conseguimos recuperar a linha central original, mesmo quando alguns pontos estão ausentes ou têm leituras incorretas.

Reprodução de Rota com Dados Reais

Visualize e analise como seu campo foi trabalhado. Trabalhos futuros podem incluir análises detalhadas de quando as operações foram realizadas, por quais máquinas e sugestões de como melhorá-las.

Implementos Rebocados

Um veículo pode ter um ou mais implementos rebocados acoplados atrás dele. Atualmente modelamos o veículo principal com geometria de direção Ackermann, com o ponto de engate a uma distância fixa atrás do eixo traseiro de cada veículo e implemento. Múltiplos implementos podem ser encadeados, e assumimos que todos são não motorizados. Executamos simulações cinemáticas do veículo percorrendo nossas curvas para mostrar onde estarão os limites do seu sistema de equipamentos, alertando sobre situações perigosas de saída do campo. Trabalhos futuros incluem melhorar as curvas levando em conta o implemento rebocado, otimizar curvas para minimizar o estresse no engate e incorporar isso ao nosso algoritmo de busca.

Representação do Campo em Grade

Uma abordagem promissora usada em autonomia é discretizar a área de trabalho como uma grade, onde um tipo de busca conhecido como A* híbrido pode ser usado para encontrar o caminho direcionável mais curto entre quaisquer dois pontos da grade. Abaixo está um exemplo de parte de um campo discretizado dessa forma. As seções verdes são passagens de cabeceira e são consideradas preferíveis para deslocamento, o marrom é espaço de cabeceira válido e o vermelho é área perigosa que pode levar à saída do campo.

Todas as abordagens atuais são baseadas em métodos geométricos e, portanto, podem ter dificuldade em encontrar atalhos. Um exemplo pode ser a seção inferior, onde uma abordagem tradicional de "sempre seguir a cabeceira" pode fazer o usuário dar uma volta desnecessária ao redor do obstáculo, aumentando o tempo não produtivo. Executando um algoritmo de busca, podemos ver que talvez seja possível cruzar por ali. Essa estimativa aproximada pode ajudar a guiar uma busca mais refinada, validando que seu veículo junto com quaisquer implementos pode realmente realizar esse atalho.

Um exemplo de um veículo buscando um caminho em um sistema de grade mais simples. Observe como o planejador incorpora as dimensões do veículo. Os vários arcos verdes e marrons correspondem a possíveis trajetórias que o algoritmo percorreu antes de encontrar a solução final. Trabalhos futuros incluem uma função de penalização que evite colar nas paredes como neste vídeo, bem como diversas melhorias de desempenho, preferência por percursos ao longo das cabeceiras e integração geral com nossa solução completa de roteamento.

Mais informações sobre casos de uso potenciais e mais exemplos em breve.

Opções de Configuração

Uma lista de opções possíveis a serem passadas ao algoritmo de roteamento, com uma breve explicação. Para mais informações, consulte nossa documentação de API ou entre em contato conosco.