Ronald Choe
Venanzio Cichella, Dr. Enric Xargay, Dr. Naira Hovakimyan,
Anna C. Trujillo, Dr. Isaac Kaminer
{choe19,chichell2,xargay,nhovakim}@illinois.edu,
anna.c.trujillo@nasa.gov, kaminer@nps.edu
AIAA Infotech@Aerospace Conference
Boston, MA, 19th August 2013
                    University of Illinois at Urbana-Champaign
UIUC logo.png
1
A Trajectory-Generation Framework forTime-Critical Cooperative Missions
UIUC logo.png
University of Illinois
at Urbana-Champaign
Outline
2
Background
Problem Formulation
Trajectory-Generation Framework
Simulation Example
Summary
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
Background
3
Integration of sUAS in the NAS requirestrajectory planning to ensure safe operationin non-positively controlled airspace
C:\Users\xargay\Desktop\4images.png
Generating desired trajectories forguidance algorithms, cooperative path-following algorithms
High-density, all-weather, and self-separation operational concepts; expectedto allow mixed-capability aircraft to operate within the same airspace, includingpiloted aircraft and UAVs
High-density, all-weather, and self-separation operational concepts; expectedto allow mixed-capability aircraft to operate within the same airspace, includingpiloted aircraft and UAVs
NextGen CONOPS
NextGen CONOPS
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
Requirements / Challenges
4
Trajectory that can be followed by a (flying) vehicle, i.e. it satisfies the dynamicconstraints of the vehicle
Trajectory that can be followed by a (flying) vehicle, i.e. it satisfies the dynamicconstraints of the vehicle
Flyable Trajectory
Trajectory that is flyable and safe to fly, i.e. spatially deconflicted and free from(static) obstacles
Trajectory that is flyable and safe to fly, i.e. spatially deconflicted and free from(static) obstacles
Feasible Trajectory
A priori generation of  feasible trajectories that are clear from staticobstacles  and ensure spatial de-confliction with other vehicles
Computationally efficient:
1.Limited computing power onboard sUAS;
2.Potential need for re-planning on-the-fly in case of:
Loss-of-link between operator and sUAS  (return-to-base,alternate landing site);
Change of mission;
Unforeseen dynamic and static obstacles;
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
Objective
5
Background
Problem Form
Trajectory Gen
Sim Example
Summary
Introduce a heuristic approach to the planar trajectory generationproblem for multiple UAVs and explore the feasibility of using thisframework to generate feasible trajectories in (near) real-time
Introduce a heuristic approach to the planar trajectory generationproblem for multiple UAVs and explore the feasibility of using thisframework to generate feasible trajectories in (near) real-time
Combining tools and ideas from the literature to formulate aconstrained optimization problem, solved using standard Matlabroutines
Geometrical approach: exploiting geometric properties of curves
Illustrative example: generating trajectories for team ofcooperating UAVs executing time-critical mission
UIUC logo.png
University of Illinois
at Urbana-Champaign
Generate feasible planar trajectories
that minimize cost function    subject to
boundary conditions
dynamic constraints of the vehicles
mission-specific constraints, e.g. simultaneous arrival of the vehicles
constraints that ensure minimum spatial clearance between vehiclesand obstacles
where   is used during trajectory generation phase and can bedistinct from the actual mission time
6
Problem Formulation
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
7
Decoupling Space and Time
The trajectory      can be decomposed into spatial and temporalelement by introducing parameter (Yaranenko, 1968)
The geometric element of the trajectory is now re-parameterized by
Temporal element determines howevolves with time
Let timing lawbe defined as
Hence, the trajectory can be recovered from and :
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
The timing lawprovides extra degrees-of-freedom tosatisfy spatial and temporal constraints and specifications:
The speed profile  can be adjusted independently fromthe path        if
8
Timing Law
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
Path: satisfy spatialconstraints and specifications
Path: satisfy spatialconstraints and specifications
Speed profile: satisfy temporalconstraints and specifications
Speed profile: satisfy temporalconstraints and specifications
latex-image-1.eps
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
We can formulate the trajectory-generation problem as aconstrained optimization problem
In general, for computational efficiency, the set       is the set ofdegree n real polynomials, and the set      is the set of degree mreal polynomials
9
Optimization Problem
latex-image-1.eps
subject toboundary conditions
dynamic constraints of the vehicles
mission-specific constraints
constraints for spatial de-confliction
Examples of cost functionstotal path length, total mission time, total drag (fuelconsumption), bending energy of the path, speed deviation from initial speed
latex-image-1.eps
latex-image-1.eps
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
10
Trajectory Generation
Background
Problem Form
Trajectory Gen
Sim Example
Summary
Introduce a heuristic approach to the planar trajectory generationproblem for multiple UAVs and explore the feasibility of using thisframework to generate feasible trajectories in (near) real-time
Introduce a heuristic approach to the planar trajectory generationproblem for multiple UAVs and explore the feasibility of using thisframework to generate feasible trajectories in (near) real-time
To relieve the computational load, is to seek class of curves withgeometric properties that can be exploited in satisfying the set ofimposed constraints
a.Bézier Curves
b.Pythagorean Hodograph Curves
Objective
Objective
UIUC logo.png
University of Illinois
at Urbana-Champaign
11
Dr. Pierre Bézier
Dr. Pierre Bézier, an engineer with the Renault car company, inventedthe Bézier curves in the early 1960s, to provide the designers andartists an intuitive curve formulation, for use in shape design of thecars
Bézier curves are extensively used:
Computer Graphics
Animation
Postscript Fonts (splines composed of cubic Bézier curves)
True Type Fonts (splines composed of quadratic Bézier curves)
Trajectory generation?
Cubic Béziercurve
Cubic Béziercurve
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
where
                  is dimensionless parameter
           are the Bernstein polynomials
      are the control points of the Bézier curve; the curve iscompletely defined by these control points
