BRPI0519965B1

BRPI0519965B1 - Método para determinar um trajeto para um veículo, e, planejador de trajeto para determinar um trajeto para um veículo

Info

Publication number: BRPI0519965B1
Application number: BRPI0519965-4A
Authority: BR
Inventors: Nicholas Simon Flann; Shane Lynn Hansen; Sarah Ann Gray
Original assignee: Deere & Company
Priority date: 2005-01-25
Filing date: 2005-12-13
Publication date: 2018-01-09
Also published as: US7079943B2; EP1844298A2; EP1844298A4; BRPI0519965A2; EP1844298B1; CA2593530A1; WO2006080996A3; AU2005325706A1; WO2006080996A2; AU2005325706B2; US20050192749A1

Abstract

método para determinar um trajeto para um veículo, e, planejador de trajeto para determinar um trajeto para um veículo. um planej ador de trajeto (1 o) e um método para determinar um trajeto para um veículo inclui definir um ponto de partida para o veículo. um ponto de terminação é definido. um detector de obstáculo (14) detecta um ou mais obstáculos em uma área de trabalho entre o ponto de partida e o ponto de terminação. uma zona de limite é definida sobre cada obstáculo correspondente. trajetos candidatos são identificados entre o ponto de partida e o ponto de terminação. cada trajeto candidato só intersecta uma vez cada zona de limite para cada obstáculo correspondente. um custo econômico é estimado para atravessar cada trajeto candidato ou uma porção dele entre o ponto de partida e o ponto de terminação. um trajeto preferencial é selecionado dos trajetos candidatos identificados baseado no trajeto preferencial estando associado com um custo econômico estimado mais baixo.

Description

(54) Título: MÉTODO PARA DETERMINAR UM TRAJETO PARA UM VEÍCULO, E, PLANEJADOR DE TRAJETO PARA DETERMINAR UM TRAJETO PARA UM VEÍCULO (51) lnt.CI.: G01C 21/34 (30) Prioridade Unionista: 25/01/2005 US 11/042,636 (73) Titular(es): DEERE & COMPANY (72) Inventor(es): NICHOLAS SIMON FLANN; SHANE LYNN HANSEN; SARAH ANN GRAY

1/24 “MÉTODO PARA DETERMINAR UM TRAJETO PARA UM VEÍCULO, E, PLANEJADOR DE TRAJETO PARA DETERMINAR UM TRAJETO PARA UM VEÍCULO”

Campo da Invenção [001] A presente invenção diz respeito a um planejador de trajeto e a um método para planejar um trajeto a partir de um ponto a outro.

Fundamento da Invenção [002] Um planejador de trajeto pode ser usado para determinar um ou mais planos de trajeto para um veículo se mover por uma área de trabalho de um primeiro ponto até um segundo ponto, afastado do primeiro ponto. A área de trabalho pode representar um campo para cultivar uma colheita, um campo de batalha, ou qualquer outro terreno. Tal área de trabalho pode incluir um ou mais obstáculos que podem prevenir, mas não precisam prevenir, um trajeto geralmente bnear do primeiro ponto ao segundo ponto.

[003] Th. Lozano-Perez et al., “An Algorithm for Planning ColbsionFree Paths Amongst Polyhedral Obstacles”, Research Report, IBM Research Division, 6 de Dezembro de 1978, considerado como genérico, descreve um método para planejamento de trajeto e um planejador de trajeto. Os pontos de partida e de terminação e posições de obstáculos são inseridos, e o trajeto curto do ponto de partida ao ponto de terminação é determinado com uma suficiente zona de folga em relação aos obstáculos para evitar uma cobsão com o objeto, usando um assim-denominado algoritmo ‘VGRAPH’ que utibza um gráfico de visibibdade entre vértices conectados dos obstáculos. Esse algoritmo alcança, de forma automática, um número de trajetos isentos de cobsão, sendo o trajeto mais curto finalmente selecionado.

[004] Documento WO 91/09275 revela um sistema de posicionamento de veículo com um sensor de obstáculos.

[005] Documento US 5.793.934 divulga um outro método de planejar trajeto em que uma contribuição econômica de células da rede a serem cruzadas é avabada e, finalmente, a rota possuindo melhor custo-benefício é selecionada.

Petição 870170064787, de 31/08/2017, pág. 7/38

2/24

Sumário da Invenção [006] Um planejador de trajeto e um método para a determinação de um trajeto para um veículo incluem definir um ponto de partida para o veículo. Um ponto de terminação é definido. Um detector de obstáculo detecta um ou mais obstáculos em uma área de trabalho entre o ponto de partida e o ponto de terminação. Uma zona de folga de obstáculo é definida sobre cada obstáculo correspondente. Trajetos candidatos são identificados entre o ponto de partida e o ponto de terminação. Cada trajeto candidato só intercepta a zona de folga de obstáculo um número máximo de vezes (por exemplo, uma vez) para cada obstáculo correspondente. Um custo econômico é estimado para cruzar cada trajeto candidato ou uma porção do mesmo entre o ponto de partida e o ponto de terminação. Um trajeto preferencial é selecionado dos trajetos candidatos identificados com base no trajeto preferencial sendo associado com um custo econômico estimado mais baixo.

Breve Descrição dos Desenhos [007] Figura 1 é um diagrama de blocos de um planejador de trajeto de acordo com a invenção.

[008] Figura 2 é um exemplo de um método para planejar um trajeto de um veículo de acordo com a invenção.

[009] Figura 3 é um outro exemplo de um método para planejar um trajeto de um veículo de acordo com a invenção.

[0010] Figura 4 é uma vista de cima de uma área de trabalho ilustrativa com vários obstáculos.

[0011] Figura 5 é uma vista de cima da área de trabalho ilustrativa da

Figura 4 ilustrando segmentos de trajeto candidato.

[0012] Figura 6 é uma vista de cima da área de trabalho ilustrativa da

Figura 5 ilustrando um plano de trajeto preferencial.

[0013] Figura 7 mostra dois obstáculos ilustrativos que podem se achar em um plano de trajeto ilustrativo ou real.

[0014] Figura 8 mostra segmentos de trajetos candidatos de trajetos ao

Petição 870170064787, de 31/08/2017, pág. 8/38

3/24 redor de ou entre os obstáculos.

Descrição da Concretização Preferencial [0015] Figura 1 representa um diagrama de blocos de um sistema de planejamento de trajeto 11.0 sistema de planejamento de trajeto 11 inclui um receptor determinador de localização 26 e uma interface de usuário 28 acoplada a um planejador de trajeto 10. O planejador de trajeto 10 está acoplado a um controlador veicular 24. Por sua vez, o controlador veicular 24 está acoplado a um sistema de direção 30, um sistema de frenagem 32 (se presente), um sistema de propulsão 34 e um sistema de proteção 36.

[0016] Planejador de trajeto 10 inclui um dispositivo definidor 12, um detector de obstáculo 14, um modelador de obstáculo 16, um analisador 18, um estimador 20 e um maquinário de pesquisa 22, que podem ser chamados, coletivamente, dos componentes do planejador de trajeto 10. Os componentes (12, 14, 16, 18, 20 e 22) do planejador de trajeto 10 podem se comunicar entre si.

[0017] Um receptor determinador de localização 26 pode definir um ponto de partida para o veículo, enquanto o dispositivo definidor 12 define um ponto de terminação para o veículo. O ponto de partida pode incluir um ponto de partida (por exemplo, coordenadas bi- ou tridimensionais) e rumo de partida. O ponto de terminação pode incluir um ponto de terminação (por exemplo, coordenadas bi- ou tridimensionais) e um rumo de terminação. Pela interface de usuário 28, um usuário pode entrar com um ponto de terminação (e rumo de terminação) para o veículo baseado em uma preferência de usuário, uma decisão de usuário ou algum outro objetivo ou alvo.

