×

zbMATH — the first resource for mathematics

Discovering state constraints for planning with conditional effects in Discoplan. I. (English) Zbl 1444.68171
Summary: Discoplan is a durable and efficient system for inferring state constraints (invariants) in planning domains, specified in the PDDL language. It is exceptional in the range of constraint types it can discover and verify, and it directly allows for conditional effects in action operators. However, although various aspects of Discoplan have been previously described and its utility in planning demonstrated, the underlying methodology, the algorithms for the discovery and inductive verification of constraints, and the proofs of correctness of the algorithms and their complexity analysis have never been laid out in adequate detail. The purpose of this paper is to remedy these lacunae.
MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
PDDL; UCPOP
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Alcázari, V., Torralba, A.: A reminder about the importance of computing and exploiting invariants in planning. In: Proceedings of the Twenty-Fifth International Conference on Automated Planning and Scheduling, pp 2-6 (2015)
[2] Allen, J.; Schubert, L.; Ferguson, G.; Heeman, P.; Hwang, C.; Kato, T.; Light, M.; Martin, N.; Miller, B.; Poesio, M.; Traum, D., The TRAINS project: a case study in defining a conversational planning agent, J Exp. Theor. AI, 7, 7-48 (1995) · Zbl 0939.68857
[3] Asai, M., Fukunaga, A.: Fully automated cyclic planning for large-scale manufacturing domains. In: Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling (2014)
[4] Bacchus, F., Fraser, C.B.: Inner and outer boundaries of literals: a mechanism for computing domain specific information. In: Working Notes of the AIPS00 Workshop on Analysing and Exploiting Domain Knowledge for Efficient Planning, pp 29-36. AAAI Press (2000)
[5] Bac̈kstrom̈, C.; Nebel, B., Complexity results for SAS + planning, Comput. Intell., 11, 4, 625-655 (1995)
[6] Bernardini, S.; Fagnani, F.; Smith, DE, Extracting mutual exclusion invariants from lifted temporal planning domains, Artif. Intell., 258, 1-65 (2018) · Zbl 1433.68404
[7] Bonet, B., Geffner, H.: Planning as heuristic search: artificial intelligence 129(1-2) (2001) · Zbl 0971.68146
[8] Cenk Gazen, B.C.B., Knoblock, C.A.C.A.: Combining the expressiveness of UCPOP with the efficiency of Graphplan. In: Steel, S., Alami, R. (eds.) Recent Advances in AI: Planning: 4th European Conference on Planning, ECP-97. Springer (1997)
[9] Chen, Y.; Huang, R.; Xingm, Z.; Zhang, W., Long-distance mutual exclusion for planning, Artif. Intell., 173, 2, 365-391 (2009) · Zbl 1192.68639
[10] Cooper, MC; de Roquemaurel, M.; Régnieri, P., A weighted CSP approach to cost-optimal planning, AI Commun., 24, 1, 1-29 (2011) · Zbl 1233.68205
[11] Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms. MIT Press (1990) · Zbl 1158.68538
[12] Domshlak, C.; Hoffmann, J.; Katz, M., Red-black planning: a new systematic approach to partial delete relaxation, Artif. Intell., 221, 73-114 (2015) · Zbl 1328.68194
[13] Edelkamp, S., Helmert, M.: Exhibiting knowledge in planning problems to minimize state encoding length. In: Recent Advances in AI Planning. 5th European Conference on Planning (ECP-99), Volume 1809 of Lecture Notes in Artificial Intelligence, pp 135-147. Springer (1999)
[14] Fox, M.; Long, D., The automatic inference of state invariants in TIM, J. Artif. Intell. Res. (JAIR), 9, 367-421 (1998) · Zbl 0910.68199
[15] Genesereth, M.; Nilsson, NJ, Logical Foundations of Artificial Intelligence (1987), Los Altos: Morgan Kaufmann, Los Altos · Zbl 0645.68104
[16] Gerevini, A., Schubert, L.: Discovering State Constraints for Planning: DISCOPLAN. Technical Report 2005-09-48, Dip. Di Elettronica per l’Automazione, Università Degli Studi di Brescia, 2005. Revised Version of Technical Report 811, Dept. of Computer Science, University of Rochester (2003)
[17] Gerevini, A.; Saetti, A.; Serina, I., Planning through stochastic local search and temporal action graphs, J. Artif. Intell. Res. (JAIR),, 20, 239-290 (2003) · Zbl 1058.68103
[18] Gerevini, A.; Schubert, L., Accelerating partial-order planners: some techniques for effective search control and pruning, J. Artif. Intell. Res. (JAIR), 5, 95-137 (1996)
[19] Gerevini, A., Schubert, L.: Inferring state constraints for domain-independent planning. In: Proceedings of the Fifteenth National Conference of the American Association for Artificial Intelligence (AAAI-98), pp. 905-912. AAAI Press/The MIT Press (1998)
[20] Gerevini, A., Schubert, L.: Extending the types of state constraints discovered by discoplan. In: Working Notes of the AIPS00 Workshop on Analysing and Exploiting Domain Knowledge for Efficient Planning, pp. 4-11 (2000)
[21] Gerevini, A., Schubert, L.: Inferring state constraints in discoplan: some new results. In: Proceedings of the Seventeenth National Conference of the American Association for Artificial Intelligence (AAAI-00), pp. 761-767. AAAI Press/The MIT Press (2000)
[22] Gerevini, A., Schubert, L.K.: Discoplan: an efficient on-line system for computing planning domain invariants. In: Proceedings of the European Conference on Planning (ECP-01), pp. 284-288. AAAI Press (2014)
[23] Ghallab, M., Howe, A., Knoblock, G., McDermott, D., Ram, A., Veloso, M., Weld, D., Wilkins, D.: PDDL—planning domain definition language. Technical report. Available at http://cs-www.cs.yale.edu/homes/dvm/ (1998)
[24] Haslum, J., Scholz, U.: Domain knowledge in planning representation and use. In: Proceedings of the 13th International Conference on Automated Planning & Scheduling (ICAPS-03), Workshop on PDDL, pp. 69-78 (2003)
[25] Helmert, M., Concise finite-domain representations for PDDL planning tasks, Artif. Intell., 173, 5-6, 503-535 (2009) · Zbl 1191.68635
[26] Kelleher, G.: Determining general consequences of sets of actions. Technical Report TR CMS.14.96, Liverpool Moores University (1996)
[27] Kelleher, J., Cohn, A.: Automatically synthesising domain constraints from operator descriptions. In: Proceedings of the Tenth European Conference on Artificial Intelligence (ECAI-92), pp. 653-655. Wiley (1992)
[28] Kvarnström, J.: Applying domain analysis techniques for domain-dependent control in Talplanner. In: Proceedings of the Sixth International Conference on Artificial Intelligence Planning Systems, pp. 101-111 (2002)
[29] Lin, F.: Discovering state invariants. In: Proceedings of the Ninth International Conference on Principles of Knowledge Representation and Reasoning (KR-04), pp. 536-544. AAAI Press (2004)
[30] Lipovetzkyi, N., Muise, C.J., Geffner, G.: Traps, invariants, and dead-ends. In: Proceedings of the Twenty-Sixth International Conference on Automated Planning and Scheduling, ICAPS 2016, pp. 211-215 (2016)
[31] McAllester, D.: Observations on cognitive judgements. In: Proceedings of the Nineth National Conference of the American Association for Artificial Intelligence (AAAI-91), pp. 910-914. MIT Press (1991)
[32] Morris, P., Feldman, R.: Automatically derived heuristics for planning search. In: Proceedings of the Second Irish Conference on AI and Cognitive Science. School of Computer Science Applications, Dublin City University (1989)
[33] Nebel, B., On the compilability and the expressive power of propositional planning formalisms, J. Artif. Intell. Res. (JAIR), 12, 271-315 (2000) · Zbl 0943.68182
[34] Penberthy, J.S., Weld, D.S.: UCPOP: a sound, complete, partial order planner for ADL. In: Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning (KR-92), pp. 103-114. Morgan Kaufmann, Boston (1992)
[35] Rankoohi, MF; Ghassem-sani, G., ITSAT: an efficient sat-based temporal planner, J. Artif. Intell. Res., 53, 541-632 (2015) · Zbl 1336.68239
[36] Rintanen, J.: A planning algorithm not based on directional search. In: Proceedings of the Sixth International Conference on Principles of Knowledge Representation and Reasoning (KR-98), pp. 617-624. Morgan Kaufmann (1998)
[37] Rintanen, J.: An iterative algorithm for synthesizing invariants. In: Proceedings of the Seventeenth National Conference of the American Association for Artificial Intelligence (AAAI-00), pp. 806-811. AAAI Press/The MIT Press (2000)
[38] Rintanen, J.: Regression for classical and nondeterministic planning. In: ECAI 2008 - 18th European Conference on Artificial Intelligence, Proceedings, pp. 568-572 (2008)
[39] Rintanen, J.: Constraint-based algorithm for computing temporal invariants. In: Logics in Artificial Intelligence - 14th European Conference, Proceedings, pp. 665-673 (2014) · Zbl 1432.68419
[40] Rintanen, J.: Schematic invariants by reduction to ground invariants. In: Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, pp. 3644-3650 (2017)
[41] Scholz, U.: Extracting state constraints from PDDL-like planning domains. In: Working Notes of the AIPS00 Workshop on Analyzing and Exploiting Domain Knowledge for Efficient Planning, pp. 43-48. AAAI Press (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.