Analiza świata klocków jako zadanie programowania liniowego

Gałuszka, A.

Artykuł - szczegóły

Tytuł artykułu

Analiza świata klocków jako zadanie programowania liniowego

Autorzy

Gałuszka A.

Identyfikatory

Warianty tytułu

Block world analysis as linear programming problem

Języki publikacji

Abstrakty

W pracy sprowadzono problem planowania w środowisku tzw. świata klocków, posiadający reprezentację STRIPS, do problemu programowania liniowego. Uwzględniono również niepełność dostępnej informacji i przeanalizowano jej wpływ na rozwiązanie zadania programowania liniowego. Pokazano także zależność rozmiaru problemu liniowego od rozmiaru świata klocków. Transformacja do zadania programowania liniowego polega na założeniu liczby etapów planowania i przypisaniu każdemu warunkowi i operatorowi systemu STRIPS w każdym etapie planowania jednej zmiennej. Przy ograniczeniu dopuszczalnych wartości zmiennych do przedziału <0,1> założono, że wartości te odpowiadają stopniu spełnienia warunków oraz stopniu zastosowania operatorów w systemie STRIPS.

In the paper block world environment with STRIPS representation is presented as linear programming problem. It is also assumed that information about state of the problem may be incomplete and its influence to linear programming problem solution is shown. Translation of the STRIPS planning to linear programming is based on assumption of the number of planning steps and mapping conditions and operators in each planning step to variables. Variables are mapped to values between 0 and 1: it corresponds to truth degree of conditions and operators.

Słowa kluczowe

programowanie liniowe STRIPS planowanie optymalne świat klocków

linear programming STRIPS optimal planning block world

Wydawca

Wydawnictwo Politechniki Śląskiej

Czasopismo

Zeszyty Naukowe. Automatyka / Politechnika Śląska

Rocznik

2006

Tom

z. 146

Strony

33--45

Opis fizyczny

Bibliogr. 26 poz.

Twórcy

autor

Gałuszka A.

Instytut Automatyki Politechnika Śląska, 44-100 Gliwice, ul. Akademicka 16, tel. (032)237-18-08, adam.galuszka@polsl.pl

Bibliografia

1. Barret A. i D.S. Weld. 1994. Partial-order planning: evaluating possible efficiency gains. Artificial Intelligence, 67:71-112.
2. Bylander, T. 1994. The computational complexity of prepositional STRIPS planning. Artificial Intelligence, 69:165-204.
3. Bylander T. 1997. A Linear Programming Heuristic for Optimal Planning. Int. Conf. American Association for Artificial Intelligence, 1997, www.aaai.org.
4. Cormen T.H., Ch.E. Leiserson, R.L. Rivest. 1994. Introduction to Algorithms. The Massachusetts Institute of Technology.
5. Dougherty, E.R. i Ch.R. Giardina. 1988. Mathematical Methods for Artificial Intelligence and Autonomous Systems. Prentice-Hall International, Inc. USA.
6. Gałuszka A. 1999. „Distinguish- and indistinguishability of STRIPS planning problem elements”. In Proceedings of the 11th European Simulation Symposium (Erlangen, 1999), 95-99.
7. Gałuszka A. i A. Świerniak. 2004. Translation STRIPS Planning in Multi-Robot Environment to Linear Programming. LNCS, Springer-Verlag, Volume 3070 / 2004, pp.768-773.
8. Garey M.R. i D.S. Johnson. 1979. Computers and Intractability - A Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA.
9. Gupta N. i Nau D.S. 1992. On the complexity of Blocks-World Planning. Artificial Intelligence, 56 (2-3): 223-254.
10. Howe A.E. i E.Dahlman. 2002. A Critical Assesment of Benchmark Comparison in Planning. Journal of Artificial Intelligence Research, 17: 1-33.
11. Joslin D. i J. Roach. 1989/90. A Theoretical Analysis of Conjuctive-Goal Problems. Artificial Intelligence, 41: 97-106.
12. Klir, G.J., T.A. Folger. 1988. Fuzzy Sets, Uncertainty, and Information. Prentice-Hall International, Inc. USA.
13. McDermott D. i J. Hendler. 1995. Planning: what it is, what it could be, an introduction to the special issue on planning and scheduling. Artificial Intelligence, 76:1-16.
14. Nebel B. i J. Koehler. 1995. Plan reuse versus plan generation: a theoretical and empirical results. Artificial Intelligence, 76:427-454.
15. Nilson N. J. 1980. Principles of Artificial Intelligence. Toga Publishing Company, Palo Alto, California.
16. Popovic, D. i V.P. Bhatkar. 1994. Methods And Tools For Applied Artificial Intelligence. Marcel Dekker, Inc., New York, NY.
17. Rintanen, J. 1999. Constructing Conditional Plans by a Theorem-Prover. Journal of Artificial Intelligence Research, 10: 323-352.
18. Ruspini, E.H., A. Saffiotti, K. Konolige. 1995. Progress in Research on Autonomous Vehicle Motion Planning, [in] Yen, J.; R. Langari; L.A. Zadeh. 1995. Industrial Applications of Fuzzy Logic and Intelligent Systems. IEEE Press. New York.
19. Sierocki I.1997. A Serial Decomposition of Planning Problems. Proc. Fourth International Symposium on Methods and Models in Automation and Robotics. Międzyzdroje, Poland, 1179-1184.
20. Slaney J. i S. Thiebaux. 2001. Block World revisited. Artificial Intelligence, 125:119-153.
21. Slavin T. 1996. Virtual port of call, in: New Scientist, June, 40-43.
22. Smith, D.E. i D.S. Weld. 1998. Conformant Graphplan. Proc. 15th National Conf. on AI.
23. Świerniak, A. i A. Gałuszka. 1999. Betweenness and Indistinguishability in Modeling and Control of Uncertain Systems, Proc. of 18th IASTED Conference Modeling, Identification and Control, Innsbruck, 56-58.
24. Weld, D.S. 1999. Recent Advantages in AI Planning. AI Magazine.
25. Weld, D.S., C.r. Anderson i D.E. Smith. 1998. Extending Graphplan to Handle Uncertainty & Sensing Actions. Proc. 15th National Conf. on AI.
26. Yen, J., R. Langari, L.A. Zadeh. 1995. Industrial Applications of Fuzzy Logic and Intelligent Systems. IEEE Press. New York.

Typ dokumentu

Bibliografia

Identyfikator YADDA

bwmeta1.element.baztech-article-BSL2-0015-0021