Yochan Research Group  

Optiplan

 
   
 

Yochan

AltAlt

SAPA

 

Introduction

Optiplan is a domain independent planning system for classical planning. The architecture of Optiplan is very similar to that of Blackbox (Kautz & Selman 1999) and of GP-CSP (Do & Kambhampati 2001), but instead of unifying satisfiability of constraint satisfaction with graph based planning, Optiplan uses integer programming (IP). Like Blackbox and GP-CSP, Optiplan works in two phases. In the first phase the planning graph is build and transformed into an IP, then in the second phase the IP is solved using the commercial solver CPLEX. The IP formulation is based on the state change encoding (Vossen et al. 1999), however, a couple of changes have been added to this encoding that "strengthen" the original encoding and make it more general at the same time.


Publications

M.H.L van den Briel, and S. Kambhampati. 2004. Optiplan: Unifying IP-based and graph-based planning (PDF)


Integer programming in AI planning

T. Bylander. 1997. A linear programming heuristic for optimal planning. In Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI), 694-699.

Y. Dimopoulos. 2001. Improved integer programming models and heuristic search for AI planning. In Proceedings of the Sixth European Conference on Planning (ECP).

Y. Dimopoulos, and A. Gerevini. 2002. Temporal planning trough mixed integer programming. In AIPS Workshop on Planning for Temporal Domains, 2-8

H. Kautz, and J Walser. 1999. State-space planning by integer optimization. In Proceedings of the 17th National Conference of the American Association for Artificial Intelligence (AAAI), 526-533.

T. Vossen, M. Ball, A Lotem, and D. Nau. 1999. On the use of integer programming models in AI planning. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 304-309.

S. A. Wolfman, and D. S. Weld. 1999. The LPSAT engine its application to resource planning. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), 310-317


Implementation

Optiplan is implemented in C++ using CPLEX Concert Technology, anyone who is interested in the code or running Optiplan, please contact me.


 

HOME | RESEARCH | LINKS | ABOUT