figura A: mapeamento trapezoidal após a linha 2 do algoritmo

figura B: mapeamento após a linha 3 do algoritmo (remoção de trapezóides no interior dos polígonos).

A linha 2 do algoritmo leva tempo O(n log n). Para maior aprofundamento no assunto, ver em [1], catp 6. Na linha 3, para remover os trapezóides que estão no interior dos polígonos que representam os obstáculos, levamos tempo constante, uma vez que, para isso, basta achar a aresta associada a cada trapezóide, utilizando a estrutura t(E) devolvida pelo algoritmo de trapezoidalização.

Para saber se devemos retirar ou não um trapezóide, é suficiente verificar se as arestas associadas ao obstáculo estão abaixo ou acima dele. Mas as arestas dos obstáculos são listadas em ordem, seguindo a estrutura t(E).

O algoritmo EspaçosLivres leva tempo O(n log n) para ser executado, onde n é o número de arestas dos obstáculos.

A primeira parte é o mapeamento trapezoidal do espaço livre: t (Cfree). Tendo isto, vamos construir o mapa de caminhos Groad. Assim, já estaremos falando em encontrar um caminho entre um ponto origem e um ponto destino.

Para obter este mapa, fazemos o seguinte: achamos o centro de cada trapezóide e o marcamos com um ponto. Também colocamos um ponto no meio de cada extensão vertical (ver desenho).

Este mapa pode ser construído em tempo O(n), utilizando a estrutura t (Cfree).

Podemos ir de um nó no centro de um trapezóide para outro nó no centro de outro trapezóide vizinho através de um ponto no limite da extensão vertical que os separa.

Para determinar o caminho entre Porigem e Pdestino, fazemos o seguinte: primeiramente, achamos os trapezóides onde estão Porigem e Pdestino. Estes são indicados por D origem e D destino, respectivamente. Se D origem = D destino, ou seja, a origem e o destino estão no mesmo trapezóide, então basta-nos movermos de Porigem para Pdestino por uma linha reta entre eles. Se não estiverem no mesmo trapezóide, devemos achar Vorigem e Vdestino, que são o centro de D origem e D destino, respectivamente. Assim, dividimos o nosso problema em três partes: encontrar um caminho de Porigem a Vorigem (como estão no mesmo trapezóide, é só traçar uma linha reta entre eles); encontrar (no Groad), o caminho entre Vorigem e Vdestino e encontrar o caminho entre Vdestino e Pdestino (linha reta).

Segue o algoritmo:

Entrada: mapa trapezoidal t (Cfree) do espaço livre, o mapa de caminhos Groad, Porigem e Pdestino.

Saída: um caminho entre Porigem e Pdestino, se existir. Se não existir, relata o fato.

1. Achar os trapezóides D origem e D destino, que contém Porigem e Pdestino respectivamente.
2. Se D origem ou D destino não existem
3. Então relata o fato
4. Senão Ache Vorigem, nó de D origem em Groad
5.           Ache Vdestino, nó de D destino em Groad
6. Trace o caminho, na Groad, de Vorigem a Vdestino, usando o algoritmo de busca em largura
7. Se não há caminho
8. Então relate o fato (não há caminho entre Porigem e Pdestino)
9. Senão ache o caminho entre Porigem até Vorigem
10.           Junte este caminho com o caminho encontrado na linha 6
11.           Ache o caminho entre Vdestino e Pdestino

• Como garantimos que o caminho retornado pelo algoritmo não colide com os obstáculos?

Para provar que não há colisões, é simples: como estamos lidando com o mapa trapezoidal do espaço livre, para onde quer que caminhemos na estrutura, sabemos que, se o caminho é possível, o mesmo está no espaço livre, ou seja, NÃO vai colidir com nenhum obstáculo.

• É garantido que sempre o algoritmo consegue achar um caminho entre Porigem e Pdestino, se existir?

Suponha que há um caminho entre Porigem e Pdestino. Estes pontos pertencem ao trapezóide do espaço livre, portanto, resta-nos provar que há um caminho em Groad entre Vorigem e Vdestino

O caminho de Porigem a Pdestino deve passar por uma sequência de trapezóides D i = D 2, D 3,…, D k = D destino, onde Vi é o vértice de Groad que está no centro do trapezóide D i. Se o caminho passa de D i para D i+1, então estes são vizinhos e, portanto, dividem uma extensão vertical. Mas Groad é contruída tendo como base que os nós dos trapezóides são conectados por um vértice que está no limite. Assim, EXISTE um caminho em Groad de Vi para Vi+1. Podemos aplicar o mesmo raciocínio de V1 até Vk. Assim, garantimos que a busca em largura, certamente, encontrará um caminho de Vorigem a Vdestino, se existir…

