39   Optional Advanced Features of the Reflector Tool


39.1 Preliminaries
     39.1.1 The Reflector-Script
     39.1.2 Specifying a Piece Shape or IvP Domain Point in String Format
     39.1.3 Specifying a Region of an IvP Domain in String Format
39.2 Optional Feature #1: Choosing the Piece Shape in Uniform Functions
     39.2.1 Potential Advantages
     39.2.2 Specifying the Piece Shape Implicitly from a Piece Count Request
     39.2.3 Specifying the Uniform Piece Shape Explicitly
39.3 Optional Feature #2: IvP Functions with Directed Refinement
39.4 Optional Feature #3: IvP Functions with Smart Refinement
     39.4.1 Potential Advantages
     39.4.2 The Smart-Refinement Algorithm
     39.4.3 Invoking the Smart-Refine Algorithm in the Reflector
39.5 Optional Feature #4: IvP Functions with Auto-Peak Refinement
     39.5.1 Potential Advantages
     39.5.2 The Auto-Peak Algorithm
     39.5.3 Invoking the Auto-Peak Algorithm in the Reflector


39.1   Preliminaries    [top]


The previous section discussed how to build IvP functions with the 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.

39.1.1   The Reflector-Script    [top]


The basic invocation of the Reflector 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 38.6. In reality the invocation of create() is comprised of a 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:

  • Uniform function creation
  • Directed refinement
  • Smart refinement
  • Auto-Peak 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.

39.1.2   Specifying a Piece Shape or IvP Domain Point in String Format    [top]


Aspects of the 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:

    "discrete @ x:5,y:5" 

A uniform function built over this domain with the above requested piece shape would have 35 pieces in a manner rendered in Figure 39.1.

Figure 39.1: 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 "discrete @ x:22,y:12". It may also be referenced by the string "native @ x:22,y:10".

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:

    "native @ x:5,y:25" 

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 39.1. 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, "native @ x:5,y:22.6" specifies a piece with five units on the y dimension, "native @ x:5,y:22.4" specifies a piece with four units on the y dimension. And when a native value is given exactly between two domain points, the value is rounded up, so "native @ x:5,y:22.5" specifies a piece with five units on the y'' dimension.

    A single point in the IvP domain can be similarly referenced. When the string "discrete @ x:5,y:5" is used to represent a piece shape, the numerical values represent the length of the piece. When the same string is used to represent a point in the IvP domain, the numerical values represent the index into the domain. For example, the circled point in Figure 39.1 can be be referenced by the string "discrete @ x:22,y:12". It may also be referenced by the string "native @ x:22,y:10". When a native values does not map exactly to a domain value, the nearest domain point is used.

39.1.3   Specifying a Region of an IvP Domain in String Format    [top]


Aspects of the Reflector tool require the specification of a 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:

    "native @ x:10:24,y:-25:20"

or equivalently,

    "discrete @ x:10:24,y:5:14"

This region is rendered in Figure 39.2. 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 "native @ x:10:24, y:-25:50" and "native @ x:10:24, y:-25:50000" would specify the same region given the example in Figure 39.2.

Figure 39.2: 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 Reflector. The region is specified by the string "discrete @ x:10:24, y:5:14" or "native @ x:10:24, y:-25:20". In this case smaller uniform pieces are applied within the region.

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

39.2   Optional Feature #1: Choosing the Piece Shape in Uniform Functions    [top]


39.2.1   Potential Advantages    [top]


By simply specifying the desired number of pieces, the 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 38.6.) 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.

39.2.2   Specifying the Piece Shape Implicitly from a Piece Count Request    [top]


When the 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 39.1, 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 39.1 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 39.1 below, and some examples are shown in Table 39.1.

Listing 39.1 - The heuristic for generating a uniform piece based on piece-count and domain.

   1  IvPBox buildUniformPiece(IvPDomain domain, int max_amount)
   2  {
   3    int dim = domain.getDim();
   4    vector<int>  pcs_on_edge(dim,1);
   5    vector<bool> pcs_maxed(dim,false);
   6    vector<int>  pts_on_edge(dim,0);
   7  
   8    // Store the number of points on an edge for quick reference
   9    for(i=0; i<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<dim; i++)
  18        done = done && 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<dim; d++) {          
  25            if(!pcs_maxed[d]) {              
  26            double ratio = (pts_on_edge[d] / pcs_on_edge[d]);
  27            if(ratio > 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<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 > 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] >= 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<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  }

The heuristic progresses by growing the number of "pieces on an edge", pcs_on_edge, on each dimension. The algorithm proceeds to grow the pcs_on_edge for each dimension until it cannot grow further. For example, in Figure 39.1 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 39.1). 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 39.1. 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.

RequestedAspectShapeActualPieces On thePieces On the
PiecesRatioof PiecePieces'x' Domain Edge'y' Domain Edge
630.78112x1436397
641.0125x1256488
5001.046x464842222
5120.9644x465062322
10000.9732x339923231
10241.032x3210243232
10251.032x3210243232
40001.016x1639696363

Table 39.1: 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.

    Consider how the heuristic performs instead on the 3D domain shown in Table 39.2. 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.

RequestedShapeActualPieces On thePieces On thePieces On the
Piecesof PiecePieces'x' Domain Edge'y' Domain Edge'z' Domain Edge
100100x100x10010010101
20072x72x10019614141
100044x46x5096822222
750023x24x25739244424

Table 39.2: 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.

    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.

39.2.3   Specifying the Uniform Piece Shape Explicitly    [top]


The piece shape used in a uniform IvP function can be set explicitly using the uniform_piece parameter in the Reflector setParam() function first mentioned in Section 38.4. For example, the uniform piece shown in Figure 39.3 can be requested as follows:

   reflector.setParam("uniform_piece", "discrete @ x:6,y:4");  
   int amt = reflector.create();  

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

