Characterising approximate problem solving: by partially fulfilled pre- and postconditions

Frank van Harmelen, Annette ten Teije

Introduction

In 1969, Tony Hoare introduced a logic that defined program correctness through strict pre- and postconditions. This binary contract—if the input is valid, the output is guaranteed—remains the bedrock of traditional software engineering. However, as Artificial Intelligence (AI) and Knowledge-Based Systems (KBS) tackle increasingly complex, intractable problems, this "all-or-nothing" approach has become a bottleneck. AI often relies on heuristics and approximate methods designed to provide "good enough" answers even when data is missing or noisy. This paper proposes a formal framework to bridge the gap between classical logic and the practical reality of approximate problem-solving.

The Limitation of Binary Logic

Classical logic treats a precondition as a boolean switch. If a sensor fails or an observation is missing, the precondition is technically "false," and the program's behavior becomes mathematically undefined. In reality, an AI diagnostic tool or planner does not simply cease to function; it provides a degraded or broader set of possibilities. The challenge is that we lack a formal vocabulary to describe how that degradation occurs. Without this, we cannot mathematically predict the reliability of a system under partial information, nor can we distinguish between two algorithms that behave identically under perfect conditions but diverge under uncertainty.

A Framework for Gradual Functionality

The author extends standard Dynamic Logic to accommodate degrees of fulfillment. The framework is built on three main pillars:

  1. Gradual Preconditions: Instead of a simple true/false, the state of the input is measured by a metric ($M$) and an ordering system ($\prec$). This allows developers to rank states from "completely fulfilled" to "less fulfilled."
  2. Gradual Functionality: The program's output relation is redefined. Instead of a single guaranteed postcondition, the framework describes a range of expected behaviors mapped to the degree of input completeness.
  3. The Five Proof Obligations: To ensure a system is correctly characterized, the author identifies five formal requirements. These include verifying that gradual conditions align with classical ones at 100% completeness, ensuring the ordering reflects precondition strength, and proving that the implementation's deviation from the ideal is predictable based on the input's "distance" from the ideal state.

Case Study: Sceptical vs. Credulous Reasoning

To demonstrate the framework's utility, the paper examines two common AI approaches to diagnosis:

  • The Sceptical Method: This algorithm only concludes a diagnosis if all supporting evidence is present. Under partial information, it produces a "subset" of the true answer, building up certainty as more data arrives (approximating from below).
  • The Credulous Method: This algorithm includes any diagnosis that isn't explicitly ruled out. Under partial information, it produces a "superset" of possibilities, narrowing them down as data arrives (approximating from above).

Using the new framework, the author mathematically proves these dual natures. For the sceptical method, less informed input strictly leads to a smaller set of solutions; for the credulous method, it leads to a larger set. This demonstrates that the framework can successfully capture the "anytime" or gradual behavior of AI heuristics that classical logic ignores.

Significance and Future Directions

This formalization has significant implications for software reuse and system verification. In modern software libraries, a search for a component that meets a strict precondition often fails. A "gradual" characterization allows engineers to find components that are "close enough" for their specific constraints, improving the flexibility of Knowledge-Based Systems.

While the current study uses simplified diagnostic models, it lays the groundwork for modeling more complex AI techniques, such as limited-length logical clause solvers. Future work will focus on applying this to real-world reasoning methods and empirically testing whether this formalization improves the indexing and configuration of AI components in practical environments.

Summary updated

BibTeX
@inproceedings{harmelen1998characterising,
  author = {Frank van Harmelen and Annette ten Teije},
  title = {{Characterising approximate problem solving: by partially fulfilled pre- and postconditions}},
  booktitle = {EUROVAV},
  year = {1998},
}
Figure