×

zbMATH — the first resource for mathematics

Extracting mutual exclusion invariants from lifted temporal planning domains. (English) Zbl 1433.68404
Summary: We present a technique for automatically extracting mutual exclusion invariants from temporal planning instances. It first identifies a set of invariant templates by inspecting the lifted representation of the domain and then checks these templates against properties that assure invariance. Our technique builds on other approaches to invariant synthesis presented in the literature but departs from their limited focus on instantaneous actions by addressing temporal domains. To deal with time, we formulate invariance conditions that account for the entire temporal structure of the actions and the possible concurrent interactions between them. As a result, we construct a more comprehensive technique than previous methods, which is able to find not only invariants for temporal domains but also a broader set of invariants for sequential domains. Our experimental results provide evidence that our domain analysis is effective at identifying a more extensive set of invariants, which results in the generation of fewer multi-valued state variables. We show that, in turn, this reduction in the number of variables reflects positively on the performance of the temporal planners that use a variable/value representation.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
Graphplan; STAN; Walksat
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bäckström, C.; Nebel, B., Complexity results for SAS+ planning, Comput. Intell., 11, 4, 625-655, (1995)
[2] Barnes, J. M.; Pandey, A.; Garlan, D., Automated planning for software architecture evolution, (2013 28th IEEE/ACM International Conference on Automated Software Engineering (ASE), (2013)), 213-223
[3] Bernardini, S.; Smith, D. E., Developing domain-independent search control for EUROPA2, (Proc. of the Workshop on Heuristics for Domain-independent Planning: Progress, Ideas, Limitations, Challenges, 17th International Conference on Automated Planning and Scheduling, ICAPS’07, (2007))
[4] Bernardini, S.; Smith, D. E., Automatically generated heuristic guidance for EUROPA2, (Proc. of the 9th International Symposium on Artificial Intelligence, Robotics, and Automation for Space, iSAIRAS’08, (2008))
[5] Bernardini, S.; Smith, D. E., Translating pddl2.2. into a constraint-based variable/value language, (Proc. of the Workshop on Knowledge Engineering for Planning and Scheduling, 18th International Conference on Automated Planning and Scheduling, ICAPS’08, (2008))
[6] Bernardini, S.; Smith, D. E., Automatic synthesis of temporal invariants, (Proc. of the Ninth Symposium on Abstraction, Reformulation and Approximation (SARA-11), Parador de Cardona, Spain, (2011)), 10-17
[7] Bernardini, S.; Smith, D. E., Finding mutual exclusion invariants in temporal planning domains, (Proc. of the Seventh International Workshop on Planning and Scheduling for Space (IWPSS-11), Darmstadt, Germany, (2011))
[8] Blum, A.; Furst, M., Fast planning through planning graph analysis, Artif. Intell., 90, 281-300, (1997) · Zbl 1017.68533
[9] Bonet, B.; Geffner, H., Planning as heuristic search, Artif. Intell., 129, 5-33, (2001) · Zbl 0971.68146
[10] Chen, Y.; Huang, R.; Xing, Z.; Zhang, W., Long-distance mutual exclusion for planning, Artif. Intell., 173, 2, 365-391, (2009) · Zbl 1192.68639
[11] Chien, S.; Rabideau, G.; Knight, R.; Sherwood, R.; Engelhardt, B.; Mutz, D.; Estlin, T.; Smith, B.; Fisher, F.; Barret, T.; Stebbins, G.; Tran, D., ASPEN - automated planning and scheduling for space missions operations, (6th International Conference on Space Operations, (2000))
[12] Coles, A. J.; Coles, A. I.; Fox, M.; Long, D., Forward-chaining partial-order planning, (Proceedings of the Twentieth International Conference on Automated Planning and Scheduling (ICAPS-10), (2010)), 42-49
[13] Cushing, W.; Weld, D.; Kambhampati, S.; Mausam; Talamadupula, K., Evaluating temporal planning domains, (Proc. of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS-07), (2007)), 105-112
[14] Do, M. B.; Kambhampati, S., Planning as constraint satisfaction: solving the planning graph by compiling it into CSP, J. Artif. Intell. Res., 132, 151-182, (2001) · Zbl 0983.68181
[15] Edelkamp, S.; Helmert, M., Exhibiting knowledge in planning problems to minimize state encoding length, (Proc. of the Fifth European Conference on Planning (ECP’99), (1999)), 135-147
[16] Edelkamp, S.; Helmert, M., The model checking integrated planning system (MIPS), AI Mag., 22, 3, 67-71, (2001)
[17] Edelkamp, S.; Hoffmann, J., PDDL2.2: the language for the classical part of the 4th international planning competition, (2004), Albert-Ludwigs-Universität Freiburg, Tech. Rep. 195
[18] Eyerich, P.; Mattmüller, R.; Röger, G., Using the context-enhanced additive heuristic for temporal and numeric planning, (Proc. of the Nineteenth International Conference on Automated Planning and Scheduling (ICAPS-09), (2009)), 49-64
[19] Fikes, R.; Nilsson, N., STRIPS: a new approach to the application of theorem proving to problem solving, Artif. Intell., 2, 3-4, 189-208, (1971) · Zbl 0234.68036
[20] Fox, M.; Long, D., The automatic inference of state invariants in TIM, J. Artif. Intell. Res., 9, 367-421, (1998) · Zbl 0910.68199
[21] Fox, M.; Long, D., PDDL 2.1: an extension to PDDL for expressing temporal planning domains, J. Artif. Intell. Res., 20, 61-124, (2003) · Zbl 1036.68093
[22] Fox, M.; Long, D., Efficient implementation of the plan graph in STAN, J. Artif. Intell. Res., 10, 87-115, (2011) · Zbl 0914.68180
[23] Frank, J.; Jónsson, A., Constraint based attribute and interval planning, Constraints, 8, 4, 339-364, (2003), Special Issue on Planning · Zbl 1074.68609
[24] Fratini, S.; Pecora, F.; Cesta, A., Unifying planning and scheduling as timelines in a component-based perspective, Arch. Control Sci., 18, 2, 5-45, (2008) · Zbl 1184.93053
[25] Gerevini, A.; Saetti, A.; Serina, I., An approach to temporal planning and scheduling in domains with predictable exogenous events, J. Artif. Intell. Res., 25, 187-231, (2006) · Zbl 1161.68783
[26] Gerevini, A.; Schubert, L., Inferring state constraints for domain-independent planning, (Proc. of the Fifteenth National Conference on Artificial Intelligence (AAAI-98), (1998)), 905-912
[27] Gerevini, A.; Schubert, L., Discovering state constraints in discoplan: some new results, (Proc. of the 17th National Conference on Artificial Intelligence (AAAI-2000), (2000)), 761-767
[28] Ghallab, M.; Laruelle, H., Representation and control in ixtet, temporal planner, (Proc. of the Second International Conference on Artificial Intelligence Planning Systems (AIPS-94), (1994), AAAI Press), 61-67
[29] Ghosh, N.; Ghosh, S. K., An intelligent approach for security management of an enterprise network using planner, (Pratihar, D. K.; Jain, L. C., Intelligent Autonomous Systems: Foundations and Applications, (2010), Springer-Verlag), 187-214, Ch. 9
[30] Golden, K., A domain description language for data processing, (Proceedings of the ICAPS’03 Workshop on PDDL, (2003))
[31] Haslum, P.; Botea, A.; Helmert, M.; Bonet, B.; Koenig, S., Domain-independent construction of pattern database heuristics for cost-optimal planning, (Proc. of the Twenty-Second National Conference on Artificial Intelligence (AAAI-07), (2007)), 1007-1012
[32] Helmert, M., The fast downward planning system, J. Artif. Intell. Res., 26, 191-246, (2006) · Zbl 1182.68245
[33] Helmert, M., Concise finite-domain representations for PDDL planning tasks, Artif. Intell., 3, 17, 503-535, (2009) · Zbl 1191.68635
[34] Helmert, M.; Geffner, H., Unifying the causal graph and additive heuristics, (Proc. of the Eighteenth International Conference on Automated Planning and Scheduling (ICAPS-08), (2008)), 140-147
[35] Hoffmann, J.; Nebel, B., The FF planning system: fast plan generation through heuristic search, J. Artif. Intell. Res., 14, 253-302, (2001) · Zbl 0970.68044
[36] Howey, R.; Long, D.; Fox, M., Val: automatic plan validation, continuous effects and mixed initiative planning using pddl, (16th IEEE International Conference on Tools with Artificial Intelligence, (2004)), 294-301
[37] Huang, R.; Chen, Y.; Zhang, W., A novel transition based encoding scheme for planning as satisfiability, (Proc. of the Twenty-Forth National Conference on Artificial Intelligence (AAAI-10), vol. 2, (2010), AAAI Press), 89-94
[38] Iatauro, M., EUROPA main wiki page, (2017)
[39] Kautz, H.; Selman, B., Unifying SAT-based and graph-based planning, (Proc. of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI-99), (1999), Morgan Kaufmann Publishers Inc.), 318-325
[40] Liu, Z.; Ranganathan, A.; Riabov, A., A planning approach for message-oriented semantic web service composition, (Proceedings of the 22nd National Conference on Artificial Intelligence - Volume 2, AAAI’07, (2007), AAAI Press), 1389-1394
[41] McDermott, D., The 1998 AI planning systems competition, AI Mag., 21, 2, 35-55, (2000)
[42] Muscettola, N., HSTS: integrating planning and scheduling, (Zweben, M.; Fox, M., Intelligent Scheduling, (1994), Morgan Kauffmann), 451-469
[43] Pednault, E., Toward a mathematical theory of plan synthesis, (1986), Stanford University, Department of Electrical Engineering, Ph.D. thesis
[44] Richter, S.; Westphal, M., The LAMA planner: guiding cost-based anytime planning with landmarks, J. Artif. Intell. Res., 39, 1, 127-177, (Sep. 2010)
[45] Rintanen, J., An iterative algorithm for synthesizing invariants, (Proc. of the Seventeenth National Conference on Artificial Intelligence (AAAI-00), (2000)), 806-811
[46] Rintanen, J., Regression for classical and nondeterministic planning, (Proc. of the 18th European Conference on Artificial Intelligence (ECAI-08), (2008), IOS Press), 568-571
[47] Rintanen, J., Constraint-based algorithm for computing temporal invariants, (Proc. of the European Conference on Logic in Artificial Intelligence (JELIA-14), (2014), Springer-Verlag), 665-673 · Zbl 1432.68419
[48] Rintanen, J., Schematic invariants by reduction to ground invariants, (Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17), (2017), AAAI Press), 3644-3650
[49] Vidal, V., The YAHSP planning system: forward heuristic search with lookahead plans analysis, (Proceedings of the 4th International Planning Competition (IPC-2004), Whistler, BC, Canada, (Jun. 2004)), 59-60
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.