In their 1987 AAAI proceedings paper, Matthew Ginsberg and David Smith addressed a fundamental challenge in early Artificial Intelligence: enabling machines to reason about the real world without becoming paralyzed by an infinite list of potential failures. This challenge is known as the qualification problem.
The Qualification Problem
In classical AI, a simple rule like "If the key is turned, the car starts" is insufficient for real-world application. A car might fail to start for countless reasons: a dead battery, a potato in the tailpipe, or a stolen engine. Explicitly listing every possible precondition for an action is computationally impossible.
Early attempts to solve this used "default logic," assuming an action succeeds unless a specific disabling condition is proven. However, as environments grow more complex, the rules for what "disables" an action become impossibly tangled.
The Possible Worlds Approach
Ginsberg and Smith proposed a framework based on Possible Worlds. Instead of maintaining a single "true" state, the system considers a set of logically consistent states.
- Nearest Possible Worlds: When an action is performed, the system identifies a new state that incorporates the action's direct consequences while minimizing changes from the previous state.
- The Qualification Set ($Q$): For each action, a set of domain constraints (e.g., "two objects cannot occupy the same space") is defined. These constraints can potentially block an action.
- The Success Test: To determine if an action succeeds, the system temporarily ignores the constraints in $Q$ and calculates the "nearest possible world." If the ignored constraints are inevitably violated in this new world, the action is "qualified" (it fails). If a valid state exists that satisfies both the action and the constraints, the action succeeds.
Handling Complex Constraints: The Dumbbell Problem
A key insight of the paper is that qualifications are often just "illegal" ramifications—side effects that violate fundamental domain laws. This is best illustrated by the Dumbbell Problem.
In this scenario, moving block A also moves block B because they are connected. A system using general domain constraints realizes that since B moves with A, it does not block A's movement. Previous default-logic systems struggled with such nuances, often requiring manual overrides for every possible connection between objects.
Results and Impact
The "inferential" approach proposed by Ginsberg and Smith offers significant computational advantages. While exhaustive approaches scale exponentially ($2^{\kappa a}$) with domain growth, this method scales polynomially ($\kappa a^2$). This efficiency makes it far more viable for complex, real-world environments.
Furthermore, the system demonstrates logical robustness by correctly identifying failures in complex scenarios, such as the "pulley problem," where simpler models would either fail or require excessive manual rule-writing.
Conclusion
While the system has limitations—such as an inability to handle "unknown unknowns" (e.g., a system without the concept of a "potato" cannot reason about one in a tailpipe)—it remains a landmark in symbolic AI. By shifting the focus from specific failure rules to general domain constraints, Ginsberg and Smith provided a more intuitive and scalable way for machines to navigate the complexities of the physical world.
Summary updated