Dubins path

<h2 id="discussion">Discussion</h2>
<p>Dubins proved his result in 1957. In 1974 Harold H. Johnson proved Dubins' result by applying <a href="/facts/Pontryagin%27s_maximum_principle/gEVJ1sjc">Pontryagin's maximum principle</a>.<a class="footnote-ref" id="fnref:4" href="#fn:4"><sup>4</sup></a> In particular, Harold H. Johnson presented necessary and sufficient conditions for a plane curve, which has bounded piecewise continuous curvature and prescribed initial and terminal points and directions, to have minimal length. In 1992 the same result was shown again using Pontryagin's maximum principle.<a class="footnote-ref" id="fnref:5" href="#fn:5"><sup>5</sup></a> More recently, a geometric curve-theoretic proof has been provided by J. Ayala, D. Kirszenblat and J. Hyam Rubinstein.<a class="footnote-ref" id="fnref:6" href="#fn:6"><sup>6</sup></a> A proof characterizing Dubins paths in homotopy classes has been given by J. Ayala.<a class="footnote-ref" id="fnref:7" href="#fn:7"><sup>7</sup></a>
</p>
<h2 id="applications">Applications</h2>
<p>The Dubins path is commonly used in the fields of <a href="/facts/Robotics/wkmvodJz">robotics</a> and <a href="/facts/Control_theory/aIuERpn6">control theory</a> as a way to plan paths for wheeled robots, airplanes and underwater vehicles. There are simple geometric<a class="footnote-ref" id="fnref:8" href="#fn:8"><sup>8</sup></a> and analytical methods<a class="footnote-ref" id="fnref:9" href="#fn:9"><sup>9</sup></a> to compute the optimal path.
</p><p>For example, in the case of a wheeled robot, a simple kinematic car model (also known as Dubins' car) for the systems is:

x
                      ˙
                    
                  
                
              
              
                
                =
                V
                cos
                ⁡
                (
                θ
                )
              
            
            
              
                
                  
                    
                      y
                      ˙
                    
                  
                
              
              
                
                =
                V
                sin
                ⁡
                (
                θ
                )
              
            
            
              
                
                  
                    
                      θ
                      ˙
                    
                  
                
              
              
                
                =
                u
              
            
          
        
      
    
    {\displaystyle {\begin{aligned}{\dot {x}}&=V\cos(\theta )\\{\dot {y}}&=V\sin(\theta )\\{\dot {\theta }}&=u\end{aligned}}}

where 
  
    
      
        (
        x
        ,
        y
        )
      
    
    {\displaystyle (x,y)}
  
 is the car's position, 
  
    
      
        θ
      
    
    {\displaystyle \theta }
  
 is the heading, the car is moving at a constant speed 
  
    
      
        V
      
    
    {\displaystyle V}
  
, and the turn rate control 
  
    
      
        u
      
    
    {\displaystyle u}
  
 is bounded. In this case the maximum turning rate corresponds to some minimum <a href="/facts/Turning_radius/XuJYKKa2">turning radius</a> (and equivalently maximum curvature). The prescribed initial and terminal tangents correspond to initial and terminal <a href="/facts/Direction_(geometry)/Tj24mTJ8">headings</a>. The Dubins' path gives the shortest path joining two oriented points that is feasible for the wheeled-robot model.
</p><p>
The optimal path type can be described using an analogy with cars of making a 'right turn (R)', 'left turn (L)' or driving 'straight (S).' An optimal path will always be at least one of the six types: RSR, RSL, LSR, LSL, RLR, LRL. For example, consider that for some given initial and final positions and tangents, the optimal path is shown to be of the type 'RSR.' Then this corresponds to a right-turn arc (R) followed by a straight line segment (S) followed by another right-turn arc (R). Moving along each segment in this sequence for the appropriate length will form the shortest curve that joins a starting point A to a terminal point B with the desired tangents at each endpoint and that does not exceed the given curvature. </p>
<h2 id="dubins-interval-problem">Dubins interval problem</h2>
<p>Dubins interval problem is a key variant of the Dubins path problem, where an interval of heading directions are specified at the initial and terminal points. The tangent direction of the path at initial and final points are constrained to lie within the specified intervals. One could solve this using geometrical analysis,<a class="footnote-ref" id="fnref:10" href="#fn:10"><sup>10</sup></a> or using Pontryagin's minimum principle.<a class="footnote-ref" id="fnref:11" href="#fn:11"><sup>11</sup></a>
</p>

<h2 id="external-links">External links</h2>
<ul><li><a href="http://planning.cs.uiuc.edu/node821.html">Dubins Curves</a> <a href="https://web.archive.org/web/20160322015719/http://planning.cs.uiuc.edu/node821.html">Archived</a> 2016-03-22 at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a>, from Planning Algorithms by  Steven M. LaValle</li>
<li><a href="https://demonstrations.wolfram.com/IsochronsForADubinsCar/">Isochrons for a Dubins Car</a>, a demonstration from <a href="/facts/Wolfram_Demonstrations_Project/l0sh4gln">Wolfram Demonstrations Project</a></li>
<li><a href="https://github.com/builtrobotics/rsplan/">An open-source Python Reeds-Shepp implementation</a>, authored by <a href="/facts/Built_Robotics/XUHWKtSc">Built Robotics</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Reeds, J. A.; Shepp, L. A. (1990). "Optimal paths for a car that goes both forwards and backwards". Pacific Journal of Mathematics. 145 (2): 367–393. doi:10.2140/pjm.1990.145.367. <a href="https://doi.org/10.2140%2Fpjm.1990.145.367" target="_blank">https://doi.org/10.2140%2Fpjm.1990.145.367</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
<li id="fn:2"><p>"IN MEMORIAM Lester Eli Dubins Professor of Mathematics and Statistics, Emeritus UC Berkeley 1920–2010". University of California. Archived from the original on 15 September 2011. Retrieved 26 May 2012. <a href="https://web.archive.org/web/20110915140737/http://universityofcalifornia.edu/senate/inmemoriam/lesterelidubins.html" target="_blank">https://web.archive.org/web/20110915140737/http://universityofcalifornia.edu/senate/inmemoriam/lesterelidubins.html</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></p></li>
<li id="fn:3"><p>Dubins, L. E. (July 1957). "On Curves of Minimal Length with a Constraint on Average Curvature, and with Prescribed Initial and Terminal Positions and Tangents". American Journal of Mathematics. 79 (3): 497–516. doi:10.2307/2372560. JSTOR 2372560. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></p></li>
<li id="fn:4"><p>Johnson, Harold H. (1974). "An application of the maximum principle to the geometry of plane curves". Proceedings of the American Mathematical Society. 44 (2): 432–435. doi:10.1090/S0002-9939-1974-0348631-6. MR 0348631. <a href="https://doi.org/10.1090%2FS0002-9939-1974-0348631-6" target="_blank">https://doi.org/10.1090%2FS0002-9939-1974-0348631-6</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></p></li>
<li id="fn:5"><p>Boissonat, J.-D.; Cerezo, A.; Leblond, K. (May 1992). "Shortest Paths of Bounded Curvature in the Plane" (PDF). Proceedings of the IEEE International Conference on Robotics and Automation. Vol. 3. Piscataway, NJ. pp. 2315–2320. doi:10.1109/ROBOT.1992.220117. <a href="/wiki/Jean-Daniel_Boissonnat" target="_blank">/wiki/Jean-Daniel_Boissonnat</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></p></li>
<li id="fn:6"><p>Ayala, José; Kirszenblat, David; Rubinstein, Hyam (2018). "A Geometric approach to shortest bounded curvature paths". Communications in Analysis and Geometry. 26 (4): 679–697. arXiv:1403.4899. doi:10.4310/CAG.2018.v26.n4.a1. <a href="https://doi.org/10.4310%2FCAG.2018.v26.n4.a1" target="_blank">https://doi.org/10.4310%2FCAG.2018.v26.n4.a1</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></p></li>
<li id="fn:7"><p>Ayala, José (2015). "Length minimising bounded curvature paths in homotopy classes". Topology and Its Applications. 193: 140–151. arXiv:1403.4930. doi:10.1016/j.topol.2015.06.008. <a href="https://doi.org/10.1016%2Fj.topol.2015.06.008" target="_blank">https://doi.org/10.1016%2Fj.topol.2015.06.008</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></p></li>
<li id="fn:8"><p>Anisi, David (July 2003). Optimal Motion Control of a Ground Vehicle (PDF) (Report). Swedish Research Defence Agency. 1650-1942. <a href="https://people.kth.se/~anisi/articles/foi-r-0961-se.pdf" target="_blank">https://people.kth.se/~anisi/articles/foi-r-0961-se.pdf</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></p></li>
<li id="fn:9"><p>Bui, Xuan-Nam; Boissonnat, J.-D.; Soueres, P.; Laumond, J.-P. (May 1994). "Shortest Path Synthesis for Dubins Non-Holonomic Robot". IEEE Conference on Robotics and Automation. Vol. 1. San Diego, CA. pp. 2–7. doi:10.1109/ROBOT.1994.351019. <a href="/wiki/Jean-Daniel_Boissonnat" target="_blank">/wiki/Jean-Daniel_Boissonnat</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></p></li>
<li id="fn:10"><p>Manyam, Satyanarayana; Rathinam, Sivakumar (2016). "On Tightly Bounding the Dubins Traveling Salesman's Optimum". Journal of Dynamic Systems, Measurement, and Control. 140 (7): 071013. arXiv:1506.08752. doi:10.1115/1.4039099. S2CID 16191780. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></p></li>
<li id="fn:11"><p>Manyam, Satyanarayana G.; Rathinam, Sivakumar; Casbeer, David; Garcia, Eloy (2017). "Tightly Bounding the Shortest Dubins Paths Through a Sequence of Points". Journal of Intelligent & Robotic Systems. 88 (2–4): 495–511. doi:10.1007/s10846-016-0459-4. S2CID 30943273. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></p></li>
</ol>

Dubins path open-in-new

Dubins path