Optimization-based approach to path planning for closed chain robot systems

Wojciech Szynkiewicz ; Jacek Błaszczyk

International Journal of Applied Mathematics and Computer Science, Tome 21 (2011), p. 659-670 / Harvested from The Polish Digital Mathematics Library

Résumé

An application of advanced optimization techniques to solve the path planning problem for closed chain robot systems is proposed. The approach to path planning is formulated as a “quasi-dynamic” NonLinear Programming (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.

Détail

Publié le : 2011-01-01

Zbl 1283.93206

EUDML-ID : urn:eudml:doc:208078

Bibliographie

[000] Abbasi-Yadkori, Y., Modayil, J. and Szepesvari, C. (2010). Extending rapidly-exploring random trees for asymptotically optimal anytime motion planning, IEEE/RSJ International Conference on Intelligent Robots and Systems, Taipei, Taiwan, pp. 127-132.

[001] Asfour, T., Gyarfas, F., Azad, P. and Dillmann, R. (2006). Imitation learning of dual-arm manipulation tasks in humanoid robots, IEEE/RAS International Conference on Humanoid Robots (Humanoids 2006), Genoa, Italy, pp. 40-47.

[002] Bell, B.M. and Burke, J.V. (2008). Algorithmic differentiation of implicit functions and optimal values, in C.H. Bischof, H.M. Bücker, P.D. Hovland, U. Naumann and J. Utke (Eds.), Advances in Automatic Differentiation, Springer, Berlin/Heidelberg, pp. 67-77. | Zbl 1152.65434

[003] Benson, H.Y., Shanno, D.F. and Vanderbei, R.J. (2001). Interiorpoint methods for nonconvex nonlinear programming: Filter methods and merit functions, Technical Report ORFE00-06, Operations Research and Financial Engineering, Princeton University, Princeton, NJ. | Zbl 1022.90017

[004] Benson, H.Y., Shanno, D.F. and Vanderbei, R.J. (2002). A comparative study of large-scale nonlinear optimization algorithms, Technical Report ORFE-01-04, Operations Research and Financial Engineering, Princeton University, Princeton, NJ. | Zbl 1066.90138

[005] Błaszczyk, J., Karbowski, A. and Malinowski, K. (2007). 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, DOI: 10.2478/v10006-0070043-y. | Zbl 1234.90022

[006] Błaszczyk, J.P. (2007). Object Library of Algorithms for Dynamic Optimization: A Study on Effectiveness of Sequential Quadratic Programming and Nonlinear Interior Point Methods, Ph.D. thesis, Warsaw University of Technology, Warsaw, (in Polish).

[007] Byrd, R.H., Gilbert, J.C. and Nocedal, J. (2000). A trust region method based on interior point techniques for nonlinear programming, Mathematical Programming 89(1): 149-185. | Zbl 1033.90152

[008] Byrd, R.H., Hribar, M.E. and Nocedal, J. (1999). An interior point algorithm for large scale nonlinear programming, SIAM Journal on Optimization 9(4): 877-900. | Zbl 0957.65057

[009] Canny, J. (1988). The Complexity of Robot Motion Planning, MIT Press, Cambridge, MA. | Zbl 0668.14016

[010] Cortés, J., Siméon, T. and Laumond, J.-P. (2002). A random loop generator for planning the motions of closed kinematic chains using PRM methods, IEEE International Conference on Robotics and Automation ICRA, Washington, DC, USA, pp. 2141-2146.

[011] Daniel, J. (1971). Approximate Minimisation of Functionals, Prentice Hall, Englewood Cliffs, NJ.

[012] de Boor, C. (1978). Practical Guide to Splines, Springer, New York, NY/Heidelberg. | Zbl 0406.41003

[013] Dolan, E.D. and Moré, J.J. (2002). Benchmarking optimization software with performance profiles, Mathematical Programming 91(2): 201-213. | Zbl 1049.90004

[014] Fiacco, A.V. and McCormick, G.P. (1968). Nonlinear Programming: Sequential Unconstrained Minimization Techniques, John Wiley and Sons, New York, NY/London. | Zbl 0193.18805

[015] Fiser, A., Do, R. and Sali, A. (2000). Modeling of loops in protein structure, Protein Science 9(9): 1753-1773.

[016] Fletcher, R. and Leyffer, S. (2002). Nonlinear programming without a penalty function, Mathematical Programming 91(2): 239-269. | Zbl 1049.90088

[017] Haegele, M., Nilsson, K. and Pires, J.N. (2008). Springer Handbook of Robotics, Springer, Berlin/Heidelberg.

[018] Han, L. and Amato, N. (2000). A kinematics-based probabilistic roadmap method for closed chain systems, Workshop on Algoritmic Foundations of Robotics, Dartmouth, Hanover, NH, USA, pp. 233-245. | Zbl 1015.70007

[019] Han, L., Rudolph, L., Blumenthal, J. and Valodzin, I. (2006). Stratified deformation space and path planning for a planar closed chain with revolute joints, in S. Akella, N. Amato, W. Huang and B. Mishra (Eds.), International Workshop on Algorithmic Foundations of Robotics WAFR, Springer Tracts in Advanced Robotics, Vol. 47, Springer, New York, NY, pp. 235-250. | Zbl 1188.93064

[020] Kallmann, M., Aubel, A., Abaci, T. and Thalmann, D. (2003). Planning collision-free reaching motions for interactive object manipulation and grasping, Eurographics 22(3): 313-322.

[021] Kanehiro, F., Lamiraux, F., Kanoun, O., Yoshida, E. and Laumond, J.-P. (2008). A local collision avoidance method for non-strictly convex polyhedra, Proceedings of Robotics: Science and Systems (RSS) IV, Zurich, Switzerland, pp. 151-158.

[022] Kavraki, L.E., Svestka, P., Latombe, J.-C. and Overmars, M.H. (1996). Probabilistic roadmaps for path planning in highdimensional configuration spaces, IEEE Transactions on Robotics and Automation 12(4): 566-580.

[023] Kuffner, J.J. and LaValle, S.M. (2000). RRT-connect: An efficient approach to single-query path planning, IEEE International Conference on Robotics and Automation, San Francisco, CA, USA, pp. 995-1001.

[024] Latombe, J.-C. (1991). Robot Motion Planning, Kluwer, Boston, MA.

[025] LaValle, S. (2006). Planning Algorithms, Cambridge University Press, Cambridge. | Zbl 1100.68108

[026] Liu, G. and Trinkle, J. (2005). Complete path planning for planar closed chains among point obstacles, Proceedings of Robotics: Science and Systems (RSS) I, Cambridge, MA, USA, pp. 33-40.

[027] Merlet, J. (2000). Parallel Robots, Kluwer, Dordrecht. | Zbl 0983.70002

[028] Morales, J.L., Nocedal, J., Waltz, R.A., Liu, G. and Goux, J.-P. (2001). Assessing the potential of interior methods for nonlinear optimization, Technical Report OTC 2001/4, Optimization Technology Center, Northwestern University, Evanston, IL. | Zbl 1062.65063

[029] Ratliff, N., Zucker, M., Bagnell, J.A. and Srinivasa, S. (2009). CHOMP: Gradient optimization techniques for efficient motion planning, IEEE International Conference on Robotics and Automation (ICRA), Kobe, Japan, pp. 489-494.

[030] Szynkiewicz, W. (2003). Motion planning for multi-robot systems with closed kinematic chains, 9th IEEE International Conference on Methods and Models in Automation and Robotics, Międzyzdroje, Poland, pp. 779-786.

[031] Szynkiewicz, W. and Gosiewski, A. (1995). Motion space analysis and trajectory planning for dual-arm system, 2nd International Symposium on Methods and Models in Automation and Robotics, Międzyzdroje, Poland, pp. 503-510.

[032] Tang, X., Thomas, S. and Amato, N. (2007). Planning with reachable distances: Fast enforcement of closure constraints, IEEE International Conference on Robotics and Automation ICRA, Rome, Italy, pp. 2694-2699.

[033] Tits, A.L., Wächter, A., Bakhtiari, S., Urban, T.J. and Lawrence, C. (2002). A primal-dual interior-point method for nonlinear programming with strong global and local convergence properties, Technical Report TR 2002-29, Institute for Systems Research, University of Maryland, College Park, MD. | Zbl 1075.90078

[034] Trinkle, J. and Milgram, R. (2002). Complete path planning for closed kinematic chains with spherical joints, International Journal of Robotics Research 21(9): 773-789.

[035] Ulbrich, M., Ulbrich, S. and Vicente, L.N. (2004). A globally convergent primal-dual interior-point filter method for nonlinear programming, Mathematical Programming 100(2): 379-410. | Zbl 1070.90110

[036] Vanderbei, R.J. and Shanno, D.F. (1997). An interior-point algorithm for non-convex nonlinear programming, Technical Report SOR-97-21, Statistics and Operations Research, Princeton University, Princeton, NJ.

[037] Wächter, A. (2002). An Interior Point Algorithm for Large-Scale Nonlinear Optimization with Applications in Process Engineering, Ph.D. dissertation, Carnegie Mellon University, Pittsburgh, PA.

[038] Wächter, A. and Biegler, L.T. (2000). Failure of global convergence for a class of interior point methods for nonlinear programming, Mathematical Programming 88(3): 565-574. | Zbl 0963.65063

[039] Wächter, A. and Biegler, L.T. (2005). Line search filter methods for nonlinear programming: Motivation and global convergence, SIAM Journal on Optimization 16(1): 1-31. | Zbl 1114.90128

[040] Wächter, A. and Biegler, L.T. (2006). On the implementation of a primal-dual interior-point filter line-search algorithm for large-scale nonlinear programming, Mathematical Programming 106(1): 25-57. | Zbl 1134.90542

[041] Waltz, R.A. and Plantenga, T. (2006). KNITRO 5.0 User's Manual, Ziena Optimization, Inc., http://www.ziena.com/docs/knitroman.pdf.

[042] Yakey, J., LaValle, S. and Kavraki, L. (2001). Randomized path planning for linkages with closed kineamtic chains, IEEE Transactions on Robotics and Automation 17(6): 951-958.

[043] Yershova, A. and LaValle, S. (2009). Motion planning for highly constrained spaces, in K.R. Kozłowski (Ed.) Robot Motion and Control 2009, Springer, Berlin/Heidelberg, pp. 297-306.

[044] Zefran, M. and Kumar, V. (1997). A variational calculus framework for motion planning, IEEE International Conference on Robotics and Automation ICRA, Albuquerque, NM, USA, pp. 415-420.

[045] Zhang, J. and Knoll, A. (1995). An enhanced optimization approach for generating smooth robot trajectories in the presence of obstacles, Proceedings of the European Chinese Automation Conference, London, UK, pp. 263-268.

[046] Zieliński, C. and Winiarski, T. (2010). Motion generation in the MRROC++ robot programming framework, International Journal of Robotics Research 29(4): 386-413.