Bounded-Curvature Motion Planning amid Polygonal Obsta les by Jonathan Ba ker a thesis submitted in partial fulfillment of the requirements for the degree of Do tor of Philosophy in the fa ulty of graduate studies (Computer S ien e) University of British Columbia (Van ouver) February 2009 © Jonathan Ba ker, 2009 Abstra t We onsider the problem of nding a bounded- urvature path in the plane from one onguration αs to another onguration αt that avoids the interior of a set of polygonal obsta les E . We all any su h path from αs to αt a feasible path. In this thesis, we develop algorithms to nd feasible paths that have expli it guarantees on when they will return a feasible path. We phrase our guarantees and run time analysis in terms of the omplexity of the desired solution (see k and λ below). In a sense, our algorithms are output sensitive, whi h is parti ularly desirable be ause there are no known bounds on the solution omplexity amid arbitrary polygonal environments. Our rst major result is an algorithm that given E , αs, αt, and a positive integer k either (i) veries that every feasible path has a des riptive omplexity greater than k or (ii) outputs a feasible path. The run time of this algorithm is bounded by a polynomial in n (the total number of obsta le verti es in E), m (the bit pre ision of the input), and k. This result omplements earlier work by Fortune and Wilfong [17℄: their algorithm onsiders paths of arbitrary des riptive omplexity (it has no dependen e on k), but it never outputs a path, just whether or not a feasible path exists. Our se ond major result is an algorithm that given E , αs, αt, a length λ, and an approximation fa tor ε, either (i) veries that every feasible path has length greater than λ or (ii) onstru ts a feasible path that is at most (1 + ε) times longer than the shortest feasible path. The run time of this algorithm is bounded by a polynomial in n, m, ε−1, and λ. This algorithm is the result of applying the te hniques developed earlier in our thesis to the previous approximation approa hes [18, 3℄. A short oming of these prior approximation algorithms is that they only sear h a spe ial lass of feasible paths. This restri tion implies that the path that they return may be arbitrarily longer than the shortest path. Our algorithm returns a true approximation be ause we sear h for arbitrary shortest paths. ii Contents Abstra t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v A knowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii 1 Introdu tion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Statement of Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2 Literature Review . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1 Paths in Free Spa e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.2 Paths Amid Obsta les . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3 Normal Forms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.1 Fortune and Wilfong Normal Form . . . . . . . . . . . . . . . . . . . . 24 3.2 Combinatorial Augmentation . . . . . . . . . . . . . . . . . . . . . . . 27 4 Testing Feasibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.1 Exhaustive Sear h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2 Redundan y Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . 37 5 Eliminating Redundan y . . . . . . . . . . . . . . . . . . . . . . . . . 42 5.1 Filtering with Walls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 5.2 Corner to Corner Extensions . . . . . . . . . . . . . . . . . . . . . . . . 43 5.3 Bounds on the Run Time . . . . . . . . . . . . . . . . . . . . . . . . . . 54 6 Shortest Bounded-Curvature Path Approximation . . . . . . . . . 56 6.1 Path Normalisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 6.2 Systemati Sear h for Shortest ε-Dis rete Paths . . . . . . . . . . . . . 61 6.3 Redundan y Among Conta t Congurations . . . . . . . . . . . . . . . 62 7 Con lusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 iii Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 A Jumps between Corners . . . . . . . . . . . . . . . . . . . . . . . . . . 71 A.1 Sides of a Jump . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 A.2 Non-Crossing Condition . . . . . . . . . . . . . . . . . . . . . . . . . . 73 B Links between Corners . . . . . . . . . . . . . . . . . . . . . . . . . . 80 B.1 Link Monotoni ity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 B.2 Non-Crossing Links . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 B.3 Number of Homotopy Classes . . . . . . . . . . . . . . . . . . . . . . . 86 C Convergen e to a Fixed-Point . . . . . . . . . . . . . . . . . . . . . . 87 C.1 Forward Iteration (∆ < 2) . . . . . . . . . . . . . . . . . . . . . . . . . 87 C.2 Forward Iteration (∆ > 2) . . . . . . . . . . . . . . . . . . . . . . . . . 95 C.3 Ba kward Iteration (∆ ≤ 2) . . . . . . . . . . . . . . . . . . . . . . . . 97 C.4 Ba kward Iteration(∆ ≥ 2) . . . . . . . . . . . . . . . . . . . . . . . . . 102 iv List of Figures 1.1 Visualisation of the bounded urvature onstraint. . . . . . . . . . . . . 3 1.2 Example problem instan es. . . . . . . . . . . . . . . . . . . . . . . . . 4 2.1 Paths are wedged between ones. . . . . . . . . . . . . . . . . . . . . . 9 2.2 Length redu ing deformations. . . . . . . . . . . . . . . . . . . . . . . . 9 2.3 Shortest un onstrained path amid polyhedra. . . . . . . . . . . . . . . . 12 2.4 Rea hable intervals of obsta le onta t. . . . . . . . . . . . . . . . . . . 14 2.5 Some moderate obsta les. . . . . . . . . . . . . . . . . . . . . . . . . . 15 2.6 A oating pair of C-segments. . . . . . . . . . . . . . . . . . . . . . . . 16 2.7 A orridor and its redu ed orridor. . . . . . . . . . . . . . . . . . . . . 18 2.8 A robot with a turning radius of one annot traverse this orridor. . . . 18 2.9 Environment onta ts that not ε robust. . . . . . . . . . . . . . . . . . 21 3.1 Deformations used in FW normalisation. . . . . . . . . . . . . . . . . . 24 3.2 Representing a FW-normal path as a sequen e of jumps. . . . . . . . . 25 3.3 Observations leading to our jump representation. . . . . . . . . . . . . 26 3.4 Ea h onta t onguration has one degree of freedom. . . . . . . . . . . 28 3.5 We introdu e onstraints as we roll a onguration. . . . . . . . . . . . 30 3.6 A onguration be omes moored by rolling it. . . . . . . . . . . . . . . 31 4.1 Linkages and an hor graphs. . . . . . . . . . . . . . . . . . . . . . . . . 35 4.2 Algorithm that exhaustively sear hes for linkages. . . . . . . . . . . . . 37 4.3 One hain dire tly rea hes another. . . . . . . . . . . . . . . . . . . . . 38 4.4 Filtering ongurations before propagation. . . . . . . . . . . . . . . . . 39 5.1 Jump spe tra. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.2 Our subproblems guarantee feasibility. . . . . . . . . . . . . . . . . . . 45 5.3 Only one onguration θ an rea h ψ. . . . . . . . . . . . . . . . . . . . 46 5.4 The ongurations that an be rea hed by a jump. . . . . . . . . . . . 48 5.5 Singular jump spe tra. . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 5.6 Using symmetries to simplify the onstru tion of 〈Ψi〉. . . . . . . . . . 49 5.7 Generating a ontiguous over. . . . . . . . . . . . . . . . . . . . . . . . 50 5.8 Ba kwards iteration overlaps forwards iteration. . . . . . . . . . . . . . 51 6.1 Conta t onguration degree of freedom. . . . . . . . . . . . . . . . . . 58 v 6.2 Pro edure to onstru t short linkages. . . . . . . . . . . . . . . . . . . . 61 6.3 Pro edure to onstru t short viable linkages. . . . . . . . . . . . . . . . 63 A.1 Jumps from F to G with L-segments pointing in one xed dire tion. . . 72 A.2 L-segments are ontained in R. . . . . . . . . . . . . . . . . . . . . . . 73 A.3 Points rea hed by a jump starting with a lo kwise oriented C-segment. 73 A.4 Segments of the same type do not ross. . . . . . . . . . . . . . . . . . 74 A.5 Jumps from c to O starting with a lo kwise C-segment. . . . . . . . . 74 A.6 Earlier C-segment does not ross later L-segment. . . . . . . . . . . . . 75 A.7 Range of jumps from c to O starting with a ounter lo kwise C-segment. 76 A.8 Later C-segment does not ross earlier L-segment. . . . . . . . . . . . . 77 A.9 Earlier C-segment does not ross later L-segment . . . . . . . . . . . . 77 A.10 Lo us of points rea hing a onguration φ. . . . . . . . . . . . . . . . . 78 A.11 The jump S erties that J1 and J2 do not ross. . . . . . . . . . . . . 79 A.12 Jumps to the same onguration φ do not ross. . . . . . . . . . . . . . 79 B.1 A range of C−L0C+ stru ture links from F to G. . . . . . . . . . . . . 80 B.2 Same underlying ir le entres. . . . . . . . . . . . . . . . . . . . . . . 81 B.3 Monotoni ity of links with stru ture C0LC + . . . . . . . . . . . . . . . . 81 B.4 Monotoni ity of links with stru ture C−pi LC + . . . . . . . . . . . . . . . 82 B.5 Arbitrary quadrilateral expressed as ve tors and angles. . . . . . . . . . 83 B.6 CL0C-link monotoni ity. . . . . . . . . . . . . . . . . . . . . . . . . . . 85 B.7 Neighbours do not ross. . . . . . . . . . . . . . . . . . . . . . . . . . . 86 C.1 Forward iteration approximation. . . . . . . . . . . . . . . . . . . . . . 87 C.2 Underestimate forward iteration when ∆ ≤ 2. . . . . . . . . . . . . . . 95 C.3 Early termination when ∆ > 2. . . . . . . . . . . . . . . . . . . . . . . 96 C.4 Underestimate of ba kward iteration. . . . . . . . . . . . . . . . . . . . 97 C.5 The position of L for ∆ > 2 is the same as its position for ∆ = 2. . . . 102 vi A knowledgements Foremost, I would like to thank my supervisor, David Kirkpatri k, for all of his support over the years. He generously shared his immense experien e as a resear her, writer, and tea her, whi h fostered my a ademi and personal growth. This thesis is extremely te hni al in several pla es, and David was an invaluable guide when I be ame lost be ause I ould no longer see the forest for all of the trees. Where my arguments are elegant, it is be ause David knew that they ould be. Where they are ugly, it is be ause I ould see no other way. In addition to David, I want to thank two other members of my PhD ommittee: Will Evans and Ian Mit hell. Will was an en ouraging sounding board, and Ian looked at my thesis through the eyes of a pra titioner (even though this is a very theoreti al thesis). On a personal note, I ould not have nished this thesis without the emotional support (and unending patien e) of my wife, Robin. I also want to thank my parents: they always en ouraged me to satisfy my uriousity, and they taught me the value of hard work through their example. vii Chapter 1 Introdu tion The types of problems that we address in this thesis arise when planning the motion of robots. To see some of the issues involved, onsider two dierent problems: the exploration of the surfa e of planets and the assembly of ars in fa tories. When ex- ploring new environments, the result of a robot's a tion may be unpredi table (we only know the probability of various out omes) and the environment may be hanging or unknown. In industrial settings, we an engineer the problem around the solution. Hen e, the opposite is often true: the result of a robot's a tion is predi table and the environment is stati and known in great detail. However, even in this ideal setting, there remain two types of di ulties in planning motion: the urse of dimensionality and kinemati onstraints. Intuitively, the former means that the relation between a robot and its environment is ompli ated, and the latter means that slightly hanging the relation between a robot and its environment may require a ompli ated a tion (e.g. moving a ar slightly loser to the urb when parallel parking). Kinemati on- straints are lassied as holonomi or nonholonomi . There are standard te hniques to deal with holonomi onstraints, but the same is not true of nonholonomi onstraints. The fo us of our resear h is how to deal with a spe i type of nonholonomi onstraint. We now onsider the problem of moving a box via rigid motions to illustrate the dieren e between holonomi and nonholonomi onstraints, (see [20℄ for a more pre ise denition). Note that we an spe ify the pla ement of the box with three spatial parameters (one for ea h oordinate axis x, y, and z) and three angular parameters (yaw, pit h, and roll). Hen e, the spa e of all possible ongurations is six dimensional. Without any kinemati onstraints, we an independent translate and rotate the box. More spe i ally, there are no restri tions on the the velo ity of the box in any dimension of its onguration spa e (spatial or angular). Suppose that we want the box to slide along the surfa e of a planet. We an model this restri tion by insisting that the entre of one side of the box (the bottom) always tou hes the outside of a large sphere (the planet). This restri ts the pla ement of the box to a three-dimensional subspa e of its six-dimensional onguration spa e. To see this, note that the pla ement of the box is spe ied by the point where the box tou hes the sphere and its rotation about the ve tor normal to the point of onta t. 1 Although the pla ement of the box is more restri ted, the box still has quite a bit of freedom to move. In a three-dimensional frame of referen e just des ribed (relative to the sphere), the box an translate and rotate independently. More spe i ally, there are no restri tions on the box's velo ity in any dimension (spatial and angular) in the appropriate frame of referen e. Intuitively, this is why restri ting the box to the surfa e of a sphere is onsidered a holonomi onstraint. Now suppose that we want the box to move with a bounded turning radius like an automobile. To do this, we designate one side of the box as its front and insist that whenever the box translates, it moves in the dire tion of the front or the dire tion opposite the front. As the box moves, we limit how qui kly it rotates relative to the distan e travelled. Spe i ally, let s1 and s2 be any two pla ements of the box. If the box travels ℓ units from s1 to s2 (the length of the urve tra ed by the point of onta t), we insist that the dieren e in orientation from s1 to s2 is at most ℓ radians. Note that the spa e of rea hable pla ements is exa tly the same as it was before: we an rea h any position and orientation on the sphere by moving far enough. What hanged is that we annot hange our position and orientation independently. More spe i ally, there are restri tions on the box's velo ity (spatial and angular). This is why restri ting the turning radius is a nonholonomi onstraint. The fo us of this thesis is on ompleteness: nding a path, whenever one exists. To a hieve this property, we must sometimes nd paths that are unsuitable for real-world robots be ause they are either too di ult or too ompli ated for a robot to follow. So although our problems are motivated by real-world settings, their solutions are of more theoreti al interest than pra ti al interest. Realisti ally, we probably want to satisfy a dierent notion of ompleteness: nding a pra ti al path, whenever a pra ti al path exists. We hope that some of the te hniques developed in this thesis may be used to a hieve dierent notions of ompleteness as well. In this thesis, we adopt the algebrai model of omputation, where real numbers are the data primitive and arithmeti operations (+, −, ×, /, and √ ) take onstant time. This is distin t from the bit model of omputation, where bits are the data primitive and boolean operations take onstant time. We use the algebrai model of omputation to simplify our analysis. This is quite ommon in the literature. We mention of use of the algebrai model now, be ause it is another way in whi h our results are theoreti al. Converting our algorithms to the bit model of omputation probably annot be done in a straightforward manner. In order to a hieve ompleteness, our algorithms onsider paths whose natural des ription (in terms of planar oordinates) ould require a large number of bits in the bit model. That is, we doubt the one an dire tly substitute approximate arithmeti (e.g. oating-point representation) for exa t arithmeti . However, we will argue that all the paths that we onsider have a su in t ombinatorial des ription. So, it may be possible to use approximate arithmeti in a lever manner. In re ognition of the theoreti al nature of our work, we make no eort to optimise the performan e of our algorithms (we are satised with polynomial bounds). This allows us to fo us more on te hnique and less on analysis (whi h is already quite in- 2 volved in pla es). This attention to te hnique is important be ause our te hniques may have broader appli ations. Spe i ally, we develop two general te hniques to e iently determine if a path exists: a dis retisation of the path spa e and a method pruning the sear h for a path without sa ri ing ompleteness. The approximation results ontained in this thesis are a se ond appli ation of these two te hniques. 1.1 Statement of Results The problem motivating our resear h is moving a ar-like robot from one onguration (position and orientation) to another while avoiding obsta les. To permit rigorous analysis, we restri t our attention to a simplied setting: the robot is a point that only moves forward and it must avoid polygonal obsta les in the two-dimensional plane. The restri tion to forward motion is ommon. Intuitively, the problem with reversals is easier be ause a point robot an turn sharply (on a dime) by making arbitrarily many reversals. We rst formalise what we mean by ar-like robot. Let X(s) : ℜ → ℜ2 be a dierentiable urve tra ed by the point robot. We assume that X(s) is parameterised by ar length. We say that X has bounded urvature if there exists a onstant R (the smallest allowed radius of urvature) su h that ∥∥∥dX ds (s1)− dXds (s2) ∥∥∥ ≤ R−1 |s1 − s2|, for every s1 and s2. A geometri interpretation of this denition is that a path has bounded urvature if every point on the path an be wedged between two ir les of radius R lo ally (see Figure 1.1). The robot an only move forward lo ally be ause the bounded- urvature restri tion limits how mu h it an turn relative to the distan e that it travels. Hen e, the instantaneous onguration of a robot tra ing su h a path both its position and dire tion in whi h it an move. Like many of the bounded- urvature results reported in the literature, we assume without loss of generality that R = 1 by suitable s aling of the environment. Figure 1.1: Visualisation of the bounded urvature onstraint. A problem instan e onsists of a sour e onguration αs (the initial position and orientation of the robot), a target onguration αt (the destination position and orien- tation of the robot), and a set of obsta les E to avoid (see Figure 1.2(a)). A solution to problem instan e is a bounded- urvature path from αs to αt that does not ross the interior of any obsta le. In bounded- urvature motion planning, we must sometimes follow a long path in order to slightly hange our orientation. For example, in Figure 1.2(b) the robot must 3 loop around an obsta le in order to arrive at the same point with a slightly dierent orientation. The algorithmi results in bounded- urvature motion planning handle this potential ompli ation in two dierent ways. One result onsiders paths with an arbitrary amount of looping, but it runs in exponential time [17℄. Other results limit the degree of looping and run in polynomially bounded time. The approa h to limiting the looping is often indire t: by restri ting the lass of obsta les [2, 10, 1, 8℄ or restri ting the type of paths that are found [18, 3℄. The results in this thesis are dierent in that they take a parameter (k and λ below) that dire tly limits the amount of looping that we will onsider. αs αt (a) A problem instan e and one solution. αs αt (b) A long path may be required to slightly hange the robot's orientation. Figure 1.2: Example problem instan es. Our resear h fo uses on nding bounded- urvature paths amid polygonal obsta les. To distinguish them from graph-theoreti terms, we refer to obsta le fa es as walls (not edges) and the points where walls meet as orners (not verti es). We assume that these obsta les of E are disjoint and that an obsta le does not interse t itself. This is a modest restri tion be ause it is possible to prepro ess the environment to make this assumption hold. The ee t of this prepro essing is at most a polynomially bounded in rease in the omplexity of the environment. As in other bounded- urvature results, we let n represent the number of orners in E . In this setting, the number n is an adequate measure the omplexity of E be ause the total number of walls and orners is O(n) by Euler's formula. For purposes of analysis, we make a further assumption about the input: we assume that a problem instan e is represented with m bits of pre ision. Spe i ally, we insist that ea h real parameter of the problem instan e (su h as a orner oordinate or a oordinate of a dire tion ve tor of αs) is represented as the ratio of two integers with magnitude at most 2m. Similar assumptions are made in other results in the eld [21, 17℄. Like the authors of these other results, we use this assumption to bound how dierent two distin t things must be. For example, under this assumption two distin t orners must be at least 2−O(m) and at most 2O(m) apart. The rst main result of this thesis was presented at the 23rd Annual Symposium on Computational Geometry [5℄. It is an algorithm that given E , αs, αt, and a positive integer k either (i) veries that every feasible path has a des riptive omplexity greater 4 than k or (ii) onstru ts a feasible path whose des riptive omplexity is bounded by a polynomial in k. The run time of this algorithm is polynomially bounded in n, m, and k (a loose bound of O(n29k2(m+ nk)3) is presented in Se tion 5.3). This result diers from the prior feasibility result [17℄ in two respe ts: our algorithm runs in polynomially bounded time, whereas the previous algorithm takes exponential time; moreover, our result returns a path when a path is found whereas the prior result just indi ates that a path exists. The se ond main result of this thesis was presented at the 19th International Sym- posium on Algorithms and Computation [6℄. It is an algorithm that given E , αs, αt, a length λ, and an approximation fa tor ε, either (i) veries that every feasible path has length greater than λ or (ii) onstru ts a feasible path that is at most (1 + ε) times longer than the shortest feasible path. The run time of this algorithm is polynomially bounded in n, m, ε−1, and λ. Whereas our new result nds an approximation to the shortest path, the previous approximation results nd an approximation to the shortest ε-robust path [18, 3℄. We formally dene what it means for a path to be ε-robust in the next hapter, where we dis uss the prior approximation results. Intuitively, a path Π is ε-robust, if Π an be deformed at ea h point where Π tou hes the environment by at least ε without making Π infeasible. The restri tion to approximating an ε-robust path is substantial for two reasons. First, we an onstru t instan es where the shortest path is arbitrarily shorter than the shortest ε-robust path. In su h ases, our new result will nd an approximation to the shortest path, but the previous approximation results will not. Se ond, sometimes the only feasible paths are only ε-robust very small ε. In parti ular, it was shown that nding a shortest bounded- urvature path is NP-hard via redu tion from 3SAT [23℄. All of the feasible paths in a problem instan e that results from the polynomial time transformation of an instan e of 3SAT are 2−Ω(n)-robust. In this ase, our approximation algorithm will nd a path in polynomially bounded time (all of the paths have length O(n)), but the previous approximation results may require exponential time to guarantee that they will nd a path. 1.2 Overview In the next hapter, we review many results related to our resear h. A ore result is that every shortest bounded- urvature path amid polygonal obsta les is made of ar s of unit-radius ir les and straight-line segments [16, 18℄. We all any bounded- urvature path omposed of su h ar s and straight-line segments a Dubins path. This notion is important be ause it often su es to nd a Dubins path to solve a problem. Spe i ally, all of the bounded- urvature motion planning algorithms in the literature look for a Dubins path. In the third hapter, we present a new normal form for bounded- urvature paths. Every path in this normal form has a ombinatorial des ription. Hen e, the set of normal paths an be systemati ally enumerated. Part of our analysis bounds how mu h more ompli ated a Dubins path be omes by normalising it. To be more spe i , 5 let the intri a y of a Dubins path be the number of dierent segments of whi h it is omposed. The intri a y of a path is a measure of its des riptive omplexity be ause ea h path segment an be des ribed by a onstant number of real numbers. We prove that if there is a Dubins path of intri a y k, then there is a normal path of intri a y at most O(nk + n3). In the fourth hapter, we present one way of exhaustively sear hing for a path. The time that it takes to nd a parti ular normal path is a fun tion its intri a y. This is why the previous hapter's bound on the in rease in intri a y is important: if there is a Dubin's path Π of intri a y k, then there exists a normal path Π′ of intri a y at most O(nk + n3). However, this exhaustive sear h ould take time that is exponential in the intri a y of the path for whi h we are looking, in the worst ase. So we show how to prune the sear h. The major result of this hapter is that pruning does not sa ri e ompleteness. That is, although our sear h may not nd Π′, it will nd a path Π′′ whose intri a y is roughly at most a onstant fa tor greater than Π′. That is, the intri a y of Π′′ is also O(nk+n3). This is important be ause the run time of the pruned sear h still depends on the intri a y of the path Π′′ for whi h we are sear hing. In the fth hapter, we des ribe the details of pruning. The pruning algorithms are straightforward and obviously take time that is polynomial in the size of the set that they prune. However, the proofs that they are orre t (do not prune too mu h) and return a polynomially bounded set are te hni al. The most te hni al of these details that are isolated in separate appendi es: the rst and se ond appendi es analyse when two short, simple, bounded- urvature paths do not ross; the third appendix analyses what one short, simple, bounded- urvature path an rea h. In the sixth hapter, we apply the te hniques that we developed in the previous hapters to the problem of nding a feasible path that is not mu h longer than the shortest feasible path. Again, intri a y plays a entral role but its use is indire t. In this setting, we are looking for the shortest path Π with length less than λ. Given λ, we are able to obtain an upper bound k on the intri a y of Π. We argue that in order to approximate Π, it su es to nd a path Π′ whose intri a y is polynomial in k. As before, it su es to sear h for paths of bounded intri a y. Unlike before, we annot stop as soon as we nd a path be ause we want to nd a good approximation to the shortest path. To elaborate, in the worst ase, we must onsider all paths with intri a y below a ertain threshold in order to verify that the path that we have found is in fa t a good approximation. In the seventh hapter, we on lude with dire tions for future resear h. 6 Chapter 2 Literature Review The problems that we dis uss in this hapter are losely related to bounded- urvature motion planning. For a mu h broader survey of motion planning from a theoreti al perspe tive, we dire t the reader to an ex ellent survey by Sharir [27℄. In all the problems dis ussed in this hapter, we want to ontinuously move a point robot from a start onguration to a terminal onguration while avoiding the interior of stationary obsta les. These problems dier in the type of obsta les to avoid, the type of onstraints that are pla ed on the motion, and how (or whether) the motion should be optimised. We say that a path is feasible if it begins at the start onguration, ends at the terminal onguration, satises the appropriate motion onstraints, and does not interse t the interior of any obsta le. We note that a feasible path an tou h an obsta le's boundary, whi h is typi al of optimal paths. In this hapter, we onsider a motion onstraint that is dierent from the bounded urvature onstraint: we say that the motion of a point satises the kinodynami on- straint if (a) the magnitude of the point's velo ity never ex eeds a onstant and (b) the magnitude of the point's a eleration never ex eeds a onstant. By appropriate spatial and temporal s aling, we an assume without loss of generality that these limiting on- stants are one [23℄. Noti e that the bounded- urvature onstraint is more restri tive than the kinodynami onstraint: a point robot an follow a bounded- urvature path with unit speed (only the dire tion of the velo ity varies) without the magnitude of the a eleration ever ex eeding one (the dire tion of the a eleration is always orthogonal to the velo ity). In the kinodynami setting, a point robot's instantaneous ongura- tion is its position and its velo ity. As the speed of the robot an hange over time, the literature learly distinguishes between the path tra ed by a robot and the robot's traje tory : a des ription of its onguration at any point in time. To illustrate the dieren e between these two on epts, note that two dierent traje tories may tra e the same path. In the kinodynami setting, the ee t of the motion onstraint is weak- ened by travelling slowing: a robot an tra e (almost) any ontinuous path by moving arbitrarily slowly. Hen e, the kinodynami motion planning literature fo uses on nd- ing the qui kest traje tory, unlike the bounded- urvature literature whi h looks for the shortest path. The kinodynami motion planning problem is investigated under both 7 the L2 norm (Eu lidean norm) and the L∞ norm (supremum, uniform, or Chebyshev norm). Although the L2 norm is arguably more interesting, the L∞ norm is analyti ally simpler. 2.1 Paths in Free Spa e Finding a shortest path or qui kest traje tory are goals whi h further restri t the feasible solutions to a parti ular problem that we onsider. Optimal solutions are rst studied in the absen e of obsta les, where the motion onstraint is the only on ern. Typi ally, the analysis results in a set of ne essary onditions that optimal solutions must satisfy. We adopt the terminology found in other results in the eld and all solutions that satisfy these riteria anoni al [18, 12, 3, 25℄. To larify, in the absen e of obsta les, every optimal solution is anoni al but a anoni al solution may be suboptimal be ause it only satises ne essary (not su ient) onditions. Canoni al solutions are important be ause we need only onsider anoni al solutions when sear hing for an optimal solution: in free spa e, every optimal solution is anoni al, and amid obsta les, an optimal solution is typi ally a sequen e of anoni al solutions to subproblems. Canny et al. des ribe the kinodynami qui kest traje tory under the L∞ norm [12℄. This norm is spe ial be ause the d-dimensions are de oupled. Spe i ally, a traje tory is kinodynami if and only if ea h of its one-dimensional proje tions is kinodynami . Moreover, a qui kest traje tory an be omposed of qui kest one-dimensional traje to- ries (if qui kest traje tories in dierent dimensions take dierent times, gaps must be inserted to make them all take the same time). Hen e, the hara terisation of kinody- nami qui kest traje tories under the L∞ norm redu es to the one dimensional ase. Qui kest traje tories in one dimension a elerate as fast as possible towards the goal and de elerate as fast as possible, when they must, to avoid overshooting the target. Despite the involved ase analysis, this strategy an be omputed qui kly by solving quadrati equations. Dubins shows that shortest bounded- urvature paths belong to a small set [16℄. He rst observes that a shortest path is made of a nite sequen e of line segments (L-segments) and ar s of unit-radius ir les (C-segments). His argument is that short subpaths are sandwi hed between two ones originating from the sour e onguration and destination onguration of the subpath; the shortest path between those two ongurations uses C-segments from the ones and a bitangential L-segment (see Fig- ure 2.1). Ea h subpath of a path must be optimal, whi h proves that a shortest path is omposed of C- and L-segments. We all any dierentiable bounded- urvature path omposed of C- and L-segments Dubins normal. The stru ture of a Dubins path is the sequen e of segment types of whi h it is omposed, denoted by a string in {C,L}∗. The intri a y of a Dubins path is its total number of path segments. We hoose this parti ular measure of the des riptive omplexity of a path be ause the size of a natural representation of a Dubins normal path is proportional to its intri a y. Note that in general, the intri a y and length of 8 Figure 2.1: Short subpaths (bla k) are ontained between ones (dotted) emanating from the endpoints (boxes). a Dubins path are independent: a Dubins path an have high intri a y and low length (and vi e versa). (a) LCL forbidden. (b) CCL forbidden. ( ) Middle ar must be ≥ pi. (d) CCCC forbidden. Figure 2.2: Dubins' length redu ing perturbations ontinuously deform a path from solid to dotted. By using the length redu ing perturbations shown in Figure 2.2, Dubins keeps the set of anoni al paths small. Theorem 2.1. [16℄ The stru ture of a shortest bounded- urvature path is a subsequen e of CLC or CCC. If its stru ture is CCC, the middle C-segment is longer than π. Boissonnat et al. prove the above theorem using ontrol theory [9℄. Although their proof is more on ise, it la ks the dire t geometri reasoning of the earlier proofs. 9 2.2 Paths Amid Obsta les We now onsider results about path planning in the presen e of obsta les. We begin our overview with two results that demonstrate that path planning is NP-hard in general ontexts. Then we survey three algorithms that are guaranteed to nd paths (when they exist) in general ontexts. These are the best results with whi h to ompare our new results be ause our new results also provide guarantees in general ontexts. We note that, unlike the algorithms developed in this thesis, these algorithms will nd paths of unbounded omplexity and length. However, also unlike the algorithms developed in this thesis, they also take super-polynomial time (in the worst ase, singly- or doubly-exponential in the size of the input). We then review results that nd paths in restri ted domains in polynomially bounded time. In these restri ted settings, the des riptive omplexity of the desired path is polynomially bounded by the omplexity of the environment. Hen e, our results generalise these results in that (a) they nd paths in more general ontexts and (b) when restri ted to these domains, our results also nd paths in time that is polynomially bounded in terms of the environment omplexity (i.e. we an remove expli it referen e to k and λ from the bound on the run time), albeit with asymptoti ally worse performan e. Finally, we survey three approximation results that nd paths in general ontexts. To nd an approximation of a shortest path, it su es to nd a path that is a slight distortion of a shortest path. In the ase of bounded- urvature motion planning, the guarantees that a path will be found by the approximation results are weak. In hapter six, we ombine the idea behind these approximation results with new te hniques found in this thesis to get an approximation algorithm with stronger guarantees. 2.2.1 Hardness Results The results reviewed in this se tion ee tively pla e a lower bound on the time required to nd a shortest path: Canny and Reif show that nding a 3-dimensional Eu lidean shortest path (3ESP) is NP-hard [13℄, and Reif and Wang argue that nding a 2- dimensional bounded- urvature shortest path (2BSP) is NP-hard [23℄. Both redu tions are on eptually similar, so we outline the ommon ore. Both papers redu e solving a 3-SAT instan e with n variables and m lauses to nding the shortest path amid obsta les. These hardness results not only suggest that it is impossible to e iently nd an exa t solution, but they bound how lose an e ient algorithm an ome to the exa t solution: the redu tion of 3-SAT to 3ESP shows that it is NP-hard to nd a path that is at most 2−O(n) longer than the shortest path, where n is a measure of the problem size. We an split the set of feasible paths into homotopy lasses. A representative path of a homotopy lass is a shortest path in the homotopy lass. In the redu tions to 3ESP and 2BSP, ea h homotopy lass has exa tly one representative path. Roughly speaking, ea h representative path orresponds to a variable assignment in an instan e of 3-SAT, whi h we denote with a binary string of length n. The redu tions rst reate 10 Θ(2n+m) homotopy lasses su h that the dieren e in the length between two dierent representative paths is at most 2−Ω(n 2) . Then for ea h lause of the instan e of 3-SAT, obsta les are introdu ed so that the length of representative paths that do not satisfy the lause be ome at least 2−O(n) units longer than representative paths that do satisfy the lause. Hen e, if there is a shortest path within 2−O(n) of a threshold, the instan e of 3-SAT is satisable be ause that path satises every lause. One riti ism of the 2BSP onstru tion is that it requires all representative paths to pass through holes of innitesimal width. Later in this survey, we introdu e two measures of problem instan e ill- onditioning: pre ision sensitivity and path robustness. The 2BSP onstru tion is extremely pre ision sensitive and the representative paths are non-robust. 2.2.2 General Domains The algorithms in this se tion are mostly of theoreti al interest be ause they require exponential spa e and (at least) exponential time. However, they provide a upper bound on the omplexity of various problems. Denoted ℜ(+,×), the rst order theory of the reals is the rst-order logi with real variables, inequalities, addition, and multipli ation. Ea h result in this se tion reates a formula in ℜ (+,×) that satisable if and only if the underlying problem is solvable. Theorem 2.2. Satisability of a formula in ℜ(+,×) of length l, degree d, and with v variables an be tested in time (dl)2 O(v) [15℄ and spa e (dl)O(v) [7℄. These redu tions to ℜ (+,×) on eptually work the same way. At the ore of ea h result is an analysis that shows that the desired path be omes a sequen e of anoni al subpaths when split by its onta t with the environment. The redu tions use real variables to represent potential environment onta ts. They use lauses to (a) enfor e the feasibility of a anoni al subpath between onse utive environment onta ts and (b) guarantee the optimality of the entire path. Eu lidean Shortest Path Reif and Storer des ribe how to test if there exists a path Π that avoids three-dimensional polyhedral obsta les su h that the length of Π is less than some given algebrai number [24℄. The runtime of their algorithm is singly exponential in the problem size, whereas the previous best known result is doubly exponential. First they partition the polyhedral obsta les into onvex regions, alled islands, whi h introdu es new ina essible internal fa es. They partition the obsta les be ause the shortest path along an island's surfa e an be found in polynomial time [28℄. They want to minimise the size s of the de omposition be ause the number of real variables in the redu tion to ℜ (+,×) is proportional s. However, it is NP- omplete to nd the smallest su h partition of a two-dimensional polygon [19℄. So Reif and Storer suggest the brute-for e approa h of enumerating all possible partitions in exponential time. 11 Figure 2.3: A shortest path (thi k) omposed of dire t paths (solid) and onta t paths (dashed). A dire t path is a line segment whose interior does not interse t any obsta les (see Figure 2.3). A onta t path is a shortest path ontained on an island's a essible fa es. Finally, a fundamental path is a dire t path followed by a onta t path, either of whi h may have length zero. Reif and Storer observe that (a) ea h turning point on a shortest path o urs on an obsta le edge and (b) between onse utive turning points, the shortest path either travels through free spa e or along an obsta le fa e. These observations motivate their shortest path normal form: there exists a shortest path omposed of k fundamental paths. Determining if a dire t path is obsta le free or if there is a onta t path of a ertain length an both be he ked with a ℜ(+,×) formula of polynomially bounded size. By introdu ing variables for ea h of the k (possibly zero length) fundamental paths on the shortest path, Reif and Storer ombine these formulas to get a formula that is satisable if and only if there is a feasible path no longer than a given length. Kinodynami Qui kest Traje tory Canny et al. [12℄ redu e nding the qui kest kinodynami traje tory in two dimensions under the L∞ norm to the satisability of ℜ(+,×). As des ribed in Se tion 2.1, they develop a losed form for the qui kest traje tory in the absen e of obsta les between two ongurations under the L∞ norm alled a anoni al segment. Central to their approa h is a theorem whi h states that, independent of ve tor norm, there is always a loop-free qui kest traje tory starting from and ending at rest. By loop, they mean a traje tory that begins and ends at the same position, regardless of the parti ular starting and ending velo ities. To prove this theorem, they rst show how to reate a new traje tory that tra es the path of a given traje tory. This new traje tory starts at rest and greedily a elerates whenever possible until it at hes the original traje tory or rea hes the end of the path. At every point on the path, the magnitude of the velo ity of the tra ing traje tory is less than the magnitude of 12 the velo ity of the original traje tory be ause the new traje tory follows the original traje tory if the traje tories ever oin ide. This allows the authors to bound the time dieren e between the two traje tories at any point p on the path in terms of the velo ity dieren e at p and maximum a eleration bound. They then use this bound to show that spli ing out the loop by oming to a omplete stop, instantaneously turning, and starting from rest is no slower than following the loop. By using a ontinuous deformation argument, Canny et al. show that a qui kest traje tory an be viewed as a sequen e of anoni al segments. They also give a simple argument bounding the number of anoni al segments: if a traje tory tou hes a wall twi e, then we an spli e out the middle and greedily follow the wall with no penalty; if a traje tory tou hes a orner twi e, then we have a loop that an be eliminated. This means that the total number of anoni al segments is at most linear in the omplexity of the environment. The losed form for anoni al paths and small number of anoni al segments on a qui kest traje tory give us a redu tion to the rst order theory of the reals. Bounded Curvature Path Feasibility Fortune and Wilfong determine if a feasible bounded- urvature path exists in the pres- en e of polygonal obsta les with a redu tion to ℜ(+,×) [17℄. Unlike the other redu tions in this se tion, the variables in the redu tion do not orrespond to one parti ular path, but a ontinuous range of paths. This representation of paths is so ompa t that it not lear that one parti ular path from the range an be extra ted e iently. Fortune and Wilfong use path normalisation to redu e the problem of nding a feasible path to nding regions of the environment boundary that an be rea hed. They rst show that if there is a feasible bounded urvature path amid obsta les from a start onguration to a terminal onguration, there is a feasible Dubins path amid obsta les from the same start onguration to the same terminal onguration. Then, they for e every C-segment to tou h an obsta le. To do this, Fortune and Wilfong assume without loss of generality that the obsta le-free spa e is bounded : this an be a hieved by surrounding the obsta les with a large bounding box; by making the box large enough, the original problem admits a feasible path if and only if the new problem admits a feasible path. We des ribe Fortune and Wilfong's path normalisation in greater detail in Chapter 3, where we extend their normalisation. Fortune and Wilfong dene a jump as a Dubins path whose stru ture is a subse- quen e of CLC. By splitting a normalised Dubins path where C-segments tou h the environment, the path is de omposed into a sequen e of jumps. In this sense, a jump repla es the notion of a anoni al subpath in the previous results. The dieren e be- tween the denition of a jump and a anoni al subpath is slight: jumps annot have stru ture CCC whereas anoni al subpaths an. Fortune and Wilfong use jumps in- stead of anoni al subpaths to redu e the number of ases that they onsider in their analysis. In the next hapter, we use a more restri tive notion of a jump to further de rease the number of ases that we onsider in our analysis. 13 A feature refers to some parti ular orner or wall of the environment. Ea h onta t that a feasible path has with the environment only has one degree of freedom: where a path tou hes a wall, the point of onta t an lie anywhere on the wall (a ontinuous range), but the orientation of onta t must be parallel to the wall; where a path tou hes a orner, the point of onta t is xed, but the orientation of onta t an lie anywhere in a ontinuous range. Hen e, we an ompa tly represent ranges of rea hable onta t with an interval: at walls, we use an interval of the wall augmented with one of two possible dire tions; at orners, we use an interval of orientations. W θ C (a) Destination ongurations point to the left. W θ C (b) Destination ongurations point to the right. Figure 2.4: A rea hable interval (dashed) on wall W from an start onguration θ (dotted) from a orner C. Fortune and Wilfong rst des ribe all of the ongurations at a feature that an be rea hed by a jump from a single onguration at another feature. In Figure 2.4, for example, a single onguration θ at orner C an rea h two intervals of ongurations at wallW using a single jump. This denes the propagation by one jump of a onguration to a set of rea hable intervals. Building on this, Fortune and Wilfong des ribe how to propagate an interval of rea hable ongurations to a family of rea hable intervals. Let Ij be the family of rea hable intervals that an be rea hed from the start onguration using at most j jumps. Then Ij+1 an be derived from Ij using interval propagation. Fortune and Wilfong's redu tion to R (+,×) nds the smallest I∗ that ontains the start onguration θ and is losed with respe t to interval propagation. This losure I∗ orresponds to the xed-point of Ij . Note that there is no guaranteed rate of onvergen e to the xed-point I∗. That is, every onguration in I∗ is rea hable by a path of nite intri a y, but this intri a y may be arbitrarily large. Related to this observation, the rea hable intervals of Ij are all losed but the intervals of I∗ may be open be ause ea h endpoint of an interval in I∗ is a limit, whi h may or may not be rea hed. To keep the representation of I∗ su in t, Fortune and Wilfong merge rea hable intervals in I∗ whenever they interse t. A ore result of their paper is that I∗ ontains a polynomially bounded number of intervals after merging. Fortune and Wilfong on lude with a redu tion to ℜ(+,×) that denes I∗: they use real variables to represent intervals of I∗, various formulas to lose I∗ with respe t to jumps, and other formulas to spe ify that I∗ is the smallest su h set with an interval ontaining the given start onguration. 14 2.2.3 Restri ted Domains The study of bounded- urvature paths in restri ted domains started as a way of solving problems of real-world interest [29℄. In the fa e of Reif and Wang's NP-hardness result, restri ted domains are used to regain tra tability and to understand what makes this motion planning problem di ult. Moderate Obsta les Agarwal et al. [2℄ give an algorithm for nding the shortest path amid moderate ob- sta les, where an obsta le is moderate if it is simple, onvex, and our point robot an tra e its boundary (see Figure 2.5). This is a very restri ted problem: if there were no orientation asso iated with the start and terminal onguration, then this problem is equivalent to the Eu lidean shortest path problem in two dimensions. initial goal Figure 2.5: Some moderate obsta les. The majority of this paper develops a strong hara terisation of shortest paths amid moderate obsta les, from whi h a straightforward algorithm follows. First a few denitions: an O-segment is a ontiguous pie e of an obsta le boundary; a terminal ir le/C-segment is tangent to either the start or the terminal onguration; a an- hored ir le/C-segment is tangent to two obje ts, ea h of whi h is either an obsta le or terminal ir le; and a oating ir le/C-segment tou hes only one obsta le or terminal ir le. Agarwal et al. show that on every shortest path amid moderate obsta les (see Figure 2.6) 1. if there are three C-segments in a row, then either the rst or last C-segment is terminal; 2. all C-segments are either an hored or oating; 3. there are at most two oating C-segments when there are exa tly two, they o ur onse utively; 4. and the entre of the rst (respe tively last) oating C-segment is at most two units from the start (respe tively terminal) onguration. The approximation algorithm of Agarwal et al. treats an hored ir les and oating ir les as pseudo-obsta les: like obsta les, they an be travelled to and along, but unlike 15 initial goal Figure 2.6: A oating pair of C-segments. obsta les, they an be passed through. While there are only O(n) an hored ir les, where n is the obsta le omplexity, there are innitely many possible oating ir les. To limit the number of oating pairs onsidered, Agarwal et al. sample the spa e of possible oating pairs uniformly to get O (ε−1) relevant pairs. The upper bound on the number of relevant pairs is independent of the obsta le geometry be ause the pair entres must be lose to the start and terminal ongurations and the obsta les are moderate. Agarwal et al. then onstru t a weighted visibility graph, where the nodes are the ongurations (and their dire tional reversals) shared between obsta les, an hored ir- les, relevant pairs, and the tangents between them. They add a weighted edge between two nodes if some O-, C-, or L-segment joins them su h that the segment does not pass through an obsta le or another node. The weight of the edge is the shortest path found between nodes. They show that the visibility graph an be onstru ted and sear hed in O ( (n+ ε−1)2 log (n+ ε−1) ) time. Boissonnat and Lazard [10℄ rene this result to get an exa t O(n2 logn) time algo- rithm, where n is the omplexity of the moderate obsta les. The essen e of their paper is a more rened hara terisation of shortest paths, whi h redu es the number of pla e- ments of oating pairs. Spe i ally, they show that a oating pair on a shortest path is part of subpath with stru ture XLCCLX ′, where X ,X ′ ∈ {O,CA} and CA is an an- hored ir le. As ea h oating C-segment must tou h an obsta le, there are only O(n4) ombinatorial arrangements for a oating C-segment. Agarwal et al. noted that oating C-segments must o ur lose to the start and terminal ongurations, whi h further redu es the number of ombinatorial arrangements to O(c4), where c is some onstant upper bounding the number of obsta les lose to the start and terminal ongurations. Boissonnat and Lazard also show that there are only a xed number of pla ements of oating pairs for ea h ombinatorial arrangement by analysing the equilibria of a me- hani al system modelling the shortest path through the arrangement. These equilibria orrespond to high, but xed, degree polynomials. This gives an O(n2 logn) time exa t algorithm be ause the time taken to nd the roots of these polynomials is a ounted for by the hidden onstants in the asymptoti notation. 16 Convex En losure Agarwal et al. [1℄ analyse the stru ture of shortest bounded- urvature paths inside onvex polygons. This leads to a polynomial time algorithm. Some of the results from their study of moderate obsta les hold in this domain as well: spe i ally (a) no non-terminal C-segment has length greater than π, (b) every non-terminal C-segment is tangent to the boundary or terminal ir le in at least one point, and ( ) no subpath that ex ludes the rst and last C-segment has type CCC. Agarwal et al. also introdu e the notion of a po ket that on e entered annot be left and vi e versa, whi h substantially redu es the spa e of possible paths. One of the more interesting results in this domain is that an optimal path has at most one non-terminal CC subpath, and any non-terminal C-segment that pre edes (respe tively follows) su h a C1C2 subpath is oriented the same way as C1 (respe tively C2). Hen e, any non-terminal CC subpath denes a turning point. A rigorous hara terisation of the remaining types of paths shows that every optimal path is a subsequen e of CICSCCSCCG where CI ,CG are terminal C- segments. Agarwal et al. a hieve an O(n logn) algorithm with an analysis of C-segment onta t, where n is the number of orners of the onvex polygon. Ahn et al. hara terise the positions inside a onvex polygon that an be rea hed by bounded- urvature paths [4℄. Spe i ally, their analysis ignores the orientation and just fo uses on lo ation. By s aling the polygon, they assume that the urvature bound is one. Their results rely on two key lemmas: the Pestov-Ionin Lemma that gives a su ient ondition for a losed bounded- urvature ir uit to ontain a unit radius dis , and the Po ket Lemma proved by Agarwal et al. [1℄. Ahn et al. start with an analysis of the region that is rea hed from a onguration on the polygon boundary. Then for a given start onguration inside the polygon, they onsider four anoni al traversals to ea h polygon edge, whi h redu es the rea hable area to regions just overed. The entire rea hable region is found by iterating over all polygon edges and adding regions that are dire tly a essible from the start onguration (i.e. rea hable via one C- and one L-segment). They on lude by showing that the rea hable region has O(n) omplexity, where n is the number of orners of the polygon. Narrow Corridors Bereg and Kirkpatri k look for bounded- urvature paths in a domain akin to non- bran hing roadways [8℄. Again, the environment is s aled so that the urvature bound is one. If Π is a feasible path, the orridor about Π is the region swept out as the entre of a dis of xed diameter w tra es Π. A orridor C is redu ible if some other feasible path Π′ has an asso iated orridor C ′ ontained in C (see Figure 2.7). In a redu ed orridor, the path followed by the tra ing dis has bounded- urvature (its minimum radius of urvature is w/2). Bereg and Kirkpatri k try to nd paths from one end of the orridor to the other. They restri t their attention to irredu ible orridors with width less than two be ause, if the width is greater or equal to two, the path tra ed by the dis is a bounded- urvature traversal of the orridor. The ore result of Bereg and Kirkpatri k is a width threshold τ su h that every 17 Figure 2.7: A orridor (left) and its redu ed orridor (right), both of whi h are tra ed by a dis following a path. 1 1 1 Figure 2.8: A robot with a turning radius of one annot traverse this orridor. orridor with w > τ an be traversed and for every w < τ there are orridors of width w that annot be traversed (see Figure 2.8). The proof that orridors with w > τ admit a traversal is provided by a greedy algorithm. 2.2.4 Approximation Algorithms The hardness results presented earlier motivate the sear h for e ient approximation algorithms. All of the (1 + ε)-approximation algorithms des ribed below use a weighted visibility graph: the nodes orrespond to potential path onta t with the environment; the range of possible path onta t is sampled with a granularity that is monotoni in ε; edges between nodes orrespond to the shortest anoni al subpath between onta ts; the shortest path in the visibility graph orresponds to a path that is at most (1 + ε) times longer than the desired optimal path. Eu lidean Shortest Path The rst approximation algorithm that we dis uss nds an approximation to the un- onstrained shortest path in three dimensions amid arbitrary polyhedral obsta les. In this setting, the edges of polyhedral obsta les play an important role. We use refer to an edge of an obsta le as a ridge to distinguish it from an edge of a visibility graph. Eu lidean shortest paths bend at ridges and only visit ea h a ridge at most on e. 18 Papadimitriou partitions ea h ridge into fragments, where ea h fragment represents a potential path onta t with a ridge [21℄. His subdivision is highly non-uniform in the sense that fragments of the same ridge will have quite dierent lengths. Ea h node in his visibility graph orresponds to a fragment, and an edge between nodes orresponds to the shortest, feasible, straight-line path between two fragments. A path P in the visibility graph orresponds to a Eu lidean path Π: ea h edge in P orresponds to a hop between fragments; to onstru t Π, we glue these hops together we an transition between hops that o ur onse utively on P by following the fragment that they both tou h. By keeping the size of ea h fragment relatively small, the length of Π is dominated by its hops between fragments rather than its transitions between onse utive hops. In this ase, Π is a good approximation of the Eu lidean shortest path. Papadimitriou partitions a ridge into fragments as follows. He rst identies the point p on the ridge losest to the start position. The distan e d from the start position to p lower bounds the length of any path from the start position to the ridge. The smallest fragment f of the ridge ontains p. The length of f is a fun tion of d so that the error in approximation due to gluing hops together via f is dominated by the length of the path rea hing f . Spe i ally, the size of this fragment is proportional to ε and inversely proportional d and the total number of ridges n (the maximum number of fragments visited by a shortest path). The size of a ridge fragment in reases geomet- ri ally the further it gets from the smallest fragment: Papadimitriou assumes that the oordinates of ea h ridge endpoint are spe ied in xed-point arithmeti representation with at most m digits; this limited pre ision implies that the length of a ridge is at most 2O(m) and the distan e from the start position to a ridge is at least 2−O(m); hen e, ea h ridge subdivides into a polynomially bounded number of fragments. Rened Analysis Papadimitriou omputes within an algebrai framework, but his analysis assumes a bit model representation of input (xed-point). Choi et al. arry out a detailed analysis that substitutes oating point arithmeti of su ient pre ision for real arithmeti [14℄. In [26℄, Choi et al. introdu e a bit model parameter δ−1 that measures problem instan e di ulty. This measure is exponential for instan es generated by the redu tion that proves that 3ESP is NP-hard. Choi et al. distinguish between the ombinatorial and numeri al aspe ts of 3ESP; they say that two paths in 3ESP are ombinatorially distin t if they onta t a dierent sequen e of obsta le edges. Let d1 be the length of shortest path and d2 be the length of the shortest path that is ombinatorially distin t from the path orresponding to d1. They dene the pre ision sensitivity of the problem as δ ≡ (d2−d1)/d1. In the bit model of omputation, the runtime of the approximation algorithm is polynomially bounded in n, m, ε−1, and δ−1. 19 Kinodynami Shortest Path The kinodynami approximation algorithms do not nd an approximation to the short- est path. Rather they nd a (1 + ε)-approximation to the shortest δ-safe path: a path is δ-safe if every point on the path is at least δ units away from every obsta le. Spe if- i ally, these algorithms are not true shortest path approximation algorithms be ause, in general, the shortest δ-safe an be arbitrarily longer than the shortest path. The restri tion to δ-safe paths is exploited algorithmi ally. Intuitively, there is a range of feasible paths surrounding a shortest δ-safe path Π. In order to approximate Π, it su es to sear h for a feasible path Π′ in the obsta le free region surrounding Π. The safety of Π allows us to restri t our attention to a Π′ that is omposed of a sequen e of anoni al subpaths. A drawba k of this approa h is that Π′ may not be δ-safe, even though Π is δ-safe. One hallenge in approximating the shortest δ-safe path is hoosing an appropriate set of ongurations to use as nodes in the visibility graph. In parti ular, it is insu ient to sample the surfa e of the obsta les be ause a δ-safe path never tou hes the obsta le boundary. Instead, Reif and Wang use non-uniform grid de omposition of free spa e [25℄. This leads to the asymptoti ally state-of-the-art polynomial time algorithm for approximating the kinodynami shortest path. Their free spa e box-de omposition method is very similar to an o t-tree de omposition of free spa e: they start with a d-dimensional ube that ontains all of the obsta les; if a ube ontains part of an obsta le, then they re ursively split it into 2d ubes, ea h with half the side length of the original; they never de ompose a ube with side length less than cδ, where c is a onstant; and if a ube shares a fa e with a ube that has a side length more than twi e as large, then they split the larger ube. The last rule guarantees ne sample granularity near obsta les. Reif and Wang uniformly pla e O(1/εd−1) sample position points along ea h box fa e surrounded by empty boxes, and they uniformly sample all possible velo ity ve tors with O(1/εd) velo ities. The nodes of the visibility graph are the Cartesian produ t of sample positions and sample velo ities. Edges are added between nodes on a fa e and nodes on the fa es of an extended box ontaining the fa e, whi h is essentially the union of the boxes ontaining that fa e. The length of an edge orresponds to the length of a anoni al path between the ongurations joined by the edge. In general, anoni al paths annot be omputed dire tly be ause there is no simple losed form (ex ept for the L∞ norm). So, an approximation to the anoni al path is substituted. The set of approximate anoni al paths is independent of the parti ular obsta le geometry and an be pre omputed. The side length ratio limit of the box-de omposition redu es the number of approximate anoni al paths that are pre omputed. Bounded-Curvature Shortest Path The length redu ing deformations used by Dubins to hara terise bounded- urvature shortest paths in the absen e of obsta les are ontinuous. Hen e, his results have immediate onsequen es amid polygonal obsta les. Ja obs and Canny expli itly state 20 this in their work on approximating shortest bounded- urvature paths [18℄. Theorem 2.3. Let Π be a shortest bounded- urvature path in the presen e of polygonal obsta les. The ongurations where Π just tou hes the environment partition Π into ollision free subpaths. Ea h of these subpaths has the stru ture of a shortest bounded- urvature path in the absen e of obsta les (see Theorem 2.1). We say that a path Π is JC-normal if splitting Π where it just tou hes the envi- ronment results in a sequen e of subpaths that have the form of a shortest bounded- urvature path in the absen e of obsta les. Rather than nding an approximation to the shortest path, the bounded- urvature approximation algorithms nd a (1 + ε) approximation to the shortest ε-robust path: we say that a JC-normal path Π is ε-robust if ea h point where Π just tou hes the environment onta t an be perturbed (simultaneously and independently) by ε without hanging the feasibility or stru ture of Π. By perturb we mean that if Π just tou hes a wall, we an slide that onta t by ε along the wall (see Figure 2.9(a)), and if Π just tou hes a orner, we an pivot that onta t by ε radians at the orner (see Figure 2.9(b)). This restri tion to ε-robust paths allows us to restri t our node set: if we sample the spa e of potential path onta ts with a granularity proportional to ε (dots and arrows in Figure 2.9), an ε-robust path an be deformed so that every environment onta t o urs at a sample point, in whi h ase, a anoni al subpath joins onse utive onta t points. We make our granularity proportional to ε to ensure that the resulting path is at most (1 + ε) times longer than the original path. This argument is explained in greater detail in Chapter 6, where we des ribe a new result that extends the previous approximation algorithms. ε (a) The path's wall onta t annot be perturbed by ε. ε (b) The path's orner onta t annot be per- turbed by ε. Figure 2.9: Environment onta ts that not ε robust. To reate the nodes of their visibility graph, Ja obs and Canny [18℄ sample the potential path onta ts at a feature with granularity proportional to ε (see Figure 2.9). They then give two methods of onstru ting the weighted edges: one guarantees that the orresponding path is robust and the other does not. Let n be the number of orners and w be the total length of the walls. The total runtime of the graph onstru tion and 21 sear h for the robust approa h is O ( (n+ w)2 ε−4 + n4 logn ) whereas the total runtime for the non-robust approa h is O ( (n+ w)2 ε−4 + n2 (n+ w) ε−2 logn ) . Wang and Agarwal revise the algorithm of Ja obs and Canny to get a tighter asymp- toti bound [3℄. Their major ontribution is eliminating the asymptoti dependen e on w. We say that a path onta t c is witnessed by a point p if cp is a unobstru ted line segment of length no more than 15. Wang and Agarwal prove that every path onta t with a wall on a shortest robust path is witnessed by a orner. Only O(n) length of wall is witnessed by orners, where n is the number of orners. Wang and Agarwal also use a dierent method to generate the edges of the weighted visibility graph. This faster method for generating weighted visibility edges redu es the runtime omplexity to O(n2ε−4 log n). 22 Chapter 3 Normal Forms Path normalisation plays a riti al role in our design and analysis of path-planning algorithms. Spe i ally, the stru ture imposed on paths by normalisation dire ts our approa h to nding paths, our proof that the approa h is orre t, and our analysis of the e ien y of the approa h. In this hapter, we des ribe how to normalise paths so that every normal path has a dis rete des ription: this allows us to perform a ombina- torial sear h for a path, to make this sear h exhaustive, and to bound the run time of the sear h by bounding the size of its sear h spa e. Considering the vital role that nor- malisation plays in this thesis, it is not surprising that all previous bounded- urvature path-nding results also rely on normalisation: the shortest-path results impli itly nor- malise paths by looking for optimal paths (see Se tion 2.1) and the feasibility result expli itly des ribes how to normalise paths (see Se tion 2.2.2). To start this hapter, we des ribe a minor modi ation to the normalisation of Fortune and Wilfong [17℄. The spa e of all su h FW-normal paths is ontinuous. After that, we des ribe our major extension to this normalisation. The spa e of all su h BK-normal paths is ountable and, hen e, systemati ally sear hable. The way that we get a BK-normal path from a FW-normal path an be illustrated with a simple analogy. A FW-normal path is like a plumber's snake that has been threaded through a sequen e of pipes: every bend is onstrained by a pipe, but the bends retain some freedom, whi h allow the snake to be twisted. To make su h a path BK-normal, we an hor the end of the plumber's snake and twist the snake until its elasti ity is stret hed to its breaking point. The ombination of internal onstraints (elasti ity) and external onstraints (pipes) removes all freedom from the plumber's snake. This total la k of freedom allows us to des ribe the snake in terms its onstraints (where it tou hes the pipes and how it bends). Whereas this des ription of the snake has ontinuous elements, our des ription of an a tual BK-normal path is dis rete be ause the a tual path onstraints have a dis rete des ription. 23 3.1 Fortune and Wilfong Normal Form We exploit path normalisation to simplify our algorithm design and improve our algo- rithm's e ien y. We want to hoose our normal form so that the spa e of normal paths is small and normal paths are easy to nd and des ribe. These two goals ompete in the sense that a hieving one omes at the expense of the other: as we make our normal form more restri tive, the more intri ate the simplest desired normal path be omes, but the smaller the spa e of all normal paths be omes. We make this ompromise expli it by quantifying how the intri a y of the desired path in reases as we limit our attention to more restri tive normal forms (and smaller path spa es). Earlier, we surveyed prior bounded- urvature path normalisations (see Se tions 2.1 and 2.2.2). Re all that a Dubins path is a dierentiable path made of C-segments (ar s of unit-radius ir les) and L-segments (straight-line segments). Fortune and Wilfong des ribe how to turn an arbitrary feasible bounded- urvature path into a Dubins path in the presen e of obsta les [17℄. Hen e, we an restri t our path sear h to Dubins paths. Also re all that we dene the intri a y of a Dubins path as the number of its (non- zero) segments. We hoose this measure be ause the length of a natural des ription of a Dubins path is proportional to the number of its segments. In this sense, the intri a y of the simplest desired Dubins path is a lower bound on the run time of any algorithm that returns an expli it des ription of a feasible Dubins path. After turning a given bounded- urvature path into a Dubins path, Fortune and Wilfong deform the result to onstrain its turns. Intuitively, these deformations either eliminate a path C-segment (see Figure 3.1(b)) or push it into onta t with the envi- ronment (see Figure 3.1( )). On e this phase nishes, ea h internal C-segment tou hes some obsta le (there may be a C-segment at the start and end that do not tou h an obsta le). This phase an be applied to any Dubins path. Fortune and Wilfong argue the entire pro ess in reases the path intri a y by a fa tor of at most n (the number of obsta le orners). (a) Initial Dubins path. (b) Pop out C-segments. ( ) Pull in C-segments. (d) Push out C-segments. Figure 3.1: Deformations used in FW normalisation. 24 We add one more phase to Fortune and Wilfong's normalisation: if some π-length subar does not tou h an obsta le, we slide a π-length subar (not ne essarily the same subar , but a related one) like part of a trombone until it tou hes an obsta le (see Figure 3.1(d)). Like Fortune and Wilfong, we assume without loss of generality that the obsta le-free spa e is bounded. Hen e, the sliding subar eventually tou hes an obsta le. By areful hoi e of what fragment to slide, we guarantee that the re- maining, unperturbed portions of the original C-segment also tou h an obsta le. Ea h time we slide a subar , we break one C-segment into at most ve path segments (see Figure 3.1(d)). Hen e, we at most quintuple the intri a y of the path in the worst ase. Theorem 3.1. [17℄ Suppose that there exists a feasible Dubins normal path of intri a y k from start onguration αs to terminal onguration αt. Then there exists a feasible Dubins normal path of intri a y at most 5nk from αs to αt su h that 1. every internal C-segment tou hes an obsta le and 2. every subar of length π tou hes an obsta le. We refer to any Dubins path with the above properties as FW-normal. Like Fortune and Wilfong, we refer to a FW-normal path with stru ture CLC (ea h segment an be zero length) as a jump. Our denition of jump diers from Fortune and Wilfong's denition of jump in one respe t: we now require that every C-segment on a jump has length at most π. α ωβ (a) Path is a jump from α to ω or a jump from α to β followed by a jump from β to ω. p q (b) The point p just tou hes an obsta le but q does not. Figure 3.2: Representing a FW-normal path as a sequen e of jumps. Jumps are important be ause we represent FW-normal paths as a sequen e of jumps. For example, the FW-normal path in Figure 3.2(a) is a jump from α to β followed by a jump from β to ω. The following lemma states that any FW-normal path an be represented as a sequen e of jumps. In general, there are several ways to represent a FW-normal path as a sequen e of jumps: in Figure 3.2(a), the path from α to ω is also a single jump. We now remove ambiguity in how we represent a path by jumps. We say that a point p of a path Π just tou hes an obsta le, if p tou hes an obsta le and some point on Π arbitrarily lose to p does not tou h an obsta le. For example, the point p in Figure 3.2(b) just tou hes an obsta le, but the point q does not just tou h an obsta le. We an obtain a unique representation of Π by splitting it at all of the points where Π just tou hes the environment. This results in a nite sequen e be ause ea h segment of Π just tou hes ea h feature at most twi e. 25 We say that a jump is anoni al if no point in its interior just tou hes an obsta le. Referring ba k to Figure 3.2(a), the jump from α to ω is non- anoni al but both jumps from α to β and from β to ω are anoni al. We say that a sequen e of jumps 〈Ji〉 is a anoni al representation of a path Π if (a) ea h jump Jj is anoni al, (b) Jj and Jj+1 meet at a point where Π just tou hes the environment, and ( ) Π is the on atenation of the jumps in 〈Ji〉. The next lemma bounds the size of a path's anoni al representation in terms of the intri a y of the path and the omplexity of the environment. Lemma 3.2. Suppose that there exists a Dubins path from start onguration αs to terminal onguration αt with intri a y k. Then there exists a FW-normal path from αs to αt whose anoni al representation onsists of O(nk + n 2) jumps. Proof. By Theorem 3.1, let Π be a FW-normal path from αs to αt with O(nk) intri a y. To a hieve the desired bounds on the size of its anoni al representation, we rst remove some redundan y from Π. Let 〈Ji〉 be the anoni al representation of Π. If Jj = Jl, for j < l, the subpath orresponding to 〈Jj , . . . , Jl−1〉 forms a loop (it begins and ends at the same onguration), in whi h ase we remove the subpath from Π and the subsequen e from 〈Ji〉. Let 〈J ′i〉 be the result of removing all su h loops. Let Π′ be the on atenation of jumps in 〈J ′i〉. Clearly, Π′ is FW-normal and 〈J ′i〉 is its anoni al representation. To prove this lemma, it su es to show that the length of 〈J ′i〉 is O(nk + n2). We rst bound the number of jumps of 〈J ′i〉 that onsist of more than one non-zero segment: Π′ has intri a y O(nk) be ause it is a subpath of Π; hen e, Π′ has O(nk) transitions from one non-zero length segment to another; therefore, there are O(nk) jumps of 〈J ′i〉 that onsist of more than one non-zero segment be ause ea h su h jump ontains at least one su h transition of Π′. Now we bound the number of jumps of 〈J ′i〉 that onsist of exa tly one non-zero segment: there are O(1) anoni al jumps from one feature to another feature that onsist of exa tly one segment; hen e, there are O(n2) unique anoni al jumps that onsist of exa tly one segment; therefore, there are O(n2) jumps of 〈J ′i〉 that onsist of exa tly one segment be ause J ′j 6= J ′l , for j < l. (a) There is at most one L- segment from one oriented ir- le to another. θ (b) There are two oriented unit-radius ir les tangent to θ. θ φ ( ) There are at most four CLC-stru ture paths from θ to φ. Figure 3.3: Observations leading to our jump representation. Our goal is to develop a normal form where every normal path has a dis rete de- s ription. We just illustrated that a path an be represented as a sequen e of jumps. 26 If every jump in su h a sequen e has a dis rete des ription, the path has a dis rete de- s ription. Before normalising a path to give its jumps a dis rete des ription, we argue that every jump has a su in t des ription: its rst onguration, its last ongura- tion, and a detailed des ription of its stru ture. Re all that the stru ture of a jump is CLC, where any segment an have zero length. We view the L-segment of a jump as a transition from the oriented ir le underlying the rst C-segment to the oriented ir le underlying the se ond C-segment (see Figure 3.3(a)). This transition is uniquely dened by the oriented ir les be ause there is at most one L-segment from one ori- ented ir le to another. Note that there are two oriented unit-radius ir les tangent to any onguration (see Figure 3.3(b)). Hen e, a jump from a onguration θ to a onguration φ is a transition from one of two ir les tangent to θ to one of two ir les tangent to φ (see Figure 3.3( )). Thus, there are at most four possible jumps from θ to φ. To ompletely spe ify a jump, we distinguish between these four possibilities using a more rened notion of path stru ture that we all the signed stru ture of a path: we augment ea h C in the stru ture with a supers ript indi ating the orientation of its orresponding C-segment `+' for lo kwise and `-' for ounter lo kwise. The above observations imply that a jump is ompletely determined by its rst onguration, its last onguration, and its signed stru ture (one of C+LC+, C+LC−, C−LC+, and C−LC−). In the next orollary, a onta t onguration of a path Π refers to either the rst onguration on Π, the last onguration on Π, or a onguration where Π just tou hes the environment. Corollary 3.3. Suppose that there is a Dubins path from onguration αs to ongu- ration αt with intri a y k. Then there exists a FW-normal path Π from αs to αt that an be represented as sequen e of onta t ongurations 〈θi〉 and a sequen e of signed stru tures 〈Γi〉 su h that 1. the ith jump in the anoni al representation of Π is the jump from θi to θi+1 with signed stru ture Γi, 2. the lengths of 〈θi〉 and 〈Γi〉 are O(nk + n2). 3.2 Combinatorial Augmentation We now dene new normal form where ea h normal path has a dis rete des ription. This dis rete des ription is an extension of the path representation stated in the pre- eding orollary. The potentially non-dis rete elements in the path representation of Corollary 3.3 are the onta t ongurations. In this se tion, we des ribe how to deform a path in a way that ea h onta t onguration has a dis rete des ription. In general, a onguration has three degrees of freedom be ause it an be translated horizontally, translated verti ally, and rotated. However, the onta t ongurations of a FW-normal path are restri ted in the following sense: if a onta t onguration o urs at a orner, its position is xed by the orner but its orientation lies in a ontinuous 27 range; if a onta t onguration o urs at a wall, its position belongs to a ontinuous range (the wall) but its orientation must be parallel to the wall. Intuitively, we dis retise our des ription of a FW-normal path by pushing ea h degree of freedom to its limit. For example, if a onta t onguration o urs at a orner, we may pivot it around the orner (see Figure 3.4(a)); if a onta t onguration o urs at a wall, we may slide it along the wall (see Figure 3.4(b)). Ea h su h deformation arti ially onstrains the freedom of the perturbed onta t onguration: it maintains onta t with a parti ular feature, even though we ould (in many situations) translate the onguration away from its onta t without violating feasibility. (a) Range of possible orner onta ts. (b) Range of possible wall onta ts. Figure 3.4: By requiring a onta t onguration to tou h some feature, it has just one degree of freedom. We all perturbing a onta t onguration in the above way rolling be ause the ir les tangent to the perturbed onguration appear to roll along the surfa e of the environment. In Figure 3.4, we roll a onta t onguration independently of all oth- ers. We now exploit the fa t that we annot independently roll a onta t onguration in general. As the path deforms, its des ription outlined in Corollary 3.3 hanges. Typi ally, these hanges in the des ription are ontinuous (i.e. only the onta t on- gurations hange), but o asionally the hanges are dis ontinuous (for example, the number of jumps in the anoni al representation in reases). Whenever a dis ontinuity o urs, there is a orresponding hange in the stru ture of the path. At this point, we onstrain the path to preserve this new stru ture. This onstraint has a dis rete des ription be ause it refers to the stru ture of the path, whi h is ombinatorial. In- sisting that the path satisfy su h a onstraint ee tively removes a degree of freedom. Eventually the path is over onstrained and no onta t onguration an hange. At this point, ea h onta t onguration is uniquely determined by the onstraints that we impose on the path. Hen e, the resulting path has a purely dis rete des ription. To be more formal, when we roll a onta t onguration, we perturb it ontinuously while maintaining onta t with a spe i feature: at a orner, the onguration will rotate about that orner (see Figure 3.4(a)); at a wall, the onguration will tra e a ontinuous path along that wall (see Figure 3.4(b)). Our insisten e that rolling is ontinuous allows us to keep a path feasible during normalisation: rolling a onguration auses the path to deform ontinuously; by ontinuity, if ex essive rolling makes a path infeasible, there is a smaller amount of rolling su h that (a) the path is feasible and 28 (b) rolling it an arbitrarily small amount more makes it infeasible; at this point, we introdu e a onstraint to ensure that any future rolling keeps the path feasible. One way that we onstrain a path is by de laring a onta t onguration stati . We refer to su h a onguration as an an hor be ause we never roll it. To see one way that we use an hors, note that we annot roll a onguration indenitely (see Figure 3.4): at a orner, if we pivot too mu h, the onta t onguration will be dire ted into an obsta le (whi h annot o ur on a feasible path); at a wall, if we slide too far, the onta t onguration will no longer tou h the wall. We all the ongurations that bound the safe range of rolling at a feature type 1 an hors. There are O(n1) type 1 an hors: O(1) at ea h of O(n) features. By de laring these extreme ongurations an hors, we know that we an safely roll a non-an hor onta t onguration. The other way that we onstrain a path is by restri ting the length of a segment on a jump J in its anoni al representation, as summarised by the next two invariants: 1. on e an L-segment of J has zero length, that segment of J always has that length; and 2. on e a C-segment of J has zero or π length, that segment of J always has that length. To re ord the onstraints due to these invariants, we further rene our notion of stru - ture: we augment ea h letter of the signed stru ture with a subs ript indi ating its length (examples follow shortly). When the length of a C-segment is zero, the C- segment's orientation is irrelevant, so we omit the orresponding supers ript. We all the resulting sequen e the ne stru ture. The above invariants imply that the ne stru ture of a jump in the anoni al representation of a path always be omes more spe i . We take two dierent approa hes to maintaining length restri tions. If a jump on the anoni al representation is over onstrained (at least two of its segments have a length onstraint), we keep the jump stati with a new type of an hor 1 : a type 2 an hor is the rst or last onguration of an over- onstrained jump. There are O(n2) type 2 an hors O(n) possible features to leave from, O(n) possible features to arrive at, and O(1) possible link types. If a jump on the anoni al representation is singly- onstrained (only one of its segments has a length onstraint), we maintain the jump's length onstraint by insisting that the rst and last onguration of a jump roll simultaneously. We refer to a onstrained jump (either singly- or over- onstrained) as a link be ause the jump's onstraints establish a homeomorphism (a ontinuous fun tion with a ontinuous inverse) between the rst and last onguration of that jump. We denote the type of a link by its ne stru ture. To maintain length the onstraints asso iated with a link, we must simultaneously roll the rst and last ongurations of that link. A hain is a sequen e of ongurations where onse utive ongurations are joined by a link. We say that two ongurations 1 A C0LC0 jump along a wall is the one ex eption to this rule: we an typi ally roll both ongu- rations without hanging the jump's ne stru ture, so we do not keep this type of jump stati . 29 are hained to ea h other if they are part of the same hain. This denition is important be ause if θ is hained to ψ, then θ and ψ must roll simultaneously or not at all. We note that being hained denes an equivalen e relation between onta t ongurations: θ is trivially hained to θ by a hain of length one; θ is hained to φ if and only if φ is hained to θ; and if θ is hained to φ and φ is hained to ψ, then θ is hained to ψ. The equivalen e lasses of this relation are the maximal hains of the path. If we roll a onguration θ, we must simultaneously roll every onguration that is hained to θ. Hen e, if θ is hained to an an hor, we annot roll θ. In this ase, we say that θ is moored. Note that every an hor is moored (by a hain of length one), but not every moored onguration is an an hor. Moored ongurations are important be ause they have a dis rete des ription: an moored onguration θ is determined by an an hor and a hain of links leading to that an hor, ea h of whi h has a dis rete des ription. The next two examples illustrate how we roll unmoored onta t ongurations to make them moored. In Figure 3.5(a), we roll ongurationW in a ounter lo kwise manner about orner w until the L-segment on the jump from V to W vanishes. At this point, the jump from V and W is a C+L0C − -type link. In Figure 3.5(b), we simultaneously roll V and W be ause 〈V,W 〉 is a hain. We do this until the rst C-segment on the jump from U to V vanishes. At this point, the jump from U to V is a C0LC + -type link. In Figure 3.5( ), we simultaneously roll U , V , and W be ause 〈U, V,W 〉 is a hain. We do this until a C-segment tou hes orner t. At this point, U is type 2 an hor be ause the jump from t to u is over- onstrained. Hen e,W is moored be ause 〈U, V,W 〉 is a hain. WV U w v u (a) A link from V to W forms. W V U wv u (b) A link from U to V forms. U V W w v u T t ( ) The hain 〈U, V,W 〉 be- omes moored. Figure 3.5: As we roll W in a ounter lo kwise dire tion, we introdu e onstraints whi h ause a hain to grow. In Figure 3.6(a), we roll S ounter lo kwise about s until the L-segment on the jump from S to U tou hes t. At this point the jump from S to U is non- anoni al: in the anoni al representation of the path, the path from S to U is de omposed into a C−LC0-type link from S to T and a C0LC+-type link from T to U . In Figure 3.6(b), we simultaneously roll S, T , and U be ause 〈S, T, U〉 is a hain. We do this until the rst C-segment on the jump from U to W be omes exa tly π long. At this point, the jump from U to W is C+pi LC − -type link. In Figure 3.6( ), we simultaneously S, T , U , and W be ause 〈S, T, U,W 〉 is a hain. We do this until the rst C-segment on the jump from U to W tou hes v. At this point, the jump from U to W is non- anoni al: 30 in the anoni al representation, it splits into a jump from U to V (with ne stru ture C+L0C0) and a jump from V to W (with ne stru ture C +LC−). The jump from U to V is over- onstrained, so the ongurations U and V are type 2 an hors. Hen e S is moored be ause 〈S, T, U〉 is a hain and U is an an hor. S s t u U w W T v (a) The un onstrained jump from S to U be omes non- anoni al. S s t u U w W T v (b) A link from U toW forms. S s t u U w W V T v ( ) A new hain forms and S be omes moored. Figure 3.6: If we roll S in a ounter lo kwise dire tion, it eventually be omes moored. In Figure 3.6( ), the ongurations S and W are no longer hained when a new onta t o urs at v be ause the new jump from V to W is un onstrained. We nd this new un onstrained jump problemati be ause it suggests that W does not have a dis rete des ription (W is not hained to anything other than itself). However, the (non- anoni al) jump from U to W is a singly- onstrained link and U is an an hor. So W does have a dis rete des ription, if we use a non- anoni al representation of the path. To apture this fa t in a way that is onsistent with our anoni al path representation, we introdu e a new lass of type 3 an hors: the rst and last ongurations of a non- anoni al link. Ea h type 3 an hor has a dis rete des ription be ause the interior of every non- anoni al link tou hes an obsta le whi h over- onstrains the link. There are O(n3) type 3 an hors: there are O(1) dierent types of links, O(n) features the link an leave from, O(n) features the link an arrive at, and O(n) features that the interior of the link an tou h. In the examples above, we rolled a onguration until (a) a onguration be ame an an hor, (b) a previously anoni al jump be ame non- anoni al, or ( ) the length of a segment on a jump of the anoni al representation degenerated. We all these types of events path degenera ies. In the last example, we saw that rolling a onguration until a degenera y o urs may break a hain. However, the ongurations in that hain were still related. Lemma 3.4. Let 〈θi〉 be a hain. After rolling a onguration until a degenera y o urs, 〈θi〉 may no longer be a hain. However, 〈θi〉 still satises an important ondition: θj is moored if and only if θl is moored. Proof. If 〈θi〉 is still a hain when we quit rolling, this lemma is obviously true. However, 〈θi〉 will break and no longer be a hain, if a link between two onse utive onta t 31 ongurations on 〈θi〉 be omes non- anoni al. This is the ase that we now onsider. We assume without loss of generality that j ≤ l . The proof of this lemma is indu tive on l. If j = l, this is trivially true. So onsider the ase when j < l. As an indu tion hypothesis, assume that θj is moored if and only if θl−1 is moored. To prove the indu tive step, we onsider two ases. If the jump J from θl−1 to θl is anoni al, then J is a link be ause we preserve the length restri tions on ea h link while rolling. Hen e, θl−1 is moored if and only if θl is moored. Thus, θj is moored if and only if θl is moored by our indu tive hypothesis. If the jump from θl−1 to θl is non- anoni al, then θl−1 and θl are both type 3 an hors. By our indu tive hypothesis, θj is moored be ause θl−1 is an an hor. Trivially, our indu tive step holds be ause θj and θl are both moored. As one of our previous examples showed (see Figure 3.6), the number of non-an hor onta t ongurations may in rease, but only in a very parti ular manner. Lemma 3.5. Let J be a anoni al jump on a path. If J be omes non- anoni al due to rolling, then 1. the interior of J ontains at most one non-an hor onta t onguration; and 2. if the interior of J ontains a non-an hor onta t onguration, then every jump in the anoni al representation of J is a link. Proof. New onta t ongurations on a C-segment of J are type 1 an hors. So any new non-an hor onta t ongurations must o ur on the interior of L-segment of J . If there is more than one onta t on the L-segment of J , then all of the onta t ongurations on the L-segment are type 1 an hors. This proves laim 1. To see laim 2, suppose that the interior of the L-segment of J tou hes an obsta le at p. Then the interior of every anoni al jump K ontained in J does not ontain p. Hen e, either the rst or the last C-segment of K has zero-length. Therefore, K is a link. Rolling an unmoored onguration makes the des ription of a path more dis rete, but it does so at the expense of in reasing the size of its anoni al representation. The next lemma quanties this trade-o. Lemma 3.6. Let Π be a FW-normal path. If we roll a onguration until a degenera y o urs, we in rease the number of non-an hor ongurations on Π by at most two and we de rease the number of unmoored maximal hains of Π by at least one. Proof. We rst show that the number of non-an hor ongurations in reases by at most two. As we roll a onguration θ, we simultaneously roll ea h onguration in the maximal hain 〈θi〉 that ontains θ. The only parts of Π that deform are the jump pre eding 〈θi〉, the links between onse utive ongurations of 〈θi〉, and the jump following 〈θi〉: ea h of these jumps hosts at most one new non-an hor onguration by Lemma 3.5; moreover, any interior onta t on the link from θi to θi+1 is a type 3 32 an hor; hen e, there are at most two new non-an hor onta t ongurations one on the jump pre eding 〈θi〉 and one on the jump following 〈θi〉. We now show that the number of unmoored maximal hains de reases by at least one. Suppose that some θi be omes moored. Then the number of unmoored maximal hains drops by at least one be ause ea h θi is moored (see Lemma 3.4) and all new onta t ongurations are moored: any new onta t ongurations on the link from θi to θi+1 are an hors, and any new onta t ongurations on the jump pre eding or pro eeding 〈θi〉 are moored (see Lemma 3.5). Suppose that no θi be omes moored. Then 〈θi〉 is still an unmoored hain: the link from θi to θi+1 is still anoni al be ause θi is not type 3 an hor. Hen e, either the jump pre eding 〈θi〉 or the jump pro eeding 〈θi〉 degenerated (be ame a link or non- anoni al). In either ase, the hain 〈θi〉 merges with another hain: if the jump pre eding 〈θi〉 degenerated, then 〈θi〉 merges with the hain pre eding it; otherwise 〈θi〉 merges with the hain pro eeding it. If 〈θi〉 merges with an moored maximal hain, then 〈θi〉 be omes moored, whi h de reases the total number of unmoored maximal hains. Otherwise, two unmoored maximal hains merge, redu ing the total number of unmoored maximal hains. We say that a FW-normal path is BK normal if every onta t onguration is moored. The ompleteness of our normal form is expressed below. Theorem 3.7. Suppose that there is a Dubins path from onguration αs to ong- uration αt with intri a y k. Then there is a BK-normal path Π from αs to αt with O(nk + n3) onta t ongurations. Proof. To prove this theorem, we use a potential fun tion P that assigns a natural number to any FW-normal path Π from αs to αt. Let c(Π) be the number of non- an hor ongurations on Π, d(Π) be the number of unmoored maximal hains of Π, and P(Π) = c(Π) + 3d(Π). Now, suppose that some hain of Π is unmoored. We an redu e the potential of Π by rolling it until a degenera y o urs: by the previous lemma, c(Π) in reases by at most two and d(Π) de reases by at least one; hen e, P(Π) de reases by at least one. Therefore, if Π is a path from αs to αt with minimum potential, every onta t onguration on Π is moored. Not only are low potential paths dis rete, but they also have bounded intri a y. Suppose that there is a Dubins path from αs to αt with intri a y k. By Lemma 3.2, there exists a FW-normal path Π from αs to αt with at most O(nk + n 2) onta t ongurations. Hen e, P(Π) = O(nk + n2) be ause c(Π) = O(nk + n2) and d(Π) = O(nk+n2). Let Π′ be a FW-normal path from αs to αt with minimum potential. Then c(Π′) = O(nk+n2). We assume without loss of generality that no an hor onguration o urs twi e on Π′: if it does, Π′ has a loop; if we remove this loop, Π′ is still FW- normal and P(Π′) does not in rease. Therefore Π′ has O(nk+n3) onta t ongurations be ause there are O(n3) an hor ongurations. Moreover, by the previous paragraph, every onta t onguration of Π′ is moored. 33 Chapter 4 Testing Feasibility In this hapter, we present two path-planning algorithms. Our rst algorithm exhaus- tively sear hes the spa e of BK-normal paths. Our se ond algorithm prunes this sear h to ignore paths that are redundant. The major result of this hapter is that our se ond algorithm is both e ient and omplete: let Π be a feasible path that has the least intri a y of all feasible paths; then our algorithm will nd a feasible BK-normal path Π′, where the intri a y of Π′ is polynomially bounded in the intri a y of Π. A motion-planning problem instan e onsists of a set of polygonal obsta les to avoid, a start onguration αs, and a terminal onguration αt. The intrinsi di ulty of a problem instan e is the minimum intri a y of a feasible Dubins path from αs to αt. Intuitively, the intrinsi di ulty is a lower bound on the run time of any algorithm that returns a natural des ription of the path that it nds. Although previous results do not mention intrinsi di ulty, our statement is onsistent with them. Take the bounded- urvature algorithms reviewed in Se tion 2.2.3 for example: these algorithms work in restri ted domains; these domain restri tions imply that the intrinsi di ulty is bounded in terms of the size of the problem instan e; therefore, the intrinsi di ulty is impli itly in luded in the upper bound on the run time as a parameter measuring the size of the input. There is no known bound on the intrinsi di ulty when the obsta les an be arbitrary polygonal obsta les. So we formulate our bounds in terms of the intrinsi di ulty. We insist that a parameter k that bounds the intri a y of the paths that our algorithms will onsider be given as input. Given k, our algorithms will either verify that the intrinsi di ulty is greater than k (no solution is found) or return a feasible solution. If a solution Π is returned, the intri a y of Π is polynomially bounded in terms of k and the omplexity of the environment n. The main reason that we do not return a path of minimum intri a y is that we sear h for BK-normal paths (see Theorem 3.7). We limit our sear h to the spa e of BK-normal paths be ause it is ountable and, hen e, systemati ally sear hable. Our rst algorithm exhaustively sear hes for a BK-normal paths from αs to αt. In the worst ase, its sear h spa e may be exponentially large in terms of the environment omplexity n. To improve e ien y, we identify a form of redundan y and prune our 34 sear h to ignore redundant paths. To leverage this redundan y, we allow a onstant fa tor in rease in intri a y: the path found by our algorithm with pruning is at most a onstant fa tor more omplex than the path found by our exhaustive algorithm. When we des ribe our pruned sear h, we omit the subroutine that does the pruning. Instead, we spe ify a property that we want it to satisfy. This property is su ient to guarantee that it does not prune too mu h. It is always possible to satisfy this property: it is trivially satised by not pruning anything. The next hapter explains how we prune. At that time, we prove that pruning is both e ient and ee tive. 4.1 Exhaustive Sear h The path-nding algorithm that we present in this se tion performs an exhaustive sear h for a BK-normal paths. We exploit the fa t that we just want to nd one solution to a planning problem, not every solution. Spe i ally, we break the problem into smaller subproblems and ombine one solution to ea h subproblem to get the desired solution to the problem. αs αt α1 α2 (a) This path is an (αs, α1)-linkage, followed by an (α1, α2)-linkage, followed by an (α2, αt)- linkage. αs α1 α2 αt 1 0 2 (b) Path in the an hor graph orresponds to a BK-normal path. Figure 4.1: Linkages and an hor graphs. If we split any BK-normal path at its an hors, ea h resulting subpath is BK-normal, starts at an an hor, ends at an an hor, and is internally free of an hors (see Fig- ure 4.1(a)). We all su h a path from an an hor α to an hor α′ an (α, α′)-linkage. This denition implies that a BK-normal path from αs to αt is omposed of a unique sequen e of linkages. Our path-nding algorithm has two phases: we rst sear h for a linkage between ea h pair of an hors; then we sear h for a path from αs to αt by ombining the linkages that we found. During the rst phase, we onstru t a dire ted weighted graph alled an an hor graph. Ea h vertex orresponds to an an hor and ea h edge orresponds to a feasible linkage. The weight of an edge is the number of non-an hor onta t ongurations on the linkage asso iated with that edge. We are areful to nd linkages that minimise the weight of ea h edge. In the se ond phase, we nd the minimum weight path P from αs to αt in the an hor graph (see Figure 4.1(b)). By on atenating the linkages asso iated with ea h 35 edge of P , we re over a BK-normal path Π from αs to αt. The path Π has the fewest non-an hor onta t ongurations possible by our hoi e of P and onstru tion of the an hor graph. Fa t 4.1. If there is a feasible Dubins path from αs to αt with intri a y k, there exists a path in the an hor graph with weight O(nk). Proof. This follows from loser examination of the proof of Lemma 3.2 and Theorem 3.7. Spe i ally, given the ante edent, the proof of Lemma 3.2 implies the existen e of a feasible FW-normal path from αs to αt with O(nk) non-an hor onta t ongurations. This implies the existen e of a feasible BK-normal path Π from αs to αt with O(nk) non-an hor ongurations by the proof of Theorem 3.7. This path Π orresponds to a path in the an hor graph with weight O(nk). To onstru t our an hor graph, we need to nd linkages between an hors. To nd linkages, we exploit their stru ture. Let Π be a (α, α′)-linkage. Ea h onta t ong- uration of Π is either hained to α or α′ be ause Π is BK-normal and internally free of an hors. This allows us to split Π into a hain starting with α, a hain ending in α′, and a jump from the former to the latter. Based on this observation, we sear h for a (α, α′)-linkage by attempting to bridge every hain starting with α to every hain ending with α′ by a single jump. This redu es our problem of nding a (α, α′)-linkage to nding hains starting with α and nding hains ending with α′. To nd hains starting with α, we iteratively extend by one link those hains that we have already found. The details of this pro edure depend on our representation of hains. Re all that we want to nd linkages with the minimum number of non- an hor onta t ongurations. This is a hieved by nding hains that rea h a parti ular onguration with the minimum number of links. Hen e, we only need to know a few things about ea h hain: where it starts, where it ends, and how many links it takes to get from its start to its end. To this end, let Φα,Fl denote the set of all onta t ongurations at feature F that are rea hed by a hain of l links from an an hor α. We build the sets Φα,Fl in rementally using a pro edure named Propagate: the pro edure all Propagate(Φα,Fl ) adds a onguration φ ′ to Φα,Gl+1 whenever there exists a onguration φ in Φα,Fl that rea hes a onguration φ ′ at G via a single feasible link. Similarly, we denote with Ψα,Fl the set of all onta t ongurations at feature F that rea h α by a hain of l links. We do not expli itly onstru t Ψα,Fl be ause we an reate it in a way similar to Φα,F : to see the symmetry between the two sets, note that a hain ending with α is the reverse of a hain beginning with the ree tion of α. Figure 4.2 ontains the pseudo- ode for a pro edure AllLinkages that onsiders linkages with at most τ non-an hor onta t ongurations. Sin e he king if a given L- or C-segment avoids all obsta les an be done in O(n) time, it is straightforward to onrm that pro edure AllLinkages an be implemented to run in time that is polynomial in the total number of ongurations generated by propagation. 36 AllLinkages(τ) 1 initialise Φα,F0 for all α and F for all an hors α do for l = 0 to τ − 1 do for all environment features F do Propagate(Φα,Fl ) 2 for all pairs of an hors α, α′ do for all pairs of environment features F, F ′ do for all l and l′ su h that l + l′ ≤ τ do determine if there exist ongurations φ ∈ Φα,Fl and ψ ∈ Ψα′,F ′l′ su h that: (i) there is a feasible jump joining φ and ψ, and (ii) the (α, α′)-linkage through φ and ψ has fewer non-an hor onta t ongurations than any (α, α′)-linkage found so far. Figure 4.2: Algorithm that exhaustively onsiders all linkages with at most τ non- an hor onta t ongurations. It re ords the (α, α′)-linkage with fewest non-an hor onta t ongurations found, for ea h pair of an hors (α, α′). 4.2 Redundan y Elimination The run time of the algorithm in Figure 4.2 is dominated by the time taken to onstru t the various Φα,Fl . Re all that ea h of these sets represent hains: φ ∈ Φα,Fl if there exists a feasible l-link hain starting with α and ending at feature F with onguration φ. We use φ inter hangeably to refer to a onguration and the hain that rea hes φ. Whi h of these will be lear from ontext. To nd hains starting with an an hor, we iteratively extend the hains that we have already found by one more link. During this pro ess, the same hain may be extended by O(n) distin t links be ause there are O(n) features that an be rea hed by a link. Su h an un he ked proliferation of hains ould generate O(n)O(nk) hains be ause we generate all hains with O(nk) links. In this se tion, we argue that it su es to al ulate a subset Φ̂α,Fl of Φ α,F l , if we permit a onstant fa tor in rease in intri a y. To be pre ise, if our algorithm that onstru ts Φα,Fl nds a path with c non-an hor onta t ongurations, our algorithm that onstru ts Φ̂α,Fl will nd a path with O(c) non-an hor onta t ongurations. The gist of our argument justifying our onstru tion of Φ̂α,Fl instead of Φ α,F l is simple: any time a hain in Φα,Fl o urs on a path, we an repla e it by a hain in Φ̂α,Fl . The details of this argument are ompli ated by the fa t that it is unlikely that two hains share the same beginning and ending onguration. So rather than a simple substitution of one hain for another, we are going to use a more sophisti ated pro edure. Spe i ally, we are going to remove one hain, add the other hain, and 37 φ′ l φl+1 JF G (a) φ′l rea hes φl+1 via J . φ′ l φl+1 J K F G (b) φ′l rea hes φl+1 via J and K. φ′ l φl+1 J K F G ( ) φ′l rea hes φl+1 via K and J . Figure 4.3: In ea h instan e, the hain φ′l (solid dark) dire tly rea hes the hain φl+1 (gray). then use one or two additional jumps as putty to ll in any remaining gap. In general, this substitution still may not be possible, so we use a pre ise phrase to denote when it is possible. Spe i ally, whenever we an append one hain φ′l with at most one jump J and one link K to reate a path that begins and ends at the same ongurations as φl+1, we say that φ ′ l almost spans φl+1. Figure 4.3 illustrates several dierent situations where φ′l almost spans φl+1. When nding hains that start with an an hor, we want to avoid produ ing re- dundant hains. We do this with a pro edure Filter, whi h we periodi ally all to remove redundant hains (see Figure 4.4). This ulling prevents the potential explosion noted earlier. We leave the des ription of Filter to the next hapter. For now, we just des ribe the essential property of its output. To do this, we need to distinguish between the hains that Filter removes (unviable hains) and those that it does not (viable hains). Completeness Property: If φl ∈ Φ̂α,Fl is unviable, then ea h one link extension φl+1 of φl is almost spanned by some viable φ ′ l ∈ Φ̂α,Fl . 38 AllViableLinkages(τ) 1 initialise Φ̂α,F0 for all α and F for all an hors α do for l = 0 to τ − 1 do for all environment features F do if l is divisible by 4 then Φ̂α,Fl ← Filter(Φ̂α,Fl ) Propagate(Φ̂α,Fl ) 2 for all pairs of an hor ongurations α, α′ do for all pairs of environment features F, F ′ do for all l and l′ su h that l + l′ ≤ τ do determine if there exist φ ∈ Φ̂α,Fl and ψ ∈ Ψ̂α′,F ′l′ su h that: (i) there is path Π from φ to ψ onsisting of at most 8 links and one jump, and (ii) φ+Π + ψ has fewer non-an hor onta t ongurations than any (α, α′)-linkage found so far. Figure 4.4: Filtering ongurations before propagation. The result of repla ing an unviable hain with a viable hain that almost spans it may not be BK-normal. The next lemma shows that an unviable hain is still redundant when we restri t our attention to BK-normal paths. Essentially, it states that if there exists a (α, α′)−linkage Λ that starts with an unviable prex, then there exists a feasible BK-normal path P from α to α′ that starts with a viable prex of roughly the same intri a y as Π. This lemma in ludes several onditions that highlight the important similarities and dieren es between Π and P . These details are used in a later theorem. Lemma 4.2. Let φl+1 be an one link extension of an unviable hain φl of Φ̂ α,F l . If φl+1 is the prex of some (α, α′)-linkage Λ, there exists a BK-normal path P from α to α′ su h that 1. a viable hain φ′l of Φ̂ α,F l is the prex of P , 2. the sux of Λ is a sux of P , and 3. P has at most three more non-an hor onta t ongurations than Λ. Proof. By the Completeness Property, there exists a viable hain φ′l of Φ̂ α,F l su h that φ′l almost spans φl+1. Let Λ ′ be the result of repla ing φl+1 with φ ′ l and at most one jump J and one link K (see Figure 4.3). It is straightforward to verify that (a) Λ′ has at most one more non-an hor onguration than Λ and (b) Λ′ has at most one unmoored maximal hain (be ause J is an arbitrary jump). Note that Λ′ satises 39 the three onditions of this theorem. However, the possible existen e of an unmoored maximal hain prevents Λ′ from being BK-normal. Let P be the result of rolling su h an unmoored maximal hain until it degenerates. By Lemma 3.6, P has at most two more non-an hor onta t ongurations than Λ′. Hen e, the third ondition of this lemma is satised. Moreover, the moored onta t ongurations of Λ′ are un hanged by this operation. Therefore, the rst and se ond onditions of this lemma hold as well. With the pre ise notion of redundan y given in the previous lemma, we are able to prove that AllViableLinkages an be used to nd a feasible path. Theorem 4.3. Suppose that there exists a feasible Dubins path from αs to αt with intri a y k. Then there exists a feasible BK-normal path Π∗ from α to αt su h that 1. Π∗ has O(nk + n3) onta t ongurations, and 2. every linkage in Π∗ is found by AllViableLinkages. Proof. To quantify the extent to whi h a BK-normal path Π from αs to αt satises this theorem, we assign a non-negative integer potential, denoted P(Π). We argue that a BK-normal path Π∗ with minimum potential satises this theorem. The rst term ontributing to P(Π) is proportional to the number of non-an hor ongurations on Π, denoted c(Π). The se ond term ontributing to P(Π) is propor- tional to the viability of Π, denoted v(Π), that is a measure of how mu h of the path is found through onguration propagation. The potential P(Π) is 5c(Π)− 4v(Π). To al ulate v(Π), we sum the viability of its onstituent linkages. Let Λ be one su h (α, α′)-linkage and v(Λ) denote its viability. Re all that Λ an be de omposed into a hain φ starting at α, followed by a jump J , followed by a hain ψ ending at α′. Let φi denote the i-link prex of φ. Then the largest i, denoted v(φ), su h that φi is viable measures how mu h of φ is found by AllViableLinkages. Although φv(φ) is viable, it may not have been subje ted to the pro edure Filter be ause AllViableLinkages only alls Filter(Φ̂α,Fl ) when l is a multiple of four. To this end, let v ′(φ) = 4⌊v(φ)/4⌋. Then φv′(φ) is the longest viable prex of φ that is ltered. We dene v ′(ψ) analogously. Finally, we dene v(Λ) as v′(φ∗) + v′(ψ∗), where φ∗, J , and ψ∗ are a de omposition of Λ that maximises v′(φ∗) + v′(ψ∗). Let Π∗ be a feasible BK-normal path from αs to αt with minimum potential. Su h a path exists be ause (a) there are feasible BK-normal paths from αs to αt and (b) the potential of a path is always non-negative. Condition (a) follows from Theorem 3.7. Condition (b) is satised be ause c(Π) ≥ 0, v(Π) ≥ 0, and c(Π) ≥ v(Π). The last laim is ru ial and bears further examination: learly c(Π) = ∑ Λ∈Π c(Λ) and v(Π) =∑ Λ∈Π v(Λ), where Λ ∈ Π means that Λ is a linkage of BK-normal path Π; hen e, it su es to show that c(Λ) ≥ v(Λ), for ea h Λ; to see this, note that c(Λ) + 1 is the number of jumps on the anoni al representation of Λ and v(Λ) + 1 is at most the number of jumps on the anoni al representation of Λ. 40 Suppose for ontradi tion that AllViableLinkages did not nd one of the link- ages between an hors on Π∗. Let Λ be an (α, α′)-linkage of Π∗ that is not found by our algorithm. We now argue that there exists a BK-normal path P from α to α′ su h that P(P ) < P(Λ). This is impossible be ause if we repla e Λ with P on Π∗, we reate a path with lower potential than Π∗, a ontradi tion. To nd P , we rst de ompose Λ into the hain φ, jump J , and ψ that maximises v(φ) + v(ψ). The subpath of Λ joining φv′(φ) and ψv′(ψ) has at least 9 links be ause AllViableLinkages did not nd Λ. Hen e, either φ is at least 5 links longer than φv′(φ) or ψ is at least 5 links longer than ψv′(ψ). Suppose the former (the latter ase is symmetri ). Then φv′(φ)+4 is unviable by denition of v ′(φ). Moreover, φv′(φ)+5 is a prex of Λ. Hen e, we an apply Lemma 4.2: let P be a BK-normal path α to α′ su h that (a) P has viable [v(φ) + 4]-link prex, (b) ψv′(ψ) is a sux of P , and ( ) c(P ) ≤ c(Λ) + 3. Conditions (a) and (b) imply that v(P ) ≥ v(Λ) + 4. Thus P(P ) ≤ 5[c(Λ) + 3]− 4[v(Λ) + 4] = P(Λ)− 1. We now bound the number of non-an hor ongurations on Π∗. By Theorem 3.7, there exists a BK-normal path Π from αs to αt with O(nk) non-an hor onta t ong- urations. Hen e, P(Π) ∈ O(nk) be ause P(Π) ≤ 5c(Π). Therefore, P (Π∗) ∈ O(nk). Note that P (Π∗) ≥ c (Π∗) be ause c (Π∗) ≥ v (Π∗). Thus c (Π∗) ∈ O(nk). If an an hor onguration o urs twi e on Π∗, we an remove the asso iated loop without in reasing the potential of Π∗. Therefore, we an assume without loss of gen- erality that no an hor o urs twi e on Π∗. In this ase, the number of onta t ongu- rations on Π∗ is c(Π∗) +O(n3) = O(nk + n3). 41 Chapter 5 Eliminating Redundan y In the previous hapter, we dis ussed two path-planning algorithms that grow paths of in reasing intri a y until the set of dis overed paths is ri h enough that it must ontain a solution, if the problem admits a solution of su iently low intri a y. The rst path- planning algorithm is exhaustive, whereas the se ond path-planning algorithm prunes its sear h. To be more pre ise, the rst algorithm al ulates the entire set Φα,Fl of l-link hains an hor α to feature F , whereas the se ond algorithm only al ulates a subset Φ̂α,Fl of Φ α,F l . We generate Φ α,F l and Φ̂ α,F l in similar manners. To al ulate Φ α,G l , we onsider every one link extension to G of every hain in every Φα,Fl−1 . To al ulate Φ̂ α,G l , we onsider every one link extension to G of every viable hain in every Φ̂α,Fl−1 , where a hain is viable if it is not removed by ltering. Re all that we insist that unviable hains redundant with respe t to viable hains, as formalised in the following ondition. Completeness Property: If φl ∈ Φ̂α,Fl is unviable, then ea h one link extension φl+1 of φl is almost spanned by some viable φ ′ l ∈ Φ̂α,Fl . In this hapter, we lter Φ̂α,Fl in a way that satises the Completeness Property. We start with two ases where we an satisfy the the Completeness Property in a straight- forward manner. Then, we dis uss a third ase where we satisfy the Completeness Property indire tly. In this ase, we rely on several te hni al results that we prove in Appendi es A and B. In this hapter, we also argue that our ltering is polynomially bounded. Spe i ally, we show that ltering Φ̂α,Fl takes time that is polynomially bounded in |Φ̂α,Fl | and n. Moreover, we show that the number of resulting viable ongurations is polynomially bounded in n, m, and l. To prove this result, we rely on some te hni al results that we prove in Appendix C. These two onditions imply that the run time of our se ond algorithm is polynomially bounded in n, m, and k. We ta kle the problem of ltering Φ̂α,Fl with a divide-and- onquer approa h. Spe if- i ally, we identify dierent types of one-link extensions of Φ̂α,Fl . We dene the extension types so that extensions of a parti ular type are so similar that we an solve the asso- iated subproblem with one simple strategy. To larify what we mean by subproblem, for ea h type of extension T , we sele t a subset Φ̂α,Fl [T ] of Φ̂ α,F l so that every one-link 42 extension of Φ̂α,Fl of type T is almost spanned by some hain in Φ̂ α,F l [T ]. The result of ltering Φ̂α,Fl is the union ⋃ T Φ̂ α,F l [T ]. This union satises the Completeness Property be ause our hoi e of types types is exhaustive: every one-link extension of Φ̂α,Fl is of some parti ular type. 5.1 Filtering with Walls We rst address the easiest ase: suppose that we want to lter Φ̂α,Fl when F is a wall. In this instan e, we use the fa t that on e we rea h a wall, we an follow that wall unimpeded. To be more pre ise, let φl, φ ′ l ∈ Φ̂α,Fl be two ongurations at F oriented in the same dire tion. If φ′l omes before φl, then φ ′ l an rea h φl by following F (see Figure 4.3(b)). Hen e, φ′l almost spans every one link extension of φl. Therefore, we an eliminate all but the two hains of Φ̂α,Fl that rea h F the earliest in ea h dire tion and still satisfy the Completeness Property. Now, suppose that we want to lter Φ̂α,Fl when F is a orner. In this ase, we distinguish the extensions of Φ̂α,Fl by the feature G that they rea h. For ea h G, we identify a subset Φ̂α,Fl [G] of Φ̂ α,F l so that for every one link extension φl+1 of φl ∈ Φ̂α,Fl to G, there exists φ′l ∈ Φ̂α,Fl [G] su h that φ′l almost spans φl+1. Suppose that we want to identify Φ̂α,Fl [G] when G is a wall. Again, we use the fa t that on e we rea h a wall, we an follow the wall unimpeded. Spe i ally, let φl, φ ′ l be hains of Φ̂α,Fl and φl+1, φ ′ l+1 be one link extensions to G of φl and φ ′ l respe tively. If φl+1 and φ ′ l+1 are oriented the same way and φ ′ l+1 rea hes G before φl+1 at G, then φ′l+1 an follow G to rea h φl+1 (see Figure 4.3( )). In this ase, φ ′ l almost spans φl+1. Hen e, we sele t at most two hains for Φ̂α,Fl [G]: the hains of Φ̂ α,F l that rea h G via a one link extension the earliest. 5.2 Corner to Corner Extensions In the ases that we just addressed, we used the fa t that one hain an rea h a range of ongurations via a single jump. In parti ular, on e we rea h a wall, we an follow that wall unimpeded. We now address the problem of onstru ting Φ̂α,Fl [G], when both F and G are orners. In this ase, we use the fa t that one onguration at F an rea h a range of ongurations at G via a single jump (see Figure 5.1(a)). This rea h is dierent from the rea h along a wall in two important ways: an obsta le may blo k a jump from F to G, whereas the jump along a wall is free of obsta les; and the rea h from F to G shifts (see Figure 5.1(b)), whereas the rea h at a wall grows monotoni ally (the earlier you rea h the wall, the better). First, we formalise what we mean by the rea h from F to G with a ouple of denitions. The spe trum of jumps rea hing G from one onguration φ at F is the set of all jumps from φ to G, in luding jumps blo ked by obsta les (see Figure 5.1(a)). By allowing jumps in a spe trum to ollide with obsta les, a jump spe trum only depends 43 on φ and the relation of φ to G (see Figure 5.1(b)). The rea h of a jump spe trum from φ to G, denoted reach(φ), is the set of all destination ongurations rea hed by some jump in that spe trum. F G (a) One onguration at F rea hes a range of ongurations at G via a single jump. φ2 φ3 φ1 F G (b) The range of ongurations rea hed at G depends on the sour e onguration at F . Figure 5.1: Jump spe tra. We now des ribe how to sele t Φ̂α,Fl [G] so that for every one-link extension φl+1 of φl ∈ Φ̂α,Fl , there exists φ′l ∈ Φ̂α,Fl [G] su h that there is a feasible jump from φ′l to φl+1 (in whi h ase, φ′l almost spans φl+1). We guarantee the existen e of a jump from φ ′ l to φl+1 with jump spe tra: there exists a jump from φ ′ l to φl+1, if φl+1 ∈ reach(φ′l). However, this guaranteed jump from φ′l to φl+1 may be infeasible be ause jumps in a spe trum an be blo ked by obsta les. To guarantee that this jump is ollision-free, we introdu e new subproblems. In our new subproblems, we distinguish the extensions of Φ̂α,Fl by the feature G that they rea h, their ne stru ture Γ, and their homotopy lass h. For ea h G, Γ, and h, we identify a subset Φ̂α,Fl [G,Γ, h] of Φ̂ α,F l so that for every one link extension φl+1 of φl ∈ Φ̂α,Fl to G with ne stru ture Γ and homotopy h, there exists φ′l ∈ Φ̂α,Fl [G,Γ, h] su h there exists a feasible jump from φ′l to φl+1. Then we take the union of the solutions to the subproblems ⋃ Γ,h Φ̂ α,F l [G,Γ, h] as the desired Φ̂ α,F l [G]. We hoose Φ̂α,Fl [G,Γ, h] with a greedy approa h. Initially, we set Φ̂ α,F l [G,Γ, h] to the ongurations of Φ̂α,Fl that an rea h G via a link with ne stru ture Γ and homotopy h. Then we repeatedly eliminate ongurations from Φ̂α,Fl [G,Γ, h] when it is safe to do so. Spe i ally, we look for a triple φ1, φ2, φ3 ∈ Φ̂α,Fl [G,Γ, h] su h that reach(φ2) ⊆ reach(φ1) ∪ reach(φ3) and remove φ2 when su h a triple is found (see Figure 5.1(b)). Although Γ and h play no role in our de ision to eliminate φ2, they ertify that the removal of φ2 is safe. To see this, let L2 be the link from φ2 to G with ne stru ture Γ and homotopy h (see Figure 5.2(b)). It is safe to remove φ2 if the extension of φ2 by L2 is almost spanned by φ1 or φ2. By our hoi e of φ2, the destination onguration of L2 is ontained in reach(φ1) or reach(φ3). Suppose the latter (the other ase is symmetri ), and let J be the jump from φ3 to the destination onguration of L2. If J is free of ollisions, then the extension of φ2 by L2 is almost spanned by φ3. To see that J is ollision free, noti e that J is wedged between L2 and L3, where L3 is link from φ3 to 44 FG (a) Links with ne stru ture C−L0C + from F to G. F G L2 L3 φ3 φ2 J (b) Jump from φ1ℓ to φ 2 ℓ+1 is wedged between L1 and L2. Figure 5.2: We rene our subproblems so that our redundan y elimination is safe. G with ne stru ture Γ and homotopy h. This wedging of J between L2 and L3 is true in general: Lemma A.2 states that neither L2 nor L3 ross J ; moreover, the links L2 and L3 always lie on dierent sides of J by the monotoni ity of links with stru ture Γ (see Lemma B.1). This wedging implies that J is ollision free be ause the L2 and L3 have the same homotopy h. Therefore, it is safe to remove φ2 from Φ̂α,Fl [G,Γ, h]. This method of onstru ting Φ̂α,Fl [G,Γ, h] takes time that is polynomially bounded in |Φ̂α,Fl | and n be ause reach(φ) is easily represented and readily omputed: reach(φ) is an interval of orientations (this follows from the arguments in Se tion A.2); this interval is bounded by links from φ to G be ause the destination onguration of an un onstrained jump an be rolled by a small amount in either dire tion. Therefore, we an lter Φ̂α,Fl in time that is polynomially bounded in |Φ̂α,Fl | and n be ause there are only O(n) hoi es of G, O(1) hoi es of Γ, and O(n) hoi es for h (see Lemma B.3). In the rest of this hapter, we argue that |Φ̂α,Fl [G,Γ, h]| is polynomially bounded in n, m, and l. The stru ture of this proof is as follows. First, we formalise a property T that Φ̂α,Fl [G,Γ, h] satises. We also argue that Φ̂ α,F l [G,Γ, h] is minimal in this respe t: no proper subset of Φ̂α,Fl [G,Γ, h] satises T . This minimality implies that the size of Φ̂α,Fl [G,Γ, h] is at most twi e as large as any set that satises T . Hen e, it su es to onstru t a set Ψ that satises T and whose size is polynomially bounded in n, m, and l. We on lude by onstru ting su h a set and showing that its size is bounded. 5.2.1 Minimality of Greedy Filtering Throughout the remainder of this hapter, we assume without loss of generality, by suitable translation and rotation, that F is at the origin and G lies on the positive x-axis. Under this assumption, we an represent any onta t onguration at G by its ounter lo kwise angle from the dire tion of the positive x-axis measured in the range of (−π, π]. We now mention two important properties of reach(φ). Lemma 5.1. Let φ and φ′ be two distin t onta t ongurations. Then 1. reach(φ) is a losed subinterval of (−π, π], and 45 2. reach(φ) 6⊆ reach(φ′) and reach(φ) 6⊇ reach(φ′). Proof. The rst property hinges on one fa t: there is only one onguration θ at F that an rea h the onguration ψ with the dire tion π at G (see Figure 5.3). By symmetry, the only onguration that θ rea hes at G is ψ. Re all that the rea h reach(φ) is a ontiguous range of dire tions. If φ 6= θ, then reach(φ) does not ontain π. In this ase, reach(φ) is a subinterval of (−π, π]. Alternatively, if φ = θ, then reach(φ) = [π, π]. GF θ ψ Figure 5.3: Only one onguration θ an rea h ψ via a jump from F to G. The se ond property follows from the fa t both endpoints of reach(φ) vary mono- toni ally with φ (see Figure 5.1(b)). This is true be ause the links bounding the jump spe trum from φ are monotoni in φ (see Lemma B.1). Now we formalise the property that we maintain as we greedily remove ongura- tions from Φ̂α,Fl [G,Γ, h]. Let Θ be a set of onta t ongurations at F and Reach(Θ) denote ⋃ θ∈Θ reach(θ). Then Reach(Θ) is the set of all ongurations at G that an be rea hed via a jump from some onguration in Θ. We say that Ψ overs Θ, if Reach(Ψ) ⊇ Reach(Θ). We say that Ψ minimally overs of Θ, if no proper subset of Ψ also overs Θ. We now argue that Φ̂α,Fl [G,Γ, h] minimally overs itself. Re all our ondition for removing φ2 from Φ̂α,Fl [G,Γ, h]: we insist that reach(φ 2) ⊆ reach(φ1)∪ reach(φ3), where φ1,φ2, and φ3 are unique ongurations of Φ̂α,Fl [G,Γ, h]. We now show that this is equiv- alent to requiring that Φ̂α,Fl [G,Γ, h] \ {φ2} overs Φ̂α,Fl [G,Γ, h]: learly, if reach(φ2) ⊆ reach(φ1) ∪ reach(φ3), then Φ̂α,Fl [G,Γ, h] \ {φ2} overs Φ̂α,Fl [G,Γ, h]; so suppose that Φ̂α,Fl [G,Γ, h] \ {φ2} overs Φ̂α,Fl [G,Γ, h]; by Corollary 5.1, reach(φ′) either extends to the left of reach(φ2) or to the right of reach(φ2) but not both, for φ′ ∈ Φ̂α,Fl [G,Γ, h]\{φ2}; let φ1 be the onguration of Φ̂α,Fl [G,Γ, h] \ {φ2} su h that reach(φ1) extends to the left of reach(φ2) and reach(φ1) ∩ reach(φ2) is maximised; similarly, let φ3 be the on- guration of Φ̂α,Fl [G,Γ, h] \ {φ2} su h that reach(φ3) extends to the right of reach(φ2) and reach(φ2)∩reach(φ3) is maximised; then reach(φ2) ⊆ reach(φ1)∪reach(φ3). Hen e, Φ̂α,Fl [G,Γ, h] minimally overs itself, on e we nish removing redundan y. We exploit the property that Φ̂α,Fl [G,Γ, h] minimally overs itself to bound the size of Φ̂α,Fl [G,Γ, h]. Spe i ally, the following lemma implies that |Φ̂α,Fl [G,Γ, h]| is at most twi e as large as any over of Φ̂α,Fl [G,Γ, h]. Lemma 5.2. Let Ψ and Ψ′ be nite overs of Θ. If Ψ minimally overs Θ, then |Ψ| ≤ 2|Ψ′|. 46 Proof. Let ψ′ be an arbitrary onguration in Ψ′. To prove this lemma, we show that there exist ψ1 and ψ2 in Ψ su h that reach(ψ1) ∪ reach(ψ2) ⊇ reach(ψ′) ∩ Reach(Θ). Hen e, |Ψ| ≤ 2|Ψ′| by minimality of Ψ. Let ω1 and ω2 be the extreme ongurations of reach(ψ) ∩ Reach(Θ). There exists ψ1 ∈ Ψ su h that ω1 ∈ reach(ψ1) be ause Reach(Ψ) ⊇ Reach(Θ). So we hoose ψ1 su h that ω1 ∈ reach(ψ1) and reach(ψ1)∩ [ω1, ω2] is maximised. Similarly, we hoose ψ2 su h that ω2 ∈ reach(ψ2) and reach(ψ2) ∩ [ω1, ω2] is maximised. If reach(ψ1) ∪ reach(ψ2) ⊇ reach(ψ′) ∩ Reach(Θ), we are done. So suppose not, and onsider ω3 ∈ [reach(ψ′) ∩ Reach(Θ)] \ [reach(ψ1) ∪ reach(ψ2)] for ontradi tion. Then there exists ψ3 ∈ Ψ su h that ω3 ∈ reach(ψ3) be ause Reach(Ψ) ⊇ Reach(Θ). Then ω1 6∈ reach(ψ3) be ause our hoi e of ψ1 maximised reach(ψ1)∩ [ω1, ω2]. Similarly, ω2 6∈ reach(ψ3). Thus, reach(ψ3) ⊂ [ω1, ω2] be ause ω3 ∈ reach(ψ3)∩[ω1, ω2]. Therefore, reach(ψ3) ⊂ reach(ψ) be ause [ω1, ω2] ⊆ reach(ψ), whi h ontradi ts Corollary 5.1. 5.2.2 Generating a Cover By Lemma 5.2, |Φ̂α,Fl [G,Γ, h]| ≤ 2|Ψ|, if Ψ overs Φ̂α,Fl [G,Γ, h]. In this se tion, we des ribe how to nd su h a Ψ. We rst dene a sequen e 〈Ψi〉 that grows: Ψi+1 is the result of adding a onstant number of ongurations to Ψi. This sequen e 〈Ψi〉 is onstru ted so that it eventually overs Φ̂α,Fl [G,Γ, h]: there exists i su h that Ψi overs Φ̂α,Fl [G,Γ, h]. We hoose as Ψ the smallest Ψi that overs Φ̂ α,F l [G,Γ, h]. Our goal is to show that |Ψ| is bounded. Our proof that |Ψ| is bounded essentially uses the following reasoning. Suppose that we have an innite sequen e 〈xi〉 and that we want to show that some xi ex eeds a ertain value b. It is su ient to show that 〈xi〉 onverges to a value x∗ and that b < x∗. To bound |Ψ|, we examine the worst ase that Ψ must rea h: let R ⊆ (−π, π] denote the entire range of ongurations at G that an be rea hed by any jump from F . We will show that limi→∞Reach(Ψi) = R, in whi h ase we say that 〈Ψi〉 eventually rea hes R. We also show that Reach(Φ̂α,Fl [G,Γ, h]) ⊂ R. Intuitively, it follows that some Ψi overs Φ̂α,Fl [G,Γ, h]. Su h arguments only show that |Ψ| is nite. To get a better bound on |Ψ|, we quantify the rate at whi h Reach(Ψi) onverges to R and how mu h smaller Reach(Φ̂α,Fl [G,Γ, h]) is than R. We start by hara terising the set R that Ψ eventually rea hes. Lemma 5.3. Let ∆ be the distan e from F to G. If ∆ ≥ 2, then R = (−π, π]. If ∆ < 2, every onguration at G that enters one (but not both) of the unit-radius ir les through F and G annot be rea hed by any jump from F to G (see Figure 5.4( )). Proof. If ∆ ≥ 2, then every onguration at G an be rea hed by a jump J from F , where the C-segments of J have the same length and orientation (see Figure 5.4(a)). Suppose that ∆ < 2. The unbounded shaded region in Figure 5.4(b) represents all of the points that an rea h a onta t onguration θ at G by a single jump. Hen e, if one of the two unit radius ir les tangent to onguration θ at G ontains F , there is 47 no jump from F to θ. Figure 5.4( ) illustrates two ranges of ongurations at G that annot be rea hed by a jump from F . Ea h su h range is bounded by a onguration that has a unit-radius ir le C tangent to it su h that F lies on the boundary of C. (a) If ∆ ≥ 2, then every ongura- tion at G an be rea hed. θ (b) Lo us of points that an rea h θ via a single jump. GF ( ) Some ongu- rations annot be rea hed by a jump from F . Figure 5.4: Chara terisation of the set R of ongurations that an be rea hed by a single jump. Corollary 5.4. There are nite neighbourhoods around ertain an hors that belong to R but not Reach(Φ̂α,Fl [G,Γ, h]). Proof. Figure 5.5 shows ve ongurations at G that we all singularities. We all them singularities be ause ea h su h onguration an only be rea hed by one onguration at F . That ea h jump is a singularity follows from lo us arguments similar to the argument illustrated in Figure 5.4(b). For example, onsider the singularities that are rea hed by a single C-segment: to rea h su h a singularity from F , we must start on the boundary of the forbidden region in Figure 5.4(b); this implies that a jump to a singularity has a zero-length L-segment be ause the lo us of starting points of jumps with non-zero length L-segments does not in lude the boundary of the forbidden region; similarly, the C-segments of a jump to a singularity must also have the same orientation; hen e, to rea h a singularity from a point starting on the boundary, the jump must never leave the boundary. The jumps that rea h ea h singularity are symmetri . Therefore, a onguration at F that rea hes a singularity only rea hes that singularity. Re all that the rea h of one jump spe trum is losed and is never ontained in the rea h of another jump spe trum (see Corollary 5.1). Hen e, reach(φ) of a onguration φ ∈ Φ̂α,Fl [G,Γ, h] is either a singleton ontaining a singularity or an interval that is a nite distan e away from all singularities. Thus, there are ongurations lose to ea h singularity that are not ontained in Reach(Φ̂α,Fl [G,Γ, h]). 48 GF Figure 5.5: Ea h dashed onguration at G an only be rea hed by one onguration at F via a jump. We now show how to onstru t a 〈Ψi〉 that eventually rea hes R. We will see that the regions of R that Reach(Ψi) does not rea h lie in neighbourhoods around singularities. As i grows, these neighbourhoods shrink rapidly. Hen e, there exists i su h that Ψi overs Φ̂α,Fl [G,Γ, h]. Therefore, |Ψ| is nite. To onstru t 〈Ψi〉, we rst split R into quadrants, where Rq denotes R restri ted to the qth quadrant (see Figure 5.6(a)). Then we onstru t a 〈Ψqi 〉 that eventually rea hes Rq. This implies that 〈Ψi〉 eventually rea hes R, where Ψi = ⋃q Ψqi . We use this approa h be ause we onstru t 〈Ψ4i 〉 in su h a way that ree tions of 〈Ψ4i 〉 eventually rea h R1, R2, and R3. First, note that if 〈Ψ4i 〉 eventually rea hes R4, then the verti al ip of 〈Ψ4i 〉 eventually rea hes R1 be ause if J is a jump from F to R4, then the verti al ip of J is a jump from F to R1. Similarly, if 〈Ψ2i 〉 eventually rea hes R2, then the verti al ip of 〈Ψ2i 〉 eventually rea hes R3. Therefore, it su es to onstru t 〈Ψ2i 〉 and 〈Ψ4i 〉. 4 12 3 (a) Range of onta t on- gurations at G. J K GF (b) For every jump J with stru ture C+LC+, there exists a jump K with stru ture C−LC− su h that (a) the sour e onguration of J is the reverse of the sour e onguration of K and (b) the destination onguration of J is the reverse of the destination onguration of K. Figure 5.6: Using symmetries to simplify the onstru tion of 〈Ψi〉. The symmetry that allows us to use a ree tion of 〈Ψ4i 〉 to over R2 is more subtle. Let J be C+LC+-stru ture jump from F to a onguration in R4 (see Figure 5.6(b)). Then there exists a C−LC−-stru ture jump K from F to R2, where the sour e on- guration of K is the ree tion through F of the sour e onguration of J and the destination onguration of K is the ree tion through G of the destination ongura- 49 tion of J . In our onstru tion of 〈Ψ4i 〉, we ensure that 〈Ψ4i 〉 eventually rea hes R4 via jumps that have stru ture C+LC+. Hen e, the ree tion of 〈Ψ4i 〉 through F eventually rea hes R2 via jumps that have stru ture C−LC−. To onstru t 〈Ψ4i 〉, we take Ψ4i as the rst i ongurations of a sequen e 〈ψj〉 that we dene re ursively via a fun tion f : ψj+1 = f(ψj). The sequen e 〈ψj〉 qui kly onverges to a xed-point ψ∞ of f . This rapid onvergen e is important be ause the dieren e between ψi and ψ∞ measures the region of R4 not yet rea hed by Ψ4i . Of the many hoi es of f available to us, we pi k one that mimi s an iterative pro ess that is known to rapidly onverge: the Newton-Raphson method of nding the root of a dierentiable fun tion g(x). This method works as follows. Let x1 be an estimate of the root of g(x). Then we hoose xj+1 as the interse tion of the line tangent to g(xj) and the x-axis. If 〈xj〉 onverges to a number x∗, then x∗ is a root of g. Moreover, if x1 is hosen lose to a root of g(x), then onvergen e of 〈xj〉 to x∗ is very rapid: |xj − x∗| ≤ 22−Ω(j) , for su iently large j. dj cj cj+1 L T d∞ dj+1 H I (a) Rea h underestimate. ∆/3 d1 d2 d∞1 (b) Rapid onvergen e of 〈dj〉 to d∞. Figure 5.7: Rea h underestimate onstru tion (left) and iteration (right). Figure 5.7(a) illustrates our hoi e of f . In this gure, the point dj is the entre of a lo kwise-oriented unit-radius ir le tangent to ψj . Given dj, we onstru t dj+1 geometri ally. Let H be the unit-radius ir le entred at F . Let T be the line tangent to H at dj. The dire tion of T is parallel to the dire tion of ψj . Let L be the lo us of points that are equidistant to F and G. The point dj+1 is the horizontal proje tion onto H of the interse tion of T and L. The sequen e 〈di〉 onverges to a point d∞ where H interse ts L. This pro ess orresponds to the Newton-Raphson method of nding the interse tion of H and L. The fun tion f has the property that the ongurations rea hed by C+LC+-stru ture jumps from ψj and ψj+1 overlap. Let cj be the ree tion of dj through L. Then there is a C+LC+-stru ture jump from the ir le entred at dj to any ir le whose entre lies on the ar between cj and cj+1. To see this, start with the jump J from the ir le entred at dj to the ir le entred at cj. This is a C +LC+-stru ture jump where both C-segments have the same length. We an deform this jump by rolling J 's destination onguration in a lo kwise manner. This auses the entre of the ir le underlying the se ond C-segment to move lo kwise along I. It also auses the length of the rst C-segment to shrink and the length of the se ond C-segment to grow. We must stop 50 rolling on e the length of the rst C-segment be omes zero. However, at this point the entre of the ir le underlying the se ond C-segment is at the interse tion of T and I in Figure 5.7(a). Hen e, there is a C+LC+-stru ture jump from the ir le entred at dj to any ir le whose entre lies on the ar between cj and cj+1. Figure 5.7(b) shows Reach(Ψ4i ) rapidly approa hing R 4 . Unfortunately, in order for Reach(Ψ4i ) to onverge to R 4 , we would have to begin our iterative pro ess with d1 set to the point dire tly below F . Unfortunately, this position is a xed-point of f . To handle this degenera y, we use the inverse f−1 to dene a sequen e 〈ψ−i〉 where ψ−(i+1) = f−1(ψ−i) (see Figure 5.8(a)). Let Ψ4i = {ψ−i, ψ−i+1, . . . , ψ−1, ψ1, ψ2, . . . , ψi}. By a areful hoi e of d1 and d−1 in terms of the distan e ∆ between F and G (see Figures 5.7(b) and 5.8(a)) guarantees that Reach(Ψ4i ) is ontiguous (see Figure 5.8(b) and Lemma C.2). Moreover, Reach(Ψ4i ) rapidly onverges to all of R. d−2d−∞ d−1 ∆/5 (a) Rapid ba kward onvergen e. d1 d −1 (b) Rea h underestimates overlap. Figure 5.8: Ba kwards iteration (left) ombined with a suitable starting point (right). In Appendix C, we expli itly bound the rate of onvergen e of Reach(Ψ4i ) to R 4 . We formalise this by measuring how far dj and d−j are from their respe tive xed points d∞ and d−∞. Let ξ+ (j) denote the verti al distan e between d+j and d+∞. Similarly, let ξ− (j) denote the verti al distan e between d−j and d−∞. Theorem 5.5. The distan e ξ±(j) ≤ 2−Ω(j), for j ≥ 1. If the distan e between F and G is not exa tly two, then ξ±(j) ≤ 2−2Ω(j) , for j > O(m). Proof. See Appendix C. 5.2.3 Separation Bound The previous theorem bounds just how rapidly 〈Ψi〉 rea hes R. In this se tion, we bound the rea h of Φ̂α,Fl [G,Γ, h] away from R. These two bounds will imply that |Ψ| is polynomially bounded, where Ψ is the smallest Ψi that overs Φ̂ α,F l [G,Γ, h]. In turn, this implies that Φ̂α,Fl [G,Γ, h] is polynomially bounded by Lemma 5.2. To bound the rea h of Φ̂α,Fl [G,Γ, h] away from R, we use a result of Burnikel et al. [11℄: given an expression E omposed of integer operands and arithmeti operators (+, −, ×, /, and √ ), they bound how dierent the value of E must be from zero, if 51 the value of E is not exa tly zero. This separation bound is al ulated dire tly from the arithmeti expression. Theorem 5.6. [11℄Let E be an expression with integer operands and operations +, −, ×, /, and √ . Let ξ be the value of E, let s be the number of square-roots in E, and let u (E) and l (E) be dened re ursively on the stru ture of E by the rules shown in the table below. Then ξ = 0 or |ξ| ≥ ( l (E)u (E)2 s−1)−1 . u (E) l (E) integer N |N | 1 E1 ± E2 u (E1) l (E2) + l (E1)u (E2) l (E1) l (E2) E1 × E2 u (E1)u (E2) l (E1) l (E2) E1/E2 u (E1) l (E2) l (E1)u (E2)√ E1 √ u (E1) √ l (E1) The above theorem denes the separation bound ξ of an expression E in terms of the entire stru ture of E. For our purposes, we do not need the full generality of this theorem. We are satised with the following orollary that denes the separation bound ξ in terms of the number of operators in E. Corollary 5.7. Let E be an expression omposed of integer operands of magnitude at most 2m and e arithmeti operations (either +, −, ×, /, or √ ). Let ξ be the value of E. Then either ξ = 0 or |ξ| ≥ 2−m6e. Proof. LetM (E) = max {u (E) , l (E)}. We now argue thatM (E) ≤ 2m·3eby indu tion on e. The base ase is e = 0, where E is an integer of magnitude at most 2m. Then M (E) ≤ 2m = 2m·3e . So suppose that M (F ) ≤ 2m·3f and M (G) ≤ 2m·3g , for expressions F and G with f < e and g < e operations respe tively. We now onsider the various ases that ould possibly generate E. Suppose that E = √ F . Then M (E) = √ M (F ) ≤ √ 2m·3f ≤ 2m·3f ≤ 2m·3e by our indu tive hypothesis. Suppose that E = F ± G. Then u (E) = u (F ) l (G) + l (F ) u (G) ≤ 2 ·M (F ) · M (G) ≤ 2 · 2m·3f · 2m·3g = 2m(3f+3g)+1 ≤ 2m(3f+3g+1), by our indu tive hypothesis. Now, e = f + g + 1, so our desired bound is a hieved if 3f + 3g + 1 ≤ 3f+g+1. This inequality is true if and only if 3−g−1 + 3−g−1 + 3−f−g−1 ≤ 1. Ea h ea h term on the left side is learly less than 1 3 . Hen e, u (E) ≤ 2m·3e . From the denition l (E) = l (F ) · l (G) ≤ M (F ) ·M (G) ≤ 2m·3f · 2m·3g = 2m(3f+3g) < 2m(3f+3g+1) ≤ 2m·3e , by our indu tive hypothesis. The reasoning for E = F × G and E = F/G are similar (and simpler) than the previous ase. Therefore, M (E) ≤ 2m·3e in general. 52 Clearly the number of square roots in E is less than e. So the previous theorem implies that either ξ = 0 or |ξ| ≥ ( l (E)u (E)2 e−1)−1 ≥M (E)−2e ≥ (2m·3e)−2e = 2−m·6 e . In Corollary 5.4, we argued that there are regions of R around singularities are not part of Reach(Φ̂α,Fl [G,Γ, h]). We now derive an expression for the onguration φ′ ∈ Reach(Φ̂α,Fl [G,Γ, h]) that gets as lose as possible to a singularity α′. Combined with the above orollary, this will give us a bound on how dierent Reach(Φ̂α,Fl [G,Γ, h]) is from R. In the dis ussion that follows, we use a natural representation for onta t ongurations: at a wall, we use the point where the onguration tou hes the wall; at a orner, we use a unit-length ve tor in the dire tion of the onguration. Lemma 5.8. Let α′ be an an hor at G and φ ∈ Φ̂α,Fl [G,Γ, h]. If φ′ is the onguration in the rea h of φ that is losest to α′, then either φ′ = α′ or φ′ an be expressed with integers operands of magnitude at most 2m and O(l) operators. Proof. Let φ′ be the onguration at G in the rea h of φ that is losest to α′. If φ′ = α′, then we have nothing to prove. Otherwise, φ rea hes φ′ via a link be ause the jump spe trum from φ to G is bounded by links. Although, we are not sure whi h link from φ leads to φ′, there are only O(1) su h links, so we an try them all. The existen e of a link from φ to φ′ means that φ′ an be al ulated from α with O(l) arithmeti operations. Re all, that φ ∈ Φ̂α,Fl [G,Γ, h] implies that there is a l-link hain from α to φ. Hen e, there is a (l+1)-link hain from α to φ′. Also re all that the nal onguration of a link is a fun tion of its sour e onguration. Therefore, φ′ an be al ulated from α by evaluating (l + 1) link fun tions. Finally, ea h link fun tion an be expressed with O(1) arithmeti operators and integer operands with magnitude at most 2m (ea h orner oordinate is the ratio of two su h integers). Therefore φ′ an be al ulated from α with O(l) arithmeti operations. An hors are the ongurations on over- onstrained links. Hen e, α an be expressed with O(1) arithmeti operators and O (1) orner oordinates. Hen e, φ′ an be al u- lated with O(l) arithmeti operators. This separation bound and Theorem 5.5 have an immediate impli ation. Corollary 5.9. The size of Φ̂α,Fl [G,Γ, h] is at most O(m+ l). Proof. Let φ′ be the onguration in Reach(Φ̂α,Fl [G,Γ, h]) that gets as lose to a singu- larity α′ as possible without rea hing it. Then φ′ an be expressed with integer operands of magnitude at most 2m and O(l) operators by Lemma 5.8. With an additional O(1) operators, we an transform φ′ into the oordinate system where we did our analysis of how qui kly 〈Ψi〉 rea hes R. In this frame of referen e, we an express the verti al distan e between φ′ and α′ with O(l) operators. By Corollary 5.7, this distan e must be 2−m2 O(l) . We only argue the ase where the distan e ∆ from F to G is not exa tly 2. In this ase, we an apply Theorem 5.5. This theorem implies that the set Ψi rea hes all 53 of R, ex ept a small amount with verti al distan e of 2−2 Ω(i) from the singularities, for i > O(m). Therefore, Ψi overs Φ̂ α,F l [G,Γ, h] for some i ∈ O(m)+(l+logm) = O(l+m). Hen e, |Ψ| ∈ O(l + m). Re all that |Φ̂α,Fl [G,Γ, h]| ≤ 2|Ψ| by Lemma 5.2. Thus, |Φ̂α,Fl [G,Γ, h]| ∈ O(l +m). When the distan e ∆ from F to G is exa tly 2, we an a hieve a polynomial bound with a more detailed analysis that exploits symmetry further. 5.3 Bounds on the Run Time In this se tion we derive a loose bound on the run time of path nding algorithm. Re all that rst we onstru t an an hor graph, and then we look for a shortest path in the an hor graph. The rst phase is the most omputationally expensive. It is arried out by the algorithm AllViableLinkages (see Figure 4.4). Its run time depends on the number of hains that are generated. This in turn depends on the ee tiveness of ltering. In Corollary 5.9, we state an expli it bound on the ee tiveness of one important step of ltering. We now use this to get an expli it bound on |Φ̂α,Fl |. Lemma 5.10. Before ltering, the size of Φ̂α,Fl is at most O(n 6(m+ l)). Proof. We rst bound the size of Φ̂α,Fl after it has been ltered. If F is a wall, then Φ̂ α,F l ontains at most two hains after ltering. Otherwise, we partition all of the possible one link extensions of Φ̂α,Fl a ording to the feature G that is rea hed by the link, the ne stru ture Γ of the link, and the homotopy h of the link. For ea h of the O(n) hoi es of G, O(1) hoi es of Γ, and O(n) hoi es of h, we identify a subset Φ̂α,Fl [G,Γ, h] of Φ̂α,Fl so that every one link extension of Φ̂ α,F l to G with stru ture Γ and homotopy h is almost spanned by a hain in Φ̂α,Fl [G,Γ, h]. Clearly, ⋃ G,Γ,h Φ̂ α,F l [G,Γ, h] satises the ompleteness property with respe t to Φ̂α,Fl . By Corollary 5.9, ⋃ G,Γ,h Φ̂ α,F l [G,Γ, h] ontains at most O(n2(m+ l)). To get a bound on |Φ̂α,Fl | before it is ltered, we work ba kwards: ea h hain in Φ̂α,Fl is a one link extension of a hain in Φ̂ α,G l−l , for some G; there are O(n) hoi es of G and O(1) possible ne stru tures for the one link extension, so |Φ̂α,Fl | is at most O (∑ G |Φ̂α,Gl−l | ) ⊆ O(n × maxG |Φ̂α,Gl−1 |). Every hain φ in Φ̂α,Fl has a prex φ′ that was ltered. If φ′ is the longest su h prex of φ, then φ is at most four links longer than φ′. It follows that |Φ̂α,Fl | is at most O(n6(m+ l)). The time spent propagating hains depends on the number of hains generated. There are O(n3) an hors and we only generate hains with at most O(nk) links. Hen e the number of hains generated is at mostO(n10k(m+nk)). Ea h hain that is generated must be tested for feasibility. Fortunately, it su es to he k the last link be ause all of the other links must have been feasible in order for the hain to be generated. Ea h link onsists of at most three segments and ea h segment an be tested for feasibility in O(n) time. Hen e, the total time spent propagating hains is at most O(n12k(m+nk)). 54 We now bound the time spent ltering hains. Re all that in the worst ase, the all to Filter identies O(n2) subproblems. As des ribed earlier in Se tion 5.2, the time spent sele ting Φ̂α,Fl [G,Γ, h] is ubi in the size of |Φ̂α,Fl | . Hen e, ea h all to Filter takes O(n20(m+ nk)3) time. There are O(n3) dierent an hors and we onsider hains with O(nk) links, so Filter is alled O(n4k) times. Therefore, the total time spent ltering is O(n24k(m+ nk)3). It remains to bound the times that it takes to join one hain to another. In the worst ase we try to join every hain to every other hain. There are at mostO(n20k2(m+nk)2) su h pairs. For ea h pair, we try to join them with at most eight links and one jump. There are O(n8) su h paths. It takes O(n) time to test the feasibility of ea h su h path be ause ea h su h path has at most 27 segments. Therefore, AllViablePaths takes at most O(n29k2(m+ nk)2) +O(n24k(m+ nk)3) ⊂ O(n29k2(m+ nk)3) time. 55 Chapter 6 Shortest Bounded-Curvature Path Approximation As dis ussed in Se tion 2.2.1, nding a shortest bounded- urvature path amid arbitrary polygonal obsta les is NP-hard [23℄, even if the length and intri a y of a shortest path are known to be linear in n and m. Previous work on approximation algorithms has provided a (1 + ε)-approximation to the shortest ε-robust bounded- urvature path [18, 3℄. Although these results are very e ient (O(n2ε−4 log n) in [3℄), the restri tion to ε- robust paths is non-negligible. Spe i ally, robust solutions do not exist for all problem instan es that admit bounded- urvature paths. Furthermore, even if a ε-robust path exists, the shortest bounded- urvature path may be arbitrarily shorter than the shortest ε-robust path. Finally, these approa hes do not really address the di ulty exposed by the NP-hardness result be ause the only feasible paths in the asso iated redu tion have very low robustness (2−Ω(n)); in other words, it is ompletely onsistent with existing approximation algorithms that no general polynomial-time approximation s heme exists for shortest bounded- urvature paths. In this hapter, we des ribe an algorithm that unies and extends previous work on the feasibility and approximation of bounded- urvature paths. Spe i ally, our new algorithm removes the robustness requirement: it returns a (1+ε) approximation to the shortest path, whereas previous results return a (1 + ε) approximation to the shortest ε-robust path. A measure of length is taken as input by our algorithm. This measure is made relative to urvature bound. Spe i ally, we assume without loss of generality that the environment is s aled so that the urvature bound is one unit. Given a length parameter λ, our algorithm either (i) veries that every feasible path has length greater than λ or (ii) returns a feasible path that is at most (1 + O(ε)) times longer than the shortest feasible path. The run time of the algorithm is polynomially bounded in n, m, ε−1, and λ. (It follows, of ourse, that we ould produ e a true (1 + ε) approximation by s aling ε appropriately. In fa t, we will assume that our ε satises ε−1 ≥ γn2λ, for some onstant γ > 0.) Compared with our previous result, this new result ex hanges a polynomial dependen e on k (the minimum path intri a y) for a polynomial dependen e on the minimum path length λ. The intuition behind this swit h is straightforward: in 56 pra ti e, the desired approximation Π an be found in time dependent on its intri a y; however, to ertify that Π is lose to optimal, we look for paths that are shorter than Π; in general, a shorter path may have mu h greater intri a y than the intri a y of Π; fortunately, we an bound the intri a y of any path that is shorter than Π in terms of n and ‖Π‖; hen e, we an phrase our runtime bound in terms of λ instead of k. In the remainder of this hapter, we rst des ribe a path normalisation pro edure that in orporates the riti al observations from the previous approximation results [18, 3℄ with the te hniques developed in Chapter 3. After normalising a shortest path, the resulting path is at most (1 + ε) times longer and has a ombinatorial des ription. This allows us to nd an approximately shortest path by enumerating a nite (but potentially exponential-size) spa e. We next des ribe the redundan y used to lter the enumeration, whi h results in an e ient algorithm. This redundan y is a renement of the redundan y that we exploited in Chapter 4. This redundan y allows us to asso iate a su in t set of ongurations with every environment feature. These ongurations serve as an adequate set of potential he kpoints in the onstru tion of a path. The total size of these onguration sets is a dominant fa tor in the omplexity of our algorithm. Thus, the riti al step in our analysis is the demonstration that we an maintain a polynomial bound on the size of these onguration sets while still a hieving a good approximation. The te hniques used to maintain su h a bound are extensions of those developed in Chapters 4 and 5. 6.1 Path Normalisation In Chapter 2, we surveyed prior algorithmi results in bounded- urvature motion plan- ning that either normalise a given feasible path [17, 8, 5℄ or hara terise shortest feasible paths [2, 1, 10, 3, 18℄. The stru ture that results from normalisation enables a system- ati sear h for a path and narrows the spa e of paths onsidered. In this se tion, we ombine our new normalisation approa h (see Chapter 3) with the approa h taken by the previous approximation algorithms [18, 3℄. The intuition behind this hybrid is straightforward. Re all that our normalisation deforms a path until ea h onta t on- guration is moored. Spe i ally, if onta t onguration ever be omes an an hor, it will remain un hanged. To limit how mu h a path is deformed by normalisation, we introdu e new an hors. The result is that a path is stret hed by at most a fa tor of (1 + ε) by normalisation. In Se tion 2.1, one of the results that we dis ussed is the following hara terisation of shortest bounded- urvature paths in free spa e. Theorem. [16℄ In the absen e of obsta les, a shortest bounded- urvature path is type CLC or CCC. If its stru ture has type CCC, the middle C-segment has length at least π. We all a bounded- urvature path with the properties set out in the above theorem a Dubins jump. A Dubins jump diers from our earlier notion of a jump in that it may 57 have C-segments with length greater than π and may have stru ture CCC. In this hapter, the only types of jumps that we will onsider are Dubins jumps. Dubins jumps play an important role in this hapter be ause amid arbitrary polygonal obsta les, any shortest bounded- urvature path an be expressed as a sequen e of Dubins jumps (as rst noted in Se tion 2.2.4). Corollary. [18℄ Let Π be any shortest bounded- urvature path amid polygonal obsta les. When we split Π at its onta t ongurations, ea h resulting onta t-free subpath is a Dubins jump. We all any path that satises the above property JC-normal. This normal form is a generalisation of the FW-normal form. We an represent a JC-normal path in the same way that we represent a FW-normal path: as a sequen e of onta t ongurations 〈θi〉 and a sequen e of strings 〈Γi〉, where Γi is the stru ture of the jump from θi to θi+1. This representation redu es the problem of nding paths to that of determining whi h onta t ongurations an be rea hed from a given start onguration. Figure 6.1 represents a ontinuous range of JC-normal paths from the same start onguration to the same terminal onguration. Noti e that there is a ontinuous range of onta t ongurations, but in ea h ase, only one onguration represents a path of minimal length. Finding a shortest path requires identifying this single onguration, but (as we shall see) approximating it only requires nding a nearby onguration. αs αt (a) Conta t onguration an pivot about a orner. αt αs (b) Conta t onguration an slide along a wall. Figure 6.1: Conta t onguration degree of freedom. To this point, optimality has restri ted our attention to a ontinuous spa e of JC- normal paths. As we des ribe in Chapter 3, to further restri t our attention to a ountable set of paths, we impose additional onstraints: we roll onta t ongurations while keeping ea h su h onguration θi in onta t with every feature that it tou hes. Even with this restri tion, θi may still have one degree of freedom: when θi onta ts a single orner, the position of θi is xed, but its orientation may vary (see Figure 6.1(a)); when θi onta ts the interior of a wall, the dire tion of θi is xed, but its position may vary (see Figure 6.1(b)). These onta t-preserving motions (pivoting and sliding, respe tively) are the only ways that we deform paths. When we pivot, the rolling distan e is measured in radians; when we slide, the rolling distan e is measured in standard distan e units. Using this notion of rolling, we an formalise the denition of ε-robustness that is entral to previous approximation results (rst dened in Se tion 2.2.4). A jump 58 between two onta t ongurations is ε-robust if every simultaneous and independent ε- perturbation of its endpoint ongurations an be joined by another feasible jump of the same stru ture. More generally, a JC-normal path is ε-robust if ea h if its onstituent jumps is ε-robust. Note that a jump is non-robust if, for some ε-perturbation of ea h of its endpoint ongurations either (i) the resulting onguration pair annot be joined by a jump without violating feasibility, or (ii) the resulting onguration pair an be joined by a feasible jump but only by undergoing a stru tural hange. It follows from ondition (ii) that ea h segment of an ε-robust jump must be non-degenerate. The next lemma makes pre ise the intuition that small deformations of a jump J result in at most a small in rease its length ‖J‖. Lemma 6.1. [3℄ Let J and J ′ be any pair of similar-stru ture jumps between the same two features. Then |‖J ′‖ − ‖J‖| is bounded by the sum of the distan es between the orresponding endpoints of J and J ′. If a jump J between two onta t ongurations is ε-robust, ‖J‖ must be at least ε. It follows from the lemma above that if we perturb the sour e and destination ongurations of J by at most O(ε2), the length of the result is at most ‖J‖ + ε2 ≤ (1 + ε)‖J‖. Therefore, simultaneously and arbitrarily perturbing ea h onta t on an ε-robust path Π by O(ε2) auses the length of Π to in rease by a fa tor of at most (1 + ε). The previous algorithms that nd a (1 + ε) approximation to the shortest ε-robust path an be des ribed as follows [18, 3℄: (i) sample the spa e of possible onta t ongu- rations with O(ε2) granularity, and (ii) nd the shortest JC-normal path Π where ea h onta t onguration is a sampled onguration. The hoi e of O(ε2) granularity is used to onvert the absolute error bound given in Lemma 6.1 to a relative error bound. Spe i ally, to see that Π exists and is a (1 + ε) approximation, let Π′ be the shortest ε-robust path. We an perturb ea h onta t onguration of Π′ by at most O(ε2) to get Π′′ su h that ea h onta t onguration of Π′′ is a sampled onguration. Then Π′′ is a (1 + ε) approximation of Π′ by Lemma 6.1. Therefore, Π is at most (1 + ε) times longer than Π′ be ause Π is no longer than Π′′ by our hoi e of Π. We now des ribe a new type of normalisation that opes with the degenera ies that prevent a JC-normal path Π from being ε-robust. The general approa h is the same as we used in Chapter 3. However, it is ompli ated by that fa t that, in order to onsider only approximately-shortest paths, we must now deal with a family of paths whose form is less restri tive. As with the previous approximation approa hes, we rst uniformly sample the spa e of possible onta t ongurations, at ea h of the O(n) obsta le features, with granularity O(ε2). In addition, we identify, for ea h obsta le feature, the O(n3) onta t ongurations that o ur on over- onstrained jumps (the type 1, 2, and 3 an hor ongurations dened in Chapter 3). Together, we refer to these sampled ongurations, over- onstrained ongurations, start onguration αs, and terminal onguration αt, as an hor ongurations. There are O(n 3 + nε−2) su h ongurations in total. 59 Next, we ontinuously deform Π while preserving all of its onta ts and segment degenera ies. The goal is to exer ise any residual degrees of freedom in the path to bring its onta t ongurations as lose as possible to an an hor onguration. Our approa h is the same as in Chapter 3. If some onta t onguration annot be rolled dire tly to an an hor onguration, we are able to introdu e a new onstraint. Eventually, the path be omes ompletely onstrained and there is no freedom left. We summarise our new normalisation result in the following theorem. Theorem 6.2. Let Π be an arbitrary bounded- urvature path of length ‖Π‖ from a onguration αs to a onguration αt. Then there exists an ε-dis rete path Π ′ from αs to αt with length at most ‖Π‖(1+O(nε2)) and O(n‖Π‖) non-an hor onta t ongurations. Proof. We rst observe that the shortest feasible bounded- urvature path Π from αs to αt has O(n‖Π‖) onta t ongurations. The intuition behind this laim is that the shortest bounded- urvature path from a feature to the same feature is a unit radius ir le. Hen e, if we split Π into subpaths of length 2π, ea h subpath tou hes ea h of the n features at most on e. This reasoning is pre ise for orners, but we must rene it for walls. Noti e that on e Π rea hes a wall w at a onguration θ, Π an follow w to rea h other onta t ongurations at w in the dire tion of θ. Hen e, on e Π leaves w after θ, it must loop ba k (travel at least 2π) before rea hing w in the dire tion of θ be ause otherwise (as a shortest path) Π should not have left w. This implies that ea h subpath of length at most 2π has O(1) onta t ongurations at any parti ular wall. The proof that we an normalise Π to get a ε-dis rete path Π′ follows from the proof of Theorem 3.7: intuitively, we an roll unmoored ongurations of Π until there are no unmoored ongurations left. The analysis in Theorem 3.7 indi ates that this pro ess auses at most a onstant fa tor in rease in the number of non-an hor onta t ongurations. Hen e, Π′ has at most O(n ‖Π‖) non-an hor onta t ongurations be ause Π has at most O(n ‖Π‖) onta t ongurations. It remains to argue that Π′ is at most (1 + O(nε2)) times longer than Π. This fa t hinges on three invariants of rolling a onguration: it preserves the Π's onta t with the environment ( onta t ongurations may hange, but the onta t persists); it preserves the stru ture of the path between any two onta ts (spe i ally, stru tures only be ome more onstrained); and it limits the net hange in any onta t onguration to at most ε2 (this follows from our hoi e of an hors). It follows from Lemma 6.1 that ea h jump between onse utive onta ts of Π is stret hed by at most ε2. We argued above that there are O(n‖Π‖) su h jumps. Therefore, ‖Π′‖ ≤ ‖Π‖ + O(ε2n‖Π‖) = (1 +O(nε2))‖Π‖. An important property of all ε-dis rete paths is that they admit a ombinatorial des ription: ea h su h path onsists of a sequen e of onta t ongurations ea h of whi h is either an an hor onguration or is rea hable from an an hor onguration by a sequen e of links. 60 6.2 Systemati Sear h for Shortest ε-Dis rete Paths In this se tion, we des ribe an algorithm that onstru ts a feasible path Π′ that is at most (1+ ε) times longer than the shortest feasible path Π, provided that Π has length at most λ. Using the assumption stated in the introdu tion of this hapter that ε is su iently small, there exists an ε-dis rete path Π′ with length at most (1+ε) ‖Π‖ and at most O(nλ) onta t ongurations by Theorem 6.2. We an systemati ally sear h for this path be ause ε-dis rete paths have a ombinatorial des ription. Our approa h is roughly the same as the approa h in Chapter 4. We onstru t an an hor graph and nd the shortest path P in the an hor graph. This path P orresponds to a feasible bounded- urvature path Π′ that is at most (1 + ε) times longer that the shortest feasible path. There is one important dieren e between the an hor graph onstru ted in Chapter 4 and the an hor graph that we now onstru t: the weight of an edge now orresponds to the length of a linkage, rather than the number of onta t ongurations on a linkage. Sin e we are looking for an ε-dis rete path with at most O(nλ) onta t ongurations, it su es to nd a shortest (α, α′)-linkage with at most O(nλ) onta t ongurations, for every pair of an hor ongurations α, α′. Figure 6.2 outlines a systemati way to nd the shortest (α, α′)-linkage that has most τ onta t ongurations, for every pair of an hor ongurations α, α′. This algorithm is very similar to the exhaustive algorithm introdu ed in Chapter 4 (see Figure 4.2). This new algorithm keeps tra k of the shortest (α, α′)-linkage, whereas the previous algorithm keeps tra k of the (α, α′)-linkage with the least number of onta t ongurations. AllLinkages(τ) 1 for all an hor ongurations α do for h = 1 to τ do for all environment features F do Propagate(Φα,Fl−1 ) 2 for all pairs of an hor ongurations α, α′ do for all pairs of environment features F, F ′ do for all l and l′ su h that l + l′ ≤ τ do determine if there exist ongurations φ in Φα,Fl and φ′ in Φα ′,F ′ l′ su h that: (i) the jump joining φ and φ′ is ollision-free, and (ii) the (α, α′)-linkage through φ and φ′ is shorter than the shortest (α, α′)-linkage found so far. Figure 6.2: Pro edure for the onstru tion of all shortest (α, α′)-linkages with τ onta t ongurations. The algorithm in Figure 6.2 suers from the same problem as the algorithm in Figure 4.2: the size of Φα,Fl ould be exponential in l. Fortunately, it su es to dis over 61 only a single (α, α′)-linkage that is approximately the same length as the shortest (α, α′)-linkage. This allows us to identify and propagate only a subset of rea hable ongurations at ea h feature in ea h propagation phase. As before, the intuition is that if two rea hable ongurations at a feature F are su iently similar then it should be possible to repla e one by the other in all paths that use the rst without sa ri ing feasibility or signi antly in reasing the length of the path. While this intuition is basi ally orre t, the details of what onstitutes su iently similar and the analysis of the impa t of this redundan y elimination are somewhat involved. 6.3 Redundan y Among Conta t Congurations By allowing a fa tor (1 + ε) in rease in length, we were able to restri t our sear h to a nite spa e of paths (for a xed λ). In this se tion, we use a further potential in rease in length to restri t our sear h to a spa e of paths that is polynomially bounded in size. In this se tion, we argue that it su es to al ulate a subset Φ̂α,Fl of Φ α,F l , if we allow a slight in rease in path length. We start by rening the notion of almost spanning dened in Se tion 4.2. Re all that we said that a hain φ′ almost spans a hain φ, if two onditions are satised (see Figure 4.3): (a) φ′ and φ begin at the same onguration and (b) we an append φ′ with at most one jump J and at most one link K to rea h the nal onguration of φ. In the ontext of approximation, we add a third ondition to the notion of almost spanning: ( ) ‖φ′‖+ ‖J‖+ ‖K‖ ≤ ‖φ‖+ 2ε2. When nding hains that start with a parti ular an hor, we want to avoid produ ing redundant hains. We do this with a pro edure Filter, whi h we all periodi ally to remove hains that we do not need to extend (see Figure 6.3). The important aspe t of of ltering is that is does not eliminate too many hains, whi h we formalise with the Completeness Property below. The ondition distinguishes between the hains that Filter removes (unviable hains) and those that are not removed (viable hains). Completeness Property: If a hain φl ∈ Φ̂α,Fl is unviable, then ea h one-link exten- sion φl+1 of φl is almost spanned by some viable φ ′ l ∈ Φ̂α,Fl . In Chapter 5, we dis ussed how to implement Filter when the notion of almost span- ning just required onditions (a) and (b) above. The approa h was a divide-and- onquer algorithm: it divided Φ̂α,Fl into subproblems where it was easy to satisfy the Complete- ness Property. To satisfy ondition ( ), we make the subproblems smaller. We begin by partitioning Φ̂α,Fl into subsets Φ̂ α,F l [i] su h that the lengths of the hains in Φ̂ α,F l [i] lie in the range [(i − 1)ε2, iε2). Sin e we restri t our attention to paths of length at most λ(1 + O(ε)), the number of resulting partitions is at most λ(1 + O(ε))/ε2. We then lter ea h of these partitions in almost the same way as des ribed in Chapter 5. The main dieren e is that if L is the link from φl to φl+1 in the Completeness Property, we are areful that the length ‖J‖+ ‖K‖ of the path that extends φ′l to rea h φl+1 ex eeds ‖L‖ by at most ε2. Hen e, ondition ( ) of the denition of almost spanned is satised: ‖φ′l‖+ ‖J‖+ ‖K‖ ≤ [‖φl‖+ ε2] + [‖L‖+ ε2] = ‖φl+1‖+ 2ε2. 62 AllViableLinkages(τ) 1 initialise Φ̂α,F0 for all α and F for all an hors α do for h = 0 to τ − 1 do for all environment features F do if (h is divisible by 4) then Φ̂α,Fl ← Filter(Φ̂α,Fl ) Propagate(Φ̂α,Fl ) 2 for all pairs of an hors α, α′ do for all pairs of environment features F, F ′ do for all l and l′ su h that l + l′ ≤ τ do determine if there exist φ ∈ Φ̂α,Fl and ψ ∈ Ψ̂α ′,F ′ l′ su h that: (i) there is a path Π from φ to ψ with at most 8 links and one jump, and (ii) φ+Π + ψ is shorter than any (α, α′)-linkage found so far. Figure 6.3: Pro edure for the onstru tion of all shortest viable (α, α′)-linkages with τ non-an hor onta t ongurations. The result of repla ing a unviable hain with a viable hain may not be ε-dis rete. The next lemma shows that an unviable hain is also redundant when we restri t our attention to ε-dis rete paths. It is a slight extension of Lemma 4.2. This next result is used in main result of this hapter. Lemma 6.3. Let φl+1 be a one link extension of an unviable φl ∈ Φ̂α,Fl . If φl+1 is the prex of some (α, α′)-linkage Λ with O(nλ) non-an hor onta t ongurations, there exists a ε-dis rete path P from α to α′ su h that 1. a viable hain φ′l ∈ Φ̂α,Fl is the prex of P , 2. the sux of Λ is a sux of P , 3. P has at most three more non-an hor onta t ongurations than Π, and 4. ‖P‖ ≤ ‖Π‖+O(ε2nλ). Proof. To onstru t P , we start with Λ and repla e φl+1 with some φ ′ l that almost spans it. By our denition of almost spanned, the resulting path Λ′ is at most 2ε2 units longer than Λ and has at most one more onta t onguration than Λ. This path Λ′ is JC-normal but not ne essarily ε-dis rete. So we normalise Λ′. This results in a length in rease of at most O(ε2nλ) be ause Λ′ has O(nλ) jumps that are deformed by 63 normalisation (only the non-an hor onta t ongurations an hange). This explains ondition 4. Conditions 1 through 3 follow from the proof of Lemma 4.2. With the pre ise notion of redundan y given in the previous lemma, we now prove that AllViableLinkages an be used to nd a feasible path. Theorem 6.4. Suppose that there exists a bounded- urvature path Π from a start on- guration αs to a terminal onguration αt with length at most λ. Then there is an ε-dis rete path from αs to αt with length at most ‖Π‖(1 + O(ε)) and O(n‖Π‖) on- ta t ongurations that an be onstru ted from the linkages found by the pro edure AllViableLinkages(nλ). Proof. The proof of this theorem is very similar to the proof of Theorem 4.3. These two proofs only dier in our hoi e of the potential fun tion P(Π) that assigns a value to a path Π from αs to αt. Whereas, the potential fun tion in the proof of Theorem 4.3 only depends on the number of non-an hor onta t ongurations on Π (denoted c(Π)) and the viability of Π (denoted v(Π)), our new potential fun tion also depends on the length of Π. Spe i ally, we dene P(Π) as ‖Π‖ + ξε2nλ[5c(Π) − 4v(Π)], for some su iently large onstant ξ. Let Π∗ be a feasible ε-dis rete path with minimum potential. By Lemma 6.3 and the same arguments ontained in Theorem 4.3, if some linkage of Π∗ is not dis overed by AllViableLinkages(nλ), we an onstru t a path Π′ su h that c(Π′) ≤ c(Π∗)+3, v(Π′) ≥ v(Π∗) + 4, and ‖Π′‖ ≤ ‖Π∗‖ + O(ε2nλ). Hen e, P(Π′) ≤ ‖Π∗‖ + O(ε2nλ) + ξε2nλ[5c(Π∗)−4v(Π∗)−1]. We an rewrite this as P(Π′) ≤ P(Π∗)+O(ε2nλ)−ξε2nλ. By making ξ su iently large, P(Π′) must be less than P(Π∗), a ontradi tion. Therefore, every linkage on Π∗ is found by AllViableLinkages(nλ). We now show that ‖Π∗‖ ≤ (1+O(ε))‖Π‖. We an assume without loss of generality that Π is the shortest feasible path. Then c(Π) ≤ O(n‖Π‖) by the reasoning at the beginning of the proof of Theorem 6.2. By hoi e of Π∗, we know that P(Π∗) ≤ P(Π). Hen e, ‖Π∗‖ ≤ ‖Π‖+ξε2nλ ·5O(n‖Π‖). If we assume that ε−1 ≥ ξn2λ (as was stated in the introdu tion of this hapter), this inequality simplies to ‖Π∗‖ ≤ ‖Π‖ + ‖Π‖O(ε), whi h is the desired result. Finally, we show that c(Π∗) ≤ O(n‖Π‖). Re all that P(Π∗) ≤ P(Π) and c(Π∗) ≥ v(Π∗) (the argument for this inequality is given in Theorem 4.3). Hen e, ‖Π∗‖ + ξε2nλc(Π∗) ≤ ‖Π‖+ 5ξε2nλc(Π). Therefore c(Π∗) ≤ 5c(Π) be ause ‖Π∗‖ ≥ ‖Π‖. 64 Chapter 7 Con lusion In this thesis, we presented two algorithms for nding a bounded- urvature path amid polygonal obsta les. These algorithms are dierent from existing algorithms for bounded- urvature motion-planning in that they take an input parameter (k or λ) that bounds the omplexity of the desired output. Given su h a parameter, our algorithms are guar- anteed to nd a path (if one exists) in time that is polynomial in the bound on the output (k or λ), the size of the input n, and the input pre ision m. This is an advan e in the state-of-the-art be ause the only other algorithm that is guaranteed to dete t a feasible path amid arbitrary polygonal obsta les takes exponential time in the size of the input n and input pre ision m [17℄. Moreover, this algorithm just indi ates whether or not a feasible path exists (it does not return a des ription of a path), whereas our new algorithms return a des ription of the desired path. Our algorithms dier from previous bounded- urvature approximation algorithms in that they sear h for paths in a non-uniform, adaptive manner. To larify what we mean by non-uniform, the set of environment onta ts that we onsider is typi ally on entrated around degenera ies (su h as an hors). This is dierent from the prior shortest bounded- urvature approximation algorithms, in whi h the set of environment onta ts that are onsidered are distributed uniformly about ea h feature. To larify what we mean by adaptive, the environment onta ts that our algorithm onsiders are determined during the path sear h. We prune this sear h so that ea h path that we extend overs the paths that we do not extend. Intuitively, this fo uses attention away from easy to rea h regions. In ontrast, several other bounded- urvature motion plan- ning algorithms sele t the onta ts to be onsidered independent of the path sear h [18, 2, 3, 10℄. Our su essful appli ation of a non-uniform, adaptive sear h suggests that heuristi sear hes ould be made more robust (likely to nd a path) by being non-uniform and adaptive as well: intuitively, by sear hing more arefully around de- genera ies (e.g. where an hor ongurations o ur) and less arefully in easy to rea h areas, as determined by the sear h. Our algorithms rely on two new te hniques: the total dis retisation of the spa e of paths that we onsider and a sophisti ated argument that allows us to prune our sear h without sa ri ing ompleteness. We believe that both te hniques have wider 65 appli ation. These two te hniques were rst developed to nd a feasible path. In this thesis, we demonstrated their wider appli ability in reating an algorithm to nd an approximately shortest feasible path. Re all from Chapter 2 that the bounded- urvature motion restri tion is a spe ial type of kinodynami restri tion. In the kinodynami setting, the question of nding an approximation to the qui kest traje tory in polynomial time is open. To larify, there are approximation algorithms, but they return approximations to the qui kest δ-safe traje tories. Given a δ > 0, we an ontrive a simple problem instan e that admits a feasible traje tory but no δ-safe traje tory. Hen e, it is reasonable to ask if the te hniques in this thesis an be applied to remove the ondition of safety from the urrent approximation results. This is not at all lear. Moreover, even if it is possi- ble in prin iple, it might not be possible in pra ti e be ause the analysis be omes too ompli ated. To begin with, we would rst want to dis retise the spa e of traje tories. The dis retisations in this thesis relied heavily on Dubins hara terisation of short- est bounded- urvature paths [16℄. Unfortunately, in general, the stru ture of qui kest traje tories is mu h less understood than the stru ture of shortest bounded- urvature paths. Even in the one ase where the stru ture is well understood (in the plane where distan e is measured with the L∞ norm [12℄), it is un lear how to eliminate degrees of freedom from a traje tory by perturbation: unlike the bounded- urvature setting, there are two degrees of freedom at an obsta le onta t be ause the magnitude of the velo ity an vary; additionally, it is un lear how additional obsta le onta ts (something that o urs frequently in our bounded- urvature normalisation) eliminate freedom from a traje tory. For similar reasons, it is un lear our te hniques apply to nding bounded- urvature paths in three-dimensions: we do not urrently have a good understanding of what shortest bounded- urvature paths in three-dimensions look like, and any obsta le on- ta t has two degrees of freedom in three dimensions. Note that the worst ase paths that a omplete algorithm must nd are unrealisti for real-world roboti appli ations be ause they require tou hing obsta les and turning with great pre ision. The restri tion to ε-robust paths redu es the pre ision required, but paths must still brush up against the environment. Re all that a path is δ-safe if the entre of an δ-radius ball an tra e the path without the ball tou hing any obsta les. This denition is distin t from the notion of robustness: an ε-robust path is 0-safe be ause most of its turns tou h the environment, and there exist δ-safe solutions to problems where the only robust solutions are 0-robust. Finding an δ-safe path redu es to problems that we have already onsidered by taking a Minkowski sum of the obsta les with an δ-radius ball. Hen e, we are ondent that our results an be generalised to nd an δ-safe bounded- urvature path amid polygonal obsta les in the plane in polynomially bounded time. However, the problem be omes more interesting if we are satised with a path that is less safe: say for example, if we are satised with nding a (δ/2)-safe path, whenever a δ-safe path exists. This avenue of resear h has been explored in the higher dimensions: there is a non-uniform dis retisation approa h to nding an (1 + ε) approximation to the shortest δ-safe (almost) bounded- urvature path in three or more 66 dimensions [25℄. In this ase, the returned path is only guaranteed to be (δ/3)-safe. A hieving a similar result in two dimensions is open. We are optimisti that rephrasing the problem in terms of safety would allow us to a hieve asymptoti ally better bounds than we have a hieved in this thesis. Moreover, we feel that the restri tion to safe paths is a more realisti than the restri tion to robust paths. Shortest bounded- urvature paths with reversals in the plane are also omposed of C-segments and L-segments [22℄. Finding a feasible path is less interesting in this setting be ause we an approximate an given ontinuous path by using an arbitrary number of reversals. However, nding a path with bounded number of reversals (e.g. a path with intri a y at most k) is an open problem. One ompli ation is that reversals an o ur on an obsta le boundary. So we no longer have just one degree of freedom when a path tou hes a wall. Although the run times of our algorithms are a fun tion of input pre ision m, we have still exploited the Real RAM model of omputation in our analysis. This is similar to the (1 + ε) approximation algorithm developed by Papadimitriou for nding the shortest un onstrained path amid arbitrary polyhedra in three dimensions [21℄. Subsequent work has shown that Papadimitriou's approa h works in polynomial time in a bit model of omputation [14℄. It remains to be seen if our algorithms also have a polynomially bounded omplexity in a bit model. The loose bound on the run time of our feasibility algorithm is O(n29k2(m+ nk)3). In this thesis, we abandoned our attempts to optimise the asymptoti bound on the run time in order to simplify our analysis. However, the subtleties that lead to a high degree bound are real issues that any omplete algorithm must address. Therefore, it is not lear if any omplete algorithm an be asymptoti ally ompetitive with the fast O(n2ε−4 log n) approximation algorithm for ε-robust paths. Our algorithms take parameters that limit the length or intri a y of the paths that they onsider. However, there is no known upper bound on the length or intri a y of the feasible paths in arbitrary polygonal environments, whi h poses an open problem. If the ne essary intri a y is polynomially bounded, the run times of algorithms presented here are polynomially bounded in the size of the input. Otherwise, minimising the intri a y is a well justied optimisation riteria. This is analogous to nding a minimum-link path when there are no onstraints on the path. Our feasibility result only nds an approximately minimum intri a y path. To larify, it returns a path with intri a y at most O(nk + n3), when a path of intri a y k exists. An open problem is to lose this gap: to nd a path with intri a y at most O(k) when a path of intri a y k exists. A good starting point is understanding what bounded- urvature paths (with or without reversals) with minimum intri a y look like. Finding su h a hara terisation is an open problem. 67 Bibliography [1℄ Pankaj K. Agarwal, Therese Biedl, Sylvain Lazard, Steve Robbins, Subhash Suri, and Sue Whitesides. Curvature- onstrained shortest paths in a onvex polygon. SIAM Journal on Computing, 31(6):18141851, 2002. [2℄ Pankaj K. Agarwal, Prabhakar Raghavan, and Hisao Tamaki. Motion planning for a steering- onstrained robot through moderate obsta les. In STOC '95: Pro- eedings of the twenty-seventh annual ACM symposium on Theory of omputing, 1995. [3℄ Pankaj K. Agarwal and Hongyan Wang. Approximation algorithms for urvature- onstrained shortest paths. SIAM Journal on Computing, 30(6):17391772, 2001. [4℄ Hee-Kap Ahn, Otfried Cheong, Ji°í Matou²ek, and Antoine Vigneron. Rea hability by paths of bounded urvature in onvex polygons. In SCG '00: Pro eedings of the sixteenth annual symposium on Computational geometry, pages 251259, New York, NY, USA, 2000. ACM Press. [5℄ Jonathan Ba ker and David Kirkpatri k. Finding urvature- onstrained paths that avoid polygonal obsta les. In SCG '07: Pro eedings of the Twenty-Third Annual Symposium on Computational Geometry, pages 6673, New York, NY, USA, 2007. ACM. [6℄ Jonathan Ba ker and David Kirkpatri k. A omplete approximation algorithm for shortest bounded- urvature paths. In Algorithms and Computation, pages 628643. Springer-Verlag, 2008. [7℄ Mi hael Ben-Or, Dexter Kozen, and John Reif. The omplexity of elementary algebra and geometry. Journal of omputer and system s ien es, 32:251, 1986. [8℄ Sergey Bereg and David Kirkpatri k. Curvature-bounded traversals of narrow orridors. In SCG '05: Pro eedings of the twenty-rst annual symposium on Com- putational geometry, pages 278287, New York, NY, USA, 2005. ACM Press. [9℄ Jean-Daniel Boissonnat, André Cérézo, and Juliette Leblond. Shortest paths of bounded urvature in the plane. Journal of Intelligent and Roboti Systems, 11(1):520, Mar h 1994. 68 [10℄ Jean-Daniel Boissonnat and Sylvain Lazard. A polynomial-time algorithm for omputing shortest paths of bounded urvature amidst moderate obsta les. Inter- national Journal of Computational Geometry & Appli ations, 13(3):189229, 2003. [11℄ Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan S hirra, and Susanne S hmitt. A separation bound for real algebrai expressions. In Le ture Notes in Computer S ien e: European Symposium on Algorithms 2001, volume 2161, pages 254. Springer-Verlag, January 2001. [12℄ John Canny, Ashutosh Rege, and John Reif. An exa t algorithm for kinodynami planning in the plane. Dis rete and Computational Geometry, 6(1):461484, De- ember 1991. [13℄ John Canny and John Reif. New lower bound te hniques for robot motion planning problems. In Pro eedings of the 28th IEEE Symposium on the Foundations of Computer S ien e, New York, 1987. IEEE. [14℄ Joonsoo Choi, Jürgen Sellen, and Chee-Keng Yap. Approximate eu lidean shortest path in 3-spa e. In SCG '94: Pro eedings of the tenth annual symposium on Computational geometry, pages 4148, New York, NY, USA, 1994. ACM Press. [15℄ George E. Collins. Hauptvortrag: Quantier elimination for real losed elds by ylindri al algebrai de omposition. In Pro eedings of the 2nd GI Conferen e on Automata Theory and Formal Languages, pages 134183, London, UK, 1975. Springer-Verlag. [16℄ L. E. Dubins. On urves of minimal length with a onstraint on average urvature, and with pres ribed initial and terminal positions and tangents. Amer. J. Math., 79:497516, 1957. [17℄ Steven Fortune and Gordon Wilfong. Planning onstrained motion. Ann. Math. Arti ial Intelligen e, 3(1):2182, 1991. Algorithmi motion planning in roboti s. [18℄ Paul Ja obs and John Canny. Planning smooth paths for mobile robots. In Pro- eedings of the 1989 IEEE International Conferen e on Roboti s and Automation, pages 27, 1989. [19℄ David S. Johnson. The NP- ompleteness olumn. Journal of Algorithms, 3(1):182 195, 1982. [20℄ Jean-Claude Latombe. Robot Motion Planning (The Springer International Series in Engineering and Computer S ien e). Springer, De ember 1990. [21℄ Christos H. Papadimitriou. An algorithm for shortest-path motion in three dimen- sions. Inform. Pro ess. Lett., 20(5):259263, 1985. 69 [22℄ J. A. Reeds and L. A. Shepp. Optimal paths for a ar that goes both forwards and ba kwards. Pa i J. Math., 145(2):367393, 1990. [23℄ John Reif and Hongyan Wang. The omplexity of the two dimensional urvature- onstrained shortest-path problem. In WAFR '98: Pro eedings of the third work- shop on the algorithmi foundations of roboti s on Roboti s : the algorithmi per- spe tive, pages 4957, Nati k, MA, USA, 1998. A. K. Peters, Ltd. [24℄ John H. Reif and James A. Storer. A single-exponential upper bound for nding shortest paths in three dimensions. J. ACM, 41(5):10131019, 1994. [25℄ John H. Reif and Hongyan Wang. Nonuniform dis retization for kinodynami motion planning and its appli ations. SIAM J. Comput., 30(1):161190, 2000. [26℄ Jürgen Sellen, Joonsoo Choi, and Chee-Keng Yap. Pre ision-sensitive eu lidean shortest path in 3-spa e. SIAM Journal on Computing, 29(5):15771595, 2000. [27℄ Mi ha Sharir. Algorithmi motion planning. In Ja ob E. Goodman and Joseph O'Rourke, editors, Handbook of Dis rete and Computational Geometry, hapter 57, pages 10371064. CRC Press LLC, Bo a Raton, FL, 2004. [28℄ Mi ha Sharir and Amir S horr. On shortest paths in polyhedral spa es. In STOC '84: Pro eedings of the sixteenth annual ACM symposium on Theory of omputing, pages 144153, New York, NY, USA, 1984. ACM Press. [29℄ Gordon T. Wilfong. Motion planning for an autonomous vehi le. In Pro eedings of IEEE International Conferen e on Roboti s and Automation, pages 529533, 1988. 70 Appendix A Jumps between Corners In this appendix we prove several properties of jumps from a orner F to a orner G. These properties allows us to dene su ient onditions to guarantee that two jumps do not ross. We use them to prove the orre tness of our approa h to ltering ongurations. The rst main result of this appendix states that all jumps are ontained in a region R between F and G (see Lemma A.1). This region R has the property that any jump J from F to G splits R into two smaller regions S1 and S2. These smaller regions orrespond to dierent sides of J and satisfy the following property: if jump K is on one side of J (i.e. K ⊆ S1) and jump K ′ is on the other side (i.e. K ′ ⊆ S2), then K and K ′ do not ross. The se ond main result is a su ient ondition to guarantee that two jumps do not ross (see Lemma A.2): if two jumps K and K ′ from F to G share a ommon sour e onguration or a ommon destination onguration, then K and K ′ do not ross. A.1 Sides of a Jump We rst argue that all jumps from a orner F to a orner G are ontained in one region R dened as follows: let R1 be the region swept out by a radius two dis whose entre tra es the line segment between F and G; let R2 be the portion of the line through F and G that is not between F and G; then let R = R1 \R2 (see Figure A.2(b)). Lemma A.1. Every jump J from F to G is ontained in a region R. The region R is su h that any su h J splits R into two regions, alled the sides of J . Proof. We rst show that the L-segments of su h jumps are ontained inR. Let J (θ) be the set of jumps from F to G where the L-segment points in dire tion θ (see Figure A.1). Let J be an arbitrary jump in J (θ). As we tra e a point on the L-segment of J in the dire tion of the L-segment, the point gets progressively farther from F and loser to G. This is true be ause the sour e and destination C-segments of J have length at most π. Hen e, the L-segment of J lies in the interse tion of two half planes (see Figure A.1(a)): 71 the boundary of the rst half-plane starts at F and the half-plane points in the dire tion of θ; the boundary of the se ond half-plane starts at G and the half-plane points in opposite dire tion of θ. We also note that an L-segment of J starts at most two units from F be ause the sour e C-segment has length at most π (see Figure A.1(b)). Hen e the L-segment is ontained in the light shaded region of Figure A.1(b). Similarly, the L-segment of J ends at most two units from G. F G (a) L-segments of jumps get farther from F and loser to G. F G (b) L-segments start at most two units from F . Figure A.1: Jumps from F to G with L-segments pointing in one xed dire tion. Combining all of our observations so far, the L-segment of J must lie in the darkly shaded parallelogram of Figure A.2(a). We overestimate this region with the lightly shaded parallelogram: two sides are parallel to the line through F and G; the other two sides are perpendi ular to θ. The union over all θ of these overestimates is R (see Figure A.2(b)). This region has two small slits be ause our arguments are overestimates: L-segments rarely rea h the interior of the sides of our bounding parallelograms that are perpendi ular to θ (just at F and G). A more rened analysis shows if there is a jump from F to G where the L-segment is dire ted verti ally (perpendi ular to the line through F and G), the distan e between F and G is exa tly two or four; in these ases, the L-segment is ontained in R. It remains to be shown that jump C-segments are ontained in the shaded regions. If we ignore the slits, the C-segments are learly in this region be ause every point on a jump C-segment is at most two units from a orner. To see that C-segments do not ross these slits, onsider the lo us of jumps starting with a ounter lo kwise oriented C-segment (see Figure A.3). This pi ture proves that a ounter lo kwise oriented sour e C-segment annot ross a slit: if the sour e C-segment interse ts the slit tou hing F , G is ontained in the unbounded region that annot be rea hed; if this sour e C-segment rosses the slit tou hing G, then G is ontained in the unit radius ir le that annot be rea hed. By verti ally ree ting Figure A.3, it is learly true that lo kwise oriented 72 F G (a) The L-segments of J (θ) lie in the dark shaded region. We overestimate it with light shaded region. (b) The union of our overestimate for all θ is R. Figure A.2: L-segments are ontained in R. sour e C-segments annot ross either slit. By reversing the jumps and inter hanging the roles of F and G, the same arguments show that the destination C-segments annot ross either slit. Figure A.3: Points rea hed by a jump starting with a lo kwise oriented C-segment. A.2 Non-Crossing Condition In this se tion we prove the following lemma. Lemma A.2. Let J and K be two jumps from F to G. If J and K share the same sour e onguration or the same destination onguration, then J and K do not ross. By reversal of J and K, we only need to onsider the ase where J and K have a ommon destination onguration. We start by proving a mu h weaker result: if the rst C-segments of J and K have the same orientation and the se ond C-segments of J and K have the same orientation, then J and K do not ross. We prove this by onsidering two distin t ases: either the 73 C-segments of J have the same orientation (see Lemma A.3) or the C-segments of J have a dierent orientations (see Lemma A.4). Lemma A.3. Jumps with signed stru ture C+LC+ from a orner to a onguration do not ross. Proof. Let c be the orner that the jumps leave from and O be the underlying ir le that all of the jumps rea h. We assume without loss of generality that c and the entre of O lie on the x-axis (translation and rotation), that c is left of the entre of O (horizontal ree tion), and that O is lo kwise oriented (verti al ree tion). c (a) C-segments from c do not ross. O (b) L-segments to O do not ross. Figure A.4: Segments of the same type do not ross. Two sour e C-segments from c do not ross be ause the C-segments have length at most π (see Figure A.4(a)). Two L-segments rea hing O do not ross (see Figure A.4(b)). Hen e any rossing between two jumps must o ur between the sour e C- segment of one jump and the L-segment of the other. C c OX o p q U T (a) Range of jumps. p c X O q T Lp Cq o (b) Ordering of jumps. Figure A.5: Jumps from c to O starting with a lo kwise C-segment. We represent ea h jump from c to O by the entre of its initial underlying ir le. Every initial underlying ir le entre lies on a unit-radius lo kwise-oriented ir le C entred at c (see Figure A.5(a)). The restri tion that the sour e C-segment has length at most π further restri ts ea h ir le entre to the lo kwise-oriented ar X. This ar X an be dened as follows: let p be a point of C and T be the oriented line tangent to C at p; then p ∈ X if and only if the ir le entre o of O is not on the right-hand side 74 of T . Hen e, X is bounded by tangent points p and p′ where the orresponding tangent lines T and T ′ ontain pass through o. Figure A.5(b) illustrates two jumps from c to O with sour e underlying ir le entres p and q. We order these entres by the orientation of X. In this ase, p omes before q. The C-segment Cq of a later jump does not interse t the L-segment Lp of an earlier jump (see Figure A.5(b)): draw a line T from the entre p of the ir le underlying D to o; then T is parallel to Lp, and they are exa tly one unit apart; moreover, T splits X into two parts by the geometri denition of X given in the previous paragraph; so T splits q and Lp be ause Lp lies entirely to one side of T and q omes after p on X; this veries that q is more than one unit away from Lp; hen e, Cq does not interse t Lp. c O q X p Lq Cp b (a) L-segment ontained in onvex region. c O bq′ q o T ′ T B C X Lq p (b) M starts from ir le entered at p. Figure A.6: Earlier C-segment does not ross later L-segment. We now show that the C-segment Cp of an earlier jump does not interse t the L- segment Lq of a later jump (see Figure A.6(a)). If both endpoints of Lq are in the onvex gray region of Figure A.6(a), then Lq does not ross the boundary, whi h ontains Cp. Clearly the last endpoint of Lq is in the onvex region. Figure A.6(b) explains why the rst endpoint b of Lq is in the region: let T be a line from q to the entre o of O; then T is parallel to Lq, and both are exa tly one unit apart; hen e, the unit-radius ir le B entred at b is ompletely to the left of T ′; let C be the unit ir le entred at c; learly q is on both C and B; let q′ be the other point ommon to C and B; then q′ is left of T be ause q′ is on B and B is left of T . Let T ′ be parallel to T but through q′; then T ′ is left of T ; hen e o is right of T ′ be ause T ′ and T are parallel; this erties that q′ is not on X; let p be a point of X that ome before q; then p is on the ar of C from q′ to q; therefore p is ontained in B (i.e. p is less than one unit away from b). Lemma A.4. Jumps of type C−LC+ from a orner to a onguration do not ross. Proof. We prove that jumps starting with a ounter lo kwise-oriented C-segment from a orner c to a lo kwise-oriented unit-radius ir le O do not ross. The arguments are similar to the previous proof but have a few additional ompli ations. As before, the sour e C-segment of one jump annot ross the sour e C-segment of another, and the L-segment of one jump annot ross the sour e C-segment of another. Hen e, any 75 rossing must o ur between a sour e C-segment of one and a L-segment of another. Our proof shows that this annot happen. c O X O′ C q p o UT (a) Distan e from c to o less than three. O c q p O′ X C T U o (b) Distan e from c to o greater than three. Figure A.7: Range of jumps from c to O starting with a ounter lo kwise C-segment. One ompli ating fa tor is that there is a qualitative dieren e in the way in whi h the range of jumps from c to O is bounded that depends on the distan e from c to the entre o of O. If the distan e is less than three, then the range of jumps is bounded by a jump with a zero-length sour e C-segment and a jump with a zero-length L-segment (see Figure A.7(a)). If the distan e is greater than three, then the range is bounded by a jump with a zero-length sour e C-segment and a jump with a π-length sour e C-segment (see Figure A.7(b)). As before, we represent jumps from c to O by the entres of their sour e underlying ir les. Let the ounter lo kwise oriented ar X be the domain of sour e underlying ir le entres. Figure A.8 illustrates two jumps represented by entres p and q. As before, we order jumps by the order of their initial underlying ir le entres on X. In this ase, p omes before q. In this proof, we rely on two properties of X. Fa t A.5. Let O′ be the lo kwise-oriented radius-two ir le entred at o. Suppose that p ∈ X. Then 1. the oriented line T from p and tangent to O′ interse ts X on e, and (a) the oriented half line T ′ emanating from X and tangent to X at p does not interse t O'. Proof. The rst property results from the restri tion that the sour e C-segment has length at most π: in general, T interse ts the unit-radius ir le entred at c twi e; ea h of these interse tions orresponds to a type C−L path from c to O, but only one of these paths has a C-segment with length at most π. The se ond property is a onsequen e of the rst: rotate T away from O′ about p until it be omes tangent to X. The sour e C-segment Cq from a later jump does not ross the L-segment Lp of an earlier jump (see Figure A.8): let T be the oriented line from p and tangent to O′; then T is parallel to Lp, and both are exa tly one unit apart; moreover, T splits X into two 76 TpX q O c O′ Lp Cq Figure A.8: Later C-segment does not ross earlier L-segment. pie es; in parti ular, q and Lp are on dierent sides of T ; hen e q is at least one unit from Lp; therefore Cq does not ross Lp. We now show that sour e segment C-segment Cp of an earlier jump does not ross the L-segment Lq of a later jump. This argument onsists of two distin t parts: the ir le underlying Cp ontains the rst endpoint of Lq, and Lq annot ross Cp be ause the relevant parts of Lq are ontained in a onvex region bounded by Cp. T ′ T q q′ O′ O c b o Lq C B X (a) Later L-segment starts from earlier underlying ir le. O p q Lq Cp X P b c m (b) Relevant part ofM ontained in onvex region. Figure A.9: Earlier C-segment does not ross later L-segment First, let b be the initial endpoint of an L-segment Lq of a jump represented by q (see Figure A.9(a)). Let B be the unit-radius ir le entred at b. To omplete the rst part of our proof, it su es to show that every point of X before q is ontained in B. Let T be the oriented line from q and tangent to O′. Then T is parallel to Lq. Moreover, B is ompletely to the right of T . Let C be the ounter lo kwise-oriented unit-radius ir le entred at c. Clearly q is on both C and B. Let q′ be the other point ommon to C and B. Then q′ is right of T be ause B is right of T . Let T ′ be the half line from q′ tangent to C. Then T is parallel to T ′. Hen e, T ′ is right of T be ause T ′ ontains q′ whi h is right of T . The distan e between T and T ′ is less than two be ause the distan e between q′ and q is less than two. Hen e, T ′ interse ts O′ be ause T ′ and T are on the same side of T . Thus q′ 6∈ X by Fa t A.5. The range of C from q′ to q is ontained in B. Therefore, all of X that omes before q is ontained in B. We now show that Lq does not ross Cp (see Figure A.9(b)). Let P be the line underlying Lp of the earlier jump represented by p. Let D be the ir le underlying the C-segment Cp. Then D is on the left of P and O is on the right. We know that Lq 77 rosses P be ause it starts inside D and ends at O. However, the part of Lq on the right side of P is irrelevant be ause it annot ross D. The point m where Lq rosses P must be after the L-segment Lp of the earlier jump p be ause the half lines in Figure A.4(b) do not interse t. So m is on the boundary of the shaded onvex region in Figure A.9(b). The part of Lq that an ross Cp is between b and m. However, b and m are in the shaded onvex region, whi h has Cp on the boundary. Therefore Cp and Lq do not ross. We now generalise our non- rossing ondition to jumps whose se ond C-segments have the same orientation. Corollary A.6. Jumps of with signed stru ture CLC+ from a orner to a onta t onguration at a wall do not ross. Proof. Let J1 and J2 be two su h jumps. If J1 and J2 start with a lo kwise-oriented C-segment, they do not ross by Lemma A.3. If they both start with a ounter lo kwise- oriented C-segment, they do not ross by Lemma A.4. φ (a) Jumps with signed stru - ture C+LC+. φ (b) Jumps with signed stru - ture C−LC+. φ ( ) Jumps with ne stru ture C0LC + . Figure A.10: Lo us of points rea hing a onguration φ. Otherwise, there is a type C0LC + jump S from the orner to the ommon ong- uration (see Figure A.11): Let φ be the destination onguration ommon to J1 and J2. Figure A.10(a) shows the lo us of points that an rea h φ via a jump with C +LC+ signed stru ture. Figure A.10(b) shows the lo us of points that an rea h φ via a jump with C−LC+ signed stru ture. The interse tion of these two regions is the lo us of points that an rea h φ via a jump with C0LC + ne stru ture (see Figure A.10( )). Let R be the region that ontains J1, J2, and S indi ated by Lemma A.1. Then S splits R into two pie es (see Figure A.11). Ea h jump Ji is ontained in some pie e be ause Ji does not ross S by Lemma A.3 and Lemma A.4. Moreover, the sour e orientations J1 and J2 point to dierent sides of S, so J1 and J2 lie in dierent pie es of S. Hen e, J1 and J2 do not ross. We are now ready to prove Lemma A.2. Re all that it su es to prove that two jumps J1 and J2 that end with the same onguration φ do not ross. If the orientations of the se ond C-segments of J1 and J2 are the same, they do not ross by Corollary A.2. 78 SJ2 J1 Figure A.11: The jump S erties that J1 and J2 do not ross. Otherwise, there is a type CLC0 jump S from the orner to φ (see Figure A.12( )): Figure A.12(a) shows the lo us of points that an rea h φ via a jump with CLC+ signed stru ture. The verti al ree tion of this represents the lo us of points that an rea h φ via a jump with CLC− signed stru ture. The interse tion of these two regions is the lo us of points that an rea h φ via a jump with CLC0 ne stru ture (see Figure A.12(b)). φ (a) Lo us of jumps with signed stru ture CLC+ that rea h φ. φ (b) Lo us of jumps with ne stru ture CLC0 that rea h φ. S J1 J2 φ ( ) The jump S erties that J1 and J2 do not ross. Figure A.12: Jumps to the same onguration φ do not ross. Let R be the region that ontains J1, J2, and S indi ated by Lemma A.1. Then S splits R into two pie es (see Figure A.12( )). Ea h jump Ji is ontained in some pie e be ause Ji does not ross S by Corollary A.6. Moreover, J1 and J2 are on dierent sides of S be ause the orientations of the se ond C-segments of J1 and J2 are dierent. Hen e, J1 and J2 do not ross. 79 Appendix B Links between Corners In this appendix, we restri t our analysis to links of a parti ular ne stru ture between two orners F and G. Consider, for example, the set of links with stru ture C−L0C+ illustrated in Figure B.1. Within this ontext, we will show three main results: if you roll the sour e onguration in a lo kwise dire tion, the destination onguration deforms in a lo kwise dire tion (see Lemma B.1); no two links ross (see Lemma B.2); and there are O(n) homotopy lasses of links amid polygonal obsta les (see Lemma B.3). F G Figure B.1: A range of C−L0C+ stru ture links from F to G. B.1 Link Monotoni ity In this se tion, we prove the following. Lemma B.1. Links of a xed ne stru ture Γ from one orner to another are mono- toni . That is, rolling the sour e onguration ounter lo kwise always auses the des- tination onguration to turn lo kwise. We prove this lemma by onsidering ea h type Γ of link between orners. We re- du e the number of ases that we onsider through symmetry. First we note a strong orresponden e between links with stru ture C−pi LC − and C0LC + : for every link with 80 stru ture C0LC + , we obtain a orresponding link with stru ture C−pi LC − by ree t- ing the sour e and destination ongurations through their onta ts (see Figure B.2). Hen e, we do not expli itly links with stru ture C±pi LC ± and C±LC±pi be ause they are symmetri to other ases that we onsider. 0LC piLC Figure B.2: Same underlying ir le entres. We assume without loss of generality that the orners lie on the x-axis (by suitable rotation and translation). We denote the distan e between the orners ∆. B.1.1 Links with Stru ture C0LC and CLC0 The reverse of link with stru ture C0LC has stru ture CLC0, so we only onsider the former. We assume without loss of generality that the C-segment tou hes the orner on the right (by a horizontal ree tion) and that the nal C-segment is oriented lo kwise (by a verti al ree tion). Figure B.3 shows two links with stru ture C0LC + . Our analysis fo uses on a quadrilateral formed by the underlying ir le entres and orners. 1 1 e ∆ θ γ φ (a) Non-self-interse ting quadrilateral. s 1 1 e γ −φ θ ∆ (b) Self-interse ting quadrilateral. Figure B.3: Monotoni ity of links with stru ture C0LC + . We rst look at the proje tions of the sides adja ent to φ onto the side perpendi ular to the side of length e. sin γ +∆cos θ = 1 (B.1) cos γ · dγ dθ −∆sin θ = 0 dγ dθ = ∆sin θ cos γ (B.2) 81 Then we look at the proje tions of the sides adja ent to φ onto the side of length e. ∆sin θ = e+ cos (π − γ) cos γ +∆sin θ = e (B.3) The sum of the interior angles of a quadrilateral is onstant. θ + π 2 + γ + φ = 2π 1 + dγ dθ + dφ dθ = 0 dφ dθ = − ( 1 + ∆ sin θ cos γ ) by Equation B.2 = −cos γ +∆sin θ cos γ = − e cos γ by Equation B.3 This tells us monotoni ity of φ relative to θ is governed by the sign of cos γ. Looking at Figure B.3, we see that γ is π/2 plus the length of the C-segment. Hen e, pi 2 ≤ γ ≤ 3pi 2 , whi h means that cos γ is always negative. So φ always in reases with θ. B.1.2 Links with Stru ture C±LC∓pi and C ± pi LC ∓ The reverse of link with stru ture C±LC∓pi is a link with stru ture C ± pi LC ∓ , so we only onsider the latter. We assume, without loss of generality, that the π length C-segment starts at the left orner (by a horizontal ip) and that the left C-segment is ounter- lo kwise oriented (by a verti al ip). Again, our analysis fo uses on a onstrained quadrilateral. ∆ 3 e 1 θ φ γ Figure B.4: Monotoni ity of links with stru ture C−pi LC + . The geometry underlying a link with stru ture C−pi LC + (see Figure B.4) is very similar to the geometry underlying a link with stru ture C0LC + (see Figure B.3): the length three side in the former gure has length one in the latter. Fortunately, the same analysis works be ause the derivative of the onstant length in Equation B.1 is zero regardless of the value (zero or three). 82 B.1.3 Links with Stru ture CL0C We rst examine the relationship between angles of an arbitrary quadrilateral when the side lengths are xed (see Figure B.5). Then we use those results to show that a link with stru ture CL0C is monotoni . α β γ δ ~a ~b ~c ~d Figure B.5: Arbitrary quadrilateral expressed as ve tors and angles. Let ~uand ~v be ve tors in the plane. Dene ~u · ~v = ‖~u‖ ‖~v‖ cos θ and ~u × ~v = ‖~u‖ ‖~v‖ sin θ, where θ is the lo kwise angle from u to v. In parti ular, the dot produ t is ommutative (~u ·~v = ~v ·~u) but the ross produ e is not quite (~u×~v = −~v×~u). Both of these produ ts are distributive. We rst derive Equation B.4 that has a simple geometri interpretation when the quadrilateral is simple: the quadrilateral in Figure B.5 has two triangulations; the sum of the areas of one de omposition are the same as the sum of the areas of the other de omposition. ~a+~b+ ~c + ~d = 0 ~a+ ~c = − ( ~b+ ~d ) (~a+ ~c)× ( ~b+ ~d ) = 0 ~a×~b+ ~a× ~d+ ~c×~b+ ~c× ~d = 0 ~a×~b+ ~c× ~d = − ~a× ~d− ~c×~b = ~b× ~c+ ~d× ~a (B.4) We now derive the derivative of opposite angles in the quadrilateral (see Equation B.6). ~a+~b+ ~c + ~d = 0 ~a+~b = − ( ~c+ ~d ) (B.5)( ~a+~b ) · ( ~a+~b ) = ( ~c+ ~d ) · ( ~c+ ~d ) ~a · ~a+ 2~a ·~b+~b ·~b = ~c · ~c+ 2~c · ~d+ ~d · ~d d dα ( ~a ·~b ) = d dα ( ~c · ~d ) d dα ( ‖~a‖ ∥∥∥~b∥∥∥ cosα) = d dα ( ‖~c‖ ∥∥∥~d∥∥∥ cos γ) 83 −‖~a‖ ∥∥∥~b∥∥∥ sinα = −dγ dα ‖~c‖ ∥∥∥~d∥∥∥ sin γ dγ dα = ~a×~b ~c× ~d (B.6) By relabelling, dδ dβ = ( ~b× ~c ) / ( ~d× ~a ) . Assume that the sum α + β + γ + δ is some onstant multiple C of 2π. This not true in general be ause of the y li nature of angle parameterisation: for example, as an angle passes through 0 to 2π the onstant must hange. However, we an make it hold lo ally (around values lose to the original values) by reparameterising the angles as ne essary (e.g. [−π, π) instead of [0, 2π)). α + β + γ + δ = 2Cπ α + γ = 2Cπ − (β + δ) d dα (α + γ) = −dβ dα · d dβ (β + δ) 1 + dγ dα = dβ dα [ −1− dδ dβ ] 1 + ~a×~b ~c× ~d = − dβ dα 1 + ~b× ~c ~d× ~a by EquationB.6 ~a×~b+ ~c× ~d ~c× ~d = − dβ dα ~b× ~c+ ~d× ~a ~d× ~a dβ dα = − ~a×~b+ ~c× ~d ~b× ~c+ ~d× ~a ~d× ~a ~c× ~d = − ~d× ~a ~c× ~d by EquationB.4 We now onsider links with stru ture CL0C. We assume, without loss of generality, that the link goes from left orner to right orner (by a horizontal ip) and that the left C-segment is oriented lo kwise (by a verti al ip). We have labelled the quantities relevant to analysis in Figure B.6. Note that π−δ is the length of the initial C-segment. So 0 ≤ π − δ ≤ π. Hen e, 0 ≤ δ ≤ π. Similarly, γ − π is length of the nal C-segment. So 0 ≤ γ − π ≤ π. Hen e, π ≤ γ ≤ 2π. Now dβ dα = −‖d‖ ‖a‖ sin δ‖c‖ ‖d‖ sin γ = − 2 sin δ 2 sin γ whi h is non-positive for δ ∈ [0, π] and γ ∈ [π, 2π]. 84 βδ γ α 1 ∆ 1 2 Figure B.6: CL0C-link monotoni ity. B.2 Non-Crossing Links In this se tion, we argue that links with the same ne stru ture do not ross. Lemma B.2. Let J be the set of links from orner F to orner G with ne stru ture Γ. Then no two links of J ross. Proof. We an refer to ea h link of J by its sour e onguration: re all that any jump is uniquely determined by its sour e onguration θ, destination onguration φ, and ne stru ture Γ; by Lemma B.1, there is exa tly one φ given θ. Ea h sour e onguration an be represented by a number in (−π, π] indi ating how its orientation diers from the dire tion from F to G. By referen e to ea h link of J by its sour e onguration, we an treat J as a subset of (−π, π]. Our proof relies on one riti al observation: for ea h J ∈ J , there is a non-empty two-sided neighbourhood around J su h that no link in this neighbourhood rosses J . The details verifying that this is true depends on the ne stru ture Γ. We only onsider the ase when Γ = C−L0C+ be ause the other ases are similar. As illustrated by Figure B.7, we an derive a jump S− with stru ture C−LC+ from J by slightly rolling the sour e onguration of J in a ounter lo kwise dire tion. There is a J− ∈ J with the same sour e onguration as S− that we an derive by rolling the destination onguration of S− lo kwise until the L-segment of S− disappears. By Lemma A.2, neither J− nor J ross S−. By onstru tion, J− and J are on dierent sides of S− (see Lemma A.1). Hen e J− and J do not ross. Therefore, there is a non-empty neighbourhood on one side of J that does not ross J . A similar argument holds for jumps J+ on the other side of J . Let J0 be an arbitrary link of J . We now argue that no link of J rosses J0. Then let K be the subset of J that rosses with J0. If K = ∅, we are done. Otherwise, by reversing the order of J as ne essary, we assume without loss of generality that there exists some jump K ∈ K su h that J0 < K. Let J2 be the greatest lower bound of {K ∈ K : J0 < K}. We now argue that J0 does not ross J2. This is trivially true if J0 = J2. So suppose J0 6= J2. Consider a jump J1 in the neighbourhood of J2 su h that J0 < J1 < J2 and J1 does not ross J2. Noti e that J1 does not ross J0 by denition of J2. Thus, J0 does not ross J2 be ause J0 and J2 lie on dierent sides of J1. 85 FG J+ J S+ J− R S− Figure B.7: Links J− and J+ that are lose to J do not ross J . Let N be a non-empty two-sided neighbourhood of J2 su h that any jump of N does not ross J2. Let J3 ∈ N be su h that J2 < J3 . Then J1 does not ross J3 be ause J1 and J3 are on dierent sides of J2. Therefore, the existen e of N ontradi ts that J2 is a greatest lower bound. B.3 Number of Homotopy Classes We now argue that there are only a bounded number of homotopy lasses of links. Lemma B.3. Let J be the set of links from orner F to orner G with ne stru ture Γ. Then there are O(n) homotopy lasses of J . Proof. By Lemma B.2, no two links of J ross. This implies a natural order < on J , where Ju < Jv < Jw implies that Ju and Jw are on dierent sides of Jv (see Lemma A.1). Hen e the homotopy lasses of J have a natural order: suppose that Ju < Jv < Jw, Ju and Jv are homotopi , and Jv and Jw are homotopi ; then Ju and Jw are homotopi be ause Ju and Jw lie on dierent sides of Jv. This ordering of homotopy lasses implies that are O(n) homotopy lasses be ause ea h feature separates at most two onse utive homotopy lasses. 86 Appendix C Convergen e to a Fixed-Point In this hapter, we prove Theorem 5.5. Let ∆ represent the distan e between orners F and G. We split our analysis a ording to whether ∆ < 2 or ∆ ≥ 2. The te hniques that we use in ea h ase are similar, but we make dierent ompromises when balan ing inequalities. In Theorem 5.5, we get quadrati onvergen e after O(m) iterations when ∆ 6= 2. The input pre ision m is part of the statement of the result be ause we use m to push ∆ away from zero and two. Lemma C.1. If ∆ 6= z, then |∆− z| ≥ 2−O(m), for integers z with magnitude at most 2m. Proof. Follows immediately from Corollary 5.7 be ause ea h orner oordinate is given as the ratio of two integers, ea h with magnitude at most 2m. C.1 Forward Iteration (∆ < 2) dj cj cj+1 L T d∞ dj+1 H I Figure C.1: Forward iteration approximation. We now prove the rapid onvergen e of 〈di〉 to d∞. Figure C.1 illustrates how we onstru t dj+1 from dj. Let H be the unit-radius ir le entred at F . Let T be the line tangent to H at dj. Let L be the lo us of points that are equidistant to F and G. The point dj+1 is the horizontal proje tion onto H of the interse tion of T and L. 87 Let the fun tion f (y) map the y- oordinate y of dj to the y- oordinate of dj+1. Then f is a single Newton-Raphson iteration onverging to the y- oordinate of d∞. We now derive an expression for f(y): the slope of the line through the origin and dj is y (1− y2)−1/2; hen e, the slope of T is − (1− y2)1/2 y−1 be ause T is perpendi ular to that line; the oordinates of the the interse tion of L and T are (∆/2, f (y)), so − ( 1− y2 )1/2 y−1 = (f (y)− y) ( ∆ 2 − [ 1− y2 ]1/2)−1 y (f (y)− y) = ( 1− y2 )1/2 ([ 1− y2 ]1/2 − ∆ 2 ) f (y) y − y2 = [ 1− y2 ] − ∆ 2 [ 1− y2 ]1/2 f (y) y = 1 2 ( 2−∆ √ 1− y2 ) f (y) = 1 2 ( 2−∆ ( 1− y2 )1/2) y−1 (C.1) Lemma C.2. The rea h of d−1 and d1 overlap. Proof. Let y±1 be the y- oordinate of d±1. Then overlap happens if f (y−1) ≥ y1. This is equivalent to y21 ≤ f (y−1)2 be ause both f (y−1) , y1 ≤ 0. Now y−1 = − ( 1− (∆/5)2 )1/2 and y1 = − ( 1− (∆/3)2 )1/2 (see Figures 5.7(b) and 5.8(a)). So f (y−1) 2 = 1 4 ( 2−∆ ( 1− y2−1 )1/2)2 y−2−1 = 1 4 ( 2−∆ ( 1− [ 1− (∆/5)2 ])1/2)2 [ 1− (∆/5)2 ]−1 = 1 4 (2−∆(∆/5))2 [ 1− (∆/5)2 ]−1 = (2−∆(∆/5))2 [ 4− 4 (∆/5)2 ]−1 = ( 4− 4∆ (∆/5) + ∆2 (∆/5)2 ) [ 4− (2∆/5)2 ]−1 = ( 100− 20∆2 +∆4 ) [ 100− 2∆2 ]−1 Re all that we want f (y−1) 2 ≤ y21( 100− 20∆2 +∆4 ) [ 100− 2∆2 ]−1 ≤ [1− (∆/3)2] 100− 20∆2 +∆4 ≤ [ 1− (∆/3)2 ] [ 100− 2∆2 ] 88 9 ( 100− 20∆2 +∆4 ) ≤ [ 9−∆2 ] [ 100− 2∆2 ] 900− 180∆2 + 9∆4 ≤ 900− 18∆2 − 100∆2 + 2∆4 −180∆2 + 9∆4 ≤ −118∆2 + 2∆4 7∆4 − 62∆2 ≤ 0 ∆2 ( 7∆2 − 62 ) ≤ 0 7∆2 ≤ 62 whi h is true be ause ∆ < 2. In the rest of this subse tion, we prove the following theorem. Theorem C.3. The error measure ξ+ (j) = y∞−yj de reases very rapidly. In parti ular 1. If ∆ ∈ (0, 2], then ξ+ (j) ≤ 2−Ω(j), for j > 1. 2. If ∆ ∈ (0, 2), then ξ+ (j) ≤ 2−2Ω(j) , for j > O(m). Proof. By Taylor's Theorem, f(y) = f (y∞) + f ′ (u) (y − y∞), for some u ∈ [y, y∞]. Using this expansion, the error term ξ+ (j + 1) = y∞ − f (yj) be omes y∞ − f (y∞) − f ′ (u) (yj − y∞) = −f ′ (u) (yj − y∞) = f ′ (u) · ξ+ (j). Corollary C.5 bounds f ′ (u) ∈[ 0, 3 5 ] , for ∆ ∈ (0, 2]. Hen e, ξ+ (j + 1) ≤ 35ξ+ (j). Now ξ+ (j) ≤ 1, so ξ+ (j) ≤( 3 5 )j−1 = [( 3 5 )2](j−1)/2 = [ 9 25 ](j−1)/2 ≤ (1 2 )(j−1)/2 = 2−(j−1)/2 = 2−Ω(j), for j ≥ 1. Again, by Taylor's Theorem f(y) = f (y∞) + f ′ (y∞) (y − y∞) + 12f ′′ (v) (y − y∞)2, for some v ∈[y, y∞]. In our analysis of f ′, we show that f ′ (y∞) = 0, for ∆ ∈ (0, 2) (see Equation C.6). So the error term ξ+ (j + 1) = y∞ − f (yj) be omes y∞ − f (y∞)− f ′ (y∞) (yj − y∞) − 12f ′′ (v) (yj − y∞)2 = −12f ′′ (v) (y − y∞)2 = −12f ′′ (v) ξ+ (j)2. Un- fortunately, f ′′ (v) may be poorly behaved. In parti ular, it may de rease without bound at an extreme of (y1, y∞) as ∆ tends to zero or two. Fortunately, we are able to use the input pre ision measure m to push ∆ away zero and two (see Lemma C.6). This enables the weak bound of f ′′ (v) ∈ [ −2O(m), 0 ] (see Corollary C.7). Hen e, ξ+ (j + 1) ≤ 2O(m)ξ+ (j)2. Earlier we showed that ξ (j) ≤ 2−Ω(j), for j ≥ 1. We use this rapid onvergen e to take us into the domain where the bound ξ+ (j + 1) ≤ 2O(m)ξ+ (j)2 be omes dominant. Consider j0 and d > 0 su h that j ≥ j0 implies that ξ+ (j) ≤ 2−dj . Similarly, onsider m0 and c > 0 su h that m ≥ m0 implies that ξ+ (j + 1) ≤ 2cmξ+ (j)2. Let h = max {⌈ cm+1 d ⌉ , j0 } = O (m). We now argue indu tively that ξ+ (h+ i) ≤ 2−(cm+2i). The base ase is i = 0. Then ξ+ (h) ≤ 2−dh ≤ 2−d⌈ cm+1 d ⌉ ≤ 2−(cm+1). So suppose that ξ+ (h+ i) ≤ 2−(cm+2i). Then ξ+ (h+ (i+ 1)) ≤ 2cmξ+ (h+ i)2 ≤ 2cm [ 2−(cm+2 i) ]2 = 2cm [ 2−(2cm+2 i+1) ] = 2−(cm+2 i+1) . 89 It is now straightforward to prove that ξ+ (j) ≤ 2−2Ω(j) , for j > O(m). Consider any j > 2h = O (m). Let i = j − h = j 2 + ( j 2 − h ) ≥ h. Then ξ+ (j) = ξ+ (h + i) ≤ 2−(cm+2 i) ≤ 2−2i ≤ 2−2j/2 = 2−2Ω(j) . We now prove the laims used in the above theorem. Re all that the rst and se ond derivatives of f were ru ial to our analysis by Taylor expansion. f ′ (y) = d dy [ 1 2 ( 2−∆ ( 1− y2 )1/2) y−1 ] by EquationC.1 = 1 2 [ y−1 d dy ( 2−∆ ( 1− y2 )1/2) + ( 2−∆ ( 1− y2 )1/2) d dy y−1 ] = 1 2 [ −∆y−1 d dy ( 1− y2 )1/2 − (2−∆ (1− y2)1/2) y−2 ] = 1 2 [ −∆ 2 y−1 ( 1− y2 )−1/2 d dy ( 1− y2 ) − ( 2−∆ ( 1− y2 )1/2) y−2 ] = 1 2 [ ∆ ( 1− y2 )−1/2 − (2−∆ (1− y2)1/2) y−2] = 1 2 [ ∆y2 ( 1− y2 )−1/2 − (2−∆ (1− y2)1/2)] y−2 = 1 2 [ ∆y2 ( 1− y2 )−1/2 +∆ ( 1− y2 )1/2 − 2] y−2 = 1 2 [ ∆y2 +∆ ( 1− y2 ) − 2 ( 1− y2 )1/2] y−2 ( 1− y2 )−1/2 = 1 2 [ ∆− 2 ( 1− y2 )1/2] y−2 ( 1− y2 )−1/2 (C.2) and f ′′ (y) = d dy ( 1 2 [ ∆− 2 ( 1− y2 )1/2] y−2 ( 1− y2 )−1/2) = 1 2 y−2 (1− y2)−1/2 d dy ( ∆− 2 (1− y2)1/2 ) +( ∆− 2 (1− y2)1/2 ) (1− y2)−1/2 d dy y−2+( ∆− 2 (1− y2)1/2 ) y−2 d dy (1− y2)−1/2 = 1 2 −y−2 (1− y2)−1/2 (1− y2)−1/2 d dy (1− y2)+ −2 ( ∆− 2 (1− y2)1/2 ) (1− y2)−1/2 y−3+ −1 2 ( ∆− 2 (1− y2)1/2 ) y−2 (1− y2)−3/2 d dy (1− y2) = 1 2 2y−1 (1− y2)−1 − 2 ( ∆− 2 (1− y2)1/2 ) (1− y2)−1/2 y−3+( ∆− 2 (1− y2)1/2 ) y−1 (1− y2)−3/2 90 = 1 2 2y2 (1− y2)1/2 − 2 ( ∆− 2 (1− y2)1/2 ) (1− y2) + ( ∆− 2 (1− y2)1/2 ) y2 y−3 (1− y2)−3/2 = 1 2 2y2 (1− y2)1/2 − 2∆ (1− y2) + 4 (1− y2)3/2 +∆y2 − 2y2 (1− y2)1/2 y−3 (1− y2)−3/2 = 1 2 [ −2∆ + 2∆y2 + 4 ( 1− y2 )3/2 +∆y2 ] y−3 ( 1− y2 )−3/2 = 1 2 y−3 ( 1− y2 )−3/2 · g (y) where g (y) = 3∆y2 + 4 (1− y2)3/2 − 2∆ (C.3) The xed-point y∞ is essential be ause iteration restri ts f ′ and f ′′ to the domain (y1, y∞). y∞ = f (y∞) = 1 2 · ( 2−∆ √ 1− y2∞ ) y−1∞ y2∞ = 1− ∆ 2 √ 1− y2∞ 1− y2∞ = ∆ 2 √ 1− y2∞√ 1− y2∞ = ∆ 2 , assuming y∞ 6= −1, (i.e. ∆ 6= 0) 1− y2∞ = ∆2 4 y∞ = − √ 1− ∆ 2 4 (C.4) The restri tion of the domain to (y1, y∞) produ es a loose bound on f ′′ (y). Lemma C.4. The fun tion f ′′ (y) is negative and the fun tion g (y) is in (0,∆), for y ∈ (−1, y∞) and ∆ ∈ (0, 2]. Proof. We rst prove that g (y) ∈ (0,∆) by showing that g (y) is monotoni ally de reas- ing. Consider the derivative g′ (y) = 6∆y − 12y (1− y2)1/2 = 6y [ ∆− 2 (1− y2)1/2 ] . Now y < y∞ = − √ 1− ∆ 2 4 by EquationC.4 y2 > 1− ∆ 2 4 ∆2 4 > 1− y2 ∆ > 2 ( 1− y2 )1/2 91 So g′ (y) is negative, for y ∈ (−1, y∞). It follows by the Mean Value Theorem that g (y) ∈ (g (y∞) , g (−1)), for y ∈ (−1, y∞). Now g (y∞) = 3∆y 2 ∞ + 4 ( 1− y2∞ )3/2 − 2∆ = 3∆ ( 1− ∆ 2 4 ) + 4 ( 1− ( 1− ∆ 2 4 ))3/2 − 2∆ = 3∆− 3 4 ∆3 + 4 ( ∆2 4 )3/2 − 2∆ = 3∆− 3 4 ∆3 + 1 2 ∆3 − 2∆ = ∆− 1 4 ∆3 = 1 4 ∆ ( 4−∆2 ) = 1 4 ∆ (2 + ∆) (2−∆) ≥ 0, for ∆ ∈ (0, 2] g (−1) = 3∆ (−1)2 + 4 ( 1− [−1]2 )3/2 − 2∆ = 3∆− 2∆ = ∆ Hen e g (y) ∈ (0,∆), for y ∈ (−1, y∞). Clearly, the fa tor 12y−3 (1− y2) −3/2 of f ′′ (y) is negative for y ∈ (−1, 0) ⊃ (−1, y∞). Therefore, f ′′ (y) is negative, for y ∈ (−1, y∞). This loose bound on f ′′ is su ient for a tight bound on f ′. Corollary C.5. The fun tion f ′ (y) is in [ 0, 3 5 ] , for y ∈ [y1, y∞] and ∆ ∈ (0, 2]. Proof. We rst argue that f ′ (y) is ontinuous for y ∈ [−1, y∞]. By inspe tion of Equation C.2, the potential dis ontinuities of f ′(y) o ur when y is −1 or 0. When y is −1, y1 must be −1, whi h implies that ∆ is 0. So we an ignore this ase. When y is 0, y∞ must be 0, whi h in turn implies that ∆ is 2. Let us evaluate f ′ (y) in this spe ial ase. lim y→0 f ′ (y) = lim y→0 1 2 · 2− 2 (1− y 2) 1/2 y2 (1− y2)1/2 = 1 2 · 0 0 , whi h is undened So we apply L'Hospital's Rule lim y→0 f ′(y) = lim y→0 1 2 · 2 (1− y 2) −1/2 y 2y (1− y2)1/2 − y3 (1− y2)−1/2 = lim y→0 1 2 · 2 2 (1− y2)− y2 = 1 2 · 2 2 = 1 2 Hen e f ′ (y) is ontinuous on y ∈ [y1, y∞]. Therefore, f ′ (y) ∈ [f ′ (y∞) , f ′ (y1)], for y ∈ [y1, y∞] by the Mean Value Theorem and Lemma C.4. f ′ (y1) = 1 2 [ ∆− 2 ( 1− y21 )1/2] y−21 ( 1− y21 )−1/2 by EquationC.2 92 = 1 2 [ ∆− 2 ( 1− ( 1−∆2/9 ))1/2] ( 1−∆2/9 )−1 ( 1− ( 1−∆2/9 ))−1/2 by Figure 5.7(b) = 1 2 [ ∆− 2 ( ∆2/9 )1/2] ( 1−∆2/9 )−1 ( ∆2/9 )−1/2 = 1 2 [∆− 2∆/3] ( 1−∆2/9 )−1 (∆/3)−1 = 1 2 · ( 1−∆2/9 )−1 ≤ 1 3 (1− 4/9)−1 = 1 3 ( 5 9 )−1 = 3 5 (C.5) f ′ (y∞) = 1 2 [ ∆− 2 ( 1− y2∞ )1/2] y−2∞ ( 1− y2∞ )−1/2 by EquationC.2 = 1 2 ∆− 2 ( 1− [ 1− ∆ 2 4 ])1/2 ( 1− ∆ 2 4 )−1 ( 1− ( 1− ∆ 2 4 ))−1/2 by EquationC.4 = 1 2 ∆− 2 ( ∆2 4 )1/2 ( 1− ∆ 2 4 )−1 ( ∆2 4 )−1/2 = 1 2 (∆−∆) ( 1− ∆ 2 4 )−1 ( ∆ 2 )−1 = 0, for ∆ ∈ (0, 2) (C.6) We get a tighter bound on f ′′ (y) by pushing y from away from −1 and 0, where f ′′(y) ould degenerate. Lemma C.6. If ∆ ∈ (0, 2), then [y1, y∞] ⊆ [ 2−O(m) − 1,−2−O(m) ] . Proof. By Lemma C.1,∆ ∈ [ 2−O(m), 2− 2−O(m) ] . Hen e, [y1, y∞] ⊆ [ 2−O(m) − 1,−2−O(m) ] . y1 = − √ 1−∆2/9 ≥ − √ 1−∆2/9 + (∆2/9)2 = − √ (1−∆2/9)2 = ∆2/9− 1 ≥ 2−O(m) − 1 To show that y∞ ≤ −2−O(m), we note that y∞ = − √ 1−∆2/4 is monotoni ally in reas- ing with values of ∆ in the range (0, 2). y∞ = −1 2 √ 4−∆2 = −1 2 √ 4− (2− 2−O(m))2 = −1 2 √ 4− (4− 4β + β2) = −1 2 √ 4β − β2 = −1 2 √ 2 · 2−O(m) − 2−2O(m) ≤ −1 2 93 Consider the hange of variables β = 2−∆. Then β ≥ 2−O(m) and y∞ is monoton- i ally de reasing with β. Now y∞ = −1 2 √ 4−∆2 = −1 2 √ 4− (2− β)2 = −1 2 √ 4− (4− 4β + β2) = −1 2 √ 4β − β2 If β ≥ 1, then y∞ = −12 √ β (4− β) ≤ −1 2 √ 4− β ≤ −1 2 √ 4− 2 = − √ 2 2 ≤ −2−O(1) = −2−O(m). If β ≤ 1, then β2 ≤ β and y∞ = −1 2 √ 4β − β2 ≤ −1 2 √ 4β − β = − √ 3 2 √ β = − √ 3 2 ( 2−O(m) )1/2 = −2−O(m) We an bound f ′′ using these bounds away from degenera y. Corollary C.7. If ∆ ∈ (0, 2), then f ′′ (y) ∈ [ −2O(m), 0 ] , for y ∈ [y1, y∞]. We bound the fa tor 1 2 y−3 (1− y2)−3/2of f ′′ (y) be ause y ∈ [ 2−O(m) − 1,−2−O(m) ] ⊇ [y1, y∞]. Either y ≤ −1/ √ 2 or y ≥ −1/√2. Suppose the former. Then y ∈ [ 2−O(m) − 1,− 1√ 2 ] . Both y−3and (1− y2)−3/2 are monotoni in this domain, so we an bound them by evaluating them at the interval endpoints. Hen e y−3 ∈ [( −√2 )3 , (−1)3 ] = [ −2√2,−1 ] . To evaluate (1− y2)−3/2 at 2−O(m)−1, suppose that y = 2−h(m)−1, where h(m) = O (m). Re all that y ≤ 0, whi h implies that h (m) > 0. Then ( 1− y2 )−3/2 = ( 1− ( 2−h(m) − 1 )2)−3/2 = ( 1− ( 2−2h(m) − 2 · 2−h(m) + 1 ))−3/2 = ( 2 · 2−h(m) − 2−2h(m) )−3/2 ≤ ( 2 · 2−h(m) − 2−h(m) )−3/2 by monotono ity of z−3/2 on z ∈ (0,∞) = ( 2−h(m) )−3/2 = 2( 3 2 h(m)) So y = 2−O(m) − 1 implies that (1− y2)−3/2 = 2O(m). At the other interval endpoint. ( 1− y2 )−3/2 = 1− ( − 1√ 2 )2 −3/2 = ( 1− 1 2 )−3/2 = (2)3/2 = 2 √ 2 Therefore, 1 2 y−3 (1− y2)−3/2 ∈ [ 1 2 · ( −2√2 ) · 2O(m), 1 2 · (−1) · 2√2 ] ⊆ [ −2O(m),−√2 ] . 94 So suppose that y ≥ −1/√2. Then y ∈ [ − 1√ 2 ,−2−O(m) ] . Again, both y−3 and (1− y2)−3/2 are monotoni in this domain, so we an bound both by evaluating them at the interval endpoints. To evaluate y−3 at y = −2−O(m), let y = −2−h(m) , where h (m) = O (m). We require y ≥ −1, so h (m) ≥ 0. Then y−3 = ( −2−h(m) )−3 = − ( 2−h(m) )−3 = −23h(m) So y = −2−O(m) implies y−3 = −2O(m). Hen e y−3 ∈ [ −2O(m),−2√2 ] . If y = 0 then (1− y2)−3/2 = 1. So (1− y2)−3/2 ∈ [ 1, 2 √ 2 ] . Therefore 1 2 y−3 ( 1− y2 )−3/2 ∈ [1 2 · ( −2O(m) ) · 2 √ 2, 1 2 · ( −2 √ 2 ) · 1 ] ⊆ [ −2O(m),− √ 2 ] Combined with our bound on g (y) ∈ (0,∆), we know that f ′′ (y) ∈ [ −2O(m), 0 ] . C.2 Forward Iteration (∆ > 2) dj cj cj+1 L T d∞ dj+1 H I (a) Constru tion for ∆ = 2. dj cj cj+1 L T dj+1 H d∞ I (b) Constru tion for ∆ > 2. Figure C.2: The position of L for ∆ > 2 is the same as its position for ∆ = 2. When the distan e between orners is greater than two, we simplify our analysis by using the onstru tion of the previous se tion when the distan e is exa tly two (see Figures C.2(a)). This underestimate is valid be ause cj+1 is on the appropriate side of T (see Figure C.2(b)). The quadrati onvergen e of the previous se tion expli itly required the distan e between orner to be stri tly less than two (see Theorem C.3). Fortunately, quadrati onvergen e to d∞ is unne essary be ause iterating to a window around d∞ overs the desired range. Re all that we are trying to over the range of orientations in quadrant A (see Figure 5.6(a)). The underestimates from ba kward iteration (i.e. d−1, d−2, . . .) over the horizontal orientation of quadrant A up to the orientations of d1. With forward iteration 95 df 1 α− 1 l h d∞ Figure C.3: Underlying ir les with entres between df and d∞ rea h the end of the range. (i.e. d1, d2, . . .), ea h underestimate of dj+1 overs a ontiguous range overlapping the previous underestimate of dj. So we have overed quadrant A on e a bin overs the verti al orientation of quadrant A. Ea h bin orresponding to a dj on the dashed ar between df and d∞ in Figure C.3 has this property. We now argue that this ar is large. Lemma C.8. If ∆ > 2, then h = y∞ − yf ≥ 2−O(m). From Figure C.3, we see that l = √ (∆− 1)2 − 1 = √∆2 − 2∆. By ommon angles, the triangle with side lengths h and 1 is ongruent to the triangle with side lengths l and ∆− 1. So h = h 1 = l ∆− 1 = √ ∆2 − 2∆ ∆− 1 = ( ∆2 − 2∆ )1/2 (∆− 1)−1 We prove that h is monotoni ally in reasing with respe t to ∆ by examining the derivative. h′ (∆) = (∆− 1)−1 d d∆ ( ∆2 − 2∆ )1/2 + ( ∆2 − 2∆ )1/2 d d∆ (∆− 1)−1 = (∆− 1)−1 · 1 2 ( ∆2 − 2∆ )−1/2 d d∆ ( ∆2 − 2∆ ) − ( ∆2 − 2∆ )1/2 (∆− 1)−2 d d∆ (∆− 1) = (∆− 1)−1 · 1 2 ( ∆2 − 2∆ )−1/2 (2∆− 2)− ( ∆2 − 2∆ )1/2 (∆− 1)−2 = ( ∆2 − 2∆ )−1/2 − (∆2 − 2∆)1/2 (∆− 1)−2 = ( ∆2 − 2∆ )−1/2 (∆− 1)2 (∆− 1)−2 − ( ∆2 − 2∆ )1/2 ( ∆2 − 2∆ )1/2 ( ∆2 − 2∆ )−1/2 (∆− 1)−2 = [ (∆− 1)2 − ( ∆2 − 2∆ )] ( ∆2 − 2∆ )−1/2 (∆− 1)−2 = [ ∆2 − 2∆ + 1− ( ∆2 − 2∆ )] ( ∆2 − 2∆ )−1/2 (∆− 1)−2 96 = ( ∆2 − 2∆ )−1/2 (∆− 1)−2 > 0, for ∆ > 2 by inspe tion By the Mean Value Theorem, h is minimised as ∆ tends to 2 be ause h is ontinuous, for ∆ ≥ 2. We an lower bound h by using the lower bound 2 + 2−O(m)on ∆ given by Lemma C.1. Suppose that ∆ = 2 + 2−g(m), where g (m) = O (m) ≥ 0. In this ase, h = ( ∆2 − 2∆ )1/2 (∆− 1)−1 = ([ 2 + 2−g(m) ]2 − 2 [2 + 2−g(m)])1/2 ([2 + 2−g(m)]− 1)−1 = ( 4 + 4 · 2−g(m) + 2−2g(m) − 4− 2 · 2−g(m) )1/2 ( 1 + 2−g(m) )−1 = ( 2 · 2−g(m) + 2−2g(m) ) ( 1 + 2−g(m) )−1 ≥ 2−g(m) ( 1 + 2−g(m) )−1 ≥ 2−g(m) (1 + 20)−1 = 2−g(m)2−1 = 2−[g(m)+1] So h ≥ 2−O(m). From Theorem C.3, ξ+ (j) = y∞ − yj ≤ 2−Ω(j), for j > 1. We just argued that we an stop iterating on e y∞ − yj < y∞ − yf ≤ 2−O(m). This is guaranteed when 2−Ω(j) < 2−O(m), whi h is equivalent to O (m) < Ω (j). So it is su ient for j = O (m), and only O (m) bins are required. C.3 Ba kward Iteration (∆ ≤ 2) dj cj L T H d−∞ cj−1dj−1 I Figure C.4: Underestimate of ba kward iteration. Although the onstru tions shown in either Figure 5.7(a) or C.1 dene mappings of dj to dj−1, we hoose an underestimate that is easier to analyse algebrai ally (see Figure C.4): We ree t dj through the line L of equidistan e to get cj, we draw a line T through d−∞ and the midpoint of cj and dj, and let dj−1 be a point of interse tion between H and T . If T were tangent to H , this would be the inverse of Figure C.1. 97 However, T interse ts H twi e, so it is a further underestimate. To see why we hose it, let y be the y- oordinate of dj and f (y) be the y- oordinate of dj−1. Then the slope of T an be expressed two ways. m = y + 1 ∆/2 = f (y) + 1√ 1− f (y)2 2 (y + 1) √ 1− f (y)2 = ∆(f (y) + 1) 4 (y + 1)2 ( 1− f (y)2 ) = ∆2 (f (y) + 1)2 4 (y + 1)2 (1− f (y)) (1 + f (y)) = ∆2 (f (y) + 1)2 4 (y + 1)2 (1− f (y)) = ∆2 (f (y) + 1) 4 (y + 1)2 − 4f (y) (y + 1)2 = ∆2f (y) + ∆2 4 (y + 1)2 −∆2 = ∆2f (y) + 4f (y) (y + 1)2 4 (y + 1)2 −∆2 = f (y) ( ∆2 + 4 (y + 1)2 ) f (y) = ( 4 (y + 1)2 −∆2 ) ( 4 (y + 1)2 +∆2 )−1 Theorem C.9. The error measure ξ− (j) = y−j − y−∞ de reases very rapidly. In parti ular 1. If ∆ ∈ (0, 2], then ξ− (j) ≤ 2−Ω(j), for j > 1. 2. If ∆ ∈ (0, 2], then ξ− (j) ≤ 2−2Ω(j) , for j > O(m). As before, our error analysis fo uses on the Taylor expansion of f (y) at the xed point y−∞. In parti ular, f (y) = f (y−∞) + f ′ (u) (y − y−∞), for some u ∈ [y−∞, y]. Hen e ξ− (j + 1) = f (y−j) − y−∞ = f ′ (u) (y−j − y−∞) = f ′ (u) ξ− (j). Corollary C.11 bounds f ′ (u) ∈ [ 0, 4 5 ] , for ∆ ∈ (0, 2]. Hen e, ξ+ (j + 1) ≤ 45ξ− (j). Now ξ− (j) ≤ 1, so ξ− (j) ≤ ( 4 5 )j−1 = [( 4 5 )4](j−1)/4 = [ 256 625 ](j−1)/4 ≤ (1 2 )(j−1)/4 = 2−(j−1)/4 = 2−Ω(j), for j ≥ 1. Again, by Taylor's Theorem f(y) = f (y−∞)+f ′ (y−∞) (y − y−∞)+12f ′′ (v) (y − y−∞)2, for some v ∈[y−∞, y]. In our analysis of f ′, we show that f ′ (y−∞) = 0, for ∆ ∈ (0, 2] (see Equation C.7). So the error term ξ− (j + 1) = f (y−j) − y−∞ be omes f (y−∞)+ f ′ (y−∞) (y−j − y−∞)+ 12f ′′ (v) (y−j − y−∞)2− y−∞ = 12f ′′ (v) (y−j − y−∞)2 = 1 2 f ′′ (v) ξ− (j) 2 . Unfortunately, f ′′ (v) may be poorly behaved. In parti ular, it may de rease without bound as v tends to y−∞ when ∆ tends to zero. Fortunately, we are able to use the input pre ision measure m to push ∆ away zero (see Lemma C.1). This enables the weak bound of f ′′ (v) ∈ [ 0, 2O(m) ] (see Lemma C.12). Hen e, ξ− (j + 1) ≤ 2O(m)ξ− (j) 2 . Earlier we showed that ξ− (j) ≤ 2−Ω(j), for j ≥ 1. We use this rapid onvergen e to take us into the domain where the bound ξ− (j + 1) ≤ 2O(m)ξ− (j)2 be omes dominant. 98 Consider j0 and d > 0 su h that j ≥ j0 implies that ξ− (j) ≤ 2−dj . Similarly, onsider m0 and c > 0 su h that m ≥ m0 implies that ξ− (j + 1) ≤ 2cmξ− (j)2. Let h = max {⌈ cm+1 d ⌉ , j0 } = O (m). We now argue indu tively that ξ− (h+ i) ≤ 2−(cm+2i). The base ase is i = 0. Then ξ− (h) ≤ 2−dh ≤ 2−d⌈ cm+1 d ⌉ ≤ 2−(cm+1). So suppose that ξ− (h+ i) ≤ 2−(cm+2i). Then ξ− (h+ (i+ 1)) ≤ 2cmξ− (h+ i)2 ≤ 2cm [ 2−(cm+2 i) ]2 = 2cm [ 2−(2cm+2 i+1) ] = 2−(cm+2 i+1) . It is now straightforward to prove that ξ− (j) ≤ 2−2Ω(j) , for j > O(m). Consider any j > 2h = O (m). Let i = j − h = j 2 + ( j 2 − h ) ≥ h. Then ξ− (j) = ξ− (h + i) ≤ 2−(cm+2 i) ≤ 2−2i ≤ 2−2j/2 = 2−2Ω(j) . The above proof used Taylor expansions of f (y) in terms of f ′ (y) and f ′′ (y) . f ′ (y) = d dy ( 4 (y + 1)2 −∆2 ) ( 4 (y + 1)2 +∆2 )−1 = ( 4 (y + 1)2 −∆2 ) d dy ( 4 (y + 1)2 +∆2 )−1 + ( 4 (y + 1)2 +∆2 )−1 d dy ( 4 (y + 1)2 −∆2 ) = ( 4 (y + 1)2 −∆2 ) · −1 · ( 4 (y + 1)2 +∆2 )−2 d dy ( 4 (y + 1)2 +∆2 ) + ( 4 (y + 1)2 +∆2 )−1 · 8 · (y + 1) = − ( 4 (y + 1)2 −∆2 ) ( 4 (y + 1)2 +∆2 )−2 · 8 · (y + 1) + ( 4 (y + 1)2 +∆2 )−1 · 8 · (y + 1) = 8 · (y + 1) [( 4 (y + 1)2 +∆2 )−1 − (4 (y + 1)2 −∆2) (4 (y + 1)2 +∆2)−2] = 8 (y + 1) ( 4 (y + 1)2 +∆2 )−2 [( 4 (y + 1)2 +∆2 ) − ( 4 (y + 1)2 −∆2 )] = 16∆2 (y + 1) ( 4 (y + 1)2 +∆2 )−2 f ′′ (y) = d dy [ 16∆2 (y + 1) ( 4 (y + 1)2 +∆2 )−2] = 16∆2 d dy [ (y + 1) ( 4 (y + 1)2 +∆2 )−2] = 16∆2 (y + 1) ddy ( 4 (y + 1)2 +∆2 )−2 + ( 4 (y + 1)2 +∆2 )−2 d dy (y + 1) 99 = 16∆2 (y + 1) · −2 · ( 4 (y + 1)2 +∆2 )−3 d dy ( 4 (y + 1)2 +∆2 ) + ( 4 (y + 1)2 +∆2 )−2 = 16∆2 [ −2 (y + 1) ( 4 (y + 1)2 +∆2 )−3 · 8 · (y + 1) + (4 (y + 1)2 +∆2)−2] = 16∆2 [ −16 (y + 1)2 ( 4 (y + 1)2 +∆2 )−3 + ( 4 (y + 1)2 +∆2 )−2] = 16∆2 ( 4 (y + 1)2 +∆2 )−3 [( 4 (y + 1)2 +∆2 ) − 16 (y + 1)2 ] = 16∆2 ( ∆2 − 12 (y + 1)2 ) ( 4 (y + 1)2 +∆2 )−3 In order to bound f ′ (y), we show that it is monotoni ally in reasing on its domain. Lemma C.10. The se ond derivative f ′′ (y) is positive, for y ∈ [y−∞, y−1] and ∆ ∈ (0, 2]. The sign of f ′′ (y) hanges at 12 (y + 1)2 = ∆2 y + 1 = ± ∆√ 12 y = ± ∆√ 12 − 1 Re all that y ∈ [y−∞, y−1]. We note that −1−∆/ √ 12 < y−∞ be ause ∆ > 0. We now show that y−1 = − √ 1− (∆/5)2 < ∆/ √ 12− 1√ 1− (∆/5)2 > 1−∆/ √ 12 1− (∆/5)2 > 1− 2∆/ √ 12 + ∆2/12 2∆/ √ 12 > ∆2/12 + ∆2/25 2/ √ 12 > ∆(1/12 + 1/25) 2/ √ 12 > ∆(37/300) ∆ < 600/ ( 37 √ 12 ) = 50 √ 12/37 Now 50 √ 12/37 ≥ 50√9/37 = 150/37 > 2. Therefore f ′′(y) > 0, for y ∈ [y−∞, y−1]. Corollary C.11. The rst derivative f ′ (y) is in [0, 4/5], for y ∈ [y−∞, y−1] and ∆ ∈ (0, 2]. By inspe tion, f ′ (y) is ontinuous on y ∈ [−1, 0] ⊇ [y−∞, y−1] be ause ∆ > 0. Hen e f ′ (y) ∈ [f ′ (y−∞) , f ′ (y−1)] by the Mean Value Theorem and Lemma C.10. Then 100 f ′ (y−∞) = 16∆ 2 ((−1) + 1) ( 4 (−1 + 1)2 +∆2 )−2 = 16∆2 · 0 ·∆−4 = 0, for ∆ ∈ (0, 2] (C.7) The interval end-point is harder to evaluate be ause f ′ (y−1) is a omposition of two fun tions, f ′ (y) and y−1, with a dependen e on ∆. We analyse this omposition using the Chain Rule df ′(y−1) d∆ = df ′(y−1) dy−1 · dy−1 d∆ . By Lemma C.10, the rst fa tor is positive, for ∆ ∈ (0, 2]. We now derive the se ond fa tor. y−1 (∆) = − (1− (∆/5))1/2 dy−1 d∆ = − d d∆ ( 1− (∆/5)2 )1/2 = −1 2 ( 1− (∆/5)2 )−1/2 · d d∆ ( 1− (∆/5)2 ) = −1 2 ( 1− (∆/5)2 )−1/2 · −2 (∆/5) = (∆/5) ( 1− (∆/5)2 )−1/2 = ∆ ( 5−∆2 )−1/2 > 0, for ∆ ∈ (0, 2] So, df ′(y−1) d∆ is positive for ∆ ∈ (0, 2]. The omposition of ontinuous fun tions is ontinuous, so f ′ (y−1 (∆)) is ontinuous on ∆ ∈ (0, 2] be ause f ′ (y) is ontinuous on y ∈ [−1, 0] and y−1 (∆) is ontinuous on ∆ ∈ (0, 2]. Therefore f ′ (y−1 (∆)) ∈ [f ′ (y−1 (0)) , f ′ (y−1 (2))] by the Mean Value Theorem. Now f ′ (y) is non-negative by inspe tion, so f ′ (y−1 (0)) ≥ 0. y−1 (2) = − ( 1− (2/5)2 )1/2 = − (1− 4/25)1/2 = − (21/25)1/2 ≤ −4/5 f ′ (y−1 (2)) = 16 · 22 · (y−1 (2) + 1) ( 4 (y−1 (2) + 1) 2 + 22 )−2 ≤ 16 · 4 · ( −4 5 + 1 ) ( 0 + 22 )−2 = 16 · 4 · 1 5 · 1 16 = 4 5 Thus f ′ (y−1 (∆)) ∈ [0, 4/5], for∆ ∈ (0, 2]. Therefore, f ′ (y) ∈ [0, 4/5] ⊇ [f ′ (y−∞) , f ′ (y−1)], for y ∈ [y−∞, y−1] and ∆ ∈ (0, 2]. To get a tighter bound on f ′′ (y), we use a bound pushing ∆ away from 0 (see Lemma C.1). Lemma C.12. The se ond derivative f ′′ (y) is in [ 0, 2O(m) ] , for y ∈ [y−1, y−∞] and ∆ ∈ (0, 2]. Lemma C.10 asserts that f ′′ (y) ≥ 0. Now we derive an upper bound. f ′′ (v) = 16∆2 ( ∆2 − 12 (v + 1)2 ) ( 4 (v + 1)2 +∆2 )−3 ≤ 16∆2 ( ∆2 − 0 ) ( 0 + ∆2 )−3 = 16∆2 ·∆2 ·∆−6 = 16∆−2 101 Therefore, f ′′ (y) ∈ [0, 16∆−2]. By Lemma C.1, ∆ > 2−O(m). Hen e f ′′ (y) ∈ [ 0, 2O(m) ] . C.4 Ba kward Iteration(∆ ≥ 2) dj cj cj+1 L T d−∞ dj+1 H I (a) Constru tion for ∆ = 2. dj cj cj+1 L T dj+1 H d−∞ I (b) Constru tion for ∆ > 2. Figure C.5: The position of L for ∆ > 2 is the same as its position for ∆ = 2. When the distan e between orners is greater than two, we simplify our analysis by using the onstru tion of the previous se tion when the distan e is exa tly two (see Figures C.5(a)). This underestimate is valid be ause cj+1 is on the appropriate side of T (see Figure C.5(b)). So we reuse the onvergen e analysis of the previous se tion (see Theorem C.9). 102
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Bounded-curvature motion planning amid polygonal obstacles
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Bounded-curvature motion planning amid polygonal obstacles Backer, Jonathan 2009
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Bounded-curvature motion planning amid polygonal obstacles |
Creator |
Backer, Jonathan |
Publisher | University of British Columbia |
Date Issued | 2009 |
Description | We consider the problem of finding a bounded-curvature path in the plane from one configuration αs to another configuration αt that avoids the interior of a set of polygonal obstacles Ε. We call any such path from αs to αt a feasible path. In this thesis, we develop algorithms to find feasible paths that have explicit guarantees on when they will return a feasible path. We phrase our guarantees and run time analysis in terms of the complexity of the desired solution (see k and λ below). In a sense, our algorithms are output sensitive, which is particularly desirable because there are no known bounds on the solution complexity amid arbitrary polygonal environments. Our first major result is an algorithm that given Ε, αs, αt, and a positive integer k either (i) verifies that every feasible path has a descriptive complexity greater than k or (ii) outputs a feasible path. The run time of this algorithm is bounded by a polynomial in n (the total number of obstacle vertices in Ε), m (the bit precision of the input), and k. This result complements earlier work by Fortune and Wilfong: their algorithm considers paths of arbitrary descriptive complexity (it has no dependence on k), but it never outputs a path, just whether or not a feasible path exists. Our second major result is an algorithm that given E, αs, αt, a length λ, and an approximation factor Ε, either (i) verifies that every feasible path has length greater than λ or (ii) constructs a feasible path that is at most (1+ Ε) times longer than the shortest feasible path. The run time of this algorithm is bounded by a polynomial in n, m, Ε-1, and λ. This algorithm is the result of applying the techniques developed earlier in our thesis to the previous approximation approaches. A shortcoming of these prior approximation algorithms is that they only search a special class of feasible paths. This restriction implies that the path that they return may be arbitrarily longer than the shortest path. Our algorithm returns a true approximation because we search for arbitrary shortest paths. |
Extent | 1025471 bytes |
Subject |
motion planning bounded-curvature curvature-constrained nonholonomic |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-02-26 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0051257 |
URI | http://hdl.handle.net/2429/5153 |
Degree |
Doctor of Philosophy - PhD |
Program |
Computer Science |
Affiliation |
Science, Faculty of Computer Science, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2009-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2009_spring_jonathan_backer.pdf [ 1001.44kB ]
- Metadata
- JSON: 24-1.0051257.json
- JSON-LD: 24-1.0051257-ld.json
- RDF/XML (Pretty): 24-1.0051257-rdf.xml
- RDF/JSON: 24-1.0051257-rdf.json
- Turtle: 24-1.0051257-turtle.txt
- N-Triples: 24-1.0051257-rdf-ntriples.txt
- Original Record: 24-1.0051257-source.json
- Full Text
- 24-1.0051257-fulltext.txt
- Citation
- 24-1.0051257.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0051257/manifest