[0018] Um detector de obstáculo 14 detecta um ou mais obstáculos em uma área de trabalho entre o ponto de partida e o ponto de terminação. O detector de obstáculo pode usar um ou mais dos componentes seguintes: um detector de obstáculo ultra-sônico, um laser de varredura, um descobridor de alcance, um sistema de ladar (por exemplo, radar a laser), a sistema de radar, um sistema de visão por máquina, um sistema de visão estéreo, ou outro

Petição 870170064787, de 31/08/2017, pág. 9/38

4/24 detector de obstáculo. O detector de obstáculo 14 pode usar dados observados do sistema de proteção 36 para detectar a presença de um obstáculo ou dados coletados previamente, ou uma pesquisa da área de trabalho que é introduzida ou entrada no planejador de trajeto 10 pela interface de usuário 28.

[0019] Um modelador de obstáculo 16 define uma zona de folga de obstáculo sobre um limite físico de cada obstáculo. Por exemplo, a zona de folga de obstáculo pode ser definida estendendo uma zona sobre as dimensões físicas atuais ou limite físico do obstáculo antes de um ou mais do seguinte: (a) modelar o perímetro ou periferia da zona de folga de obstáculo como um aumento no tamanho bidimensional ou tridimensional do limite do objeto por um certo fator ou porcentagem (por exemplo, percentagem definível por usuário), e (b) modelar o perímetro ou periferia da zona de folga de obstáculo como um aumento no tamanho bidimensional ou tridimensional do limite do objeto em proporção aos constrangimentos veiculares do veículo. Os referidos constrangimentos veiculares do veículo incluem o raio de curvatura mínimo do veículo, a largura veicular, a base de roda e similares. Por exemplo, a zona de folga de obstáculo pode ser selecionada para assegurar passagem segura do veículo baseado na precisão e confiabilidade do receptor determinador de localização 26 para constrangimentos de orientação e veiculares (por exemplo, largura veicular e raio de curvatura mínimo) tal que o veículo passe seguramente pela obstrução ou obstáculo sem colidir com ele, bater nele, esbarrar contra ele, ou caso contrário contatá-lo.

[0020] Um analisador 18 identifica trajetos candidatos (ou segmentos de trajeto candidato) entre o ponto de partida e o ponto de terminação. Em uma concretização, cada trajeto candidato ou segmento de trajeto candidato só intercepta cada zona de folga de obstáculo um número máximo de vezes (por exemplo, uma vez) para cada obstáculo correspondente. O número máximo real de vezes para interceptar a zona de folga de obstáculo pode depender da geometria física do obstáculo (por exemplo, se suas superfícies ou convexas ou côncavas).

Petição 870170064787, de 31/08/2017, pág. 10/38

5/24 [0021] Um estimador 20 estima um custo econômico para cruzar cada trajeto candidato ou uma porção dele (por exemplo, segmento de trajeto candidato) entre o ponto de partida e ponto de terminação. O custo econômico pode ser definido em termos (a) da distância do trajeto candidato ou porção dele, (b) a duração antecipada de executar o trajeto candidato ou uma porção dele, ou (c) a distância e duração antecipada.

[0022] O estimador 20 pode ainda incluir um filtro para descartar ou excluir trajetos candidatos de um processo de procura (por exemplo, algoritmo de pesquisa) se tal trajeto candidato tiver pelo menos uma de uma estimativa de custo de trajeto total, uma estimativa de duração de trajeto total e uma estimativa de comprimento de trajeto total que excede uma estimativa de desempenho de referência de trajeto correspondente, por mais de um limiar máximo, associado com um trajeto linear geralmente direto entre o ponto de partida e o ponto de terminação. Aquela estimativa de desempenho de referência pode ser expressa como uma estimativa de custo de referência, uma estimativa de duração de referência, ou uma estimativa de comprimento de referência para o trajeto linear geralmente direto entre o ponto de partida e o ponto de terminação. [0023] Um maquinário de pesquisa 22 seleciona um trajeto preferido daqueles trajetos candidatos identificados ou segmentos de trajetos candidatos identificados com base no trajeto preferencial sendo associado com um custo econômico estimado mais baixo. Por exemplo, o trajeto preferido poderá estar associado com a distância mais curta dos trajetos candidatos ou com a duração antecipada mais curta de execução para os trajetos candidatos.

[0024] O controlador de veículo 24 aceita uma entrada do plano de trajeto (por exemplo, o plano de trajeto preferencial) e controla o veículo consistente com o plano de trajeto (por exemplo, plano de trajeto preferencial), a menos que o sistema de proteção 36 detecte um obstáculo, obstrução, perigo, ou condição de segurança que requeira o veículo partir do trajeto planejado, para parar movimento ou tomar medidas evasivas para evitar uma colisão com um objeto ou ser vivo.

Petição 870170064787, de 31/08/2017, pág. 11/38

6/24 [0025] O controlador de veículo 24 pode gerar sinais de controle para um sistema de direção 30, um sistema de frenagem 32, e um sistema de propulsão 34 que são consistentes com rastrear o plano de trajeto (por exemplo, plano de trajeto preferencial). Os sinais de controle podem incluir um sinal de controle de direção ou mensagem de dados que define um ângulo de direção do eixo de direção; um sinal de controle de frenagem ou mensagem de dados que define a quantidade de desaceleração, pressão hidráulica, ou fricção de frenagem aplicada a freios; um sinal de controle de propulsão ou mensagem de dados que controla um ajuste de acelerador, um fluxo de combustível, ou um sistema de injeção de combustível. Onde o sistema de propulsão inclui um acionamento elétrico ou motor elétrico, o sinal de controle pode incluir energia elétrica, corrente elétrica, tensão elétrica, velocidade veicular ou aceleração veicular.

[0026] O sistema de direção 30 pode incluir um sistema de direção hidráulica controlado eletricamente, uma direção de cremalheira e pinhão eletricamente acionada, um sistema de direção de Ackerman, ou outro sistema de direção. O sistema de frenagem 32 pode incluir um sistema de frenagem hidráulica controlado eletricamente, ou outro sistema de frenagem de fricção controlado eletricamente. O sistema de propulsão 34 pode incluir um motor de combustão interna, um sistema híbrido de motor combustão interna elétrico, um sistema de acionamento elétrico, ou similar.

[0027] Figura 2 é um fluxograma de um método para determinar um trajeto para um veículo. O método da Figura 2 começa na etapa S100.

[0028] Na etapa S100, um receptor determinador de localização 26 ou um planejador de trajeto 10 define um ponto de partida para o veículo. Por exemplo, o receptor determinador de localização 26 determina um ponto de partida (por exemplo, em coordenadas bi- ou tridimensionais) e um rumo (por exemplo, referenciado para Norte, Norte magnético ou outro ponto de referência ou direção) para o veículo.

[0029] Na etapa S102, o dispositivo definidor 12 define um ponto de

Petição 870170064787, de 31/08/2017, pág. 12/38

7/24 terminação para o veículo. Por exemplo, o dito dispositivo definidor 12 define o ponto de terminação (por exemplo, em coordenadas bi- ou tridimensionais) e rumo para o veículo.

[0030] Na etapa S104, um detector de obstáculo 14 detecta um ou mais obstáculos em uma área de trabalho entre o ponto de partida e o ponto de terminação. Por exemplo, o detector de obstáculo pode varrer uma região ao redor do veículo e estimar os locais bidimensionais e tridimensionais de pontos em ou mais obstáculos na região varrida. Em uma concretização, um obstáculo pode ser modelado como uma região pobgonal (por exemplo, um retângulo). Em outra concretização, um obstáculo pode ser modelado com um perímetro que representa um ou mais arcos (por exemplo, um elipsóide ou um círculo) ou uma combinação de um ou mais arcos e uma ou mais seções retilíneas interconectando os arcos.

