Collision Detection and Path Planning
slides are from different sources, e.g. C.J. Taylor (UPenn), J. Latombe (Stanford), D. ),…
Motion-Planning Framework
Copyright By PowCoder代写 加微信 powcoder
Continuous representation
Discretization
Graph searching
(Search: blind, best-first, informed) [e.g., Grassfire, Dijkstra’s, A*]
Recap: Planning Path through Configuration Space
• In this setting the task of planning a path for our robot correspond to planning a trajectory through configuration space from the starting configuration to the end configuration.
• Polygonalobstaclesareconvenienttowork with because they provide an explicit description of the configuration space obstacles.
• Oftentimeswedonothavethisluxuryandthe obstacles are instead defined implicitly by a collision function.
Collision Detection Function
• Let x denote the coordinates of a point in configuration space.
• CollisionCheck(x)shouldreturn
• 0ifxisinfreespaceand
• 1ifxresultsinacollisionwiththeobstacles.
Collision Detection
CollisionCheck (x) = 0
Collision Detection
CollisionCheck (x) = 1
Collision Detection
Consider the robot and obstacles as collection of triangles.
• Deciding whether the robot and the obstacle intersect is now a matter of determining whether any of the robot triangles overlap any of the obstacle triangles.
Testing Triangles for Overlap
• Here we can make use of the fact that triangles are convex polygons.
• In this circumstance it means that we can test whether two triangles intersect by checking all of the sides on both triangles and testing whether that side acts as a separating line where all of the points from one triangle lie on one side and all those from the other lie on the opposite side.
• If you can find such a separating edge you have proved that the triangles don’t intersect, if not you can conclude that they do.
Testing Triangles for Overlap
Separating Edge -> No Overlap
No Separating Edge -> Overlap
• Thisideaoffindingaseparatinglineorplane actually generalizes to higher dimension. For instance if you have convex polygons in three dimensions like boxes or pyramids you can check for collision by testing if any of the faces act as separating planes.
• Inthecasesthatwehaveconsideredsofar the robots and the obstacles are basically composed of simple polygons, so to test for collision we first transform the robot according to the configuration space parameters and then test for collision between the robot components and the obstacles.
Collision Checking
CollisionCheck (x) = 0
Collision Checking
CollisionCheck (x) = 1
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com