Optymalizacja w zastosowaniu do planowania ruchu ściśle współpracujących robotów

pol Article in Polish DOI:

Wojciech Szynkiewicz *, Jacek Błaszczyk **, Krzysztof Malinowski * * Instytut Automatyki i Informatyki Stosowanej Politechniki Warszawskiej ** Naukowa i Akademicka Sieć Komputerowa NASK

Download Article

Streszczenie

W artykule omówiono wykorzystanie zaawansowanych technik optymalizacji do rozwiązywania zadań planowania ścieżek ruchu dla ściśle współpracujących robotów. Zadanie planowania ścieżki jest formułowane jako problem minimalizacji warunkowej funkcjonału, a następnie jest sprowadzane do zadania programowania nieliniowego (NLP). Do numerycznego rozwiązania zadania NLP wykorzystuje się solwer IPOPT oparty na prymalno-dualnej metodzie punktu wewnętrznego dla zadań nieliniowych, będącej obecnie jedną z wiodących technik optymalizacji nieliniowej dla zadań wielkiej skali.

Optimization in motion planning for tightly cooperating robots

Abstract

Application of advanced optimization techniques to solve the path planning problem for tightly cooperating robots is discussed in this paper. The approach to path planning is formulated as a “quasi-dynamic” nonlinear optimization (NLP) problem with equality and inequality constraints in terms of the joint variables. The essence of the method is to find joint paths which satisfy the given constraints and minimize the proposed performance index. For numerical solution of the NLP problem the IPOPT solver is used, which implements a nonlinear primal-dual interior-point method one of the leading techniques for large-scale nonlinear optimization.

