START Optimization Tools

Note: This page describes a software tool that is used to optimize portfolios of missions, systems, or technologies. In 2007/8, the START team developed a separate software tool, called HURON, for optimizing the allocation and scheduling of tasks to be performed by humans and robots on the Moon. That tool is described here.

The START team has developed version 1 of a unified, multipurpose software tool designed to enhance the speed and reliability of our analyses while retaining all of the flexibility of our past efforts. We believe that decision-makers will find this tool extremely useful in helping them to form and support their decisions.

The tool combines the best features of the tools and methodologies applied to previous studies and adds new capabilities.

Scaling

The START tool accommodates as many system levels as desired: programs of multiple missions (e.g., traveling to the Moon, prospecting for lunar resources, exploiting those resources and returning to Earth), single missions (e.g., prospecting for lunar resources), individual systems (e.g., robotic rovers), subsystems (e.g., instruments), and contributing technologies (e.g., a tunable laser used in an instrument).

Uncertainty

Much of the input on which the analysis depends is in the form of predictions and estimates by experts, which often contain a great deal of uncertainty. START enables the user to manage this uncertainty in two ways.

First, it allows many of the values to be expressed as ranges, rather than as specific amounts. These include the System Architect's statements of required performance and corresponding utility, and the technologists' assessments of predicted performance, development cost and probability of success.

Second, the tool includes the ability to determine the sensitivity of the results to variations in the input values. Thus, the selection of a particular capability for an optimal development portfolio may be shown to be robust even if there is considerable uncertainty about the values that were input for it, while selection of another may be highly dependent on a narrow range of input values.

Scheduling

In addition to "static" analyses, in which portfolios are assembled based on return on investment without consideration of scheduling, the START tool is capable of temporal analysis, which calculates not only which capabilities to fund but also when to fund them in order to make the best use of the varying annual budgets that are expected.

Interrelationships

The START tool recognizes interrelationships among capabilities and missions, and factors them into its calculations.

Where a mission is dependent on a certain set of capabilities, those capabilities are designated as "enabling" and all of them are fully funded. If one or more of them cannot be completely funded, the mission is not selected to proceed. Much greater flexibility is accorded capabilities that are designated as "enhancing." These would improve the performance of the mission but are not required. At the sponsor's discretion, they may be selected for partial funding to the degree that monetary resources permit.

Where a set of missions is dependent on another mission (for example, a mission to explore for water ice at the south lunar pole depends on the success of a mission to travel from Earth to the Moon), the tool makes sure that the dependent missions are selected to proceed only if the "parent" mission has been enabled.

If one capability is dependent on another (for example, a laser-guided descent system may depend on development of a certain laser), the tool makes sure that the dependent capability is included in the portfolio only if all of its parent capabilities are funded.

The default method of determining a capability's value is based on its importance to the mission(s) being analyzed. When considering capabilities that support more than one mission in a particular study, the START tool credits these capabilities with increased value over those that support only one mission, and avoids funding the same capability more than once.

Preferences and non-technical constraints

The START tool accommodates weighting of missions and desired capabilities to reflect the preferences of the decision-makers. It also accommodates non-technical constraints, such as workforce considerations or congressionally mandated tasks, that need to be included in the calculations.

In addition to calculating the optimal portfolio for a given set of inputs, the tool can solve for the best portfolio that includes a specified component (K-best analysis).

Under the hood

The tool is written in Python, a popular open-source programming language used by NASA, Google, and Industrial Light & Magic, among many others. Python features extensive libraries and is compatible with Windows, Linux/Unix, Mac OSX, and all other major operating systems. Its object-oriented nature permits a modular architecture that makes our tool very flexible and responsive to the needs of our sponsors. Interfaces allow it to communicate with other packages such as Microsoft Excel.

We also use open-source problem solvers which match or exceed the performance of Excel's premium solver.

Inputting data

The examples presented here are from a demonstration study we conducted for NASA of a mission to the lunar south pole.

Input is divided into three categories, each with its own Excel-based data sheet: Management data, System Architect data, and Technologist data. Based on the information provided in the data sheets, the START tool generates a database which interfaces with modules that permit various kinds of data analysis.

Illustrative portion of a Technologist data sheet, showing the general data-sheet format. Please note that all numbers on this example are for illustration purposes only. Similar data sheets collect information from Management and System Architects.

