Early Holocene (11.65-7.0 cal. ka BP)

Uma das principais características do DP é que o caminho total é composto pela união de três curvas (semicírculos e retas). Conforme visto anteriormente, existem dois tipos de composições possíveis: a composição do tipo CCC, referente ao caminho do tipo curto; e a do tipo CLC, correspondente ao caminho do tipo longo.

Analisando esse aspecto do DP, é possível generalizar essa idéia para promover a cons- trução de uma trajetória pela união de três curvas quaisquer (que não simplesmente arcos e retas), de modo que a função de curvatura final apresentada seja contínua. Em outras pa- lavras, é possível unir três funções para gerar uma trajetória contínua entre dois waypoints. Essas funções devem, individualmente, respeitar as restrições consideradas para o problema. Assim sendo, tal trajetória pode ser representada por meio do conjunto B, composto por três funções [B1, B2, B3], onde cada função Bj apresenta uma função contínua de curvatura, e

valores equivalentes para κ(t) em suas duas extremidades.

Uma vantagem imediata proporcionada pela utilização desse conjunto é a continuidade em κ(t), não apenas de uma trajetória ~r(t) específica entre dois waypoints, mas também para a junção de diversas trajetórias que passam por diversos waypoints no plano. Além disso, espera-se que a curva total resultante apresente um comprimento relativamente próximo ao caminho ótimo, algo que é considerado fundamental nesse problema. Espera-se ainda que a determinação das funções do conjunto B possa ser realizada em tempo computacional finito. Um tipo de função que pode ser utilizada com essa finalidade é a curva de Bézier. Conforme visto anteriormente, a metodologia do HP apresenta funções contínuas de curvatura ao longo de toda a trajetória, porém as curvas geradas não exibem valores semelhantes para κ(t) em seus pontos extremos ~r(t)|t=0 e ~r(t)|t=1.

Uma propriedade bastante interessante das curvas de Bézier é que o vetor T tangente a curva ~r(t) no ponto inicial r(0) é sempre paralelo ao vetor −−−→p0p1 , formado pelos dois pontos

de controle iniciais. O mesmo é observado para o ponto final da curva r(1), cuja tangente é paralela ao vetor −−−−−→pn−1pn, formado pelos dois pontos de controle finais. Essa característica

waypoint na etapa de planejamento.

Outra propriedade que também pode ser bastante útil refere-se ao valor da curvatura nos pontos extremos de cada curva. Observando a Equação 3.4 é possível ver que a curvatura de uma função depende das derivadas parciais de primeira e segunda ordens da mesma. Conclui- se então que para a curva de Bézier, as curvaturas inicial e final dependem da configuração dos três pontos de controle mais extremos dessa curva ([p0, p1, p2] e [pn−2, pn−1, pn], respectiva-

mente). Matematicamente, a curvatura inicial de uma curva de Bézier pode ser determinada por meio da Equação 3.63 (Sederberg, 2007).

κ_(t)|t=0= (n − 1)

n

kp2− p1k

kp1− p0k

sin σ, (3.63) onde σ representa o ângulo formado entre os vetores −−−→p0p1 e −−−→p1p2. Se esse ângulo for propor-

cional à π por qualquer valor inteiro, maior ou igual a zero, então κ(0) será nulo. Se σ é nulo, então os vetores em questão são colineares com sentidos equivalentes. O mesmo raciocínio se estende para a curvatura κ(1), no outro extremo da curva.

Logo, é possível gerar uma curva de Bézier com valores inicial e final de curvatura nulos, por meio do alinhamento dos três pontos de controle mais próximos de cada extremidade da mesma. Uma vez que tais curvas apresentam funções contínuas em κ(t) com valores nulos nas extremidades, a união de duas ou mais curvas sempre produzirá trajetórias com funções de curvatura contínuas.

Tal suposição é válida apenas para polinômios cuja ordem é igual ou superior à cinco. Entretanto, a utilização de uma função de quinta ordem (como é o caso da Quintic Pythagorean Hodograph) limita em muito o projeto de curvas, já que os seis pontos de controle ficam restritos à condição de colinearidade. Por outro lado, a complexidade exigida no projeto de curvas de mais alta ordem fica reduzida, devido à mesma condição, de modo que se pode utilizar uma técnica bastante semelhante ao cálculo do HP para uma curva de Bézier de 7a

ordem, conforme apresentado na seqüência.

Para garantir que o conjunto B não constitua uma trajetória muito maior do que o caminho tridimensional de Dubins, tomemos esse como base para a construção das três curvas de Bézier. O primeiro passo é: dadas as poses inicial e final, calcular o DP, conforme apresentado na Expressão 3.64.

D = dubinspath(Pi, Pf, ksρmin), (3.64)

onde ks > 1 constitui um ganho que é acrescido de forma iterativa pelo algoritmo, com a

finalidade de restringir a curva à κmax.

Como já é sabido, D é composto por três curvas, onde a primeira e a terceira representam arcos de raio ksρmin. Utilizando a informação dessas duas curvas, será realizada na seqüência,

3.3. Planejamento Utilizando Curvas de Bézier de 7a _{Ordem 51}

P1 = Pi,

P2 =



ci(x) + ksρmincos ψb, ci(y) + ksρminsin ψb, ψb±

π 2  , P3 = 

cf(x) + ksρmincos ψc, cf(y) + ksρminsin ψc, ψc±

π 2

 ,

P4 = Pf,

