The Automated Scheduling and Planning Environment (ASPEN) software system, aspects of which have been reported in several previous NASA Tech Briefs articles, includes a subsystem that utilizes a portfolio of heuristic algorithms that work synergistically to solve problems. The nature of the synergy of the specific algorithms is that their likelihoods of success are negatively correlated: that is, when a combination of them is used to solve a problem, the probability that at least one of them will succeed is greater than the sum of probabilities of success of the individual algorithms operating independently of each other. In ASPEN, the portfolio of algorithms is used in a planning process of the iterative repair type, in which conflicts are detected and addressed one at a time until either no conflicts exist or a user-defined time limit has been exceeded. At each choice point (e.g., selection of conflict; selection of method of resolution of conflict; or choice of move, addition, or deletion) ASPEN makes a stochastic choice of a combination of algorithms from the portfolio. This approach makes it possible for the search to escape from looping and from solutions that are locally but not globally optimum.
This program was written by Robert Sherwood, Russell Knight, Gregg Rabideau, Steve Chien, Daniel Tran, and Barbara Engelhardt of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.techbriefs.com/tsp under the Software category.
This software is available for commercial licensing. Please contact Don Hart of the California Institute of Technology at (818) 393-3425. Refer to NPO-30379.
This Brief includes a Technical Support Package (TSP).
Using a Portfolio of Algorithms for Planning and Scheduling
(reference NPO-30379) is currently available for download from the TSP library.
Don't have an account?
Overview
The document is a NASA Technical Support Package detailing the use of algorithm portfolios for planning and scheduling, specifically in the context of space mission operations. It highlights the innovative approach of combining multiple algorithms that work synergistically to solve complex problems. The core idea is that these algorithms are designed to be negatively correlated in their success probabilities, meaning that the likelihood of at least one algorithm succeeding is greater than the sum of their individual success probabilities. This synergy enhances the overall effectiveness of the problem-solving process.
The report discusses the ASPEN (Automating Space Mission Operations using Automated Planning and Scheduling) system, which employs a stochastic combination of a portfolio of choice heuristics. At each decision point in the planning process—such as conflict selection, resolution method selection, and activity selection—ASPEN makes stochastic choices from a user-defined set of heuristics. This method allows the system to escape local minima and looping issues, thereby improving responsiveness and enabling the resolution of a wide range of real-world planning and scheduling challenges.
The document also references several key publications and research efforts that contribute to the understanding and development of automated planning and scheduling systems. Notable works include studies on iterative repair methods and the application of automated planning in goal-based autonomous spacecraft. The authors of the report, including Steve Chien, Barbara Engelhardt, Russell Knight, and Gregg Rabideau, are recognized for their contributions to the field.
In summary, the document emphasizes the importance of algorithm portfolios in enhancing the capabilities of automated planning and scheduling systems, particularly in the context of space missions. By leveraging the strengths of multiple algorithms, these systems can achieve greater success in complex problem-solving scenarios, ultimately leading to more efficient and effective mission operations. The insights provided in this report are valuable for researchers and practitioners in the fields of artificial intelligence, robotics, and space exploration.
