ccpp

Continuous-Curvature Path Planning: 

Continuous-Curvature Path Planning Eric Griffith

Papers: 

Papers From Reeds and Shepp's to Continuous-Curvature Paths, Th. Fraichard and A. Scheuer. Accepted to IEEE Transactions on Robotics and Automation. Submitted in February 2002, revised in June 2003. From Reeds and Shepp's to continuous-curvature paths, Th. Fraichard and A. Scheuer and R. Desvigne, Proceedings of the International Conference on Advanced Robotics, pages 585--590, Oct 1999, Tokyo, Japan. Continuous-curvature path planning for car-like vehicles, A. Scheuer and Th. Fraichard, Proc. of the IEEE-RSJ Int. Conf. on Intelligent Robots and Systems, volume 2, pages 997--1003, Sep 1997, Grenoble, France.

What Is Curvature?: 

What Is Curvature? Curvature describes the behavior of a curve in a small neighborhood It can be thought of as how quickly a curve is deviating from its tangent line Circles have constant curvature Smaller circles have higher curvature Lines can be thought of as circles with infinite radius (and consequently zero curvature) Intuitively, it is the inverse of the radius of the circle that best approximates the curve at a point

Curvature: 

Curvature

Curvature for a General Curve: 

Curvature for a General Curve Consider a curve parameterized by time: The tangent for this curve is defined as: The curvature for this curve is defined as:

The Car Model: 

The Car Model The configuration of the car is specified by: The curvature at the initial and goal configurations must be zero

Car Model Details: 

Car Model Details Given these configuration variables, the car can be modeled as follows:

More Car Model Details: 

More Car Model Details The system is driven by two inputs: These inputs are subject to these constraints: And, due to mechanical limitations on steering:

Dubins Curves: 

Dubins Curves For robots that can only move forward Attempts to connect two points with the shortest path The shortest path will be one of 6 potential paths The paths consist of either circular arcs or line segments The paths are of the form CCC or CSC CSC is circular arc, line segment, circular arc CCC is circular arc, circular arc, circular arc The combinations are: CCC: RLR, LRL CSC: RSR, RSL, LSR, LSL

Dubins Curves: 

Dubins Curves

Reeds and Shepp Curves: 

Reeds and Shepp Curves Extend the notion of Dubins curves to robots that can move both forward and backward They introduce cusps in the path where the robot reverses direction This shortens the distance requried to turn around in The shortest path will be one of 48 potential paths These paths can be characterized similarly to the Dubins curves

Reeds and Shepp Curves: 

Reeds and Shepp Curves

Why Continuous Curvature?: 

Why Continuous Curvature? With both Dubins curves and Reeds and Shepp curves, there are line segments meeting circular arcs This corresponds to an instantaneous change in the steering angle The robot must stop at the end of a circular arc or line segment and adjust its steering angle before continuing Continuous-Curvature curves allow the robot to traverse the path without having to stop They also allows the robot to more accurately track the path

The Basic Idea: 

The Basic Idea Given two points, A and B, compute the shortest, collision-free path between them Once such a method has been developed, it can be incorporated into a larger path planning system This could be a local path planner incorporated into PRM

The Basic Approach: 

The Basic Approach The objective is to generate paths with continuous curvature that respect the constraints of the robot Nonholonomic constraints Minimum turning radius Start with either Dubins curves or Reeds and Shepp curves Dubins if the robot can only move forward Reeds and Shepp otherwise Introduce “curvature bridges” to join the different pieces of the curves together This is what makes the curvature continuous

Clothoid Arcs: 

Clothoid Arcs The “curvature bridges” chosen were clothoid arcs Clothoid arcs are pieces of clothoid, or Cornu, spirals These spirals have the special property that their curvature varies linearly with respect to arc length

Clothoid Arcs, cont’d: 

Clothoid Arcs, cont’d The parametric equation for a Clothoid Arc is:

Formulation of Curvature-Continuous Paths: 

Formulation of Curvature-Continuous Paths The key difference between Curvature-Continuous (CC) paths and Reeds and Shepp paths are the turns With Reeds and Shepp paths, there are two cases where the curvature is discontinuous: Two circular arcs meet A line segment and a circular arc meet CC paths must address the discontinuity at these join points

The CC Turn: 

