On transformation of conditional, conformant and parallel planning to linear programming

• Autorzy: Galuszka Adam , Probierz Eryka

Identyfikatory

DOI

10.24425/acs.2021.137423

• Języki publikacji: EN

Abstrakty

EN

Classical planning in Artificial Intelligence is a computationally expensive problem of finding a sequence of actions that transforms a given initial state of the problem to a desired goal situation. Lack of information about the initial state leads to conditional and conformant planning that is more difficult than classical one. A parallel plan is the plan in which some actions can be executed in parallel, usually leading to decrease of the plan execution time but increase of the difficulty of finding the plan. This paper is focused on three planning problems which are computationally difficult: conditional, conformant and parallel conformant. To avoid these difficulties a set of transformations to Linear Programming Problem (LPP), illustrated by examples, is proposed. The results show that solving LPP corresponding to the planning problem can be computationally easier than solving the planning problem by exploring the problem state space. The cost is that not always the LPP solution can be interpreted directly as a plan.

Słowa kluczowe

EN

planning; conformant planning; conditional planning; parallel planning; uncertainty; linear programming; computational complexity

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2021
• Tom: Vol. 31, No. 2
• Strony: 375--399
• Opis fizyczny: Bibliogr. 33 poz., tab., wzory

Twórcy

autor

Galuszka Adam

• Department of Automatic Control and Robotics, Silesian University of Technology, Akademicka 16, 44-100 Gliwice, Poland

autor

Probierz Eryka

• Department of Automatic Control and Robotics, Silesian University of Technology, Akademicka 16, 44-100 Gliwice, Poland

Bibliografia

