Ch.13: Robot Motion Planning
From "Computational Geometry: Algorithms and Applications", 3rd edition (Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars) 13.1. Work Space and Configuration Space 13.2. A Point Robot 13.3. Minkowski Sums 13.4. Translational Motion Planning 13.5. Motion Planning with Rotations 13.6. Notes and Comments
92 flashcards · Mathematics · by lakesare
Part of Textbooks › Computational Geometry: Algorithms and Applications (de Berg et al.) · 16 courses
[Robot Motion Planning] What is the motion planning problem for a robot?
Using its knowledge of the environment, the robot must find a way to its goal position without colliding with any obstacle. Part of building autonomous robots: you tell the robot what to do, not how. Knowledge comes from e.g. a floor plan (walls, machines) plus sensors (people).
[Robot Motion Planning] What is an articulated robot (robot arm)?
A number of links connected by joints; one end (the base) is fixed to the ground, the other carries a hand or tool. Usually three to six or more links. It must avoid collisions with the environment, the object it works on, and with itself.
[Robot Motion Planning] A robot arm joint that lets the links rotate around it, like an elbow, is a revolute joint; one that lets a link slide in and out is a prismatic joint.
[Robot Motion Planning] Which simplifying assumptions does the chapter make about the motion planning problem?
Planar work space, polygonal obstacles and robot, a static environment known to the robot, and motion in arbitrary directions (mostly translation only). Rotation is considered only at the end of the chapter.
[Robot Motion Planning] Why are car-like robots excluded from the chapter's model of motion?
Their motions are constrained: they cannot move sideways and have a minimum turning radius, which makes the geometry of their motions complicated. The chapter's robots can move in arbitrary directions.
[Work Space and Configuration Space] What is the work space of a robot R\mathcal{R}R ?
The environment the robot moves around in, here 2-dimensional, with a set S={P1,…,Pt}S = \{\mathcal{P}_1, \dots, \mathcal{P}_t\}S={P1,…,Pt} of obstacles.
[Work Space and Configuration Space] A simple polygon R\mathcal{R}R can only translate. What does R(x,y)\mathcal{R}(x, y)R(x,y) denote, and how is a placement of R\mathcal{R}R specified?
R(x,y)\mathcal{R}(x, y)R(x,y) is the robot translated over the vector (x,y)(x, y)(x,y) ; a placement (configuration) is given by a translation vector. So the robot itself is given by the vertices of R(0,0)\mathcal{R}(0, 0)R(0,0) .
[Work Space and Configuration Space] R(0,0)\mathcal{R}(0, 0)R(0,0) has vertices (1,−1),(1,1),(0,3),(−1,1),(−1,−1)(1, -1), (1, 1), (0, 3), (-1, 1), (-1, -1)(1,−1),(1,1),(0,3),(−1,1),(−1,−1) . What are the vertices of R(6,4)\mathcal{R}(6, 4)R(6,4) ?
(7,3),(7,5),(6,7),(5,5),(5,3)\boldsymbol{(7, 3), (7, 5), (6, 7), (5, 5), (5, 3)}(7,3),(7,5),(6,7),(5,5),(5,3) Add (6,4)(6, 4)(6,4) to every vertex.
[Work Space and Configuration Space] What is the reference point of a robot R\mathcal{R}R , and what does R(x,y)\mathcal{R}(x, y)R(x,y) mean in terms of it?
The point that is at the origin for R(0,0)\mathcal{R}(0, 0)R(0,0) ; R(x,y)\mathcal{R}(x, y)R(x,y) is the robot placed with its reference point at (x,y)(x, y)(x,y) . The reference point need not lie inside the robot: think of it as attached to the robot by an invisible stick.
[Work Space and Configuration Space] For a robot that can also rotate around its reference point, what does R(x,y,ϕ)\mathcal{R}(x, y, \phi)R(x,y,ϕ) denote?
The robot with its reference point at (x,y)(x, y)(x,y) , rotated counterclockwise through the angle ϕ\phiϕ . The initial robot is R(0,0,0)\mathcal{R}(0, 0, 0)R(0,0,0) .
[Work Space and Configuration Space] What is the number of degrees of freedom (DOF) of a robot, and what is it for: a planar translating robot, a planar translating and rotating robot, a translating robot in R3\mathbb{R}^3R3 , a translating and rotating robot in R3\mathbb{R}^3R3 ?
The number of parameters that specify a placement: 2, 3, 3 and 6.
[Work Space and Configuration Space] What is the configuration space C(R)\mathcal{C}(\mathcal{R})C(R) of a robot R\mathcal{R}R ?
The parameter space of R\mathcal{R}R : a point ppp in it corresponds to the placement R(p)\mathcal{R}(p)R(p) in the work space.
[Work Space and Configuration Space] What is the configuration space of a planar robot that translates and rotates, and what is its topology?
R2×[0:360)\boldsymbol{\mathbb{R}^2 \times [0 : 360)}R2×[0:360) , a topology like a cylinder. It is not Euclidean 3-space, since rotations over 0 and 360 degrees are the same.
[Work Space and Configuration Space] For a translating planar robot the configuration space is the plane, identical to the work space. Why still distinguish the two?
The work space is where the robot actually moves; the configuration space is its parameter space. In the configuration space the whole polygonal robot is a single point, and every point is a placement of an actual robot.
[Work Space and Configuration Space] What are the forbidden space Cforb(R,S)\mathcal{C}_{\text{forb}}(\mathcal{R}, S)Cforb(R,S) and the free space Cfree(R,S)\mathcal{C}_{\text{free}}(\mathcal{R}, S)Cfree(R,S) of a robot R\mathcal{R}R among obstacles SSS ?
Cforb\mathcal{C}_{\text{forb}}Cforb : configurations where the robot intersects an obstacle in SSS . Cfree\mathcal{C}_{\text{free}}Cfree : the rest, the free placements (robot intersects no obstacle).
[Work Space and Configuration Space] What does a collision-free path of the robot in the work space correspond to in the configuration space?
A curve in the free space (every placement along the path maps to a point of the configuration space). Left the work space, right the configuration space with the forbidden part grey (obstacles shown only for clarity).
[Work Space and Configuration Space] What is the configuration-space obstacle (C-obstacle) of an obstacle P\mathcal{P}P ?
The set of points ppp in configuration space such that R(p)\mathcal{R}(p)R(p) intersects P\mathcal{P}P .
[Work Space and Configuration Space] Can the C-obstacles of two disjoint obstacles overlap?
Yes, when some placement of the robot intersects both obstacles at the same time.
[Work Space and Configuration Space] Are obstacles taken to be open or closed sets in the chapter, and what does that mean for the robot?
Open, so the robot is allowed to touch obstacles. In practice, passing very close to an obstacle is unsafe (errors in robot control); slightly enlarging all obstacles before computing a path avoids it.
[A Point Robot] What is the setting of the point robot problem, and why are its work space and configuration space identical?
Obstacles: polygons with disjoint interiors, nnn vertices in total. The spaces coincide because the reference point is the robot itself. With another reference point, the configuration space is a translated copy of the work space.
[A Point Robot] Why does the chapter build a data structure for the free space instead of computing one path from a given start to a given goal?
The structure then gives a path between any start and goal position, which pays off when the work space doesn't change and many paths have to be computed.
[A Point Robot] A point robot moves among polygons P1,…,Pt\mathcal{P}_1, \dots, \mathcal{P}_tP1,…,Pt inside a large bounding box BBB . What is Cfree\mathcal{C}_{\text{free}}Cfree ?
Cfree=B∖⋃i=1tPi\boldsymbol{\mathcal{C}_{\text{free}} = B \setminus \bigcup_{i=1}^{t} \mathcal{P}_i}Cfree=B∖⋃i=1tPi The area outside BBB is treated as one extra, infinitely large obstacle. The free space can be disconnected and have holes.
[A Point Robot] What are the steps of ComputeFreeSpace (S)(S)(S) , which computes a trapezoidal map of Cfree\mathcal{C}_{\text{free}}Cfree for a point robot among a set SSS of disjoint polygons?
Compute the trapezoidal map T(E)\mathcal{T}(E)T(E) of the set EEE of all polygon edges, then remove the trapezoids inside polygons. T(E)\mathcal{T}(E)T(E) is computed with the randomized algorithm TrapezoidalMap. (a) the trapezoidal map of the obstacle edges inside the bounding box, (b) after removing trapezoids inside obstacles.
[A Point Robot] Computing a trapezoidal map of the free space for a point robot: how do you decide in O(1)O(1)O(1) time whether a trapezoid lies inside an obstacle?
Check whether the edge bounding the trapezoid from the top bounds its obstacle from above or from below. TrapezoidalMap gives each trapezoid's top edge and its obstacle; since the obstacle edges are listed in order along the boundary, the obstacle lies on a known side of each edge.
[A Point Robot] Lemma 13.1 A trapezoidal map of the free configuration space for a point robot among disjoint polygonal obstacles with nnn edges in total can be computed in … ?
O(nlogn)\boldsymbol{O(n \log n)}O(nlogn) expected time (randomized algorithm). The time of TrapezoidalMap; removing trapezoids inside obstacles costs O(1)O(1)O(1) per trapezoid.
[A Point Robot] How is the road map Groad\mathcal{G}_{\text{road}}Groad of the trapezoidal map T(Cfree)\mathcal{T}(\mathcal{C}_{\text{free}})T(Cfree) defined?
Nodes at trapezoid centers and at midpoints of vertical extensions; arcs join each center to the nodes on its trapezoid's boundary. Arcs are embedded as straight segments, so following an arc is a straight-line motion of the robot.
[A Point Robot] Why does the road map of a trapezoidal map of the free space put nodes in the middle of the vertical extensions?
Any two neighboring trapezoids share a vertical edge that is a vertical extension, so the node on it connects their center nodes.
[A Point Robot] How fast can the road map Groad\mathcal{G}_{\text{road}}Groad be built from the trapezoidal map T(Cfree)\mathcal{T}(\mathcal{C}_{\text{free}})T(Cfree) ( nnn obstacle edges in total), and how?
O(n)O(n)O(n) time, by traversing the doubly-connected edge list of T(Cfree)\mathcal{T}(\mathcal{C}_{\text{free}})T(Cfree) .
[A Point Robot] A point robot has the trapezoidal map T(Cfree)\mathcal{T}(\mathcal{C}_{\text{free}})T(Cfree) and road map Groad\mathcal{G}_{\text{road}}Groad of its free space. What are the steps of ComputePath from pstartp_{\text{start}}pstart to pgoalp_{\text{goal}}pgoal ?
Locate the trapezoids Δstart,Δgoal\Delta_{\text{start}}, \Delta_{\text{goal}}Δstart,Δgoal , then breadth-first search in Groad\mathcal{G}_{\text{road}}Groad between their center nodes vstart,vgoalv_{\text{start}}, v_{\text{goal}}vstart,vgoal . Report a straight motion pstart→vstartp_{\text{start}} \to v_{\text{start}}pstart→vstart , the road map path, and a straight motion vgoal→pgoalv_{\text{goal}} \to p_{\text{goal}}vgoal→pgoal . No trapezoid found: that position is in the forbidden…
[A Point Robot] ComputePath for a point robot reports a straight move into the start trapezoid's center, a path along the road map, and a straight move out of the goal trapezoid's center. Why is every reported path collision-free?
It consists of segments inside trapezoids, and all trapezoids lie in the free space.
[A Point Robot] ComputePath for a point robot searches the road map (center node per trapezoid, node per vertical extension) between the center nodes of the start and goal trapezoids. Why does it find a path whenever a collision-free path exists?
Consecutive trapezoids crossed by a collision-free path share a vertical extension, so their center nodes are joined via its node. The path crosses Δ1=Δstart,…,Δk=Δgoal\Delta_1 = \Delta_{\text{start}}, \dots, \Delta_k = \Delta_{\text{goal}}Δ1=Δstart,…,Δk=Δgoal , giving a road map path from v1v_1v1 to vkv_kvk . Breadth-first search then finds some (possibly different) path.
[A Point Robot] Point robot among obstacles with nnn edges in total: why does a ComputePath query (locate start and goal, breadth-first search in Groad\mathcal{G}_{\text{road}}Groad , report the path) take O(n)O(n)O(n) time?
Point location takes O(logn)O(\log n)O(logn) (or O(n)O(n)O(n) by checking all trapezoids), and Groad\mathcal{G}_{\text{road}}Groad has O(n)O(n)O(n) nodes and arcs, so the search and the reported path are O(n)O(n)O(n) . Nodes: one per trapezoid and one per vertical extension, both linear in nnn . Arcs: linear because the graph is planar.
[A Point Robot] Theorem 13.2 Let R\mathcal{R}R be a point robot among a set SSS of polygonal obstacles with nnn edges in total. How fast can SSS be preprocessed, and how fast is a query for a collision-free path between any start and goal?
Preprocessing O(nlogn)O(n \log n)O(nlogn) expected time; each query O(n)O(n)O(n) (it finds a path if one exists).
[A Point Robot] What is the weakness of the paths found with the trapezoidal map and road map of the free space?
They can make large detours: nothing guarantees a short path. Shortest paths (Chapter 15) are possible, but that algorithm is slower by an order of magnitude.
[Minkowski Sums] What makes motion planning for a polygonal robot harder than for a point robot?
The configuration-space obstacles are no longer the same as the obstacles in the work space. Otherwise the same approach works: trapezoidal map of the free space plus road map.
[Minkowski Sums] For a convex translating robot R\mathcal{R}R and a convex obstacle P\mathcal{P}P , how can you visualize the boundary of the C-obstacle CP:={(x,y):R(x,y)∩P≠∅}\mathcal{C}\mathcal{P} := \{(x, y) : \mathcal{R}(x, y) \cap \mathcal{P} \neq \emptyset\}CP:={(x,y):R(x,y)∩P=∅} ?
Slide R\mathcal{R}R along the boundary of P\mathcal{P}P : the reference point of R\mathcal{R}R traces the boundary of CP\mathcal{C}\mathcal{P}CP .
[Minkowski Sums] What is the Minkowski sum S1⊕S2S_1 \oplus S_2S1⊕S2 of two sets S1,S2⊂R2S_1, S_2 \subset \mathbb{R}^2S1,S2⊂R2 ?
S1⊕S2:={p+q:p∈S1,q∈S2}\boldsymbol{S_1 \oplus S_2 := \{p + q : p \in S_1, q \in S_2\}}S1⊕S2:={p+q:p∈S1,q∈S2} p+q=(px+qx,py+qy)p + q = (p_x + q_x, p_y + q_y)p+q=(px+qx,py+qy) is the vector sum.
[Minkowski Sums] For a set SSS in the plane, what is −S-S−S ?
−S:={−p:p∈S}\boldsymbol{-S := \{-p : p \in S\}}−S:={−p:p∈S} , the reflection of SSS about the origin, where −p=(−px,−py)-p = (-p_x, -p_y)−p=(−px,−py) .
[Minkowski Sums] Theorem 13.3 Let R\mathcal{R}R be a planar, translating robot and P\mathcal{P}P an obstacle. The C-obstacle of P\mathcal{P}P is … ?
P⊕(−R(0,0))\boldsymbol{\mathcal{P} \oplus (-\mathcal{R}(0, 0))}P⊕(−R(0,0)) P⊕(−R(0,0))\mathcal{P} \oplus (-\mathcal{R}(0, 0))P⊕(−R(0,0)) is sometimes called the Minkowski difference of P\mathcal{P}P and R(0,0)\mathcal{R}(0, 0)R(0,0) ; the book avoids the term since mathematics defines it differently.
[Minkowski Sums] For a translating planar robot R\mathcal{R}R , the C-obstacle of P\mathcal{P}P is P⊕(−R(0,0))\mathcal{P} \oplus (-\mathcal{R}(0, 0))P⊕(−R(0,0)) .What is the key step of the proof?
A point qqq lies in R(x,y)\mathcal{R}(x, y)R(x,y) if and only if q−(x,y)∈R(0,0)q - (x, y) \in \mathcal{R}(0, 0)q−(x,y)∈R(0,0) , so q∈R(x,y)∩Pq \in \mathcal{R}(x, y) \cap \mathcal{P}q∈R(x,y)∩P gives (x,y)=q+(−(q−(x,y)))∈P⊕(−R(0,0))(x, y) = q + (-(q - (x, y))) \in \mathcal{P} \oplus (-\mathcal{R}(0, 0))(x,y)=q+(−(q−(x,y)))∈P⊕(−R(0,0)) . Conversely, (x,y)=p−r(x, y) = p - r(x,y)=p−r with r∈R(0,0)r \in \mathcal{R}(0, 0)r∈R(0,0) , p∈Pp \in \mathcal{P}p∈P means p=r+(x,y)∈R(x,y)∩Pp = r + (x, y) \in \ma…
[Minkowski Sums] A translating robot has R(0,0)\mathcal{R}(0, 0)R(0,0) = the triangle with vertices (0,0),(1,0),(0,1)(0, 0), (1, 0), (0, 1)(0,0),(1,0),(0,1) . What is the C-obstacle of an obstacle consisting of the single point (0,0)(0, 0)(0,0) ?
The triangle with vertices (0,0),(−1,0),(0,−1)(0, 0), (-1, 0), (0, -1)(0,0),(−1,0),(0,−1) , i.e. −R(0,0)-\mathcal{R}(0, 0)−R(0,0) . R(x,y)\mathcal{R}(x, y)R(x,y) contains the origin exactly when (x,y)∈−R(0,0)(x, y) \in -\mathcal{R}(0, 0)(x,y)∈−R(0,0) : the reflection matters.
[Minkowski Sums] Observation 13.4 Let P\mathcal{P}P and R\mathcal{R}R be objects in the plane and CP:=P⊕R\mathcal{C}\mathcal{P} := \mathcal{P} \oplus \mathcal{R}CP:=P⊕R . What is an extreme point in direction d⃗\vec{d}d on CP\mathcal{C}\mathcal{P}CP ?
The sum of extreme points in direction d⃗\vec{d}d on P\mathcal{P}P and on R\mathcal{R}R .
[Minkowski Sums] Theorem 13.5 Let P\mathcal{P}P and R\mathcal{R}R be convex polygons with nnn and mmm edges. What is P⊕R\mathcal{P} \oplus \mathcal{R}P⊕R , and how many edges can it have?
A convex polygon with at most n+mn + mn+m edges. Exactly n+mn + mn+m if P\mathcal{P}P and R\mathcal{R}R have no parallel edges.
[Minkowski Sums] The Minkowski sum of convex polygons P\mathcal{P}P and R\mathcal{R}R with nnn and mmm edges has at most n+mn + mn+m edges.How does the proof count the edges?
Charge each edge eee of P⊕R\mathcal{P} \oplus \mathcal{R}P⊕R to an edge of P\mathcal{P}P or R\mathcal{R}R that is extreme in the direction of eee 's outer normal; each edge is charged at most once. eee is extreme in its outer normal direction, so it is generated by extreme points of P\mathcal{P}P and R\mathcal{R}R in that direction, and at least one of them must be an edge.
[Minkowski Sums] How many edges does the Minkowski sum of the unit square [0,1]2[0, 1]^2[0,1]2 and the triangle with vertices (0,0),(1,0),(0,1)(0, 0), (1, 0), (0, 1)(0,0),(1,0),(0,1) have?
5: the pentagon (0,0),(2,0),(2,1),(1,2),(0,2)(0, 0), (2, 0), (2, 1), (1, 2), (0, 2)(0,0),(2,0),(2,1),(1,2),(0,2) . 4+3=74 + 3 = 74+3=7 edges minus two, because the bottom and left edges of the square and triangle are parallel (same outer normal) and merge.
[Minkowski Sums] When are two planar objects o1,o2o_1, o_2o1,o2 , each bounded by a simple closed curve, a pair of pseudodiscs?
When ∂o1∩int(o2)\partial o_1 \cap \operatorname{int}(o_2)∂o1∩int(o2) and ∂o2∩int(o1)\partial o_2 \cap \operatorname{int}(o_1)∂o2∩int(o1) are both connected. Intuitively: their boundaries intersect in at most two points. The formal version also handles degenerate cases such as 1-dimensional boundary overlaps.
[Minkowski Sums] What is a collection of pseudodiscs, and does it make sense to call a single object a pseudodisc?
A collection in which every pair of objects is a pair of pseudodiscs. No: the property is about how two boundaries interact. Examples: collections of discs, collections of axis-parallel squares.
[Minkowski Sums] For polygons P,P′\mathcal{P}, \mathcal{P}'P,P′ , when is an intersection point p∈∂P∩∂P′p \in \partial\mathcal{P} \cap \partial\mathcal{P}'p∈∂P∩∂P′ a boundary crossing?
When ∂P\partial\mathcal{P}∂P crosses from the interior of P′\mathcal{P}'P′ to the exterior of P′\mathcal{P}'P′ at ppp .
[Minkowski Sums] Observation 13.6. How many boundary crossings can a pair of polygonal pseudodiscs P,P′\mathcal{P}, \mathcal{P}'P,P′ define?
At most two.
[Minkowski Sums] When is one polygon more extreme in a direction d⃗\vec{d}d than another, and what is the range from direction d⃗1\vec{d}_1d1 to d⃗2\vec{d}_2d2 ?
Its extreme points in direction d⃗\vec{d}d lie further in that direction. The range: the directions on the counterclockwise arc of the unit circle from d⃗1\vec{d}_1d1 to d⃗2\vec{d}_2d2 . So the range from d⃗1\vec{d}_1d1 to d⃗2\vec{d}_2d2 differs from the range from d⃗2\vec{d}_2d2 to d⃗1\vec{d}_1d1 .
[Minkowski Sums] Observation 13.7 Let P1,P2\mathcal{P}_1, \mathcal{P}_2P1,P2 be convex polygons with disjoint interiors, and d⃗1,d⃗2\vec{d}_1, \vec{d}_2d1,d2 directions in which P1\mathcal{P}_1P1 is more extreme than P2\mathcal{P}_2P2 . Then … ?
P1\mathcal{P}_1P1 is more extreme than P2\mathcal{P}_2P2 in all directions of the range from d⃗1\vec{d}_1d1 to d⃗2\vec{d}_2d2 , or in all directions of the range from d⃗2\vec{d}_2d2 to d⃗1\vec{d}_1d1 . The directions where each polygon is more extreme form connected ranges.
[Minkowski Sums] Theorem 13.8 Let P1,P2\mathcal{P}_1, \mathcal{P}_2P1,P2 be convex polygons with disjoint interiors and R\mathcal{R}R another convex polygon. What can you say about P1⊕R\mathcal{P}_1 \oplus \mathcal{R}P1⊕R and P2⊕R\mathcal{P}_2 \oplus \mathcal{R}P2⊕R ?
They are pseudodiscs.
[Minkowski Sums] P1,P2,R\mathcal{P}_1, \mathcal{P}_2, \mathcal{R}P1,P2,R are convex polygons, P1,P2\mathcal{P}_1, \mathcal{P}_2P1,P2 with disjoint interiors, and CPi:=Pi⊕R\mathcal{C}\mathcal{P}_i := \mathcal{P}_i \oplus \mathcal{R}CPi:=Pi⊕R . Claim: ∂CP1∩int(CP2)\partial\mathcal{C}\mathcal{P}_1 \cap \operatorname{int}(\mathcal{C}\mathcal{P}_2)∂CP1∩int(CP2) is connected.How does the proof by contradiction go?
Otherwise there are points p,q,r,sp, q, r, sp,q,r,s in this order on ∂CP1\partial\mathcal{C}\mathcal{P}_1∂CP1 with p,rp, rp,r inside CP2\mathcal{C}\mathcal{P}_2CP2 and q,sq, sq,s not, so CP2\mathcal{C}\mathcal{P}_2CP2 is more extreme in the alternating outward normals d⃗p,d⃗r\vec{d}_p, \vec{d}_rdp,dr but not in d⃗q,d⃗s\vec{d}_q, \vec{d}_sdq,ds . Since extreme points of Pi⊕R\mathcal{P}_i \oplus \mathcal{R}Pi⊕R are extreme points of Pi\mathcal{P}_iPi plus those of the common R\mathcal{R}…
[Minkowski Sums] Theorem 13.9. What is the complexity of the union of a collection SSS of convex polygonal pseudodiscs with nnn edges in total?
At most 2n2n2n .
[Minkowski Sums] The union of convex polygonal pseudodiscs with nnn edges in total has complexity at most 2n2n2n . Union vertices are pseudodisc vertices, or intersections of two edges eee (of P\mathcal{P}P ) and e′e'e′ (of P′\mathcal{P}'P′ ).To which pseudodisc vertex does the proof charge a union vertex v=e∩e′v = e \cap e'v=e∩e′ ?
Say eee has no other boundary crossing with ∂P′\partial\mathcal{P}'∂P′ ; follow eee from vvv into the interior of P′\mathcal{P}'P′ and charge vvv to the endpoint of eee reached there. Since vvv is a boundary crossing and polygonal pseudodiscs have at most two, eee or e′e'e′ has no other crossing. Pseudodisc vertices on the union boundary are charged to themselves.
[Minkowski Sums] Union of convex polygonal pseudodiscs: each union vertex that is a pseudodisc vertex is charged to itself; a union vertex e∩e′e \cap e'e∩e′ is charged to the endpoint of eee (or e′e'e′ ) reached by following that edge into the other pseudodisc.Why is each pseudodisc vertex vvv charged at most twice?
At most one charge per incident edge, and charges from both edges only when vvv is not a union vertex (so it isn't charged to itself). Along each incident edge only the first crossing is charged to vvv . Charges come from both edges only when both go from vvv into the union's interior. If vvv lies in no other pseudodisc, it is charged only by itself. If it lies inside one, it is not a union vertex.
[Minkowski Sums] Does the linear bound on the union complexity of pseudodiscs need them to be polygons?
No: the union of any set of pseudodiscs has complexity linear in their total complexity, e.g. the union of nnn discs has complexity O(n)O(n)O(n) . Stronger: the number of boundary intersections that are union vertices is linear in the number of pseudodiscs. Its proof is much harder than the polygonal one.
[Minkowski Sums] What is the simple algorithm for the Minkowski sum of convex polygons P\mathcal{P}P and R\mathcal{R}R , and why is it inefficient?
Compute v+wv + wv+w for every vertex vvv of P\mathcal{P}P and www of R\mathcal{R}R , then take the convex hull. It looks at every pair of vertices.
[Minkowski Sums] What does angle(pq)\mathit{angle}(pq)angle(pq) denote?
The angle that the vector pq⃗\vec{pq}pq makes with the positive xxx -axis.
[Minkowski Sums] What are the steps of MinkowskiSum (P,R)(\mathcal{P}, \mathcal{R})(P,R) for convex polygons with vertices v1,…,vnv_1, \dots, v_nv1,…,vn and w1,…,wmw_1, \dots, w_mw1,…,wm ?
Start at i=j=1i = j = 1i=j=1 . Repeat: add vi+wjv_i + w_jvi+wj as a vertex; if angle(vivi+1)<angle(wjwj+1)\mathit{angle}(v_iv_{i+1}) < \mathit{angle}(w_jw_{j+1})angle(vivi+1)<angle(wjwj+1) advance iii , if greater advance jjj , if equal advance both; until i=n+1i = n + 1i=n+1 and j=m+1j = m + 1j=m+1 . Indices wrap: vn+1=v1v_{n+1} = v_1vn+1=v1 , vn+2=v2v_{n+2} = v_2vn+2=v2 , wm+1=w1w_{m+1} = w_1wm+1=w1 , wm+2=w2w_{m+2} = w_2wm+2=w2 .
[Minkowski Sums] MinkowskiSum walks along convex polygons P\mathcal{P}P (vertices v1,…,vnv_1, \dots, v_nv1,…,vn ) and R\mathcal{R}R ( w1,…,wmw_1, \dots, w_mw1,…,wm ) at once. In which order must the vertices be given?
Counterclockwise, with v1v_1v1 and w1w_1w1 the vertices of smallest yyy -coordinate (smallest xxx -coordinate in case of ties). v1v_1v1 and w1w_1w1 are both extreme in the downward direction, so v1+w1v_1 + w_1v1+w1 is a vertex of the sum.
[Minkowski Sums] MinkowskiSum adds vi+wjv_i + w_jvi+wj as a vertex, then advances iii , jjj or both, depending on which of the edges vivi+1v_iv_{i+1}vivi+1 , wjwj+1w_jw_{j+1}wjwj+1 has the smaller angle with the positive xxx -axis.Why does it output the correct vertices, and why in linear time?
Each vertex of the sum adds two vertices extreme in a common direction, which the angle test finds; each step advances iii or jjj . Neither index is advanced after reaching n+1n + 1n+1 resp. m+1m + 1m+1 , so there are at most n+mn + mn+m iterations.
[Minkowski Sums] Theorem 13.10. How fast can the Minkowski sum of two convex polygons with nnn and mmm vertices be computed?
O(n+m)\boldsymbol{O(n + m)}O(n+m) time.
[Minkowski Sums] Which identity for Minkowski sums and unions lets you handle non-convex polygons?
S1⊕(S2∪S3)=(S1⊕S2)∪(S1⊕S3)\boldsymbol{S_1 \oplus (S_2 \cup S_3) = (S_1 \oplus S_2) \cup (S_1 \oplus S_3)}S1⊕(S2∪S3)=(S1⊕S2)∪(S1⊕S3) Triangulate the non-convex polygon and take the union of the sums of its triangles.
[Minkowski Sums] P\mathcal{P}P is a non-convex polygon with nnn vertices and R\mathcal{R}R a convex polygon with mmm vertices. Why is the complexity of P⊕R\mathcal{P} \oplus \mathcal{R}P⊕R only O(nm)O(nm)O(nm) ?
Triangulate P\mathcal{P}P : the n−2n - 2n−2 sums ti⊕Rt_i \oplus \mathcal{R}ti⊕R are pseudodiscs with at most m+3m + 3m+3 vertices each, so their union has complexity O(nm)O(nm)O(nm) . The union complexity of pseudodiscs is linear in their total complexity. P⊕R=⋃i=1n−2ti⊕R\mathcal{P} \oplus \mathcal{R} = \bigcup_{i=1}^{n-2} t_i \oplus \mathcal{R}P⊕R=⋃i=1n−2ti⊕R . The triangles have disjoint interiors, which makes the sums pseudodiscs.
[Minkowski Sums] Which example shows that the Minkowski sum of a non-convex polygon P\mathcal{P}P ( nnn vertices) and a convex polygon R\mathcal{R}R ( mmm vertices) can have complexity Θ(nm)\Theta(nm)Θ(nm) ?
⌊n/2⌋\lfloor n/2 \rfloor⌊n/2⌋ upward spikes, and a small R\mathcal{R}R = top half of a regular (2m−2)(2m - 2)(2m−2) -gon: each spike of the sum has mmm vertices at its top.
[Minkowski Sums] P\mathcal{P}P and R\mathcal{R}R are both non-convex, with nnn and mmm vertices. Why is the complexity of P⊕R\mathcal{P} \oplus \mathcal{R}P⊕R O(n2m2)O(n^2m^2)O(n2m2) ?
Triangulate both: P⊕R\mathcal{P} \oplus \mathcal{R}P⊕R is the union of the (n−2)(m−2)(n - 2)(m - 2)(n−2)(m−2) constant-complexity polygons ti⊕ujt_i \oplus u_jti⊕uj . The bound is tight in the worst case:
[Minkowski Sums] Theorem 13.11. P\mathcal{P}P and R\mathcal{R}R are polygons with nnn and mmm vertices. What is the complexity of P⊕R\mathcal{P} \oplus \mathcal{R}P⊕R if both are convex, if one is convex, and if neither is?
O(n+m)\boldsymbol{O(n + m)}O(n+m) , O(nm)\boldsymbol{O(nm)}O(nm) and O(n2m2)\boldsymbol{O(n^2m^2)}O(n2m2) ; all tight in the worst case.
[Minkowski Sums] How do you compute the Minkowski sum of two non-convex polygons?
Triangulate both, compute the Minkowski sum of each pair of triangles, and take the union.
[Translational Motion Planning] Theorem 13.12 Let R\mathcal{R}R be a convex robot of constant complexity, translating among a set SSS of non-intersecting polygonal obstacles with nnn edges in total. What is the complexity of Cfree(R,S)\mathcal{C}_{\text{free}}(\mathcal{R}, S)Cfree(R,S) ?
O(n)\boldsymbol{O(n)}O(n)
[Translational Motion Planning] A convex robot R\mathcal{R}R of constant complexity translates among non-intersecting polygonal obstacles with nnn edges in total. Claim: the free space has complexity O(n)O(n)O(n) .What is the proof?
Triangulate the obstacles: the O(n)O(n)O(n) C-obstacles of the triangles are constant-complexity pseudodiscs, so their union is O(n)O(n)O(n) . The triangles have disjoint interiors. The free space is the complement of that union. Pseudodiscs: Minkowski sums of convex polygons with disjoint interiors with the same convex polygon −R(0,0)-\mathcal{R}(0, 0)−R(0,0) . Linear: the union of convex polygonal pseudodiscs with nnn edges has complexity at most 2n2n2n .
[Translational Motion Planning] For a translating convex robot R\mathcal{R}R , with the obstacles triangulated into triangles P1,…,Pn\mathcal{P}_1, \dots, \mathcal{P}_nP1,…,Pn , what formula gives the forbidden space?
Cforb=⋃i=1nCPi=⋃i=1nPi⊕(−R(0,0))\boldsymbol{\mathcal{C}_{\text{forb}} = \bigcup_{i=1}^{n} \mathcal{C}\mathcal{P}_i = \bigcup_{i=1}^{n} \mathcal{P}_i \oplus (-\mathcal{R}(0, 0))}Cforb=⋃i=1nCPi=⋃i=1nPi⊕(−R(0,0)) The algorithm computes Cforb\mathcal{C}_{\text{forb}}Cforb ; the free space is its complement.
[Translational Motion Planning] How does ForbiddenSpace (CP1,…,CPn)(\mathcal{C}\mathcal{P}_1, \dots, \mathcal{C}\mathcal{P}_n)(CP1,…,CPn) compute the union of the C-obstacles?
Divide and conquer: recursively compute the union of the first ⌈n/2⌉\lceil n/2 \rceil⌈n/2⌉ and of the rest, then merge the two by computing their union. With the regions stored as doubly-connected edge lists, the union is computed with the map overlay algorithm (Chapter 2).
[Translational Motion Planning] Lemma 13.13. How fast can the free space of a convex robot of constant complexity translating among polygons with nnn edges in total be computed?
O(nlog2n)\boldsymbol{O(n \log^2 n)}O(nlog2n) time. By divide and conquer: compute the union of the C-obstacles of the obstacles' triangles.
[Translational Motion Planning] ForbiddenSpace computes the union of nnn constant-complexity C-obstacles (of the triangles of the obstacles) by divide and conquer, merging with the map overlay algorithm in O((n1+n2+k)log(n1+n2))O((n_1 + n_2 + k) \log(n_1 + n_2))O((n1+n2+k)log(n1+n2)) , where n1,n2,kn_1, n_2, kn1,n2,k are the complexities of the two halves and of their union.Why is the total time O(nlog2n)O(n \log^2 n)O(nlog2n) ?
The free (and forbidden) space has complexity linear in the obstacles' total complexity, so n1,n2,kn_1, n_2, kn1,n2,k are O(n)O(n)O(n) and a merge costs O(nlogn)O(n \log n)O(nlogn) : T(n)=T(⌈n/2⌉)+T(⌊n/2⌋)+O(nlogn)=O(nlog2n)T(n) = T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + O(n \log n) = O(n \log^2 n)T(n)=T(⌈n/2⌉)+T(⌊n/2⌋)+O(nlogn)=O(nlog2n) . Triangulating obstacles with mim_imi vertices costs ∑milogmi≤nlogn\sum m_i \log m_i \le n \log n∑milogmi≤nlogn , and computing the C-obstac…
[Translational Motion Planning] Theorem 13.14 Let R\mathcal{R}R be a convex robot of constant complexity translating among a set SSS of disjoint polygonal obstacles with nnn edges in total. What are the preprocessing and query times for collision-free paths between any start and goal?
Preprocessing O(nlog2n)O(n \log^2 n)O(nlog2n) expected time; each query O(n)O(n)O(n) (it finds a path if one exists). Compute the free space, then its trapezoidal map and road map; map start and goal placements to points of the configuration space, find a path as for a point robot, and map it back to the work space.
[Motion Planning with Rotations] When is translational motion not enough for a robot, and when is it?
A long, skinny robot may have to change its orientation to pass a narrow passage or go around a corner. For a circular robot, translation is enough.
[Motion Planning with Rotations] A convex polygonal robot R\mathcal{R}R translates and rotates among obstacles P1,…,Pt\mathcal{P}_1, \dots, \mathcal{P}_tP1,…,Pt . What is its configuration space, and what is the C-obstacle CPi\mathcal{C}\mathcal{P}_iCPi ?
R2×[0:360)\boldsymbol{\mathbb{R}^2 \times [0 : 360)}R2×[0:360) with (x,y,0)(x, y, 0)(x,y,0) and (x,y,360)(x, y, 360)(x,y,360) identified; CPi:={(x,y,ϕ):R(x,y,ϕ)∩Pi≠∅}\boldsymbol{\mathcal{C}\mathcal{P}_i := \{(x, y, \phi) : \mathcal{R}(x, y, \phi) \cap \mathcal{P}_i \neq \emptyset\}}CPi:={(x,y,ϕ):R(x,y,ϕ)∩Pi=∅} .
[Motion Planning with Rotations] A robot R\mathcal{R}R translates and rotates. What is the cross-section of the C-obstacle CPi\mathcal{C}\mathcal{P}_iCPi with a plane ϕ=ϕ0\phi = \phi_0ϕ=ϕ0 , and what does CPi\mathcal{C}\mathcal{P}_iCPi look like?
A Minkowski sum Pi⊕(−R(0,0,ϕ0))\mathcal{P}_i \oplus (-\mathcal{R}(0, 0, \phi_0))Pi⊕(−R(0,0,ϕ0)) placed at height ϕ0\phi_0ϕ0 ; it changes continuously with ϕ0\phi_0ϕ0 , so CPi\mathcal{C}\mathcal{P}_iCPi is a twisted pillar. Within a plane of fixed ϕ\phiϕ the problem is purely translational. All edges and facets of the pillar except the top and bottom facet are curved.
[Motion Planning with Rotations] What is the combinatorial complexity of the free space of a robot that translates and rotates in the plane?
It can be quadratic for a convex robot, and even cubic for a non-convex robot. Its boundary is also curved, not polygonal, which makes a cell decomposition hard to compute.
[Motion Planning with Rotations] What is the idea of the slice method for planning motions with rotations?
Use finitely many slices ϕ=ϕi\phi = \phi_iϕ=ϕi (horizontal cross-sections); move by translation within a slice and by rotation between consecutive slices. With zzz slices, ϕi=i⋅(360/z)\phi_i = i \cdot (360/z)ϕi=i⋅(360/z) for 0≤i≤z−10 \le i \le z - 10≤i≤z−1 . In each slice, compute the trapezoidal map Ti\mathcal{T}_iTi and road map Gi\mathcal{G}_iGi of the free space of R(0,0,ϕi)\mathcal{R}(0, 0, \phi_i)R(0,0,ϕi) .
[Motion Planning with Rotations] Slice method: how are the road maps Gi\mathcal{G}_iGi and Gi+1\mathcal{G}_{i+1}Gi+1 of consecutive slices ϕi,ϕi+1\phi_i, \phi_{i+1}ϕi,ϕi+1 connected into one road map Groad\mathcal{G}_{\text{road}}Groad ?
For each intersecting pair Δ1∈Ti\Delta_1 \in \mathcal{T}_iΔ1∈Ti , Δ2∈Ti+1\Delta_2 \in \mathcal{T}_{i+1}Δ2∈Ti+1 , add a rotation arc from (x,y,ϕi)(x, y, \phi_i)(x,y,ϕi) to (x,y,ϕi+1)(x, y, \phi_{i+1})(x,y,ϕi+1) for a point (x,y)∈Δ1∩Δ2(x, y) \in \Delta_1 \cap \Delta_2(x,y)∈Δ1∩Δ2 . Ti,Ti+1\mathcal{T}_i, \mathcal{T}_{i+1}Ti,Ti+1 are the slices' trapezoidal maps. The new nodes are joined to the center nodes of Δ1\Delta_1Δ1 resp. Δ2\Delta_2Δ2 (translations). The pairs come from an overlay…
[Motion Planning with Rotations] Slice method: what are the five parts of the motion reported from R(xstart,ystart,ϕstart)\mathcal{R}(x_{\text{start}}, y_{\text{start}}, \phi_{\text{start}})R(xstart,ystart,ϕstart) to the goal placement?
Rotate to the nearest slice, translate to vstartv_{\text{start}}vstart , road map path to vgoalv_{\text{goal}}vgoal , translate within that slice, rotate to the goal. vstart,vgoalv_{\text{start}}, v_{\text{goal}}vstart,vgoal are the center nodes of the start and goal trapezoids in those slices, and the road map path is found by breadth-first search.
[Motion Planning with Rotations] What two errors can the slice method for rotating robots make?
It can report that no path exists when one does, and the reported paths need not be collision-free. e.g. the start is free but the start position within the nearest slice is not. And a rotation between two collision-free placements in adjacent slices may collide halfway. Both get less likely with more slices, but never certain.
[Motion Planning with Rotations] Slice method with zzz slices: how is the robot enlarged to make the rotational motions safe?
Rotate R\mathcal{R}R clockwise and counterclockwise over (180/z)°(180/z)°(180/z)° , and plan with a convex polygon R′\mathcal{R}'R′ that contains the swept area. Cost: more cases where the method wrongly reports that no path exists.
[Motion Planning with Rotations] Slice method with zzz slices, 360/z degrees apart: planning uses an enlarged convex robot R′\mathcal{R}'R′ that contains the area R\mathcal{R}R sweeps when rotated by up to (180/z)°(180/z)°(180/z)° either way.Why can R\mathcal{R}R not collide while rotating from slice ϕi\phi_iϕi to ϕi+1\phi_{i+1}ϕi+1 ?
Every intermediate orientation is within (180/z)°(180/z)°(180/z)° of ϕi\phi_iϕi or ϕi+1\phi_{i+1}ϕi+1 , so R\mathcal{R}R lies inside R′\mathcal{R}'R′ placed at one of these two slices, and both of those placements are free.
[Notes and Comments] How many breakpoints (boundary intersections of two pseudodiscs) can the boundary of the union of nnn pseudodiscs have, polygonal or not?
At most 6n−126n - 126n−12 .
[Notes and Comments] For a convex robot of constant complexity translating among polygons with nnn edges, the divide-and-conquer union of the C-obstacles takes O(nlog2n)O(n \log^2 n)O(nlog2n) . How much faster can this step be done, and how?
O(nlogn)\boldsymbol{O(n \log n)}O(nlogn) , with a randomized incremental algorithm.
[Notes and Comments] A planar robot translates and rotates. How fast can its motion planning be solved exactly with an exact cell decomposition, in general and for a convex robot?
O(n3)\boldsymbol{O(n^3)}O(n3) in general, O(n2log2n)\boldsymbol{O(n^2 \log^2 n)}O(n2log2n) for a convex robot. The slice method is only approximate: it isn't guaranteed to find a path if one exists.
[Notes and Comments] What is the retraction method for motion planning, and which road map is a natural choice?
A road map built directly, plus a retraction of every free point onto it. A Voronoi diagram (it stays as far from obstacles as possible). No decomposition of the free space; paths retract start and goal and then follow the road map. For a disc robot the normal Voronoi diagram works; otherwise a distance function depending on the robot's shape. Often computable in O(nlogn)O(n \log n)O(nlogn) .
[Notes and Comments] What are the potential field method and the probabilistic road map method?
Potential field: the goal attracts and obstacles repel the robot. Probabilistic road map: random placements, connected into a road map. Both are heuristics, not exact methods. With a potential field the robot moves as the field dictates and can get stuck in local minima.
[Notes and Comments] A path where the robot may touch obstacles is called semi-free; a path that touches no obstacle is called free.