\documentclass{article}

\newcommand{\ang}[1]{#1^{\circ}}
\newcommand{\mywhile}{{\bf while} }
\newcommand{\myif}{{\bf if} }
\newcommand{\mythen}{{\bf then} }
\newcommand{\mydo}{{\bf do} }
\newcommand{\myreturn}{{\bf return} }
\newcommand{\myfor}{{\bf for} }
\newcommand{\myuntil}{{\bf until} }
\newcommand{\myelse}{{\bf else} }
\newcommand{\mynot}{{\bf not} }
\newcommand{\myand}{{\bf and} }
\newcommand{\myor}{{\bf or} }
\newcommand{\mytrue}{{\bf true} }
\newcommand{\myfalse}{{\bf false} }
\newcommand{\myprocedure}{{\bf procedure} }
\newcommand{\mygoal}{{\bf goal state} }
\newcommand{\mycur}{{\bf current state} }
\newcommand{\mysame}{{\bf same} }
\newcommand{\ingoal}{{\bf in\_goal\_state} }
\newcommand{\incur}{{\bf in\_current\_state} }
\newcommand{\ininit}{{\bf in\_initial\_state} }
\newcommand{\suchthat}{{\bf such that} }
\newcommand{\myassign}{$\leftarrow$ }
\newcommand{\distill}{{\sc Distill} }
\newcommand{\fixme}[1]{}


\title{Loop Notes}
%\author{Elly Zoe Winner and Manuela Veloso}

\begin{document}

\date{}
\maketitle

\begin{table}[ht!]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
{\bf Input}: Minimal annotated consistent partial order $\cal P$\\
{\bf Output}: Template $T$ representing $\cal P$\\
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
\myprocedure Convert\_To\_Template($\cal P$):\\
\> $T$.conditions \myassign Find\_Relevant\_Current($\cal P$) $+$ Find\_Relevant\_Goal($\cal$)\\
\> $T$.body \myassign $\cal P$\\
\> Identify\_Loops($T$)\\
\\
\myprocedure Identify\_Loops($T$):\\
\> change \myassign \mytrue \\
\> \mywhile(change) \mydo \\
\> \> change \myassign \myfalse \\
\> \> $\forall$ fan outs\\
\> \> \> $\forall$ fans with same sequences:\\
\> \> \> \> identify varying parameter(s),\\
\> \> \> \> introduce new variable for them\\
\> \> \> \> \myif fans then have same init conds \& results \mythen \\
\> \> \> \> \> newloop \myassign empty while loop\\
\> \> \> \> \> newloop.conditions \myassign fans.init conds \& results\\
\> \> \> \> \> newloop.body \myassign fan.sequence\\
\> \> \> \> \> replace similar fans with newloop\\
\> \> \> \> \> reconnect condition and result arcs\\
\> \> \> \> \> change \myassign \mytrue\\
\> \> $\forall$ sequences\\
\> \> \> use string-matching algs to find repeated seqs\\
\> \> \> $\forall$ repeated sequences\\
\> \> \> \> \myif last repetition has different outcome \mythen\\
\> \> \> \> \> identify varying parameter(s) (if any)\\
\> \> \> \> \> introduce new variable for them\\
\> \> \> \> \> newloop \myassign empty while loop\\
\> \> \> \> \> newloop.conditions \myassign \mynot last outcome \myand
any common conditions\\
\> \> \> \> \> newloop.body \myassign sequence\\
\> \> \> \> \> change \myassign \mytrue
\end{tabbing}
\hrule
}}
\caption{Converting a plan into a template with loops}
\label{alg:convertToLoops}
\end{table}