In addition to the three Excel spreadsheet formats, the user can review the input in a hierarchical viewer (based on an open-source package called "TreeLine") that combines all three sets of data. This can be a handy method of getting an overall picture and trying out alternative values for the data in "what if" scenarios.

Users can opt to view the data compiled into a single hierarchical list.

Selecting the analysis

Four different kinds of analysis are available.

Four types of analysis are available to calculate optimal portfolios and development schedules, and to test sensitivity of the results to changes in the data.

Static analysis assembles optimal portfolios of capabilities based on expected utility and budget constraints.

Temporal analysis uses the same criteria to assemble optimal capability portfolios, and also recommends scheduling of the development of each selected capability so as to make the most efficient use of the varying budgets predicted for each year.

Monte Carlo analysis tests the sensitivity of the results to changes in the values assigned on the data sheets. This provides a measure of how robust the results are, given the uncertainty inherent in many of the estimates. Typically, the expected cost and utility for each capability is varied randomly within a specified range (e.g., within 10% or 25% of the value stated in the data sheets, or within the ranges given in the data sheets), and 1000 runs are conducted. Capabilities that are selected in the largest percentage of these runs are considered stable. Those that are selected in only a small percentage of runs are considered unstable; the values assigned to their expected cost and utility are much more critical in determining whether they belong in an optimal portfolio.

K-best analysis identifies the second-best, third-best, etc. portfolios for a given budget. This can be useful if a non-technical constraint becomes known which eliminates the optimal portfolio as the best choice. For example, a politically favored technology or capability may first show up in a portfolio ranked third best in terms of expected cost and utility under the initial set of constraints. Also, capabilities that are selected in a large number of highly ranked portfolios may be considered more robust than those that are not, and thus K-best can serve as a quick sensitivity analysis when there is insufficient time to conduct a more-detailed Monte Carlo analysis.

Examining the results

Before running the analysis, the program performs a first-order "sanity" check. This lets the user know, without spending the time to run the analysis, whether there is sufficient budget to fund all of the enabling capabilities of each mission under consideration (if not, the mission cannot proceed), and whether all of the required data has been provided (if not, the missing metrics will not be considered when the analysis is run).

While the analysis is running, a log informs the user of the progress toward an optimal solution. Running time depends on the speed of the computer, size of the problem, and type of analysis selected. On a current laptop running a temporal analysis of 6,000 variables, the optimization would take about 30 seconds and the end-to-end duration, including pre- and post-processing (including generation of graphs and tables), would be on the order of 2 or 3 minutes or less.

The time needed for a Monte Carlo analysis would depend on how many runs are desired. A typical set of 1000 runs would take 1000 times the 30 seconds needed for optimization, plus perhaps another couple of minutes to generate graphs and tables.

The program can be interrupted at any point if the user, monitoring the progress on the log window, decides the solution is close enough and opts not to wait for further processing. The program will then present the latest iteration as the result.

Click here for larger image.

This graph illustrates the optimal schedule for funding development of capability areas in our demonstration study. Note how closely the recommended expenditures (bars) follow the expected budgets for 2007 through 2012 (black line). Similar graphs (with accompanying tables) present portfolios for the entire group of lunar missions; individual missions and capability areas that are reserved (i.e., mandated by Congress or another entity), enabling, and enhancing; how the work is distributed among NASA centers; and combinations of missions and capability areas. Deeper levels are also possible, down to individual technologies.

"What if" analyses

A user can easily conduct additional "what if" runs with alternate values for mission weights and yearly budget caps without having to change them on the data sheets. The number of partial funding intervals can also be quickly changed if the user wants to see how the results would differ if enhancing capabilities were allowed to be funded at, for example, 33% and 66% in addition to 100%. Partial funding can fill the gaps between the budget cap and the total amount spent on fully funded capabilities in a given year, thus allowing "leftover" portions of the budget to be used productively.

In future versions of the START tool, the user will also be able to modify the objective function for these "what if" analyses. This will enable some users to more accurately express their attitudes toward risk, or to express preference for certain capabilities.

Evolution of the tool

The START tool is continually being advanced by testing new elements in pre- or post-processing stages. This allows us to fine-tune them and to confirm whether they really add value to the analysis without risking any ill effect on the tool's stability. Operations that prove themselves during this process will ultimately become part of the tool, itself.

While the tool reflects our desire to unify, to a large degree, the analyses we offer, we expect always to take advantage of the tool's flexibility to ensure that it meets the specific needs of whatever decision-making processes we are asked to support.