Abstract
Part of the recent work in AI planning is concerned with the development of algorithms that regard planning as a combinatorial search problem. The underlying representation language is basically propositional logic. While this is adequate for many domains, it is not clear if it remains so for problems that involve numerical constraints, or optimization of complex objective functions. Moreover, the propositional representation imposes restrictions on the domain knowledge that can be utilized by these approaches. In order to address these issues, we propose moving to the more expressive language of Integer Programming (IP). We show how capacity constraints can be easily encoded into linear 0-1 inequalities and how rich forms of domain knowledge can be compactly represented and computationally exploited by IP solvers. Then we introduce a novel heuristic search method based on the linear programming relaxation. Finally, we present the results of our experiments with a classical relaxation-based IP solver and a logic-based 0-1 optimizer.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Barth, P.: Logic-based 0-1 constraint programming. Operations Research Computer Science Interfaces Series. Kluwer, Dordrecht (1996), http://www.mpi-sb.mpg.de/~barth/opbdp/opbdp.html
Barth, P., Bockmayr, A.: Modelling discrete optimisation problems in constraint logic programming. Annals of Operations Research 81, 467–496 (1998)
Blum, A., Furst, M.: Fast planning through planning graph analysis. Artificial Intelligence 90, 281–300 (1997)
Bockmayr, A.: Solving pseudo-Boolean constraints. In: Podelski, A. (ed.) Constraint Programming: Basics and Trends. LNCS, vol. 910, pp. 22–38. Springer, Heidelberg (1995)
Bockmayr, A., Dimopoulos, Y.: Mixed integer programming models for planning problems. In: CP 1998 Workshop on Constraint Problem Reformulation (1998)
Bonet, B., Loerincs, G., Geffner, H.: A fast and robust action selection mechanism for planning. In: AAAI 1997 (1997)
Bylander, T.: A Linear Programming Heuristic for Optimal Planning. In: AAAI 1997 (1997)
CPLEX Optimization, Inc. Using the CPLEX callable library (1995), http://www.cplex.com
Gerevini, A., Schubert, L.: Accelerating Partial-Order Planners: Some Techniques for Effective Search Control and Pruning. Journal of Artificial Intelligence Research 5 (1996)
Huang, Y.-C., Selman, B., Kautz, H.: Control Knowledge in Planning: Benefits and Tradeoffs. In: IJCAI 1999 (1999)
Kautz, H., Selman, B.: Pushing the envelope: planning, propositional logic and stochastic search. In: AAAI 1996 (1996)
Kautz, H., Selman, B.: The Role of Domain-Specific Knowledge in the Planning as Satisfiability Framework. In: AIPS 1998 (1998)
Kautz, H., Selman, B.: Unifying SAT-based and Graph-based Planning. In: IJCAI 1999 (1999)
Kautz, H., Walser, J.: State-Space Planning by Integer Optimization. In: AAAI 1999 (1999)
Koehler, J.: Planning under Resource Constraints. In: ECAI 1998 (1998)
Koehler, J., Nebel, B., Hoffmann, J., Dimopoulos, Y.: Extending Planning Graphs to an ADL Subset. In: Steel, S. (ed.) ECP 1997. LNCS, vol. 1348. Springer, Heidelberg (1997)
McDermott, D.: A heuristic estimator for means-ends analysis in planning. In: AIPS 1996 (1996)
Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, Chichester (1988)
van Beek, P., Chen, X.: CPlan: A Constraint Programming Approach to Planning. In: AAAI 1999 (1999)
Vossen, T., Ball, M., Lotem, A., Nau, D.: On the Use of Integer Programming Models in AI Planning. In: IJCAI 1999 (1999)
Wolfman, S., Weld, D.: The LPSAT Engine and its Application to Resource Planning. In: IJCAI 1999 (1999)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bockmayr, A., Dimopoulos, Y. (2000). Integer Programs and Valid Inequalities for Planning Problems. In: Biundo, S., Fox, M. (eds) Recent Advances in AI Planning. ECP 1999. Lecture Notes in Computer Science(), vol 1809. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10720246_19
Download citation
DOI: https://doi.org/10.1007/10720246_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67866-3
Online ISBN: 978-3-540-44657-6
eBook Packages: Springer Book Archive