[0031] Na etapa S106, um anabsador 18 define uma zona de folga de obstáculo sobre cada obstáculo correspondente. Por exemplo, a zona de folga de obstáculo está espaçada à parte do obstáculo ou objeto tal que o veículo tenha uma folga física para passar desimpedido entre o veículo e a periferia física extema do objeto se o veículo seguir um trajeto que é tangencial a ou caso contrário associado com um limite externo da zona de folga de obstáculo. Um segmento de trajeto planejado pode interceptar o limite externo da zona de folga de obstáculo associada com um vértice ou nó no bmite de objeto, por exemplo. Um vértice ou nó é onde segmentos de trajeto diferentes estão interconectados. O bmite exterior pode ser centrado sobre o obstáculo. Em um exemplo, o bmite exterior inclui uma forma elíptica ou circular. Em outro exemplo, o bmite exterior inclui uma forma retangular para reduzir recursos computacionais. O obstáculo pode ser modelado como formas elípticas, circulares, ou retangulares consistentes com o limite exterior da zona de folga de obstáculo.

[0032] Na etapa S108, um anabsador 18 identifica trajetos candidatos (ou segmentos de trajeto) entre o ponto de partida e ponto de terminação. Cada

Petição 870170064787, de 31/08/2017, pág. 13/38

8/24 trajeto candidato apenas intercepta cada zona de folga de obstáculo um número máximo de vezes (por exemplo, uma vez) para cada obstáculo correspondente. Por exemplo, cada trajeto candidato intercepta cada bmite exterior da zona de folga de obstáculo uma vez para cada obstáculo.

[0033] Etapa S108 pode ser efetuada de acordo com vários procedimentos, que podem ser apbcados separadamente ou cumulativamente. De acordo com uma primeira técnica, o trajeto candidato identificado inclui um trajeto ou segmento de trajeto do ponto de partida para a zona de limite sobre um obstáculo correspondente. De acordo com uma segunda técnica, o trajeto candidato identificado inclui um primeiro segmento de trajeto de um ponto de partida para um primeiro bmite (de uma primeira zona de folga de obstáculo) sobre um primeiro obstáculo correspondente, um segundo segmento de trajeto de um primeiro bmite para um segundo bmite (de uma segunda zona de folga de obstáculo) sobre um segundo obstáculo correspondente. De acordo com uma terceira técnica, o trajeto candidato identificado inclui um trajeto de um bmite de objeto para um ponto de terminação ou uma fronteira da área de trabalho. De acordo com uma quarta técnica, nós ou vértices dos trajetos candidatos são determinados formando interconexões tangenciais entre bmites de objeto adjacentes.

[0034] Na etapa S109, um filtro ou estimador 20 filtra os trajetos candidatos identificados baseado em pelo menos uma de uma estimativa de custo geralmente bnear e uma regra de trajeto (por exemplo, critérios de toques máximos). Por exemplo, o filtro ou estimador 20 pode reduzir o espaço de pesquisa ou eliminar trajetos candidatos ou segmentos de trajeto de consideração que (1) não são acionados pelo veículo (por exemplo, requerem voltas ortogonais onde o veículo tem direção de Ackerman), (2) batem ou cobdem com um ou mais obstáculos na área de trabalho, (3) excedem um comprimento de trajeto máximo ou bmite de custo de bmiar máximo (por exemplo, em relação a outros trajetos candidatos propostos ou de tentativa ou soluções para o trajeto preferencial), ou (4) tocam um obstáculo ou limite

Petição 870170064787, de 31/08/2017, pág. 14/38

9/24 exterior da área de trabalho mais que um número de vezes máximo de limiar. Porém, um único toque ou toque de um obstáculo é definido aqui como (a) o veículo está entrando em contato com um limite exterior da zona de folga de obstáculo associado com um obstáculo correspondente, (b) o veículo está viajando ou não viajando ao longo do limite exterior da zona de folga de obstáculo, e (c) o veículo está partindo do limite exterior depois da ocorrência de (a) ou (b) acima. Trajetos candidatos não são acionados onde o raio de um arco no segmento de trajeto candidato é maior do que o raio de curvatura mínimo do veículo.

[0035] Sob uma técnica de estimação de custo linear, o estimador 20 estima o custo para completar um trajeto parcial do ponto de partida. Por exemplo, uma estimativa de custo de trajeto de linha reta do ponto de partida do trajeto para o ponto de terminação, ignorando obstáculos pode prover uma estimativa de custo bnear de referência (por exemplo, uma estimativa de custo ideal) para comparação contra trajetos candidatos realistas dados obstáculos. A estimativa de custo de referência precedente tende a subestimar o custo verdadeiro para completar desde que ignora constrangimentos de raio de curvatura e a possível interferência de obstáculos. Porém, se um trajeto candidato exceder a estimativa de custo linear de referência por mais que uma quantidade máxima, o trajeto candidato pode ser rejeitado sumariamente para suprimir o espaço de solução e conservar recursos computacionais do planejador de trajeto 10. Os trajetos candidatos identificados são filtrados baseado em uma estimativa de desempenho de referência de um trajeto bnear geralmente direto entre o ponto de partida e o ponto de terminação.

[0036] Em uma concretização, a técnica de estimativa de custo bnear pode ser efetuada de acordo com o procedimento seguinte: O filtro ou estimador 20 filtra os trajetos candidatos identificados para excluir pelo menos uma porção rejeitada dos trajetos candidatos identificados de um processo de pesquisa se tal trajeto candidato rejeitado tiver pelo menos uma de uma estimativa de custo de trajeto total, uma estimativa de duração de

Petição 870170064787, de 31/08/2017, pág. 15/38

10/24 trajeto total, e uma estimativa de comprimento de trajeto total que excede uma estimativa de referência de trajeto correspondente, por mais que um limiar máximo, associado com um trajeto linear geralmente direto entre o ponto de partida e o ponto de terminação.

[0037] Sob a apbcação de regras de trajeto, o filtro ou estimador 20 reduz ou ebmina percurso em volta desnecessário do trajeto candidato ou segmento de trajeto candidato pelos obstáculos. Por exemplo, a regra de trajeto pode fixar um limite no número de vezes que um trajeto candidato pode interceptar uma zona de folga de obstáculo. Tal bmitação no número de vezes que um trajeto candidato pode interceptar uma zona de folga de obstáculo pode ser chamada critérios de toques máximos. Sob um exemplo de critérios de toques máximos, uma regra de trajeto relaciona-se a contatar um bmite exterior associado com uma folga de obstáculo sobre um obstáculo menos que ou igual a um número de vezes máximo designado.

[0038] Considere um obstáculo convexo que se acha entre o ponto de partida e o ponto de terminação. Aqui, o número máximo de toques do bmite exterior da zona de folga de obstáculo é fixado a um para o filtro de toques máximos. Portanto, cada segmento de trajeto candidato vábdo ou trajeto é permitido tocar (chegar, seguir a fronteira de forma, então partir) uma vez durante a construção de trajeto candidato ou pesquisa para o trajeto preferencial. Qualquer segmento de trajeto candidato ou solução parcial que toque este limite exterior da zona de evitar obstáculo (por exemplo, para um obstáculo convexo) mais que o número máximo de toques (por exemplo, uma vez, para um obstáculo convexo ou mais vezes para um obstáculo com concavidades) será considerado inválido ou não ótimo e pode ser descartado de consideração pelo processo de pesquisa. Em termo geral, os toques máximos permitidos podem ser determinados como um mais o número de concavidades da forma.

[0039] Porém, a regra de formação de trajeto no número máximo de toques é diferente para a forma de fronteira exterior do que para um obstáculo

Petição 870170064787, de 31/08/2017, pág. 16/38

11/24 convexo na área de trabalho. Aqui, o número máximo de toques permitidos é simplesmente o número de concavidades da forma de fronteira exterior associada com a área de trabalho. Em resumo, trajetos candidatos, segmentos de trajeto ou a solução parcial que excede o número máximo de toques permitidos para uma forma de fronteira externa, uma zona de folga de limite, ou uma zona de folga de obstáculo é descartada antes ou durante o processo de pesquisa. Este processo de filtragem é particularmente efetivo quando há muitos obstáculos em uma área de trabalho porque força o processo de pesquisa a expandir trajetos que fazem progresso para a meta de alcançar o ponto de terminação, em lugar de vagar sem objetivo entre obstáculos ou seguir uma rota sinuosa.