Bibliography

  1. B. M. Bell, J. V. Burke. Algorithmic Differentiation of Implicit Functions and Optimal Values. In Ch. H. Bischof, H. M. Bücker, P. D. Hovland, U. Naumann, J. Utke, editors, Advances in Automatic Differentiation, str. 67–77. Springer, 2008.
  2. H. Y. Benson, D. F. Shanno, R. J. Vanderbei. A Comparative Study of Large-Scale Nonlinear Optimization Algorithms. Raport instytutowy ORFE-01-04, Operations Research and Financial Engineering, Princeton University, 2002.
  3. H. Y. Benson, D. F. Shanno, R. J. Vanderbei. Interior-Point Methods for Nonconvex Nonlinear Programming: Filter Methods and Merit Functions. Raport instytutowy ORFE-00-06, Operations Research and Financial Engineering, Princeton University, 2001.
  4. C. de Boor. Practical guide to splines. Springer, New York, Heidelberg, 1978.
  5. R. H. Byrd, J. Ch. Gilbert, J. Nocedal. A Trust Region Method Based on Interior Point Techniques for Nonlinear Programming. Mathematical Programming, 89:149–185, 2000.
  6. R. H. Byrd, M. E. Hribar, J. Nocedal. An Interior Point Algorithm for Large Scale Nonlinear Programming. SIAM Journal on Optimization, 9(4):877–900, 1999.
  7. J. Bł aszczyk, A. Karbowski, K. Malinowski. Object Library of Algorithms for Dynamic Optimization Problems; Benchmarking SQP and Nonlinear Interior Point Methods. International Journal of Applied Mathematics and Computer Science, 17(4):515–537, 2007.
  8. J. P. Błaszczyk. Obiektowa biblioteka algorytmów optymalizacji dynamicznej; badanie efektywności metod sekwencyjnego programowania kwadratowego i punktu wewnętrznego dla zadań nieliniowych. Praca doktorska, Politechnika Warszawska, Wydzia ł Elektroniki i Technik Informacyjnych, Instytut Automatyki i Informatyki Stosowanej, Warszawa, 2007. Rozprawa doktorska w dyscyplinie Automatyka i Robotyka.
  9. J. Cortés, T. Siméon, J.-P. Laumond. A Random Loop Generator for Planning the Motions of Closed Kinematic Chains using PRM Methods. IEEE International Conference on Robotics and Automation ICRA, str. 2141–2146, 2002. IEEE.
  10. J.W. Daniel. Approximate minimisation of functionals. Prentice Hall, Englewood Cliffs, N.J., 1971.
  11. E. D. Dolan, J. J. Moré. Benchmarking Optimization Software with Performance Profiles. Mathematical Programming, 91(2):201–213, 2002.
  12. A. V. Fiacco, G. P. McCormick. Nonlinear Programming: Sequential Unconstrained Minimization Techniques. John Wiley and Sons, New York/London, 1968.
  13. A. Fiser, R.K. Do, A. Sali. Modeling of loops in protein structure. Protein Science, 9(9):1753–1773, 2000.
  14. R. Fletcher, S. Leyffer. Nonlinear Programming without a Penalty Function. Mathematical Programming, 91(2):239–269, 2002.
  15. M. Galicki. Wybrane metody planowania optymlanych trajektorii robotów manipulacyjnych. WNT, 2000.
  16. I. M. Gelfand, S.W. Fomin. Rachunek wariacyjny. PWN, Warszawa, 1979.
  17. L. Han, N. Amato. A kinematics-based probabilistic roadmap method for closed chain systems. Workshop on Algoritmic Foundations of Robotics, str. 233–245, 2000.
  18. M. Kallmann, A. Aubel, T. Abaci, D. Thalmann. Planning collision-free reaching motions for interactive object manipulation and grasping. Eurographics, 22:313–322, 2003.
  19. L. E. Kavraki, P. Svestka, J.-C. Latombe, M. H. Overmars. Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation, 12(4):566–580, 1996.
  20. K. Kozłowski, P. Dutkiewicz, W. Wróblewski. Modelowanie i sterowanie robotów. Wydawnictwo Naukowe PWN, Warszawa, 2003.
  21. J. J. Kuffner, S. M. LaValle. RRT-Connect: An efficient approach to single-query path planning. IEEE International Conference on Robotics and Automation, str. 995–1001, 2000.
  22. J.-C. Latombe. Robot motion planning. Kluwer, Boston, MA, 1991.
  23. S. M. LaValle. Planning Algorithms. Cambridge University Press, Cambridge, U.K., 2006.
  24. J.P. Merlet. Parallel Robots. Kluwer, Dordrecht, 2000.
  25. J. L. Morales, J. Nocedal, R. A. Waltz, G. Liu, J.-P. Goux. Assessing the Potential of Interior Methods for Nonlinear Optimization. Raport instytytowy OTC 2001/4, Optimization Technology Center of Northwestern University, 2001.
  26. R. M. Murray, Z. Li, S. S. Sastry. A Mathematical Introduction to Robotic Manipulation. CRC Press, 1994.
  27. T. Siméon, J. -P. Laumond, J. Cortés, A. Sahbani. Manipulation planning with probabilistic roadmaps. The International Journal of Robotics Research, 23(7-8):729–746, 2004.
  28. W. Szynkiewicz. Motion Planning for Multi-Robot Systems with Closed Kinematic Chains. 9th IEEE Int. Conf. on Methods and Models in Automation and Robotics, str. 779–786, Międzyzdroje, 2003.
  29. K. Tchoń , I. Dulęba, A. Mazur, R. Hossa, R. Muszyński. Manipulatory i roboty mobilne. Modele, planowanie ruchu, sterowanie. Akademicka Oficyna Wydawnicza PLJ, Warszawa, 2000.
  30. A. L. Tits, A. Wächter, S. Bakhtiari, T. J. Urban, C. T. Lawrence. A Primal-Dual Interior-Point Method for Nonlinear Programming with Strong Global and Local Convergence Properties. Raport instytutowy TR 2002-29, Institute for Systems Research, University of Maryland, 2002.
  31. J. C. Trinkle, R. J. Milgram. Complete path planning for closed kinematic chains with spherical joints. International Journal of Robotics Research, 21(9):773–789, 2002.
  32. M. Ulbrich, S. Ulbrich, L. N. Vicente. A Globally Convergent Primal-Dual Interior-Point Filter Method for Nonlinear Programming. Mathematical Programming, 100(2):379–410, 2004.
  33. R. J. Vanderbei, D. F. Shanno. An Interior-Point Algorithm for Non-convex Nonlinear Programming. Raport instytutowy SOR-97-21, Statistics and Operations Research, Princeton University, 1997.
  34. A. Wächter. An Interior Point Algorithm for Large-Scale Nonlinear Optimization with Applications in Process Engineering. Ph. D. Dissertation, Department of Chemical Engineering, Carnegie Mellon University, Pittsburgh, PA, USA, 2002.
  35. A. Wächter, L. T. Biegler. Failure of Global Convergence for a Class of Interior Point Methods for Nonlinear Programming. Mathematical Programming, 88(3): 565–574, 2000.
  36. A. Wächter, L. T. Biegler. Line Search Filter Methods for Nonlinear Programming: Motivation and Global Convergence. SIAM Journal on Optimization, 16(1): 1–31, 2005.
  37. A. Wächter, L. T. Biegler. On the Implementation of a Primal-Dual Interior-Point Filter Line-Search Algorithm for Large-Scale Nonlinear Programming. Mathematical Programming, 106(1):25–57, 2006.
  38. R. A. Waltz, T. Plantenga. KNITRO 5.0 User's Manual. 2006.
  39. W. Wedemeyer, H. Scheraga. Exact analytical loop closure in proteins using polynomial equations. Journal of Computational Chemistry, 20(8):819–844, 1999.
  40. J. H. Yakey, S. M. LaValle, L. E. Kavraki. Randomized path planning for linkages with closed kineamtic chains. IEEE Transactions on Robotics and Automation, 17(6):951–958, 2001.
  41. T. Zielińska. Maszyny kroczące. PWN, 2003.
  42. C. Zieliński, W. Szynkiewicz, T. Winiarski, T. Kornuta. MRROC++ Based System Description. Raport instytutowy 06-9, IAIS, Warsaw, 2006.