<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%====================================================================
\section{Introduction to the IvPBuild Toolbox}
%====================================================================
\wikisec{grp=extend,file=IvPBuildOverview,short=IvP Build Tools Overview}
\label{sec_bldu_intro}

The IvPBuild Toolbox is a set of C++ classes and algorithms for
building IvP functions. The primary objective is to provide tools to
the implementors of new helm behaviors that are fast and easy to use.
In the behavior implementation example in Listing
\ref{lst_bhv_simple_cpp_c}, the creation of an IvP function required
only about a dozen lines of code using two different methods available
in the IvPBuild Toolbox.

%====================================================================
\subsection{Brief Overview}

An instance of the class \var{IvPFunction} is the primary output of a
behavior on each helm iteration, and is comprised of anywhere from a
handful to thousands of "pieces" that approximate the utility
function of the behavior. An example IvP function approximating a
utility function is shown below in Figure \ref{fig_ipfview}.

\vspace{0.15in}
\begin{figure}[ht]
  \centering 
  \includegraphics[width=0.8\textwidth]{figures/ffview.png}
  \caption{{\bf An IvP function approximating an underlying function}:
    The \var{fview} tool is used to render an IvP function with 289
    pieces to approximate a given function, shown below the IvP
    function.}
  \label{fig_ipfview}
\end{figure}
\vspace{0.15in}

\noindent
The toolbox contains tools for making simple one-variable objective
functions (the "ZAIC" tools) as well as functions over N variables
(the "Reflector" tools). The primary contribution of the user
(behavior implementor) is to provide the underlying utility function
provided to the toolbox. The IvP function approximation is generated
automatically given user parameter preferences.

%---------------------------------------------------------------------
\subsubsection{Where to Get the IvPBuild Toolbox}

The IvPBuild Toolbox is part of the standard moos-ivp bundle
distributed from www.moos-ivp.org. See Section \ref{obtaining_ivp}. In
the software tree it is entirely contained in the module
\var{lib\_ivpbuild}.

%---------------------------------------------------------------------
\subsubsection{What is an Objective Function?}

An objective function is a function like any other, a mapping from a
domain to a range. In the case where the domain variables correspond
to decisions or choices, and the range corresponds to the utility with
respect to a particular user objective, the function is often called 
an "objective" function, or "utility" function.

%---------------------------------------------------------------------
\subsubsection{What is Multi-objective Optimization?} 

The term multi-objective optimization refers to a situation where there
are multiple objective functions defined over the same domain, i.e.,
decision space, and the ideal goal is to find a point in the decision
space that optimizes all functions simultaneously. Rarely is such a
mutually agreeable decision available and typically the functions can
be said to be "competing". Techniques vary widely on how to handle
this. A simple technique would be to rank order the functions and
optimize the most important first, and so on. Another technique
involves setting a competence threshold for each and choosing from
decisions that satisfy a minimum competence for each function.

%For an
%in-depth treatment see \cite{deb01}, \cite{kr93}, \cite{mie99},
%\cite{pir98}, \cite{pc97}, \cite{rie99}, \cite{ros97}, \cite{rt95}.

\vspace{0.1in}
\noindent
Many techniques for optimization are predicated on there being a user
involved in the decision process who can interactively alter
parameters of the problem until an agreeable resolution emerges. In
these cases the notion of Pareto optimality, \cite{par64}, often plays
a central role. A Pareto optimal solution is one that cannot be
improved in regard to one objective unless it comes at the expense of
another objective. Typical user-interactive multi-objective
optimization techniques involve letting the user explore the Pareto
frontier, i.e., those solutions that are all Pareto optimal differing
only on the user's value function or relative preference in importance
of objectives.

\vspace{0.1in}
\noindent
In repeatedly applying multi-objective optimization to the output of
behaviors in an on-board {\em autonomous} decision making system,
there is no user involved by definition. There is no exploration of
the Pareto frontier since that exploration requires a user. Instead,
part of the autonomy process involves also setting the value function,
i.e., the relative importance of objectives. In the IvP helm, this
value function is reflected by {\em priority weights} assigned to each
function, and the multi-objective optimization problem is reduced to 
a single objective optimization problem, given $k$ functions and $w_i$
being the weight of the $i$th function:

\vspace{0.1in}
\begin{figure}[H]
  \centering 
  \includegraphics[width=0.28\textwidth]{figures/argmax.png}