[0040] Em resumo, o estimador 20 ou o filtro pode filtrar os trajetos candidatos identificados com base em um ou mais dentre o seguinte: (1) uma estimativa de desempenho de referência de um trajeto bnear geralmente direto entre o ponto de partida (por exemplo, de acordo com a técnica de estimativa de custo bnear) e o ponto de terminação, e (2) um critério de toque máximo, onde o critério de toque máximo se refere a contatar um limite exterior associado com uma folga de obstáculo sobre um obstáculo menos que ou igual a um número de vezes máximo designado.

[0041] Na etapa Si 10, um estimador 20 estima um custo econômico para cruzar cada trajeto candidato ou uma porção dele (por exemplo, um segmento de trajeto) entre o ponto de partida e o ponto de terminação. O custo econômico pode ser definido em termos da distância do trajeto candidato ou porção dele, a duração antecipada de executar o trajeto candidato ou uma porção dele, ou ambos.

[0042] Na etapa Si 12, um planejador de trajeto 10 ou maquinário de pesquisa 22 seleciona um trajeto preferencial dos trajetos candidatos identificados baseado no trajeto preferencial sendo associado com um custo econômico estimado mais baixo (por exemplo, um custo total do trajeto candidato e seus segmentos de trajeto candidato constituintes no agregado).

Petição 870170064787, de 31/08/2017, pág. 17/38

12/24

Por exemplo, o trajeto preferencial pode ser associado com a distância mais curta dos trajetos candidatos ou a duração antecipada mais curta de execução para os trajetos candidatos percorrerem do ponto de partida ao ponto de terminação. Além de ser o custo estimado mais baixo, o trajeto preferencial deve satisfazer um ou mais dos critérios suplementares seguintes: (1) o trajeto preferencial deve ser acionável pelo veículo dados seus constrangimentos veiculares (por exemplo, raio de curvatura mínimo); (2) o trajeto preferencial deve evitar golpear ou colidir com objetos e obstáculos na área de trabalho; e (3) o trajeto preferencial deve evitar golpear, contatar ou machucar pessoas e animais na área de trabalho.

[0043] A seleção da etapa S112 pode ser executada de acordo com vários procedimentos, que podem ser aplicados alternada ou cumulativamente. Sob um primeiro procedimento, o planejador de trajeto 10 ou o maquinário de pesquisa 22 pesquisa os trajetos candidatos ou porções de trajetos candidatos de acordo com o algoritmo de pesquisa A* para determinar o plano de trajeto preferencial. Sob um segundo procedimento, o planejador de trajeto 10 ou o maquinário de pesquisa 22 pesquisa os trajetos candidatos ou porções de trajetos candidatos de acordo com o algoritmo de pesquisa A* ligado. Sob de um terceiro procedimento, o planejador de trajeto 10 ou o maquinário de pesquisa 22 pesquisa os trajetos candidatos ou porções de trajetos candidatos de acordo com outro algoritmo de pesquisa para determinar o plano de trajeto preferencial.

[0044] Sob o primeiro procedimento, um planejador de trajeto 10 determina o plano de trajeto preferencial do plano de trajeto candidato baseado nos custos econômicos dos planos de trajeto candidato (por exemplo, cada plano de trajeto candidato ou um subconjunto razoável disso) de acordo com um algoritmo de pesquisa A*. Os custos econômicos podem incluir as distâncias ou consumo de energia para um ou mais dos movimentos veiculares seguintes: um veículo percorrendo a partir de um ponto de partida veicular a um primeiro obstáculo ou zona de folga de obstáculo de uma área de trabalho,

Petição 870170064787, de 31/08/2017, pág. 18/38

13/24 o veículo percorrendo a partir de um obstáculo para outro obstáculo, o veículo percorrendo de um obstáculo a um último obstáculo, e o veículo percorrendo do último obstáculo a um ponto de terminação. Um custo econômico pode ser estimado para cada permutação ou para cada combinação de ordens de obstáculo, segmentos de plano de trajeto candidato entre pares de obstáculos, e possíveis planos de trajeto candidato agregados. Um algoritmo de pesquisa pode ser usado para pesquisar entre planos de trajeto candidato (ou segmentos dele) para um plano de trajeto preferencial. Embora um sortimento prodigioso de algoritmos de pesquisa possa ser usado, tal algoritmo de pesquisa A* e tal algoritmo de pesquisa A* Limitado são dois exemplos ilustrativos de algoritmos de pesquisa para achar um plano de trajeto preferencial para o veículo de trabalho cobrir uma porção designada da área de trabalho.

[0045] Algoritmo de pesquisa A* e algoritmo de pesquisa A* Limitado ambos usam a notação seguinte, constantes e funções:

[0046] S denota uma solução (tanto vazia, parcial ou completa). Uma solução representa um plano de trajeto. Uma solução completa representa um plano de trajeto preferencial. Uma solução parcial representa uma estimativa ou plano de trajeto candidato, que pode ou não representar um plano de trajeto preferencial.

[0047] W é uma constante, um número negativo grande (tal como 10.000). O usuário pode definir o número mínimo de limiar.

[0048] Depth(S) é a profundidade da solução S (a contagem do número de expansões que ela teve). Uma expansão é uma solução potencial ou plano de trajeto candidato. A expansão pode ter segmentos de trajeto candidato filho que são dependentes de um plano de trajeto candidato pai, por exemplo.

[0049] Q denota uma fila de prioridade com uma função de prioridade

Score(S), onde S é um item na Fila.

[0050] Pop(Q) retoma o item de contagem mais baixa na fila ou pilha de dados. A fila ou pilha de dados pode representar uma série de registros de armazenamento de dados, armazenamento magnético de dados, memória

Petição 870170064787, de 31/08/2017, pág. 19/38

14/24 óptica de dados, memória, memória de computador volátil ou similar.

[0051] Push(Q, S) empurra S sobre a fila Q ou pilha de dados.

Funções dependentes de domínio:

G(S) é o custo da solução parcial até agora;

H(S) é o custo estimado para completar a solução parcial;

F(S) é simplesmente G(S) + H(S), um limite inferior no custo final de S;

Expand(S) retoma uma lista de novas soluções de filho criadas expandindo-se a solução parcial S;

Complete?(S) retoma como verdadeiro quando S é uma solução completa; falso, caso contrário.

[0052] De acordo com um primeiro procedimento para executar a etapa

SI 12, o Algoritmo A* pode ser usado para pesquisar uma solução de plano de trajeto óúma ou preferencial para o gráfico de obstáculo de acordo com aquelas instruções de software a seguir:

Let Score(S) χ F(S)

Let S be the empty solution, push(G, S)

Let best_solution = false

While Not(best_soluíion)

S = pop(Q)

If Complete?(S) then best = S

Efse For all s Ϊ Expand(S)

Do Push(G,s)

Fínaily Return best [0053] Os componentes seguintes do algoritmo A* podem ser usados para executar o processo de pesquisa da etapa SI 12:

A solução inicial: Isto consiste de um trajeto vazio começando na configuração de partida;

O custo de uma solução até agora: é a soma daqueles custos individuais das bordas (trajetos) na solução até agora;

Petição 870170064787, de 31/08/2017, pág. 20/38

15/24

A função de expansão de solução: essa toma uma solução e retoma um conjunto de soluções de filhos. Considere uma solução parcial que chegou à forma Z indo na direção anti-horária. Então, esta solução pode ser expandida para seguir a fronteira de forma Z na direção anti-horária, então deixar a forma Z a uma tangente chegar a todas as formas em qualquer direção onde um trajeto direto desimpedido existe; e

O custo estimado para completar: esta função retoma um salto mais baixo no custo para completar a solução. Quanto mais preciso este salto inferior, melhor o desempenho do maquinário de pesquisa, visto que soluções serão achadas mais cedo e menos memória será consumida. Uma técnica heurística pode ser usada para estimar este salto inferior.

[0054] Algoritmo A* anterior geralmente não emprega um salto para limitar as repetições computacionais de possíveis planos de trajeto candidato e recursos computacionais auxiliares. A primeira solução A* acha que será ótima contanto que a função H nunca superestime o verdadeiro custo para completar a solução. Tal função H é chamada um heurístico admissível porque pode ser usada para decidir quais soluções são consideradas completas e quais não são. Numa concretização, depois de um gráfico de visibilidade for construído que inclua vários trajetos candidatos ou segmentos de trajeto candidato, a pesquisa anterior pode ser executada com o referido algoritmo A* para achar um trajeto preferencial ou trajeto de custo de mínimo a partir do ponto de partida ao ponto de terminação.

[0055] Sob um segundo procedimento, o qual é uma alternativa para o algoritmo A*, algoritmo A* Limitado é usado para executar a pesquisa pelos planos de trajeto candidato para identificar um plano de trajeto preferencial. O algoritmo A* Limitado espalha por planos de trajeto candidato para identificar a solução para o plano de trajeto preferencial. Pesquisa é um método poderoso para resolver as classes de problemas cujas soluções não podem ser calculadas diretamente. A metodologia de pesquisa resolve tais problemas primeiramente representando um grande espaço de possíveis soluções, então executando uma

Petição 870170064787, de 31/08/2017, pág. 21/38

16/24 pesquisa por este espaço começando a uma solução vazia e terminando a uma solução completa e próxima a ótima. Para definir claramente este processo de pesquisa, é necessário definir os componentes do algoritmo A*:

1) A solução inicial: um dos obstáculos que confinam a forma externa pode facilitar a determinação da solução inicial ou um plano de trajeto candidato;

2) O custo de uma solução: até agora pode ser estimado pela soma dos custos de cada uma das bordas empregadas entre os obstáculos. Não há qualquer necessidade de incluir o custo real de cruzar (por exemplo, ceifar) cada obstáculo desde que todas as soluções incluirão todos os obstáculos;

3) A função de expansão de solução: essa toma uma solução e retoma um conjunto de soluções de filho. Considerando uma solução parcial cujo último obstáculo cruzou (por exemplo, ceifou) é j, para quais obstáculos a solução poderia ser expandida? A resposta depende de qual lado de obstáculo j a solução chegou e a paridade de j. Digamos que a solução chegou ao primeiro lado de j em Forma A; então, se a paridade do obstáculo for par, o veículo terminará obstáculo j na fronteira de ShapeA. Consequentemente, todos os obstáculos não cruzados (por exemplo, não ceifados) que tem um lado em ShapeA são candidatos para expansão. Altemativamente, se a paridade do obstáculo for impar, então o veículo terminará obstáculo j no segundo lado (digamos em ShapeZ), e todos os obstáculos não cruzados (por exemplo, não ceifados) que tem um lado em ShapeZ serão candidatos para expansão.

[0056] O algoritmo A* Limitado é um híbrido daquele algoritmo A* e o algoritmo de Ramal e Salto, onde soluções são expandidas em uma primeira profundidade, melhor primeiro modo, e um salto é usado para terminar soluções parciais desnecessárias. Neste caso, o salto melhor até agora é comparado ao valor da função F de cada solução parcial. Empregando o valor F, em lugar do valor G, provê um salto mais apertado e, portanto, mais efetivo. O algoritmo A* Limitado mencionado pode ser expresso como a seguir, em consistência com as definições prévias de termos apresentados em conjunção com a Figura

Petição 870170064787, de 31/08/2017, pág. 22/38

17/24

9.

Let Score(S) = F(S) + W *Depth(S)

Let S be the empty solution, push(Q, S)

Let bound ~ ¥

While Not(Empty?(Q))

S = Pop(Q) ]f Complete?(S) then If F(S) < bound then bound - F(S), best_so_far - S

Else If F(S) < bound then For all s í Expand(S)

Do If F(s) < bound then push(G, s)

FinalEy Return bestsofar.

[0057] Aquele Algoritmo A* Limitado faz uma pesquisa de primeira profundidade e por esse meio economiza memória. O Algoritmo A* Limitado usa sua função heurística F(s) para dirigir a pesquisa a focalizar nas soluções mais promissoras durante o processo de pesquisa direta. Além disso, a função heurística F(s) é usada como um salto mais baixo em s para termina-la cedo, se seu valor nunca pode ser melhor que a solução melhor até agora.

[0058] O A* Limitado combina técnicas de ambos os Ramal-e-Salto de primeira profundidade e A* para produzir um algoritmo que: (a) acha uma solução razoável rapidamente, (b) melhora incrementalmente a solução dado mais tempo de Unidade de Processamento Central (CPU) daquele planejador de trajeto 10 ou outro processador de dados, (c) usa apenas memória limitada linearmente na profundidade de solução e (d) habilita conhecimento de controle ser incorporado no processo de pesquisa. O Ramal-e-Salto é uma abordagem clássica desenvolvida pela comunidade de pesquisa de operações para resolver problemas de otimização combinatória discreta. Vantagens de Ramal-e-Salto de primeira profundidade são que uma solução é com frequência achada de modo rápido e requisitos de memória são minimizados. Porém, a solução ótima

Petição 870170064787, de 31/08/2017, pág. 23/38

18/24 só é achada seguindo uma pesquisa exaustiva. Outro método desenvolvido da comunidade de Inteligência Artificial é A*. A vantagem de A* é que a solução ótima é achada primeiro, e conhecimento de controle pode ser incorporado no algoritmo para acelerar o progresso. Porém, A* pode requerer uma quantidade exponencial de memória, e pode não produzir uma solução dentro de um prazo razoável. Um método híbrido, referenciado de A* Limitado, captura atributos desejáveis de ambos algoritmo A* e algoritmo A* Limitado.

[0059] O método da Figura 3 é semelhante ao método da Figura 2, exceto que a etapa Si04 é substituída pela etapa S204. Mesmos números de referência indicam mesmas etapas ou procedimentos na Figura 2 e Figura 3. [0060] Na etapa S204, um ou mais obstáculos são definidos em uma área de trabalho entre o ponto de partida e o ponto de terminação. Por exemplo, um usuário pode observar e entrar com os locais (por exemplo, coordenadas bi- ou tridimensionais), dimensões (por exemplo, altura, comprimento e largura máxima) ou outras especificações dos obstáculos na área de trabalho pela interface de usuário 28. O usuário ou outro pode usar equipamento de medição (por exemplo, receptores determinadores de locahzação), equipamento de agrimensura, ou outro equipamento para determinar as locahzações de pelo menos obstáculos que são pertinentes a trajetos potenciais entre o ponto de partida e ponto de terminação na área de trabalho.

[0061] Figura 4 é uma representação de uma área de trabalho 400 com vários obstáculos 406. Um ponto de partida 404 e rumo de partida são definidos. Um ponto de terminação 402 e rumo de terminação também são definidos. Figura 4 descreve uma representação gráfica ilustrativa do ponto de partida 404 definido na etapa S100 da Figura 2 e o ponto de terminação 402 definido na etapa S102 da Figura 2, por exemplo.

[0062] Embora os obstáculos 406 e bmites de área de trabalho 400 da

Figura 4 poderiam ser apresentados como medidos ou sentidos por um veículo, os obstáculos 406 e bmites de área de trabalho 400 podem ser

Petição 870170064787, de 31/08/2017, pág. 24/38

19/24 modelados e expandidos como descrito neste parágrafo. Os obstáculos 406 atuais e fronteira exterior da área de trabalho 400 podem ser pré-processados para considerar a distância de segurança e raio de curvatura mínimo do veículo. Para propósitos de modelar os obstáculos 406 e a área de trabalho para planejamento de trajeto de ponto a ponto ou navegação por um veículo, o limite de mapa mundial real é modelado como reduzido em tamanho (por exemplo, pela zona de folga de limite 409) e os obstáculos 406 são modelados como aumentados em tamanho (por exemplo, por cada zona de folga de obstáculo respectiva) tal que o veículo seja capaz de um ou mais do seguinte:

