lista01_CSI457_2023-2 soluções

Prévia do material em texto

DECSI - UFOP, CSI 457 e CSI 701
Notas de Aula
Lista 01
Inteligência Arti�cial
Prof. Dr. Talles Henrique de Medeiros
Talles Medeiros
2023/2
Exercícios
IMPORTANTE: Essa lista deverá ser feita manualmente, de forma organizada, ordenada e nítida.
Para submeter a lista no Moodle, você deverá enviar o material em formato PDF, escaneado. Uma
opção é o app: CamScanner - Phone PDF Creator, disonível para iOS/Android.
1. “Computadores não podem ser inteligentes – eles podem fazer apenas o que seus progra-
madores dizem a eles”. Esta última a�rmação é verdadeira? A última a�rmação implica
na primeira?
RESPOSTA: Isso depende da sua de�nição de "inteligente"e "dizer". Em certo sentido, apenas
computadores fazer o que os programadores ordenam que façam, mas em outro sentido o
que os programadores conscientemente diz ao computador para fazer, muitas vezes tem
muito pouco a ver com o que o computador realmente faz. Qualquer pessoa que escreveu um
programa com um bug desagradável sabe disso, assim como qualquer pessoa que escreveu um
programa de aprendizado de máquina de sucesso. Então, em certo sentido, Samuel "disse"ao
computador “aprenda a jogar damas melhor do que eu, e depois jogue assim”, mas de outra
sentido, ele disse ao computador “siga este algoritmo de aprendizagem” e ele aprendeu a
jogar. Então onde deixado na situação em que você pode ou não considerar aprender a jogar
damas como um sinal de inteligência (ou você pode pensar que aprender a jogar da maneira
certa requer inteligência, mas não desta forma), e você pode pensar que a inteligência reside
no programador ou no computador.
2. De�na os seguintes termos com suas próprias palavras: agente, função de agente, pro-
grama de agente, racionalidade, autonomia, agente reativo (re�exivo), agente baseado em
modelo, agente baseado em objetivo, agente baseado em utilidade.
RESPOSTA: Agente: entidade que percebe e atua; ou, aquele que pode ser visto como
percebendo e atuando. Essencialmente, qualquer objeto se quali�ca; o ponto chave é a
forma como o objeto implementa uma função de agente. (Nota: alguns autores restringem
o termo a programas que operam em nome de um ser humano, ou para programas que
podem fazer com que parte ou todo o seu código seja executado em outras máquinas em uma
rede, como em agentes móveis.) • Função do agente: uma função que especi�ca a ação do
agente em resposta a todas as perceber a sequência. • Programa de agente: aquele programa
que, combinado com uma arquitetura de máquina, implementa uma função de agente. Em
nossos designs simples, o programa assume uma nova percepção sobre cada invocação e
retorna uma ação. Racionalidade: uma propriedade dos agentes que escolhem ações que
maximizam sua utilidade esperada, dadas as percepções até o momento. • Autonomia: uma
propriedade dos agentes cujo comportamento é determinado por sua própria experiência
em vez de apenas por sua programação inicial. • Agente de re�exo: um agente cuja ação
2
depende apenas da percepção atual. • Agente baseado em modelo: um agente cuja ação é
derivada diretamente de um modelo interno do estado mundial atual que é atualizado ao
longo do tempo. • Agente baseado em metas: um agente que seleciona ações que acredita
que irão atingir explicitamente objetivos representados. • Agente baseado em utilidade: um
agente que seleciona ações que acredita que irão maximizar o utilidade esperada do estado
de resultado. • Agente de aprendizagem: um agente cujo comportamento melhora ao longo
do tempo com base em sua experiência.
3. Os ambientes do problema do aspirador (capítulo 02) considerados até o momento são to-
dos determinísticos. Discuta possíveis programas de agentes para cada uma das seguintes
versões estocásticas:
• a. Lei de Murphy: Em 25% do tempo, a ação de aspirar o chão não consegue limpá-lo
caso este esteja sujo, ou, caso esteja limpo, sujeira é depositada acidentalmente.
Como o programa do agente é afetado se se o sensor de sujeira dá a resposta errada
em 10% das leituras?
• b. Crianças pestinhas: A cada momento, cada quadriculado limpo do chão tem 10%
de chance de �car sujo. Como você projetaria o agente racional para este caso?
RESPOSTAS: a. Para um agente re�exo, isso não representa um desa�o adicional, porque
o agente continuará para sugar, desde que o local atual permaneça sujo. Para um agente
que constrói um plano sequencial, cada ação de sucção precisaria ser substituída por “Sugar
até limpar”. Se o sensor de sujeira pode estar errado em cada etapa, o agente pode querer
esperar por um algumas etapas para obter uma medição mais con�ável antes de decidir se
deve sugar ou mover para um novo quadrado. Obviamente, há uma compensação porque
esperar muito signi�ca que a sujeira permanece no chão (incorrendo em uma penalidade),
mas agir imediatamente corre o risco de sujar um quadrado limpo ou ignorar um quadrado
sujo (se o sensor estiver errado). Um agente racional também deve continuar visitando e
veri�cando os quadrados, caso tenha perdido um em uma vez anterior (por causa de leituras
de sensor ruins). Não é imediatamente óbvio como o tempo de espera em cada quadrado deve
mudar a cada nova vez. Esses problemas podem ser esclarecidos por experimentação, o que
pode sugerir uma tendência geral que pode ser veri�cada matematicamente. Este problema é
um processo de decisão de Markov parcialmente observável - Capítulo 17. Esses problemas
são difíceis em geral, mas alguns casos especiais podem ceder a análise cuidadosa.
b. Nesse caso, o agente deve continuar percorrendo as praças inde�nidamente. A probabilidade
de que um quadrado está sujo aumenta monotonicamente com o tempo desde que foi limpo
pela última vez, então o estratégia racional é, grosso modo, executar repetidamente o tour
mais curto possível todos os quadrados. (Dizemos "grosso modo"porque existem complicações
causadas pelo fato de que o passeio mais curto pode visitar algumas praças duas vezes,
dependendo da geogra�a.) Este problema também é um processo de decisão de Markov
parcialmente observável.
4. Formule o problema (estado inicial, possíveis ações, modelo de transição, função de
objetivo, custo de caminho) para os casos a seguir. Escolha o nível de abstração adequado
para a implementação:
3
• b. Você tem 3 jarros que medem 12 L, 8 L e 3 L, e uma torneira. Você pode: (i)
completar os jarros com água até a boca, (ii) transferir o conteúdo de um jarro para
outro ou (iii) esvaziá-los descartando seu conteúdo. Deseja-se obter uma quantidade
de água de exatamente 1 L.
b. Estado inicial: os jarros têm valores [0, 0, 0]. Função sucessora: valores dados [x, y, z],
gerar [12, y, z], [x, 8, z], [x, y, 3] (preenchendo); [0, y, z], [x, 0, z], [x, y, 0] (por esvaziamento);
ou para quaisquer dois jarros com valores atuais x e y, despeje y em x; isso muda a jarra com
x para o mínimo de x + y e a capacidade da jarra, e diminui a jarra com y na quantidade
ganha pela primeira jarra. Função de custo: número de ações.
5. Rastreie a operação da busca A* aplicada ao problema de chegar a Bucareste a partir de
Lugoj usando a heurística da distância em linha reta (Veja valores no livro). Ou seja,
mostre a sequência de nós que o algoritmo irá considerar e o score 5 , 6 e ℎ para cada nó.
RESPOSTA: L[0+244=244]
M[70+241=311], T[111+329=440]
L[140+244=384], D[145+242=387], T[111+329=440]
D[145+242=387], T[111+329=440], M[210+241=451], T[251+329=580]
C[265+160=425], T[111+329=440], M[210+241=451], M[220+241=461], T[251+329=580]
T[111+329=440], M[210+241=451], M[220+241=461], P[403+100=503], T[251+329=580],
R[411+193=604],D[385+242=627]
M[210+241=451], M[220+241=461], L[222+244=466], P[403+100=503], T[251+329=580],
A[229+366=595],R[411+193=604], D[385+242=627]
M[220+241=461], L[222+244=466], P[403+100=503], L[280+244=524], D[285+242=527],
T[251+329=580], A[229+366=595], R[411+193=604], D[385+242=627]
L[222+244=466], P[403+100=503], L[280+244=524], D[285+242=527], L[290+244=534],
D[295+242=537], T[251+329=580], A[229+366=595], R[411+193=604], D[385+242=627]
P[403+100=503], L[280+244=524],D[285+242=527], M[292+241=533], L[290+244=534],
D[295+242=537], T[251+329=580], A[229+366=595], R[411+193=604], D[385+242=627],
T[333+329=662]
B[504+0=504], L[280+244=524], D[285+242=527], M[292+241=533], L[290+244=534], D[295+242=537],
T[251+329=580], A[229+366=595], R[411+193=604], D[385+242=627], T[333+329=662],
R[500+193=693], C[541+160=701]
6. O problema de missionários e canibais é normalmente enunciado como a seguir. Três
missionários e três canibais estão em um lado de um rio, juntamente com um barco que
pode levar uma ou duas pessoas. Descubra um meio de fazer todos atravessarem o rio sem
deixar que um grupo de missionários de um lado �que em número menor que o número
de canibais nesse mesmo lado do rio. Esse problema é famoso em IA porque foi assunto
4
do primeiro artigo que abordou a formulação de problemas a partir de um ponto de vista
analítico.
• a. Formule o problema precisamente, fazendo apenas as especi�cações necessárias
para assegurar uma solução válida. Faça um diagrama do espaço de estados completo.
• RESPOSTA: Uma possível representação seria: Um estado que é uma estrutura de seis
inteiros listando, respectivamente, o número de missionários, de canibais, de barcos de
um lado da margem e o mesmo para o outro lado da margem. O objetivo é um estado
com 3 missionários, 3 canibais na outra margem do rio. A função de custo é unitária,
os sucessores de um estado são todos estados que movem uma ou duas pessoas e um
barco de um lado para o outro do rio.
• b. Implemente e resolva o problema de forma ótima, utilizando um algoritmo de
busca apropriado. É uma boa ideia veri�car a existência de estados repetidos?
• RESPOSTA: O espaço de busca é pequeno, então qualquer algoritmo ótimo resolve bem.
É importante eliminar movimentos que gerem estados repetidos.
• c. Por que você imagina que as pessoas têm di�culdades para resolver esse quebra-
cabeça, considerando que o espaço de estados é tão simples?
• RESPOSTA: Não é óbvio que quase todos os movimentos sejam ilegais ou revertam
ao estado anterior. Há uma sensação de um grande fator de rami�cação 1 e quase
nenhuma alternativa clara de movimento.
7. Qual das seguintes alternativas são falsas e quais são verdadeiras? Explique suas respostas.
• a. A busca em profundidade sempre expande pelo menos tantos nós quanto a busca
A* com uma heurística admissível.
• FALSO: um DFS (Deep First Search) sortudo pode expandir exatamente 3 nós para
atingir a meta. A domina amplamente qualquer algoritmo de busca em grafo uma vez
que ele possui garantia de otimalidade em encontrar soluções ótimas.
• b. ℎ(=) = 0 é uma heurística admissível para o quebra cabeças de 8 peças.
• VERDADEIRO: ℎ(=) = 0 é sempre uma heurística admissível, desde que o custo seja
não-negativo.
• c. Em robótica, A* não é útil porque as percepções, estados e ações são contínuas.
• FALSO: busca A* é frequentemente usada na robótica; o espaço de estados pode ser
discretizados ou minimizados.
• d. A busca em largura é completa mesmo se os custos de passos iguais a zero forem
permitidos.
• VERDADEIRO: a profundidade da solução é o que importa para a busca em largura,
não os custos.
5
• e. Assuma que a torre pode se mover em um tabuleiro de xadrez qualquer quanti-
dade de quadrados em linha reta, verticalmente ou horizontalmente, mas não pode
pular sobre as peças. A distância de Manhattan é uma heurística admissível para
o problema de movimentar a torre do quadrado A para o B no menor número de
movimentos.
• FALSO: uma torre pode mover-se pelo tabuleiro em um movimento único, embora
a distância manhattan de um início até um �m seja um número maior, constando
movimentos de vertical e horizontal.
6