Limited space precludes a survey of propositional satisfiability algorithms and linear programming methods in this paper. See [Cook and Mitchell1997] for a survey of satisfiability and [Karloff1991] for a survey of linear programming.

Our work was inspired by the idea of compiling probabilistic planning problems to MAJSAT [Majercik and Littman1998]. It seemed that if one could extend the SAT ``virtual machine'' to support probabilistic reasoning, then it would be useful to consider the orthogonal extension to handle metric constraints.

Other researchers have combined logical and constraint reasoning,
usually in the context of programming languages. CLPR may be
thought of as an integration of Prolog and linear programming, and
this work introduced the notion of incremental
Simplex [Jaffar *et al.*1992]. Saraswat's
thesis [Saraswat1989] formulates a family of programming
languages which operate through the incremental construction of a
constraint framework. CHIP [Van Hentenryck1989] augments logic
programming with the tools to efficiently solve constraint
satisfaction problems (*e.g.*, consistency checking), but deals only with
variables over finite domains. NUMERICA extends this work by
adding a variety of differential equation solvers to the
mix [Van Hentenryck1997]. Hooker et al. describe a technique
for combining linear programming and constraint
propagation [Hooker *et al.*1999].

BLACKBOX uses a translate/solve/decode scheme for planning and
satisfiability [Kautz and Selman1998]. ZENO is a causal link
temporal planner which handled resources by calling an incremental
Simplex algorithm within the plan-refinement
loop [Penberthy and Weld1994]. The GRAPHPLAN [Blum and Furst1995]
descendant IPP has also been extended to handle metric reasoning
in its plan graph [Koehler1998]. SIPE [Wilkins1990] and OPLAN [Currie and Tate1991] are
industrial strength planners which include resource planning
capabilities. Two recent systems address the metric planning
problem using compilation to integer
programming [Kautz and Walser1999,Vossen *et al.*1999].