Anytime Synthetic Projection: Maximizing the Probability of Goal Satisfaction

Mark Drummond, John L. BresinaAAAI 1990

Abstract

This paper presents an anytime algorithm for synthesizing reactive control rules in embedded systems. By integrating temporal projection with a heuristic that balances state probability against remaining work, the proposed system incrementally constructs robust Situated Control Rules (SCRs). This approach maximizes the probability of goal satisfaction in unpredictable environments by focusing computational resources on the most likely failure modes, bridging the gap between brittle sequence-based plans and computationally expensive universal plans.

Introduction

Embedded systems, such as autonomous robots, operate in environments where exogenous events frequently disrupt planned action sequences. Traditional AI planning often produces single-path solutions that fail under uncertainty. Conversely, universal plans—which provide actions for every possible state—are often intractable to compute for complex domains.

The authors address this by proposing an "anytime" synthetic projection framework. This framework allows a system to quickly generate a baseline plan and then use additional computation time to "robustify" it, preparing for high-probability deviations.

Methodology

Behavioral Constraints (BCs)

The system utilizes a rich goal language based on branching temporal logic, termed Behavioral Constraints (BCs). Unlike simple reachability goals, BCs can express complex requirements such as maintenance (ensuring a condition remains true) and prevention (ensuring a condition never occurs).

Grammar for Behavioral Constraints (BCs) used to specify complex goals.

The Traverse and Robustify Algorithms

The core of the framework consists of two primary algorithms:

  1. Traverse: A heuristic search that identifies an initial path to the goal. It employs a heuristic $h(s, \beta) = K1 \cdot p(s) + K2 \cdot rwt(s, \beta)$, where $p(s)$ is the probability of reaching state $s$ and $rwt$ is the estimated remaining work.
  2. Robustify: Once an initial path is established, this algorithm identifies high-probability transitions that lead away from the intended path. It then recursively calls Traverse to find recovery paths back to the goal or a safe state.
State transition graph illustrating the Robustify algorithm and sub-goal strategies.

Complexity Management: Cut-and-Commit

To mitigate the exponential growth of the search space, the authors introduce a "cut-and-commit" strategy. The overall goal is decomposed into a sequence of sub-problems ($\beta_1, \beta_2, \dots$). Once a solution for a sub-problem is found, the system "commits" to it, significantly reducing the number of situations the projector must evaluate.

Evaluation and Results

The framework was evaluated in the Reactive Tile World, a simulated environment featuring exogenous events and temporally extended goals.

Key results include:

  • Search Efficiency: Mathematical analysis shows that a strategy of length $c$ for a path of length $n$ with branching factor $b$ reduces search complexity from $b^{n+1}$ to $c \cdot b^{(n/c)+1}$.
  • Incremental Robustness: The anytime nature of the algorithm allows it to provide a valid set of SCRs at any point, with the quality and robustness of the plan improving as more computation time is allocated.
  • Heuristic Effectiveness: While not guaranteeing global optimality, the heuristic approach provides a computationally feasible method for maximizing the probability of success in real-time scenarios.

Discussion and Future Work

While effective, the current approach has limitations. The "cut-and-commit" strategy, while efficient, introduces the risk of committing to a sub-goal that makes the ultimate goal unreachable, necessitating complex backtracking mechanisms. Furthermore, the system currently relies on static transition probabilities provided in the causal theory. Future work aims to enable the system to learn and update these probabilities through experience and to resolve potential conflicts between overlapping Situated Control Rules.

Summary updated

BibTeX
@inproceedings{drummond1990anytime,
  author = {Mark Drummond and John L. Bresina},
  title = {{Anytime Synthetic Projection: Maximizing the Probability of Goal Satisfaction}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1990},
}
Figure