(1) seguir os limites revisados da área de trabalho 400 sem deixar a área de trabalho ou golpear ou contatar qualquer obstáculo ao redor da borda da área de trabalho; (2) viajar pela área de trabalho 400 enquanto mantendo uma folga mínima desejada (por exemplo, zona de folga de obstáculo) entre o veículo e um obstáculo; (3) viajar pela área de trabalho sem golpear ou colidir com qualquer obstáculo estacionário ou móvel; (4) viajar ao longo de um limite exterior de uma zona de folga de obstáculo sobre um obstáculo ou em espaço livre dentro da área de trabalho; e (5) viajar de um limite exterior de um obstáculo para um próximo limite exterior de um próximo obstáculo para cruzar por um ambiente atravancado por obstáculo dentro da área de trabalho. [0063] Figura 5 é uma representação da área de trabalho 400 da

Figura 4, que inclui um grupo de planos de trajeto candidato (ou segmentos de trajeto candidato) entre o ponto de partida 404 e o ponto de terminação 402. Figura 5 descreve uma representação gráfica ilustrativa dos trajetos candidatos identificados 408 da etapa S108, por exemplo.

[0064] Um problema de planejamento de trajeto é normalmente resolvido primeiro construindo o que é conhecido como um gráfico de visibilidade, como mostrado na Figura 5, que é então pesquisado usando o algoritmo A* para achar o trajeto mais curto (ou mais barato) do ponto de partida ou confirmação de partida ao ponto de terminação ou a configuração de fim. O gráfico de visibilidade da Figura 5 consiste em segmentos (por

Petição 870170064787, de 31/08/2017, pág. 25/38

20/24 exemplo, segmentos curvados, segmentos lineares ou bordas) e nós 412, onde as bordas representam trajetos dirigíveis diretos por espaço livre (isto é, não interceptando nenhum dos obstáculos 406 ou indo fora da fronteira) e nós 412 representam pontos escolhidos onde trajetos se fundem e dividem. Há cinco tipos de trajetos (bordas) neste gráfico: (a) trajetos do ponto de partida para o ponto de terminação ou trajetos da configuração de partida para a configuração de fim; (b) trajetos do ponto de partida ou configuração de partida para as fronteiras, limite exterior de zona de folga de obstáculo (por exemplo, obstáculos 406); (c) trajetos das fronteiras ou limite externo de quaisquer das formas ou zona de folga de obstáculo à configuração de fim ou ponto de terminação; (d) trajetos ao redor das formas (por exemplo, coextensivos ou viajando ao longo de um limite exterior da zona de folga de obstáculo); e (e) trajetos deixando uma forma chegando a uma forma (possivelmente a mesma forma). Cada obstáculo 406 está associado com uma zona de folga de obstáculo 409 sobre o obstáculo para prover folga suficiente para um veículo navegar ou dirigir ao longo de um limite exterior 413 da zona de folga de obstáculo 409 sem contatar ou colidir com o obstáculo correspondente 406. As dimensões da zona de folga de obstáculo 409 podem depender das dimensões do veículo, largura veicular, raio de curvatura, e das dimensões do obstáculo, por exemplo.

[0065] Figura 6 é uma representação de uma área de trabalho 400, que mostra um plano de trajeto preferencial 410 ilustrativo entre um ponto de partida 404 e um ponto de terminação 402. O plano de trajeto preferencial 410 da Figura 6 é selecionado dos planos de trajeto candidato descritos na Figura

5. Figura 6 mostra uma representação gráfica ilustrativa do resultado do processo de seleção na etapa Si 12 da Figura 2, por exemplo.

[0066] Figura 7 mostra uma área de trabalho 409 que contém obstáculos ilustrativos (por exemplo, um primeiro obstáculo 700 e um segundo obstáculo 702). A área de trabalho 409 está bmitada por uma zona de folga de limite 409. A zona de folga de limite pode estabelecer um limite para

Petição 870170064787, de 31/08/2017, pág. 26/38

21/24 um trajeto do veículo de forma que o veículo permaneça na área de trabalho 409 e não interfira com (por exemplo, bata ou cobda) quaisquer perigos, objetos ou obstáculos na borda da área de trabalho 409. Cada obstáculo mostrado na Figura 7 tem uma forma de obstáculo ou forma física que é indicada por uma bnha tracejada. Embora a forma de obstáculo inclua extremidades geralmente semicirculares associadas com uma região central retangular, a forma de obstáculo pode ter qualquer forma geométrica ou outra na prática. Uma zona de folga de obstáculo 704 cerca a forma de obstáculo correspondente do primeiro obstáculo 700 e tem um limite exterior 706. Semelhantemente, uma zona de folga de obstáculo 704 cerca a forma de obstáculo correspondente do segundo obstáculo 702 e tem um limite exterior 706. Em geral, a zona de folga de obstáculo 704 rastreia a forma de obstáculo. Por exemplo, o limite exterior 706 da zona de folga de obstáculo 704 pode representar uma versão graduada ou expandida (por exemplo, uniformemente ou isotropicamente) do bmite físico do obstáculo.

[0067] Figura 8 mostra a geração de vários trajetos candidatos entre dois obstáculos (700, 702) da Figura 7. Deveria ser reconhecido que os trajetos candidatos na Figura 8 estão entre dois obstáculos (700, 702), em lugar de um ponto de partida e um ponto de terminação. Por conseguinte, os trajetos candidatos da Figura 8 podem representar uma porção ou segmento de um trajeto candidato ou trajeto preferencial da Figura 2. O segmento de trajeto preferencial da Figura 8 entre os obstáculos (700, 702) pode depender do ponto de partida e ponto de terminação, porém, como parte de um plano de trajeto global economicamente eficiente.

[0068] Se o raio de curvatura do veículo for maior que zero e que as formas de bmite exterior 706 das zonas de folga de obstáculo 704 ao redor dos obstáculos representar trajetos dirigíveis ao redor dos obstáculos atuais, então os trajetos diretos entre formas serão Unhas geralmente retas que partem e chegam a tangentes às zonas de folga de obstáculo 704 em limite exterior 706 da zona de folga de obstáculo 704. Onde as formas das zonas de folga de

Petição 870170064787, de 31/08/2017, pág. 27/38

22/24 obstáculo 704 são representadas por Unhas retas e arcos de círculos (onde o raio de cada arco é maior que ou igual ao raio físico mínimo do obstáculo), os possíveis trajetos diretos (por exemplo, 710, 712, 714 e 716) entre os dois obstáculos (700, 702) geralmente partem e chegam nos segmentos de arco 721 das formas.

[0069] O planejador de trajeto 10 pode considerar os arcos 721 do primeiro obstáculo 700 e os arcos do segundo obstáculo 702. Para cada par de arcos entre o primeiro obstáculo 700 e o segundo obstáculo 702, direções de viagem de partida e chegada também podem ser consideradas para rastrear cada segmento de trajeto candidato. Dados dois arcos 721 e suas direções de chegada e de partida correspondentes, os vetores 718 dos centros de arco para os pontos tangentes requeridos nos arcos 721 são computados por meio de uso de trigonometria ou de outra forma. Os pontos finais de cada trajeto candidato (710, 712, 714, e 716) podem ser representados pelos pares de vetores (ou coordenadas associadas com eles). Para construir o gráfico de visibibdade da Figura 8, o processo de formação de trajeto candidato é repetido para todos os possíveis pares de formas, incluindo a forma de fronteira exterior ou zona de folga de bmite 409. Para cada possível trajeto tangente ou trajeto candidato computado, uma verificação é feita para assegurar que não cruze por qualquer obstáculo 700 ou 702. Só trajetos desimpedidos que não interceptam quaisquer daqueles obstáculos são adicionados ao gráfico de visibibdade de ditos trajetos candidatos.

