Reviving Integer Programming Approaches for AI Planning: A Branch-and-Cut Framework

Menkes van den Briel, Thomas Vossen, and Subbarao Kambhampati

The conventional wisdom in the planning community is that planners based on integer programming (IP) techniques cannot compete with satisfiability and constraint satisfaction based planners. In this paper we challenge this perception of IP techniques by presenting novel formulations that outperform the most efficient SAT-based planner that currently exists. We will present a series of IP formulations that (1) use multi-valued state variables that are represented by networks, and that (2) control the encoding length by progressively generalizing the notion of parallelism. The resulting IP encodings are solved within a branch-and-cut framework and yield impressive results.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.