zbMATH — the first resource for mathematics

Metric hybrid factored planning in nonlinear domains with constraint generation. (English) Zbl 07116714
Rousseau, Louis-Martin (ed.) et al., Integration of constraint programming, artificial intelligence, and operations research. 16th international conference, CPAIOR 2019, Thessaloniki, Greece, June 4–7, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11494, 502-518 (2019).
Summary: We introduce a novel planner SCIPPlan for metric hybrid factored planning in nonlinear domains with general metric objectives, transcendental functions such as exponentials, and instantaneous continuous actions. Our key contribution is to leverage the spatial branch-and-bound solver of SCIP inside a nonlinear constraint generation framework where we iteratively check relaxed plans for temporal feasibility using a domain simulator, and repair the source of the infeasibility through a novel nonlinear constraint generation methodology. We experimentally evaluate SCIPPlan on a variety of domains, showing it is competitive with, or outperforms, ENHSP in terms of run time and makespan and handles general metric objectives. SCIPPlan is also competitive with a general metric-optimizing unconstrained Tensorflow-based planner (TF-Plan) in nonlinear domains with exponential transition functions and metric objectives. Overall, this work demonstrates the potential of combining nonlinear optimizers with constraint generation for planning in expressive metric nonlinear hybrid domains.
For the entire collection see [Zbl 1410.68020].

68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
90C27 Combinatorial optimization
Full Text: DOI