\begin{table}[htb]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
\mywhile ((\incur({\sf at(v?1:obj v?2:loc)}) \myor \\
\> \> \> \incur({\sf inside(v?1:obj v?4:rocket)})) \myand \\
\> \> (\ingoal({\sf at(v?1:obj v?3:loc)}) \myor \\
\> \> \> \ingoal({\sf inside(v?1:obj v?4:rocket)}))) \mydo \\
\> \myif (\incur({\sf at(?1:obj ?2:loc)}) \myand \\
\> \> \> \incur({\sf at(?4:rocket ?5:loc)})) \mythen \\
\> \> {\sf move(?4:rocket ?5:loc ?2:loc)}\\
%\> {\sf load(?1:obj ?4:rocket ?2:loc)}\\
\> \mywhile (\incur({\sf at(v?6:obj ?2:loc)}) \myand \\
\> \> \> \incur({\sf at(?4:rocket ?2:loc)}) \myand \\
\> \> \> (\ingoal({\sf at(v?6:obj v?7:loc)}) \myor \\
\> \> \> \> \ingoal({\sf inside(v?6:obj ?4:rocket)}))) \mydo\\
\> \> {\sf load(?6:obj ?4:rocket ?2:loc)} \\
\> \mywhile (\incur({\sf inside(v?6:obj ?4:rocket)}) \myand \\
\> \> \> \incur({\sf at(?4:rocket ?2:loc)}) \myand \\
\> \> \> \ingoal({\sf at(v?6:obj ?2:loc)})) \mydo \\
\> \> {\sf unload(?6:obj ?4:rocket ?2:loc)} \\
\mywhile (\incur({\sf inside(v?1:obj v?2:rocket)}) \myand \\
\> \> \incur({\sf at(v?2:rocket v?3:loc)}) \myand \\
\> \> \ingoal({\sf at(v?1:obj v?4:loc)})) \mydo \\
\> {\sf move(?2:rocket ?3:loc ?4:loc)} \\
\> \mywhile (\incur({\sf inside(v?5:obj ?2:rocket)}) \myand \\
\> \> \> \ingoal({\sf at(v?5:obj ?4:loc)})) \mydo \\
\> \> {\sf unload(?5:obj ?2:rocket ?4:loc)} \\
\mywhile (\incur({\sf at(v?1:rocket v?2:loc)}) \myand \\
\> \> \ingoal({\sf at(v?1:rocket v?3:loc)})) \mydo \\
\> {\sf move(?1:rocket ?2:loc ?3:loc)}
\end{tabbing}
\hrule
}}
\caption{Rocket domain template}
\label{alg:rocket}
\end{table}


\begin{table}[htb]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
% get packages that need to be broken to appropriate locs
\mywhile (\mynot(\incur({\sf broken(v?1:package)})) \myand \\
\> \> \incur({\sf at(v?1:package v?2:loc)}) \myand \\
\> \> \ingoal({\sf broken(v?1:package)})) \mydo \\
% if their current loc isn't going to blow
\> \myif (\mynot(\ingoal({\sf blownup(?2:loc)})) \myor \\
\> \> \> (\ingoal({\sf blownup(?2:loc)}) \myand \\
\> \> \> \> \incur({\sf blownup(?2:loc)}))) \mythen \\
% if their goal loc IS going to blow, move them there
\> \> \myif (\ingoal({\sf at(?1:package ?3:loc)}) \myand \\
\> \> \> \> \ingoal({\sf blownup(?3:loc)}) \myand \\
\> \> \> \> \mynot(\incur({\sf blownup(?3:loc)}))) \mythen \\
\> \> \> {\sf move(?1:package ?2:loc ?3:loc)} \\
% o.w. move them somewhere that is going to blow
\> \> \myelse \myif (\ingoal({\sf blownup(?3:loc)}) \myand \\
\> \> \> \> \mynot(\incur({\sf blownup(?3:loc)}))) \mythen \\
\> \> \> {\sf move(?1:package ?2:loc ?3:loc)} \\
% o.w. if cur loc can't blow, move them somewhere that can
\> \> \myelse \myif (\ingoal(\mynot({\sf blownup(?2:loc)})) \myand
\> \> \> \> (\mynot(\ingoal(\mynot({\sf blownup(?3:loc)})))) \mythen \\
\> \> \> {\sf move(?1:package ?2:loc ?3:loc)} \\
% blow locs that need blowing
\mywhile (\ingoal({\sf blownup(v?1:loc)}) \myand \\
\> \> \mynot(\incur({\sf blownup(v?1:loc)}))) \mydo \\
% but first get packages that need not to blow out
\> \mywhile (\incur({\sf at(v?2:package ?1:loc)}) \myand \\
\> \> \> \ingoal(\mynot({\sf broken(?2:package)}))) \mydo \\
% if their goal loc isn't going to blow or is already blown, put them there
\> \> \myif (\ingoal({\sf at(?2:package ?3:loc)}) \myand \\
\> \> \> \> (\mynot(\ingoal({\sf blownup(?3:loc)})) \myor \\
\> \> \> \> \> \incur({\sf blownup(?3:loc)}))) \mythen \\
\> \> \> {\sf move(?2:package ?1:loc ?3:loc)} \\
% o.w. if there's somewhere that's already blown, put them there
\> \> \myelse \myif (\incur({\sf blownup(?3:loc)})) \mythen \\
\> \> \> {\sf move(?2:package ?1:loc ?3:loc)} \\
% o.w. if there's somewhere that doesn't have to blow, put them there
\> \> \myelse \myif (\mynot(\ingoal({\sf blownup(?3:loc)}))) \\
\> \> \> {\sf move(?2:package ?1:loc ?3:loc)} \\
% o.w. just put them somewhere else
\> \> {\sf move(?2:package ?1:loc ?3:loc)}\\
%\> \> \myelse \myif (\ingoal({\sf blownup(?3:loc)})) \\
%\> \> \> {\sf move(?2:package ?1:loc ?3:loc)} \\
% blow locs that need blowing
\> {\sf blow(?1:loc)}
% blow locs with packages that need blowing
% loc package is at is already guaranteed to be blowable
\mywhile (\incur({\sf at(v?1:package v?2:loc)}) \myand \\
\> \> \ingoal({\sf broken(v?1:package)}) \myand \\
\> \> \mynot(\incur({\sf broken(v?1:package)}))) \mythen \\
\> \mywhile (\incur({\sf at(v?3:package v?2:loc)}) \myand \\
\> \> \> \ingoal(\mynot({\sf broken(v?3:package)}))) \mythen \\
\> \> {\sf move(?3:package ?2:loc ?4:loc)} \\
\> {\sf blow(?2:loc)} \\
% move packages to correct final dests
\mywhile (\incur({\sf at(v?1:package v?2:loc)}) \myand \\
\> \> \ingoal({\sf at(v?1:package v?3:loc)})) \mydo \\
\> {\sf move(?1:package ?2:loc ?3:loc)}
\end{tabbing}
\hrule
}}
\caption{Bomb domain template}
\label{alg:bomb}
\end{table}


