Navegação e Controle
de Robôs Móveis
PLANEJAMENTO DE
CAMINHOS
Paradigmas Robóticos
Deliberativo.
 Reativo.
 Híbrido Deliberativo/Reativo

Primitivas
Primitiva
Percepção
Entrada
Dados
sensoriais
Saída
Informação
percebida
Planejamento Informação
percebida
Diretivas
Ação
Comandos
para atuadores
Informação
percebida ou
Diretivas
Paradigma Deliberativo
Perceber
Planejar
Primitiva
Entrada
Agir
Saída
Percepção
Dados sensoriais
Informação
percebida
Planejamento
Informação
percebida
Diretivas
Ação
Informação
percebida ou
Diretivas
Comandos para
atuadores
Paradigma Reativo
Perceber
Primitiva
Agir
Entrada
Saída
Percepção
Dados sensoriais
Informação
percebida
Planejamento
Informação
percebida
Diretivas
Ação
Informação
percebida
Diretivas
Comandos para
atuadores
Paradigma Híbrido
Planejar
Perceber
Primitiva
Agir
Entrada
Saída
Planejamento
Informação
percebida
Diretivas
Percepção-Ação
(Comportamentos)
Dados sensoriais
Comandos para
atuadores
O Problema do Carregador de Piano
Como levar um piano no interior de um
edifício,
através
de
corredores
povoados de obstáculos, até a sua
localização final dentro do prédio?
 Piano = corpo rígido móvel.
 Obstáculos = corpos rígidos fixos.
 Localização = posição e orientação.

Movimento de um robô A no Espaço de
Trabalho W com obstáculos Bi's. 
 Movimento de um ponto no Espaço de
Configuração C com C-obstáculos CBi's.

W
C
A
CB1
B1
CB1
B2
Configuração q

Especificação da Posição e Orientação
do robô. Exemplo: q = [x y ]T.
yW
yA
xA
y

x
xW
Espaço de Configuração C é o conjunto
de todas as possíveis configurações do
robô.
 Espaço de Configuração Livre CL é o
conjunto de todas as possíveis
configurações em que o robô não colide
com os obstáculos Bi’s.

W
CL
Obstáculo em Espaço de
Configuração - CB
Um obstáculo B no espaço de trabalho
W pode ser representado de forma
equivalente por um C-obstáculo CB no
espaço de configuração C.
 O C-Obstáculo é o conjunto de todas as
configurações em que o robô se
superpõe ao obstáculo.


Exemplo: C-obstáculo em espaço
poligonal, robô com orientação fixa .
CB = {PW/  b  B,  a0  A(0): P = b - a0}
CB
B
A
 = 0
CB
B
C-Obstáculo para q = (x,y,)

CB = união de infinitas fatias poligonais.
 Os limites de CB são as faces, (retalhos de
C-Superfícies), correspondentes a contatos
do tipo A ou do tipo B:
  Contato tipo A (eixo do robô e vértice do
obstáculo)  Face = retalho de helicóide
(gerada por uma reta em translação-rotação).
  Contato tipo B (eixo do obstáculo e vértice
do robô)  Face = retalho de plano (gerado
por uma reta em translação).

CB
0
y
x
CB(0)
MAPA DE ROTAS
Princípio: Capturar a conectividade
do espaço de configuração livre na
forma de uma rede de curvas R, (Mapa
de Rotas), que é usada como um
conjunto de caminhos padrão.
 O planejamento se reduz a buscar um
caminho em R entre qini e qfin.

Grafo de Visibilidade
Aplicável a W = R2, robô A poligonal e
com orientação fixa e obstáculos Bi
poligonais.
 Princípio: construir um caminho entre
qini e qfin formado por uma linha
poligonal através dos vértices de CB.


Grafo de Visibilidade é um grafo não
direcional, G, tal que:
  Os Nós de G são qini, qfin e vértices de CB.
  Dois nós são conexos por um arco se e
somente se o segmento que os une é um
eixo de CB ou está contido inteiramente no
espaço livre.

Propriedade: O Grafo de Visibilidade contém
o caminho mais curto entre qini e qfin.
qini
qfin
Algoritmo de Planejamento:
i. Construir o Grafo G.
 ii. Buscar um caminho de qini até qfin em G.
 iii. Se o caminho é encontrado, retorná-lo,

se não, reportar falha.

Construção do Grafo de Visibilidade:
Tomar pares (X, X’) de nós de G.
2. Se X e X’ são extremos do mesmo eixo em
CB, conectá-los por um arco.
3. Se X e X’ não são extremos do mesmo eixo
em CB, computar as interseções da linha
suporte de (X, X’) com CB. Caso não
acontecer nenhuma interseção em (X, X’),
ligar os nós por um arco em G.
1.
Busca do menor caminho

•
•
•
•
Exemplo: algoritmo de busca em grafos A*:
Aplicável a grafos em que os arcos têm
custos associados, por exemplo, distância
entre os nós.
Custo de um caminho = soma dos custos dos
seus arcos.
Distância ao alvo = função heurística para
guiar a busca.
Permite obter o menor caminho em termos
da métrica adotada.
Procedimento:
- G
explorado
iterativamente
seguindo
caminhos a partir do nó inicial Nini.
- Custo de cada nó N :
f(N) = g(N) + h(N).
- g(N) = custo do caminho entre Nini e N em T
corrente.
- h(N) = estimativa heurística do custo h*(N) do
caminho mínimo entre N e o nó final Nfin.
Para cada nó visitado, um ou mais caminhos
são gerados a partir de Nini, mas só o de
menor custo é memorizado.
- Os nós são armazenados numa lista L em
ordem crescente do seu custo f(N).
- Os caminhos gerados formam uma árvore T
do subconjunto de G já explorado.
-
Procedimento A*(G, Nini, Nfin, k, h);
INSERIR o nó inicial Nini na árvore T;
INSERIR Nini na lista L; marcar Nini como visitado;
enquanto a Lista não estiver VAZIA faça
N  primeiro Nó da Lista;
se N = Nfin, então sair do laço enquanto;
para cada nó N' adjacente a N em G, faça
se N' é não visitado, então
adicionar N' a T com um ponteiro para N;
INSERIR N‘ em L; marcar N' como visitado;
se não, se g(N') > g(N) + custo(N, N'), então
redirecionar o ponteiro de N' para N em T;
se N‘ está em L,então APAGAR N';
INSERIR(N',L);
fim;
se a Lista L não estiver VAZIA, então
retornar o caminho traçando os ponteiros de Nfin a Nini;
se não reportar falha;
fim;
N7fin
12
3
4
5
ini
N
qini
ini
4,0
4,0
N2
3,9
5,8
N4
2,5
N6
N1
5,8
3,9
N3
3,8
NNini ,,, 15,9+2,2
0+12,2
14,9+0
N
,
4,0+10,0
7,9+6,4
4,0+10,2
N34127fin
10,4+4,1
7,9+6,6
4 , 13,9+3,2
5
N
15,9+2,2
4,0+10,2
N
N534175 ,,,13,9+3,2
10,4+4,1
13,9+3,2
7,9+6,6
N
7,9+6,4
N45 ,, 13,9+3,2
6,3
6,0
N5
4,8 2,6
4,2
N7
3,2
2,2
Nqfin
fin