12
Bézier Curve
degree n Bézier curve is given by
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
C:\Users\Cherrish\Desktop\bez_curve.png
13
Bézier Curve :: Properties
Example    Degree or Quintic Bézier curve is given by
TP_tmp.png
TP_tmp.png
TP_tmp.png
TP_tmp.png
TP_tmp.png
TP_tmp.png
latex-image-1.eps
Quintic Bézier Curve
The curve starts at the first andends at the last control point
The curve lies completely inthe convex hull of the controlpoints
The curve lies tangent to thecontrol polygon at the first andlast control point
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
14
Hodographs
For degree n Bézier curve, the hodograph is degree n-1 Béziercurve and its control points are determined by the controlpoints of the curve
latex-image-1.eps
latex-image-1.eps
The locus described by the first parametric derivative of a (Bézier) curve:
The locus described by the first parametric derivative of a (Bézier) curve:
Hodograph
latex-image-1.eps
latex-image-1.eps
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
15
Minimum Distance
C:\Users\ronald\Downloads\min_dist_bez1.png
Minimum Distance
Two quintic Bézier curves
[1]Chang, J.W., Choi, Y.K., Kim, M.S., Wang W., Computation of the minimum distance between two Bézier curves/surfaces,”Shape Modeling International (SMI) Conference, vol. 35, no. 3, pp. 677-684, 2011.
Nodes-Culling method1
Iterative method to find minimum distance between two Bezier curves, using GJK andde Casteljau algorithms
Nodes-Culling method1
Iterative method to find minimum distance between two Bezier curves, using GJK andde Casteljau algorithms
Gilbert-Johnson-Keerthi (GJK) Algorithm:minimum distance between convex shapes
Bézier curves are contained withinconvex hull of control polygon
Bézier curves are contained withinconvex hull of control polygon
de Casteljau Algorithm: subdivides the curvein two segments with each control points
15-30 msec
15-30 msec
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
16
Pythagorean Hodographs (PH)
Pythagorean Hodograph curves are curves whosehodographs                          satisfy thePythagorean triple:
for some polynomial
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
PH_condition.eps
latex-image-1.eps
latex-image-1.eps
Curve
latex-image-1.eps
Then the arc length is given by:
latex-image-1.eps
Closed-form solution for the arc length!
Closed-form solution for the arc length!
latex-image-1.eps
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
For planar PH curves the following PH Condition must be satisfied
where ,, andare polynomials.
The curvature of a PH curve can also be written in terms of,
         , and     :
17
PH Condition
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
Background
Problem Form
Trajectory Gen
Sim Example
Summary
latex-image-1.eps
UIUC logo.png
University of Illinois
at Urbana-Champaign
Quintic PH Bézier curves for the planar paths
Ref. [2] states that quintic PH Bézier are the simplest PH Bézier curves that allow first-orderHermite interpolation: smooth curve with given end points and derivatives
Hence, with ,andare quadratic Bézier curves:
Quadratic Bézier curves for the timing laws
18
Choice of Curves
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
[2] Farouki, R.T., and Sakkalis, T., Pythagorean Hodographs,” IBM Journal of Research and Development, vol. 34, no. 5, pp. 736-752, September, 1990.
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
Desired speed profileis also a Bézier curve:
Closed-form solution for the time function
Sinceis a strictly monotonically increasing function, theinverse functionexists!
19
Speed Profile and Time Function
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
We can re-formulate the constrained optimization problem in terms of
           ,            , and            :
