02 buscacega IA

Prévia do material em texto

Busca Cega 
(ou exaustiva)
COMP0271:	Inteligência Artificial
Professor:	Hendrik	Macedo
Universidade Federal	de	Sergipe,	Brasil
Busca cega
Agentes Reativos
• Ações baseadas na percepção atual
• Não considera futuras consequências dos	seus atos
Agentes	Reativos
2 INTELLIGENT AGENTS
function TABLE-DRIVEN-AGENT(percept ) returns an action
persistent: percepts , a sequence, initially empty
table , a table of actions, indexed by percept sequences, initially fully specified
append percept to the end of percepts
action← LOOKUP(percepts , table)
return action
Figure 2.3 The TABLE-DRIVEN-AGENT program is invoked for each new percept and returns an
action each time. It retains the complete percept sequence in memory.
function REFLEX-VACUUM-AGENT([location ,status ]) returns an action
if status = Dirty then return Suck
else if location = A then return Right
else if location = B then return Left
Figure 2.4 The agent program for a simple reflex agent in the two-state vacuum environment. This
program implements the agent function tabulated in Figure ??.
function SIMPLE-REFLEX-AGENT(percept ) returns an action
persistent: rules , a set of condition–action rules
state← INTERPRET-INPUT(percept )
rule← RULE-MATCH(state , rules)
action← rule .ACTION
return action
Figure 2.6 A simple reflex agent. It acts according to a rule whose condition matches the current
state, as defined by the percept.
2
Agentes com	planejamento
• Decisões baseadas em hipóteses levantadas sobre as	consequências de	seus atos
• Mantém modelo de	como o	mundo evoluirá
• Deve formular um	objetivo (em forma	de	teste)
• Completude vs.	Otimalidade
Problemas de	busca
Formulação de	um	problema de	busca
•ESPAÇO	DE	ESTADOS
•FUNÇÃO	SUCESSOR
(com	ações e	custos)
•ESTADO	INICIAL
•ESTADO	OBJETIVO
“Norte”,	1.0
“Leste”,	1.0
Uma	solução é uma sequência de	ações
(plano)	que	transforma um	estado inicial em um	
estado objetivo
“Leste”,	1.0
...
Como	formular?
• Problema:	percurso
• Espaço de	Estados:	posições (x,y)
• Função sucessor:	NSLO
• Estado	inicial:	(0,	0)
• Estado	objetivo:	(x,y)	=	FIM	?
• Problema:	Comer	todos os pontos
• Espaço de	Estados:	?
• Função sucessor:	?
• Estado	inicial:	?
• Estado	objetivo:	?
O	Espaço de	busca deve conter apenas o	necessário para	o	planejamento (abstração)
Onde começa?
Objetivo?
Ações?
Solução?
• Problema:	8-puzzle
• Espaço:	?
• Sucessor:	?
• Inicial:	?
• Objetivo:	?
• Problema:	Torre	de	Hanoi
• Espaço:	?
• Sucessor:	?
• Inicial:	?
• Objetivo:	?
• Problema:	Percurso na cidade
• Espaço:	?
• Sucessor:	?
• Inicial:	?
• Objetivo:	?
• Problema:	processo de	construção
• Espaço:	?
• Sucessor:	?
• Inicial:	?
• Objetivo:	?
6
So
lu
çã
o
?
O
nd
e 
c
o
m
eç
a?
O
bje
tiv
o?
Aç
õe
s?
6
Solução?
Onde começa?
Objetivo?
Ações?
Grafos do	espaço de	estados
• Representação matemática do	espaço de	busca
• Nós são estados
• Arcos	são sucessores
• Cada estado ocorre apenas uma vez!
• Usualmente não conseguimos manter todo o	grafo na
memória
Grafos do	espaço de	estados
• Representação matemática do	espaço de	busca
• Nós são estados
• Arcos	são sucessores
• Cada estado ocorre apenas uma vez!
• Usualmente não conseguimos manter todo o	grafo na
memória
S
G
d
b
p q
c
e
h
a
f
r
Árvores do	espaço de	estados
• Nós representam estados mas	correspondem também a	PLANOS	que	geraram estes
estados.	Ou seja,	diferentes planos podem gerar estados iguais.
• Para	a	maioria dos	problemas,	nunca conseguimos construir toda a	árvore
“L”,	1.0“N”,	1.0
Estado	inicial (nó raiz)
Possíveis estados sucessores
(nós filhos)
Q:	Grafos vs.	Árvores
Árvore a	partir de	S	?
S
G
d
b
p q
c
e
h
a
f
r
Q:	Grafos vs.	Árvores
S G
b
a
Árvore a	partir de	S	?
Busca em árvore
Algoritmo de	busca genérico
Que	nó da	fronteira escolher para	expandir?
fronteira
Propriedades do	algoritmo de	busca
• Completude:	garante encontrar uma solução se	existir ?
• Otimalidade:	garante encontrar o	caminho de	menor custo?	
• Complexidade de	tempo?
• Complexidade de	espaço?
• Aspectos da	árvore de	busca:
• b	= fator de	ramificação
• m	=	maior profundidade
• Objetivos podem existir em vários níveis
• Número de	nós total	na árvore?
• 1	+	b	+	b2 +	….	bm =	O(bm)
…
b 1 nó
b nós
b2 nós
bm nós
m camadas
Depth-First	Search	(DFS)
{B}
{B, F, D, A}
{B, F, C, E, D, A}
{B, F, C, E, J, K, D, A}
{B, D, G, A}
{B, A, H, I}
{B, A, H, I, L}
Completo : não 
Ótimo (para problemas com uma única 
solução, caso encontre-a)
Tempo: O(bm) no pior caso
Espaço: O(bm) nós
Busca-Genérica (problema, Insere-no-Começo)
em Profundidade
Estratégia:	expandir
primeiramente cada uma das	
ramificações até sua
profundidade máxima
Implementação:	fronteira é
uma estrutura LIFO
Depth-First	Search	(DFS)
S
a
b
d p
a
c
e
p
h
f
r
q
q c G
a
qe
p
h
f
r
q
q c G
a
S
G
d
b
p q
c
e
h
a
f
rqp
h
fd
b
a
c
e
r
Depth-First	Search	(DFS)	.:	propriedades :.
• Quais nós DFS	expande?
• Esquerda para	direita da	árvore
• Pode processar toda a	árvore
• Se	m	é finito,	tempo	=	O(bm)
• Quanto espaço a	fronteira ocupa?
• Apenas irmãos no	caminho para	a	raiz,	espaço
=	O(bm)
• Completude?
• Apenas se	prevenirmos ciclos
• Otimalidade?
• Não.	Encontra a	solução mais à esquerda
independentemente da	profundidade e	do	
custo.
…
b 1 nó
b nós
b2 nós
bm nós
m 
camadas
Breadth-First	Search	(BFS)
Estratégia:	expandir
primeiramente todos os
filhos do	nível mais acima
Implementação:	fronteira
é uma estrutura ?
Breadth-First	Search
S
a
b
d p
a
c
e
p
h
f
r
q
q c G
a
qe
p
h
f
r
q
q c G
a
S
G
d
b
p q
c
e
h
a
f
r
Camdas
Breadth-First	Search	(BFS)	.:	propriedades:.
• Que	nós expande?
• Todos os nós acima do	nível do	nó objetivo
mais raso
• Se	nível do	nó objetivo for	s
• busca leva	tempo	=	O(bs)
• Espaço?
• Todos os nós da	última camadaà O(bs)
• Completude?
• Se	solução existe,	sim!
• Otimalidade?
• Apenas se	custos forem todos de	igual valor
…
b 1 nó
b nós
b2 nós
bm nós
s 
camadas
bs nós
Q:	DFS	vs	BFS;	Quem é quem abaixo?	
Q:	DFS	vs	BFS;	Quando um	será melhor que	
outro?
Iterative	Deepening
Iterative	Deepening
• Ideia:	espaço DFS	+	tempo	BFS
• Executa DFS	com	profundidade 1…
• Executa DFS	com	profundidade 2…
• Executa DFS	com	profundidade 3...
…
b
Considerando custos diferenciados na busca…
BFS	encontra o	melhor caminho em termos de	
número de	ações,	não em termos de	menor custo!	
START
GOAL
d
b
p
q
c
e
h
a
f
r
2
9 2
81
8
2
3
2
4
4
15
1
3
2
2
Uniform	Cost	Search
Estratégia: expandir
primeiramente um nó
menos custoso
Fronteira é uma Fila 
de prioridade
(prioridade = custo
acumulado)
Uniform	Cost	Search
S
a
b
d p
a
c
e
p
h
f
r
q
q c G
a
qe
p
h
f
r
q
q c G
a
S
G
d
b
p q
c
e
h
a
f
r
3 9 1
164 11
5
713
8
1011
17 11
0
6
3 9
1
1
2
8
8 2
15
1
2
Contornos
de custo
2
…
Uniform	Cost	Search	(UCS)	.:propriedades:.
• Expansão?
• Todos os nós com	custo menor do	que	da	solução mais barata.
• Se	solução custa C* e	arcos	custam pelo menos e ,à
profundidade efetiva =	C*/e
• Tempo	=	O(bC*/e)
• Espaço?
• Apenas última camadaà O(bC*/e)
• Completude?
• Sim!• Otimalidade?
• Sim!	
b
C*/e
“camadas” c £ 3
c £ 2
c £ 1
Uniform	Cost	:	observações
• UCS	explora contornos de	custos
crescentes
• UCS	é completo e	ótimo (BOM)
• UCS	explora opções em todas as	direções
(não há dica sobre local	do	estado
objetivo) (RUIM)
Start Goal
…
c £ 3
c £ 2
c £ 1
Q:	DFS	vs.	BFS	vs.	UCS;	Quem é quem?
Busca age	sobre modelos do	mundo
• O	agente não tenta
todos os possíveis
planos para	aquele
problema!
• A	busca é tão boa	
quanto for	seu
modelo do	mundo
Podem	existir	diferentes	modelos	para	o	
mesmo	problema
13
Qual o Espaço de Estados?
Diferentes	espaços	de	estado
15
Solução ótima no espaço discretizado
18
Uma solução possível
20
Solução ótima no espaço discretizado e no 
espaço contínuo original
Q:	Para	cada	estratégia	de	busca	em	grafo,	mostre	a	ordem	em	que	os	
estados	são	expandidos	e	o	caminho	da	solução	retornado	pela	busca	
(empates resolvem-se	em	ordem	alfabética)
CS188 Spring 2014 Section 0: Search
1 Search algorithms in action
CS188: Artificial Intelligence, Fall 2008
Written Assignment 1
Due: September 11th at the beginning of lecture
1 Graph Search Strategies
A
h=2
C
h=2
Goal
D
h=1
Start
B
h=5
2
4
2
5
4
5
3 1
Our intrepid hero, Search Agent, is late for her artificial intelligence class and needs to get there fast! The
graph above represents how long it takes Search Agent to walk between di�erent parts of campus. For each
of the following graph search strategies, work out the order in which states are expanded, as well as the path
returned by graph search. In all cases, assume ties resolve in such a way that states with earlier alphabetical
order are expanded first. The start and goal state are S and G, respectively. Remember that in graph search,
a state is expanded only once.
a) Depth-First Search
b) Breadth First Search
c) Uniform-Cost Search
d) Greedy search with the heuristic values listed at each state.
e) A� search with the heuristic values listed at each state.
For each of the following graph search strategies, work out the order in which states are expanded, as well
as the path returned by graph search. In all cases, assume ties resolve in such a way that states with earlier
alphabetical order are expanded first. The start and goal state are S and G, respectively. Remember that in
graph search, a state is expanded only once.
a) Depth-first search.
States Expanded: Start, A, C, D, B, Goal
Path Returned: Start-A-C-D-Goal
b) Breadth-first search.
States Expanded: Start, A, B, D, C, Goal
Path Returned: Start-D-Goal
c) Uniform cost search.
States Expanded: Start, A, B, D, C, Goal
Path Returned: Start-A-C-Goal
d) Greedy search with the heuristic h shown on the graph.
States Expanded: Start, D, Goal
Path Returned: Start-D-Goal
e) A? search with the same heuristic.
States Expanded: Start, A, D, C, Goal
Path Returned: Start-A-C-Goal
1
a) Depth-first search
Estados expandidos: ??
Caminho retornado: ??
b) Breadth First Search
Estados expandidos: ??
Caminho retornado: ??
c) Uniform-Cost Search
Estados expandidos: ??
Caminho retornado: ??
Q:	Para	cada	estratégia	de	busca	em	grafo,	mostre	a	ordem	em	que	os	
estados	são	expandidos	e	o	caminho	da	solução	retornado	pela	busca	
(empates resolvem-se	em	ordem	alfabética)
CS188 Spring 2014 Section 0: Search
1 Search algorithms in action
CS188: Artificial Intelligence, Fall 2008
Written Assignment 1
Due: September 11th at the beginning of lecture
1 Graph Search Strategies
A
h=2
C
h=2
Goal
D
h=1
Start
B
h=5
2
4
2
5
4
5
3 1
Our intrepid hero, Search Agent, is late for her artificial intelligence class and needs to get there fast! The
graph above represents how long it takes Search Agent to walk between di�erent parts of campus. For each
of the following graph search strategies, work out the order in which states are expanded, as well as the path
returned by graph search. In all cases, assume ties resolve in such a way that states with earlier alphabetical
order are expanded first. The start and goal state are S and G, respectively. Remember that in graph search,
a state is expanded only once.
a) Depth-First Search
b) Breadth First Search
c) Uniform-Cost Search
d) Greedy search with the heuristic values listed at each state.
e) A� search with the heuristic values listed at each state.
For each of the following graph search strategies, work out the order in which states are expanded, as well
as the path returned by graph search. In all cases, assume ties resolve in such a way that states with earlier
alphabetical order are expanded first. The start and goal state are S and G, respectively. Remember that in
graph search, a state is expanded only once.
a) Depth-first search.
States Expanded: Start, A, C, D, B, Goal
Path Returned: Start-A-C-D-Goal
b) Breadth-first search.
States Expanded: Start, A, B, D, C, Goal
Path Returned: Start-D-Goal
c) Uniform cost search.
States Expanded: Start, A, B, D, C, Goal
Path Returned: Start-A-C-Goal
d) Greedy search with the heuristic h shown on the graph.
States Expanded: Start, D, Goal
Path Returned: Start-D-Goal
e) A? search with the same heuristic.
States Expanded: Start, A, D, C, Goal
Path Returned: Start-A-C-Goal
1
a) Depth-first search.
Expandidos: Start, A, C, D, B, Goal
Retornados: Start-A-C-D-Goal
b) Breadth First Search
Expandidos: Start, A, B, D, C, Goal
Retornados: Start-D-Goal
c) Uniform-Cost Search
Expandidos: Start, A, B, D, C, Goal
Retornados: Start-A-C-Goal
Divulgação	científica
44
http://www.saense.com.br
https://www.facebook.com/saense/
Hendrik	Macedo
Escreve	sobre	Inteligência	Artificial no	Saense.
http://www.saense.com.br/autores/artigos-publicados-por-hendrik-macedo/