Several algorithms developed for use in automated planning and scheduling of sets of interdependent activities employ aggregation techniques to increase the efficiency of searching for temporal assignments that are legal in the sense that they do not violate constraints. In the aggregate-search approach, one computes the aggregate state and resource requirements of a cluster of interdependent activities and searches for minimally conflicting temporal placements for the corresponding cluster of requirements. During the search, all activities that temporally constrain each other (for example, as in the requirement to complete activity A before starting activity B) are moved in unison. In computational tests based on a synthetic planning and scheduling problem and on problems from spacecraft and Rocky-7 Mars Rover operations, the aggregation-search algorithms were found to out-perform alternative algorithms that follow the "naïve" approach of searching for legal placements of the constituent activities individually.
This work was done by Steve Chien, Russell Knight, Gregg Rabideau, and Robert Sherwood of Caltech for NASA's Jet Propulsion Laboratory. For further information, access the Technical Support Package (TSP) free on-line at www.nasatech.com/tsp under the Materials 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-20660.
This Brief includes a Technical Support Package (TSP).
Aggregate-Search Approach for Planning and Scheduling
(reference NPO-20660) is currently available for download from the TSP library.
Don't have an account?
Overview
The document discusses the "Aggregate-Search Approach for Planning and Scheduling," developed by a team at NASA's Jet Propulsion Laboratory (JPL), including Steve Chien, Russell Knight, Gregg Rabideau, and Robert Sherwood. This approach addresses the challenges of automated planning and scheduling of interdependent activities, particularly in complex environments such as spacecraft operations and planetary rovers.
The core of the aggregate-search method lies in its ability to enhance the efficiency of searching for temporal assignments that comply with various constraints. Traditional methods often involve searching for legal placements of activities individually, which can be computationally expensive and inefficient, especially as the number of activities and their interdependencies increase. In contrast, the aggregate-search approach computes the aggregate state and resource requirements for a cluster of interdependent activities, allowing for a more streamlined search process.
During the search, activities that temporally constrain each other—such as the requirement to complete one activity before starting another—are moved in unison. This collective movement reduces the complexity of the search space and minimizes conflicts, leading to more efficient scheduling outcomes. The document highlights empirical tests conducted on synthetic planning problems and real-world scenarios from spacecraft and Mars Rover operations, demonstrating that the aggregation-search algorithms significantly outperform the naïve approach.
The findings indicate that the aggregate-search method not only reduces the overall time required to reach a valid scheduling solution but also improves the quality of the solutions obtained. The document emphasizes the importance of this work in the context of automated planning and scheduling, which has applications across various fields, including resource management and supply chain operations.
Additionally, the software developed from this research is available for commercial licensing, with contact information provided for interested parties. The document serves as a technical support package, detailing the methodology, results, and implications of the aggregate-search approach, while also noting that the work was carried out under contract with NASA.
In summary, the aggregate-search approach represents a significant advancement in the field of automated planning and scheduling, offering a more efficient and effective means of managing interdependent activities in complex operational environments.