Figure 39.3: 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 "discrete @ x:6,y:4" or "native @ x:6,y:20". This piece shape would not be resulting piece shape had the user simply requested 36 pieces given this domain.

    In summary, when the Reflector 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 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.

39.3   Optional Feature #2: IvP Functions with Directed Refinement    [top]


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 uniform_piece, refine_region, and refine_piece parameters in the Reflector setParam() function first mentioned in Section 38.4. For example, the IvP function shown in Figure 39.2 would be generated with the following lines:

Listing 39.2 - An example configuration of the Reflector tool using directed refinement.

   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();  

When the 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 39.1.1. 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 refine_region - refine_piece pairs prior to the invocation of the create() function. They must be added in pairs however since the refine_piece is always associated with the last specified refine_region.

For an illustrative case we return to the Gaussian function rendered in Figure 38.4:

where A=150, , and . 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 39.4, conceding for now that the approximation will be poor in the sub-region around the peak.

Figure 39.4: An initial IvP function approximation: The 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.

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 39.5 was identified for directed refinement, with much smaller pieces used in the sub-region.

Figure 39.5: An IvP function generated with directed-refinement: After an initial uniform function has been generated, the Reflector refines the function on the prescribed sub-domain of the function with much smaller pieces.

    The results in Table 39.3 below were generated by configuring the reflector-script to include directed-refinement on the underlying Gaussian function shown in Figure 39.5, in a manner similar to the four lines in Listing 39.2. Each row in the table below differs only in the size of the refine_piece shown in the second column.

CaseRefineTotalWorstAverageTime
 Edge SizePiecesErrorErrormillisecs
A426070.77600.010438.9
B516870.77600.012325.6
C611620.77600.014917.8
D78470.77600.017813.0
E86820.90930.021410.2
F95351.18950.02548.2
G104471.45890.03026.7
H113671.82630.03515.7
I122952.24700.04094.7
J132622.65270.04724.1
K142313.03210.05403.6
L152023.58860.06153.2

Table 39.3: Results of directed-refinement: Characteristics of 12 different IvP functions approximating the underlying function shown in Figure 39.4 and 39.5. Each function is built by starting with an initial uniform function and then performing directed refinement over the region by . The refinement piece size shown in the second column is the parameter that results in the 12 different functions.

    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.

    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 39.3 with Table 38.1. We look for cases in Table 39.3 that dominate cases in Table 38.1. 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).

39.4   Optional Feature #3: IvP Functions with Smart Refinement    [top]


39.4.1   Potential Advantages    [top]


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.

39.4.2   The Smart-Refinement Algorithm    [top]


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 , and these n values are used to determine the linear function for that piece:

The same n points are again evaluated using this newly determined linear function instead, producing another set of n values . The regression score is determined by:

The 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 39.6. This algorithm for implementing a priority queue can be found in [11]. 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)).

Figure 39.6: Priority queue keyed with regression scores: The Reflector uses a balanced priority queue based on a regression score to determine which pieces could benefit the most from further refinement.

    The 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.

    An example of the smart-refinement algorithm applied to the same Gaussian function shown in Figure 39.5 is shown below in Figure 39.7.

Figure 39.7: 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 39.4.

    The results in Table 39.4 show the results of applying the smart-refinement algorithm to the function in Figure 38.3. 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 38.1, 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!

CaseEdgePiecesWorstAvgTimePiecesWorstAvgTime
 Size ErrorErrormsec ErrorErrormsec
41025001.45890.023239.934450.85120.013970.1
51511563.45320.055118.920231.32410.022447.3
6206255.58550.101410.410931.98340.029727.6
7254007.797640.15856.57002.59240.036218.1
83028912.03470.23034.75052.39050.048011.3
94016924.29770.39192.829512.61920.08857.5
105010018.21130.59171.61753.41660.11944.3
11754942.06521.21430.9857.92360.31002.3
121002530.39382.02850.54312.38870.51881.2

Table 39.4: 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.

    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 39.4, 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 39.8.

Figure 39.8: 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.

39.4.3   Invoking the Smart-Refine Algorithm in the Reflector    [top]


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.

   reflector.setParam("smart_amount", 400);

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:

   reflector.setParam("smart_percent", 35);

There is a third parameter 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 smart_amount or smart_percent has been reached:

   reflector.setParam("smart_thresh", 0.05);

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 create() function call, and the smart threshold as the third argument:

   reflector.create(1000, 400, 0.5);

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:

   reflector.setParam("uniform_amount", 1000) 
   reflector.setParam("smart_amount", 400) 
   reflector.setParam("smart_thresh", 0.5) 
   reflector.create();

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

39.5   Optional Feature #4: IvP Functions with Auto-Peak Refinement    [top]


39.5.1   Potential Advantages    [top]


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 39.4 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 "heading=133, speed=3.2" and the peak of the IvP function is "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 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.

39.5.2   The Auto-Peak Algorithm    [top]


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:

Listing 39.3 - An overview of the auto-peak algorithm.

  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.

    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 39.9 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.

Figure 39.9: Priority queue keyed with maximum utility scores: The 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.

    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 39.3. 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.

39.5.3   Invoking the Auto-Peak Algorithm in the Reflector    [top]


Use of the auto-peak tool is done using the auto_peak and auto_peak_max_pcs parameters in the Reflector setParam() function first mentioned in Section 38.4. The auto_peak parameter simply turns the tool on or off, with true or false. The 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:

   reflector.setParam("auto_peak", "true") 
   reflector.setParam("auto_peak_max_pcs", 100) 
   reflector.create(1000);

    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.


Page built from LaTeX source using the texwiki program.