where the set      is the set of degree 2 Bézier curves
20
Trajectory-Generation Framework
subject toboundary conditions
PH Conditions
dynamic constraints of the vehicles
mission-specific constraints
constraints for spatial de-confliction
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
21
Illustrative Example
Three fixed-wing UAVs are tasked to converge to and follow threespatially de-conflicted paths and arrive at their final destinationssimultaneously (only relative temporal constraints)
Scenario : Cooperative Mission
A.Generate (offline) feasible trajectories with speed profilesallowing for simultaneous arrival
B.Simulation with cooperative path-following framework basedon kinematic model of fixed-wing UAV along with asimplified, decoupled linear model describing the roll, pitch,yaw, and speed dynamics of the closed-loop UAV with itsautopilot [3]
[3] Xargay, E., Time-Critical Cooperative Path-Following Control of Multiple Unmanned Aerial Vehicles,” Ph.D. dissertation,University of Illinois at Urbana-Champaign, Urbana, IL, United States, May 2013.
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
Given initial (position, heading angle, and speed) and final (position, heading angle, andspeed) values:
Dynamic Constraints:
Mission-specific constraints:
Spatial de-confliction:
Cost Function: minimize speed deviations from initial speed
Example :: Trajectory Generation
22
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
latex-image-1.eps
Background
Problem Form
Trajectory Gen
Sim Example
Summary
UIUC logo.png
University of Illinois
at Urbana-Champaign
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\separation23_no_sep.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\separation13_no_sep.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\flight_path_no_sep.png
Without Spatial De-confliction
23
No Spatial Separation Constraint
No Spatial Separation Constraint
Background
Problem Form
Trajectory Gen
Sim Example
Summary
(a) Two-dimensional flight paths
(b) Spatial separation between UAV 1 and UAV 3
(b) Spatial separation between UAV 2 and UAV 3
UIUC logo.png
University of Illinois
at Urbana-Champaign
Example :: Feasible Trajectories
24
Spatially De-conflicted
Spatially De-conflicted
Background
Problem Form
Trajectory Gen
Sim Example
Summary
(a) Two-dimensional flight paths
(b) Curvature of the flight paths
(e) Spatial separation betweenUAV 1 and UAV 3
(c) Speed profiles of the UAVs
(d) Timing laws and time functions
(f) Spatial separation betweenUAV 2 and UAV 3
latex-image-1.eps
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\flight_path.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\curvature.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\separation13.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\speed_profile.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\timing_law.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\separation23.png
UIUC logo.png
University of Illinois
at Urbana-Champaign
Example :: Simulation
25
Time-Critical Path Following
Time-Critical Path Following
Background
Problem Form
Trajectory Gen
Sim Example
Summary
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\Scen1_cpf3D01.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\Scen1_cpf3D02.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\Scen1_cpf3D03.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\Scen1_cpf3D04.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\Scen1_cpf3D05.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\Scen1_cpf3D06.png
UIUC logo.png
University of Illinois
at Urbana-Champaign
Example :: PF and TC Errors
26
Path-Following and Time-Coordination Errors
Path-Following and Time-Coordination Errors
Background
Problem Form
Trajectory Gen
Sim Example
Summary
(a) Position Error
(b) Attitude Error
(c) Coordination Error
(d) Coordination-state rates
(e) UAV speeds
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\Scen1_cpfPF_pF.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\Scen1_cpfPF_PsiR.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\Scen1_cpfTCC_v.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\Scen1_cpfTCC_xi.png
C:\Ronald\Dropbox\Personal\Study Documents\InfoTech13_CollAvoid\figures\Scen1_cpfTCC_xidot.png
UIUC logo.png
University of Illinois
at Urbana-Champaign
Summary
27
Introduced heuristic approach for multiple UAVstrajectory-generation problem
Preliminary results show that this heuristic approachachieves promising rates of convergence
Simulation results show that the UAVs are able toclosely follow the generated paths
Future work
Extension to spatial (3D) trajectories
Implementation in C
Comparison with existing Legendre and Chebyshev Pseudo-Spectral Methods
Background
Problem Form
Trajectory Gen
Sim Example
Summary
Thank You!
                    University of Illinois at Urbana-Champaign
UIUC logo.png
28
http://naira.mechse.illinois.edu
C:\Users\choe19\Downloads\ACRL website QR code.png