×

zbMATH — the first resource for mathematics

A heuristic search approach to planning with temporally extended preferences. (English) Zbl 1191.68623
Summary: Planning with preferences involves not only finding a plan that achieves the goal, it requires finding a preferred plan that achieves the goal, where preferences over plans are specified as part of the planner’s input. In this paper we provide a technique for accomplishing this objective. Our technique can deal with a rich class of preferences, including so-called temporally extended preferences (TEPs). Unlike simple preferences which express desired properties of the final state achieved by a plan, TEPs can express desired properties of the entire sequence of states traversed by a plan, allowing the user to express a much richer set of preferences. Our technique involves converting a planning problem with TEPs into an equivalent planning problem containing only simple preferences. This conversion is accomplished by augmenting the inputed planning domain with a new set of predicates and actions for updating these predicates. We then provide a collection of new heuristics and a specialized search algorithm that can guide the planner towards preferred plans. Under some fairly general conditions our method is able to find a most preferred plan, i.e., an optimal plan. It can accomplish this without having to resort to admissible heuristics, which often perform poorly in practice. Nor does our technique require an assumption of restricted plan length or make-span. We have implemented our approach in the HPlan-P planning system and used it to compete in the 5th International Planning Competition, where it achieved distinguished performance in the Qualitative Preferences track.