Achar os trapezóides de Porigem a Pdestino leva tempo O(log n), usando a estrutura t (E). Alternativamente, poderíamos buscar um a um na estrutura, de modo que leva tempo linear, o que não vai fazer diferença no final das contas.

A busca em largura leva tempo linear em Groad, que tem um vértice por trapezóide, mais um vértice por extensão vertical. Tanto o número de trapezóides quanto o de extensões são lineares no número total de vértices dos obstáculos. Assim, o tempo gasto é O(n).

O tempo para indicar (imprimir) o caminho está associado ao número máximo de arcos no caminho, que é O(n).

• Pré-processamento: mapeamento trapezoidal [O(n log n)]
• Achar D origem e D destino [O(log n)]
• Busca em largura [O(n)]
• Impressão dos resultados [O(n)]

Na parte anterior, estudamos o movimento de um robô puntiforme. Agora, vamos tratar o robô como sendo um polígono. Vamos assumir que o robô R é convexo, assim como os obstáculos são. O espaço de configuração do obstáculo (C-obstáculo) P e o robô R são o conjunto de pontos no espaço de configuração que corresponde à localização em que R intersecta P. Notação: denotamos o C-obstáculo de P por Cp.

Cp := { (x,y) : R(x,y) ∩ P ¹ Æ }

Pode-se visualizar o formato de Cp deslizando R ao redor dos limites de P. Podemos descrever (expressar) os C-obstáculos abaixo:

S1 Å S2 := { p + q: p Î S1, q Î S2}; p = (px, py) e q = (qx, qy) Þ p + q = (px + qx, py + qy}

A soma de Minkovski aplica-se à modelagem porque polígonos são planares.

Outras definições:

1. p = (px, py)
2. –p = (-px, -py)
3. " S, -S := {-p: p Î S}

Defina R, robô translacional, polígono e defina P como obstáculo. O C-obstáculo de P é P Å (-R(0,0)).

Temos de provar que R(x,y) intersecta P Û (x,y) Î P Å (-R(0,0)).

(Þ ) Suponha que R(x,y) intersecta P.

Defina q = (qx, qy) ponto de R ∩ P Þ q Î R(x,y) E q Î P.

Assim, como q Î R(x,y), temos que (qx – x, qy – y) Î R(0,0) Þ (-qx + x, -qy + y) Î -R(0,0).

Como q Î P Þ (x,y) Î P Å (-R(0,0)).

(Ü ) Defina (x,y) Î P Å (-R(0,0)).

Então há pontos (rx, ry) Î R(0,0) e (px, py) Î P tais que (x,y) = (px – rx, py – ry), ou seja, px = rx + x e py = ry + y, implicando que R(x,y) intersecta P. CQD ■

• P e R são 2 ‘objetos’ no plano.

Cp := P Å R. Um ponto extremo na direção d de Cp é a soma dos pontos extremos, na direção d, de P e R.

P e R polígonos convexos com n e m arestas, respectivamente. Então, P Å R é um polígono convexo com pelo menos n + m arestas.

A convexidade segue diretamente da definição.

Verificando o número de arestas: considere uma aresta extrema e de P Å R. Deve ser gerada por pontos em P e R que são extremos na mesma direção. Ademais, pelo menos P ou R devem ter uma aresta extrema naquela direção. Vamos chamá-la de e. Desta forma, cada aresta é associada a pelo menos uma (de P ou R), de modo que o número total de arestas é pelo menor n + m. Se P e R não tiverem arestas paralelas, esse número é exatamente n + m.

Assim: a soma de Minkovski de 2 polígonos convexos é convexa e tem complexidade linear.

Vamos escrever, abaixo, o algoritmo de soma de Minkovski. Um algoritmo é: " para (v,w) de vértices, v Î P e w Î R, execute v + w. Após, execute o fecho convexo de todas essas somas. Este algoritmo é ineficiente quando o polígono tem muitos vértices, porque o algoritmo olha para todo par de vértices.

Um algoritmo alternativo: olha somente a pares de vértices que são extremos na mesma direção. No algoritmo, usaremos a notação ângulo(pq) para denotar o ângulo pq com o eixo x.

Entrada: polígonos convexos: P com vértices v1,…, vn

Q com vértices w1,…, wn

Vértices ordenados no sentido horário, com v1 e w1 sendo os vértices com menor y-coordenada.

