Abstract
Planning is the model-based approach to autonomous behavior where a predictive model of actions and sensors is used to generate the behavior for achieving given goals. The main challenges in planning are computational as all models, whether featuring uncertainty and feedback or not, are intractable in the worst case when represented in compact form. Classical planning refers to the simplest form of planning where goals are to be achieved by applying deterministic actions to a fully known initial situation. In this invited paper, I review the inferences performed by classical planners that enable them to deal with large problems, and the transformations that have been developed for using these planners to deal with non-classical features such as soft goals, hidden goals to be recognized, planning with incomplete information and sensing, and multiagent nested beliefs.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
- Belief State
- Controller State
- Partial Observable Markov Decision Process
- Dynamic Epistemic Logic
- Plan Recognition
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Erol, K., Hendler, J., Nau, D.S.: HTN planning: Complexity and expressivity. In: Proc. 12th Nat. Conf. on Artificial Intelligence, pp. 1123–1123 (1994)
Levesque, H., Reiter, R., Lespérance, Y., Lin, F., Scherl, R.: GOLOG: A logic programming language for dynamic domains. J. of Logic Progr. 31, 59–83 (1997)
Sutton, R., Barto, A.: Introduction to Reinforcement Learning. MIT Press (1998)
Russell, S.J., Norvig, P.: Artificial Intelligence: A Modern Approach, 3rd edn. Prentice-Hall (2009)
Ghallab, M., Nau, D., Traverso, P.: Automated Planning: Theory and practice. Morgan Kaufmann (2004)
Richter, S., Westphal, M.: The LAMA planner: Guiding cost-based anytime planning with landmarks. Journal of Artificial Intelligence Research 39, 127–177 (2010)
McDermott, D.V.: Using regression-match graphs to control search in planning. Artificial Intelligence 109(1-2), 111–159 (1999)
Bonet, B., Geffner, H.: Planning as heuristic search. Artificial Intelligence 129(1-2), 5–33 (2001)
Hoffmann, J., Porteous, J., Sebastia, L.: Ordered landmarks in planning. Journal of Artificial Intelligence Research 22, 215–278 (2004)
Hoffmann, J., Nebel, B.: The FF planning system: Fast plan generation through heuristic search. Journal of Artificial Intelligence Research 14, 253–302 (2001)
Helmert, M.: The Fast Downward planning system. Journal of Artificial Intelligence Research 26, 191–246 (2006)
Kautz, H.A., Selman, B.: Pushing the envelope: Planning, propositional logic, and stochastic search. In: Proc. AAAI, pp. 1194–1201 (1996)
Rintanen, J.: Planning as satisfiability: Heuristics. Art. Int. 193, 45–86 (2012)
Yoon, S., Fern, A., Givan, R.: FF-replan: A baseline for probabilistic planning. In: Proc. 17th Int. Conf. on Automated Planning and Scheduling, pp. 352–359 (2007)
Geffner, H., Bonet, B.: A Concise Introduction to Models and Methods in Automated Planning. Morgan & Claypool (2013)
Cresswell, S., Coddington, A.M.: Compilation of LTL goal formulas into PDDL. In: Proc. 16th European Conf. on Artificial Intelligence, pp. 985–986 (2004)
Edelkamp, S.: On the compilation of plan constraints and preferences. In: Proc. 16th Int. Conf. on Automated Planning and Scheduling, pp. 374–377 (2006)
Albarghouthi, A., Baier, J.A., McIlraith, S.A.: On the use of planning technology for verification. In: Proc. ICAPS 2009 Workshop VV&PS (2009)
Patrizi, F., Lipovetzky, N., de Giacomo, G., Geffner, H.: Computing infinite plans for LTL goals using a classical planner. In: Proc. 22nd Int. Joint Conf. on Artificial Intelligence, pp. 2003–2008 (2011)
Taig, R., Brafman, R.: Compiling conformant probabilistic planning problems into classical planning. In: Proc. ICAPS (2013)
Brafman, R., Shani, G.: A multi-path compilation approach to contingent planning. In: Proc. AAAI (2012)
Palacios, H., Albore, A., Geffner, H.: Compiling contingent planning into classical planning: New translations and results. In: Proc. ICAPS Workshop on Models and Paradigms for Planning under Uncertainty (2014)
Smith, D.E.: Choosing objectives in over-subscription planning. In: Proc. 14th Int. Conf. on Automated Planning and Scheduling, pp. 393–401 (2004)
Helmert, M., Do, M.B., Refanidis, I.: 2008 IPC Deterministic planning competition. In: 6th IPC Booklet, ICAPS 2008 (2008)
Keyder, E., Geffner, H.: Soft goals can be compiled away. Journal of Artificial Intelligence Research 36, 547–556 (2009)
Ramírez, M., Geffner, H.: Probabilistic plan recognition using off-the-shelf classical planners. In: Proc. 24th Conf. on Artificial Intelligence, pp. 1121–1126 (2010)
Bonet, B., Geffner, H.: Flexible and scalable partially observable planning with linear translations. In: Proc. AAAI (2014)
Palacios, H., Geffner, H.: Compiling uncertainty away in conformant planning problems with bounded width. JAIR 35, 623–675 (2009)
Bonet, B., Geffner, H.: Width and complexity of belief tracking in non-deterministic conformant and contingent planning. In: Proc. 26nd Conf. on Artificial Intelligence, pp. 1756–1762 (2012)
Albore, A., Palacios, H., Geffner, H.: A translation-based approach to contingent planning. In: Proc. 21st Int. Joint Conf. on Artificial Intelligence, pp. 1623–1628 (2009)
Maliah, S., Brafman, R., Karpas, E., Shani, G.: Partially observable online contingent planning using landmark heuristics. In: Proc. ICAPS (2014)
Bonet, B., Palacios, H., Geffner, H.: Automatic derivation of memoryless policies and finite-state controllers using classical planners. In: Proc. ICAPS (2009)
Fagin, R., Halpern, J., Moses, Y., Vardi, M.: Reasoning about Knowledge. MIT Press (1995)
van Ditmarsch, H., van der Hoek, W., Kooi, B.: Dynamic Epistemic Logic. Springer (2007)
van Ditmarsch, H., Kooi, B.: Semantic results for ontic and epistemic change. In: Logic and the Foundations of Game and Decision Theory (LOFT 7), pp. 87–117 (2008)
Kominis, F., Geffner, H.: Beliefs in multiagent planning: From one agent to many. In: Proc. ICAPS Workshop on Distributed and Multi-Agent Planning (2014)
Brafman, R., Shani, G., Zilberstein, S.: Qualitative planning under partial observability in multi-agent domains. In: Proc. AAAI (2013)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Geffner, H. (2014). Non-classical Planning with a Classical Planner: The Power of Transformations. In: Fermé, E., Leite, J. (eds) Logics in Artificial Intelligence. JELIA 2014. Lecture Notes in Computer Science(), vol 8761. Springer, Cham. https://doi.org/10.1007/978-3-319-11558-0_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-11558-0_3
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11557-3
Online ISBN: 978-3-319-11558-0
eBook Packages: Computer ScienceComputer Science (R0)