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.
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68T30 | Knowledge representation |
References:
| [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, (Proceedings of the 21st National Conference on Artificial Intelligence (AAAI-06) (2006)), 788-795 |
| [3] | Baier, J. A.; Bacchus, F.; McIlraith, S. A., A heuristic search approach to planning with temporally extended preferences, (Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07) (2007)), 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, (Proceedings of the 7th Workshop on Nonmonotonic Reasoning, Action and Change (NRAC-07) (2007)) |
| [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, (Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-01) (2001)), 509-514 |
| [8] | Benferhat, S.; Dubois, D.; Prade, H., Towards a possibilistic logic handling of preferences, (Applied Intelligence, vol. 14 (2001), Kluwer), 303-317 · Zbl 0986.91006 |
| [9] | Benton, J.; Kambhampati, S.; Do, M. B., YochanPS: PDDL3 simple preferences and partial satisfaction planning, (Proceedings of the 5th International Planning Competition Booklet (IPC-06) (2006)), 54-57 |
| [10] | Benton, J.; van den Briel, M.; Kambhampati, S., A hybrid linear programming and relaxed plan heuristic for partial satisfaction problems, (Proceedings of the 17th International Conference on Automated Planning and Scheduling (ICAPS-07) (2007)), 34-41 |
| [11] | Bienvenu, M.; Fritz, C.; McIlraith, S., Planning with qualitative temporal preferences, (Proceedings of the 10th International Conference on Knowledge Representation and Reasoning (KR-06) (2006)), 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, (Proceedings of the 15th International Conference on Automated Planning and Scheduling (ICAPS-05) (2005)), 182-191 |
| [15] | Brewka, G., Complex preferences for answer set optimization, (Proceedings of the 9th International Conference on Knowledge Representation and Reasoning (KR-04) (2004)), 213-223 |
| [16] | Brewka, G., A rank based description language for qualitative preferences, (Proceedings of the 16th European Conference on Artificial Intelligence (ECAI-04) (2004)), 303-307 |
| [17] | Brewka, G.; Benferhat, S.; Berre, D. L., Qualitative choice logic, Artificial Intelligence, 157, 1-2 (2004), Special Issue on Nonmonotonic Reasoning · Zbl 1085.68159 |
| [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, (Proceedings of the 9th International Conference on Knowledge Representation and Reasoning (KR-04) (2004)), 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, (Proceedings of the 9th International Conference on Knowledge Representation and Reasoning (KR-04) (2004)), 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, (Proceedings of the 5th International Planning Competition Booklet (IPC-06) (2006)), 31-33 |
| [25] | Edelkamp, S.; Jabbar, S.; Naizih, M., Large-scale optimal PDDL3 planning with MIPS-XXL, (Proceedings of the 5th International Planning Competition Booklet (IPC-06) (2006)), 28-30 |
| [26] | Ehrgott, M., Multicriteria Optimization (2000), Springer: 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, (Proceedings of the 10th International Conference on Knowledge Representation and Reasoning (KR-06) (2006)), 503-514 |
| [30] | Ferrein, A.; Fritz, C.; Lakemeyer, G., On-line decision-theoretic Golog for unpredictable domains, (Proceedings of 27th German Conference on AI (KI-04) (2004)), 322-336 |
| [31] | Fritz, C.; McIlraith, S., Decision-theoretic GOLOG with qualitative preferences, (Proceedings of the 10th International Conference on Principles of Knowledge Representation and Reasoning (KR-06) (2006)), 153-163 |
| [32] | Gabaldon, A., Precondition control and the progression algorithm, (Proceedings of the 9th International Conference on Knowledge Representation and Reasoning (KR-04) (2004)), 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.; 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, (Proceedings of the 22nd Conference on Artificial Intelligence (AAAI-07) (2007)), 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, (Proceedings of the 1st International Joint Conference on Artificial Intelligence (1969)), 219-240 |
| [38] | Haddawy, P.; Hanks, S., Representations for decision-theoretic planning: Utility functions for deadline goals, (Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning (KR-96) (1992)), 71-82 |
| [39] | Helmert, M., Decidability and undecidability results for planning with numerical state variables, (Proceedings of the Sixth International Conference on Artificial Intelligence Planning Systems (AIPS-02) (2002)), 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, (Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI-07) (2007)), 1924-1929 |
| [42] | Kautz, H. A.; Selman, B., Unifying SAT-based and graph-based planning, (Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99) (1999)), 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.; 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, (Proceedings of the 24th IEEE/ACM International Conference on Automated Software Engineering (ASE-09) (2009)), 565-569 |
| [47] | J. McCarthy, Situations, actions and causal laws. Tech. Rep., Stanford University, 1963.; 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.; 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, (Proceedings of the 8th International Conference on Knowledge Representation and Reasoning (2002)), 482-493 |
| [50] | Myers, K.; Lee, T., Generating qualitatively different plans through metatheoretic biases, (Proceedings of the 16th National Conference on Artificial Intelligence (AAAI-99) (1999)), 570-576 |
| [51] | Pnueli, A., The temporal logic of programs, (Proceedings of the 18th IEEE Symposium on Foundations of Computer Science (FOCS-77) (1977)), 46-57 |
| [52] | Puterman, M., Markov Decision Processes: Discrete Dynamic Programming (1994), Wiley: Wiley New York · Zbl 0829.90134 |
| [53] | Reiter, R., Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems (2001), MIT Press: 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, (Proceedings of the 14th International Conference on Automated Planning and Scheduling (ICAPS-04) (2004)), 393-401 |
| [56] | Sohrabi, S.; Baier, J. A.; McIlraith, S. A., HTN planning with preferences, (Proceedings of the 21st International Joint Conference on Artificial Intelligence (IJCAI-09) (2009)), 1790-1797 |
| [57] | Sohrabi, S.; McIlraith, S. A., On planning with preferences in HTN, (Proceedings of the 4th Multidisciplinary Workshop on Advances in Preference Handling (M-Pref-08) at AAAI-08 (2008)), 103-109 |
| [58] | Sohrabi, S.; Prokoshyna, N.; McIlraith, S., Web service composition via generic procedures and customizing user preferences, (Proceedings of the 5th International Semantic Web Conference (ISWC-06) (2006)), 597-611 |
| [59] | Son, T. C.; Pontelli, E., Planning with preferences using logic programming, (Proceedings of the 7th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-04) (2004)), 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, (Proceedings of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR-07) (2007)), 290-296 |
| [62] | van den Briel, M.; Nigenda, R. S.; Do, M. B.; Kambhambati, S., Effective approaches for partial satisfaction (oversubscription) planning, (Proceedings of the 19th National Conference on Artificial Intelligence (AAAI-04) (2004)), 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, (Proceedings of the 19th National Conference on Artificial Intelligence (AAAI-04) (2004)), 735-741 |
| [65] | Yorke-Smith, N.; Venable, K. B.; Rossi, F., Temporal reasoning with preferences and uncertainty, (Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI-03) (2003)), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
