An Introduction to the IvPBuild Toolbox
Maintained by: mikerb@mit.edu Get PDF
src: project-pavlab/chapters/chap_bldu_overview
1 Introduction to the IvPBuild Toolbox
1.1 Brief Overview
1.1.1 Where to Get the IvPBuild Toolbox
1.1.2 What is an Objective Function?
1.1.3 What is Multi-objective Optimization?
1.1.4 What is an IvP Function?
1.1.5 Why the IvP Function Construct? A Brief Description of the Solver
1.1.6 Properties of the IvPDomain Class
1.2 Tools Available in the IvPBuild Toolbox
1.2.1 The ZAIC Tools for Functions with One Variable
1.2.2 The Reflector Tool for Functions with Multiple Variables
1.2.3 The Coupler Tool for Coupling Two Decoupled IvP Functions
1 Introduction to the IvPBuild Toolbox
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 ???, the creation of an IvP function required only about a dozen lines of code using two different methods available in the IvPBuild Toolbox.
1.1 Brief Overview [top]
An instance of the class 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 1.1: An IvP function approximating an underlying function: The fview tool is used to render an IvP function with 289 pieces to approximate a given function, shown below the IvP function.
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.
1.1.1 Where to Get the IvPBuild Toolbox [top]
The IvPBuild Toolbox is part of the standard moos-ivp bundle distributed from www.moos-ivp.org. See Section ???. In the software tree it is entirely contained in the module lib_ivpbuild.
1.1.2 What is an Objective Function? [top]
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.
1.1.3 What is Multi-objective Optimization? [top]
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.
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{?} , 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.
In repeatedly applying multi-objective optimization to the output of behaviors in an on-board 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 priority weights assigned to each function, and the multi-objective optimization problem is reduced to a single objective optimization problem, given k functions and being the weight of the ith function:
The properties of IvP multi-objective optimization and solution algorithms were discussed in Section ???.
1.1.4 What is an IvP Function? [top]
An IvP function is a piecewise linearly defined function where each piece has an upper and lower boundary (or 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 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.
An IvP function as an instance of the IvPFunction class defined as part of the lib_ivpcore module included in the basic software bundle distributed from www.moos-ivp.org.
1.1.5 Why the IvP Function Construct? A Brief Description of the Solver [top]
The IvP function construct was chosen because it balances three aspects needed for use in the extendable behavior-based autonomy philosophy.
- 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.
- 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.
- 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.
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{?} .
1.1.6 Properties of the IvPDomain Class [top]
The domain of an IvP function is an instance of the class 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 decision space. The 2D base of the cube in 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. shows an example domain with three variables as it would be specified within the MOOS configuration block for the pHelmIvP process. See Listing ???.
Listing 1.1 - An IvP domain with three variables, as specified in pHelmIvP configuration.
1 Domain = course:0:359:360 2 Domain = speed:0:3:16 3 Domain = depth:0:500:101
Each line augments the initially null domain with a new variable. The first of four arguments is the variable name, e.g., 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.
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 AOF class described in Section ???. 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:
Domain = depth:0:500:101
It could not be defined over:
Domain = depth:0:100:101
To facilitate the proper creation of sub-domains, the following function is provided in the build toolbox (in BuildUtils.h in lib_ivpbuild):
IvPDomain subDomain(IvPDomain original_domain, string variable_names);
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 domain.size(), which returns the number of domain variables. A proper sub-domain of the domain shown in , with only the depth variable, could be created with the following function call:
#include "BuildUtils.h" ... domain = subDomain(original_domain, "depth");
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.
A call to 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 isRunnable() function call described in Section ???. This will cause an error message to be posted to the BHV_ERROR variable and result in the helm posting all-stop values to its actuators.
1.2 Tools Available in the IvPBuild Toolbox [top]
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.
1.2.1 The ZAIC Tools for Functions with One Variable [top]
The ZAIC tools are used for functions defined over a single decision variable. An example is shown in 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{?} ).
Figure 1.3: An objective function with a single decision variable: This function assigns a maximum utility to depths in a range of roughly meters. A linear decrease in utility is associated with depths outside this interval up to another additional 20 meters.
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 ZAIC_PEAK utility is a tool in the ZAIC toolbox used for automating the production of IvP piecewise functions of the form shown in . It is described in Section ???.
1.2.2 The Reflector Tool for Functions with Multiple Variables [top]
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 . 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 ???, but the basic usage boils down to the following:
- Create an instance of the underlying function to be approximated.
- Create an instance of the Reflector, passing it the underlying function.
- Invoke the Reflector with a requested number of pieces.
- Retrieve the new IvP function from the Reflector.
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:
- The Directed Refinement Reflector option.
- The Smart Refinement Reflector option.
- The AutoPeak Refinement Reflector option.
The details of these advanced options are discussed in Section ???. Each of the advanced tools are used after an initial basic uniform function has been generated. The directed refinement option allows the user to specify subsets of the domain and use pieces of different sizes for that region only. The 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 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.
1.2.3 The Coupler Tool for Coupling Two Decoupled IvP Functions [top]
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:
- Create the two independent IvP functions.
- Create an instance of the OF_Coupler class.
- Pass the two functions to the Coupler.
- Retrieve the new IvP function from the Coupler.
This tool was used in the example SimpleWaypoint behavior of Section ??? in Listing ??? 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.
Document Maintained by: mikerb@mit.edu
Page built from LaTeX source using texwiki, developed at MIT. Errata to issues@moos-ivp.org. Get PDF