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