July 28th, 2012
PDP: A paradigm shift for NASA Space Shuttle Flight Design
During my time working on the Space Shuttle I developed at NASA/Johnson Space Center a Parallel Distributed Processing (PDP) package to distribute tasks such as Space Shuttle trajectory simulations across the Unix workstation network we had at Rockwell Space Operations. The basic idea is very simple (as many people have told me): find an idle workstation somewhere on the network and run a command there instead of on the user’s workstation.
Although it sounds straightforward, there are many issues and problems to be dealt with. Some examples:
- What exactly is an “idle” workstation?
- How to keep track of when a remote (distributed) task has finished.
- What do you do if a remote workstation crashes? How can you tell?
- How do you handle intermittent network connectivity problems?
- What do you do if someone logs onto a previously-idle workstation that you’ve distributed a task to?
The package was developed using Perl and C: Perl for the main tasks, and C for a daemon process and to use remote procedure calls (RPC). The project evolved from an idea to a simple script, then to a more sophisticated script, then to a fully-functional prototype. The estimated cost savings NASA realized from using the PDP software is about $40+ million dollars.
NASA apparently thought the idea, and the increased efficiency, was worthwhile and awarded me a NASA New Technology Award. I also received a Technology Utilization Award from Rockwell. The IEEE also invited me to make a presentation at a local chapter meeting.
Click the left button below to read the slides for the IEEE presentation. This presentation also contains results (using the prototype) from a project for Space Shuttle Flight Software upgrades where PDP reduced the compute time required from 378 days to under 12. A write-up summarizing the project was also published in NASA Technology Review magazine–click on the right button to read the article.
July 28th, 2012
There are many different optimization algorithms and methods. The goal of an optimization algorithm is to analyze the response of a system by varying a set of inputs (“factors”), and determining the set of factors which yields the “best” responses. To a certain extent the choice of what method to employ depends on the system being optimized. There is no one “best” method, and therefore it is essential to have several in your toolbox to use on various problems.
In most cases the input factors and responses are subject to constraints. For example, determining the optimum route and speed to fly a plane is subject to constraints such as air traffic restrictions, fuel capacity, weather, and airplane structural limitations. Optimizing the operations of a manufacturing plant is subject to constraints such as environmental regulations, safety limits of machinery, and raw materials costs. How easy it is to incorporate constraints is one criteria to consider when choosing an optimization algorithm.
This paper describes the Sequential Simplex Optimization algorithm, how it works, some of the issues to keep in mind when considering using it, etc. I proposed using Simplex optimization for Space Shuttle Flight Design and Dynamics (FDD) and I later used Simplex to optimize the fuel flow for the Interim Control Module (ICM) Propulsion Subsystem simulator/trainer for the International Space Station. The ICM system is diagrammed above. The station problem was rather large (26-dimensional) and there were many challenges in finding the solution. I wrote the algorithm, including constraint and vehicle simulation execution, in Python. It required some trial-and-error testing and adjusting, but in the end it worked.
Sequential Simplex Optimization Presentation (scanned pdf)
July 28th, 2012
This project researched the application of Sequential Simplex Optimization and Experimental Design concepts to the problem of optimizing some of the target values used in the Space Shuttle first stage guidance subsystem. Shuttle first stage employs “open-loop” guidance, essentially flying an attitude profile based on current speed. I first found the optimum targeting values and then modeled the response surface area around the optimum. Modeling the area (the response surface) around the optimum is critical because engineers must know how performance is impacted by minor targeting variations.
Optimized Space Shuttle First Stage Guidance Targets paper (pdf)
July 28th, 2012
Multi-Stage Monte Carlo Optimization
Monte Carlo optimization has been a widely used optimization method for many years. It’s very easy to understand: For a set of factors (independent variables), randomly select values for each factor to make a set of inputs to the system and test the system response for each set. For example, referring to the picture, we would pick different (x,y) value pairs and test the system response.
Monte Carlo optimization has several advantages:
- It will not be distracted by high variability in the system response since it doesn’t care what the response is.
- You do not need to have much of an understanding of the system response. You just define the range of values for each input and let the method randomly pick test sets.
Monte Carlo optimization also has several disadvantages:
- The method does not learn from test results as it runs. An area where the optimum probably is located may become clear after a certain number of tests but the method won’t know it and will just blindly keep testing random points.
- You often need a large sample size of points to find the optimum, and if each test is expensive (e.g., an airplane flight test or a complex manufacturing process) then the costs of using Monte Carlo would be prohibitive.
What would improve the method is a way to break up the sampling so that more points could be run in the area where the optimum value is more likely to be. This is what Multi-Stage Monte Carlo does, and I modified the method to adjust the sampling to handle cases where there are many local optima in the response surface. Today Monte Carlo optimization is not used as widely as before but there are times when it’s still the best method, and the Multi-Stage and Enhanced Multi-Stage algorithms can help to lessen some of the disadvantages.
Multi-Stage Monte Carlo Optimization Presentation (scanned pdf)
July 28th, 2012
Many of the same competing project forces which are common in the business world are also well represented in the Shuttle Program. The Space Shuttle has always been a work-in-progress, constantly being reviewed, revised, studied, and improved. How is this constant change managed? Projects compete for scarce resources (knowledgeable staff, funding, time, etc.). Complicating the management of these competing forces is the nature of the program: America’s National Space Transportation System. Although the day-to-day work becomes as routine as it does in most environments, what we all work on everyday (designing Space Shuttle missions) requires a special attention and thoroughness. This presentation will discuss Space Shuttle flight design and the challenges, risks, and opportunities unique to driving projects in the shadow of Apollo and the rarified air of mission control.
PM Challenges in the Space Shuttle FDD Program Presentation (pdf)