"Redux" is a software engineering tool that might be described as "Goal, Operator-Oriented Programming" (GOOP).
Computation starts with one or more goals. These at a minimum have a consequent, which is some string that will be matched later to one or more operators. From some set of matching operators, one is chosen. Applying the chosen goal must produce at least one of either an assignment or another (sub-)goal. Such an application is called a decision. (An operator application that does not produce at least one subgoal or assignment is an error.) As Redux was orignially constructed for design problems, these are sometimes referred to as "design decisions".
The assignments produced by a decision are statements about the emerging design, or plan. They may be structured assignments of values to variables or simple strings. In either case, they may violate stated constraints. A constraint violation can be resolved only by rejecting one or more decisions that support the violation. The options are determined by dependency-directed backtracking.
A goal is reduced when a decision is made for it. If no subgoals result, or all of the subgoals become satisfied, then the goal is satisfied.
Decisions may have contingencies associated with it. These are conditions that if true, make the decision no longer valid. When a decision becomes invalid, so do its subgoals and assignments, and its goal is no longer reduced. A decision may also become invalid when it is retracted in order to resolve a constraint violation.
The computation terminates when either all of the goals are satisfied, it is determined that they cannot be. When no operator is available to reduce a goal, a goal block results. This is treated the same way as a constraint violation. If it cannot be resolved by rejecting some of decision(s), then the computation terminates. If by search and backtracking it is determined that no consistent solution can be obtained, then the computation terminates. The one exception is that contributing constraints may be relaxed.
Redux compuations are not guaranteed to terminate because operators transform goals. If the resulting transformation produces subgoals based upon the goal, as is often the case, then this may continue indefinitely. However, if no new operators are generated (e.g. by gensym) during the computation, Redux will ensure that no previous state of problem-solving is revisited.
"Redux" per se is composed of two parts.There is a Redux planner that uses "Redux'" (Redux Prime), which is a large subcomponent that records design decisions and provides all of the bookkeeping about the dependencies among the decisions, including goal blocks and constraint violations.
The Redux Prime model of decisions, useful especially
for distributed design, is described in detail by:
"The Redux' Server," (PostScript) Proc. Internat. Conf. on Intelligent and
Cooperative Information Systems (ICICIS), Rotterdam, May, 1993.
The use of Redux Prime for concurrent engineering is described in
"Using Pareto Optimality to Coordinate Distributed Agents,"
with T. Webster and M. Cutkosky,
AIEDAM 9, 269-281, 1995.
Redux Prime was the core of the ProcessLink agent-based system and the commands are detailed as KQML messages. The core citation for Redux is "Context Maintenance", Proc. AAAI-91, pp. 288-295, July, 1991.
Redux proper is a planning tool, though not a planner directly. It can be used for general design, of which planning is a subset. However, it has a close relationship with planners and can be used to implement many planning strategies.
The closest planner to Redux is Prodigy to which is it useful to compare. Prodigy, like most planners, has a notion of a goal state that should be satisfied. This is done by incrementally changing the initial state by a set of operators. Each operator changes the state by adding and deleting certain features of the state.
In order to apply a given operator, certain pre-conditions must be met. These are typically state conditions which, if not present at the time of the operator action upon the current state, must be made the case by the action of prior operators. In Prodigy, this is done by a combination of generating a head plan that generates the current state and a tail plan that designs a plan for fulfilling the pre-conditions of the operators needed for the head plan.
One of the "insights" of Redux is that a goal state is never provably made true by the operation of a sequence of operators. Each operator claims to add and delete certain features of the given state. Redux generalizes this notion in that any given goal, representing perhaps a current state, has a single "consequent", which may be a string or a list of strings", for which some set of operators may be applicable, according to backward chaining rules.
To explicate this contrast further, in traditional planning, one might want to go from a state in which P(a) is true to a state in which P(a) is no longer true and R(a) is true. Perhaps there is an operator that claims that it deletes P(a) and adds R(a) as a state. In Redux, one would simply have a goal that might be structured such as (P(a) to R(a) ) and then have an operator that is provably applicable to such a goal. This in no way restricts the generality of Redux since a given operator might be provably applicable to a wide variety of goals depending upon how its applicability rules are written. Such an operator may also claim that if some set of subgoals are satisfied, then the top-level goal is satisfied. For instance, the operator might generate the subgoals (P(a) to S(a) ) and (S(a) to R(a) ) and claim that satisfying these strings means the satisfation of the string (P(a) to R(a) ) .
In both Prodigy and Redux, one must always trust the operator description that the goal(state) is eventually satisfied. That is, plan correctness is never guaranteed except to the extent that operator definitions can be trusted to be applicable to goals and the results as stated. Yes, Redux operators can make stronger claims in some sense, but formally, its operators are no less trustworthy than are Prodigy operators.
There is thus, no notion of correctness in Redux. In Prodigy, if all of the pre-conditions of all operators are satisfied before the operator is applied, the plan is valid but not necessarily correct. In Redux, instead of pre-conditions, there are only new goals that form an AND tree of satisfaction for a supergoal.
This Redux insight means that the head/tail planning algorithm can be abstracted to simply backward chaining as forward chaining. That is, given that an operator that should be applied to a current goal has pre-conditions that should be met, one can just express these as subgoals. Then each application of an operator may result in a set of new goals. Any goal is satisfied when a valid operator application results only in assignments: no new subgoals are generated. The top-level goal is satisfied when all subgoals have been satisfied. In Prodigy terms, this means that the plan is valid but not necessarily correct. In Redux terms, all goals are satisfied and the plan is "correct" only in that all of the operator applications are still valid and not in conflict with any constraints.
Like Prodigy, Redux is controlled by meta-rules. These can be used to determine the best operator to apply to a goal, or the best goal to work on now. However, Redux also has two other tasks to decide on at any given cycle. One is whether to work on a goal block, similar to a SOAR impasse. A goal block may result when no operator can be applied to an un-reduced goal. The meta-rules determine if such a goal block should be left until later, or, if it should be resolved as the current task. If the latter, meta-rules decide the resolution.
Another type of task comes from Redux's abstraction of conflict. Planners such as Prodigy have a built-in kind of conflict among operators and their sequence of additions and deletions of state features. In Redux, an operator only changes the design by adding a general sort of assignment. This may only be a string, such as "Use the decoder at step B", or it might be a formal assignment of a variable such as "Color(Box-1) := red ". Of course, this can also be a statement about a state feature at a given step in the plan "State(N-10) := Clear(block-1) ".
All conflicts in Redux are expressed in terms of constraint violations and only assignments can violate constraints. Constraints can be very general, but violations are always sets of nogood assignments. And since operator applications result in assignments, constraint violations are always resolved by one or more operator applications (decisions in Redux Prime) being rejected. Thus one other Redux planning task is to decide when to work on constraint violations, and given a violation to reject, which operator applications to reject.
Specifics on rules for operator application and meta-rules
are best left to the "readme" file, but both
Redux and Prodigy allow unification over specific bindings.
For instance, there may be be different instances of general
operators applicable at any given cycle, and there can be
meta-rules that express a preference over them. This level
of meta-rule binding for forward rules was proposed and
implemented by the Proteus implementation of Redux.
"Controlling Forward Rule Instances", Petrie and Huhns,
Proc. Avignon 88 Expert Systems and Applications, Avignon, pp.
383-398, 1988.
Redux was developed by attempting to solve a variety of design and planning problems using combinations of forward chaining, backward chaining, frames, and truth maintenance with dependency-directed backtracking. The observation was that what had become planning in the late 80's in AI was too restricted a formalism for a wide variety of problems. And also, a model for the use of a TMS was required. The general idea of simply recording the firing of a forward-chaining rule by adding the rule consequent as a node in a TMS network justified by the set of antecedents was clearly not sufficient as evidenced by the failure of numerous systems. The Redux Prime decision model provided semantics for the use of a TMS, and especially dependency-directed backtracking.
One of the primary functions of DDB in Redux is to ensure that the planner never loops in resolving either constraint violations or goal blocks. A related function is to ensure that the planner is notified when an earlier discarded operator application might again be applicable because the conditions for conflict that caused its removal no longer apply. This is very useful for distributed design, even in simple cases.
Redux is especially useful for incremental replanning and any general design problem that in which assumptions may be made about design decisions that may later turn out not to be true, and in which there are general constraints that may be violated as operators are applied in an attempt to satisfy goals. (In Redux goals are initially unsatisfied and constraints are initially not violated.) Ultimately, Redux is not a complete planner but rather a programming language supported by a notification system that is useful for a large class of problems.
The core citation for Redux is "Constrained Decision Revision," Proc. AAAI-92.