% $Id: preferences.tex 53363 2016-10-14 05:28:22Z torsten $
% $HeadURL: https://svn.cs.uni-potsdam.de/svn/reposWV/Lehre/ASP/trunk/Slides/preferences.tex $
%------------------------------------------------------------
\lecture{Preferences and optimization}{preferences}
%------------------------------------------------------------
\part{Preferences and optimization}
%------------------------------------------------------------
\newcommand{\pf}[0]{\ensuremath{\mathit{preference}}} % {\ensuremath{p}}
\newcommand{\name}[0]{\ensuremath{\mathit{name}}} % {\ensuremath{p}}
\newcommand{\Holds}[1]{\ensuremath{{H}_{#1}}}
%------------------------------------------------------------
\section{Motivation}
%------------------------------------------------------------
\begin{frame}{Motivation}
  \begin{itemize}
  \item<1-> 
    Preferences are pervasive
  \item<2-> 
    The identification of preferred, or optimal, solutions is often indispensable in real-world applications
  \item<2-> []
    In many cases, this also involves the combination of various qualitative and quantitative preferences
    \bigskip
  \item<3-> 
    Only optimization statements representing objective functions using sum or count aggregates are established components of ASP systems
    \smallskip
  \item<4-> \structure{Example} \ $\mathit{\#minimize}\{40:\mathit{sauna},70:\mathit{dive}\}$
  \end{itemize}
\end{frame}
%------------------------------------------------------------
\section{The asprin framework}
%------------------------------------------------------------
\begin{frame}{Approach}
  \begin{itemize}
  \item<1-> \structure{asprin} is a framework for handling preferences among the stable models of logic programs
    \begin{itemize}
    \item<2-> \structure{general} because it captures numerous existing approaches to preference from the literature
    \item<2-> \structure{flexible} because it allows for an easy implementation of new or extended existing approaches
    \end{itemize}
  \item<3-> \structure{asprin} builds upon advanced control capacities for incremental and meta solving,
    allowing for
    \begin{itemize}
    \item<4-> \structure{search for specific preferred solutions} without any modifications to the ASP solver
    \item<4-> \structure{continuous integrated solving process} significantly reducing redundancies
    \item<4-> \structure{high customizability} via an implementation through ordinary ASP encodings
    \end{itemize}
  \end{itemize}
\end{frame}
% ----------------------------------------------------------------------
\begin{frame}[c]{Example}
\begin{align*}
&\#\pf(\mathit{costs},\mathit{less(weight)})\{40:\mathit{sauna},70:\mathit{dive}\}\\
&\#\pf(\mathit{fun},\mathit{superset})\{\mathit{sauna},\mathit{dive},\mathit{hike},\naf{\mathit{bunji}}\}\\
&\#\pf(\mathit{temps},\mathit{aso})\{{\mathit{dive}>\mathit{sauna}}\,\|\,\mathit{hot}, {\mathit{sauna}>\mathit{dive}}\,\|\,\mathit{\neg{hot}}\}\\
&\#\pf(\mathit{all},\mathit{pareto})\{\name(\mathit{costs}),\name(\mathit{fun}),\name(\mathit{temps})\}\\[5pt]
&\#\mathit{optimize}(\mathit{all})
\end{align*}
\end{frame}
% ----------------------------------------------------------------------
\section{Preliminaries}
% ----------------------------------------------------------------------
\begin{frame}[c]{Preference}
  \begin{itemize}
  \item<1-> A strict partial order $\succ$ on the stable models of a logic program
  \item<2-> [] That is, $X\succ Y$ means that $X$ is preferred to $Y$
    \smallskip
  \item<3-> A stable model $X$ is $\succ$-\alert{preferred}, if there is no other stable model $Y$ such that $Y\succ X$
    \bigskip
  \item<4-> A \alert{preference type} is a (parametric) class of preference relations
  \end{itemize}
\end{frame}
% ----------------------------------------------------------------------
\section{Language}
% ----------------------------------------------------------------------
\begin{frame}[c]{Language}
  \begin{itemize}
  \item \structure{weighted formula}
    \(
    {w_1,\dots,w_l}:\phi
    \)

    {\small where each $w_i$ is a term and $\phi$ is a Boolean formula}
  \item \structure{naming atom} $\name(s)$ 

    {\small where $s$ is the name of a preference}
  \item \structure{preference element}
    \(
    {\Phi_1>\dots>\Phi_m}\;\|\;\Phi
    \)

    {\small where each $\Phi_r$ is a set of weighted formulas and $\Phi$ is a non-weighted formula}
  \item \structure{preference statement}
    \(
    \#\pf(s,t)\{e_1,\dots,e_n\}
    \)

    {\small where $s$ and $t$ represent the preference statement and its type\\ and each $e_j$ is a preference element}
    \medskip
  \item<2-> \structure{optimization directive}
    \(
    \#\mathit{optimize}(s)
    \)
    
    {\small where $s$ is the name of a preference}
    \medskip
  \item<3-> \structure{preference specification} 
    {\small
    is a set $S$ of preference statements and a directive $\#\mathit{optimize}(s)$ 
    such that $S$ is an acyclic, closed, and $s\in S$}
\end{itemize}
\end{frame}
% ----------------------------------------------------------------------
\begin{frame}[c]{Preference type}
  \begin{itemize}
  \item<1-> A \alert{preference type} $t$ is a function
    mapping a set of preference elements, $E$, 
    to a (strict) preference relation,
    \(
    t(E)
    \),
    on sets of atoms 
    \smallskip
  \item<2-> The domain of $t$, $\mathit{dom}(t)$, fixes its admissible preference elements
    \medskip
  \item<3-> \structure{Example} $\mathit{less(cardinality)}$
    \begin{itemize}\normalsize
    \item <4->
      \(
      (X,Y)\in{\mathit{less(cardinality)}}(E)
      \)
      \par\qquad\qquad \ if 
      \(
      |\{l\in E\mid X\models l\}|<|\{l\in E\mid Y\models l\}|
      \)
      \smallskip
    \item <5-> $\mathit{dom}(\mathit{less(cardinality)})=\mathcal{P}(\{a,\neg a\mid a\in\mathcal{A}\})$
      \par\small (where $\mathcal{P}(X)$ denotes the power set of $X$)
    \end{itemize}
  \end{itemize}
\end{frame}
% ----------------------------------------------------------------------
\begin{frame}[c]{More examples}
\small
\begin{itemize}
\item $\mathit{more(weight)}$ is defined as
  \begin{itemize}
  \item \footnotesize
    \(
    (X,Y)\in{\mathit{more(weight)}}(E)\text{ if }\sum_{(w:l)\in E,X\models l}w>\sum_{(w:l)\in E,Y\models l}w
    \)
  \item $\mathit{dom}(\mathit{more(weight)})=\mathcal{P}(\{w:a,w:\neg a\mid w\in\mathbb{Z},a\in\mathcal{A}\})$; and % for the domain of single weighted literals;
\end{itemize}
\item $\mathit{subset}$ is defined as
  \begin{itemize}
  \item \footnotesize
  \(
  (X,Y)\in{\mathit{subset}}(E)\text{ if }\{ l\in E\mid X\models l\}\subset\{ l\in E\mid Y\models l\}
  \)
\item $\mathit{dom}(\mathit{less(cardinality)})=\mathcal{P}(\{a,\neg a\mid a\in\mathcal{A}\})$. %  for the domain of regular literals.
\end{itemize}
\item $\mathit{pareto}$ is defined as
  \begin{itemize}
  \item\footnotesize 
    \(
    (X,Y)\in{\mathit{pareto}}(E)
    \text{ if }
    \bigwedge_{\name(s)\in E} (X\succeq_s Y)\wedge\bigvee_{\name(s)\in E} (X\succ_s Y)
    \)    
  \item $\mathit{dom}(\mathit{pareto})=\mathcal{P}(\{n\mid n\in N\})$;
  \end{itemize}
\item $\mathit{lexico}$ is defined as
  \begin{itemize}
  \item\footnotesize
    \(
    (X,Y)\in{\mathit{lexico}}(E)
    \text{ if } 
    \bigvee_{w:\name(s)\in E}\big((X\succ_s Y)\wedge\bigwedge_{v:\name(s')\in E,v<w}(X =_{s'} Y)\big)
    \)
  \item $\mathit{dom}(\mathit{lexico})=\mathcal{P}(\{w:n\mid w\in\mathbb{Z},n\in N\})$.
  \end{itemize}
\end{itemize}
\end{frame}
% ----------------------------------------------------------------------
\begin{frame}[c]{Preference relation}
  \begin{itemize}
  \item<1-> 
    A \alert{preference relation} is obtained by applying a preference type to an admissible set of preference elements
    \medskip
  \item<2-> $\#\pf(s,t)\,E$ declares preference relation $t(E)$
    \pause
    denoted by $\succ_s$
    \bigskip
  \item<3-> \structure{Example} $\#\pf(1,\mathit{less(cardinality)})\{a,\neg{b},c\}$) \ declares
    \[
    X\succ_1 Y \text{ as } |\{ l\in\{a,\neg{b},c\}\mid X\models l\}|<|\{ l\in\{a,\neg{b},c\}\mid Y\models l\}|
    \]
    where $\succ_1$ stands for $\mathit{less(cardinality)}(\{a,\neg{b},c\})$

  \end{itemize}
\end{frame}
% ----------------------------------------------------------------------
\section{Implementation}
% ----------------------------------------------------------------------
\begin{frame}[c]{Preference program}
  \begin{itemize}
  \item<1-> \structure{Reification}
    \(
    \Holds{X}=\{\mathit{holds}(a)            \mid a\in        X\}
    \)
    and 
    \(
    \Holds{X}'=\{\mathit{holds}'(a)\mid              a\in       X  \}
    \)
    \medskip
  \item<2-> \structure{Preference program}
    Let $s$ be a preference statement declaring $\succ_s$ 
    \par
    and
    let $P_s$ be a logic program
    
    \medskip
    We define
    \(
    P_s
    \)
    as a \alert{preference program} for $s$, if for all sets $X,Y\subseteq\mathcal{A}$, we have
    \[
    X\succ_s Y
    \ \text{ iff } \
    P_s % E_{t_s}\cup F_s\cup A 
    \cup \Holds{X} \cup \Holds{Y}'
    \text{ is satisfiable}
    \]
    \medskip
  \item<3-> \structure{Note} $P_s$ usually consists of an encoding $E_{t_s}$ of ${t_s}$, 
    facts $F_s$ representing the preference statement, and auxiliary rules $A$
  \item<4-> \structure{Note} Dynamic versions of \Holds{X} and \Holds{Y} must be used for optimization
  \end{itemize}
\end{frame}
% ---------------------------------------------------------------------
\begin{frame}[fragile]{$\#\pf(3,\mathit{subset})\{a,\neg{b},c\}$}
\pause
\[
\begin{array}{l@{}c@{\;}l}
E_{\mathit{subset}}&=&
\left\{\
\begin{minipage}{0.71\linewidth}
\begin{lstlisting}[basicstyle=\ttfamily\tiny]
better(P) :- preference(P,subset),
             holds'(X) : preference(P,_,_,for(X),_), holds(X);
             1 #sum { 1,X : not holds(X), holds'(X), 
                            preference(P,_,_,for(X),_) }.
\end{lstlisting}
\end{minipage}
\right\}
\\[10pt]
F_{3}&=&
\left\{\
\begin{minipage}{0.71\linewidth}
\begin{lstlisting}[basicstyle=\ttfamily\tiny]
preference(3,subset).   preference(3,1,1,for(a),()).
                        preference(3,2,1,for(neg(b)),()).
                        preference(3,3,1,for(c),()).
\end{lstlisting}
\end{minipage}
\right\}
\\[10pt]
A&=&
\left\{\
\begin{minipage}{0.71\linewidth}
\begin{lstlisting}[basicstyle=\ttfamily\tiny]
holds(neg(A))  :- not holds(A), preference(_,_,_,for(neg(A)),_).
holds'(neg(A)) :- not holds'(A),preference(_,_,_,for(neg(A)),_).
\end{lstlisting}
\end{minipage}
\right\}
\\[10pt]
H_{\{a, b\}}&=&
\left\{\
\begin{minipage}{0.71\linewidth}
\begin{lstlisting}[basicstyle=\ttfamily\tiny]
holds(a).  holds(b).
\end{lstlisting}
\end{minipage}
\right\}
\\[10pt]
H'_{\{a\}}&=&
\left\{\
\begin{minipage}{0.71\linewidth}
\begin{lstlisting}[basicstyle=\ttfamily\tiny]
holds'(a).
\end{lstlisting}
\end{minipage}
\right\}
\end{array}
\]
We get a stable model containing \lstinline{better(3)} indicating that $\{a, b\}\succ_3\{a\}$,
or $\{a\}\subset\{a,\neg b\}$
\end{frame}
% ----------------------------------------------------------------------
\begin{frame}[c]{Basic algorithm $\mathit{solveOpt}(P,s)$}
  \begin{algorithm}[H]
  \Input{A program $P$ over $\mathcal{A}$ and preference statement $s$}
  \Output{A $\succ_s$-preferred stable model of $P$, if $P$ is satisfiable, and $\bot$ otherwise}
  \BlankLine
  $Y \leftarrow \mathit{solve}(P)$\;
  \lIf{$Y = \bot$}{\Return $\bot$}\;
  \Repeat{$Y = \bot$}{%
    $X \leftarrow Y$\;
    $Y  \leftarrow \mathit{solve}(P\cup E_{t_s}\cup F_{s} \cup R_{\mathcal{A}} \cup \Holds{X}')\cap\mathcal{A}$\;
  }
  \Return $X$
\end{algorithm}

\bigskip

where 
\(
R_{X}=\{\mathit{holds}(a)\leftarrow a\mid a\in X\}
\)
\end{frame}
% ----------------------------------------------------------------------
\begin{frame}[fragile,fragile]{Sketched Python Implementation}
\tiny
\begin{semiverbatim}
#script (python)

from gringo import *
holds = []

def getHolds():
    global holds
    return holds

def onModel(model):
    global holds
    holds = []
    for a in model.atoms():
        if (a.name() == "_holds"): holds.append(a.args()[0])
\alert<2>{
def main(prg):
    step = 1
    prg.ground([("base", [])])
    while True:
        if step > 1: prg.ground([("doholds",[step-1]),("preference",[0,step-1])]
        ret = prg.solve(on_model=onModel)
        if ret == SolveResult.UNSAT: break
        step = step+1
#end.}

#program base.                     #program doholds(m).
#show _holds(X,0) : _holds(X,0).   _holds(X,m) :- X = @getHolds().

#end.
\end{semiverbatim}
\end{frame}
% ----------------------------------------------------------------------
\begin{frame}[fragile]{Vanilla \texttt{minimize} statements}
\bigskip
  \begin{itemize}
  \item Emulating the \texttt{minimize} statement
    \medskip
\begin{semiverbatim}
   #minimize \{ C,X,Y : cycle(X,Y), cost(X,Y,C) \}.
\end{semiverbatim}

    \medskip
  \item[] in \asprin\ amounts to
    \medskip
\begin{semiverbatim}
   #preference(myminimize,less(weight))
             \{ C,(X,Y) :: cycle(X,Y) : cost(X,Y,C) \}.
   #optimize(myminimize).
\end{semiverbatim}
\bigskip
  \item<2-> \structure{Note} \asprin\ separates the declaration of preferences from
    the actual optimization directive
  \end{itemize}
\end{frame}
% ----------------------------------------------------------------------
\begin{frame}[fragile]{Example\\[-5pt]\normalsize\small in \asprin's input language}
\small
\begin{semiverbatim}
   #preference(costs,less(weight))\{
     C :: sauna : cost(sauna,C); 
     C ::  dive : cost(dive,C) 
   \}.
   #preference(fun,superset)\{ sauna; dive; hike; not bunji \}.
   #preference(temps,aso)\{
     dive > sauna ||     hot; 
    sauna > dive  || not hot
   \}.
   #preference(all,pareto)\{name(costs); name(fun); name(temps)\}.
   
   #optimize(all).
\end{semiverbatim}
\end{frame}
% ----------------------------------------------------------------------
\begin{frame}{\asprin's library}
  \begin{itemize}
  \item<1-> \structure{Basic preference types}
    \begin{itemize}
    \item  \texttt{subset} and \texttt{superset}   
    \item  \texttt{less(cardinality)} and \texttt{more(cardinality)}   
    \item  \texttt{less(weight)} and \texttt{more(weight)}   
    \item  \texttt{aso}   (Answer Set Optimization) \nocite{brnitr03a}
    \item  \texttt{poset} (Qualitative Preferences) \nocite{rogima10a}
    \end{itemize}    
  \item<2-> \structure{Composite preference types} \nocite{sonpon06a}
    \begin{itemize}
    \item \texttt{neg}
    \item \texttt{and}
    \item \texttt{pareto}
    \item \texttt{lexico}
    \end{itemize}
  \item<3-> See \textit{Potassco Guide} on how to define further types
  \end{itemize}
\end{frame}
% ----------------------------------------------------------------------
\section{Summary}
% ---------------------------------------------------------------------
\begin{frame}[c]{Summary}
  \begin{itemize}
  \item<2-> \structure{asprin} stands for ``\alert{AS}P for \alert{Pr}eference handl\alert{in}g''
    \smallskip
  \item<3-> \structure{asprin} is a general, flexible, and extendable framework for\\ preference handling in ASP
    \smallskip
  \item<3-> \structure{asprin} caters to
    \begin{itemize}
    \item \structure{off-the-shelf users} using the preference relations in \textit{asprin}'s library
    \item \structure{preference engineers} customizing their own preference relations
    \end{itemize}
  %   \bigskip
  % \item<4-> \url{http://potassco.org/labs\#asprin}
  \end{itemize}
\end{frame}
% ---------------------------------------------------------------------

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "asp"
%%% End:
