Proteus, truth maintenance and Redux

How to change your mind without starting over.

Petrie's technical thread from 1984 onward is reason maintenance: keeping track of why a system believes what it believes, so that when something changes, only the dependent conclusions have to be revisited. His master's thesis was New Algorithms for Dependency-Directed Backtracking; his AAAI-87 paper revised dependency-directed backtracking for default reasoning; his dissertation was Planning and Replanning with Reason Maintenance.

Proteus, the MCC project he led, combined frames with inheritance, forward and backward chaining rules, a truth maintenance system and dependency-directed backtracking with fix rules into one expert-system shell. NCR built its Design Advisor, an integrated-circuit design critic, on it, and that became the first commercial product based on MCC technology.

Redux, described in his 1990 MCC report and the 2012 Springer book, is what he called goal, operator-oriented programming. Computation starts with goals. An operator applied to a goal is a decision that produces assignments or subgoals. Assignments can violate constraints, and a violation can only be resolved by rejecting one or more of the decisions that support it, which dependency-directed backtracking identifies. Decisions carry contingencies, so when the world changes the decisions that depended on it become invalid and their goals reopen. It is a model of design, planning and replanning that keeps the reasons.

The airport years used the same vocabulary. IEEE Spectrum quoted his rule for a project where everything hangs on everything else: you don't have a plan, you have dependencies.

Sources: his Proteus page; Redux Overview; his CV; IEEE Spectrum, 2018. Where this page paraphrases him, the paraphrase is ours and the source is his.