DOC PREVIEW
MIT 6 838 - Motion Planning

This preview shows page 1-2-3-4-5-6 out of 17 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 17 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

March 10, 2005 Lecture 11: Motion PlanningMotion PlanningPiotr IndykMarch 10, 2005 Lecture 11: Motion PlanningPiano Mover’s Problem• Given: – A set of obstacles– The initial position of a robot– The final position of a robot• Goal: find a path that– Moves the robot from the initial to final position– Avoids the obstacles (at all times)March 10, 2005 Lecture 11: Motion PlanningBasic notions• Work space – the space with obstacles• Configuration space:– The robot (position) is a point– Forbidden space = positions in which robot collides with an obstacle– Free space: the rest • Collision-free path in the work space = path in the free part of configuration spaceMarch 10, 2005 Lecture 11: Motion PlanningDemo• http://www.diku.dk/hjemmesider/studerende/palu/start.htmlMarch 10, 2005 Lecture 11: Motion PlanningPoint case• Assume that the robot is a point• Then the work space=configuration space• Free space = the bounding box – the obstacles**March 10, 2005 Lecture 11: Motion PlanningFinding a path• Compute the trapezoidal map to represent the free space• Place a node – At the center of each trapezoid– At each edge of the trapezoid• Put the “visibility” edges• Path finding=BFS in the graph**March 10, 2005 Lecture 11: Motion PlanningNon-point robots• C-obstacle = the set of robot positions which overlap an obstacle• Free space: the bounding box minus all C-obstacles• Given a robot and obstacles, how to calculate C-obstacles ?**March 10, 2005 Lecture 11: Motion PlanningMinkowski Sum• Minkowski Sum of two sets P and Q is defined as P⊕Q={p+q: p∈P, q∈Q}• How to define C-obstacles using Minkowski Sums ?⊕oMarch 10, 2005 Lecture 11: Motion PlanningC-obstacles*March 10, 2005 Lecture 11: Motion PlanningC-obstacles• The C-obstacle of P w.r.t. robot R is equal to P⊕(-R)• Proof:– Assume robot R collides with P at position c– I.e., consider t∈(R+c) ∩ P– We have t–c∈R → c-t∈-R → c∈t+(-R)–Since t∈P, we have c∈P ⊕(-R)• Reverse direction is similarMarch 10, 2005 Lecture 11: Motion PlanningProperties of P⊕R• Assume P,R convex, with n (resp. m) edges• Theorem: P⊕R is convex: • Proof:– Consider t1,t2∈ P⊕R. We know ti=pi+rifor pi ∈ P, ri∈R– P,Q convex: λp1+(1- λ)p2 ∈P, λr1+(1- λ)r2∈R– Therefore: λt1+(1- λ)t2 = λ(p1+ r1) + (1- λ) (p2+ r2) ∈ P⊕RMarch 10, 2005 Lecture 11: Motion PlanningProperties of P⊕R II• Observation: an extreme point of P⊕R in direction d is a sum of extreme points of P and R in direction d• Proof: for p ranging in P and rranging in R:max (p+r)*d = max p*d +r*d = max p*d +max r*dMarch 10, 2005 Lecture 11: Motion PlanningProperties of P⊕R III• Theorem: P⊕R has at most n+m edges.• Proof:– Consider the space of directionsMarch 10, 2005 Lecture 11: Motion PlanningMore complex obstacles• Pseudo-disc pairs: O1and O2are in pd position, if O1-O2and O2-O1are connected• At most two proper intersections of boundariesMarch 10, 2005 Lecture 11: Motion PlanningMinkowski sums are pseudo-discs• Consider convex P,Q,R, such that P and Q are disjoint. Then C1=P⊕R and C2=Q⊕R are in pd position.• Proof:– Consider C1-C2, assume it has 2 connected components– There are two different directions d and d’ :•In which C1is more extreme than C2• Somewhere in between d and d’ , as well as d’ and d, C2is more extreme than C1– By properties of ⊕, direction d is more extreme for C1=P⊕R than C2=Q⊕R iff it is more extreme for Pthan for Q– Thus, there are two different directions d and d’ :•In which P is more extreme than Q• Somewhere in between d and d’ ,as well as d’ and d, Q is more extreme than P– Configuration impossible for disjoint, convex P,QC1C2PQMarch 10, 2005 Lecture 11: Motion PlanningUnion of pseudo-discs• Let P1,…,Pkbe polygons in pd position. Then their union has complexity |P1| +…+ |Pk|•Proof: – Suffices to bound the number of vertices– Each vertex either original or induced by intersection– Charge each intersection vertex to the next original vertex in the interior of the union– Each vertex charged at most twiceMarch 10, 2005 Lecture 11: Motion PlanningConvex R⊕ Non-convex P• Triangulate P into T1,…,Tn• Compute R⊕T1,…, R ⊕Tn• Compute their union• Complexity: |R| n• Similar algorithmic


View Full Document

MIT 6 838 - Motion Planning

Download Motion Planning
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Motion Planning and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Motion Planning 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?