\end{figure}
\vspace{0.1in}

\noindent
The properties of IvP multi-objective optimization and solution
algorithms were discussed in Section \ref{sec_ivpsolver}.

%--------------------------------------------------------------------------
\subsubsection{What is an IvP Function?}

An IvP function is a piecewise linearly defined function where each
piece has an upper and lower boundary (or {\em interval}) on the
decision space and linear function defined over the piece. An IvP
function is defined over a domain that itself has an upper and lower
boundary for each decision variable. Furthermore, the domain is
comprised of equally spaced discrete points, and therefore each piece
is defined over a finite set of points in the domain. An IvP function
is typically an {\em approximation} of the user's underlying utility
function. The fidelity of this approximation can be controlled by the
user of the toolbox by deciding how many pieces are used in the
approximation. Since the size or extents of each piece may vary within
a function, the toolbox methods may also create functions that user
smaller pieces where the underlying function is less amenable to local
linear approximations. 

\vspace{0.1in}
\noindent
An IvP function as an instance of the \var{IvPFunction} class defined
as part of the \var{lib\_ivpcore} module included in the basic software
bundle distributed from \var{www.moos-ivp.org}.

%---------------------------------------------------------------------
\subsubsection{Why the IvP Function Construct? A Brief Description of the Solver}

The IvP function construct was chosen because it balances three
aspects needed for use in the extendable behavior-based autonomy
philosophy.

\begin{itemize}
\item Flexibility: a piecewise defined function approximation can be
  formed from any underlying function and thus the behavior author is
  not compelled to produce objective functions of a restricted form,
  such as convex or continuous functions. The behavior author is free
  to innovate. The behavior author typically has insight into the
  degree of fidelity needed to faithfully reflect the underlying
  utility function.
\item Speed: the IvP function constructs, once produced, can be
  exploited by solution algorithms to give very fast solutions with a
  guarantee of global optimality modulo the error introduced in
  function approximation. 
\item Accuracy: a piecewise defined function can be highly accurate
  for a few reasons, (a) by controlling the piece size and
  distribution the approximation can be made to be as accurate as
  needed. (b) by being free to approximate any underlying function
  form, a piecewise function may better reflect a behavior's utility. 
  (c) by allowing for guaranteed globally optimal solutions in the 
  resulting optimization problem, errors of this type are eliminated.
\end{itemize}

\vspace{0.1in}
\noindent
The IvP Solver uses a branch-and-bound method to search through the
combination space of pieces, one from each of k contributing
function. Since each point in the decision space is contained in
exactly one piece in each function, the optimal decision corresponds
to a k-tuple of pieces. Thus finding the optimal k-tuple
guarantees that the optimal point in the decision space has been
found. A leaf node in the tree is simply the "intersection" of
pieces from contributing functions. Likewise the intersection of
interior functions at a leaf node is simply the sum of the linear
functions of each contributing piece. Both the intersection of
rectilinear pieces and the sum of linear functions be rapidly and
simply computed. For a detailed description of the IvP solver solution
algorithms, see \cite{ben04}.

%---------------------------------------------------------------------
\subsubsection{Properties of the IvPDomain Class}
\label{sec_domain}

The domain of an IvP function is an instance of the class
\var{IvPDomain}.  It is the same between all functions produced by all
behaviors. The domain has a finite set of labeled variables with a
lower and upper bound for each variable, and an integer number of
evenly spaced points between the bounds.  The domain is also referred
to as the {\em decision space}. The 2D base of the cube in Figure
\ref{fig_ipfview} represents the domain.  A point in the domain is
contained in exactly one piece of an IvP function.  The domain is
built by the helm at the time of launch, and a copy is handed to each
behavior in its constructor to ensure uniformity between behaviors.
Listing \ref{example_domain} shows an example domain with three
variables as it would be specified within the MOOS configuration block
for the \app{pHelmIvP} process.  See Listing \ref{helmivp_block}.


\vspace{0.25in}
\begin{listing}{An IvP domain with three variables, as specified in \var{pHelmIvP} configuration}
\label{example_domain}
\scriptsize
\begin{verbatim}
 1  Domain  = course:0:359:360
 2  Domain  = speed:0:3:16
 3  Domain  = depth:0:500:101
