Images taken from slides by B Bayazit G. Dudek. J C Latombe and A. Moore Robot motion planning and (a little) Computational Geometry Transfo Topological Methods Configuration space Skeletonization Potential functions Cell-decomposition Methods Non-holonomic Motion Collision Avoidance Additional reading Latombe, Jean-Claude Robot motion planning. Boston: Kluwer Academic Publishers, 1991 E. Rimon and D. E Koditschek Exact Robot Navigation Using Artificial Potential Functions. IEEE Transactions on Robotics and Automation, 8(5): 501518, October 1992 S. Thrun. Learning metric-topological maps for indoor mobile robot navigation. Artificial Intelligence Ssues Statement Compute a collision-free path for a rigid or articulated object (the robot among static obstacles Inputs Geometry of robot and obstacles Kinematics of robot(degrees of freedom) Initial and goal robot configurations(placements) Output Continuous sequence of collision-free robot configurations connecting the initial and goal configurations Number of degrees of freedom? Holonomic vs Non-holonomic? Kinematic Vs. Kino-dynamic? Planning and control architecture Topological VS Metric? Optimality?
Robot Motion Planning and (a little) Computational Geometry Topics: Transforms Topological Methods Configuration space Skeletonization Potential Functions Cell-decomposition Methods Non-holonomic Motion Collision Avoidance Additional reading: Latombe, Jean-Claude. Robot motion planning. Boston : Kluwer Academic Publishers, 1991. E. Rimon and D. E. Koditschek. Exact Robot Navigation Using Artificial Potential Functions. IEEE Transactions on Robotics and Automation, 8(5):501518, October 1992. S. Thrun. Learning metric-topological maps for indoor mobile robot navigation. Artificial Intelligence, 99(1):21-71, 1998. Images taken from slides by B. Bayazit, G. Dudek, J. C. Latombe and A. Moore Issues ● Statement: Compute a collision-free path for a rigid or articulated object (the robot) among static obstacles ● Inputs: – Geometry of robot and obstacles – Kinematics of robot (degrees of freedom) – Initial and goal robot configurations (placements) ● Output: – Continuous sequence of collision-free robot configurations connecting the initial and goal configurations – Number of degrees of freedom? – Holonomic vs. Non-holonomic? – Kinematic vs. Kino-dynamic? – Planning and control architecture – Topological vs. Metric? – Optimality?
Convex Polygons How to reason about this polygon? Convex hu Complexity? Minimum Covering Minimum Partitioning 7 triangles 12 triangles Complexity? Type Rectangl O(NlogN) Complexi Configuration Space The set of legal configurations of the robot Size of C-space depends on degrees of freedom of robot 3-d C-Space e=/2 0=0 A A and B are convex polygons. a is a free-flying object C is represented by parameterizing each configuration q by (xy)∈Rx[0,2 The represented C-obstacle is a volume bounded by patches of ruled surfaces Image adapted from J C Latombe
Convex Polygons How to reason about this polygon? Minimum Covering: 7 triangles Complexity? Convex Hull Complexity? Minimum Partitioning: 12 triangles Complexity? Type Holes Complexity Convex Polygons Y NP-Hard Convex Polygons N O(N3 ) Rectangles Y O(N3/2logN) Rectangles N O(N) Triangulation Y O(NlogN) Configuration Space ● The set of legal configurations of the robot ● Size of C-Space depends on degrees of freedom of robot A and B are convex polygons. A is a free-flying object. C is represented by parameterizing each configuration q by (x,y, ) R2x [0,2 ]. A A B B y y y x x x The represented C-obstacle is a volume bounded by patches of ruled surfaces. 3-d C-Space q= /2 q p q =0 q ∈ p Image adapted from J. C. Latombe
Homogeneous Transforms Convenient representation of rigid body transformations 2-D motion is x|co(△e)cos(△6)△x‖x y|=cos(△)cos(△)y‖y 0 Rotations and translations are now multiplications only 2-D Space: Visibility Graphs qgoal This figure shows the visibility graph G of a simple configuratie clude the edges of CB. The bold line is the shortest path in also in which CB consists of three disconnected c/(Cfree) between qinit and qgoal Image adapted from J C. Latomb What happens in 3-D C-space?
Homogeneous Transforms ● Convenient representation of rigid body transformations ● 2-D motion is ● Rotations and translations are now multiplications only ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ ∆ ∆ ∆ ∆ ∆ ∆ = ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎣ ⎡ 0 0 1 1 cos( ) cos( ) cos( ) cos( ) 1 ' ' y x y x y x θ θ θ θ 2-D Space: Visibility Graphs What happens in 3-D C-space? This figure shows the visibility graph G of a simple configuration space in which CB consists of three disconnected regions. The links of G also include the edges of CB. The bold line is the shortest path in cl(Cfree) between qinit and qgoal . qinit qgoal Image adapted from J. C. Latombe
Voronoi Diagrams Voronoi grap Generalized Voronoi diagram Delaunay Triangulation Skeletonization Grass-fire Transform Evolve discrete points on the polygon curves 个个个个个个个个个个 Shocks occur where wavefronts collide points occur at centres of maximal disks Images adapted from G Dudek Good for motion planning? Not really
Voronoi Diagrams Voronoi Graph Delaunay Triangulation Generalized Voronoi Diagram Skeletonization: Grass-fire Transform Evolve discrete points on the polygon curves “Shocks” occur where wavefronts collide “Critical points” occur at centres of maximal disks Good for motion planning? Not really Images adapted from G.Dudek
Images courtesy of A. Moore Cell-decomposition Exact cell Decomposition pproximate Cell Decomposition Variable-resolution Approximate Cell decomposition Images courtesy of B Bayazit Potential functions Khatib 1986 Koditschek 1998 } Attractive Potential Repulsive Potential Combined Potential for goals for obstacles Field Move along force: F(x)=VUatt(x)-VUren(x)
Cell-decomposition Approximate Cell Decomposition Variable-resolution Approximate Cell Decomposition Exact Cell Decomposition Images courtesy of A. Moore Potential Functions Attractive Potential for goals Repulsive Potential for obstacles Combined Potential Field Move along force: F(x) = ∇Uatt(x)-∇Urep(x) Khatib 1986 Latombe 1991 Koditschek 1998 Images courtesy of B. Bayazit
Numerical Navigation mages courey ot B Bay Functions 1 put a grid GC on C-space 2) label each grid point in GC with a 0 if it is in Cfree and 1 otherwise 3)use L1 distance(Manhattan distance)to xgoal as navigation function U 4)compute L1 distance from xinit to aoa by wavefront propagation a) set U(ooa=0 b) set U(x)=1 for each 1-neighbor of the goal c)set U(x)=2 for each 1-neighbor of nodes labelled in(b) d)loop until labeled Xinit or no more nodes to label Non-holonomic motion 1)TWo-phase planning Compute collision-free path ignoring nonholonomic constraints Transform this path into a nonholonomic one Efficient, but possible only if robot is"controllable Plus need to have"good"set of maneuvers 2)Direct planning Build a tree of milestones until one is close enough to the goal (deterministic or randomized Robot need not be controllable orks in high-dimensional C-spaces
Numerical Navigation Functions 1) put a grid GC on C-space 2) label each grid point in GC with a 0 if it is in Cfree and 1 otherwise 3) use L1 distance (Manhattan distance) to xgoal as navigation function U 4) compute L1 distance from xinit to xgoal by wavefront propagation a) set U(xgoal) = 0 b) set U(x’) = 1 for each 1-neighbor of the goal c) set U(x’) = 2 for each 1-neighbor of nodes labelled in (b) d) loop until labeled xinit or no more nodes to label Images courtesy of B. Bayazit Non-holonomic Motion 1) Two-phase planning: Compute collision-free path ignoring nonholonomic constraints • Transform this path into a nonholonomic one • Efficient, but possible only if robot is “controllable” • Plus need to have “good” set of maneuvers 2) Direct planning: Build a tree of milestones until one is close enough to the goal (deterministic or randomized) • Robot need not be controllable • Works in high-dimensional c-spaces
Ackerman steering example 2 constraints(front and rear wheels) 2 inputs(steering and gas pedal) ·4 states φ W=[-sin8 cos80 oI Intuition tells us g,= I which means the steering depends only on g now we want g2 to tell us the direction we would go for a fixed o tanφ Collision avoidance Dynamic Window Fox et al. 1996 Vector-Field Histogram Borenstein et al. 1991. 1998 Lane-Curvature Simmons and Ko. 1998 Local gradient Descent Konolige 2002
θ φ y x l Ackerman steering example ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = ⋅ = = − + + = − 0 tan 1 sin cos , 1 0 0 0 0 [ sin( ) cos( ) cos 0] [ sin cos 0 0] 1 2 1 φ θ θ φ φ θ φ θ φ φ θ θ l g w q w l w 2 2 1 g now we want g to tell us the direction we would go for a fixed Intuition tells us which means the steering depends only on & & •2 constraints (front and rear wheels) •2 inputs (steering and gas pedal) • 4 states ⎥ ⎥ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎢ ⎢ ⎣ ⎡ = φ θ y x q Collision Avoidance ● Dynamic Window ● Fox et al., 1996 ● Vector-Field Histogram ● Borenstein et al., 1991, 1998 ● Lane-Curvature ● Simmons and Ko, 1998 ● Local Gradient Descent ● Konolige 2002
What you should know Practical above 2 or 3-d? Practical above 8-d? Fast to compute? Gives optimal? Spots impossibilities? Easy to implement? Useful for real robots Example questions Here's a motion-planning problem. What representation would you use and why? Here's a motion-planning problem. What would you use to solve it and why? Can you use one motion-planning algorithm to improve the performance of a second algorithm?
What you should know Practical above 2 or 3-d? Practical above 8-d? Fast to compute? Gives optimal? Spots impossibilities? Easy to implement? Useful for real robots? Potential/Navigation Fields Voron Dia oi grams Visibility Graphs Cel D l ecomposition Example questions ● Here’s a motion-planning problem. What representation would you use and why? ● Here’s a motion-planning problem. What would you use to solve it and why? ● Can you use one motion-planning algorithm to improve the performance of a second algorithm?
