\documentclass[12pt, a4paper]{report}

\pagestyle{empty}
\begin{document}
 
\noindent Bacharelado em Ci\^{e}ncia da Computa\c{c}\~{a}o
\hfill DCC/ICEx/UFMG
 
\noindent {\it Intelig\^encia Artificial}
\hfill $\mbox{2}^{\mbox{\underline{o}}}$ semestre de 2001
 
\noindent Professor: Newton Jos\'{e} Vieira
 
\noindent {\bf Primeira Lista de Exerc\'{\i}cios} \hfill Devolu\c c\~ao: 18/09/01

\vspace*{3mm}
Os seguintes exerc\'{\i}cios dizem respeito \`a implementa\c c\~ao de um ambiente
e de um conjunto de agentes no mundo do aspirador de p\'o. Podem ser feitos em
grupos de no m\'aximo 3 alunos. (A numera\c c\~ao \'e a do livro texto: Russel \& Norvig's.)
\begin{enumerate}
 \item[2.5] Implemente um simulador de ambiente com medi\c c\~ao de desempenho para o
       mundo do aspirador de p\'o, como se segue:
       \begin{itemize}
        \item {\bf Est\'{\i}mulos}: Cada agente aspirador recebe um vetor de
              est\'{\i}mulos de 3 elementos por vez. O primeiro elemento, um sensor de
              toque, \'e 1 se a m\'aquina bateu em alguma coisa e 0 caso contr\'ario.
              O segundo vem de um fotosensor debaixo da m\'aquina, que emite 1 se h\'a
              sujeira e 0 se n\~ao h\'a. O terceiro vem de um sensor infravermelho,
              que emite 1 quando o agente est\'a no seu local de descanso, e 0 caso
              contr\'ario.
        \item {\bf A\c c\~oes}: H\'a 5 a\c c\~oes poss\'{\i}veis: v\'a em frente,
              vire \`a direita $90^{\mbox{o}}$, vire \`a esquerda $90^{\mbox{o}}$,
              aspire e desligue.
        \item {\bf Metas}: A meta para cada agente \'e fazer a limpeza do ambiente e
              retornar ao local de descanso. Mais precisamente, a medida de desempenho
              ser\'a 100 pontos para cada sujeira aspirada, menos 1 ponto para cada
              a\c c\~ao executada, e menos 1000 pontos se o agente n\~ao estiver no
              local de descanso quando ele se desligar.
        \item {\bf Ambiente}: Consiste de uma grade de quadrados. Alguns cont\^em
              obst\'aculos (paredes e m\'oveis) e outros s\~ao espa\c cos vazios.
              Alguns dos quadrados vazios cont\^em sujeira. Cada a\c c\~ao ``v\'a em
              frente'' move um quadrado, a menos que haja um obst\'aculo em frente;
              neste \'ultimo caso, o agente fica im\'ovel e o sensor de toque emite 1.
              Uma a\c c\~ao ``aspire'' sempre limpa a sujeira do quadrado onde est\'a
              o agente. Uma a\c c\~ao ``desligue'' acaba a simula\c c\~ao.
       \end{itemize}
       Pode-se variar a complexidade do ambiente ao longo de 3 dimens\~oes:
       \begin{itemize}
        \item {\bf Forma da sala}: No caso mais simples, a sala \'e um quadrado
              $n\times n$, para um $n$ fixo. Pode-se fazer a coisa ficar mais
              complicada mudando-se a forma para retangular, forma de L ou irregular,
              ou para uma s\'erie de salas conectadas por corredores.
        \item {\bf M\'oveis}: Colocar m\'oveis na sala faz a coisa ficar mais
              complicada. Para o agente aspirador, um peda\c co de m\'ovel n\~ao pode
              ser distinguido de uma parede por percep\c c\~ao; ambos aparecem como
              um 1 no sensor de toque.
        \item {\bf Disposi\c c\~ao da sujeira}: No caso mais simples, a sujeira \'e
              disposta uniformemente na sala. Mas \'e mais real\'{\i}stico que a
              sujeira predomine em certos locais, como ao longo de um trecho muito
              utilizado para deslocamentos para uma sala pr\'oxima, ou em frente a um
              sof\'a.
       \end{itemize}

 \item[2.6] Implemente um agente do tipo {\em table-lookup\/} para o caso especial de uma
       grade $2\times 2$ em que no m\'aximo 2 quadrados podem conter sujeira. O agente
       come\c ca no quadrado superior \`a esquerda, de frente para a direita. Lembre que
       um agente do tipo {\em table-lookup\/} consiste de uma tabela de a\c c\~oes
       indexada por uma sequ\^encia de est\'{\i}mulos. No presente ambiente, o agente
       pode completar sua tarefa com 9 a\c c\~oes ou menos (4 deslocamentos, 3 giros e
       duas aspiradas), de forma que a tabela precisa de entradas apenas para
       sequ\^encias de tamanho at\'e 9. Em cada turno h\'a 8 poss\'{\i}veis vetores de
       est\'{\i}mulos, de forma que a tabela ter\'a tamanho $8^9=134.217.728$.
       Afortunadamente, pode-se abaixar isto notando-se que o sensor de toque e o sensor
       do local de descanso s\~ao desnecess\'arios: pode-se fazer de forma o agente
       nunca trombe na parede e saiba quando retornou para o local de descanso. Com isto
       ficar\~ao apenas dois vetores relevantes de est\'{\i}mulos, $?0?$ e $?1?$, e o
       tamanho da tabela \'e no m\'aximo $2^9=512$. Execute o simulador de ambientes no
       agente em todos os mundos poss\'{\i}veis (quantos existem?). Registre o
       desempenho do agente para cada mundo e o seu desempenho m\'edio.

 \item[2.7] Implemente um ambiente para uma sala retangular $n\times m$, onde cada
       quadrado tem 5\% de chance de conter sujeira, e $n$ e $m$ s\~ao escolhidos
       aleatoriamente do intervalo 8 a 15, inclusive.

 \item[2.8] Implemente um agente de reflexo puro para o ambiente do exerc\'{\i}cio anterior,
       ignorando o requisito de retornar ao local de descanso, e me\c ca seu desempenho.
       Explique porque \'e imposs\'{\i}vel ter um agente reflexo que volte ao local de
       descanso e se desligue.

 \item[2.9] Projete e implemente v\'arios agentes com estado interno. Me\c ca seus desempenhos.
       Qu\~ao perto eles chegam ao agente ideal para este ambiente?

% \item[2.10] Calcule o tamanho da tabela para um agente do tipo {\em table look-up\/} no
%       dom\'{\i}nio do Exerc\'{\i}cio 2.7. Explique seus c\'alculos. N\~ao precisa preencher
%       as entradas da tabela.
%
% \item[2.11] Experimente com mudan\c cas na forma da sala e posicionamento da sujeira, e com
%       coloca\c c\~ao dos m\'oveis. Avalie seus agentes nestes novos ambientes. Discuta como
%       seus desempenhos podem ser melhorados para manipular geografias mais complexas.

\end{enumerate}

\end{document}
 
