Upload
fabian
View
30
Download
0
Embed Size (px)
DESCRIPTION
Busca Online. Alexandra Barros Geber Ramalho. Busca Offine x Busca Online. Busca Offline (ou planejamento clássico) Computa a solução (do estado inicial até o objetivo) para depois iniciar a seqüência de ações A partir de então as percepções são ignoradas - PowerPoint PPT Presentation
Citation preview
Busca Online
Alexandra Barros
Geber Ramalho
Busca Offine x Busca Online
Busca Offline (ou planejamento clássico)– Computa a solução (do estado inicial até o objetivo)
para depois iniciar a seqüência de ações– A partir de então as percepções são ignoradas– Domínios Determinísticos e Estáticos
Exemplo jogo dos n-números
Busca Online (e alguns planej. avançados)– Intercala planejamento e ação.
Executa uma ação, observa o ambiente e calcula a próxima ação.
– Domínios Estocásticos e DinâmicosExemplo: Ratinho tentando achar o caminho por um
labirinto, dirigir sem mapa,...
Busca online
Problemas exploratórios– Espaço de estados desconhecido
Ex. O agente não sabe que Up leva de 1,1 para 1,2 até ter feito isto (S = start e G = goal)
Agente de busca online
O que o agente sabe: Funções– Ações(s) - ações possíveis para um dado estado s– Testa-objetivo(s)– Custo(s,a,s’), onde a é uma ação
Observações– O agente não tem acesso prévio ao estado sucessor
s’ de s, nem ao valor do custo de ir de s para s’Em ambos os casos precisa agir antes...
– Vai memorizando/atualizando o espaço de busca (mapa)
Busca online
Observações (cont.) – Só pode expandir nós onde ele fisicamente se
encontra (ex. rota de cidade A para B)Adequado para busca em profundidade!
Assumi-se que – as ações são deterministas– o agente pode reconhecer estados já visitados
(memorizar)– existe uma função heurística admissível
Busca em Profundidade Online
Busca em profundidade– Coerente c/ “localidade” da expansão dos nós
Manter atualizado – um mapa das relações entre ações e estados [a,s]
=> s’ (Result)– para cada nó, uma lista das ações não executadas
Actions(s) (Unexplored)– para cada nó, uma lista dos nós predecessores para
os quais ainda não fez backtracking (Unbacktracked) Não sabe que aplicando “a” ( se a = UP, a = DOWN)
em s´, volta para s, pois desconhece as ligações entre estados e ações
Exemplo (trace)
Exemplo – Ordem das visitas: S1, S2, S3, S4, S5, S3...
– Unexplored(S3) depois de a = {Up,Left,Right}
– Unbacktracked de S3 = {S2, S6}
S2 S1
S6 S3
S5 S4
a
Busca em Profundidade Online
function ONLINE-DFS-AGENT(s’) returns an action inputs: s’, uma percepção que identifica o estado atual static: result[s,a], tabela (mapa) ação+s => s’, inicialmente vazia unexplored, para cada nó, lista das ações ainda não executadas unbacktracked, para cada nó, nós predecessores para os quais ainda unbacktracked para cada nó s, a, estado e ação anteriores, inicialmente nullif GOAL-TEST(s’) then return stopif s’ é um estado novo then unexplored[s’] ACTIONS(s´)if s não é null then do result[a,s] s’ adiciona s to na frente de unbacktracked[s’]if unexplored[s’] está vazio then if unbacktracked[s’] está vazio then return stop else a uma ação b tal que result[b,s’] = POP(unbacktracked[s’] )else a POP(unexplored[s’] )s s’return a
Hill-climbing
Hill-climbing– Mesmo princípio da localidade– Já é um algoritmo online (pois só mantém um nó na
memória)– Não muito útil (preso em ótimo local)– Reinício aleatório impossível (sem teletransporte :-).
Alternativa: Random-walk search – Escolhe ações aleatoriamente preferindo as não
usadasSe tempo suficientemente grande, acha solução
– Pode custar bem caro...
Aprendendo em Busca Online
LRTA* (Learning Real-Time A*)– Dar mais “memória” para o hill-climbing– Armazenar a melhor estimativa corrente H(s) do custo
para se atingir o objetivo a partir do nó sendo visitado– H(s) começa igual à heurística h(s) e é atualizada na
medida em que o agente conhece o espaço de estados – Agente vai para nó vizinho mais promissor e atualiza nó
anteriorH(s) = c(s,a,s’) + H(s’)
Custo estimado de s ao objetivo passando por s’ é o custo para ir de s a s’ mais H(s’)
“Aplaina” ótimos locais
– O(n2) para n estados no pior caso
LRTA* (learning real-time A*)
(a)
(b)
(c)
(d)
(e) H(s
) no
nó,
cu
sto
no
arc
oe
ag
ent
e n
o n
ó c
olo
rid
o
(a) Agente preso em mínimo local
(b) Agente vai para nó vizinho mais promissor: (esq = 9+1) vs. dir = 2 +1 e atualiza nó anterior pois H(s) estava subestimado
(c) Idem...
É claro...
Pode-se usar aprendizagem por reforço...– Até em mundos dinâmicos e não deterministas