Saída: soma de Minkovski P Å R.

1. i ¬ 1; j ¬ 1
2. v(n+1) ¬ v(1); w(n+1) ¬ w(1)
3. enquanto (i = n + 1) AND (j = m + 1) faça
4.                acrescente v(i) + w(j) como vértice de P Å R
5.                se ângulo(v(i), v(i+1)) < ângulo(w(j), w(j+1))
6.                então i ¬ i + 1
7.                senão se ângulo(v(i), v(i+1)) > ângulo(w(j), w(j+1))
8.                          então j ¬ j + 1
9.                          senão i ¬ i + 1; j ¬ j + 1

Como a prova do teorema 3, qualquer vértice da soma de Minkovski é a soma de 2 vértices originais com extremos numa direção comum. Os testes de ângulos do algoritmo asseguram que todos os pares extremos são encontrados.

A soma de Minkovski de 2 polígonos convexos com n e m vértices, respectivamente, pode ser executada em tempo O(n + m).

Até agora, só estudamos a soma de Minkovski para polígonos convexos. A partir daqui, vamos considerar polígonos não-convexos. Para tanto, vamos trabalhar com a seguinte propriedade, para S1, S2 e S3:

S1 Å (S2 U S3) = (S1 Å S2) U (S1 Å S3)

Vamos considerar, agora, a soma de Minkovski entre um polígono não-convexo P com n vértices e um polígono convexo R com m vértices.

Sabemos que P pode ser triangularizado com n – 2 triângulos t1,…, tn-2.

Da equação acima, temos que: P Å R = U ti Å R (para i = 1,..., n-2).

Se ti é triângulo e R é polígono convexo com m vértices, sabemos que ti Å R é um polígono convexo com pelo menos m + 3 vértices. Ademais, os triângulos são disjuntos. Consequentemente, a complexidade desta união (dos triângulos) é linear na soma das complexidades, ou seja, P Å R é O(nm).

Com dois polígonos NÃO-CONVEXOS, basta triangularizarmos P com n vértices e R com m vértices em (n-2) triângulos ti e (m-2) triângulos uj. A soma de Minkovski de P e R é a união das somas de Minkovski dos pares ti uj. Cada soma ti Å uj tem O(1). Como temos a união de (n-2) com (m-2) componentes, a complexidade de tempo no pior caso é O(n * n + m * m).

Defina P e R polígonos com n e m vértices, respectivamente.

A complexidade da soma de Minkovski P Å R é:

• O(n + m) se os dois polígonos são convexos;
• O(nm) se um deles é convexo e o outro é não-convexo;

• O(n * n + m * m) se ambos são não-convexos.

Vamos relembrar que um C-obstáculo corresponde à soma de Minkovski de um obstáculo Pi Å (-R).

Um par o1, o2 de objetos planares formam um par de pseudodiscos se satisfaz à propriedade:

• o1 – o2 e o2 – o1 são convexos.

Exemplo:

Para qualquer par de pseudodiscos, há pelo menos 2 intersecções próprias entre as fronteiras.

Vamos provar que uma coleção de somas de Minkovski formam uma coleção de pseudodiscos.

Obs. 4: Defina P1 e P2 polígonos convexos com interiores disjuntos. Defina d1 e d2 direções nas quais P1 é mais extremo que P2. Então, P1 é mais extremo que P2 nas direções do intervalo [d1, d2] ou nas direções do intervalo [d2, d1].

Defina P1 e P2 polígonos convexos com interiores disjuntos e defina R, outro polígono convexo. Então as 2 somas de Minkovski P1 Å R e P2 Å R são psedodiscos.

Cp1 := P1 Å R e Cp2 := P2 Å R

Por simetria, é suficiente mostrar que Cp1 – Cp2 é conexo.

Como Cp1 e Cp2 são convexos, um componente conexo de Cp1 – Cp2 deve conter um ponto no fecho convexo de Cp1 U Cp2. Se há mais do que um componente conexo, então deve haver 2 direções d1 e d2 tais que Cp1 é mais extremo nestas direções do que Cp2.

Obs. 5: Define P e R dois objetos no plano, Cp := P Å R. Um ponto extremo na direção d de Cp é a soma dos pontos extremos na direção d de P e R.

Desta obs 5, segue que P1 é mais extremo que P2 nestas 2 direções.

Da obs anterior (obs4), P1 é mais extremo que P2 nas direções do intervalo [d1, d2 ] ou nas direções do intervalo [d2, d1 ].

