Entropy minimizing curves with application to automated flight path design

28/10/2015
Publication GSI2015
OAI : oai:www.see.asso.fr:11784:14313

Résumé

Air traffic management (ATM) aims at providing companies with a safe and ideally optimal aircraft trajectory planning. Air traffic controllers act on flight paths in such a way that no pair of aircraft come closer than the regulatory separation norm. With the increase of traffic, it is expected that the system will reach its limits in a near future: a paradigm change in ATM is planned with the introduction of trajectory based operations. This paper investigate a mean of producing realistic air routes from the output of an automated trajectory design tool. For that purpose, an entropy associated with a system of curves is defined and a mean of iteratively minimizing it is presented. The network produced is suitable for use in a semi-automated ATM system with human in the loop.

Entropy minimizing curves with application to automated flight path design

Collection

application/pdf Entropy minimizing curves with application to automated flight path design Stephane Puechmorel, Florence Nicol

Média

Voir la vidéo

Métriques

156
4
157.67 Ko
 application/pdf
bitcache://204458bc4e53436bc4cb6f6b82a81aca0306cff8

Licence

Creative Commons Attribution-ShareAlike 4.0 International

Sponsors

Organisateurs

logo_see.gif
logocampusparissaclay.png

Sponsors

entropy1-01.png
springer-logo.png
lncs_logo.png
Séminaire Léon Brillouin Logo
logothales.jpg
smai.png
logo_cnrs_2.jpg
gdr-isis.png
logo_gdr-mia.png
logo_x.jpeg
logo-lix.png
logorioniledefrance.jpg
isc-pif_logo.png
logo_telecom_paristech.png
csdcunitwinlogo.jpg
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/11784/14313</identifier><creators><creator><creatorName>Stephane Puechmorel</creatorName></creator><creator><creatorName>Florence Nicol</creatorName></creator></creators><titles>
            <title>Entropy minimizing curves with application to automated flight path design</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2015</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sun 8 Nov 2015</date>
	    <date dateType="Updated">Wed 31 Aug 2016</date>
            <date dateType="Submitted">Fri 20 Jul 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">204458bc4e53436bc4cb6f6b82a81aca0306cff8</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>24705</version>
        <descriptions>
            <description descriptionType="Abstract">
Air traffic management (ATM) aims at providing companies with a safe and ideally optimal aircraft trajectory planning. Air traffic controllers act on flight paths in such a way that no pair of aircraft come closer than the regulatory separation norm. With the increase of traffic, it is expected that the system will reach its limits in a near future: a paradigm change in ATM is planned with the introduction of trajectory based operations. This paper investigate a mean of producing realistic air routes from the output of an automated trajectory design tool. For that purpose, an entropy associated with a system of curves is defined and a mean of iteratively minimizing it is presented. The network produced is suitable for use in a semi-automated ATM system with human in the loop.

</description>
        </descriptions>
    </resource>
.

Entropy minimizing curves Application to automated ight path design S. Puechmorel ENAC 29th October 2015 Problem Statement Flight path planning • Trac is expected to double by 2050; • In future systems, trajectories will be negotiated and optimized well before the ights start; • But humans will be in the loop : generated ight plans must comply with operational constraints; Muti-agent systems • A promising approach to address the planning problem; • Does not end up with a human friendly trac! • Idea : start with the proposed solution and rebuild a route network from it. A curve optimization problem An entropy criterion • Route networks and currently made of straight segments connecting beacons; • May be viewed as a maximally concentrated spatial density distribution; • Minimizing the entropy with such a density will intuitively yield a ight path system close to what is expected. Problem modeling Density associated with a curve system • A classical measure : counting the number of aircraft in each bin of a spatial grid and averaging over time; • Suers from a severe aw : aircraft with low velocity will over-contribute; • May be corrected by enforcing invariance under re-parametrization of curves; • Combined with a non-parametric kernel estimate to yield : ˜d : x → N i=1 1 0 K ( x − γi (t) ) γi (t) dt N i=1 Ω 1 0 K ( x − γi (t) ) γi (t) dtdx (1) Problem modeling II The entropy criterion • Kernel K is normalized over the domain Ω so as to have a unit integral; • Density is directly related to lengths li , i = 1. . . n of curves γi , i = 1. . . N : ˜d : x → N i=1 1 0 K ( x − γi (t) ) γi (t) dt N i=1 li (2) • Associated entropy is : E(γ1, . . . , γN) = − Ω ˜d(x) log ˜d(x) dx (3) Optimal curve displacement eld Entropy variation • ˜d has integral 1 over the domain Ω ; • It implies that : − ∂ ∂γj E(γ1, . . . , γN)( ) = Ω ∂ ˜d(x) ∂γj ( ) log ˜d(x) dx (4) where is an admissible variation of curve γi . • The denominator in the expression of ˜d has derivative : [0,1] γj (t) γj (t) , (t) dt = − [0,1] γj (t) γj (t) N , dt (5) Optimal curve displacement eld Entropy variation • The numerator of ˜d has derivative : [0,1] γj (t) − x γj (t) − x N , K ( γj (t) − x ) γj (t) dt (6) − [0,1] γj (t) γj (t) N , K ( γj (t) − x ) dt (7) Optimal curve displacement eld II Normal move • Final expression yield a displacement eld normal to the curve : Ω γj (t) − x γj (t) − x N K ( γj (t) − x ) log ˜d(x)dx γj (t) (8) − Ω K ( γj (t) − x ) log ˜d(x))dx γj (t) γj (t) N (9) + Ω ˜d(x) log( ˜d(x))dx γj (t) γj (t) N n i=1 li (10) Implementation A gradient algorithm • The move is based on a tangent vector in the tangent space to Imm([0, 1], R3)/Di+ ([0, 1) ; • It is not directly implementable on a computer; • A simple, landmark based approach with evenly spaced points was used; • A compactly supported kernel (epanechnikov) was selected : it allows the computation of density ˜d on GPUs as a texture operation that is very fast. A output from the multi-agent system Integration in the complete system • Route building from initially conicting trajectories : Figure  Initial ight plans and nal ones Conclusion and future work An integrated algorithm • Entropy minimizer is now a part of the overall route design system; • Only a simple post-processing is necessary to output a usable airways network; • The complete algorithm is being ported to GPU. Future work : take the headings into account • The behavior is not completely satisfactory when routes are converging in opposite directions; • An improved version will make use of entropy of a distribution in a Lie group (publication in progress).