Combining Static and Dynamic Models for Boosting Forward Planning

摘要

This paper presents an example of cooperation between AI planning techniques and Constraint Programming or Operations Research. More precisely, it presents a way of boosting forward planning using combinatorial optimization techniques. The idea consists in combining on one hand a dynamic model that represents the Markovian dynamics of the system considered (i.e. state transitions), and on the other hand a static, model that describes the global properties that are required over state trajectories. The dynamic part is represented by so-called constraint-based timed automata, whereas the static part is represented by so-called constraint-based observers. The latter are modeled using standard combinatorial optimization frameworks, such as linear programming, constraint programming, scheduling, or boolean satisfiability. They can be called at any step of the forward search to cut it via inconsistency detection. Experiments show significant improvements on some benchmarks of the International Planning Competition.