<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%=====================================================================
\section{Optional Advanced Features of the Reflector Tool}
%=====================================================================
\wikisec{grp=extend,file=ReflectorToolsAdvance,short=Advanced Reflector Tools}
\label{sec_bldu_advanced}
\index{Reflector!Advanced Features}

%=====================================================================
\subsection{Preliminaries}

The previous section discussed how to build IvP functions with the
\var{Reflector} tool in the IvP Build Toolbox by simply specifying
a desired number of pieces in the resulting piecewise defined
function.  This section discusses a few further methods for building
functions that give the user more control of the build process and
typically better overall results in terms of fewer pieces, less time
to build, and greater accuracy in the piecewise approximation of the
underlying function.

%----------------------------------------------------------------------
\subsubsection{The Reflector-Script}
\label{sec_reflector_script}
\index{IvPBuild Toolbox!Reflector Script}
\index{Reflector Script}

The basic invocation of the Reflector \func{create()} function may
take a single argument requesting the number of pieces to be used in
the piecewise function. An example is line 15 in Listing
\ref{uniform_alpha}.  In reality the invocation of \func{create()} is
comprised of a {\em script} of distinct build heuristics of which the
creation of uniform sized pieces is just the first of four parts. The
latter three parts are optional and require further user configuration
before being included for execution in the script. The four parts are:

\begin{packed_itemize}[2]
\item Uniform function creation
\item Directed refinement
\item Smart refinement
\item Auto-Peak refinement
\end{packed_itemize}

\index{Directed Refinement}
\index{Smart Refinement}
\index{AutoPeak Refinement}

These four heuristics are discussed in the next four sections. Uniform
function creation is revisited since finer control can be used (with
typically better results) if the choice of piece size and shape is not
left to the heuristic that converts the requested total number of pieces
into an actual uniform piece shape.

%----------------------------------------------------------------------
\subsubsection{Specifying a Piece Shape or IvP Domain Point in String Format}
\label{sec_piece_shape}
\index{IvP Domain!String Format}

Aspects of the \var{Reflector} tool require the specification of the
shape of a piece used in a piecewise defined IvP function.  The
specification is comprised of the length of the piece for each of the
$n$ dimensions, i.e., decision variables. There are two ways to describe
the lengths. Recall that the IvP domain for a variable is given by a
low and high value, and the number of points. For example the variable
$x$ could range from $0$ to $30$ with 31 points, and $y$ could
range from $-50$ to $50$ with 21 points. The first way to describe 
the length of a piece is by specifying the number of discrete points:

\index{IvP Domain!Native vs. Discrete References}

\small
\begin{verbatim}
   "discrete @ x:5,y:5" 
\end{verbatim}
\normalsize

\noindent
A uniform function built over this domain with the above requested
piece shape would have 35 pieces in a manner rendered in Figure
\ref{fig_uniform_ipf}.

\vspace{0.15in}
\begin{figure}[H]
  \centering
  \includegraphics[width=0.85\textwidth]{figs_ivpbuild/uniform_piece.png}
  \caption{{\bf A uniform IvP function}: An IvP domain is rendered
    over the two variables $x$, with 31 elements, and $y$ with 21
    elements.  Requesting a set of uniform pieces with five elements
    on each edge results in the piece distribution shown. The circled
    point represents the 23rd index into the $x$ domain and the 13th
    index into the $y$ domain.  This point can be referenced by the
    string \vvar{"discrete @ x:22,y:12"}.  It may also be referenced
    by the string \vvar{"native @ x:22,y:10"}.}
  \label{fig_uniform_ipf}
\end{figure}
\vspace{0.1in}

\noindent
Note the distribution of pieces is not completely uniform. Smaller
pieces are used at the upper ranges of the domain. A second method of
specifying the same piece shape is to use the native lengths of the
domain:

\small
\begin{verbatim}
   "native @ x:5,y:25" 
\end{verbatim}
\normalsize

