Skip to content

Instantly share code, notes, and snippets.

@NonWhite

NonWhite/IA_Lista_1.pdf

Last active May 16, 2022 17:59
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save NonWhite/2f310e557c3796e70960 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save NonWhite/2f310e557c3796e70960 to your computer and use it in GitHub Desktop.
Download ZIP
Display the source blob
Display the rendered blob
Raw
IA_Lista_1.pdf
Loading
Sorry, something went wrong. Reload?
Sorry, we cannot display this file.
Sorry, this file is invalid so it cannot be displayed.
Raw
IA_Lista_1.tex
\documentclass{article}
\usepackage{lmodern}
\usepackage[]{algorithm2e}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[portuguese]{babel}
\usepackage{mathtools}
\usepackage{enumitem}
\usepackage{listings}
\title{Lista 1 de Inteligência Artificial}
\author{9410313 - Walter Perez Urcia}
\begin{document}
\maketitle
\section{Tetris}
\subsection{Declaração}
Existem muitas variações do jogo Tetris, para esse exercício adotaremos as seguintes regras:
\begin{enumerate}
\item O tabuleiro é uma matriz contendo com 10 colunas e 22 linhas
\item Todos os tetraminós começam no meio do tabuleiro na linha superior
\item Existem 7 tipos de tetraminós "I", "O", "J", "L", "S", "Z", "T"
\item O tempo é discreto e cada ação (incluindo a ação no-op, que não causa alteração no estado) consome uma unidade de tempo
\item A posição, rotação e tipo de peça atual, assim como o estado do tabuleiro são conhecidos (e nada mais)
\end{enumerate}
Desenvolva os seguintes items:
\begin{enumerate}[ label = \alph*. ]
\item Descreva a formulação do problema de uma jogada de Tetris, ou seja, de mover a peça da posição inicial até uma posição alvo no tabuleiro previamente definida
\item Defina as funções necessárias para implementar uma busca genérica
\item Estime o número de nós expandidos no pior caso para uma busca em profundidade e uma busca em largura
\item Estime o número de nós expandidos no melhor caso para uma busca em profundidade e uma busca em largura quando o tabuleiro está vazio
\item Descreva uma heurística não admissível e uma admissível para uma estratégia de busca informada
\end{enumerate}
\subsection{Solução a}
A formulação para uma jogada de Tetris é a seguinte:
\begin{itemize}
\item Estados: Posição $( x , y )$ da peça + rotação $r$
\item Estado inicial: Posição $( x_i , y_i )$ + rotação $r_i$
\item Meta: Posição $( X_f , Y_f )$ no tabuleiro + rotação $R_f$
\item Ações: Rodar peça, mover esquerda, mover direita, no-op
\end{itemize}
A posição $( x , y $) de uma peça é definida por o quadrado inferior esquerdo, $x$ a coluna e $y$ a linha no tabuleiro.
\subsection{Solução b}
Podemos definir uma função ${buscaGenerica}$( $estado\_inicial$ , $estado\_meta$ , $função\_transição$ , $estratégia$ ) da seguinte forma:
\begin{enumerate}
\item ${estado}$ = ${estado\_inicial}$
\item Enquanto ${estado}$ diferente de ${estado\_meta}$ fazer
\begin{enumerate}
\item Encontrar as ações possíveis para ${estado}$
\item Encontrar os ${possíveis\_estados}$ usando a ${função\_transição}$ e as ações possíveis
\item Se ${possíveis\_estados}$ é uma lista vazia retorne falha
\item Seleccionar ${novo\_estado}$ usando ${estratégia}$
\item ${estado}$ = ${estado\_novo}$
\end{enumerate}
\item Retornar solução
\end{enumerate}
\subsection{Solução c}
O número de nós expandidos no pior caso são os seguintes:
\begin{itemize}
\item Busca em profundidade: $b^m$
\item Busca em largura: $b^{m+1}$
\end{itemize}
Onde $b$ é o fator de ramificação máximo de cada estado, neste casso $b = 4$ porque só tem 4 possíveis ações. Da mesma forma $m$ é a profundidade máxima que pode ter um estado no árvore de busca.
\subsection{Solução d}
O número de nós expandidos no melhor caso quando o tabuleiro está vazio são os seguintes:
\begin{itemize}
\item Busca em profundidade: $d$
\item Busca em largura: $b^{d+1}$
\end{itemize}
Os valores de $b$ e $m$ são iguais que na pergunta anterior. Além disso, $d$ é a profundidade da solução menos profunda.
\subsection{Solução e}
Uma heurística admissível pode ser
\[ h( n ) = dist( ( n.x , n.y ) , ( X_f , Y_f ) ) ,\]
onde ${dist}( p1 , p2 )$ é a distancia euclidiana entre os pontos $p1$ e $p2$. Por outro lado, uma heurística não admissível pode ser
\[ h( n ) = w_1 | n.x - X_f | + w_2 | n.y - Y_f | + w_3 | r - R_f | ,\]
onde $w_1, w_2, w_3 \geq 1$ e todas constantes porque o menor custo poderia ser quando elas tem valor igual a 1.
Para ambos casos, se assume que um nó $n$ contem a posição $( x , y )$ e a rotação $r$ da peça.
\section{Labirinto}
\subsection{Declaração}
O objetivo é dirigir o robô para fora de um labirinto. O robô inicia no meio do labirinto em direção ao norte. Você pode virar o robô em direção ao norte, sul, leste ou oeste. O robô pode ser comandado para mover uma certa distância para frente, apesar que irá parar antes de bater no muro.
\begin{enumerate}[ label = \alph*. ]
\item Formule esse problema. Qual é o tamanho do espaço de estados?
\item Ao navegar pelo labirinto, é necessário virar apenas na interseção de dois ou mais corredores. Reformule esse problema usando essa observação. Qual será o tamanho do espaço de estados agora? Estado inicial: Robô em coordenadas $(0,0)$, apontando para Norte
\item De qualquer ponto do labirinto, podemos mover em qualquer uma das quatro direções, até ter alcançado um ponto de virar e essa é a única ação que precisa ser feita. Reformule o problema usando essas ações. É necessário acompanhar a orientação do robô para resolver esse problema?
\item Na descrição inicial do problema já abstraímos do mundo real, restringindo as ações e removendo os detalhes. Liste três simplificações que fizemos
\end{enumerate}
\subsection{Solução a}
A formulação do problema é a seguinte:
\begin{itemize}
\item Estados: Posição (coordenadas) do robô no labirinto + direção
\item Estado inicial: Posição $(X_m,Y_m)$ no meio do labirinto + direção norte
\item Meta: Qualquer estado com posição $(X_f,Y_f)$ fora do labirinto
\item Ações: Virar, mover para frente
\item Função de transição: Em caso a ação seja virar, só vai mudar a direção no estado atual. Caso contrário (mover para frente) mudará a posição do robô se tem caminho na direção frente dele
\end{itemize}
Considerando um labirinto de dimensões $N \times M$ e as 4 possíveis direções: norte, sul, leste e oeste temos que o espaço de estados tem tamanho $4 \times N \times M$.
\subsection{Solução b}
Com as novas considerações a formulação do problema é a seguinte:
\begin{itemize}
\item Estados: Posição (coordenadas) do robô no labirinto + direção
\item Estado inicial: Posição $(0,0)$ + direção norte
\item Meta: Qualquer estado com posição $(X_f,Y_f)$ fora do labirinto
\item Ações: Virar (só em interseções), mover para frente
\item Função de transição: Em caso a ação seja virar, só vai mudar a direção no estado atual. Caso contrário (mover para frente) mudará a posição do robô se tem caminho na direção frente dele
\end{itemize}
Assumindo que temos $V$ pontos de interseção no labirinto, o tamanho do espaço de estados é igual a $4 \times V + 2 \times ( N \times M - V )$. Para cada posição de interseção é possível ter até 4 direções diferentes. Para as posições restantes só vai ser possível ter duas direções possíveis (dependendo da posição que vem o robô).
\subsection{Solução c}
Considerando as alterações no problema, sua formulação é a seguinte:
\begin{itemize}
\item Estados: Posição (coordenadas) do robô no labirinto
\item Estado inicial: Posição $(0,0)$
\item Meta: Qualquer estado com posição $(X_f,Y_f)$ fora do labirinto
\item Ações: mover para uma direção
\item Função de transição: Mudará a posição do robô
\end{itemize}
O tamanho do espaço de estados é $N \times M$. Não precisa colocar a orientação do robô no estado porque ele pode mover para qualquer direção em qualquer posição.
\subsection{Solução d}
As simplificações que foram feitas são:
\begin{itemize}
\item O labirinto é considerado como um tabuleiro com coordenadas inteiras
\item As distancias entre uma posição e outra não são importantes, só os movimentos para sair
\item O tempo que tarda em fazer cada uma das ações (virar e mover)
\end{itemize}
\section{Coloração de mapas}
\subsection{Declaração}
Forneça uma formulação completa do problema para cada um dos seguintes itens. Escolha a formulação suficientemente precisa para ser implementada:
\begin{enumerate}[ label = \alph*. ]
\item Usando apenas 4 cores, colorir um mapa plano de tal forma que das regiões adjacentes não tenham a mesma cor
\item Um macaco com 30 cm está em uma sala onde tem algumas bananas suspensas em um teto de 80 cm. Ele gostaria de pegar as bananas. A sala contém dois engradados móveis e escaláveis com 30 cm de altura que podem ser empilhados
\item Existe um programa que exibe a mensagem "registro de entrada inválido" ao alimentar determinado arquivo com registros de entrada. Você sabe que o processamento de cada registro é independente de outros registros e deseja descobrir qual registro é inválido
\item Existem três jarras que medem 12, 8 e 3 galões e uma torneira de água. As jarras podem ser enchidas ou esvaziadas uma da outra ou para o chão. Medir exatamente um galão, somente com essas operações
\end{enumerate}
\subsection{Solução a}
\begin{itemize}
\item Estados: Mapa com algumas regiões coloridas
\item Estado inicial: Mapa sem pintar
\item Meta: Mapa completo colorido
\item Ações: Colorir uma região
\item Função de transição: Dado um mapa com $n$ regiões coloridas, retorna um mapa com $n+1$ regiões coloridas tal que as regiões adjacentes não tenham a mesma cor
\end{itemize}
\subsection{Solução b}
\begin{itemize}
\item Estados: Altura do macaco
\item Estado inicial: Não é mencionada a altura inicial do macaco
\item Meta: 80 cm
\item Ações: Empilhar engradados, mover engradado
\item Função de transição: Não é muito precisa
\end{itemize}
Não é suficientemente precisa porque não diz sobre como o macaco pega a banana ou se precisa chegar até uma determinada altura. Alem disso, não menciona se os 30 cm são a altura dos pés do macaco ou altura de sua cabeça.
\subsection{Solução c}
\begin{itemize}
\item Estados: Posição no arquivo + válido/inválido
\item Estado inicial: Inicio do arquivo
\item Meta: Qualquer estado com inválido
\item Ações: Processar registro (e dizer se é válido ou não)
\item Função de transição: Se o registro é válido, retorna a seguinte posição. Caso contrário só muda de válido a inválido o estado
\end{itemize}
\subsection{Solução d}
\begin{itemize}
\item Estados: Quantidade de galões em cada torneira
\item Estado inicial: Não é mencionada
\item Meta: Qualquer estado com uma torneira com exatamente um galão
\item Ações: Enchidar uma torneira, esvaziar uma torneira
\end{itemize}
A formulação suficientemente precisa para ser implementada é a primeira, aquela para colorir o mapa com 4 cores.
\section{Estado e nó}
\subsection{Declaração}
Qual é a diferença entre um estado do mundo, uma descrição do estado e nó de busca? Por que é útil essa distinção?
\subsection{Solução}
Um estado do mundo é a representação simplificada da situação atual no mundo, enquanto uma descrição do estado é a interpretação desse estado no mundo. Por último um, nó de busca é um estado que pode ser expandido a outro baseado em uma estratégia de busca e é parte de um árvore de busca. A distinção é útil porque o primeiro da uma ideia sobre como está o mundo em termos gerais. O segundo ajuda a conhecer com mais detalhes a situação do mundo e os nós de busca ajudam para encontrar uma solução ao problema dependendo da estratégia de busca.
\section{Estratégias de busca}
\subsection{Declaração}
Qual das seguintes alternativas são falsas e quais são verdadeiras? Explique suas respostas.
\begin{enumerate}[ label = \alph*. ]
\item A busca em profundidade sempre expande pelo menos tantos nós quanto a busca $A^*$ com uma heurística admissível
\item $h( n ) = 0$ é uma heurística admissível para o quebra cabeças de 8 peças
\item Em robótica, $A^*$ não é útil porque as percepções, estados e ações são contínuas
\item A busca em largura é completa mesmo se os custos de passos iguais a zero forem permitidos
\item Assuma que a torre pode se mover em um tabuleiro de xadrez qualquer quantidade de quadrados em linha reta, verticalmente ou horizontalmente, mas não pode pular sobre as peças. A distância de Manhatam é uma heurística admissível para o problema de movimentar a torre do quadrado A para o B no menor número de movimentos
\end{enumerate}
\subsection{Solução a}
Falso. A busca em profundidade expande um nó ao mesmo tempo enquanto $A^*$ expande todos os nós vizinhos. Além disso, a busca em profundidade é incompleta e $A^*$ é completa.
\subsection{Solução b}
Verdadeiro. Uma heurística $h( n )$ é admissível se $h( n ) \leq C( n )$, onde $C( n )$ é o custo para chegar ao nó $n$.
\subsection{Solução c}
Falso. $A^*$ usa duas funções: uma heurística $h( n )$ que diz o custo estimado para chegar ao estado $n$ à meta e uma função de custo $C( n )$ que diz quanto custa chegar do início ao estado $n$. Aquelas funções podem retornar valores contínuos e também $n$ pode ser um valor contínuo.
\subsection{Solução d}
Verdadeiro. A busca em largura pode ser usada ainda se tem custos de passos iguais a zero só que aqueles nós tem que ser colocados ao início da fila e não ao final porque tem menor profundidade.
\subsection{Solução e}
Verdadeiro. Uma heurística $h( n )$ é admissível se $h( n ) \leq C( n )$, onde $C( n )$ é o custo para chegar ao nó $n$. Se no caminho para ir de $A$ a $B$ não tem peças $h( n ) = C( n )$, caso contrario $h( n ) < C( n )$.
\end{document}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment