Algorithm Builder

Algorithm Builder

The Algorithm Builder allows you to create a custom algorithm based on a variety of customizable criteria. It provides up to three sort steps. For each sort step, you can specify Prior Groups, External Figure of Merit, Greedy Figure of Merit, Expand All Tasks At End, Expand After Each Try, a search step (ordered, neural, or DS1MPS), a number of tries, a time limit, and end-of-trial output (text best, XML best, text last, XML last). The Algorithm Builder can generate and save an XML file containing your specified options. Click Go to obtain a schedule solution using your custom algorithm.

The available algorithm options are as follows:

  • Number of Sort Levels
  • Sort Types (per level)
  • Algorithm Modifiers
  • Search Method
  • Search Options

Initial Parameters

The algorithm Builder allows you to use existing algorithms as starting point for new custom algorithms. To load an existing algorithm's parameters and options, select the algorithm by name in the "Initialize Parameters to Primary Algorithm (Optional)" area of the Algorithm Builder UI.

Sort Parameters

The Sort Parameters allows you to specify how many levels of sorts are to be performed (1, 2, or 3) or not at all (none). Additionally, each Sort level can be set to use different attributes to sort on. A or D indicates an ascending or descending sort. in all cases the sort is done on the slots in a particular priority group.

Non-Random Sort Types:

  • List A/D: Sorts slots based on the order that they were written in the input file. Task slots, or profiles, remain in list order as the default.
  • Priority A/D: Sorts slots by priority. In most cases it is better to use priority groups instead of PriorityA.
  • EarlyStart A/D: Sorts slots by the start time of the slot. Slots with the earliest start are sorted to the top of the list.
  • LatestStart A/D: Sorts slots by the stop time of the slot. Slots with the latest stop are sorted to the top of the list.
  • Desire A/D: Slots are sorted by desirability. For example, if Sort1(desireA) is used, slots are sorted by desirability (ascending), but if two slots have the same desirability then the original slot list order is used.
  • Slack A/D: Slots are sorted based on the total slack. Slack is the slot duration minus the task minimum duration.
  • Slack Ds1: This sort provides backwards compatibility with the first generation (pre-2008) algorithm. It is assumed that there is only one priority group and computes a total slack for all slots associated with a task. It is used as part of the original MPS algorithm.
  • TaskSlotTime A/D: Sorts based on the total slot time available to a particular task.

Random Options

The following random sort options should always be the last sort parameter. Instead of sorting, these options will randomize the slots that are equal based on the prior sort option. This allows the multiple try parameter to be used to search for other solutions in a Monte-Carlo fashion.

Random Sort Options:

  • Random: Randomizes slot selection order within a priority group.
  • RanTask: Sorts slots based on an initial randomize task order.
  • RotateProfile: Sorts slots by rotating the chosen possibility order for each task.
  • RanProfile: Randomizes slots on an initial randomized possibility order.
  • RanProfilePerTask: Sorts slots using a randomize possibility order based on the possibilities for each particular task.
  • RanSlot: Same as random.
  • RanDS1: RanDs1 mimics a method from the pre-2008, which was used as part of the MPS algorithm. It randomizes the first slot chosen for a task, but leaves the remaining slots in list order.

If multiple sorts are used, they are nested within each level. For example, an algorithm with Sort1 being DesireD and Sort2 being earlyStartD, a schedule with 4 tasks (3 with desirability of 80, and 1 with a desirability of 70), the 3 "80"s will be considered first. Within that group of 3, the task with the earliest start time will be considered first, then the next start time, and then finally the latest of the start times. Only after these 3 tasks have been considered will the 4th task with a desirability of 10 be considered for scheduling.

Algorithm Modifiers

