Effect-Abstraction Based Relaxation for Linear Numeric Planning
Effect-Abstraction Based Relaxation for Linear Numeric Planning
Dongxu Li, Enrico Scala, Patrik Haslum, Sergiy Bogomolov
Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 4787-4793.
https://doi.org/10.24963/ijcai.2018/665
This paper studies an effect-abstraction based relaxation
for reasoning about linear numeric planning problems. The effect-abstraction
decomposes non-constant linear numeric effects into actions with conditional
effects over additive constant numeric effects. With little effort, on this
compiled version, it is possible to use known subgoaling based relaxations
and relative heuristics. The combination of these two steps leads to a novel
relaxation based heuristic. Theoretically, the relaxation is proved tighter
than previous interval based relaxation and leading to safe-pruning
heuristics. Empirically, a heuristic developed on this relaxation leads to
substantial improvements for a class of problems that are currently out of
the reach of state-of-the-art numeric planners.
Keywords:
Planning and Scheduling: Temporal and Hybrid planning
Heuristic Search and Game Playing: Heuristic Search
Planning and Scheduling: Planning and Scheduling