MSC:
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
Software:
Graphplan; PDDL; Yochan
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bacchus, F.; Kabanza, F., Planning for temporally extended goals, Annals of mathematics and artificial intelligence, 22, 1-2, 5-27, (1998) · Zbl 1034.68549
[2] J.A. Baier, S.A. McIlraith, Planning with first-order temporally extended goals using heuristic search, in: Proceedings of the 21st National Conference on Artificial Intelligence (AAAI), Boston, MA, 2006, pp. 788-795
[3] J.A. Baier, S.A. McIlraith, On domain-independent heuristics for planning with qualitative preferences, in: 7th Workshop on Nonmonotonic Reasoning, Action and Change (NRAC), 2007
[4] J. Benton, S. Kambhampati, M.B. Do, YochanPS: PDDL3 simple preferences and partial satisfaction planning, in: 5th International Planning Competition Booklet (IPC-2006), Lake District, England, July 2006, pp. 54-57
[5] J. Benton, M. van den Briel, S. Kambhampati, A hybrid linear programming and relaxed plan heuristic for partial satisfaction problems, in: Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS), Providence, RI, September 2007, pp. 34-41
[6] M. Bienvenu, C. Fritz, S. McIlraith, Planning with qualitative temporal preferences, in: Proceedings of the 10th International Conference on Knowledge Representation and Reasoning (KR), Lake District, England, 2006, pp. 134-144
[7] Blum, A.; Furst, M.L., Fast planning through planning graph analysis, Artificial intelligence, 90, 1-2, 281-300, (1997) · Zbl 1017.68533
[8] Bonet, B.; Geffner, H., Planning as heuristic search, Artificial intelligence, 129, 1-2, 5-33, (2001) · Zbl 0971.68146
[9] B. Bonet, H. Geffner, Heuristics for planning with penalties and rewards using compiled knowledge, in: Proceedings of the 10th International Conference on Knowledge Representation and Reasoning (KR), 2006, pp. 452-462
[10] R. Brafman, Y. Chernyavsky, Planning with goal preferences and constraints, in: Proceedings of the 15th International Conference on Automated Planning and Scheduling (ICAPS), Monterey, CA, June 2005, pp. 182-191
[11] Coles, A.I.; Smith, A.J., Marvin: A heuristic search planner with online macro-action learning, Journal of artificial intelligence research, 28, 119-156, (February 2007)
[12] J.P. Delgrande, T. Schaub, H. Tompits, Domain-specific preferences for causal reasoning and planning, in: Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS), Whistler, Canada, June 2004, pp. 63-72
[13] Dimopoulos, Y.; Gerevini, A.; Haslum, P.; Saetti, A., The benchmark domains of the deterministic part of ipc-5, (July 2006)
[14] M.B. Do, J. Benton, M. van den Briel, S. Kambhampati, Planning with goal utility dependencies, in: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), Hyderabad, India, 2007, pp. 1872-1878
[15] S. Edelkamp, Optimal symbolic PDDL3 planning with MIPS-BDD, in: 5th International Planning Competition Booklet (IPC-2006), Lake District, England, July 2006, pp. 31-33
[16] S. Edelkamp, J. Hoffmann, PDDL2.2: The language for the classical part of the 4th International Planning Competition, Tech. Rep. 195, Computer Science Department, University of Freiburg, 2004
[17] S. Edelkamp, S. Jabbar, M. Naizih, Large-scale optimal PDDL3 planning with MIPS-XXL, in: 5th International Planning Competition Booklet (IPC-2006), Lake District, England, July 2006, pp. 28-30
[18] R. Feldmann, G. Brewka, S. Wenzel, Planning with prioritized goals, in: Proceedings of the 10th International Conference on Knowledge Representation and Reasoning (KR), Lake District, England, July 2006, pp. 503-514
[19] Fikes, R.; Nilsson, N.J., STRIPS: A new approach to the application of theorem proving to problem solving, Artificial intelligence, 2, 3/4, 189-208, (1971) · Zbl 0234.68036
[20] Fox, M.; Long, D., PDDL2.1: an extension to PDDL for expressing temporal planning domains, Journal of artificial intelligence research, 20, 61-124, (2003) · Zbl 1036.68093
[21] B.C. Gazen, C.A. Knoblock, Combining the expressivity of UCPOP with the efficiency of graphplan, in: ECP97. Toulouse, France, September 1997, pp. 221-233
[22] Gerevini, A.; Dimopoulos, Y.; Haslum, P.; Saetti, A., 5th international planning competition, (July 2006)
[23] A. Gerevini, D. Long, Plan constraints and preferences for PDDL3, Tech. Rep. 2005-08-07, Department of Electronics for Automation, University of Brescia, Brescia, Italy, 2005
[24] E. Giunchiglia, M. Maratea, Planning as satisfiability with preferences, in: Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI), Vancouver, British Columbia, 2007, pp. 987-992
[25] Haslum, P., Openstacks SP-NCE domain, (2007)
[26] Hoffmann, J., The metric-FF planning system: translating ignoring delete lists to numeric state variables, Journal of artificial intelligence research, 20, 291-341, (2003) · Zbl 1036.68095
[27] Hoffmann, J.; Nebel, B., The FF planning system: fast plan generation through heuristic search, Journal of artificial intelligence research, 14, 253-302, (2001) · Zbl 0970.68044
[28] C.-W. Hsu, B. Wah, R. Huang, Y. Chen, Constraint partitioning for solving planning problems with trajectory constraints and goal preferences, in: Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), Hyderabad, India, January 2007, pp. 1924-1929
[29] D.V. McDermott, A heuristic estimator for means-ends analysis in planning, in: AIPS96, 1996, pp. 142-149
[30] D.V. McDermott, PDDL—The Planning Domain Definition Language, Tech. Rep. TR-98-003/DCS TR-1165, Yale Center for Computational Vision and Control, 1998
[31] E.P.D. Pednault, ADL: Exploring the middle ground between STRIPS and the situation calculus, in: Proceedings of the 1st International Conference of Knowledge Representation and Reasoning (KR), Toronto, Canada, May 1989, pp. 324-332
[32] A. Pnueli, The temporal logic of programs, in: Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (FOCS), 1977, pp. 46-57
[33] R. Sanchez, S. Kambhampati, Planning graph heuristics for selecting objectives in over-subscription planning problems, in: Proceedings of the 15th International Conference on Automated Planning and Scheduling (ICAPS), Monterey, CA, 2005, pp. 192-201
[34] D.E. Smith, Choosing objectives in over-subscription planning, in: Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS), Whistler, Canada, 2004, pp. 393-401
[35] Son, T.C.; Pontelli, E., Planning with preferences using logic programming, (), 247-260 · Zbl 1122.68616
[36] M. van den Briel, R.S. Nigenda, M.B. Do, S. Kambhampati, Effective approaches for partial satisfaction (over-subscription) planning, in: Proceedings of the 19th National Conference on Artificial Intelligence (AAAI), 2004, pp. 562-569
[37] L. Zhu, R. Givan, Simultaneous heuristic search for conjunctive subgoals, in: Proceedings of the 20th National Conference on Artificial Intelligence (AAAI), Pittsburgh, Pennsylvania, USA, July 9-13 2005, pp. 1235-1241
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.