The CC Turn The discontinuity between sections of the path is addressed in the construction of the turns Line segments always have zero curvature To join a CC turn to a line segment, the turn must have zero curvature where it meets the line segment The solution is to have CC turns begin and end with zero curvature This allows them to be connected to each other and to line segments This also allows turns to be connected to the initial and goal configurations

The CC Turn Details: 

The CC Turn Details The general CC turn is comprised of three parts: The turn begins and ends on a circle C with configurations qs and qg, respectively The deflection, or change in the car’s orientation, as it goes around C is δ = (θg – θs) mod 2π

The CC Turn: 

The CC Turn

The Clothoid Arc: 

The Clothoid Arc When entering a turn, the robot begins in (relative) configuration: The robot proceeds along the clothoid arc until it reaches qi:

The Circular Arc: 

The Circular Arc The radius for the circular arc is: The center of the circular arc is: The angle of the circular arc is:

The CC Circle: 

The CC Circle As mentioned before, a CC turn begins with a configuration qs on a circle and ends with a configuration qg on the same circle. This circle is referred to as the CC circle and any circular arc contained in a turn through the CC circle is concentric with the CC circle The radius of the CC circle is:

The CC Circle and μ: 

The CC Circle and μ There is a special relation between the start and end configurations of a CC turn on the CC circle and the tangents to the CC circle at those points In particular, the angle from the line containing qs, and making an angle θs with the x-axis, to the tangent to the CC circle at (xs, ys) is μ This same angle μ is formed between qg and the tangent to the CC circle at (xg, yg)

Turns of Small Deflection: 

Turns of Small Deflection Turns where δ < δmin warrant a special case Ordinarily, the path of the robot would involve a nearly complete circuit of the inner circle, which would result in the robot’s path intersecting itself as it left the turn Instead, omit the circular arc and directly connect the begin and end of the turn with two clothoid arcs with “sharpness” of σ and -σ, where:

Turns of Small Deflection: 

Turns of Small Deflection

Turns of Large Deflection: 

Turns of Large Deflection Turns where δ > δmin + π also warrant a special case Because the robot can travel both forward and backward, the path for turns of large deflection can be shortened by traveling backward For the circular arc, reverse direction through a circular arc of angle:

Turns of Large Deflection: 

Turns of Large Deflection

Arc Length Around a CC Turn: 

Arc Length Around a CC Turn The last important component required is the arc length around a CC turn This will enable the length of various paths to be compared The arc length for the three types of turns:

Putting the Pieces Together: 

Putting the Pieces Together Now that turns can be constructed which begin and end with zero curvature, CC paths can be assembled Two turns can be connected to each other provided that the θg of the first turn is equal to the θs of the turn it is being connected to A line segment can be connected to a circular arc provided that the θ along it matches the θs of the arc it is being connected to A circular arc can be connected to a line segment provided that its θg matches the θ along the line segment

Getting from Here to There: 

Getting from Here to There Given any configuration of the robot, that configuration is incident on 4 CC Circles One corresponds to a left turn going forward One corresponds to a left turn going backward One corresponds to a right turn going forward One corresponds to a right turn going backward

Getting from Here to There: 

Getting from Here to There

Getting from Here to There: 

Getting from Here to There Given an initial configuration and a goal configuration, the 4 CC Circles incident on each configuration can be computed Dubins style paths By changing the C in CCC and CSC from “circular arc” to CC turn, an equivalent to each of the 6 possible Dubins paths can be constructed Reeds and Shepp style paths Following a similar procedure, each of the 48 possible Reeds and Shepp paths can be constructed

CC vs. Reeds and Shepp: 

CC vs. Reeds and Shepp CC paths have continuous curvature Reeds and Shepp paths do not Reeds and Shepp CC paths (a to b is a clothoid arc)

CC vs. Reeds and Shepp: 

CC vs. Reeds and Shepp

Completing the Planner: 

Completing the Planner Collision Detection The area swept out by the robot on the circular arcs and the line segments can be exactly computed The area on the clothoid arcs must be approximated The area swept out by the robot should be collision free Emulating holonomic motion By performing series of elementary CC operations, namely combinations of clothoid arcs and line segments, sideways motion can be achieved

Sample Paths Produced: 

Sample Paths Produced

Considerations for Planner: 

Considerations for Planner Computing CC paths takes slightly longer than computing Reeds and Shepp paths The CC path is no longer the optimal nonholonomic path The CC path still has instantaneous changes in steering velocity CC paths are easier to track for robots, especially without having to stop CC paths respect the mechanical steering limitations of the robot