On transformation of STRIPS planning to linear programming

• Autorzy: Galuszka A.
• Języki publikacji: EN

Abstrakty

EN

STRIPS language is a convenient representation for artificial intelligence planning problems. Planning is a task of coming up with a sequence of actions that will achieve a goal. In this work a heuristic of polynomial transformation of STRIPS planning problem to linear programming problem (LP) is presented. This is done because planning problems are hard computational problems (PSPACE- complete in general case) and LP problems are known to be computational easy. Representation of STRIPS planning as a set of equalities and inequalities based on the transformation is also proposed. The exemplary simulation shows the computational efficiency of solving planning problem with proposed transformation.

Słowa kluczowe

EN

planning; problem solving; block world; uncertainty; linear programming; computational complexity

• Wydawca: Polish Academy of Sciences, Committee of Automatic Control and Robotics
• Czasopismo: Archives of Control Sciences
• Rocznik: 2011
• Tom: Vol. 21, no. 3
• Strony: 243--267
• Opis fizyczny: Bibliogr. 38 poz., rys., tab.

Twórcy

autor

Galuszka A.

• Institute of Automatic Control, Silesian University of Technology, Gliwice, Poland,

Bibliografia

• [1] J. L. Ambite and C.A. Knoblock: Planning by rewriting. J. of Artificial Intelligence Research, 15 (2001), 207-261.
• [2] M. Avriel, M. Penn, N. Shpirer and S. Witteboon: Stowage planning for container ships to reduce the number of shifts. Annals of Operations Research, 76 (1998), 55-71.
• [3] Ch. Backstrom: Computational aspects of reordering plans. J. of Artificial Intelligence Research, 9 (1998), 99-137.
• [4] 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.
• [5] R. Bartak: Constraint satisfaction techniques in planning and scheduling: An introduction. Archives of Control Sciences, 18(2), (2008).
• [6] A. Bhattacharya and P. Vasant: Soft-sensing of level of satisfaction in TOC product-mix decision heuristic using robust fuzzy-LP. European J. of Operational Research, 177(1), (2007), 55-70.
• [7] E. K. Bish, T.Y. Leong, C.L. Li, J.W.C. Ng and D. Simchi-Levi: Analysis of a new vehicle scheduling and location problem. Naval Research Logistics, 48 (2001), 363-385.
• [8] J. Blythe: An overview of planning under uncertainty. Pre-print from AI Magazine, 20(2), (1999), 37-54.
• [9] C. Boutilier and R.I. Brafman: 2001. Partial-order planning with concurrent interacting actions. J. of Artificial Intelligence Research, 14 (2001), 105-136.
• [10] T. Bylander: The computational complexity of propositional STRIPS planning. Artificial Intelligence, 69 (1994), 165-204.
• [11] T. Bylander: A linear programming heuristic for optimal planning. In Proc. of AAAI Nat. Conf., (1997).
• [12] L. G. Chaczijan: A polynomial algorithm for linear programming. Dokl. Akad. Nauk SSSR, 244 (1979), 1093-1096.
• [13] E. R. Dougherty and Ch. R. Giardina: Mathematical methods for artificial intelligence and autonomous systems. Prentice-Hall International Inc., USA, 1988.
• [14] I. Elamvazuthi, P. Vasant and T. Ganesan: Fuzzy linear programming using modified logistic membership function. Int. Review of Automatic Control (IREACO), 3(4), (2010), 370-377.
• [15] A. Galuszka and A. Swierniak: Translation STRIPS planning in multi-robot environment to linear programming. ICAISC 2004 (LNCS 3070), (2004), 768-773.
• [16] A. Galuszka and A. Swierniak: Planning in multi-agent environment using strips representation and non-cooperative equilibrium strategy. J. of Intelligent and Robotic Systems, Springer Netherlands, ISSN: 1573-0409, 58(3), (2010), 239-251.
• [17] A. Galuszka: Block world planning with uncertainty and sensing actions as integer linear programming problem. A. Cader, L. Rutkowski, R. Tadeusiewicz, J. Zurada (Eds.): Artificial intelligence and soft computing (ISBN 83-60434-09-3), IEEE Comp. Intell. Socielty - Poland, 2006, 389-395.
• [18] A. Galuszka: Scoring functions of approximation of STRIPS planning by linear programming. In Simulation, Modelling and Optimization. Mathematics and Computers in Science and Engineering. A series of Reference Books and Text-books (Eds. I. Rudas et al.), ISBN 978-960-474-113-7, 2009, 316-321.
• [19] M. Ghallab: PDDL - the planning domain definition language. Version 1.2. Technical Report DCS TR-1165, Yale Center for Computational Vision and Control, 1998.
• [20] A. Imai, E. Nishimura, and S. Papadimitriou: The dynamic berth allocation problem for a container port. Transportation Research B, 35 (2001), 401-417.
• [21] J. Koehler, and J. Hoffmann: On reasonable and forced goal orderings andtheir Use in an agenda-driven planning algorithm. J. of Artificial Intelligence Research, 12 (2000), 339-386.
• [22] J. Koehler and K. Schuster: Elevator control as a planning problem. AIPS-2000, (2000), 331-338.
• [23] S. Kraus, K. Sycara and A. Evenchik: Reaching agreements through argumentation: a logical model and implementation. Artificial Intelligence, 104 (1998), 1-69.
• [24] R. van der Krogt: Modification strategies for SAT-based plan adaptation. Archives of Control Sciences, 18(2), (2008).
• [25] 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.
• [26] 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.
• [27] N. J. Nilson: Principles of artificial intelligence. Toga Publishing Company, Palo Alto, CA, 1980.
• [28] E. P. D. Pednault: ADL and the state-transition model of action. J. of Logic and Computation, 4(5), (1994), 467-512.
• [29] D. Peidro and P. Vasant: Transportation planning with modified s-curve membership functions using an interactive fuzzy multi-objective approach. Applied Soft Computing, 11 (2011), 2656-2663.
• [30] T. Rosa, S. Jimenez, R. Fuentetaja and D. Barrajo: Scaling up heuristic planning with relational decision trees. J. of Artificial Intelligence Research, 40 (2011), 767-813.
• [31] S. J. Russell and P. Norvig: Artificial intelligence: A modern approach. Second Edition. Prentice Hall Series in Artificial Intelligence, 2003.
• [32] J. Slaney and S. Thiebaux: Block world revisited. Artificial Intelligence, 125 (2001), 119-153.
• [33] T. Slavin: Virtual port of call. New Scientist, (1996), 40-43.
• [34] D. E. Smith and D.S. Weld: Conformant graphplan. Proc. 15th National Conf. on AI., (1998).
• [35] D. S. Weld: Recent advantages in AI planning. AI Magazine, (1999).
• [36] D. S. Weld, C. R. Anderson and D.E. Smith: Extending graphplan to handle uncertainty and sensing actions. Proc. 15th National Conf. on AI, (1998), 897-904.
• [37] I. D. Wilson and P.A. Roach: Container stowage planning: a methodology for generating computerised solutions. J. of the Operational Research Society, 51 (2000), 1248-1255.
• [38] Y. Zhang:. Solving large-scale linear programs by interior-point methods under the MATLAB Environment. Technical Report TR96-01, Department of Mathematics and Statistics, University of Maryland, Baltimore County, Baltimore, MD, 1995.