\begin{table}[htb]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
generate intermediate states btw steps by propagating init state forward\\
identify CEs that do occur\\
\myfor each step \mydo\\
\> \myfor each precondition of it \mydo \\
\> \> find last provider of precondition\\
\> \> add link between provider and this step\\
\> \> \myif precondition added by active CE \mythen\\
\> \> \> add conditions of active CE to that step's precs
\end{tabbing}
\hrule
}}
\caption{Poly-time algorithm for finding MAC POs}
\label{alg:fastsprawl}
\end{table}


Worrisome issues:
\begin{itemize}
 \item How to handle whiles with not-quite-matching bodies (whiles
  with nested ifs)? ---there's a line somewhere about how aggressively
  we should merge things, but not sure where it is.
 \item If this is going to work as an watch-and-learn system WITHOUT
  guaranteed super-nice-and-wise teachers, we have to relax requirements
  on form of observed examples. How can we learn templates from
  inconsistent examples, examples with messy/difficult orderings,
  optimal examples, etc?
 \item Class of problems/domains attacking?
 \item Will we be able to say ANYTHING about efficiency?
\end{itemize}

Professed goals:
\begin{itemize}
 \item Learn dom-spec planner from super-nice-and-wise teacher
 \item Learn to solve ``some'' problems faster than g-p planning
 \item Learn to solve more of ``some'' problems than g-p planning
  (horizon!)
 \item Use for agent modelling (develop example domain(s))
 \item Any impact/help in multi-agent situation(s)? (not sure how)
 \item Can we learn dom-spec planner from non-super-nice-and-wise teacher?
\end{itemize}

Issues to remind folks of:
\begin{itemize}
 \item Folks have done work on revealing domain operators (mei wang)
 \item Folks have done work on speeding up subop plans (knoblock)
\end{itemize}

Schedule (a.k.a. To Do list):
\begin{itemize}
% \item Work out poly {\sc Sprawl} solution
 \item Rewrite {\sc Sprawl} paper to include poly solution (almost done!)
 \item Hand-write templates for all '00 \& 02 domains
 \item Decide what to do about difficult issue \#1 (handling loops of
  non-identical steps (whiles with nested ifs)) \&/or if it needs to
  be addressed right now
 \item Lure unsuspecting committee members (Manuela (hah! already
  trapped!), Reid, Avrim or Steve Smith, Craig) with appealing
  extended abstract
 \item Write up proposal
 \item Read a bunch more papers! (including the ones suggested by Dan
  Weld \& by Avrim)
 \item Give proposal talk
 \item Clean up \& mass-market {\sc Sprawl}
  \begin{itemize}
   \item Detach from FF
   \item Implement poly solution
   \item Add saving needs tree
  \end{itemize}
 \item Implement proposed while loop stuff (hah!)
 \item Clean up template language
 \item Save template in form of c program
 \item Hang moon
 \item DEFEND!
 \item Parrr-tay
