\documentclass[12pt, a4paper]{article}
 
\newcounter{conta}
\newcounter{conta2}

\hyphenation{e-xis-ten-te geo-gra-fia es-pe-cia-li-za-das e-xem-plo pro-je-to
com-ple-xi-da-de de-sa-pa-re-ce a-bor-da-gem co-mo fa-lhas es-co-lhi-da}

\begin{document}

\vspace*{7cm}
\begin{center}\Huge
Cap\'{\i}tulo 11: Planejamento
\end{center}

\vfill

\pagebreak
\noindent{\LARGE Diferen\c cas b\'asicas entre ``resolu\c c\~ao de problemas'' e planejamento:}

\begin{itemize}\Large
 \item Representa\c c\~ao de estados, metas e a\c c\~oes.

       Planejamento: estados e metas descritos em linguagem formal (L\'ogica); a\c c\~oes
       descritas por precondi\c c\~oes $\Rightarrow$ efeitos.
 
 \item Gera\c c\~ao da sequ\^encia de a\c c\~oes do plano.

       Planejamento: flexibilidade na constru\c c\~ao da sequ\^encia.

 \item Independ\^encia de partes do mundo com rela\c c\~ao a outras.

       Planejamento: composi\c c\~ao de planos a partir de subplanos
       (estrat\'egia dividir-para-conquistar).
\end{itemize}

\vspace*{1cm}
\begin{center}\large
\begin{tabular}{l|l|l}
 & {\bf Busca} & {\bf Planejamento} \\ \hline
{\bf Estados} & Estrutura de dados & Senten\c cas l\'ogicas \\
{\bf A\c c\~oes} & Procedimento & Precondi\c c\~oes/resultados \\
{\bf Meta} & Procedimento & Senten\c ca l\'ogica (conjun\c c\~ao) \\
{\bf Plano} & Sequ\^encia & Restri\c c\~oes sobre a\c c\~oes
\end{tabular}
\end{center}


\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\LARGE\bf Planejamento no C\'alculo das Situa\c c\~oes}

\vspace*{1cm}
\noindent {\LARGE Estado inicial:}

\begin{itemize}\Large
 \item $\mbox{at}(\mbox{Home},S_0)\wedge\neg\mbox{have}(\mbox{Milk},S_0)\wedge
        \neg\mbox{have}(\mbox{Bananas},S_0)$ \\
       $\wedge\neg\mbox{have}(\mbox{Drill},S_0)$
\end{itemize}

\vspace*{.5cm}
\noindent {\LARGE Estado meta:}

\begin{itemize}\Large
 \item $s\,\,|\,\, \mbox{at}(\mbox{Home},s)\wedge\mbox{have}(\mbox{Milk},s)\wedge
        \mbox{have}(\mbox{Bananas},s)$ \\
      \hspace*{.5cm} $\wedge\mbox{have}(\mbox{Drill},s)$
\end{itemize}

\vspace*{.5cm}
\noindent {\LARGE Operadores:}

\begin{itemize}\Large
 \item $\forall a,s\,\,\, \mbox{have}(\mbox{Milk},\mbox{Res}(a,s))\Leftrightarrow$ \\
        \hspace*{1.5cm}$[(a=\mbox{Buy}(\mbox{Milk})\wedge\mbox{at}(\mbox{Supermarket},s))$ \\
        \hspace*{1.7cm}$\vee(\mbox{have}(\mbox{Milk},s)\wedge a\not=\mbox{Drop}(\mbox{Milk}))]$
\end{itemize}

\vspace*{.5cm}
\noindent {\LARGE Solu\c c\~ao:}

\begin{itemize}\Large
 \item $s=\mbox{Res}(\ldots\mbox{Res}(\mbox{Buy}(\mbox{Milk}),
        \mbox{Res}(\mbox{Go}(\mbox{Supermarket}),S_0)))\ldots)$
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\LARGE Problemas do planejamento usando o C\'alculo das situa\c c\~oes:}

\begin{itemize}\Large
 \item Inefici\^encia.
 \item Planos podem conter passos irrelevantes: \\
       $\mbox{Res}(A^{-1},\mbox{Res}(A,s))$, \ldots
\end{itemize}

\vspace*{.5cm}
\noindent {\LARGE Em dire\c c\~ao \`a pr\'atica:}

\begin{itemize}\Large
 \item Linguagem restrita.
 \item Algoritmo de prop\'osito espec\'{\i}fico: um {\bf planejador}.
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE\bf Linguagem tipo STRIPS:}

\begin{itemize}\Large
 \item {\bf Estado:} representado por uma conjun\c c\~ao de literais b\'asicos sem fun\c c\~oes.

       Ex: $\mbox{at}(\mbox{Home})\wedge\neg\mbox{have}(\mbox{Milk})\wedge
            \neg\mbox{have}(\mbox{Bananas})\wedge\neg\mbox{have}(\mbox{Drill})\wedge\cdots$
 \item {\bf Meta:} representada por uma conjun\c c\~ao de literais.

       Ex1: $\mbox{at}(\mbox{Home})\wedge\mbox{have}(\mbox{Milk})\wedge
            \mbox{have}(\mbox{Bananas})\wedge\mbox{have}(\mbox{Drill})$

       Ex2: $\mbox{at}(x)\wedge\mbox{sells}(x,\mbox{Milk})$

 \item {\bf Operadores:} 3 partes:
       \begin{itemize}
        \item descri\c c\~ao da a\c c\~ao: um \'atomo (com ou sem var\'aveis);
        \item precondi\c c\~ao: conjun\c c\~ao de \'atomos;
        \item efeito: conjun\c c\~ao de literais.
       \end{itemize}
\end{itemize}


\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\LARGE Exemplo de (esquema de) Operador:}

\vspace*{.5cm}
\begin{enumerate}\Large
 \item[\ ] $\mbox{\em Op\/}(\mbox{\large ACTION}: \mbox{Go}(\mbox{\em there}),$ \\
             \hspace*{1cm}$\mbox{\large PRECOND}: \mbox{at}(\mbox{\em here})\wedge
                               \mbox{path}(\mbox{\em here},\mbox{\em there}),$ \\
             \hspace*{1cm}$\mbox{\large EFFECT}: \mbox{at}(\mbox{\em there})\wedge
                               \neg\mbox{at}(\mbox{\em here}))$
\end{enumerate}

\vspace*{.5cm}
\noindent {\LARGE Exemplo de aplica\c c\~ao de $\mbox{Go}(\mbox{Supermarket})$:}

\begin{itemize}\Large
 \item Estado atual:

       $\mbox{at}(\mbox{Home}),\mbox{path}(\mbox{Home},\mbox{Supermarket}),\ldots$

 \item Ap\'os a aplica\c c\~ao de $\mbox{Go}(\mbox{Supermarket})$:

       $\neg\mbox{at}(\mbox{Home}), \mbox{path}(\mbox{Home},\mbox{Supermarket}),$ \\
       $\mbox{at}(\mbox{Supermarket}),\ldots$
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent{\LARGE Espa\c co de estados $\times$ espa\c co de planos:}

\begin{itemize}\Large
 \item Pesquisa convencional:
         \begin{enumerate}
          \item[\ ] nodo $=$ estado (situa\c c\~ao) do mundo
          \item[\ ] solu\c c\~ao: caminho do estado inicial ao meta.
         \end{enumerate}
 \item Pesquisa de planejamento:
        \begin{enumerate}
          \item[\ ]  nodo $=$ {\bf plano parcial}
        \end{enumerate}

         ({\bf Precondi\c c\~ao aberta:} precondi\c c\~ao de um passo ainda n\~ao satisfeita.)

         Operadores sobre planos parciais:

         \begin{itemize}
          \item {\bf acrescentar um passo} ao plano (para satisfazer uma precondi\c c\~ao aberta)
          \item impor uma {\bf ordem} entre dois passos
          \item {\bf acrescentar uma liga\c c\~ao} de uma a\c c\~ao j\'a existente a uma precondi\c c\~ao aberta.
          \item Etc\ldots
         \end{itemize}

          A partir de planos incompletos/vagos construir paulatinamente planos completos e corretos.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\LARGE Planos {\bf parcialmente ordenados}:}

\begin{itemize}\Large
 \item Princ\'{\i}pio do {\bf menor comprometimento}: s\'o fazer escolhas {\bf necess\'arias}.
 \item Planos parcialmente ordenados: n\~ao h\'a ordem para alguns passos (s\'o ordenar
         quando necess\'ario).

          Exemplo: {\em RightShoe} e {\em LeftShoe} 
 \item N\~ao instanciar vari\'aveis (a menos que necess\'ario).

         Exemplo: seja a meta $\mbox{have}(\mbox{Milk})$. Pode-se escolher a a\c c\~ao
         $\mbox{\em Buy}(\mbox{\em item},\mbox{\em store})$, com:
         \begin{itemize}
          \item $\mbox{\em item}/\mbox{Milk}$
          \item $\mbox{\em store}$: n\~ao instanciada...
         \end{itemize}
\end{itemize}

\vspace*{1cm}
\noindent {\LARGE Um {\bf plano} cont\'em 4 componentes:}

\begin{itemize}\Large
 \item Conjunto de passos (operadores do problema).
 \item Conjunto de ordena\c c\~oes da forma $S_i \prec S_j$.
 \item Conjunto de substitui\c c\~oes da forma $x=v$ ($v$ pode ser uma constante ou
         vari\'avel).
 \item Conjunto de liga\c c\~oes causais da forma $S_i \stackrel{c}{\rightarrow} S_j$,
         significando {\em $S_i$ atinge a precondi\c c\~ao $c$ para $S_j$}.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\LARGE Exemplo - operadores:}

\vspace*{.5cm}
\begin{enumerate}\Large
 \item[\ ] $\mbox{\em Op}(\mbox{\large ACTION}:\mbox{\em RightShoe},
                                      \mbox{\large PRECOND}:\mbox{\em RightSockOn},$ \\
                                      \hspace*{1cm}$\mbox{\large EFFECT}:\mbox{\em RightShoeOn})$
 \item[\ ] $\mbox{\em Op}(\mbox{\large ACTION}:\mbox{\em RightSock},
                                      \mbox{\large EFFECT}:\mbox{\em RightSockOn})$
 \item[\ ] $\mbox{\em Op}(\mbox{\large ACTION}:\mbox{\em LeftShoe},
                                      \mbox{\large PRECOND}:\mbox{\em LeftSockOn},$ \\
                                      \hspace*{1cm}$\mbox{\large EFFECT}:\mbox{\em LeftShoeOn})$
 \item[\ ] $\mbox{\em Op}(\mbox{\large ACTION}:\mbox{\em LeftSock},
                                      \mbox{\large EFFECT}:\mbox{\em LeftSockOn})$
\end{enumerate}

\vspace*{1cm}
\noindent {\LARGE Exemplo - plano (parcial) inicial:}

\vspace*{.5cm}
\begin{enumerate}\Large
 \item[\ ] $\mbox{\em Plan}(\mbox{\large STEPS}:\{S_1:\mbox{\em Op}(\mbox{\large ACTION}:\mbox{\em Start}),$ \\
                                                    \hspace*{3.6cm}  $S_2:\mbox{\em Op}(\mbox{\large ACTION}:\mbox{\em Finish},$ \\
                                                    \hspace*{5.6cm}              $\mbox{\large PRECOND}:\mbox{\em RightShoeOn}$ \\
                                                     \hspace*{8cm}                    $\wedge\mbox{\em LeftShoeOn})\},$ \\
              \hspace*{1.5cm}$\mbox{\large ORDERINGS}:\{S_1 \prec S_2\},$ \\
              \hspace*{1.5cm}$\mbox{\large BINDINGS}:\{\},$ \\
              \hspace*{1.5cm}$\mbox{\large LINKS}:\{\})$ \\
\end{enumerate}

\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\LARGE Plano inicial, graficamente:}

\vspace*{3cm}
\begin{center}
Figura 11.4
\end{center}

\vspace*{3cm}
\noindent {\LARGE O plano final:}

\vspace*{6.5cm}
\begin{center}
Figura 11.5
\end{center}


\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\LARGE Solu\c c\~oes:}

\begin{itemize}\Large
 \item {\bf Solu\c c\~ao:} um plano (parcial) {\em completo\/} e {\em consistente\/}.
 \item {\bf Plano completo:} toda precondi\c c\~ao de qualquer passo \'e garantida por algum
       outro passo e n\~ao \'e desfeita por outro.
 \item {\bf Plano consistente:} n\~ao h\'a contradi\c c\~ao na ordem dos passos
       ($S_i \prec S_j$ e $S_j \prec S_i$), e nem nas substitui\c c\~oes para as vari\'aveis
       ($v=A$ e $v=B$).
\end{itemize}

\vspace*{1cm}


\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\LARGE\bf Um exemplo:}

\begin{itemize}\Large
 \item Operador para definir estado inicial:

       $\mbox{\em Op}(\mbox{\large ACTION}: \mbox{\em Start},$ \\
       \hspace*{.8cm} $\mbox{\large EFFECT}: \mbox{at}(\mbox{Home})\wedge
                                             \mbox{sells}(\mbox{HWS},\mbox{Drill})\wedge$ \\
                         \hspace*{3.3cm}    $\mbox{sells}(\mbox{SM},\mbox{Milk})\wedge
                                         \mbox{sells}(\mbox{SM},\mbox{Banana})  )$
 \item Operador para definir estado meta:

       $\mbox{\em Op}(\mbox{\large ACTION}: \mbox{\em Finish},$ \\
       \hspace*{.8cm} $\mbox{\large PRECOND}: \mbox{have}(\mbox{Drill})\wedge
                                           \mbox{have}(\mbox{Milk})\wedge$ \\
                         \hspace*{3.8cm}   $\mbox{have}(\mbox{Banana})\wedge
                                           \mbox{at}(\mbox{Home}) )$
 \item A\c c\~oes:

       $\mbox{\em Op}(\mbox{\large ACTION}: \mbox{\em Go}(\mbox{\em there}),
                         \mbox{\large PRECOND}: \mbox{at}(\mbox{\em here}),$ \\
       \hspace*{.8cm} $\mbox{\large EFFECT}: \mbox{at}(\mbox{\em there})\wedge
                                           \neg\mbox{at}(\mbox{\em here}))$

       $\mbox{\em Op}(\mbox{\large ACTION}: \mbox{\em Buy}(x),$ \\
       \hspace*{.8cm} $\mbox{\large PRECOND}: \mbox{at}(\mbox{\em store})\wedge
                                              \mbox{sells}(\mbox{\em store},x),$ \\
       \hspace*{.8cm} $\mbox{\large EFFECT}: \mbox{have}(x))$

\end{itemize}

\vspace*{.5cm}
\noindent {\LARGE Plano inicial:}


\vspace*{3cm}
\begin{center}
Figura 11.6
\end{center}

\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\LARGE Satisfazendo 3 precondi\c c\~oes de {\em Finish\/} e as 3
precondi\c c\~oes {\em sells\/}:}

\vspace*{7cm}
\begin{center}
Figura 11.7
\end{center}

\vspace*{7cm}
\begin{enumerate}\Large
 \item[\ ] Seta grossa: liga\c c\~ao causal (protegida).
 \item[\ ] Seta fina: ordenamento.
\end{enumerate}

\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\LARGE Satisfazendo as precondi\c c\~oes {\em at\/} das a\c c\~oes
{\em Buy\/}:}

\vspace*{4.5cm}
\begin{center}
Figura 11.7
\end{center}

\vspace*{4.5cm}
\noindent {\LARGE Plano incorreto levando o agente ao HWS e ao SM:}

\vspace*{4cm}
\begin{center}
Figura 11.8
\end{center}

\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\LARGE Duas formas de resolver amea\c cas a uma liga\c c\~ao causal:}

\vspace*{4cm}
\begin{center}
 Figura 11.10
\end{center}

\vspace*{4cm}
\begin{enumerate}\Large
 \item[(b)] {\bf Rebaixamento} de $S_3$: $S_3 \prec S_1$.
 \item[(c)] {\bf Promo\c c\~ao} de $S_3$: $S_2 \prec S_3$.
\end{enumerate}

\vspace*{1cm}
\noindent {\Large N\~ao h\'a como resolver a amea\c ca do exemplo por ordena\c c\~ao:}

\begin{itemize}\Large
 \item O passo {\em Go\/} que vir antes elimina a precondi\c c\~ao $\mbox{at}(\mbox{Home})$
       do outro.
 \item Rebaixamento e promo\c c\~ao falhando: {\em backtracking}.
\end{itemize}

\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\LARGE Ap\'os remover $\mbox{\em Start}\stackrel{\mbox{at}(\mbox{Home})}{\longrightarrow}
\mbox{\em Go}(\mbox{SM})$:}

\begin{itemize} \Large
 \item Outra maneira de assegurar a precondi\c c\~ao $\mbox{at}(x)$ de $\mbox{\em Go}(\mbox{SM})$:
       adicionar $\mbox{\em Go}(\mbox{HWS})\stackrel{\mbox{at}(\mbox{HWS})}{\longrightarrow}
       \mbox{\em Go}(\mbox{SM})$, etc\ldots
\end{itemize}

\vspace*{5cm}
\begin{center}
 Figura 11.11
\end{center}

\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\Large Uma solu\c c\~ao:}

\vspace*{5cm}
\begin{center}
 Figura 11.12
\end{center}

\vfill
\hfill Cap\'{\i}tulo 11: Planejamento

\pagebreak
\noindent {\LARGE\bf O algoritmo POP:}

\vspace*{8cm}
\begin{center}
 Figura 11.13
\end{center}

\vfill
\hfill Cap\'{\i}tulo 11: Planejamento


\end{document}



