IA_Lista_1.pdf

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}