onde [ci(x), ci(y)] e [cf(x), cf(y)] representam as coordenadas do centro da primeira e da

terceira curva de D, respectivamente (Equações 3.11 e 3.12), e ψbe ψc são os ângulos internos

observados na Figura 3.6. A redundância na determinação dos ângulos de cada pose pode ser resolvida em função do sentido da curvatura de cada curva, sendo que pela convenção adotada, curvas para a esquerda correspondem a sinais positivos.

A partir desse ponto é possível definir B como um conjunto de três curvas de Bézier de 7a _{ordem, onde a primeira curva define uma trajetória de P}

1 para P2, a segunda de P2 para

P3 e a última de P3 para P4. Assim sendo, dada uma das curvas do conjunto, unindo os

respectivos waypoints de partida Pa= [xa, ya, ψa] e de chegada Pb = [xb, yb, ψb] no plano, seis

de seus oito pontos de controle podem ser determinados a partir da Equação 3.65. p0 = [xa, ya], p1 = p0+ sj 2π[cos ψa,sin ψa], p2 = p1+ sj 2π[cos ψa,sin ψa], p5 = p6− sj 2π[cos ψb,sin ψb], p6 = p7− sj 2π[cos ψb,sin ψb], p7 = [xb, yb], (3.65)

onde a variável sj para j ∈ [1, 2, 3] representa o comprimento de uma das três curvas de D

correspondente a curva de B avaliada.

O problema é semelhante a geração do HP, restando dois pontos de controle a serem determinados (p3 e p4). Tais pontos podem ser calculados utilizando-se a Equação 3.66, a

qual constitui uma adaptação da metodologia apresentada em (Farouki e Neff, 1995). p3 = p2+ 1 5[u0u1− v0v1, u0v1+ u1v0] , p4 = p3+ 2 15u 2 1− v 2 1,2u1v1 + 1 15[u0u2− v0v2, u0v2+ u2v0] . (3.66)

Os parâmetros [u0, u1, u2] e [v0, v1, v2] representam os coeficientes dos polinômios u(t)

e v(t) respectivamente, utilizados no projeto do HP de quinta ordem (Shanmugavel et al., 2007). (u0, v0) = r 5 2  pk∆p1k + ∆x1, ∆y1 |∆y1|pk∆p 1k − ∆x1  . (3.67) (u2, v2) = ± r 5 2  pk∆p5k + ∆x5, ∆y5 |∆y5|pk∆p 5k − ∆x5  . (3.68) (u1, v1) = − 3 4[u0+ u2, v0+ v2] ± r 1 2  √ c+ a, b |b| √ c_{− a}  , (3.69) onde ∆xk = xk+1− xk, ∆yk= yk+1− yk, e ∆Pk= [∆xk,∆yk].

Já a, b e c podem ser determinados conforme a seguir: a = 9 16(u 2 0− v 2 0+ u 2 2− v 2 2) + 5 8(u0u2− v0v2) + 15 2 (x5− x2), b = 9 8(u0v0+ u2v2) + 5 8(u0v2+ v0u2) + 15 2 (y5− y2), c = √a2_{+ b}2_.

Assim como acontece no cálculo do HP, existem quatro possíveis soluções para a trajetória desejada, isso devido a redundâncias existentes nas Equações 3.68 e 3.69. Utiliza-se a Equação 3.33 para determinar a solução que apresenta o perfil da função de curvatura mais suave dentre todas possíveis.

Após o cálculo das três curvas do conjunto B, resta verificar se a função de curvatura da trajetória final não excede o valor permitido κmax. Uma vez que κ(t) tenha sido calculado no

passo anterior, a verificação é bastante simples. Caso essa condição não tenha sido alcançada, o valor de ks deve ser incrementado, e uma nova iteração do algoritmo é requisitada. Isso se

repete até que a curva respeite a restrição.

A Figura 3.17 apresenta uma comparação entre os resultados gerados por essa técnica e pelo DP, para um mesmo par de waypoints. A curva B foi gerada sobre um caminho ótimo do tipo CLC, apresentando um comprimento cerca de 10% maior do que o mínimo possível. O ganho disso pode ser visto na Figura 3.18, onde a função de curvatura apresenta um resultado contínuo e limitado pelo raio mínimo especificado.

3.3. Planejamento Utilizando Curvas de Bézier de 7a _{Ordem 53} X Y o DP Curvas de 7 ordem Pontos de controle

Figura 3.17: Resultado final baseado no caso do caminho longo de Dubins.

κ s o κ_max −κ_max DP Curvas de 7 ordem

Figura 3.18: Perfil de curvatura de Figura 3.17.

3.19. O resultado é importante, pois permite a realização de manobras do robô em peque- nas áreas e em curtas distâncias, ainda mantendo o perfil da função de curvatura contínua, conforme é mostrado na Figura 3.20.

Apesar do cálculo da trajetória nesse caso se dar de forma iterativa, como no caso do HP, a convergência do método tende a ser mais rápida (mesmo com o cálculo de três curvas), devido ao fato de B ser baseada em uma curva de Dubins. Além disso, sempre é possível encontrar uma trajetória, já que sempre existe um conjunto D para quaisquer dois waypoints especificados (Shkel e Lumelsky, 2001). Por fim, o comprimento da trajetória obtida é, em geral, próximo ao caminho ótimo, se comparado a alguns casos particulares do HP, já que se basea em DP com raios de curvatura ks vezes ρmin, onde ks é em geral inferior a 2.