An im plementation of such a system has been described. It adds a dumb marker-passer and a path evaluator to the NASL planner. (NASL is a “ plan in terpreter” as opposed to a “ plan compiler.”) This plan evaluator is a set of cascaded heuristics tha t check paths for certain patterns. If these are found, variable bindings are then checked to see whether following the path can add information in the present planning context. If so, the path evaluator adds statem ents in the memory tha t the planner can take advantage of. The marker-passing and plan evaluation stages can be done in parallel with the actual planning. A program dem onstrating this, C-SCRAPS, has also been implemented.