\end{verbatim}
\end{listing}
\normalsize
\vspace{0.15in}

\noindent
Each line augments the initially null domain with a new variable.
The first of four arguments is the variable name, e.g., \var{course}. 
The second and third arguments indicate the lower and upper bound
of the variable. They are integers here, but could be floating point 
values. The last of four arguments is the number of points in the 
domain for that variable. This domain would have ($360 * 16 * 101$) 
581,760 distinct possible decisions.

\vspace{0.1in}
\noindent
The behavior author, using the IvPBuild Toolbox, only needs to create
a black-box function routine able to evaluate any point in the IvP
domain with respect to the objectives of that behavior. To use the
toolbox, this routine needs to reside within an implementation of a
class that subclasses the \var{AOF} class described in Section
\ref{sec_aof}. Although behaviors share a common domain, they can be
defined over a different subset of variables as long as the common
variables match in extents. For example, a behavior in a helm
configured with the domain above could be defined over the following
sub-domain:

\small
\begin{verbatim}
  Domain  = depth:0:500:101
\end{verbatim}
\normalsize

\noindent
It could not be defined over: 

\small
\begin{verbatim}
  Domain  = depth:0:100:101
\end{verbatim}
\normalsize

\noindent 
To facilitate the proper creation of sub-domains, the following
function is provided in the build toolbox (in \var{BuildUtils.h} in
\var{lib\_ivpbuild}):

\small
\begin{verbatim}
  IvPDomain  subDomain(IvPDomain original_domain, string variable_names);
\end{verbatim}
\normalsize

\noindent
The first argument is the original domain. The string argument is a
comma separated list of variable names to be included in the
sub-domain. If a variable is named in the argument that doesn't exist
in the original domain, an empty domain is returned. This is detected
by checking the size of the domain with a call to \var{domain.size()},
which returns the number of domain variables. A proper sub-domain of
the domain shown in Listing \ref{example_domain}, with only the
\var{depth} variable, could be created with the following function
call: 

\vspace{0.15in}
\small
\begin{verbatim}
  #include "BuildUtils.h"
   ...
  domain = subDomain(original_domain, "depth");
\end{verbatim}
\normalsize
\vspace{0.15in}

\noindent
It is common for a behavior to declare its sub-domain in its
constructor, even if it is expected to be the same as the total helm
domain.  See for example line 21 in Listing.

\vspace{0.1in}
\noindent
A call to \func{subDomain()} has no effect if it names all of the
original variables. By declaring a sub-domain in the behavior's
constructor, problems can be avoided later if the overall helm domain
is expanded. If the function call above erroneously creates a null
domain for the behavior, the helm detects this automatically in the
\func{isRunnable()} function call described in Section
\ref{sec_helm_overview}. This will cause an error message to be posted
to the \mvar{BHV\_ERROR} variable and result in the helm posting
all-stop values to its actuators.


%====================================================================
\subsection{Tools Available in the IvPBuild Toolbox}

The IvPBuild Toolbox contains a few different sets of tools. (a) The
ZAIC tool is used for creating IvP functions with only one decision
variable. (b) The basic Reflector tool is used for creating IvP
functions over N coupled variables. (c) The advanced Reflector tools
are an extension of the basic Reflector tools that allow for piecewise
defined functions with non-uniform pieces. (d) The Coupler tool allows
a pair of decoupled IvP functions to be converted to a single coupled
IvP function. (e) The encoding/decoding tools allow IvP functions to
be converted to a string representation and vice versa.


%---------------------------------------------------------------------
\subsubsection{The ZAIC Tools for Functions with One Variable}

The ZAIC tools are used for functions defined over a single decision
variable. An example is shown in Figure \ref{fig_onevaripf} where a
fictional behavior may want to keep the vehicle in the so-called "deep
sound channel" or "SOFOR (SOund Fixing and Ranging) channel".  This is
a horizontal layer in the ocean around which the speed of sound is at
a minimum and where sound, especially at low frequencies, may travel
for thousands of meters with little loss of signal (See \cite{url_sofar_wiki}).

\vspace{0.15in}
\begin{figure}[ht]
  \centering 
  \includegraphics[width=0.6\textwidth]{figures/one-var-ipf.png}
  \caption{{\bf An objective function with a single decision
      variable}: This function assigns a maximum utility to depths in
    a range of roughly $100 \pm 20$ meters. A linear decrease in
    utility is associated with depths outside this interval up to
    another additional 20 meters. }
 \label{fig_onevaripf}
