Abstract
Automated planning has been the subject of intensive research and is at the core of several areas of AI, including intelligent agents and robotics. In this paper, we argue that Transaction Logic is a natural specification language for planning algorithms, which enables one to see further afield and thus discover better and more general solutions than using one-of-a-kind formalisms. Specifically, we take the well-known \({\textit{STRIPS}}\) planning strategy and show that Transaction Logic lets one specify the \({\textit{STRIPS}}\) planning algorithm easily and concisely, and to prove its completeness. Moreover, extensions to allow indirect effects and to support action ramifications come almost for free. Finally, the compact and clear logical formulation of the algorithm made possible by this logic is conducive to fruitful experimentation. To illustrate this, we show that a rather simple modification of the \({\textit{STRIPS}}\) planning strategy is also complete and yields speedups of orders of magnitude.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
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
Becker, M.Y., Nanz, S.: A logic for state-modifying authorization policies. ACM Trans. Inf. Syst. Secur. 13(3), 20:1–20:28 (2010)
Bibel, W.: A deductive solution for plan generation. New Generation Computing 4(2), 115–132 (1986)
Bibel, W.: A deductive solution for plan generation. In: Schmidt, J.W., Thanos, C. (eds.) Foundations of Knowledge Base Management. Topics in Information Systems, pp. 453–473. Springer, Heidelberg (1989)
Bibel, W., del Cerro, L.F., Fronhöfer, B., Herzig, A.: Plan generation by linear proofs: On semantics. In: Metzing, D. (ed.) 13th German Workshop on Artificial Intelligence, Informatik-Fachberichte, GWAI 1989, vol. 216, pp. 49–62. Springer, Heidelberg (1989)
Bonner, A., Kifer, M.: Transaction logic programming. In: Int’l Conference on Logic Programming, pp. 257–282. MIT Press, Budapest (1993)
Bonner, A., Kifer, M.: Applications of transaction logic to knowledge representation. In: Gabbay, D.M., Ohlbach, H.J. (eds.) ICTL 1994. LNCS, vol. 827, pp. 67–81. Springer, Heidelberg (1994)
Bonner, A., Kifer, M.: Transaction logic programming (or a logic of declarative and procedural knowledge). Tech. Rep. CSRI-323, University of Toronto (November 1995), http://www.cs.toronto.edu/~bonner/transaction-logic.html
Bonner, A., Kifer, M.: Concurrency and communication in transaction logic. In: Joint Int’l Conference and Symposium on Logic Programming, pp. 142–156. MIT Press, Bonn (1996)
Bonner, A., Kifer, M.: A logic for programming database transactions. In: Chomicki, J., Saake, G. (eds.) Logics for Databases and Information Systems, ch. 5, pp. 117–166. Kluwer Academic Publishers (March 1998)
Bonner, A.J., Kifer, M.: An overview of transaction logic. Theoretical Computer Science 133 (1994)
Cresswell, S., Smaill, A., Richardson, J.: Deductive synthesis of recursive plans in linear logic. In: Biundo, S., Fox, M. (eds.) ECP 1999. LNCS, vol. 1809, pp. 252–264. Springer, Heidelberg (2000)
Fikes, R.E., Nilsson, N.J.: STRIPS: A new approach to the application of theorem proving to problem solving. Artificial Intelligence 2(3-4), 189–208 (1971)
Fodor, P., Kifer, M.: Tabling for transaction logic. In: Proceedings of the 12th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming, PPDP 2010, pp. 199–208. ACM, New York (2010)
Giunchiglia, E., Lifschitz, V.: Dependent fluents. In: Proceedings of International Joint Conference on Artificial Intelligence (IJCAI), pp. 1964–1969 (1995)
Guglielmi, A.: Concurrency and plan generation in a logic programming language with a sequential operator. In: Hentenryck, P.V. (ed.) ICLP, pp. 240–254. MIT Press (1994)
Hölldobler, S., Schneeberger, J.: A new deductive approach to planning. New Generation Computing 8(3), 225–244 (1990)
Kahramanogullari, O.: Towards planning as concurrency. In: Hamza, M.H. (ed.) Artificial Intelligence and Applications, pp. 387–393. IASTED/ACTA Press (2005)
Kahramanogullari, O.: On linear logic planning and concurrency. Information and Computation 207(11), 1229–1258 (2009); Special Issue: Martín-Vide, C., Otto, F., Fernau, H. (eds.): LATA 2008. LNCS, vol. 5196. Springer, Heidelberg (2008)
Lifschitz, V.: On the semantics of strips. In: Georgeff, M. (ed.) Lansky, Amy (eds, pp. 1–9. Morgan Kaufmann, San Mateo (1987)
Nau, D., Ghallab, M., Traverso, P.: Automated Planning: Theory & Practice. Morgan Kaufmann Publishers Inc., San Francisco (2004)
Nilsson, N.: Principles of Artificial Intelligence. Tioga Publ. Co., Paolo Alto (1980)
Reiter, R.: Knowledge in Action: Logical Foundations for Describing and Implementing Dynamical Systems. MIT Press, Cambridge (2001)
Rezk, M., Kifer, M.: Transaction logic with partially defined actions. J. Data Semantics 1(2), 99–131 (2012)
Srivastava, S., Immerman, N., Zilberstein, S., Zhang, T.: Directed search for generalized plans using classical planners. In: Proceedings of the 21st International Conference on Automated Planning and Scheduling (ICAPS 2011). AAAI (June 2011)
Swift, T., Warren, D.: Xsb: Extending the power of prolog using tabling. Theory and Practice of Logic Programming (2011)
Thielscher, M.: Computing ramifications by postprocessing. In: IJCAI, pp. 1994–2000. Morgan Kaufmann (1995)
Thielscher, M.: Ramification and causality. Artificial Intelligence 89(1-2), 317–364 (1997)
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
Basseda, R., Kifer, M., Bonner, A.J. (2014). Planning with Transaction Logic. In: Kontchakov, R., Mugnier, ML. (eds) Web Reasoning and Rule Systems. RR 2014. Lecture Notes in Computer Science, vol 8741. Springer, Cham. https://doi.org/10.1007/978-3-319-11113-1_3
Download citation
DOI: https://doi.org/10.1007/978-3-319-11113-1_3
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11112-4
Online ISBN: 978-3-319-11113-1
eBook Packages: Computer ScienceComputer Science (R0)