On-Line Obstacle Avoidance at High Speeds
This paper presents an efficient algorithm for on-line obstacle avoidance that accounts for robot dynamics and actuator constraints. The robot trajectory (path and speed) is generated on-line by avoiding obstacles, optimally, one at a time. The trajectory
- PDF / 422,340 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 12 Downloads / 201 Views
1
Introduction
This paper presents an algorithm for obstacle avoidance at high speeds. It generates trajectories that satisfy robot dynamics and actuator constraints, and are guaranteed to reach the goal from any admissible state. The incremental generation of the trajectories and the relatively low computational requirements at each step make it suitable for on-line applications. The time-optimal control problem for robotic manipulators has been addressed in numerous studies over the past twenty years (e.g. Shiller and Dubowsky (1989)). This problem is inherently off-line, as it requires the solution of a two point boundary value problem. The typically nonlinear and coupled robot dynamics make such solutions computationally extensive. Adding obstacles makes the computational challenge even harder. Recent works have addressed the problem of on-line trajectory planning and high speed obstacle avoidance, using sampling-based methods (Kuwata et al., 2008; Knepper and Mason, 2009), and mixed-integer linear programming (MILP) (Vitus et al., 2008). Sampling-based methods are usually inefficient for tightly spaced environments with narrow passages. The MILP based method is computationally intensive and hence limited to very simple cases. The on-line algorithm presented in this paper was motivated by the observation that the effect of an obstacle on the value function (the global costto-go function) is local. Focusing on one obstacle, while ignoring the rest, V. Padois, P. Bidaud, O. Khatib (Eds.), Romansy 19 – Robot Design, Dynamics and Control, CISM International Centre for Mechanical Sciences, DOI 10.1007/978-3-7091-1379-0_35, © CISM, Udine 2013
284
Z. Shiller and S. Sharma
effectively approximates the multi-obstacle problem of avoiding m obstacles by m simpler sub-problems of avoiding one obstacle each. The trajectory is thus generated on-line, incrementally, one step at a time, requiring a low computational effort at each step relative to the original, inherently off-line, problem. Convergence to the goal is guaranteed, subject to a few assumptions, by selecting at each step the obstacle with the highest cost. When those assumptions are not satisfied, the original problem is subdivided by intermediate goals to smaller problems for which the assumptions are satisfied. The algorithm is demonstrated in a numerical example for a planar point robot moving among many (70) tightly spaced circular obstacles.
2
Problem Formulation
We wish to minimize the cost function ∫ tf 1 dt, min u
(1)
0
subject to system dynamics x ¨ = f (x, u) ; x, u ∈ Rn ,
(2)
where x ∈ Rn is the vector of axis displacements, and u ∈ Rn is a vector of actuator efforts, subject to the actuator constraints, obstacle constraints and the boundary constraints: |ui | ≤ 1 ,
g(x) ≥ 0 ; x(0) = x0 ; x(tf ) = xf ;
i ∈ {1, · · · , n}
g∈R x(0) ˙ = x˙ 0 ; x(t ˙ f ) = x˙ f m
(3) (4) (5)
where tf is free, and m is the number of obstacles. We assume that the obstacles (4) do not overlap with each other and with the goal xf . Problem (1) is difficult to solve bec
Data Loading...
