A Problem-Solver for Making Advice Operational

Jack MostowAAAI 1983

Introduction

In the early 1960s, John McCarthy proposed the concept of the "advice-taker"—a machine capable of being programmed through high-level advice rather than rigid, low-level code. However, a significant hurdle remained: the problem of operationalization. High-level advice is often "non-operational" because it refers to information the computer cannot directly observe or actions it cannot immediately execute.

This 1983 paper introduces BAR, an AI system designed to bridge the gap between abstract strategy and executable procedures. By transforming vague heuristics into concrete code, BAR automates a process that previously required intensive human intervention, significantly advancing the field of automated programming and heuristic search.

The Challenge of Operationalization

Advice is non-operational when it lacks a direct computational path. For example, in the card game Hearts, an expert might advise: "Don't lead a suit if an opponent is void." To a computer, this instruction is initially useless because it cannot see the opponents' hands. To follow this advice, the system must transform it into a computable heuristic, such as: "Check if an opponent failed to follow suit earlier, or estimate the probability of them being void based on the cards played."

BAR treats this transformation as a search problem within a specialized "problem space." In this space, states are represented as LISP-like expressions of the advice, and operators are general program transformations, such as unfolding definitions or applying probabilistic formulas.

Methodology: The BAR Architecture

BAR utilizes several key innovations to navigate the complex search space of program transformations:

1. Means-Ends Analysis (MEA)

BAR continually compares the current state of the advice to a "goal" state—an expression that meets the criteria for being executable. By identifying specific "differences" between the current and goal states, the system selects transformations specifically designed to reduce those differences.

2. Abstract Planning

To prevent the system from becoming lost in thousands of potential transformation rules, BAR employs abstract planning. It first searches a simplified, abstract space to identify a high-level sequence of rules (a "plan") before attempting to apply them in detail. This hierarchical approach prevents the "combinatorial explosion" typical of early AI search systems.

3. Separation of Knowledge

BAR maintains a strict distinction between three types of knowledge:

  • Domain Knowledge: The specific rules and mechanics of the task (e.g., the rules of Hearts).
  • Transformation Rules: General programming logic and algebraic identities that are independent of the specific task.
  • Operationality Criteria: Definitions of what the machine can actually compute given its current environment and data access.

4. Recursive Descent

When a transformation rule does not perfectly align with a current expression, BAR recursively sets a subgoal to transform the expression until the rule becomes applicable. This allows for the flexible application of general rules to complex, nested advice.

Evaluation and Results

The primary testbed for BAR was the game of Hearts. The system was tasked with operationalizing 13 distinct pieces of advice, including strategies like "Avoid taking a trick with points" and "Flush out the Queen of Spades."

Efficiency and Complexity

The results demonstrated a massive leap in automation compared to BAR's predecessor, FOO. In the FOO system, a human operator had to manually select from approximately 230 rules at every step, resulting in a branching factor of $10^3$ to $10^4$. BAR reduced this branching factor to between 1 and 10.

Furthermore, BAR successfully managed transformation sequences averaging 60 steps long, with some reaching over 100 steps. This level of depth demonstrated that the system could handle complex, multi-stage reasoning to arrive at a computable result.

Versatility

BAR proved capable of operationalizing the same piece of advice in multiple ways depending on the context. For instance, the advice to "avoid taking points" could be transformed into a simple "play a low card" heuristic or a more complex "look-ahead search procedure," depending on the available computational resources and the specific state of the game.

Insights and Limitations

One of the most significant insights from BAR is the emergence of probabilistic heuristics from hard logic. The system can transform a certain but uncomputable condition (knowing for a fact if an opponent is void) into a probabilistic but computable one (calculating likelihood).

However, the system faced several limitations:

  • The Horizon Effect: The planner occasionally selected a path that appeared promising in the abstract but led to a dead end because it ignored complexities buried deep within sub-expressions.
  • Coarse Abstraction: The abstraction method sometimes focused too heavily on top-level functions, leading to unproductive plans.
  • Cost-Blindness: BAR viewed operationality as a binary (computable or not). It did not account for the computational cost, meaning it might choose a highly accurate but prohibitively slow heuristic over a faster, slightly less accurate one.

Conclusion

BAR represented a major step forward in making McCarthy's "advice-taker" a reality. By formalizing operationalization as a guided search problem and utilizing abstract planning, the system demonstrated that computers could take high-level, human-centric strategies and autonomously refine them into executable code. This work laid the groundwork for future research in automated reasoning, machine learning, and the development of expert systems.

Summary updated

BibTeX
@inproceedings{mostow1983problem,
  author = {Jack Mostow},
  title = {{A Problem-Solver for Making Advice Operational}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}
Figure