A SAT-based approach to cost-sensitive temporally expressive planning

Abstract

Complex features, such as temporal dependencies and numerical cost constraints, are hallmarks of real-world planning problems. In this article, we consider the challenging problem of cost-sensitive temporally expressive (CSTE) planning, which requires concurrency of durative actions and optimization of action costs. We first propose a scheme to translate a CSTE planning problem to a minimum cost (MinCost) satisfiability (SAT) problem and to integrate with a relaxed parallel planning semantics for handling true temporal expressiveness. Our scheme finds solution plans that optimize temporal makespan, and also minimize total action costs at the optimal makespan. We propose two approaches for solving MinCost SAT. The first is based on a transformation of a MinCost SAT problem to a weighted partial Max-SAT (WPMax-SAT), and the second, called BB-CDCL, is an integration of the branch-and-bound technique and the conflict driven clause learning (CDCL) method. We also develop a CSTE customized variable branching scheme for BB-CDCL which can significantly improve the search efficiency. Our experiments on the existing CSTE benchmark domains show that our planner compares favorably to the state-of-the-art temporally expressive planners in both efficiency and quality.

References

1. Alsinet, T., Manya, F., and Planes, J. 2003. Improved branch and bound algorithms for Max-SAT and weighted Max-SAT. In Proceedings of the Catalan Conference on Artificial Intelligence.
2. Bacchus, F. and Ady, M. 2001. Planning with resources and concurrency: A forward chaining approach. In Proceedings of the International Joint Conference on Artificial Intelligence. 417--424.
3. Bhattacharya, A. A. and Ghosh, S. 2007. Self-optimizing peer-to-peer networks with selfish processes. In Proceedings of the International Conference on Self-Adaptive and Self-Organizing Systems. 340--343.
4. Blum, A. and Furst, M. L. 1997. Fast planning through planning graph analysis. Artificial Intelligence 90, 1--2, 281--300.
5. Büttner, M. and Rintanen, J. 2005. Satisfiability planning with constraints on the number of actions. In Proceedings of the International Conference on Automated Planning and Scheduling. 292--299.
6. Carman, M., Serafini, L., and Traverso, P. 2003. Web service composition as planning. In Proceedings of the Workshop on Planning for Web Services, International Conference on Automated Planning and Scheduling.
7. Chen, J. and Yang, Y. 2010. Localising temporal constraints in scientific workflows. J. Comput. Syst. Sci. 76, 6, 464--474.
8. Chen, Y. and Yao, G. 2009. Completeness and optimality preserving reduction for planning. In Proceedings of the International Joint Conference on Artificial Intelligence. 1659--1664.
9. Chen, Y., Lv, Q., and Huang, R. 2008. Plan-A: A cost-optimal planner based on SAT-constrained optimization. In Proceedings of the Workshop on International Planning Competition, International Conference on Automated Planning and Scheduling.
10. Chen, Y., Xu, Y., and Yao, G. 2009. Stratified Planning. In Proceedings of the International Joint Conference on Artificial Intelligence. 1665--1670.
11. Coles, A. J., Coles, A., Fox, M., and Long, D. 2010. Forward-chaining partial-order planning. In Proceedings of the International Conference on Automated Planning and Scheduling. 42--49.
12. Coles, A., Fox, M., Halsey, K., Long, D., and Smith, A. 2009. Managing concurrency in temporal planning using planner-scheduler interaction. Artif. Intell. 173, 1, 1--44.
13. Coles, A., Fox, M., Long, D., and Smith, A. 2008. Planning with problems requiring temporal coordination. In Proceedings of the National Conference on Artificial Intelligence. 892--897.
14. Coudert, O. 1996. On solving covering problems. In Proceedings of the Annual ACM IEEE Design Automation Conference. 197--202.
15. Cushing, W., Kambhampati, S., and Talamadupula, K. 2007a. Evaluating temporal planning domains. In Proceedings of the International Conference on Automated Planning and Scheduling.
16. Cushing, W., Kambhampati, S., Mausam, and Weld, D. S. 2007b. When is temporal planning really temporal? In Proceedings of the International Joint Conference on Artificial Intelligence. 1852--1859.
17. Darras, S., Dequen, G., Devendeville, L., and Li, C.-M. 2007. On inconsistent clause-subsets for Max-SAT solving. In Proceedings of the International Conference on Principles and Practice of Constraint Programming. 225--240.
18. Davis, M., Logemann, G., and Loveland, D. 1962. A machine program for theorem-proving. Comm. ACM 5, 394--397.
19. Dimopoulos, Y., Nebel, B., and Koehler, J. 1997. Encoding planning problems in nonmonotonic logic programs. In Proceedings of the European Conference on Planning. 169--181.
20. Do, M. B. and Kambhampati, S. 2003. SAPA: A multi-objective metric temporal planner. J. Artif. Intell. Res. 20, 155--194.
21. Do, M. B., Ruml, W., and Zhou, R. 2008. Planning for modular printers: Beyond productivity. In Proceedings of the International Conference on Automated Planning and Scheduling.
22. Eén, N. and Sörensson, N. 2003. An extensible SAT-solver. In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing. 502--518.
23. Eyerich, P., Mattmüller, R., and Röger, G. 2009. Using the context-enhanced additive heuristic for temporal and numeric planning. In Proceedings of the International Conference on Automated Planning and Scheduling. 130--137.
24. Fox, M. and Long, D. 2003. PDDL2.1: An extension to PDDL for expressing temporal planning domains. J. Artif. Intell. Res. 20, 61--124.
25. Fu, Z. and Malik, S. 2006. Solving the minimum-cost satisfiability problem using SAT based branch-and-bound search. In Proceedings of the International Conference on Computer-Aided Design. 852--859.
26. Gerevini, A. and Serina, I. 2002. LPG: A planner based on local search for planning graphs with action costs. In Proceedings of the International Conference on AI Planning and Scheduling. 13--22.
27. Gerevini, A., Saetti, A., and Serina, I. 2008. An approach to efficient planning with numerical fluents and multi-criteria plan quality. Artificial Intelligence 172, 8--9, 899--944.
28. Gerevini, A., Saetti, A., and Serina, I. 2010. Temporal planning with problems requiring concurrency through action graphs and local search. In Proceedings of the International Conference on Automated Planning and Scheduling.
29. Giunchiglia, E. and Maratea, M. 2006. OPTSAT: A tool for solving SAT related optimization problems. In Proceedings of the European Conference on Logics in Artificial Intelligence. Vol. 4160. 485--489.
30. Giunchiglia, E. and Maratea, M. 2007. SAT-based planning with minimal-♯actions plans and “soft” goals. In Proceedings of the 10th Congress of the Italian Association for Advances in Artificial Intelligence. Lecture Notes in Computer Science, vol. 4733, 422--433.
31. Haslum, P. 2008. Additive and reversed relaxed reachability heuristics revisited. In Proceedings of the Workshop on International Planning Competition, International Conference on Automated Planning and Scheduling.
32. Haslum, P. and Geffner, H. 2000. Admissible heuristics for optimal planning. In Proceedings of the International Conference on Automated Planning and Scheduling. 140--149.
33. Haslum, P. and Geffner, H. 2001. Heuristic planning with time and resources. In Proceedings of the Workshop on Planning with Resources, International Joint Conference on Artificial Intelligence.
34. Helmert, M., Haslum, P., and Hoffmann, J. 2008. Explicit-state abstraction: A new method for generating heuristic functions. In Proceedings of the National Conference on Artificial Intelligence. 1547--1550.
35. Hoffmann, J. and Nebel, B. 2001. The FF planning system: Fast plan generation through heuristic search. J. Artif. Intell. Res. 14, 253--302.
36. Hu, Y. 2007. Temporally-expressive planning as constraint satisfaction problems. In Proceedings of the International Conference on Automated Planning and Scheduling. 192--199.
37. Huang, R., Chen, Y., and Zhang, W. 2009. An optimal temporally expressive planner: Initial results and application to P2P network optimization. In Proceedings of the International Conference on Automated Planning and Scheduling.
38. Huang, R., Chen, Y., and Zhang, W. 2010. A novel transition based encoding scheme for planning as satisfiability. In Proceedings of the National Conference on Artificial Intelligence.
39. IPC. 2002. The third international planning competition. http://planning.cis.strath.ac.uk/competition/.
40. IPC. 2008. The sixth international planning competition. http://ipc.informatik.uni-freiburg.de/.
41. Kautz, H. 2004. SATPlan04: Planning as satisfiability. In Proceedings of the Workshop on International Planning Competition, International Conference on Automated Planning and Scheduling.
42. Kautz, H. and Selman, B. 1992. Planning as satisfiability. In Proceedings of the European Conference on Artificial Intelligence.
43. Kautz, H. and Selman, B. 1996. Pushing the envelope: Planning, propositional logic, and stochastic search. In Proceedings of the National Conference on Artificial Intelligence. 1194--1201.
44. Keyder, E. and Geffner, H. 2008. The FF(ha) planner for planning with action costs. In Proceedings of the Workshop on International Planning Competition, International Conference on Automated Planning and Scheduling.
45. Kvarnström, J. and Magnusson, M. 2003. TALplanner in the third international planning competition: Extensions and control rules. J. Artif. Intell. Res. 20, 343--377.
46. Larrosa, J., Nieuwenhuis, R., Oliveras, A., and Rodríguez-Carbonell, E. 2009. Branch and bound for boolean optimization and the generation of optimality certificates. In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing. 453--466.
47. Li, C. M., Manya, F., and Planes, J. 2006. Detecting disjoint inconsistent subformulas for computing lower bounds for Max-SAT. In Proceedings of the National Conference on Artificial Intelligence. 86--91.
48. Li, C. M., Manya, F., and Planes, J. 2007. New inference rules for Max-SAT. J. Artif. Intell. Res. 30, 321--359.
49. Li, C. M., Manya, F., Mohamedou, N., and Planes, J. 2009. Exploiting cycle structures in Max-SAT. In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing. 467--480.
50. Li, X. Y. 2004. Optimization algorithms for the minimum-cost satisfiability problem. PhD Thesis, Department of Computer Science, North Carolina State University.
51. Long, D. and Fox, M. 2003. Exploiting a graphplan framework in temporal planning. In Proceedings of the International Conference on Automated Planning and Scheduling. 52--61.
52. Manquinho, V., Marques-Silva, J., and Marques-Silva, J. P. 2002. Search pruning techniques in SAT-based branch-and-bound algorithms for the binate covering problem. IEEE Trans. Comput. Aided Des. Inter. Circuits Sys. 21, 505--516.
53. Manquinho, V., Marques-Silva, J., and Planes, J. 2009. Algorithms for weighted Boolean optimization. In Proceedings of the International Conference on Theory and Applications of Satisfiability Testing. 495--508.
54. Marques-Silva, J. P., Silva, J. P. M., Sakallah, K. A., and Sakallah, K. A. 1996. GRASP: A new search algorithm for satisfiability. In Proceedings of the International Conference on Computer-Aided Design. 220--227.
55. Max-SAT. 2010. The Sixth Max-SAT Evaluation. http://www.maxsat.udl.cat/10/.
56. Mitchell, D. G. 2005. A SAT solver primer. Bull. Eur. Assoc. Theor. Computer Sci. 85, 112--132.
57. Moskewicz, M. W., Madigan, C. F., Zhao, Y., Zhang, L., and Malik, S. 2001. Chaff: Engineering an efficient SAT solver. In Proceedings of the Annual ACM IEEE Design Automation Conference. ACM, 530--535.
58. Penberthy, J. S. and Weld, D. S. 1994. Temporal planning with continuous change. In Proceedings of the National Conference on Artificial Intelligence. 1010--1015.
59. Pipatsrisawat, K. and Darwiche, A. 2007. Clone: solving weighted Max-SAT in a reduced search space. In Proceedings of the Australian Conference on Artificial Intelligence. 223--233.
60. Planes, J. 2003. Improved branch and bound algorithms for Max-2-SAT and weighted Max-2-SAT. In Proceedings of the International Conference on Principles and Practice of Constraint Programming. 991.
61. Rao, J. and Su, X. 2004. A survey of automated web service composition methods. In Proceedings of the International Workshop on Semantic Web Services and Web Process Composition. 43--54.
62. Refanidis, I., Refanidis, I., and Vlahavas, I. 2001. A framework for multi-criteria plan evaluation in heuristic state-space planning. In Proceedings of the Workshop on Planning with Resources, International Joint Conference on Artificial Intelligence.
63. Richter, S. and Westphal, M. 2008. The LAMA planner: Using landmark counting in heuristic search. In Proceedings of the Workshop on International Planning Competition, International Conference on Automated Planning and Scheduling.
64. Richter, S. and Westphal, M. 2010. The LAMA planner: Guiding cost-based anytime planning with landmarks. J. Artif. Intell. Res.
65. Rintanen, J. 2007. Complexity of concurrent temporal planning. In Proceedings of the National Conference on Artificial Intelligence.
66. Rintanen, J., Heljanko, K., and Niemelä, I. 2006. Planning as satisfiability: parallel plans and algorithms for plan search. Artif. Intell. 170, 12--13, 1031--1080.
67. Robinson, N., Gretton, C., and Pham, D. N. 2008a. CO-PLAN: Combining SAT-based planning with forward-search. In Proceedings of the Workshop on International Planning Competition, International Conference on Automated Planning and Scheduling.
68. Robinson, N., Gretton, C., Pham, D., and Sattar, A. 2008b. A compact and efficient SAT encoding for planning. In Proceedings of the International Conference on Automated Planning and Scheduling. 296--303.
69. Robinson, N., Gretton, C., Pham, D. N., and Sattar, A. 2010. Partial weighted MaxSAT for optimal planning. In Pacific Rim International Conference on Artificial Intelligence. 231--243.
70. SAT4J. 2004. http://www.sat4j.org/.
71. Shin, J. and Davis, E. 2004. Continuous time in a SAT-based planner. In Proceedings of the National Conference on Artificial Intelligence. 531--536.
72. Smith, D. E. 1999. Temporal planning with mutual exclusion reasoning. In Proceedings of the International Joint Conference on Artificial Intelligence. 326--337.
73. Smith, D. E. 2003. The case for durative actions: A commentary on PDDL2.1. J. Artif. Intell. Res. 20, 149--154.
74. Vidal, V. and Geffner, H. 2004. CPT: An optimal temporal POCL planner based on constraint programming. In Proceedings of the Workshop on International Planning Competition, International Conference on Automated Planning and Scheduling. 59--60.
75. Vidal, V. and Geffner, H. 2006. Branching and pruning: An optimal temporal POCL planner based on constraint programming. Artif. Intell. 170, 298--335.
76. Wah, B. W. and Chen, Y. 2006. Constraint partitioning in penalty formulations for solving temporal planning problems. Artif. Intell. 170, 187--231.
77. Wolfman, S. A. and Weld, D. S. 1999. The LPSAT engine and its application to resource planning. In Proceedings of the International Joint Conference on Artificial Intelligence. 310--316.
78. Xing, Z. and Zhang, W. 2005. MaxSolver: An efficient exact algorithm for (weighted) maximum satisfiability. Artif. Intell. 164, 47--80.
79. Yang, Q., Wu, K., and Jiang, Y. 2007. Learning action models from plan examples using weighted MAX-SAT. Artif. Intell. 171, 107--143.
80. Younes, H. L. S. and Simmons, R. G. 2003. VHPOP: Versatile heuristic partial order planner. J. Artif. Intell. Res. 20, 405--430.
81. Zhang, L., Madigan, C. F., Moskewicz, M. H., and Malik, S. 2001. Efficient conflict driven learning in a Boolean satisfiability solver. In Proceedings of the International Conference on Computer-Aided Design. 279--285.
82. Zhang, L. and Malik, S. 2002. The quest for efficient boolean satisfiability solvers. In Proceedings of the International Conference on Computer-Aided Verification. 17--36.
83. Zhuo, H. H., Yang, Q., Hu, D. H., and Li, L. 2010. Learning complex action models with quantifiers and logical implications. Artif. Intell. 174, 1540--1569.

Index Terms

• Computing methodologies

  • Artificial intelligence

    • Planning and scheduling

• Information systems

  • Information systems applications

    • Decision support systems

      • Expert systems