\end{figure}
\vspace{0.15in}

\noindent
A piecewise defined IvP function can be constructed to represent this
function using five pieces. Assuming the "depth" decision space is 0
to 200 meters at one meter increments, the intervals would be:
[0,59], [60,79], [80,120], [121,140], [141,200]. The linear function
for each piece also needs to be set. This is not terribly difficult,
but it is tedious and prone to human error. Instead, the
{\zpeak} utility is a tool in the ZAIC toolbox used for
automating the production of IvP piecewise functions of the form shown
in Figure \ref{fig_onevaripf}.  It is described in Section
\ref{sec_bldu_zaics}.

%---------------------------------------------------------------------
\subsubsection{The Reflector Tool for Functions with Multiple Variables} 

The Reflector tool is used for creating IvP functions over n decision
variables where n is greater than two. The Reflector was used to
generate the IvP function rendered in Figure \ref{fig_ipfview}. The
tools do work for n=1, but one variable functions are typically
handled with the ZAIC tools described above. The Reflector produces an
IvP function approximation of a given underlying function, where the
underlying function is provided to the Reflector in the form of an
instance of a class containing the underlying function implementation,
and a specification of the IvP domain. The basic use of the Reflector
is described in detail in Section \ref{sec_bldu_reflector}, but the
basic usage boils down to the following:

\begin{packed_itemize}[2]
\item Create an instance of the underlying function to be
  approximated.  
\item Create an instance of the Reflector, passing it the underlying
  function.  
\item Invoke the Reflector with a requested number of pieces.
\item Retrieve the new IvP function from the Reflector.
\end{packed_itemize}

\noindent
The basic usage of the Reflector involves only the choosing the number
of pieces used in the IvP function representation. By choosing only
the number, pieces of uniform size will be used in the function. This
suffices for most applications, but there are ways to produce a
function that is both more accurate and uses less pieces by exploring
advanced options and algorithms of the Reflector. These include:

\begin{packed_itemize}[2]
\item The {\em Directed Refinement} Reflector option.  
\item The {\em Smart Refinement} Reflector option. 
\item The {\em AutoPeak Refinement} Reflector option.
\end{packed_itemize}

\vspace{0.1in}
\noindent
The details of these advanced options are discussed in Section
\ref{sec_bldu_advanced}.  Each of the advanced tools are used
after an initial basic uniform function has been generated.  The {\em
  directed refinement} option allows the user to specify subsets of
the domain and use pieces of different sizes for that region only. The
{\em smart refinement} option asks the Reflector to estimate the fit
of each piece as it is generated in terms of accuracy in approximating
the underlying function and performs further refinement on those
pieces that need it the most.  The {\em autopeak refinement} option
repeatedly refines the single piece containing the maxima of the
underlying function until that point is contained in a piece
containing only that point.

%------------------------------------------------------------------------
\subsubsection{The Coupler Tool for Coupling Two Decoupled IvP Functions}
\label{sec_coupler}

Two IvP functions defined over different variables can be combined to
form a single IvP function defined over the union of the two sets of
variables. The basic usage of the Coupler can be summarized as
follows:

\begin{packed_itemize}[2]
\item Create the two independent IvP functions. 
\item Create an instance of the \var{OF\_Coupler} class.
\item Pass the two functions to the Coupler. 
\item Retrieve the new IvP function from the Coupler.
\end{packed_itemize}

\noindent
This tool was used in the example SimpleWaypoint behavior of Section
\ref{sec_simple_wpt} in Listing \ref{lst_bhv_simple_cpp_d} to couple
two one-variable IvP functions. When a Coupler is passed the two IvP
function pointers, it takes over ownership of the functions, i.e., it
deletes the two one-variable functions when the Coupler object is
deleted. When a coupled IvP function is extracted from the Coupler,
ownship of the IvP function is passed to the caller, i.e., the caller
is responsible for deleting the IvP function.


%\subsection{GUI Applications for Experimenting with the Toolbox}

%\subsubsection{The {\tt zaicview} tool for Experimenting with the ZAIC Toolbox}

%\subsubsection{The {\tt ipfview} tool for Experimenting with the Reflector Toolbox}

</pre></body></html>