Production Systems

• Recall the structure of an agent ...
  

  

• A production system has 6 modules spread over the 3 parts of the central intelligence ...
  • Problem representation
    1. Problem (and maybe some environment) information in states, in a growing space of achieved states. Includes the initial state.
    • Other state lists and data structures as required.
  • Knowledge base
    2. Knowledge that can help the search control.
    • Static information that forms part of every state (and thus need not be duplicated) can be moved here.
    • Environment information
    • Semantic information for the static and dynamic information
  • Search control
    3. State transformation rules
    4. A strategy, with access to the problem representation (the three types of information) and knowledge base.
    5. A function that tests for a solution state
    6. The engine drives the system, and in conjunction with the control strategy and transformations forms the solution generator of a classical problem description.

• In general terms, the production system algorithm ...
  • Tests whether or not a solution state has been achieved
    • It may be necessary to generate several goal states before halting however, as a "best" solution may be required.
  • Finds possible achieved-state + transformation pairs
  • Selects achieved-state+transformation pairs
  • Implements the selected transformations
  • Inserts the new states in the achieved space of states.
    • The dynamic space is all known states
    • The frontier space is states from which transformations can still be done. Sometimes separated from the dynamic space.
    • The new space is states just discovered. Sometimes separated from the dynamic space.
  • Must produce motion through the state space.

• Algorithms handout

• 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);
      NewStates = RemoveLoops(NewStates,DynamicStateSpace,FrontierStates,StateToTransform);
      DynamicStateSpace += StateToTransform;
  } 

  Implementation notes
  • Static part of problem added to any a priori knowledge in KB
  • FrontierStates += NewStates moves the frontier forward.
  • ExtractStateToTransform removes the StateToTransform from the FrontierStates.

• 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);
  } 

• Influence of environment characteristics
  • Accessibility
    • Greater accessibility gives a greater possible role for knowledge acquired from the environment.
    • Explorable environment requires one sensing.
    • Contingent environment requires resensing.
  • Dynamism
    • Environment changes during process, and thus requires resensing.
    • Can plan ahead only if static.
    • Semi-dynamic plays time off against performance.
  • Continuity
    • Data structures change
  • Agents
    • Multi-agent means a dynamic environment and/or a strategic problem

• Influence of problem characteristics
  • Determinism
    • Deterministic: Can choose transformation by predicting new states. Can plan ahead (if environment allows)
    • Searchable: Can search ahead.
    • Non-deterministic: Cannot predict new states. Cannot plan or search ahead. Requires repeated sensing.
  • Decomposability
    • If episodic, each episode can be treated separately. No relative state information between episodes.
  • Recoverability
    • Recoverable: Can do any number of transformations from any number of states. No need to plan ahead - good for non-deterministic problems.
    • Backtrackable: Must do one transformation from "current" state, but can always transform back. Must take cost of backtracking into account.
    • Non-recoverable: Must do one transformation from the current state.
  • Solution quality
    • Best solution possible if recoverable or backtrackable

• The role of knowledge - how much is there, and how useful is it?
  • Ignorance - no knowledge available, e.g., first time activities
  • Known a priori - can be used consistently
  • Explorable - can be acquired through one-time use of sensors.
  • Contingent - explorable as you progress into the state space, and you learn as you go. A similar effect to non-determinism.

• 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;
          CurrentState = ApplyTransformation(CurrentState,Transformation);
          if (Loop(CurrentState,DynamicStateSpace)) {
              CurrentState = PreviousState(CurrentState,DynamicStateSpace);
          }
      }
  } 

• 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. Suitable for a roulette wheel player (where a transformation is a bet and spin).

  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());
      if (Loop(CurrentState,DynamicPartOf)) {
          NoteToAvoidSameChoiceAgain(CurrentState,Transformation);
      }
  } 

• Production system engine algorithm, for
  • Accessible-contingent, dynamic, discrete, single agent environment
  • Deterministic, non-decomposable, recoverable, any solution problem
  • Expand one way (can also do expand all ways)
  Suitable for real-time web search.

  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);
      if (Loop(CurrentState,DynamicStateSpace)) {
          NoteToAvoidSameChoiceAgain(CurrentState,Transformation);
      }
  } 

• Selecting applicable transformations
  • Matching
    • Involves search through the pre-conditions and finding all that match.
    • Slow if there are a lot of rules.
  • Indexing
    • Use the current state as an index into the rules to find appropriate rules.
    • Could use a partial index then search - the usual hashing techniques.
  • Matching with variables (unification)
    • Must keep bindings and apply them to the post-condition of the rule to get the new state.
    • More variables means more general rules but more matches with the problem state.
  • Approximate matching.
    • Arises from imprecise states and imprecise rules.

• Ability to add new information to the static knowledge base can change system behaviour. Can add new transformation rules that are consistent with old without disrupting the system.

Exam Style Questions

• What are the components of a production system? Explain what each component does.
• Give the overall algorithm executed in a production system.
• Design a production system algorithm for ...
  • Partially accessible, static, discrete, single agent environment
  • Deterministic, non-decomposable, backtrackable, any solution problem