[0070] Na Figura 8, quatro segmentos de plano de trajeto candidato (710, 712, 714 e 716) são mostrados e são chamados individualmente um primeiro segmento de trajeto candidato 710, um segundo segmento de trajeto candidato 712, um terceiro segmento de trajeto candidato 714 e um quarto segmento de trajeto candidato 716. Cada segmento plano de trajeto contata tangencialmente o bmite exterior 706 da zona de folga de obstáculo 704 do primeiro obstáculo 700 e do segundo obstáculo 702 um número máximo de vezes. Como mostrado, cada segmento de trajeto contata tangencialmente o

Petição 870170064787, de 31/08/2017, pág. 28/38

23/24 limite exterior 706 do primeiro obstáculo 700 uma vez e o bmite exterior 706 do segundo obstáculo 702 uma vez para prover um trajeto entre o primeiro obstáculo 700 e segundo obstáculo 702. Embora o contato tangencial com o bmite exterior 706 possa ocorrer na parte de arco 721 dos obstáculos como mostrado, em outras concretizações, os segmentos de trajeto candidato ou segmentos de trajeto tangentes podem contatar outras porções dos obstáculos ou objetos.

[0071] A vabdade de cada segmento de trajeto candidato pode ser confirmada determinando um segmento de teste radial que intercepta ambos com o limite exterior 706 da zona de folga de obstáculo 704 e o trajeto candidato.

[0072] O segmento de teste radial 718 pode se estender de um ponto de centro geométrico do objeto ou uma porção divisível disso. Como mostrado na Figura 8, os obstáculos são divisíveis em duas porções semicirculares interconectadas por uma região retangular. Os segmentos de trajeto candidato interceptam com zonas de folga de obstáculo 704 associadas com as duas ou mais porções semicirculares dos obstáculos. Um ponto de centro de cada porção semicircular forma um ponto de fim do segmento de teste radial 718. O outro ponto de fim do segmento de teste radial 718 pode ser o bmite exterior 706 da zona de folga de obstáculo 704 ou a periferia exterior do objeto. O segmento de teste radial 718 está associado com uma folga radial entre o obstáculo e o limite exterior 706 do obstáculo. Para o trajeto candidato ser aceitável ou vábdo, o trajeto candidato deve cumprir ou exceder uma folga radial mínima para o veículo com respeito ao primeiro obstáculo 700 e o segundo obstáculo 702. Se o trajeto candidato cumprir ou exceder a folga radial mínima (por exemplo, que pode ser baseado em constrangimentos veiculares), o trajeto candidato pode ser considerado como um trajeto candidato vabdado. Se o trajeto candidato não cumprir a folga radial mínima, o trajeto é rejeitado como um trajeto candidato e como um trajeto preferencial. Altemativamente, o trajeto candidato rejeitado pode ser

Petição 870170064787, de 31/08/2017, pág. 29/38

24/24 redefinido para cumprir o requisito de folga radial mínima.

[0073] A abordagem esboçada aqui para computar trajetos ótimos de ponto a ponto em ambientes atravancados é direta para implementar e geralmente aplicável. Criar dinamicamente as porções do gráfico de visibilidade que são precisadas e usar estimação de custo linear e regras de trajeto para focalizar e suprimir a pesquisa produz um algoritmo efetivo e eficiente que pode resolver rapidamente problemas de ponto a ponto complexos.

[0074] Tendo descrito a concretização preferida, se tomará aparente que várias modificações podem ser feitas sem partir da extensão da invenção como definida nas reivindicações acompanhantes.

Petição 870170064787, de 31/08/2017, pág. 30/38

1/7

Claims

REIVINDICAÇÕES

1. Método para determinar um trajeto para um veículo, o método incluindo:

definir um ponto de partida (404) para o veículo; definir um ponto de terminação (402) para o veículo; detectar um ou mais obstáculos (406) em uma área de trabalho (400) entre o ponto de partida (404) e o ponto de terminação (402);

definir uma zona de folga de obstáculo (409) sobre cada qual obstáculo (406) correspondente;

identificar trajetos candidatos (408,410) entre o ponto de partida (404) e o ponto de terminação (402);

estimar um custo econômico para cruzar cada trajeto candidato (408,410) ou uma porção do mesmo entre o ponto de partida (404) e o ponto de terminação (402); e selecionar um trajeto preferencial (410) dos trajetos candidatos identificados (408,410) com base no referido trajeto preferencial (410) que está associado com o custo econômico estimado mais baixo, caracterizado por:

descartar ou excluir trajetos candidatos (408, 410) se tal trajeto candidato (408) exceder um número máximo de toques predeterminados para uma zona de folga de obstáculo (409), de tal modo que cada um dos restantes trajetos candidatos identificados (408,410) intercepte, no máximo, cada zona de folga de obstáculo (409) o número predeterminado de vezes para cada obstáculo (406) correspondente, em que o número máximo de vezes é de um para um obstáculo geralmente convexo (406) e de um mais o número de concavidades de material associado com um obstáculo côncavo (406).
2. Método de acordo com a reivindicação 1, caracterizado pelo fato de que definir o ponto de partida (404) do veículo inclui definir o ponto de partida (404) e um rumo de partida do veículo; e, definir o ponto de terminação (402) inclui definir o ponto de terminação (402) e um rumo de terminação para o veículo.

Petição 870170064787, de 31/08/2017, pág. 31/38

2/7
3. Método de acordo com a reivindicação 1, caracterizado pelo fato de que o trajeto candidato identificado (410) inclui um trajeto do ponto de partida (404) ao ponto de terminação (402).
4. Método de acordo com a reivindicação 1, caracterizado pelo fato de que o trajeto candidato identificado (410) inclui um trajeto do ponto de partida (404) a um limite exterior da zona de folga de obstáculo (409) sobre um obstáculo (406) correspondente.
5. Método de acordo com a reivindicação 4, caracterizado pelo fato de que o trajeto candidato identificado (410) inclui um segmento de trajeto que se estende ao longo de uma porção do limite exterior da zona de folga de obstáculo (409).
6. Método de acordo com a reivindicação 1, caracterizado pelo fato de que o trajeto candidato identificado (410) inclui um primeiro segmento de trajeto do ponto de partida (404) a uma primeira zona de folga de obstáculo (409) sobre um primeiro obstáculo (406) correspondente e um segundo segmento de trajeto interconectado ao primeiro segmento de trajeto, o segundo trajeto se estendendo da primeira zona de folga de obstáculo (409) a uma segunda zona de folga de obstáculo (409) sobre um segundo obstáculo (406) correspondente.
7. Método de acordo com a reivindicação 1, caracterizado pelo fato de o trajeto candidato identificado (410) incluir um segmento de trajeto de um primeiro limite exterior (413) associado com uma zona de folga de obstáculo (409) de um primeiro obstáculo (406) a um segundo limite exterior (413) associado com uma zona de folga de obstáculo (409) de um segundo obstáculo (406).
8. Método de acordo com a reivindicação 7, caracterizado pelo fato de que nós ou vértices dos trajetos candidatos (408,410) são determinados formando-se interconexões tangenciais com respeito ao primeiro bmite exterior (413) e ao segundo bmite exterior (413).
9. Método de acordo com a reivindicação 1, caracterizado pelo fato de que selecionar tal trajeto preferencial (410) inclui pesquisa dos trajetos candidatos (408, 410) ou porções dos trajetos candidatos (408, 410) de acordo

Petição 870170064787, de 31/08/2017, pág. 32/38 com pelo menos um dentre um algoritmo de pesquisa A* e um algoritmo de pesquisa A* limitado.
10. Método de acordo com a reivindicação 1, caracterizado pelo fato de que selecionar tal trajeto preferencial (410) inclui pesquisa dos trajetos candidatos (408, 410) ou porções dos trajetos candidatos (408, 410), depois de descartar primeiramente trajetos candidatos (408) ou segmentos de trajeto que excedem um número máximo de toques predeterminados com respeito a uma forma de fronteira exterior de uma área de trabalho.
11. Método de acordo com a reivindicação 1, caracterizado pelo fato de o limite exterior de um obstáculo (406) ser afastado do obstáculo (406), de tal modo que o veículo tenha uma folga física entre o veículo e o obstáculo (406) se o veículo seguir um segmento de trajeto (410) que se estende ao longo do limite exterior.
12. Método de acordo com a reivindicação 1, caracterizado pelo fato de a zona de folga de obstáculo (409) incluir uma forma geralmente elíptica ou geralmente circular.
13. Método de acordo com a reivindicação 1, caracterizado pelo fato de que tal zona de folga de obstáculo (409) inclui uma forma geralmente retangular para reduzir recursos computacionais.
14. Método de acordo com a reivindicação 1, caracterizado pelo fato de incluir adicionalmente:

