Motion Planning CS 6370
Popular in Course
Popular in ComputerScienence
Marian Kertzmann DVM
verified elite notetaker
This 4 page Class Notes was uploaded by Marian Kertzmann DVM on Monday October 26, 2015. The Class Notes belongs to CS 6370 at University of Utah taught by Staff in Fall. Since its upload, it has received 12 views. For similar materials see /class/229996/cs-6370-university-of-utah in ComputerScienence at University of Utah.
Reviews for Motion Planning
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/26/15
Geometric Computations for Motion Planning David E Johnson I INTRODUCTION Path planning done a line that is without an ongoing stream of sensor data to interpret must have a computer representation of the environment and robot Since one View of path planning is to move between a start and goal con guration without hitting the environment a corresponding goal in the simulation is for the virtual robot model to move without callisian with any of the environment models As will be seen later along with collision tests distance measures between the robot model and environment model are also useful in of ine planners Therefore it is worth discussing what is meant by collision and distance measures and learning some simple ideas for computing these on modeling primitives such as lines and circles A Callisian and Distance When you think of a collision you probably think of some portion of two objects occupying or trying to occupy the same location in space Many commonsense de nitions are more precisely de ned using sets and set notation The collision between two sets can be de ned as C abaeAbeB where A and B are two sets representing objects in the environment and C is the collision set If C is empty then there is no collision The distance between two sets is more complicated In general when distance is used as a measure between two objects what is really meant is the minimum distance between the two obejcts as there are any number of distances between different parts of the objects So minDistA B mindista b LEA beB I Metrics and Narms However we have not yet de ned what the distance between two elements or points in the sets is so this de nition is not yet complete Distance is a function de ned as a metric on a set M where dist M x M a R and a metric space is M dist which satis es distab 0 ltgt a b dista b distb a dista b distb c 2 dista c Using these we can show that dista b 2 O dista b distb c 2 dista c Substituting a for c dista b distb a Z dista a 2dista b 2 dista a dista b 2 0 Most people think of Euclidean distance when they think of distance de ned for ndimensional points a and b as 1 n E distab ai 7 bil2gt i1 which does satisfy the de nition of a distance function in a metric space There are a number of other distance metrics possible Some examples are the Manhattan distance mm b lt2 lai 7 54gt i1 which corresponds to distance if you are only able to move in one dimension at a time and the chessboard distance 1 n P distab 171320 lai bill 7 i1 where diagonals have the same cost as axisaligned movements Other metrics are possible by using different values of p but they have little practical importance The concept of these different distance metrics is closely related to that of vectar narms A vector norm lalp is de ned as n 3 up Damp 11 Since the difference between two points is a vector these are essentially identical to the distance metrics These vector norms are also known as Lp norms such as L l and L2 norms 2 But Inner 0r Scalar Praduct A convenient way of computing the Euclidean distance is to nd the vector between the two points and compute its L2 norm using the dot or inner product operation on vectors The dot product for two vectors a and b is n a b Zaibi i1 If a vector is dotted with itself the squared L2 norm results since n n aa Zaiai Z lailz lag i1 i1 The dot product has several other nice properties which will be used in computing distances between geometric primitives In the general case ab laHblcos0 where 9 is the angle between the vectors Therefore the dot product of perpendicular vectors is zero and the dot product of parallel vectors the product of their norms If b is unit length then the dot product a b is the projection of a onto b or the length of a in the b direction One can also think of projection as moving the head of a onto b as quickly as possible or along the shortest path So there is a connection between projection and computing minimum distance B Geametric Camputatians an Madeling Primitives This idea of projection now leads to ways of computing distances between various geometric primitives such as points lines circles and triangles A point projected onto a primitive gives the straightline distance to that object or the minimum distance For example the closest point on a plane P to a point a is the projection of a onto the plane To make the connection between projection and minimum distance more explicit consider the problem in a slightly different form A plane can be de ned as going through a set of vertices V1V2 V3 which create an internal coordinate system with axis vectors V2 7 V1 V3 7 V1 N This system then de nes the plane in parametric form Tu v where PuvV1uV27l vV37l 1 The distance D between a point a and every point on the plane is then DOM 7 la 7 Pu7vl lt2 The closest point on the plane is the minimum of Equation 2 Minima and really all extrema occur at common zeros of the partial derivative of an equation Since the distance as expressed above involves nding vector magnitude with a square root a common trick is to use the squared distance instead The squared distance shares roots with the Euclidean distance and has a simpli ed system of partial derivatives Therefore using the correspondence between the squared L2 norm and dot product D2ltu7vgt 7 a7PwgtH2 lt3 a7PuUa7Puv 4 The minimum distance occurs at simultaneous zeros of F the system of partial derivatives of D2u 1 In the following equation partials are denoted by a subscripted parameter The partials are found by using the chain rule on DZWU D2u u 2a7Pu 11 7PM u 0 F lDiwi ml l2lta 7 Pltuivgtgt 7PM ml lol 39 5 This probably does not seem like a very natural way to nd the distance to a plane and it would be computationally inef cient to use it directly However it does provide justi cation for the geometric projection operation used earlier Looking at the system of partials F it describes the conditions that need to be met where there is a minima in distance The condition is that the vector between a and the proposed solution point on the plane Pu u must be orthogonal to both the surface tangents at Pu v This is because the dot product between that vector and each tangent must equal zero for F to be a root An equivalent way of stating these constraints is that the vector between a and the proposed solution point must be parallel to the normal since the normal is orthogonal to both surface tangents Therefore the projected straightline distance concept is equivalent to the idea of projecting along the normal to nd the closest point and this is an idea that is very easily translated into algorithmic form 1 Distance fmm 01 Paint in a Plane A plane P can be de ned implicitly with a point Pa and a unit normal PN as in Pa7PaPNO All points a that satisfy this equation are part of the plane Note that when a lies on P then the vector a 7 Pa is orthogonal to the normal so the dot product is zero This plane equation is sometimes written as PaPNdO where d 7Pa PN which can be precomputed The distance from a point a to the plane can be found by evaluating the plane equation Note that the plane equation forms the vector a 7 Pa and nds its projection onto the unit normal thus giving its length in the normal direction Since projecting along the normal gives the closest point on a surface this projection is the minimum distance However this is not quite correct The point a may lie on either side of the plane in which case the equation for distance can go negative whereas distance should always be positive The signed distance between two objects is useful in these cases and has other uses in computer simulation like distingushing between contact and penetration The closest point on the plane is the original point a moved along the normal by its distance to the plane So the closest point cp is cp a 7 a 7 Pa PNPN 2 Distance fram a Paint t0 a Circle Given a twodimensional point a and a circle C in the plane with its center Cc and radius CT Then C is Ca700700 The distance between a and C is just a plugged into the equation for the circle Again this can produce negative distances when a is inside the circle Note that the normal at any point on a circle is the vector from that point to the circle center so this ful lls the projection along the normal paradigm for closest point 3 Distance fmm a Paint t0 a Line A line L in parametric form is de ned by two points P0 and P1 Lt P0 tP1 7 P0 The vector along the line P1 7 P0 is usefully written as UL The distance from a point a to the line Lt can be found by projecting a onto the line then computing the distance between the closest point projection and a So the closest point cp on the line is 39UL 39UL CPP0 aipoli i lULl lULl and the distance is la 7 cpl If you just want the distance and not the closest point there is a clever trick using the properties of cross products showing that di SW17 L M W 4 Distance fmm a Paint t0 a Line Segment A line segment is a bounded line The logic for distance from a point to a line segment is similar to that for a line but the closest point must lie within the bounded line segment This can be checked by seeing if the projection of a onto UL lies between zero and lel 5 CircleCircle Overlap Collision tests are often easier than distance measures but for simple primitives they are often equal in complexity For two cirles CO and Cl they are separated if their centers are further apart than the sum of their radii So Candace 01 000 7 010 g 007 01 6 Line SegmentLine Segment Intersectian When line segments are generally positioned then they intersect when the endpoints of each are on opposite sides of the line formed by the other line segment One way is to nd the vectors between the closest points on the line and the endpoints and to see if the vectors point in the same or different directions Another approach is to use the cross product between the line vector and a vector from a line point to an endpoint which either points out or into the plane depending on the direction Care must be taken when dealing with degenerate cases where an endpoint lies on the other line
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'