\end{itemize}


\begin{table}[ht!]
\hrule
{\small
\noindent\begin{tabbing}
\=~~~~~~~~~~\=\=\+\kill
{\bf Input}: Minimal annotated consistent partial order $\cal P$,\\
\> current template $T_i$.\\
{\bf Output}: New template $T_{i+1}$, updated with $\cal P$\\
\end{tabbing}
\vspace{-0.5cm}
{\small
\begin{tabbing}
\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=~~~~~~\=\+\kill
\myprocedure \distill($\cal P$, $T_i$):\\
\> $\cal A$ \myassign Find\_Variable\_Assignment($\cal P$,
${T_i}.variables$, $\emptyset$)\\
\> \myuntil match \myor can't match \mydo \\
\> \> \myif $\cal A = \emptyset$ \mythen \\
\> \> \> can't match \\
\> \> \myelse \\
\> \> \> $\cal N$ \myassign Make\_New\_If\_Statement(Assign($\cal P$, $\cal A$))\\
\> \> \> match \myassign Is\_A\_Match($\cal N$, $T_i$) \\
\> \> \myif \mynot can't match \myand \mynot match \mythen \\
\> \> \> $\cal A$ \myassign Find\_Variable\_Assignment($\cal P$, ${T_i}.variables$, $\cal A$) \\
\> \myif can't match \mythen \\
\> \> $\cal A$ \myassign Find\_Variable\_Assignment($\cal P$, ${T_i}.variables$, $\emptyset$) \\
\> \> $\cal N$ \myassign Make\_New\_If\_Statement(Assign($\cal P$, $\cal A$))\\
\> $T_{i+1}$ \myassign Add\_To\_Template($\cal N$, $T_i$) \\
\\
\myprocedure Make\_New\_If\_Statement($\cal P_{\cal A}$):\\
\> $N$ \myassign empty if statement\\
\> \myfor all terms $t_m$ in initial state of $\cal P_{\cal A}$ \mydo \\
\> \> \myif exists a step $s_n$ in plan body of $\cal P_{\cal A}$
\suchthat \\
\> \> \> \> $s_n$ needs $t_m$ \myor goal state of $\cal P_{\cal A}$
needs $t_m$ \mythen \\
\> \> \> Add\_To\_Conditions($N$, \incur($t_m$))\\
\> \myfor all terms $t_m$ in goal state of $\cal P_{\cal A}$ \mydo \\
\> \> \myif exists a step $s_n$ in plan body of $\cal P_{\cal A}$ \suchthat \\
\> \> \> \> $t_m$ relies on $s_n$ \mythen \\
\> \> \> Add\_To\_Conditions($N$, \ingoal($t_m$))\\
\> \myfor all steps $s_n$ in plan body of $\cal P_{\cal A}$ \mydo \\
\> \> Add\_To\_Body($N$, $s_n$)\\
\> \myreturn $N$\\
\\
\myprocedure Is\_A\_Match($\cal N$, $T_i$):\\
\> \myfor all if-statements $I_n$ in $T_i$ \mydo\\
\> \> \myif $\cal N$ matches of $I_n$ \mythen\\
\> \> \> \myreturn \mytrue\\
\\
\myprocedure Add\_To\_Template($\cal N$, $T_i$):\\
\> \myfor all if-statements $I_n$ in $T_i$ \mydo\\
\> \> \myif $\cal N$ matches $I_n$ \mythen\\
\> \> \> $I_n$ \myassign Combine($I_n$, $\cal N$)\\
\> \> \> \myreturn\\
\> \myif $\cal N$ is unmatched \mythen\\
\> \> Add\_To\_End($\cal N$, $T_i$)\\
\end{tabbing}
\hrule
}}
\caption{The current \distill algorithm: updating a template with a new observed plan.}
\label{alg:curdistill}
\end{table}



\end{document}