Utilizando a obs5 acima, o conjunto de direções para as quais os pontos extremos em Cp1 estão mais afora que Cp2 é conexo, contradizendo nossas hipóteses que há 2 componentes conexos.

Define S como uma coleção de pseudodiscos poligonais com n arestas ao total. A complexidade da união deles é O(n).

Vamos provar que todo vértice da união dos pseudodiscos é verificado ao máximo 2 vezes. Complexidade 2n, ou seja, O(n).

Há dois tipos de vértices a serem verificados: vértices do pseudodisco e intersecção de arestas dos pseudodiscos.

Pontos (vértices) de intersecção: considere vértice v da união, que é intersecção da aresta e de um pseudodisco P Î S e outra aresta e’, de P’ Î S. Imagine que estas arestas entram em outro pseudodisco e se encontram em v. Siga e até o interior de P’. Se ele termina no interior, então verificamos v até o final de e, no interior de P’. O ponto onde isto acontece é a intersecção dos limites de P e P’. Junto com v, faz 2 pontos de intersecção, de modo que e’ não deixa o interior de P sem violar a propriedade dos pseudodiscos. Consequentemente, e’ tem um vértice dentro de P, tendo sido verificado o vértice v.

Neste raciocínio, cada vértice do pseudodisco é verificado 2 vezes.

Para os vértices no limite: verificação é trivial.

Defina R um robô convexo de complexidade constante, translade-o sobre um conjunto S de obstáculos poligonais que não se intersectam, com um total de n arestas. A complexidade para achar o espaço de configuração livre (Cfree(R,S)) é O(n).

Triangularize cada polígono que é obstáculo. Obteremos O(n) triangulos convexos, obstáculos com interiores disjuntos. O espaço de configuração livre é o complemento da união dos C-obstáculos desses triângulos. Como o robô tem complexidade constante, os C-obstáculos têm complexidade constante, de acordo com o teorema 8. Assim, o teorema 9 implica que a união tem complexidade O(n).

Vamos mostrar um algoritmo que encontra os espaços ocupados. O espaço livre é o complemento deste conjunto.

Devemos lembrar que: Cforb = U Cpi = U Pi Å (-R(0,0)) para i = 1,..., n

Entrada: coleção de C-obstáculos

Saída: espaços ocupados Cforb = U Cpi (para i = 1,..., n)

