Advanced Search
Article Contents
Article Contents

Path planning and collision avoidance for robots

Abstract Related Papers Cited by
  • An optimal control problem to find the fastest collision-free trajectory of a robot surrounded by obstacles is presented. The collision avoidance is based on linear programming arguments and expressed as state constraints. The optimal control problem is solved with a sequential programming method. In order to decrease the number of unknowns and constraints a backface culling active set strategy is added to the resolution technique.
    Mathematics Subject Classification: Primary: 49J15, 49M25, 49N90; Secondary: 90C30.


    \begin{equation} \\ \end{equation}
  • [1]

    L. D. Berkovitz, "Convexity and Optimization in $\mathbbR^n$," John Wiley Sons, New York, 2001.


    J. T. Betts, "Practical Methods for Optimal Control using Nonlinear Programming," Advances in Design and Control, volume 3, SIAM, Philadelphia, 2001.


    J. E. Bobrow, Optimal robot path planning using the minimum-time criterion, IEEE J. Robotics and Automation, 4 (1988), 443-450.doi: 10.1109/56.811.


    J. V. Burke and S. P. Han, A robust sequential quadratic programming method, Mathematical Programming, 43 (1989), 277-303.doi: 10.1007/BF01582294.


    F. L. Chernousko, Optimization in control of robots, Computational Optimal Control, 115 (1994), 19-28.


    M. Diehl, H. G. Bock, H. Diedam and P. Wieber, Fast direct multiple shooting algorithms for optimal robot control, Fast Motions in Biomechanics and Robotics: Optimization and Feedback Control, (2005), 65-94.


    S. Dubowsky, M. A. Norris and Z. Shiller, Time optimal trajectory planning for robotic manipulators with obstacle avoidance: a CAD approach , in "Proc. of IEEE Int. Conf. on Robotics and Automation," (1989), 1906-1912.


    R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269.doi: 10.1007/s101070100244.


    R. Fletcher, S. Leyffer and P. Toint, On the global convergence of a filter-SQP algorithm, SIAM Journal on Optimization, 13 (2002), 44-59.doi: 10.1137/S105262340038081X.


    J. D. Foley, A. van Dam, S. T. Feiner and J. F. Hughes, "Computer Graphics - Principles and Practice," Addison Wesley, 1990.


    M. Gerdts, "Numerische Methoden Optimaler Steuerprozesse Mit Differential-Algebraischen Gleichungssystemen Höheren Indexes und ihre Anwendungen in der Kraftfahrzeugsimulation und Mechanik," Bayreuther Mathematische Schriften, 61 (2001).


    M. Gerdts, Direct shooting method for the numerical solution of higher index DAE optimal control problems, Journal of Optimization Theory and Applications, 117 (2003), 267-294.doi: 10.1023/A:1023679622905.


    M. Gerdts and F. Lempio, "Mathematische Optimierungsverfahren des Operations Research," De Gruyter, Berlin, 2011.doi: 10.1515/9783110249989.


    E. M. Gertz and S. J. Wright, Object-oriented software for quadratic programming, ACM Transactions on Mathematical Software, 29 (2003), 58-81.doi: 10.1145/641876.641880.


    E. G. Gilbert and S. M. Hong, A new algorithm for detecting the collision of moving objects, in "IEEE Proc. Int. Conf. on Robotics and Automation," 1 (1989), 8-14.


    E. G. Gilbert and D. W. Johnson, Distance functions and their application to robot path planning in the presence of obstacles, IEEE Journal of Robotics and Automation, 1 (1985), 21-30.


    P. E. Gill and W. Murray, Numerically stable methods for quadratic programming, Mathematical Programming, 14 (1978), 349-372.doi: 10.1007/BF01588976.


    P. E. Gill, W. Murray, M. A. Saunders and M. H. Wright, Inertia-controlling methods for general quadratic programming, SIAM Review, 33 (1991), 1-36.doi: 10.1137/1033001.


    D. Goldfarb and A. Idnani, A numerically stable dual method for solving strictly convex quadratic programs, Mathematical Programming, 27 (1983), 1-33.doi: 10.1007/BF02591962.


    K. Gupta and A. P. del Pobil, "Practical Motion Planning in Robotics," Wiley, New York, 1998.


    M. E. Kahn and B. Roth, The near-minimum-time control of open-loop articulated Kinematic chains, J. of Dynamic Sys., Meas. and Contr., 93 (1971), 164-172.doi: 10.1115/1.3426492.


    S. M. LaValle, "Planning Algorithms," Cambridge University Press, Cambridge, 2006.doi: 10.1017/CBO9780511546877.


    M. Pérez-Francisco, A. P. del Pobil and B. Martinez-Salvador, Parallel collision detection between moving robots for practical motion planning, Journal of Robotic Systems, 18 (2001), 487-506.doi: 10.1002/rob.1039.


    F. Pfeiffer, "Einführung in die Dynamik," B. G. Teubner, Stuttgart, 1992.


    M. J. D. Powell, A fast algorithm for nonlinearily constrained optimization calculation, in "Lecture Notes in Mathematics, Numerical Analysis"(ed G. A. Watson), vol. 630, Springer, Berlin-Heidelberg-New York, 1978.


    S. Redon, A. Kheddar and S. Coquillart, Hierarchical back-face culling for collision detection, Proceedings of IEEE International Conference on Robotics and Automation, (2002).


    K. Schittkowski, The nonlinear programming method of Wilson, Han and Powell with an augmented Lagrangean type line search function. Part 1: Convergence analysis, Part 2: An efficient implementation with linear least squares subproblems, Numerische Mathematik, 38 (1981), 83-114, 115-127.


    K. Schittkowski, On the convergence of a sequential quadratic programming method with an augmented Lagrangean line search function, Mathematische Operationsforschung und Statistik, Series Optimization, 14 (1983), 197-216.


    Peter Spellucci, "Numerische Verfahren der Nichtlinearen Optimierung," Birkhäuser, Basel, 1993.


    R. J. Vanderbei, "Linear programming, Foundations and Extensions," International Series in Operations Research & Management Science, 37, 2001.


    G. Vaněček Jr., Back-face culling applied to collision detection of polyhedra, Journal of Visualization and Computer Animation, 5 (1994), 55-63.doi: 10.1002/vis.4340050105.


    O. von Stryk and M. Schlemmer, Optimal control of the industrial robot manutec r3, Computational Optimal Control, 115 (1994), 367-382.

  • 加载中

Article Metrics

HTML views() PDF downloads(320) Cited by(0)

Access History



    DownLoad:  Full-Size Img  PowerPoint