\noindent
This piece also has a length of five units along the $x$ dimension and
five units along the $y$ dimension, resulting in the same distribution
shown in Figure \ref{fig_uniform_ipf}. When a ``native'' value doesn't
exactly map onto one of the points in the domain, it is rounded to the
nearest domain point. For example, \var{"native @ x:5,y:22.6"}
specifies a piece with {\em five} units on the $y$ dimension,
\var{"native @ x:5,y:22.4"} specifies a piece with {\em four} units on
the $y$ dimension. And when a native value is given exactly between
two domain points, the value is rounded up, so \var{"native @
  x:5,y:22.5"} specifies a piece with {\em five} units on the $y$
dimension.

\index{IvP Domain!Specifying a Single Point}
A single {\em point} in the IvP domain can be similarly
referenced. When the string \var{"discrete @ x:5,y:5"} is used to
represent a piece {\em shape}, the numerical values represent the
length of the piece. When the same string is used to represent a {\em
  point} in the IvP domain, the numerical values represent the index
into the domain. For example, the circled point in Figure
\ref{fig_uniform_ipf} can be be referenced by the string
\vvar{"discrete @ x:22,y:12"}.  It may also be referenced by the
string \vvar{"native @ x:22,y:10"}. When a native values does not map
exactly to a domain value, the nearest domain point is used. 

%-----------------------------------------------------------------
\subsubsection{Specifying a Region of an IvP Domain in String Format}
\label{sec_region_shape}
\index{IvP Domain!Regions by Strings}

Aspects of the \var{Reflector} tool require the specification of a
\var{region} of the IvP domain. The specification is comprised of an
upper and lower bound for each of the $n$ dimensions, i.e., decision
variables. Recall that the IvP domain for a variable is given by a low
and high value, and the number of points. For example the variable $x$
could range from $0$ to $30$ with 31 points, and $y$ could range from
$-50$ to $50$ with 21 points. A region can be specified as follows:

\small
\begin{verbatim}
   "native @ x:10:24,y:-25:20"
\end{verbatim}
\normalsize

\noindent
or equivalently, 

\small
\begin{verbatim}
   "discrete @ x:10:24,y:5:14"
\end{verbatim}
\normalsize

\noindent
This region is rendered in Figure \ref{fig_region_ipf}. If the extents
specified in the string exceed the boundaries of the IvP domain, the
requested region is clipped to be exactly the boundary value. For
example, the string \var{"native @ x:10:24, y:-25:50"} and
\var{"native @ x:10:24, y:-25:50000"} would specify the same region
given the example in Figure \ref{fig_region_ipf}.

\vspace{0.15in}
\begin{figure}[H]
  \includegraphics[width=0.85\textwidth]{figs_ivpbuild/uniform_region.png}
  \caption{{\bf A non-uniform IvP function}: An IvP domain is rendered
    over the two variables, x, with 31 elements, and y, with 21
    elements.  A region of IvP domain is identified for further
    application of the \vvar{Reflector}. The region is specified by
    the string \vvar{"discrete @ x:10:24, y:5:14"} or \vvar{"native @
      x:10:24, y:-25:20"}. In this case smaller uniform pieces are
    applied within the region.}
  \label{fig_region_ipf}
\end{figure}
\vspace{0.1in}

When a native value is specified that does not map to a domain value,
this case is handled differently for {\em regions} than it was when
specifying a piece {\em shape}. In a region specification the native
value is treated as a strict boundary value. Therefore the string
\var{"native @ x:9.01:24.99, y:-29.99:24.99"} would specify the exact
same region as the example above and in Figure \ref{fig_region_ipf}.


%=====================================================================
\subsection{Optional Feature \#1: Choosing the Piece Shape in Uniform Functions}
\label{aspect_ratio}
\index{Uniform Functions!Choosing the Piece Shape}
\index{IvPBuild Toolbox!Uniform Functions}

%----------------------------------------------------------------------
\subsubsection{Potential Advantages}
\index{Uniform Functions!Advantages and Disadvantages}

By simply specifying the desired number of pieces, the \var{Reflector}
heuristically sets the piece size and aspect ratio of an initial
uniform function. This has the advantage of being very simple and
independent of the underlying function. (See line 15 in Listing
\ref{uniform_alpha}.)  However, like most heuristics, there may be
cases where the result may not be best for a particular situation. If
the user has some insight into the underlying function and the IvP
domain, the user may not wish to leave this decision to the heuristic,
but instead specify the piece shape explicitly. Below, the piece
count-to-piece shape heuristic is described as well as how to override
the heuristic with an explicit shape request.

%----------------------------------------------------------------------
\subsubsection{Specifying the Piece Shape Implicitly from a Piece Count Request}
\label{aspect_ratio_by_pcs}
\index{Uniform Functions!By Choosing the Piece Count}

When the \var{Reflector} creates a uniform IvP function based on a
requested piece count, a heuristic is invoked to generate a single
piece to be used in the uniform function based on both the piece count
and the IvP domain. This piece is not unlike the 5 x 5 piece in Figure
\ref{fig_uniform_ipf}, except that a 5 x 5 piece is not explicitly
requested, but rather the total pieces in that figure, 35, would be
requested. Knowing a little about this heuristic can help determine
when its worth the effort to instead explicitly define the shape of
the uniform piece.  The total requested pieces is an upper limit, and
often not exactly achieved. For example, the same 35 pieces in Figure
\ref{fig_uniform_ipf} would be created upon piece-count requests of
35, 36, 37, 38, and 39 pieces.  The heuristic attempts to keep the
aspect ratio of the uniform piece close to $1.0$, but will deviate to
allow a uniform piece that will result in a total number of pieces
closer to the requested amount. The heuristic is given Listing
\ref{uniform_heuristic} below, and some examples are shown in Table
\ref{table_heuristic_one}.

\vspace{0.2in}
\begin{listing}{The heuristic for generating a uniform piece based on piece-count and domain}
\label{uniform_heuristic}
\scriptsize
\begin{verbatim}
  1  IvPBox buildUniformPiece(IvPDomain domain, int max_amount)
  2  {
  3    int dim = domain.getDim();
  4    vector&lt;int&gt;  pcs_on_edge(dim,1);
  5    vector&lt;bool&gt; pcs_maxed(dim,false);
  6    vector&lt;int&gt;  pts_on_edge(dim,0);
  7  
  8    // Store the number of points on an edge for quick reference
  9    for(i=0; i&lt;dim; i++)
 10      pts_on_edge[i] = domain.getVarPoints();
 11    
 12    // Augment the number pieces on edges until done
 13    bool done = false;
 14    while(!done) {
 15      // Algorithm done if augmentations for all dimensions are maxed out.
 16      done = true;
 17      for(i=0; i&lt;dim; i++)
 18        done = done &amp;&amp; pcs_maxed[i]
 19  
 20      // Find the dimension most worthy of further augmentation
 21      if(!done) {
 22        int    augment_dim;               
 23        double biggest = 0;           
 24        for(d=0; d&lt;dim; d++) {          
 25            if(!pcs_maxed[d]) {              
 26            double ratio = (pts_on_edge[d] / pcs_on_edge[d]);
 27            if(ratio &gt; biggest) {       
 28              biggest = ratio;        
 29              augment_dim = d;            
 30            }
 31          }
 32        } 
 33
 34        // Augment the pieces_on_edge for the chosen dimension
 35        pcs_on_edge[augment_dim]++;      
 36  
 37        // Calculate hypothetical number of boxes given new augmentation.
 38        double hypothetical_total = 1;
 39        for(d=0; d&lt;dim; d++)
 40          hypothetical_total *= pcs_on_edge[d];
 41  
 43        // If max_amount exceeded, undo the augment, and max-out the dimension
 44        if(hypothetical_total &gt; max_count) {
 45          pcs_maxed[ix] = true;
 47          pcs_on_edge[augment_dim]--;
 48        }
 49  
 50        // Cant have more pieces on an edge than points on an edge
 51        if(pcs_on_edge[augment_dim] &gt;= pts_on_edge[augment_dim])  
 52          pcs_maxed[augment_dim] = true;          
 53      }
 54    }
 55   
 56    // Now build the uniform piece based on pts_on_edge and pcs_on_edge
 57    IvPBox uniform_piece(dim);
 58    for(d=0; d&lt;dim; d++) {
 59      double edge_size = ceil(pts_on_edge[d] / pcs_on_edge[d]);
 60      uniform_piece.setPTS(d, 0, edge_size-1);
 61    }
 62    return(uniform_piece);
 63  }
\end{verbatim}
\end{listing}
\normalsize
\vspace{0.15in}

\noindent
The heuristic progresses by growing the number of "pieces on an edge",
\var{pcs\_on\_edge}, on each dimension. The algorithm proceeds to grow
the \var{pcs\_on\_edge} for each dimension until it cannot grow
further. For example, in Figure \ref{fig_uniform_ipf} there are seven
pieces on the $x$ edge and five pieces on the $y$ edge.  The algorithm
is initiated with a single piece on each edge, i.e., dimension, (line
4 in Listing \ref{uniform_heuristic}). A Boolean is associated with
each dimension indicating whether growth in that dimension has been
maxed out. This vector is initiated on line 5. A dimension becomes
maxed out if additional growth in that dimension means the requested
piece count is exceeded (checked for in lines 37-48), or if the number
of pieces on an edge is equal to the number of points on and edge of
the IvP domain (checked for in lines 49-51).  At each chance to grow
the size of the uniform piece the most appropriate dimension is
identified for growth (lines 22-33) by choosing the dimension with the
largest ration of points on the edge to pieces on the edge (line 26).

Some examples of the heuristic are shown in Table
\ref{table_heuristic_one}. The domain shown in table has 1000 discrete
choices for both the $x$ and $y$ variables. Given that the domain
itself has an aspect ratio of one, not surprisingly, the generated
uniform pieces also have roughly an aspect ratio of 1.0, and the
number of pieces on each edge of the domain are also nearly
equivalent.

\vspace{0.2in}
\begin{table}[H]
  \wikitablehint{style=graytop2}
  \centering
  \footnotesize
  \begin{tabular}{|c|c|c|c|c|c|} \hline
Requested &amp;  Aspect   &amp;  Shape    &amp;   Actual  &amp; Pieces On the &amp; Pieces On the \\ 
Pieces    &amp;  Ratio    &amp; of Piece  &amp;   Pieces  &amp; 'x' Domain Edge &amp; 'y' Domain Edge \\ \hline \hline
     63   &amp;  0.78     &amp;  112x143  &amp;     63    &amp;   9             &amp;  7        \\
     64   &amp;  1.0      &amp;  125x125  &amp;     64    &amp;   8             &amp;  8        \\
     500  &amp;  1.0      &amp;  46x46    &amp;     484   &amp;   22            &amp;  22       \\
     512  &amp;  0.96     &amp;  44x46    &amp;     506   &amp;   23            &amp;  22       \\
    1000  &amp;  0.97     &amp;  32x33    &amp;     992   &amp;   32            &amp;  31       \\
    1024  &amp;  1.0      &amp;  32x32    &amp;    1024   &amp;   32            &amp;  32       \\
    1025  &amp;  1.0      &amp;  32x32    &amp;    1024   &amp;   32            &amp;  32       \\ 
    4000  &amp;  1.0      &amp;  16x16    &amp;    3969   &amp;   63            &amp;  63       \\ \hline
  \end{tabular}
  \normalsize
  \caption{{\bf Example 2D results of the uniform-piece heuristic}:
    Uniform piece characteristics resulting from a heuristic applied
    to a requested total number of pieces and a given IvP domain with
    two variables. In this case the IvPDomain is x:200:299:1000,
    y:0:999:1000.}
  \label{table_heuristic_one}
\end{table}
\vspace{0.15in}


Consider how the heuristic performs instead on the 3D domain shown in
Table \ref{table_heuristic_two}. The number of choices for the z
variable is a tenth of that for the x and y variables. The results
provided by the heuristic may or may not be the right overall,
depending on the underlying function and application. In particular
consider that when requesting 100 or 200 pieces, the z component
of the resulting uniform piece is the entire z domain, i.e., there
is only one piece on the z domain edge.

\vspace{0.15in}
\begin{table}[H]
  \wikitablehint{style=graytop2}
  \centering
  \footnotesize
  \begin{tabular}{|c|c|c|c|c|c|} \hline
Requested &amp;  Shape       &amp;   Actual  &amp; Pieces On the   &amp; Pieces On the   &amp; Pieces On the   \\ 
Pieces    &amp;  of Piece    &amp;   Pieces  &amp; 'x' Domain Edge &amp; 'y' Domain Edge &amp; 'z' Domain Edge \\ \hline \hline
     100  &amp;  100x100x100 &amp; 100   &amp;   10         &amp;  10          &amp; 1  \\
     200  &amp;  72x72x100   &amp; 196   &amp;   14         &amp;  14          &amp; 1  \\
    1000  &amp;  44x46x50    &amp; 968   &amp;   22         &amp;  22          &amp; 2  \\
    7500  &amp;  23x24x25    &amp; 7392  &amp;   44         &amp;  42          &amp; 4  \\ \hline 
  \end{tabular}
  \normalsize
\caption{{\bf Example 3D results of the uniform-piece heuristic}:
  Uniform piece characteristics resulting from a heuristic applied to
  a requested total number of pieces and a given IvP domain with three
  variables. In this case the IvPDomain is x:200:299:1000,
  y:0:999:1000, z:0:99:100.}
\label{table_heuristic_two}
\end{table}
\vspace{0.15in}

This heuristic has served fairly well in practice, but in cases where
the user has insight into a better choice for the size and shape of the
uniform piece, this can be overridden as discussed next.

%----------------------------------------------------------------------
\subsubsection{Specifying the Uniform Piece Shape Explicitly}
\index{Uniform Functions!By Choosing the Piece Shape}

The piece shape used in a uniform IvP function can be set explicitly
using the \var{uniform\_piece} parameter in the Reflector
\func{setParam()} function first mentioned in Section
\ref{sec_reflector_interface}.  For example, the uniform piece shown
in Figure \ref{fig_ipf_6x4} can be requested as follows:


\vspace{0.1in}
\small
\begin{verbatim}
  reflector.setParam("uniform_piece", "discrete @ x:6,y:4");  
  int amt = reflector.create();  
\end{verbatim}
\normalsize
\vspace{0.1in}

Compared to generating a uniform function by a simple piece-count
request, the above two lines would replace the single line with the
\func{create()} invocation, as in line 15 in Listing
\ref{uniform_alpha}.

\vspace{0.15in}
\begin{figure}[H]
  \includegraphics[width=0.85\textwidth]{figs_ivpbuild/uniform_piece_6x4.png}
  \caption{{\bf An IvP function made from an explicit piece shape
      request}: An IvP domain is rendered over the two variables x,
    with 31 elements, and y with 21 elements.  Requesting a uniform
    piece of size 6x4 would result in the rendered configuration. This
    piece can be specified with \vvar{"discrete @ x:6,y:4"} or
    \vvar{"native @ x:6,y:20"}. This piece shape would {\em not} be
    resulting piece shape had the user simply requested 36 pieces
    given this domain.}
  \label{fig_ipf_6x4}
\end{figure}
\vspace{0.1in}

In summary, when the Reflector \func{create()} function is called, the
reflector-script begins and needs to know the size and shape of the
piece used for uniform function creation. It may get this information
by either explicitly configuring the piece shape, or implicitly by
requesting a total number of pieces (as an argument to the
\func{create()} function). If both requests are inadvertently invoked,
the latter type of request is ignored and the explicit piece shape
configuration is honored. If neither specification of piece shape is
provided, a function with a single piece will be created (but perhaps
further refined in later parts of the reflector-script). Use of the
explicit piece shape request may be the preferred method for example
if a domain includes a variable for vehicle heading and a uniform
function is desired with pieces split on every three degrees,
regardless of whether the domain contains 180, 360, or 720
choices for heading.

%=====================================================================
\subsection{Optional Feature \#2: IvP Functions with Directed Refinement}
\label{sec_directed_refine}
\index{Reflector!Directed Refinement}
\index{Directed Refinement}
\index{Directed Refinement!Detailed Usage}
\index{IvPBuild Toolbox!Directed Refinement}

The directed-refinement feature of the Reflector is potentially useful
when (a) the underlying function has distinct sub-regions that are
harder to accurately represent with a piecewise linear approximation,
and (b) when the user has insight into the location of those
sub-regions.  Use of the tool involves specifying both the region to
direct further refinement, and the size of the piece to use in the
refinement region. This is done using the \var{uniform\_piece},
\var{refine\_region}, and \var{refine\_piece} parameters in the
Reflector \func{setParam()} function first mentioned in Section
\ref{sec_reflector_interface}.  For example, the IvP function shown in
Figure \ref{fig_region_ipf} would be generated with the following
lines:

\vspace{0.2in}
\begin{listing}{An example configuration of the \var{Reflector} tool using directed refinement}
\label{lst_config_drefine}
\scriptsize
\begin{verbatim}
  reflector.setParam("uniform_piece", "discrete @ x:5,y:5");  
  reflector.setParam("refine_region", "native @ x:10:24,y:-25:20");  
  reflector.setParam("refine_piece",  "discrete @ x:2,y:2");  
  reflector.create();  
\end{verbatim}
\end{listing}
\normalsize
\vspace{0.2in}

\noindent
When the \func{create()} function is invoked in the last line above,
the reflector-script will involve two of the components of the
reflector-script mentioned in Section \ref{sec_reflector_script}. The
first line configures the initial uniform function phase, and the
middle two lines configure the directed refinement phase by declaring
a sub-region (second line) and a uniform piece to be applied to that
sub-region (third line). Multiple directed refinements can be
configured and queued for inclusion in the reflector-script by adding
further \var{refine\_region} - \var{refine\_piece} pairs prior to the
invocation of the \func{create()} function. They must be added in pairs
however since the \var{refine\_piece} is always associated with the
last specified \var{refine\_region}.


% when the directed refinement phase is run, the pieces completely
% outside the sub-region will not be touched, 
%
% possible semantic errors - 
%  - region not overlapping with domain
%  - piece larger than region along any dimension
%  - 
\vspace{0.1in}

\noindent
For an illustrative case we return to the Gaussian function rendered
in Figure \ref{fig_uniform}:

\begin{equation*}
f(x,y) = Ae^{-({  \frac{(x-x_0)^2 + (y-y_0)^2}{2\sigma^2}})},
\end{equation*}
\vspace{0.03in}

\noindent 
where $A=150$, $x_0=50$, $y_0=-150$ and $\sigma=32.4$. This function
apparently has a sub-region of the domain where the function is very
nonlinear and otherwise quite linear outside the sub-region. The use
of directed-refinement begins by building an initial uniform function
as shown in Figure \ref{fig_direct_a}, conceding for now that the
approximation will be poor in the sub-region around the peak.

\vspace{0.15in}
\begin{figure}[H]
  \centering 
  \includegraphics[width=0.80\textwidth]{figs_ivpbuild/dirgauss_a.png}
  \caption{{\bf An initial IvP function approximation}: The
    \vvar{Reflector} first creates an initial simple uniform function
    with fairly large pieces, conceding for the time being poor
    performance in approximating the underlying function in areas near
    the peak of the underlying function.}
 \label{fig_direct_a}
\end{figure}
\vspace{0.15in}

\noindent
The initial uniform function was created by requesting 50 pieces, and
a function with 49 pieces was subsequently generated. The sub-region
shown in Figure \ref{fig_direct_b} was identified for directed
refinement, with much smaller pieces used in the sub-region.

\vspace{0.1in}
\begin{figure}[H]
  \centering 
  \includegraphics[width=0.80\textwidth]{figs_ivpbuild/dirgauss_b.png}
  \caption{{\bf An IvP function generated with directed-refinement}:
    After an initial uniform function has been generated, the
    \vvar{Reflector} refines the function on the prescribed sub-domain
    of the function with much smaller pieces.}
  \label{fig_direct_b}
\end{figure}
\vspace{0.05in}

The results in Table \ref{tab_directed} below were generated by
configuring the reflector-script to include directed-refinement on the
underlying Gaussian function shown in Figure \ref{fig_direct_b}, in a
manner similar to the four lines in Listing
\ref{lst_config_drefine}. Each row in the table below differs only in
the size of the \var{refine\_piece} shown in the second column.

\vspace{0.1in}
\begin{table}[H]
  \wikitablehint{style=graytop2}
  \centering
  \footnotesize
  \begin{tabular}{|c|c|c|c|c|c|} \hline
Case &amp; Refine    &amp;  Total   &amp;  Worst  &amp; Average &amp;  Time    \\ 
     &amp; Edge Size &amp;  Pieces  &amp; Error   &amp; Error   &amp;  millisecs   \\ \hline \hline
A    &amp; 4         &amp;   2607   &amp; 0.7760  &amp; 0.0104  &amp;  38.9    \\
B    &amp; 5         &amp;   1687   &amp; 0.7760  &amp; 0.0123  &amp;  25.6    \\
C    &amp; 6         &amp;   1162   &amp; 0.7760  &amp; 0.0149  &amp;  17.8    \\
D    &amp; 7         &amp;    847   &amp; 0.7760  &amp; 0.0178  &amp;  13.0    \\
E    &amp; 8         &amp;    682   &amp; 0.9093  &amp; 0.0214  &amp;  10.2    \\
F    &amp; 9         &amp;    535   &amp; 1.1895  &amp; 0.0254  &amp;  8.2     \\
G    &amp; 10        &amp;    447   &amp; 1.4589  &amp; 0.0302  &amp;  6.7     \\
H    &amp; 11        &amp;    367   &amp; 1.8263  &amp; 0.0351  &amp;  5.7     \\
I    &amp; 12        &amp;    295   &amp; 2.2470  &amp; 0.0409  &amp;  4.7     \\
J    &amp; 13        &amp;    262   &amp; 2.6527  &amp; 0.0472  &amp;  4.1     \\
K    &amp; 14        &amp;    231   &amp; 3.0321  &amp; 0.0540  &amp;  3.6     \\
L    &amp; 15        &amp;    202   &amp; 3.5886  &amp; 0.0615  &amp;  3.2     \\ \hline
  \end{tabular}
  \normalsize
  \caption{{\bf Results of directed-refinement}: Characteristics of 12
    different IvP functions approximating the underlying function
    shown in Figure \ref{fig_direct_a} and \ref{fig_direct_b}. Each
    function is built by starting with an initial uniform function and
    then performing directed refinement over the region $-50 \leq x
    \leq 150$ by $-250 \leq y \leq -50$. The refinement piece size
    shown in the second column is the parameter that results in the 12
    different functions.}
\label{tab_directed}
\end{table}

For the observed errors reported in columns 4 and 5, the domain was
sampled for each resulting IvP function at 50,000 random points for
comparison between the value provided by the IvP function against the
underlying function. The average time to create the IvP function,
noted in the last column, was taken by averaging 100 creations since
the precision of the timer used was 100 milliseconds. The data shown
here are meant to show the relationship between parameters, not
necessarily an indication of how fast things run on ``typical''
platforms. That being said, this data is from a Dell laptop containing
a Pentium chip with about 2.0 GHz processor, with a codebase compiled
without typical gcc optimization options.

\pskip

The trends in the table are as one would expect. As the number of
pieces is decreased, the average error and worst error increase, and
the time to create the IvP function is decreased. The question is
whether this technique offers the ability to improve in all three
metrics, piece-count, function accuracy, and creation time,
simultaneously compared to using a simple uniform function without
directed refinement. The answer is yes. Evidence can be seen of this
by comparing Table \ref{tab_directed} with Table \ref{tab_uniform}. We
look for cases in Table \ref{tab_directed} that dominate cases in
Table \ref{tab_uniform}.  A case that dominates another is stronger or
equal in all three performance metrics simultaneously. Case (a)
dominates case (4). Case (b) dominates cases (5),(4).  Case (c)
dominates cases (6),(5). Case (d) dominates cases (6),(5). Case (e)
dominates cases (7),(6).


%----------------------------------------------------------------------
\subsection{Optional Feature \#3: IvP Functions with Smart Refinement}
\label{sec_smart_refine}
\index{IvPBuild Toolbox!Smart Refinement}
\index{Smart Refinement}
\index{Reflector!Smart Refinement}

%----------------------------------------------------------------------
\subsubsection{Potential Advantages}
\index{Smart Refinement!Advantages and Disadvantages}

The smart-refinement algorithm works by further refining an existing
IvP function based on an (automated) estimate of which pieces need
refinement the most. There are two key ideas in this algorithm.
First, no insight into the underlying function form is required by the
user, unlike the directed-refinement tool. Second, the prioritization
of pieces is based on the apparent fit between a piece's linear
function and the underlying function, for the sub-domain of that
piece. This determination of fit can be measured by performing very
little extra computations beyond the already required calculations
performed during linear regression for each piece during the uniform
and directed-refinement phases. In short, there is typically very
little reason not to invoke this tool to some degree.

%----------------------------------------------------------------------
\subsubsection{The Smart-Refinement Algorithm}
\label{sec_smart_usage}
% The user needs to specify how many additional pieces
\index{Smart Refinement!Algorithm}

\index{Smart Refinement!Linear Regression}
\index{Linear Regression} 
\index{Reflector!Linear Regression} 
The smart-refinement algorithm utilizes information collected during
the creation of pieces earlier in the reflector-script, during the
initial uniform function phase which is always invoked, and
directed-refinement phase which is optionally invoked. During these
phases, pieces are formed and linear regression is performed to
determine the linear function associated with each piece.  

To perform linear regression for a new piece, the underlying function
over $k$ variables is sampled at $n = 2k+1$ points (the corners and
the middle point) to produce $f(\vec{x}_1) \ldots f(\vec{x}_n)$, and
these $n$ values are used to determine the linear function for that
piece:

\vspace{0.1in}
\begin{equation*}
f'(\vec{x}) = {c_1}{x_1} + \ldots + {c_k}{x_k} + b.
\end{equation*}
\vspace{0.1in}

\index{Smart Refinement!Regression Score}
\index{Regression Score}
\noindent
The same $n$ points are again evaluated using this newly determined
linear function instead, producing another set of $n$ values
$f'(\vec{x}_1) \ldots f'(\vec{x}_n)$. The \var{regression score} is
determined by:

\vspace{0.1in}
\begin{equation*}
{\tt regression\_score} = \text{sqrt} \; \displaystyle\sum_{i=1}^{n}
(f'(\vec{x}_i) - f(\vec{x}_i))^2
\end{equation*} 
\vspace{0.1in}

\index{Smart Refinement!Priority Queue}
\index{Priority Queue}
\noindent 
The \var{regression\_score} is then inserted into a priority queue
along with a reference to the piece that generated the score. The idea
is shown in Figure \ref{pq_fig}. This algorithm for implementing a
priority queue can be found in \cite{clrs01}. The priority queue
implemented in the IvPBuild Toolbox is modified slightly to be a
fixed-length queue. Insertion and retrieval time is $O(n \; log(n))$.

\vspace{0.12in}
\begin{figure}[H]
  \centering
  \includegraphics[width=0.8\textwidth]{figs_ivpbuild/priority_queue.png}
  \caption{{\bf Priority queue keyed with regression scores}: The
    \vvar{Reflector} uses a balanced priority queue based on a
    regression score to determine which pieces could benefit the most
    from further refinement.}
 \label{pq_fig}
\end{figure}
\vspace{0.12in}

The \var{Reflector} instance maintains this priority queue only if
smart-refinement is activated. The pieces made during the initial
uniform function and directed-refinement parts of the reflector-script
are stored in the priority queue. The smart-refinement proceeds by
repeatedly popping the top priority piece from the queue for further
refinement. By further refinement of a piece, we mean splitting a
piece and replacing the piece with the two new pieces after performing
regression on the two new pieces. The piece is split along the
dimension with the largest edge.  These two new pieces are then also
inserted in the priority queue for possible further refinement.

\index{Smart Refinement!Example} 

An example of the smart-refinement algorithm applied to the same
Gaussian function shown in Figure \ref{fig_direct_b} is shown below in
Figure \ref{fig_smart_refine}.

\vspace{0.1in}
\begin{figure}[H]
  \centering 
  \includegraphics[width=0.80\textwidth]{figs_ivpbuild/smartgauss.png}
  \caption{{\bf An IvP function generated with smart-refinement}:
    Results of smart-refinement on an initial uniform function with 25
    pieces and an additional 200 pieces during the smart-refinement
    phase. The function has a total of 225 pieces and is significantly
    more accurate and faster to create than a pure uniform function
    with 625 pieces. Further examples are shown in Table
    \ref{table_usmart}.}
  \label{fig_smart_refine}
\end{figure}
\vspace{0.1in}

The results in Table \ref{table_usmart} show the results of applying
the smart-refinement algorithm to the function in Figure
\ref{gauss2}. Each row in the table shows the results from creating
first a pure uniform function, and then a further refined function
using an additional 75\% more pieces with smart-refinement. The
left-hand side of the table is the same as Table \ref{tab_uniform},
duplicated here for ease of comparison. Compare for example the
smart-refine function with 175 pieces in Case 10 against the pure
uniform function with 400 pieces in Case 7. The former not only has
less pieces, but is more accurate and took less time to create. It
dominates the pure uniform function, i.e., is simultaneously better in
all measures of performance. This is similar to the way
directed-refinement dominates pure uniform functions, but in the case
of smart-refinement, no insight into the underlying function form was
required!

\begin{table}[H]
  \wikitablehint{style=graytop2}
  \centering
  \footnotesize
  \begin{tabular}{|c|r| |r|c|r|r| |r|r|r|r|} \hline
Case &amp; Edge &amp;  Pieces  &amp;  Worst  &amp;   Avg  &amp;  Time &amp; Pieces &amp; Worst   &amp;   Avg  &amp; Time   \\ 
     &amp; Size &amp;          &amp; Error   &amp; Error  &amp;  msec &amp;        &amp; Error   &amp; Error  &amp; msec   \\ \hline \hline
4    &amp; 10   &amp;   2500   &amp; 1.4589  &amp; 0.0232 &amp;  39.9 &amp; 3445   &amp; 0.8512  &amp; 0.0139 &amp; 70.1   \\
5    &amp; 15   &amp;   1156   &amp; 3.4532  &amp; 0.0551 &amp;  18.9 &amp; 2023   &amp; 1.3241  &amp; 0.0224 &amp; 47.3   \\
6    &amp; 20   &amp;    625   &amp; 5.5855  &amp; 0.1014 &amp;  10.4 &amp; 1093   &amp; 1.9834  &amp; 0.0297 &amp; 27.6   \\
7    &amp; 25   &amp;    400   &amp; 7.79764 &amp; 0.1585 &amp;  6.5  &amp; 700    &amp; 2.5924  &amp; 0.0362 &amp; 18.1   \\
8    &amp; 30   &amp;    289   &amp; 12.0347 &amp; 0.2303 &amp;  4.7  &amp; 505    &amp; 2.3905  &amp; 0.0480 &amp; 11.3   \\
9    &amp; 40   &amp;    169   &amp; 24.2977 &amp; 0.3919 &amp;  2.8  &amp; 295    &amp; 12.6192 &amp; 0.0885 &amp; 7.5    \\
10   &amp; 50   &amp;    100   &amp; 18.2113 &amp; 0.5917 &amp;  1.6  &amp; 175    &amp; 3.4166  &amp; 0.1194 &amp; 4.3    \\
11   &amp; 75   &amp;     49   &amp; 42.0652 &amp; 1.2143 &amp;  0.9  &amp; 85     &amp; 7.9236  &amp; 0.3100 &amp; 2.3    \\
12   &amp; 100  &amp;     25   &amp; 30.3938 &amp; 2.0285 &amp;  0.5  &amp; 43     &amp; 12.3887 &amp; 0.5188 &amp; 1.2    \\ \hline
  \end{tabular}
  \normalsize
  \caption{In each case an initial uniform function was created with
    the number of pieces indicated in column 3. The qualities of the
    function in terms of accuracy and time are shown in columns
    4-6. Each function was then augmented with 75\% additional pieces
    using the smart-refinement algorithm with the resulting qualities
    shown in columns 7-10.}
\label{table_usmart}
\end{table}
\vspace{0.1in}

\index{Smart Refinement!Limitations} 

The smart-refine algorithm is limited by the degree to which the
regression score is accurate for each piece entered into the
queue. Note for example, Case 9 in Table \ref{table_usmart}, where the
worst error detected for the smart-refine function is anomalous and
significantly higher than that noted in functions with far fewer
pieces. The error of 12.6192 occurred in some piece that apparently
did not report a high regression score. This is likely due to an
unfortunate case where the points sampled for use in generating the
linear function all fit the resulting linear function very well, but
the non-sampled points did not fit well. The idea is shown in Figure
\ref{fig_smart_bad}.

\begin{figure}[H]
  \centering 
  \includegraphics[width=0.66\textwidth]{figs_ivpbuild/smart-gone-bad.png}
  \caption{{\bf Regression scoring gone awry}: Assessing the
    regression score can be misleading in cases where the derived
    linear function fits each sampled point very well but otherwise
    poorly fits the underlying function.}
 \label{fig_smart_bad}
\end{figure}

%----------------------------------------------------------------------
\subsubsection{Invoking the Smart-Refine Algorithm in the Reflector}
\index{Smart Refinement!User Guide}

The smart-refine tool can be included in the refine-script in a few
different ways. The first is to simply indicate how many pieces to use
during the smart-refine process. The number of pieces is addition to
any pieces that may already be present after the initial uniform
function has bee created and after any directed-refinement has been
performed.

\small
\begin{verbatim}
  reflector.setParam("smart_amount", 400);
\end{verbatim}
\normalsize

\noindent
Alternatively the number of pieces to be used in smart-refine can be
given in terms of the percentage of additional pieces beyond what has
already been created at the time of invocation of the smart-refine
part of the refine-script. The argument is a non-negative integer
value:

\small
\begin{verbatim}
  reflector.setParam("smart_percent", 35);
\end{verbatim}
\normalsize

\noindent
There is a third parameter {\em smart\_thresh} that can affect how
many pieces are used in the smart-refine phase. The value passed with
this parameter is a regression score such that if the current top
element of the priority queue has a score below this threshold,
smart-refinement will terminate early, before the target piece amount
specified by {\em smart\_amount} or {\em smart\_percent} has been
reached:

\small
\begin{verbatim}
  reflector.setParam("smart_thresh", 0.05);
\end{verbatim}
\normalsize

\noindent
Regression scores represent the raw discrepancy between the underlying
function and the linear approximation, and in general do not reflect
any normalization. For example, depending on the function, the value
of $0.05$ above could be a relatively large value resulting in an
early termination of refinement, or a relatively small threshold that
cannot be met without thousands of additional pieces.  The user of
this parameter needs to have some knowledge of the range of the
underlying function.

Finally, the simplest way of invoking the smart-refinement tool is by
specifying the number of pieces as the second argument in the
\func{create()} function call, and the smart threshold as the third
argument:

\small
\begin{verbatim}
  reflector.create(1000, 400, 0.5);
\end{verbatim}
\normalsize

\noindent
The above will result in an initial uniform function with $1000$
pieces and an additional $400$ pieces used for smart-refinement. The
full additional $400$ pieces will be generated only if the threshold
is not reached along the way.  The above is equivalent to:

\small
\begin{verbatim}
  reflector.setParam("uniform_amount", 1000) 
  reflector.setParam("smart_amount", 400) 
  reflector.setParam("smart_thresh", 0.5) 
  reflector.create();
\end{verbatim}
\normalsize

\noindent
Accepting these three common parameters as arguments to the
\func{create()} function call is simply for convenience. If provided,
they override the setting from prior calls to \func{setParam()}.


%=====================================================================
\subsection{Optional Feature \#4: IvP Functions with Auto-Peak Refinement}
\label{auto_refine}
\index{IvPBuild Toolbox!AutoPeak Refinement}
\index{AutoPeak Refinement}
\index{Reflector!AutoPeak Refinement}
\index{AutoPeak Refinement!Detailed Usage}

%----------------------------------------------------------------------
\subsubsection{Potential Advantages}
\index{AutoPeak Refinement!Advantages and Disadvantages} 

The auto-peak algorithm is the last optional algorithm in the
reflector-script. The objective is also to build a more accurate IvP
function representing the underlying function. The metric of accuracy
referenced up to this point has been the average error and worst error
observed from a number of random sample points. For example Table
\ref{table_usmart} reported error in this way. Another metric of
accuracy is the degree to which the maximum peak of the function,
represented by a point in the discrete IvP domain, agree between the
underlying function and the IvP function. For example, if the peak of
the underlying function is \var{"heading=133, speed=3.2"} and the peak
of the IvP function is \var{"heading=129, speed=3.0"} the IvP function
could still be rated well in terms of error metrics from sampling the
entire domain. However, the peak of the function is probably the most
important part of the underlying function to represent precisely.
When the IvP function happens to be the only function or dominating
function influencing the vehicle at that moment, the peak of the
function {\em is} the output of the solver. The auto-peak refinement
focuses on this aspect of the function, without user insight into
where the actual peak occurs in the underlying function.

%----------------------------------------------------------------------
\subsubsection{The Auto-Peak Algorithm}
The auto-peak algorithm proceeds by repeatedly refining the single
piece in the IvP function that is believed to contain the maximum peak
until that one piece contains only a single point in the IvP domain.
It takes advantage of the fact that for a given piece in an IvP
function, its maximum value, over the piece interval and linear
interior function, can be rapidly calculated. The basic algorithm
steps are as follows:

\vspace{0.15in}
\begin{listing}{An overview of the auto-peak algorithm}
\label{lst_auto_peak}
\footnotesize
\begin{verbatim}
 Step  1.  Populate the priority queue with the max-value for each piece.
 Step  2   If the top piece in the priority queue has only one IvP domain point, go to 10.
 Step  3   If the number of pieces added so far has reached an upper limit, go to 10.
 Step  4.  Pop the top piece in the priority queue for further refinement.
 Step  5.      Split the piece along the longest edge. 
 Step  6.      Build the new linear function for both pieces, noting max values.
 Step  7.      Add the two new pieces back to the IvP function.
 Step  8.      Add the two max-values back to the priority queue.
 Step  9.      Go to Step 2.
 Step 10.  Done.
\end{verbatim}
\end{listing}
\normalsize
\vspace{0.15in}

The first step in the algorithm is to build a priority queue similar
to the priority queue used in the smart-refinement algorithm. In this
case, the score associate with each piece in the queue is the maximum
value for the given piece, as depicted in Figure \ref{fig_pq_autopeak}
below. The maximum value is calculated quickly and directly from the
coefficients of the linear function associated with the piece. When
the auto-peak algorithm is initiated, it works with the IvP function
generated thus far during the prior phases of the
reflector-script. The priority queue is built by evaluating the
max-value for all pieces in this function.

\vspace{0.12in}
\begin{figure}[H]
  \centering
  \includegraphics[width=0.8\textwidth]{figs_ivpbuild/priority_queue_util.png}
  \caption{{\bf Priority queue keyed with maximum utility scores}: The
    \vvar{Reflector} uses a balanced priority queue based on a max
    utility score to determine which pieces could benefit the most
    from further refinement. Each node in the tree keeps a pointer to
    the piece that generated the maximum utility key.}
  \label{fig_pq_autopeak}
\end{figure}
\vspace{0.12in}

The algorithm terminates when either the top piece in the priority
queue contains only a single IvP domain point, or when auto-peak
refinement has generated a total of new pieces that exceeds a
specified optional limit. This is checked in steps 2-3 in Listing
\ref{lst_auto_peak}. When a piece is selected for further refinement,
it is split along the longest edge creating two pieces (one new piece)
regardless of the number of edges or dimensions. Linear regression is
performed on the two pieces and they are added back to the IvP
function and the priority queue. Typically, but not necessarily, the
piece with the maximum value in the priority queue is a result of the
most recent refinement.

%----------------------------------------------------------------------
\subsubsection{Invoking the Auto-Peak Algorithm in the Reflector}

Use of the auto-peak tool is done using the \var{auto\_peak} and
\var{auto\_peak\_max\_pcs} parameters in the Reflector
\func{setParam()} function first mentioned in Section
\ref{sec_reflector_interface}. The \var{auto\_peak} parameter simply
turns the tool on or off, with true or false. The
\var{auto\_peak\_max\_pcs} parameter sets an upper limit on the number
of new pieces introduced to an IvP function during the auto-peak
phase. The following shows an example usage:

\small
\begin{verbatim}
  reflector.setParam("auto_peak", "true") 
  reflector.setParam("auto_peak_max_pcs", 100) 
  reflector.create(1000);
\end{verbatim}
\normalsize

The upper limit on pieces is typically not needed, and the default
value is no limit. The algorithm tends to reach termination quickly
because the piece with the maximum point tends to always be at the top
of the priority queue, and in cases where the top ranked piece does
not contain the maximum point, this is resolved quickly as the piece
is split. Nevertheless, this upper limit is available for the
conservative user. It is worth noting that, for underlying functions
where the maximum value is part of a large plateau, the auto-peak
tool is likely to have little benefit. 

%\vspace{0.12in}
%\subsection{Remaining issues Regarding the {\tt Reflector} Tool}
%\subsubsection{Error-Checking in the Refine-Script Configuration}
%\index{Reflector Script!Error Checking}
%
%&gt; how the reflector maintains a priority queue of pieces during
%directed refinement, when certain pieces are ``thrown out''.
%
%
%o The configuration of the reflector can be parameterized in the
%behavior configuration block.
%
%
%
%Syntactic errors made in any of the \var{setParam()} calls to the
%\var{Reflector} can be detected in a few different ways. First, the
%\var{setParam()} call itself returns a Boolean, \var{false} if any
%errors are encountered. Second, the \var{Reflector} generates and
%maintains a list error messages, adding one to the list for each
%faulty \var{setParam()} invocation. Faults can be detected by the
%call:
%
%\small
%\begin{verbatim}
%  bool faulty = reflector.hasErrors();
%\end{verbatim}
%\normalsize
%
%\noindent
%If the caller wants the actual set of error messages:
%
%\small
%\begin{verbatim}
%  vector&lt;string&gt; %messages = reflector.getErrorsVector();
%\end{verbatim%}
%\normalsize
%
%\noindent
%If the caller wants the set of error messages all in one string:
%
%\small
%\begin{verbatim}
%  vector&lt;string&gt; messages = reflector.getErrors();
%\end{verbatim}
%\normalsize
%
%\noindent
%If errors are reported by the \var{Reflector}, it is recommended that
%the caller checks for these prior to invoking the \var{create()}
%function and abort at that point. If possible the error messages
%should be reported higher up. (In behaviors that use the
%var{Reflector}, error messages can be posted to the MOOS variable
%\var{BHV\_WARNING}). Error messages cannot be cleared from a
%\var{Reflector} instance. To start over, a new instance needs to be
%created.  Finally, the last form of error detection is by checking the
%number of pieces created by the refine-script. This number is returned
%by the \var{create()} function call. A return value of zero indicates
%that something went very wrong.

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