Modifier Types:

  • Expand After Each Task: After each task assignment, an attempt is made to expand the single task to full desired duration.
  • Expand After Each Try: After each try in a trial the routine that attempts to expand all tasks as described above. This is done before FOM calculation that is used to choose the best try.
  • Expand All Tasks At End: The expansion is attempted after all tasks have been assigned the minimum duration if possible. The task duration is expanded from minimum to maximum possible or desired in as many as 20 iterations. Initially, a task can have as much as an additional 1/10 of (Max duration min duration) per iteration. An adaptive algorithm adjusts the amount of extra duration per iteration dependent on the characteristics of the problem. Tasks are iterated in the original list order. Tasks are allowed to move other tasks later in time in order to complete the expansion. This is the most common expand modifier.
  • Expand Multi-Segment Tasks Up Front: When used Handover tasks will be expanded fully and at the beginning of the priority group. This allows for backwards compatibility to performance that occurred just after handover tasks were introduced in 2004. It may be used in combination with the useExpandAllTasksAtEnd modifier.
  • Pre-Assign and Expand Soft Tasks: In some problems, a task may have all soft resources, which means resource constraints are not binding on that task. An example is a solar panel charging a battery. A task is created to charge the battery whenever the solar panel can see the sun. However if the panel is fully charged then no more charging is allowed. The upper limit is a soft limit. Even though the task is assigned after the limit is reached, the value of the resource is limited to the maximum. The task is termed a soft task. The lower limit is generally hard. If the battery is depleted, than no more tasks can be assigned that need battery power. While the soft tasks are not limited, other tasks that deplete the task may be. Thus, it is best to assign them first. This modifier instructs the algorithms to a pre-search for any such tasks and assign them.
  • Use External FOM: Allows you to manually specify an external FOM.
  • Use Greedy FOM: The normal ordered search takes the slots in the sort order (within priority groups, if used). This modifier tells the algorithm to compute the expected increase in FOM for every available slot each time an assignment occurs. The slot group is restored using the information. Thus the slot with the highest expected FOM is tried next. The slot may or may not be used depending on the other problem constraints. This modifier puts a strong premium on the Figure of Merit. This does mean it will find the best overall FOM. Short term (greedy) choices may lock out better global solutions.
  • Use multi Try in Priority Groups: Multiple tries are done for each priority group. Improves yields if a later successful task assignment in the priority group add resources that allows additional tasks to be assigned.
  • Use Priority Groups: Turns on the use of priority groups. Before any other sort is done, all slots are gathered into groups with identical properties. Using priority groups instead of a simple sort allows the priority of a task to be given elevated status in the algorithms
  • Use Next Available Slot: If the current task is part of a sequence (task sequences are defined in the input specification file) and the current task can be assigned, then the next slot checked will be for another task in the same sequence. This increases the probability that sequences are completed. This operation is done within the current priority group. (Individual tasks in a sequence have the same priority and thus are always in the same priority group.)

Search

Search Types:

  • Ordered: An ordered search is as described. For each priority group, the slots (and corresponding task) are tried in the sorted order. If a task is successfully assigned to the task, then later slots associated with the task are skipped.
  • Neural: The neural search option implements a search that competes all possible slot solutions against each other. This search option is used without sort parameters since their order is ignored. The only modifier that is fully operational with neural is the expandAllTasksAtEnd.
  • DS1MPS: This search is included to allow for backward compatibility with a standard algorithm available prior to 2008, the MPS algorithm. Providing sort options, in addition to DS1MPS, can slightly alter the results in some cases, but is not recommended. The only modifier that is fully operational with neural is the expandAllTasksAtEnd.

Search Options:

  • # of tries for the neural search or random sort: Number of times the algorithms run with different seeds. The algorithms will then select the highest scoring solution.
  • Time Limit: Unlimited or limited amount of time prior to the algorithms ceasing scheduling activities.

Trial output

The output option specifies if and how the solution will be saved to a file.

Custom Algorithm Use

After All options are configured for the custom algorithm, select the "Add Trial" button and then "Save Solution". This will open a Window Save pop up where you can name and place the new custom algorithm. To set STK Scheduler to use the custom algorithm file, Navigate to Schedule -> Schedule Properties Algorithm Tab. Select the Custom radio button, enter/navigate to the Custom Algorithm File, and Select OK. STK Scheduler will now use the custom algorithm when the "GO" button is selected to run the Algorithms.