Randomized Motion Planning – Nancy Amato – Fall 04, Univ. of Padova Configuration Space [ 1 ]Configuration SpaceAcknowledgement: Parts of these course notes are based on notes from courses given byJean-Claude Latombe at Stanford University (and Chapters 2 and 3 in his text RobotMotion Planning, Kluwer, 1991), O. Bur¸chan Bayazıt at Washington University in St.Louis. Seth Hutchinson at the University of Illinois at Urbana-Champaign, and LeoJoskowicz at Hebrew University.Randomized Motion Planning – Nancy Amato – Fall 04, Univ. of Padova Configuration Space [ 2 ]C-space of Rigid ObjectMain Idea: Represent the robot as a point, called a configuration, in aparameter space, the configuration space (or C-space).Note: For now, assume robot is a rigid object not constrained by any kinematicor dynamic constraints.FWOWxyzOAFAAxzyWorkspace W: physical workspace• represented as N-dimensional Euclidean Space IRN, where N = 2, 3• FW: fixed Cartesian coordinate system (frame) of W• OW: fixed origin of FWRobot A: moving rigid object/robot• represented as compact subset of IRN(at reference position and orientation)• FA: frame of A (aka ’local’ frame of A)– fixed wrt A (i.e., each point in A has fixed coordinates in FA)– moving wrt FW• OA: origin of FA(aka the reference point of A)Randomized Motion Planning – Nancy Amato – Fall 04, Univ. of Padova Configuration Space [ 3 ]C-space of Rigid Object (cont’d)Definitions:• A configuration q of A is a specification of the position and orientationof FAwrt FW• The configuration space of A is the space C of all the possible config-urations of A• The reference configuration of A, denoted by 0, is some (arbitrary)configuration of ANote: C is independent of choice of FAand FW(but its representation is not)Notation:• A(q): subset of W occupied by A at configuration q• a(q): position of point a ∈ A in W when A at configuration q• x(q): position of feature x ∈ A in W when A at configuration qRandomized Motion Planning – Nancy Amato – Fall 04, Univ. of Padova Configuration Space [ 4 ]Configurations as transformationsSometimes useful to think of configurations as rigid body transformations...transformation T Rqrotates and translates A(0) to A(q)• denoted T Rq(A(0)) = A(q)• preserves distance and orientationFact 1: for every q ∈ C there exists a unique rotation r and translation t, suchthat T Rq= t ◦ r (composition with r applied first), i.e., T Rq(A(0)) = A(q)Fact 2: the space of rigid body transformations has the structure of a non-commutative group; composition of two transformations is the binary operatorRandomized Motion Planning – Nancy Amato – Fall 04, Univ. of Padova Configuration Space [ 5 ]Embedding C in Euclidean SpaceIdea: represent C (for rigid A) as a subset of IRM• M depends on N, the dimension of W (e.g, M = N + N2)• IRMis ambient space of C• representation of C is embedding of C in IRMConfiguration q represented as pair (T , Θ)(translation and rotation)• depends on choice of FAand FW• T determines position of OAin FW– N-vector of coordinates of OAin FW• Θ determines orientation of FA’s axes with respect to FW– N × N matrix whose columns are components of the unit vectors alongFA’s axes in FW– Θ in Special Othogonal Group SO(N ) of N × N matrices in IRN2withorthonormal columns and rows and determinant +1– called ’rotation matrices’Randomized Motion Planning – Nancy Amato – Fall 04, Univ. of Padova Configuration Space [ 6 ]Embedding C in Euclidean Space (cont’d)Suppose reference configuration 0 is where FAand FWcoincide:• T =~0 (zero N-vector)• Θ = I (N × N identity matrix)Then, for every point a ∈ A,a = a(0)a(q) = Θa(0) + T• a is N-vector of coordinates of point a in FA• a(q) is N-vector of coordinates of point a in FWwhen A is in configurationqNote: Given T and Θ, the position of any point of A in FWcan becomputed.Fortunately, the form of the rotation matrices Θ is known for both two andthree-dimensional W.Randomized Motion Planning – Nancy Amato – Fall 04, Univ. of Padova Configuration Space [ 7 ]Constructing the Rotation Matrix ΘEx: Two-Dimensional WorkspacesThe following matrix Θ represents the orientation of FAafter a rotation ofangle θ around OW, starting from the reference configuration 0:Θ =r11r12r21r22=cos θ − sin θsin θ cos θLet MCequal the subset IRN× SO(N) ⊂ IRM• where M = N + N2(M = 6 for W = IR2and M = 12 for W = IR3)• MCrepresents C in IRMFor W = IR2, each q ∈ C is given by six numbers (x, y, r11, r12, r21, r22) ∈ MC.The constraints (boundaries) of MCare given by:h1(x, y, r11, r12, r21, r22) = r211+ r221− 1 = 0 (1)h2(x, y, r11, r12, r21, r22) = r212+ r222− 1 = 0 (2)h3(x, y, r11, r12, r21, r22) = r11r12+ r21r22= 0 (3)Similarly, for W = IR3, the rotation matrix Θ is known, and MCis a subset ofIR12(see Latombe, Ch. 2)Randomized Motion Planning – Nancy Amato – Fall 04, Univ. of Padova Configuration Space [ 8 ]Properties of CFact: C is a smooth m-dimensional manifold, where fixed m depends on M• local topological and differential structures are identical to those of IRm(notglobal though)• key point: C is locally ’like’ IRmso we can parameterize it, e.g.,– stereographic projection (only for SO(1)),– Euler angles (3 angles for S0(3)),– quaternions (4 values for SO(3)).Fact: Sometimes can get by with simpler C (use symmetry)• circle, sphere: C = IRNif choose origin at center• cylinder in IR3: C = IR3×S2(unit sphere in IR3) if choose OAon cylinder’saxis and one axis of FAon cylinder’s axis• no rotation allowed: C = IRNRandomized Motion Planning – Nancy Amato – Fall 04, Univ. of Padova Configuration Space [ 9 ]Obstacles in C-spaceLet W contain fixed obstacles B1, B2, . . . , Bqwhich are closed, but not neces-sarily bounded, regions of IRN.Definition: The obstacle Biin W maps in C to the regionCBi= {q ∈ C|A(q) ∩ Bi6= ∅}CBiis called a C-obstacle. The union of all C-obstacles is called the C-obstacleregion.Properties of C-obstaclesIf Biand A are:• compact sets, then CBiis a compact set• algebraic, then CBiis algebraic• closed, then CBiis closed• connected, then CBiis connectedRandomized Motion Planning – Nancy Amato – Fall 04, Univ. of Padova Configuration Space [ 10]C-obstacle Example: A is a disc and W = IR2• select OAat center of disc (and thus FAalso)• CB of polygon B obtained by growing B