• Production system engine algorithm, for
    • No environment
    • Deterministic, non-decomposable, recoverable, any solution problem
    • Choose state, expand all ways
    Suitable for, e.g., a theorem prover 
    Problem = SenseProblem();
KB += StaticPartOf(Problem);
CurrentState = DynamicPartOf(Problem);
NewStates = {CurrentState};
DynamicStateSpace = {};
FrontierStates = {};
while (! SolutionFound(NewStates)) {
    FrontierStates += NewStates;
    StateToTransform = ExtractStateToTransform(FrontierStates,KB,DynamicStateSpace);
    NewStates = ApplyAllTransformations(StateToTransform);
    DynamicStateSpace += StateToTransform;
}

  • To extend the basic algorithm to a best solution (e.g., a journey planner in a perfect world), call ... 
    SolutionFound(NewStates,FrontierStates)
    and install ... 
    SolutionFound(NewStates,FrontierStates) {

    static BestSolutionSoFar = NULL;

    //----Update best state so far
    foreach (State in NewStates) {
        if (IsSolution(State) && State > BestSolutionSoFar) {
            BestSolutionSoFar = State;
        } 
    }
    //----Check if there is hope for improvement
    foreach (State in NewStates + FrontierStates) {
        if (State could get better than BestSolutionSoFar) {
            return(FALSE);
        }
    }
    return(TRUE);
}

  • Production system engine algorithm, for
    • No environment
    • Deterministic, non-decomposable, backtrackable, any solution problem
    • Use option to expand only one way (backtrackable)
    Suitable for, e.g., simple maze solving. The frontier is the single current state. 
    Problem = SenseProblem();
KB += StaticPartOf(Problem);
CurrentState = DynamicPartOf(Problem);
DynamicStateSpace = {};
while (! SolutionFound(CurrentState)) {
    Transformation = ChooseTransformationFromCurrentState(CurrentState,KB,DynamicStateSpace);
    if (Transformation == "backtrack") {
        CurrentState = PreviousState(CurrentState,DynamicStateSpace);
    } else {
        DynamicStateSpace += (CurrentState,Transformation);
        CurrentState = ApplyTransformation(CurrentState,Transformation);
    }
}

  • Production system engine algorithm, for
    • Accessible-explorable, static, discrete, single agent environment
    • Non-deterministic, non-decomposable, non-recoverable, any solution problem (bad combination!)
    • Can expand only one way (non-deterministic, non-recoverable)
    The non-determinism requires resensing. In combination with the non-recoverability, this sucks. 
    Environment = SenseEnvironment();
Problem = SenseProblem();
KB += StaticPartOf(Problem) + Environment;
CurrentState = DynamicPartOf(Problem);
DynamicStateSpace = {};
while (! SolutionFound(CurrentState)) {
    Transformation = ChooseTransformationFromCurrentState(CurrentState,KB,DynamicStateSpace);
    DynamicStateSpace += CurrentState;
    ApplyTransformation(CurrentState,Transformation);
    CurrentState = DynamicPartOf(SenseProblem());
}

  • Production system engine algorithm, for
    • Accessible, dynamic, discrete, single agent environment
    • Deterministic, non-decomposable, recoverable, any solution problem
    • Expand one way (dynamic)
    Suitable for, e.g., web spider 
    Problem = SenseProblem();
KB += StaticPartOf(Problem);
CurrentState = DynamicPartOf(Problem);
DynamicStateSpace = {};
while (! SolutionFound(CurrentState)) {
    DynamicStateSpace += CurrentState;
    Environment = SenseEnvironment();
    (FromState,Transformation) = ChooseStateAndTransformation(Environment,KB,DynamicStateSpace);
    CurrentState = ApplyTransformation(FromState,Transformation);
}