Specifying and computing preferred plans. (English) Zbl 1225.68241

Summary: We address the problem of specifying and computing preferred plans using rich, qualitative, user preferences. We propose a logical language for specifying preferences over the evolution of states and actions associated with a plan. We provide a semantics for our first-order preference language in the situation calculus, and prove that progression of our preference formulae preserves this semantics. This leads to the development of PPlan, a bounded best-first search planner that computes preferred plans. Our preference language is amenable to integration with many existing planners, and beyond planning, can be used to support a diversity of dynamical reasoning tasks that employ preferences.


68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68T30 Knowledge representation
Full Text: DOI


[1] Bacchus, F.; Kabanza, F., Using temporal logics to express search control knowledge for planning, Artificial intelligence, 16, 123-191, (2000) · Zbl 0939.68827
[2] Baier, J.; McIlraith, S., Planning with first-order temporally extended goals using heuristic search, (), 788-795
[3] Baier, J.A.; Bacchus, F.; McIlraith, S.A., A heuristic search approach to planning with temporally extended preferences, (), 1808-1815
[4] Baier, J.A.; Bacchus, F.; McIlraith, S.A., A heuristic search approach to planning with temporally extended preferences, Artificial intelligence, 173, 5-6, 593-618, (2009) · Zbl 1191.68623
[5] Baier, J.A.; McIlraith, S.A., On domain-independent heuristics for planning with qualitative preferences, ()
[6] Baier, J.A.; McIlraith, S.A., Planning with preferences, AI magazine, 29, 4, 25-36, (2008)
[7] Baral, C.; Kreinovich, V.; Trejo, R., Computational complexity of planning with temporal goals, (), 509-514
[8] Benferhat, S.; Dubois, D.; Prade, H., Towards a possibilistic logic handling of preferences, (), 303-317 · Zbl 0986.91006
[9] Benton, J.; Kambhampati, S.; Do, M.B., Yochanps: PDDL3 simple preferences and partial satisfaction planning, (), 54-57
[10] Benton, J.; van den Briel, M.; Kambhampati, S., A hybrid linear programming and relaxed plan heuristic for partial satisfaction problems, (), 34-41
[11] Bienvenu, M.; Fritz, C.; McIlraith, S., Planning with qualitative temporal preferences, (), 134-144
[12] Bienvenu, M.; Fritz, C.; Sohrabi, S.; McIlraith, S., PPLAN: code, experiments, (2006)
[13] Boutilier, C.; Brafman, R.; Domshlak, C.; Hoos, H.; Poole, D., CP-nets: A tool for representing and reasoning about conditional ceteris paribus preference statements, Journal of artificial intelligence research, 21, 135-191, (2004) · Zbl 1080.68685
[14] Brafman, R.I.; Chernyavsky, Y., Planning with goal preferences and constraints, (), 182-191
[15] Brewka, G., Complex preferences for answer set optimization, (), 213-223
[16] Brewka, G., A rank based description language for qualitative preferences, (), 303-307
[17] Brewka, G.; Benferhat, S.; Berre, D.L., Qualitative choice logic, Artificial intelligence, 157, 1-2, (2004), Special Issue on Nonmonotonic Reasoning
[18] Burgard, W.; Cremers, A.B.; Fox, D.; Hähnel, D.; Lakemeyer, G.; Schulz, D.; Steiner, W.; Thrun, S., Experiences with an interactive museum tour-guide robot, Artificial intelligence, 114, 1-2, 3-55, (1999) · Zbl 0939.68865
[19] Bylander, T., The computational complexity of propositional STRIPS planning, Artificial intelligence, 69, 1-2, 165-204, (1994) · Zbl 0821.68065
[20] Coste-Marquis, S.; Lang, J.; Liberatore, P.; Marquis, P., Expressive power and succinctness of propositional languages for preference representation, (), 203-212
[21] De Giacomo, G.; Lespérance, Y.; Levesque, H., Congolog, a concurrent programming language based on the situation calculus, Artificial intelligence, 121, 1-2, 109-169, (2000) · Zbl 0948.68175
[22] Delgrande, J.; Schaub, T.; Tompits, H., Domain-specific preferences for causual reasoning and planning, (), 673-682
[23] Delgrande, J.P.; Schaub, T.; Tompits, H., A general framework for expressing preferences in causal reasoning and planning, Journal of logic and computation, 17, 871-907, (2007) · Zbl 1132.68051
[24] Edelkamp, S., Optimal symbolic PDDL3 planning with MIPS-BDD, (), 31-33
[25] Edelkamp, S.; Jabbar, S.; Naizih, M., Large-scale optimal PDDL3 planning with MIPS-XXL, (), 28-30
[26] Ehrgott, M., Multicriteria optimization, (2000), Springer Berlin · Zbl 0956.90039
[27] Eiter, T.; Faber, W.; Leone, N.; Pfeifer, G.; Polleres, A., Answer set planning under action costs, Journal of artificial intelligence research, 19, 25-71, (2003) · Zbl 1026.68124
[28] Erol, K.; Nau, D.S.; Subrahmanian, V.S., Complexity, decidability and undecidability results for domain-independent planning, Artificial intelligence, 76, 1-2, 75-88, (1995) · Zbl 1013.68548
[29] Feldmann, R.; Brewka, G.; Wenzel, S., Planning with prioritized goals, (), 503-514
[30] Ferrein, A.; Fritz, C.; Lakemeyer, G., On-line decision-theoretic golog for unpredictable domains, (), 322-336
[31] Fritz, C.; McIlraith, S., Decision-theoretic GOLOG with qualitative preferences, (), 153-163
[32] Gabaldon, A., Precondition control and the progression algorithm, (), 634-643
[33] Gerevini, A.; Haslum, P.; Long, D.; Saetti, A.; Dimopoulos, Y., Deterministic planning in the fifth international planning competition: PDDL3 and experimental evaluation of the planners, Artificial intelligence, 173, 5-6, 619-668, (2009) · Zbl 1191.68634
[34] A. Gerevini, D. Long, Plan constraints and preferences in PDDL3: The language of the fifth international planning competition. Tech. Rep., University of Brescia, 2005.
[35] Giunchiglia, E.; Maratea, M., Planning as satisfiability with preferences, (), 987-992
[36] Goldsmith, J.; Ulrich, J., AI magazine, 29, 4, (2008), Winter 2008, Special Issue on Preferences
[37] Green, C.C., Application of theorem proving to problem solving, (), 219-240
[38] Haddawy, P.; Hanks, S., Representations for decision-theoretic planning: utility functions for deadline goals, (), 71-82
[39] Helmert, M., Decidability and undecidability results for planning with numerical state variables, (), 44-53
[40] 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
[41] Hsu, C.-W.; Wah, B.; Huang, R.; Chen, Y., Constraint partitioning for solving planning problems with trajectory constraints and goal preferences, (), 1924-1929
[42] Kautz, H.A.; Selman, B., Unifying SAT-based and graph-based planning, (), 318-325
[43] Kvarnström, J.; Doherty, P., Talplanner: A temporal logic based forward chaining planner, Annals of mathematics and artificial intelligence, 30, 119-169, (2000) · Zbl 1002.68158
[44] Levesque, H.J.; Reiter, R.; Lesperance, Y.; Lin, F.; Scherl, R.B., GOLOG: A logic programming language for dynamic domains, Journal of logic programming, 31, 1-3, 59-83, (1997) · Zbl 0880.68008
[45] S. Liaskos, Acquiring and reasoning about variability in goal models, PhD in Computer Science, Department of Computer Science, University of Toronto, Toronto, Canada, 2008.
[46] Liaskos, S.; McIlraith, S.A.; Mylopoulos, J., Towards augmenting requirements models with preferences, (), 565-569
[47] J. McCarthy, Situations, actions and causal laws. Tech. Rep., Stanford University, 1963.
[48] 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.
[49] McIlraith, S.; Son, T., Adapting golog for composition of semantic web services, (), 482-493
[50] Myers, K.; Lee, T., Generating qualitatively different plans through metatheoretic biases, (), 570-576
[51] Pnueli, A., The temporal logic of programs, (), 46-57
[52] Puterman, M., Markov decision processes: discrete dynamic programming, (1994), Wiley New York · Zbl 0829.90134
[53] Reiter, R., Knowledge in action: logical foundations for specifying and implementing dynamical systems, (2001), MIT Press Cambridge, MA · Zbl 1018.03022
[54] Sistla, A.P.; Clarke, E.M., The complexity of propositional linear temporal logics, Journal of the ACM, 32, 3, 733-749, (1985) · Zbl 0632.68034
[55] Smith, D.E., Choosing objectives in over-subscription planning, (), 393-401
[56] Sohrabi, S.; Baier, J.A.; McIlraith, S.A., HTN planning with preferences, (), 1790-1797
[57] Sohrabi, S.; McIlraith, S.A., On planning with preferences in HTN, (), 103-109
[58] Sohrabi, S.; Prokoshyna, N.; McIlraith, S., Web service composition via generic procedures and customizing user preferences, (), 597-611
[59] Son, T.C.; Pontelli, E., Planning with preferences using logic programming, (), 247-260 · Zbl 1122.68616
[60] Son, T.C.; Pontelli, E., Planning with preferences using logic programming, Theory and practice of logic programming, 6, 5, 559-607, (2006) · Zbl 1122.68030
[61] Tu, P.H.; Son, T.C.; Pontelli, E., CPP: A constraint logic programming based planner with preferences, (), 290-296
[62] van den Briel, M.; Nigenda, R.S.; Do, M.B.; Kambhambati, S., Effective approaches for partial satisfaction (oversubscription) planning, (), 562-569
[63] von Neumann, J.; Morgenstern, O., Theory of games and economic behavior, (1994), Princeton University Press · Zbl 0205.23401
[64] Wilson, N., Extending CP-nets with stronger conditional preference statements, (), 735-741
[65] Yorke-Smith, N.; Venable, K.B.; Rossi, F., Temporal reasoning with preferences and uncertainty, (), 1385-1390
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.