1. se n = 1
2.     então retorne Cp1
3.     senão Cforb(1) ¬ EspaçoOcupado(P1,…,P(é n/2ù )
4.               Cforb(2) ¬ EspaçoOcupado(pé n/2ù +1,…,Pn)
5.               Execute Cforb = Cforb(1) U Cforb(2)
6. retorne Cforb

LEMA: O espaço de configuração livre de um robô convexo de complexidade constante, transladando sobre um conjunto S de polígonos com n arestas ao total pode ser executado em tempo O(n log n).

Tempo para triangularização de um polígono com m vértices: O (m log m)

mi é a complexidade do obstáculo Pi.

S mi log mi <= S mi log n = n log n (para i = 1,..., t)

A linha 5 do algoritmo leva tempo O(n log n).

Como trata-se de um algoritmo de divisão e conquista, então a recorrência é:

T(n) = T(é n/2ù ) + T(ë n/2û ) + O(n log n)

Assim, a solução da recorrência é O(n log log n).

Este resultado NÃO é o melhor possível (não é ótimo).

Para termos o caminho entre um ponto Porigem e seu Pdestino, basta seguirmos como feito na seção anterior (para robô puntiforme). Definimos o mapa trapezoidal Groad, etc….

Defina R robô convexo de complexidade constante transladando sobre um conjunto S de obstáculos poligonais disjuntos com n arestas ao total. Um pré-processamento leva tempo O(n log log n) e o caminho entre um Porigem até Pdestino, se existir, pode ser obtido em tempo linear.

Mesmo modelo: R é robô polígono convexo, que pode sofrer translação e rotação num espaço planar com P1,…,Pt obstáculos poligonais disjuntos.

Agora, R tem 3 graus de liberdade: R x R x [0:360) ® R(x, y, f ).

Assim: Cpi := {(x, y, f ) Î R x R x [0:360) : R(x, y, f ) Ç Pi ¹ Æ }

No plano com ângulo de rotação fixado, f = f0, a forma de secção cruzada é uma soma de Minkovski. Mais precisamente, uma secção cruzada de Cpi com o plano h: f = f 0 é:

Pi Å R(0, 0, f 0) Þ soma de Minkovski na altura f 0.

Agora imagine uma varredura num plano horizontal do espaço de configuração, começando em f = 0 até f = 360º. Em qualquer momento, a secção cruzada da varredura do plano com Cpi é uma soma de Minkovski.

A forma destas somas de Minkovski mudam continuamente, desde f = f 0, onde a secção cruzada é Pi Å R(0, 0, f 0) até f = f 0 + e , onde a secção é Pi Å R(0, 0, f 0 + e ). Isto significa que Cpi parece um pilar torcido. As arestas e faces deste pilar torcido, exceto no topo e na base, são curvas.

Nossa tática de construir o mapa de estradas e dividir o percurso de Porigem e Pdestino em partes, continuará a ser utilizada.

No entanto, vamos mudar nossa modelagem. Como falamos há pouco, cada secção cruzada vai se chamar fatia. A idéia é trabalhar com um número finito de fatias.

Um caminho do robô agora consiste de 2 tipos de deslocamento: dentro da fatia – que é um deslocamento puramente translacional – e de uma fatia para outra – que implica deslocamento rotacional.

Uma fatia é uma secção cruzada – plano.

Formalizando:

z é o número de fatias

" i Î N, 0 <= i <= Z, f i = i x (360 / z)

Executaremos uma fatia do espaço livre para cada f i.

Então, dentro de uma fatia, estaremos falando de deslocamento translacionais para o robô R(0, 0, f i) e usamos os métodos estudados até agora. Isto nos dará um mapa trapezoidal t i do espaço livre desta fatia. E para cada t i, teremos um mapa de estradas Gi.

Movimento entre fatias: conectamos os mapas de estradas Gi, Gi+1 para obter o mapa de estradas geral Groad do espaço de configuração inteiro. Quando adicionamos um nó extra para Groad em (x, y, f i) e em (x, y, f i+1), estão conectados por um arco. O movimento de uma fatia para outra é um movimento de rotação de f i para f i+1.

Assim, utilizaremos a seguinte técnica para achar um caminho de R(Xorigem, Yorigem, f origem) para R(Xdest, Ydest, f dest):

1. determinar as fatias para Rorigem e Rdest
2. dentro das fatias, achar os trapezóides D origem e D dest.

Se um destes trapezóides não existir (porque podem estar no espaço ocupado), relatamos o fato.

3. definir Vorigem e Vdest nos mapas de estradas respectivos.
4. Tentar achar o caminho em Groad de Vorigem até Vdest usando busca em largura. Se não há caminho, relatar o fato.

Assim, temos agora o caminho consistindo de 5 partes:

• movimento rotacional da posição origem para a fatia mais próxima definida.
• Movimento translacional dentro da projeção do ponto na fatia até o ponto Vorigem.
• Deslocamento em Groad de Vorigem a Vdest usando busca em largura.
• Movimento translacional de Vdest até a projeção do destino na fatia final.
• Movimento rotacional até a posição destino.

Este algoritmo NEM SEMPRE está correto. Algumas vezes, pode relatar erroneamente que um caminho não existe. Por exemplo: a posição inicial pode estar no espaço livre, mas a posição inicial projetada na fatia mais próxima não está num espaço livre. Neste caso, relatamos que há um caminho, quando na verdade não há.

Livre de colisão: nos movimentos rotacionais (de uma fatia para outra) pode haver problemas: as localizações dentro das 2 fatias podem ser livres de colisão. No entanto, neste caminho entre as duas fatias, pode haver colisão. Ambos os problemas são menos prováveis de ocorrer à medida que aumenta-se o número de fatias, porém nunca teremos certeza da corretude do resultado.

Para evitar estes problemas, podemos usar um truque. Fazemos o robô levemente mais largo e utilizamos o método descrito para o robô alargado R’. Embora R’ possa colidir durante as rotações, o robô original R não colide.

O ‘alargamento’ do robô é feito da seguinte maneira: rotacione o robô R nos sentidos horário e anti-horário num ângulo de (180º / z).

Utilizamos R’, ao invés de R, no algoritmo acime, nos mapas trapezoidais e mapas de estradas. Veja figura:

Esta técnica, com um grande número de fatias, na prática funciona muito bem.

O problema do deslocamento de robôs tem sido alvo de muitas pesquisas e estudos. Em alguns livros, pode-se encontrar uma literatura muito mais elaborada do que o que foi visto aqui. Em J.C. Latombe, Robot Motion Planning, Kluwer Academic Publishers, Boston ’91 há estudos mais intensivos.

[1] Computational Geometry
Algorithms and Applications
M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf
Springer
Capt 13 – Robot Motion Planning – páginas 265 a 288