Aggregate-Search Approach for Planning and Scheduling

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.