Problems with chunking
======================

One weaknesses of Soar is that chunking can create overgeneral productions
that apply in inappropriate situations, or overspecific productions that will
never fire.  These problems arise when chunking cannot accurately summarize
the processing that led to the creation of a result.  Below is a list of four
known problems in chunking.

  1. Local negated conditions Overgeneral chunks can be created when negated
     conditions test for the absence of a working memory element that, if it
     existed, would be local to the subgoal.  Chunking does not determine why
     a given working memory element does not exist, and thus a condition that
     occurred in a production in the subgoal is not included in the chunk.
     For example, if a production tests for the absence of a local flag, and
     that flag is copied down to the subgoal from a supercontext, then the
     chunk should include a test that the flag in the supercontext does not
     exist.  Unfortunately, it is computationally expensive to determine why
     a given working memory element does not exist.  Chunking only includes
     negated tests if they test for the absence of super-context working
     memory elements.  To avoid using negated conditions for local data, the
     local data can be made a result by attaching it to the super-context.
     This increases the number of chunks learned, but a negated condition for
     the super-context can be used that leads to correct chunks.
     
  2. Search control determines correctness
      Overgeneral chunks can be
     created if a result of problem solving in a subgoal is dependent on
     search-control knowledge.  Recall that desirability preferences, such as
     better than, best, and worst, are not included in the traces of problem
     solving used in chunking (Section *Note Determining conditions and
     actions:: on page See Determining conditions and actions).  In
     theory, these preferences do not affect the validity of search.  In
     practice, however, a problem space can be implemented so that search
     control *does* affect the correctness of search.  Here are two examples:
     
       1. Some of the test for correctness of a result is included in
          productions that prefer operators that will produce correct
          results.  The system will work correctly only when those
          productions are loaded.
          
       2. An operator is given a worst preference, indicating that it should
          be used only when all other options have been exhausted.  Because
          of the semantics of worst, this operator will be selected after all
          other operators; however, if this operator then produces a result
          that is dependent on the operator occurring after all others, this
          fact will not be captured in the conditions of the chunk.
     
     In both of these cases, part of the test for producing a result is
     {implicit} in search control productions.  This move allows the explicit
     goal test to be simpler because any state to which the test is applied
     is guaranteed to satisfy some of the requirements for success.  However,
     chunks created in such a problem space will be overgeneral because the
     implicit parts of the goal test do not appear as conditions.  To avoid
     this problem, necessity preferences (require and prohibit) should be
     used whenever a control decision is being made that also incorporates
     goal-attainment knowledge.  The necessity preferences are included in
     the backtrace by chunking, thereby avoiding overgenerality.
     
  3. Test for subgoal
      Overgeneral chunks can be created if a result
     of a subgoal is dependent on the creation of an impasse within the
     subgoal.  For example, processing in a subgoal may consist of
     exhaustively applying all the operators in the problem space.  If so,
     then a convenient way to recognize that all operators have applied and
     processing is complete is to wait for a state no-change impasse to
     occur.  When the impasse occurs, a production can test for the resulting
     subgoal and create a result for the original subgoal.  This form of goal
     test builds overgeneral chunks because no pre-existing structure is
     relevant to the result that terminates the subgoal. The result is
     dependent only on the existence of the subgoal within a subgoal.
     
     The current solution to this problem is to allow the problem solving to
     signal the architecture that the test for a subgoal is being made.  The
     signal used by Soar is a test for the ^$quiescence t augmentation of the
     subgoal.  The chunking mechanism recognizes this test and does not build
     a chunk when it is found in a backtrace of a subgoal.  The history of
     this test is maintained, so that if the result of the subgoal is then
     used to produce further results for a super-context, no higher chunks
     will be built.  However, if the result is used as search control (it is
     a desirability preference), then it does not prevent the creation of
     chunks because the original result is not included in the backtrace.  If
     the ^$quiescence t being tested is connected to a supergoal, it will not
     inhibit chunking and it will be included in the conditions of the chunk.
     
     
  4. Testing changing values over time
      Overspecific chunks can be
     created if the results of a subgoal are dependent on multiple values of
     a single super-context augmentation.  Consider a simple example of where
     the ticks of a clock are counted in the subgoal and the result of the
     subgoal is to create "bong" when sixty ticks have gone by.  The ticks
     are created by removing and recreating a tick object in the top context,
     while in the subgoal a count of the ticks is maintained.  The final
     result is dependent on sixty different ticks, which each occurred at a
     different time.  The chunk that is built will test for sixty ticks, all
     occurring at once.  The problem is that the relationship between the
     sixty ticks is not represented explicitly, but is instead implicit in
     the rematching of the production that increments the tick counter.  This
     particular problem could be solved by explicitly representing the after
     relationship of a tick to the one that occurred before it, creating a
     linked list of ticks.  The subgoal can then test that a new tick has
     occurred after the last one it counted, and bump its
     count. Unfortunately, this requires explicitly representing all sixty
     ticks at the top level and the resulting chunk will test for a linked
     list of sixty ticks. Another solution is to make the intermediate count
     a result of the subgoal and save only the two most recent ticks in
     working memory.  The intermediate count could have a pointer to the tick
     used to increment it.  Then, sixty chunks will be learned, one for each
     addition.