"Redux" is a software engineering technology that supports what might be suggestively described as "Goal, Operator-Oriented Programming" (GOOP). Redux is essentially a model for configuration problem solving[1], including management of change in solutions, first described in [2].
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 operator 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 configuration design problems, these are sometimes referred to as "design decisions".
|
|
| Generic Redux Decision | Example of two decisions for one goal |
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 (DBB)[3].
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 rejected in order to resolve a constraint violation.
If a computation uses specifically this model of design, it is a Redux Planner of which our current tool is but one reference model. The full Redux planner allows reasoning about which goal is to be worked upon next, what is the best operator to apply in the current context, when to work on resolving constraint violations, and which decision(s) to reject to resolve a given 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 may or may not be a Redux Planner. The dependencies produced by a GOOP-like computation may be managed by "Redux'" (Redux Prime) that records the 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 [4]. Redux Prime provides a novel model for using a TMS in maintaining dependencies. It differenciates between the reasons for a decision validity and decision optimality, and invalidates a decision only in case of the former. In general, the propagation of change in the current design is controlled by the dependency model of [4].
Many different computations can be translated into the GOOP model: almost any iterative search technique will do. Redux Prime does not actually care about how the decisions were made as long as the results can be transformed into Redux decision dependencies. Constraint propagation is an example of a computation that cannot be so translated.
A decision becomes invalid either because it has been rejected or because a contingency condition has become true. Optimality is lost when all of the reasons for making the decision have in turn become invalid, or when the goal associated with the decision has become invalid.
One special case of an optimality reason is that a previous decision, first made because it was better at the time, was rejected in order to resolve a constraint violation. Should other decisions contributing to the constraint violation be no longer the case, then there is no reason not to return to the earlier better decision: i.e., the total solution is no longer Pareto optimal. Redux Prime uses a type of nogood constructed by DDB to detect this condition and notify the decision owner. Redux Prime also ensures that no circularity can occur in the search for a consistent solution, using the same mechanism.
This is especially useful for design revision, espcially for replanning. The use of Redux Prime for concurrent engineering is described in [5]. Redux Prime has been re-implemented and re-used in several projects and referenced externally.. At Stanford, Redux Prime was the core of the ProcessLink agent-based system and the commands are detailed as KQML messages.
The Redux Planner not a planner directly. It can be used for general configuration 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[6].
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[7]. 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. Essentially, this means that DDB is used to maintain pareto optimality in the design, plan, or configuration. DDB is also used to generate for users the and/or tree of safe and non-subsumed design decisions that may be rejected in order to fix either a constraint violation or a goal block. For distributed use, Redux allows ownership of decisions and prevents non-owners from rejecting decisions.
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 technology supported by a notification system that is useful for a large class of problems.
That said, the Redux GOOP model is perfect for HTN planning. One need only define the goals and operators. Preconditions can be defined for operators, which are constraints on their application, so that planning is easy. The main difference with classical planning is that temporal constraints must be checked, so that interference of planned states does not occur (with the assumption of persistence of states.) Conjunctive goals are also acheived with such constraint checking[8].
[1] Automated Configuration Problem Solving,
SpringerBriefs in Computer Science, 2012.
Free pre-publication
version.
[2] "Constrained Decision Revision," Proc. AAAI-92
[3] "Revised Dependency-Directed Backtracking for Default Reasoning", Proc. AAAI-87, pp. 167-172, 1987.
[4] "The Redux' Server," (PostScript) Proc. Internat. Conf. on Intelligent and Cooperative Information Systems (ICICIS), Rotterdam, May, 1993.
[5] "Using Pareto Optimality to Coordinate Distributed Agents," with T. Webster and M. Cutkosky, AIEDAM 9, 269-281, 1995.
[6] "Controlling Forward Rule Instances", with M. Huhns, Proc. Avignon 88 Expert Systems and Applications, Avignon, pp. 383-398, 1988.
[7] "Reason Maintenance in Expert Systems", Kuenstliche Intelligenz,2(89):54-60, 1989.
[8]
"Planning Process Instances with Web
Services",
Proc. ICEIS AT4WS, 31-41, SciTePress, Milan, Italy, 2009.
dx.doi.org/10.5220/0002171400310041