filtrar os trajetos candidatos identificados (408,410) com base em pelo menos uma de uma estimativa de desempenho de referência de um trajeto linear geralmente direto entre o ponto de partida (404) e o ponto de terminação (402).
15. Método de acordo com a reivindicação 1, caracterizado pelo fato de incluir adicionalmente:

filtrar os trajetos candidatos identificados (408,410) para excluir pelo menos uma porção rejeitada dos trajetos candidatos identificados (408) de um processo de pesquisa se tal trajeto candidato rejeitado (408) tiver pelo menos

Petição 870170064787, de 31/08/2017, pág. 33/38

ΜΊ uma de uma estimativa de custo de trajeto total, uma estimativa de duração de trajeto total, e uma estimativa de comprimento de trajeto total que excede uma estimativa de referência de trajeto correspondente, por mais do que um limiar máximo, associado com um trajeto linear geralmente direto entre o ponto de partida (404) e o ponto de terminação (402).
16. Planejador de trajeto (10) para determinar um trajeto para um veículo, o planejador de trajeto (10) sendo para realizar o método como definido em qualquer uma das reivindicações 1 a 15, incluindo:

um receptor determinador de localização (26) configurado para definir um ponto de partida (404) para o veículo;

um dispositivo definidor (12) configurado para definir um ponto de terminação (402) para o veículo;

um detector de obstáculo (14) configurado para detectar um ou mais obstáculos (406) numa área de trabalho entre o ponto de partida (404) e o ponto de terminação (402);

um modelador de obstáculo (16) configurado para definir uma zona de folga de obstáculo (409) sobre cada obstáculo (406) correspondente;

um anabsador (18) configurado para identificar trajetos candidatos (408,410) entre o ponto de partida (404) e o ponto de terminação (402);

um estimador (20) configurado para estimar um custo econômico para cruzar cada trajeto candidato (408, 410) ou uma porção do mesmo entre o ponto de partida (404) e o ponto de terminação (402); e um maquinário de pesquisa (22) configurado para selecionar um trajeto preferencial (410) dos trajetos candidatos identificados (408, 410) com base no trajeto preferencial (410) que está associado com o custo econômico estimado mais baixo, caracterizado por:

um filtro configurado para descartar ou excluir trajetos candidatos (408, 410) se tal trajeto candidato (408) exceder um número máximo de toques predeterminados para uma zona de folga de obstáculo (409), de tal maneira que cada um dos restantes trajetos candidatos identificados (408, 410) intercepte,

Petição 870170064787, de 31/08/2017, pág. 34/38 no máximo, cada zona de folga de obstáculo (409) um número predeterminado de vezes para cada obstáculo (406) correspondente, em que o número máximo de vezes é de um para um obstáculo geralmente convexo (406) e de um mais o número de concavidades de material associado com um obstáculo côncavo (406).
17. Planejador de trajeto (10) de acordo com a reivindicação 16, caracterizado pelo fato de que o dito receptor determinador de locabzação (26) é configurado para determinar o ponto de partida (404) e um rumo de partida correspondente do veículo; e o dito dispositivo definidor (12) é configurado para definir o ponto de terminação (402) e um rumo de terminação correspondente para o veículo.
18. Planejador de trajeto (10) de acordo com a reivindicação 16, caracterizado pelo fato de que o analisador (18) é configurado para identificar um trajeto candidato (408, 410) que inclui uma porção de trajeto do ponto de partida (404) ao ponto de terminação (402).
19. Planejador de trajeto (10) de acordo com a reivindicação 16, caracterizado pelo fato de que o anabsador (18) é configurado para identificar um trajeto candidato (408, 410) que inclui uma porção de trajeto do ponto de partida (404) até um limite exterior (413) da zona de folga de obstáculo (409) sobre um obstáculo (406) correspondente.
20. Planejador de trajeto (10) de acordo com a reivindicação 16, caracterizado pelo fato de que o anabsador (18) é configurado para identificar uma porção de trajeto candidato que inclui um primeiro segmento de trajeto do ponto de partida (404) até uma primeira zona de folga de obstáculo (409) sobre um primeiro obstáculo correspondente (406) e um segundo segmento de trajeto interconectado ao primeiro segmento de trajeto, o segundo segmento de trajeto se estendendo da primeira zona de folga de obstáculo (409) até uma segunda zona de folga de obstáculo (409) sobre um segundo obstáculo correspondente (406).
21. Planejador de trajeto (10) de acordo com a reivindicação 16,

Petição 870170064787, de 31/08/2017, pág. 35/38

6/7 caracterizado pelo fato de que o analisador (18) é configurado para identificar uma porção de trajeto candidato compreendendo um segmento de trajeto de um primeiro limite exterior (413) associado com uma zona de folga de obstáculo (409) de um primeiro obstáculo (406) para um segundo limite exterior (413) associado com uma zona de folga de obstáculo (409) de um segundo obstáculo (406).
22. Planejador de trajeto (10) de acordo com a reivindicação 21, caracterizado pelo fato de que o analisador (18) é configurado para determinar nós ou vértices dos trajetos candidatos (408, 410) formando-se interconexões tangenciais com respeito ao primeiro limite exterior (413) e ao segundo limite exterior (413).
23. Planejador de trajeto (10) de acordo com a reivindicação 16, caracterizado pelo fato de que tal maquinário de pesquisa (22) é adaptado para pesquisar os trajetos candidatos (408, 410) ou porções dos trajetos candidatos (408, 410) de acordo com pelo menos um dentre um algoritmo de pesquisa A* e um algoritmo de pesquisa A* limitado.
24. Planejador de trajeto (10) de acordo com a reivindicação 16, caracterizado pelo fato de que tal filtro é configurado para descartar ou excluir trajetos candidatos (408, 410) a partir de um processo de pesquisa se tal trajeto candidato (408) exceder um número máximo de toques predeterminados para uma forma de fronteira externa de uma área de trabalho.
25. Planejador de trajeto (10) de acordo com a reivindicação 16, caracterizado pelo fato de que tal filtro é configurado para descartar ou excluir trajetos candidatos (408, 410) a partir de um processo de pesquisa se tal trajeto candidato (408, 410) tiver pelo menos uma dentre uma estimativa de custo de trajeto total, uma estimativa de duração de trajeto total, e uma estimativa de comprimento de trajeto total que excede uma estimativa de referência de trajeto correspondente, por mais do que um limiar máximo, associado com um trajeto bnear geralmente direto entre o ponto de partida (404) e o ponto de terminação (402).

Petição 870170064787, de 31/08/2017, pág. 36/38

7/7
26. Planejador de trajeto (10) de acordo com a reivindicação 16, caracterizado pelo fato de que o modelador de obstáculo (16) é configurado para modelar o bmite de obstáculo de tal maneira que o dito bmite de obstáculo seja afastado do obstáculo (406) para prover uma folga física entre o veículo e o dito obstáculo (406) se o veículo seguir um trajeto associado com um vértice ou nó no bmite de obstáculo.
27. Planejador de trajeto (10) de acordo com a reivindicação 16, caracterizado pelo fato de que o modelador de obstáculo (16) é configurado para modelar um bmite exterior (413) associado com um obstáculo (406) como pelo menos um de geralmente elíptico, geralmente circular, e geralmente retangular.

Petição 870170064787, de 31/08/2017, pág. 37/38

1/7