A Hybrid LP-RPG Heuristic for Modelling Numeric Resource Flows in
  Planning
  Although the use of metric fluents is fundamental to many practical planning
problems, the study of heuristics to support fully automated planners working
with these fluents remains relatively unexplored. The most widely used
heuristic is the relaxation of metric fluents into interval-valued variables
--- an idea first proposed a decade ago. Other heuristics depend on domain
encodings that supply additional information about fluents, such as capacity
constraints or other resource-related annotations. A particular challenge to
these approaches is in handling interactions between metric fluents that
represent exchange, such as the transformation of quantities of raw materials
into quantities of processed goods, or trading of money for materials. The
usual relaxation of metric fluents is often very poor in these situations,
since it does not recognise that resources, once spent, are no longer available
to be spent again. We present a heuristic for numeric planning problems
building on the propositional relaxed planning graph, but using a mathematical
program for numeric reasoning. We define a class of producer--consumer planning
problems and demonstrate how the numeric constraints in these can be modelled
in a mixed integer program (MIP). This MIP is then combined with a metric
Relaxed Planning Graph (RPG) heuristic to produce an integrated hybrid
heuristic. The MIP tracks resource use more accurately than the usual
relaxation, but relaxes the ordering of actions, while the RPG captures the
causal propositional aspects of the problem. We discuss how these two
components interact to produce a single unified heuristic and go on to explore
how further numeric features of planning problems can be integrated into the
MIP. We show that encoding a limited subset of the propositional problem to
augment the MIP can yield more accurate guidance, partly by exploiting
structure such as propositional landmarks and propositional resources. Our
results show that the use of this heuristic enhances scalability on problems
where numeric resource interaction is key in finding a solution.
