Browse Prior Art Database

Least Commitment Planning Algorithm for Generating an Optimized Sequence of Satellite Commands

IP.com Disclosure Number: IPCOM000040043D
Original Publication Date: 1987-Sep-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 3 page(s) / 45K

Publishing Venue

IBM

Related People

Crehan, DT: AUTHOR [+3]

Abstract

This article describes a method for dynamically calculating a plan of commands to change a system of equipment from one configuration to another without violating illegal configuration constraints and with a minimum of steps. This method solves the problem of generating and storing the large number of possible command sequences required to exhaustively encompass all the possible command sequences associated with a subsystem. An example of the problem addressed by this algorithm is depicted in Fig. 1. In this example, various pieces of satellite equipment are ON or OFF, namely, DCI-1 is OFF, MOD-1 is ON, and both HPAs are OFF. The goal is to turn HPA-2 ON. There is a constraint, however, which states that in order to turn an HPA ON, the active MOD must be OFF.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 56% of the total text.

Page 1 of 3

Least Commitment Planning Algorithm for Generating an Optimized Sequence of Satellite Commands

This article describes a method for dynamically calculating a plan of commands to change a system of equipment from one configuration to another without violating illegal configuration constraints and with a minimum of steps. This method solves the problem of generating and storing the large number of possible command sequences required to exhaustively encompass all the possible command sequences associated with a subsystem. An example of the problem addressed by this algorithm is depicted in Fig. 1. In this example, various pieces of satellite equipment are ON or OFF, namely, DCI-1 is OFF, MOD-1 is ON, and both HPAs are OFF. The goal is to turn HPA-2 ON. There is a constraint, however, which states that in order to turn an HPA ON, the active MOD must be OFF. There is also a constraint which states that in order to turn a MOD OFF, the active DCI must be OFF. The five step command block which turns HPA-2 ON while satisfying the constraints is as follows: COMMAND BLOCK:

- DCI-2 OFF

- MOD-1 OFF

- HPA-2 ON

- MOD-1 ON

- DCI-2 ON Note, however, that there are two possible DCIs, two possible MODs, and two possible HPAs, implying a total of eight possible command blocks. That is, the required command sequence is a function not only of what boxes are to be swapped, but also of what other boxes are currently active and of what constraints exist. The combinatorial explosion of possible command sequences makes it difficult to work with pre-canned command blocks. Instead, this problem seems best addressed by a process that would generate commands at "decision time" while taking into account what boxes are currently active and what constraints are currently applicable. This algorithm is illustrated by the example in Fig. 2.

There are three relays X, Y and Z, each with a current position of OFF and a desired final position of ON and two constraints. The first constraint states that "to get Relay Y into position ON, we must first get Relay X into position ON," and the second constraint states that "to get Relay Z into position ON, we must first get Relay Y into position OFF. When the algorithm begins, it has no idea which relay should be toggled first (that is what it is supposed to determine) and so must arbitrarily pick one. To take the simplest case first, suppose Relay Z is selected. The only constraint to turning Z ON is that Y must be OFF, but Y is already OFF and so Z can go ahead and toggle to ON. Next, suppose the algorithm happens to pick Relay X. In this case, there...