• [1] J.L. Ambite and C.A. Knoblock: Planning by rewriting. Journal of Artificial Intelligence Research, 15 (2001), 207-261, DOI: 10.1613/jair.754.
• [2] Ch. Backstrom: Computational Aspects of Reordering Plans. Journal of Artificial Intelligence Research, 9 (1998), 99-137, DOI: 10.1613/jair.477.
• [3] Ch. Baral, V. Kreinovich, and R. Trejo: Computational complexity of planning and approximate planning in the presence of incompleteness. Artificial Intelligence, 122 (2000), 241-267, DOI: 10.1007/3-540-44957-4_59.
• [4] R. Bartak: Constraint satisfaction techniques in planning and scheduling: An introduction. Archives of Control Sciences, 18(2), (2008), DOI: 10.1007/s10845-008-0203-4.
• [5] A. Bhattacharya and P. Vasant: Soft-sensing of level of satisfaction in TOC product-mix decision heuristic using robust fuzzy-LP, European Journal of Operational Research, 177(1), (2007), 55-70, DOI: 10.1016/j.ejor.2005.11.017.
• [6] J. Blythe: An Overview of Planning Under Uncertainty. Pre-print from AI Magazine, 20(2), (1999), 37-54, DOI: 10.1007/3-540-48317-9_4.
• [7] T. Bylander: The Computational Complexity of Propositional STRIPS Planning. Artificial Intelligence, 69 (1994), 165-204, DOI: 10.1016/0004-3702(94)90081-7.
• [8] T. Bylander: A Linear Programming Heuristic for Optimal Planning. In Proc. of AAAI Nat. Conf., (1997).
• [9] L.G. Chaczijan: A polynomial algorithm for linear programming. Dokł. Akad. Nauk SSSR, 244 (1979), 1093-1096.
• [10] E.R. Dougherty and Ch.R. Giardina: Mathematical Methods for Artificial Intelligence and Autonomous Systems, Prentice-Hall International, Inc. USA, 1988.
• [11] I. Elamvazuthi, P. Vasant, and T. Ganesan: Fuzzy Linear Programming using Modified Logistic Membership Function, International Review of Automatic Control, 3(4), (2010), 370-377, DOI: 10.3923/jeasci.2010.239.245.
• [12] A. Galuszka: On transformation of STRIPS planning to linear programming. Archives of Control Sciences, 3 (2011), 227-251, DOI:
• 10.2478/v10170-010-0042-3.
• [13] A. Galuszka, W. Ilewicz, and A. Olczyk: On Translation of Conformant Action Planning to Linear Programming. Proc. 20th International Conference on Methods and Models in Automation & Robotics, 24-27 August, (2005), 353-357, DOI: 10.1109/MMAR.2015.7283901.
• [14] A. Galuszka, T. Grzejszczak, J. Smieja, A. Olczyk, and J. Kocerka: On parallel conformant planning as an optimization problem. 32nd Annual European Simulation and Modelling Conference, Ghent, (2018), 17-22.
• [15] M. Ghallab et al.: PDDL - the Planning Domain Definition Language, Version 1.2. Technical Report DCS TR-1165, Yale Center for Computational Vision and Control, (1998).
• [16] A. Grastien and E. Scala: Sampling Strategies for Conformant Planning. Proc. Twenty-Eighth International Conference on Automated Planning and Scheduling, (2018), 97-105.
• [17] A. Grastien and E. Scala: CPCES: A planning framework to solve conformant planning problems through a counterexample guided refinement. Artificial Intelligence, 284 (2020), 103271, DOI: 10.1016/j.artint.2020.103271.
• [18] D. Hoeller, G. Behnke, P. Bercher, S. Biundo, H. Fiorino, D. Pellier, and R. Alford: HDDL: An extension to PDDL for expressing hierarchical planning problems. Proc. AAAI Conference on Artificial Intelligence, 34(6), (2020), 1-9, DOI: 10.1609/aaai.v34i06.6542.
• [19] J. Koehler and K. Schuster: Elevator Control as a Planning Problem. AIPS-2000, (2000), 331-338.
• [20] R. van der. Krogt: Modification strategies for SAT-based plan adaptation. Archives of Control Sciences, 18(2), (2008).
• [21] M.D. Madronero, D. Peidro, and P. Vasant: Vendor selection problem by using an interactive fuzzy multi-objective approach with modified s-curve membership functions. Computers and Mathematics with Applications, 60 (2010), 1038-1048, DOI: 10.1016/j.camwa.2010.03.060.
• [22] A. Nareyek, C. Freuder, R. Fourer, E. Giunchiglia, R.P. Goldman, H. Kautz, J. Rintanen, and A. Tate: Constraitns and AI Planning. IEEE Intelligent Systems, (2005), 62-72, DOI: 10.1109/MIS.2005.25.
• [23] N.J. Nilson: Principles of Artificial Intelligence. Toga Publishing Company, Palo Alto, CA, 1980.
• [24] E.P.D. Pednault: ADL and the state-transition model of action. Journal of Logic and Computation, 4(5), (1994), 467-512, DOI: 10.1093/logcom/4.5.467.
• [25] D. Peidro and P. Vasant: Transportation planning with modified scurve membership functions using an interactive fuzzy multi-objective approach, Applied Soft Computing, 11 (2011), 2656-2663, DOI: 10.1016/j.asoc.2010.10.014.
• [26] F. Pommerening, G. Roger, M. Helmert, H. Cambazard, L.M. Rousseau, and D. Salvagnin: Lagrangian decomposition for classical planning. Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, (2020), 4770-4774, DOI: 10.24963/ijcai.2020/663.
• [27] T. Rosa, S. Jimenez, R. Fuentetaja, and D. Barrajo: Scaling up heuristic planning with relational decision trees. Journal of Artificial Intelligence Research, 40 (2011), 767-813, DOI: 10.1613/jair.3231.
• [28] S.J. Russell and P. Norvig: Artificial Intelligence: A Modern Approach. Fourth Edition. Pearson, 2020.
• [29] J. Seipp, T. Keller, and M. Helmert: Saturated post-hoc optimization for classical planning. Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence, (2021).
• [30] D.E. Smith and D.S. Weld: Conformant Graphplan. Proc. 15th National Conf. on AI, (1998).
• [31] D.S. Weld: Recent Advantages in AI Planning. AI Magazine, (1999), DOI: 10.1609/aimag.v20i2.1459.
• [32] D.S. Weld, C.R. Anderson, and D.E. Smith: Extending graphplan to handle uncertainty & sensing actions. Proc. 15th National Conf. on AI, (1998), 897-904.
• [33] X. Zhang, A. Grastien, and E. Scala: Computing superior counterexamples for conformant planning. Proc. AAAI Conference on Artificial Intelligence 34(6), (2020), 1-8, DOI: 10.1609/aaai.v34i06.6558.

Uwagi

1. The work of Adam Galuszka was supported by the SUT grant No 02/060/RGP20/0019. The work of Eryka Probierz was supported in part by the European Union through the European Social Fund as a scholarship under Grant POWR.03.02.00-00-I029, and in part by the Silesian University of Technology (SUT) through the subsidy for maintaining and developing the research potential grant in 2021 for young researchers in analysis. This work was supported by Upper Silesian Centre for Computational Science and Engineering (GeCONiI) through The National Centre for Research and Development (NCBiR) under Grant POIG.02.03.01-24-099/13. Partial results of the first author have been presented on conferences: Methods and Models in Automation and Robotics in 2015 and European Simulation Multiconference in 2018.

2. Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).