A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the...

14
A Route Selection Problem Applied to Auto-Piloted Aircraft Tugs GIUSEPPE SIRIGUiuseppe Sirigu Politecnico di Torino Department of Mechanical and Aerospace Engineering Corso Duca degli Abruzzi 24 10129, Torino, ITALY [email protected] Mario Cassaro ONERA Dpartement traitement de l’information et systmes Toulouse, FRANCErance [email protected] Manuela Battipede, Piero Gili Politecnico di Torino Department of Mechanical and Aerospace Engineering C.so Duca degli Abruzzi 24 10129, Torino, ITALY [email protected] [email protected] Abstract: The antithetical needs of increasing the air traffic, reducing the air pollutant and noise emissions, jointly with the prominent problem of airport congestion spur to radically innovate the entire ground operation system and airport management. In this scenario, an alternative autonomous system for engine-off taxiing (dispatch tow- ing) attracts the interest of the civil aviation world. Even though structural and regulatory limitations undermine the employment of the already existing push-back tractors to this purpose, they remain the main candidates to accomplish the mission. New technologies are already under investigation to optimize towbarless tractor joints, so as to respond to the structure safety requirements. However, regulation limitations will soon be an issue. In this paper, a software solution for a route selection problem in a discretized airport environment is presented, in the believe that a full-authority control system, including tractors’ selection logic, path planning and mission event sequencing algorithms will possibly meet the regulation requirements. Four different algorithms are implemented and compared: two Hopfield-type neural networks and two algorithms based on graph theory. They compute the shortest path, accounting for restricted airport areas, preferential directions and dynamic obstacles. The computed route checkpoints serve as a reference for the tractor autopilot. Two different missions are analyzed, concerning the towing of departing and arriving aircraft respectively. A single mission consists of three different events, called phases: Phase 1 goes from the actual tractor position (eventually the parking zone) to the selected aircraft (parked or just landed); Phase 2 is the actual engine-off taxi towing; Phase 3 is the tractor return to its own parking zone. Both missions are simulated and results are reported and compared. Key–Words: Route selection, Airport Taxiing, Neural Network, Hopfield, Dijkstra, A* 1 Introduction The current vivid interest of the civil aviation in the development and implementation of innovative air- port management and ground operation systems is prompted by the antithetical needs of increasing the air traffic, reducing the air pollutant and noise emis- sions. In particular, airport congestion is globally rec- ognized as one of the most prominent problem areas of the next future and the straightforward solution of expanding the airfields is not that efficient and not al- ways doable. In fact, the higher complexity of air terminals deriving from the addition of runways and taxiways will penalize the overall system efficiency by increasing the human workload and error risk, re- sulting in potentially hazardous situations. For ex- ample, Hilburn in [4] and the ICAO regulations [10] demonstrate the high level of risk derived by the Head Down Operations (HDOs) during taxi phases. In ad- dition, the increasing aircraft number, jointly with the longer taxiing, will significantly contribute to an in- crease in fuel burn and emissions, which is in contrast with the stringent environmental regulations. There- fore, the concept of autonomous engines-off taxiing, using towing vehicles, has been recently investigated and recognized as a feasible and effective solution to the aforementioned issues. It consists in employing push-back tractors to tow the aircraft from gate to run- way for departure and from runway to gate for arrival, while keeping engines off during ground movements. To make the new concept operative, some structural and regulatory issues need to be solved. Structurally, nose landing gears (NLGs) are not designed to be towed for long distances; this feature can lead to fa- tigue failures due to transversal loads. Towbarless sys- tems decrease NLG loads, while ensuring an effective connection between the aircraft and the tractor. Thus, they can be used to tow the aircraft along the entire taxiing path. Indeed, aeronautical industries and aca- demics are currently investigating different solutions, WSEAS TRANSACTIONS on ELECTRONICS Giuseppe Sirigu, Mario Cassaro, Manuela Battipede, Piero Gili E-ISSN: 2415-1513 27 Volume 8, 2017

Transcript of A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the...

Page 1: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

A Route Selection Problem Applied to Auto-Piloted Aircraft Tugs

GIUSEPPE SIRIGUiuseppe SiriguPolitecnico di Torino

Department of Mechanicaland Aerospace Engineering

Corso Duca degli Abruzzi 2410129, Torino, ITALY

[email protected]

Mario CassaroONERA

Dpartement traitement del’information et systmes

Toulouse, [email protected]

Manuela Battipede, Piero GiliPolitecnico di Torino

Department of Mechanicaland Aerospace EngineeringC.so Duca degli Abruzzi 24

10129, Torino, [email protected]

[email protected]

Abstract: The antithetical needs of increasing the air traffic, reducing the air pollutant and noise emissions, jointlywith the prominent problem of airport congestion spur to radically innovate the entire ground operation systemand airport management. In this scenario, an alternative autonomous system for engine-off taxiing (dispatch tow-ing) attracts the interest of the civil aviation world. Even though structural and regulatory limitations underminethe employment of the already existing push-back tractors to this purpose, they remain the main candidates toaccomplish the mission. New technologies are already under investigation to optimize towbarless tractor joints,so as to respond to the structure safety requirements. However, regulation limitations will soon be an issue. Inthis paper, a software solution for a route selection problem in a discretized airport environment is presented, inthe believe that a full-authority control system, including tractors’ selection logic, path planning and mission eventsequencing algorithms will possibly meet the regulation requirements. Four different algorithms are implementedand compared: two Hopfield-type neural networks and two algorithms based on graph theory. They compute theshortest path, accounting for restricted airport areas, preferential directions and dynamic obstacles. The computedroute checkpoints serve as a reference for the tractor autopilot. Two different missions are analyzed, concerningthe towing of departing and arriving aircraft respectively. A single mission consists of three different events, calledphases: Phase 1 goes from the actual tractor position (eventually the parking zone) to the selected aircraft (parkedor just landed); Phase 2 is the actual engine-off taxi towing; Phase 3 is the tractor return to its own parking zone.Both missions are simulated and results are reported and compared.

Key–Words: Route selection, Airport Taxiing, Neural Network, Hopfield, Dijkstra, A*

1 Introduction

The current vivid interest of the civil aviation in thedevelopment and implementation of innovative air-port management and ground operation systems isprompted by the antithetical needs of increasing theair traffic, reducing the air pollutant and noise emis-sions. In particular, airport congestion is globally rec-ognized as one of the most prominent problem areasof the next future and the straightforward solution ofexpanding the airfields is not that efficient and not al-ways doable. In fact, the higher complexity of airterminals deriving from the addition of runways andtaxiways will penalize the overall system efficiencyby increasing the human workload and error risk, re-sulting in potentially hazardous situations. For ex-ample, Hilburn in [4] and the ICAO regulations [10]demonstrate the high level of risk derived by the HeadDown Operations (HDOs) during taxi phases. In ad-dition, the increasing aircraft number, jointly with the

longer taxiing, will significantly contribute to an in-crease in fuel burn and emissions, which is in contrastwith the stringent environmental regulations. There-fore, the concept of autonomous engines-off taxiing,using towing vehicles, has been recently investigatedand recognized as a feasible and effective solution tothe aforementioned issues. It consists in employingpush-back tractors to tow the aircraft from gate to run-way for departure and from runway to gate for arrival,while keeping engines off during ground movements.To make the new concept operative, some structuraland regulatory issues need to be solved. Structurally,nose landing gears (NLGs) are not designed to betowed for long distances; this feature can lead to fa-tigue failures due to transversal loads. Towbarless sys-tems decrease NLG loads, while ensuring an effectiveconnection between the aircraft and the tractor. Thus,they can be used to tow the aircraft along the entiretaxiing path. Indeed, aeronautical industries and aca-demics are currently investigating different solutions,

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 27 Volume 8, 2017

IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
MANUELA BATTIPEDE, PIERO GILI
IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
MARIO CASSARO
IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
IARAS
Typewritten Text
GIUSEPPE SIRIGU
IARAS
Typewritten Text
Page 2: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

ranging from a semi-robotic towbarless tractor [15] toa completely autonomous system [14]. In the Taxibotsolution, developed by an industrial consortium, thethrust required for taxing is provided by a diesel en-gine tug, while the direction control is managed by theaircraft pilot through the aircraft steering system [15].This control setup allows to avoid regulations’ limi-tations since the pilot stays in charge of the groundmaneuvering. Even if the explained solution seems tobe of ease implementation in short time and resolvethe air-noise pollution and fuel consumption issues, ithas a major drawback that is the increased hazardousconditions deriving from the higher complexity levelof operations, to be performed by pilots and groundoperators. On the other hand, an autonomous exter-nal taxiing system, with a manned tugs that tows anddrives utterly the aircraft through the taxiways, willreduce the pilot workload and will optimize the air-port ground movements. In this configuration, all thepre-flight procedures (e.g. aircraft system functional-ity checks, Flight Management System setup and en-gine warm up ) might be performed by the pilot duringthe semi-autonomous taxi, without loss of safety [14].The drawback consists of a regulatory limitation, es-pecially in terms of responsibility allocation, derivingfrom the lack of Pilot in Control (PIC) situation.To this purpose, another concept of airport groundoperation system has been presented by our researchteam [5]. It consists in a semi-automatic system, acti-vated by the control tower, in which autonomous auto-piloted tractors are capable of accomplishing towingmissions between points, selected by the tower oper-ators. Albeit a full-authority control system for tugselection and route conflict avoidance will be requiredfor the final application, at the project status, the routeselection problem is the major objective. The routeselection problem is thoroughly addressed in litera-ture and it has been solve by several techniques suchas genetic algorithms [6], heuristic methods [24] [3][25] and tabu search algorithms [16]. Neural networkshave been also used for vehicle and computer networkrouting. In particular, Hopfield-type Neural Networks(HNNs) [11] [12] [13] have been extensively used inthe past to these purposes, as they minimize an en-ergy function, which can be properly defined to per-form a shortest path search [18] [20] or can be used ina non-static environment [27]. Lately, among all theother solutions, the graph theory and the Dijkstra’s al-gorithm became established methodologies, becauseof their fastness and robustness, to solve routing se-lection problems in any kind of environment [8] [17][2]. In addition, a modified version of the Dijkstraalgorithm, which uses heuristic functions to define apreferential search direction, called A* [22] [26] [7],allows for further computational time reduction with

respect to the standard Dijkstra’s algorithm, particu-larly noticeable for large dimensions of the searchingdomain.In this paper, a software solution for the push-backtractor route selection problem in a discretized airportenvironment (apron) is presented. Four different al-gorithms are implemented: two Hopfield-type neuralnetworks and two algorithms based on the graph the-ory. Their objective is the shortest path, accountingfor restricted airport areas, preferential directions anddynamic obstacles. The computed route checkpointsserve as reference for the tractor autopilot. Two dif-ferent missions are analyzed, concerning the towingof departing and arriving aircraft respectively. A sin-gle mission consists of three different events, calledphases: Phase 1 goes from the actual tractor position(eventually the parking zone) to the selected aircraft(parked or just landed); Phase 2 is the actual engine-off taxi towing; Phase 3 is the tractor return to its ownparking zone. The paper is organized as follows: Sec-tion 2 contains the problem formulation referred toour test case airport; in Section 3 the mathematicalformulation of the proposed algorithms is presentedand their application justified. Section 4 describes thealgorithms’ implementation and the results obtainedfor the selected test case. Pertinent conclusions arereported in the closing section.

2 Problem FormulationA single mission of the tug is discretized in three dif-ferent phases which have different initial and finalcheckpoints, whether an aircraft departure or arrivalmission is being performed.

• Phase 1: reaching the targeted aircraft (A/C park-ing slot for departure mission, runways for ar-rival mission);

• Phase 2: perform engine-off taxi towing (apronto runways for departure mission, vice versa forarrival mission);

• Phase 3: returning to the tug parking area (run-ways to parking for departure mission, apron toparking for arrival mission).

As already mentioned, the problem to be solved foreach phase is a shortest path route selection problemin a non-static environment with constraints. The con-sidered constraints are the apron ground vehicles per-mitted ways, the one-way only routes and the differ-ent obstacles that can obstruct the way. Therefore, thetrivial straight-line trajectory between initial and end-ing checkpoints of each phase is not always a solutionof the problem. Fig. 1, which represents our test case,

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 28 Volume 8, 2017

Page 3: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

shows the actual taxiways and ground vehicle permit-ted areas in the Sandro Pertini airport of Turin.

Figure 1: Turin Airport ”Sandro Pertini”, satellitepicture with directions for taxi and ground move-ment. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google

For the proposed application, the spatial domainis given by the airport runways, taxiways, ground ve-hicles routes, and aircraft parking lots. Route se-lection algorithms require a domain discretization incheckpoints and arcs with directions and possible ob-stacles. For the proposed application, this operation isautomatically performed by a tool coded on purposethat discretizes differently depending on the path op-timization algorithm to be used. Fig. 2 represents oneof the possible Sandro Pertini airport discretization,with very few points for sake of clarity of the figure.The blue stars represent the checkpoints in the permit-ted airport area, while the black link are the permittedways between checkpoints. Once the spatial domainis discretized, the proposed algorithm should computethe shortest path, for each phase separately and a pre-selected tug-aircraft combination. The mission (de-parture or arrival), tug and aircraft definition is con-sidered at the moment as an external input, which canbe provided from a human operator or a schedulingsoftware in the future.

Figure 2: ”Sandro Pertini” airport checkpoint dis-cretization. Credits: Pictures 2015 DigitalGlobe, Mapdata c©2015 Google

3 Proposed AlgorithmsThe proposed algorithm consists of two main parts:the first one loads the airport geographical data (lon-gitude and latitude) and discretizes the domain, basedon the apron features; the second solves the routeselection problem computing the shortest path foreach mission phase. The computation on the do-main is performed only once at the beginning, whilethe route selection algorithm is run three times permission (arrival or departure). This section givesan overview of the mathematical formulations of thedifferent methodologies employed and compared tosolve the route selection problem under analysis.

3.1 Neural NetworkArtificial neural networks are paradigms of a non-analytic way of solving problems, which are appliedin different fields of science and engineering becauseof their versatility [9]. This system, inspired by bi-ological nervous systems, is able to learn and makeintelligent decisions without a precisely defined al-gorithm or a complete set of input data. Althoughthe work of individual neurons can be quite slow, theoverall neural network is very fast, which is due tothe large neuronal connections and parallel process-ing [9], [23]. Among all types of neural networks,particular attention is given here to the recursive neu-ral networks [18], which are characterized by a feed-back signal that allows the net to use the neuron outputvalue as an input, to obtain a faster and more robust re-sponse. Typically, this is the time delay of the signal[9]. Hopfield’s neural networks are representative ofthis type of networks [11], [12], and its structure isshown in Fig. 3.

One of the main features of the Hopfield neuralnetwork is the possibility of a simple hardware imple-mentation, as suggested by Fig. 4. Hopfield and Tankproposed their neural network structure [12] capableof solving different complex problems by the mini-mization of an energy function that has to be properlydefined. This approach was demonstrated on the well-known and computationally very complex TravelingSalesman Problem (TSP) with 30 nodes [12]. Sincethen, many researchers have used similar models forsolving a large variety of combinatorial optimizationproblems.

3.1.1 Hopfield Neural Network ImplementationEach neuron is realized as an operational amplifierwith an increasing sigmoid function, relating the out-put Vi and the input Ui of the i-th neuron. In this way,the network acquires the characteristics of nonlinear-ity. Output values are called to range from 0 to 1. The

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 29 Volume 8, 2017

Page 4: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

Figure 3: Hopfield neural network electric circuitmodel [13].

Figure 4: Electronic circuit model of Hopfield neuron.

activation function for each neuron is given as [12],[18]

Vxi = gxi (Uxi) =1

1 + e−λxi·Uxi(1)

where λ is a constant that determines the decli-nation of the characteristics. In accordance with therule of recursive networks, the output signal of the i-th neuron is fed back as input for the other neuronsof the input layer, through resistive connections. Thisconnectivity is defined with the synaptic weight ma-trix T = [Tij ]. In addition to receiving signals fromthe output neurons, each of the input neurons operateswith the additional electrical signal (bias current) Ii.This is to adjust the polarization of the input neurons[12]. The input signals’ dynamics is defined by equa-

tion 2,

dUidt

= −Uiτ

+N∑j=1

TijVj + Ii (2)

where τ is the time constant. Each neuron has itsown entrance Ui, the output signal Vi and the polar-ization signal Ii, which defines the checkpoint activa-tion level. Output feedbacks Vi and the external inputsof each neuron pass through the resistance R, i 6= j(called synapses), and iteratively provide a change ofstate of the network. At the end of the process, thenetwork converges to a stable state. A capacitor Ci isconnected in parallel to the resistance, and its capac-ity affects the neuron state as shown in the followingrelation [12].

CidUidt

= −UiRi

+

N∑j=1

TijVj + Ii (3)

The capacitor Ci acts at the input of the nonlineardifferential amplifier, whose output signals are func-tion of Vi and −Vi of these cells, according to Eq. (1)[11]. If the steepness of the sigmoid function is suf-ficiently large (for instance λi > 100), the stabilityof the network, in the Lyapunov sense, may be veri-fied by observing the energy function, E, describingthe state of the network [12]

E = −1

2

N∑i=1

N∑j=1

Tij · VjVi −N∑i=1

ViIi (4)

For the large reinforcement of an operational am-plifier, the minimum energy, at a given N dimen-sional space, is allocated in 2N distinct states, asso-ciated with an N-dimensional hypercube with sidesV ∈ {0, 1}. Then the dynamics of the i-th neuron,according to equation (2), can be expressed as

dUidt

= −Uiτ− ∂E

∂Vi(5)

Relation (5) defines the change of the input sig-nal and the neuron energy at every iteration. It canbe demonstrated that this network architecture con-verges to stable states [21]. Such a network is usedas a basic network structure for solving optimizationproblems. Starting from the original Hopfield-Tanksarchitecture, several modifications have been imple-mented for performance improvement purposes, as forexample the model proposed by Ali and Kamoun [18].In their model, the network has n (n− 1) neurons,where n denotes the dimension of the input squarematrix, by neglecting the self-recursive signals that

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 30 Volume 8, 2017

Page 5: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

are the diagonal elements (i, i) in matrix T . Duringthe iteration process, the stable neuron states definethe shortest path between the source (s) and the desti-nation (d) points. A suitable energy function is of theform

E =µ1

2

∑X

∑i6=X

(X,i)6=(d,s)

CXiVXi+

+µ2

2

∑X

∑i6=X

(X,i)6=(d,s)

ρXiVXi+

+µ3

2

∑X

∑i6=X

VXi −∑i6=X

ViX

2

+

+µ4

2

∑X

∑i6=X

VXi (1− VXi) +

+µ5

2(1− Vds)

(6)

CoefficientsCXi are the link costs from neuronXto router i and the terms ρXi describe the connectionbetween routers: the value is 1 if the routers are notconnected, and 0 for connected routers. The term µ1

minimizes the total cost; µ2 prevents nonexistent linksfrom being included in the chosen path; µ3 is zero forevery router in the valid path (the number of incom-ing links is equal to the number of outgoing links); µ4

forces the state of the neural network to converge toone of the stable statescorners of the hypercube de-fined by V ∈ 0, 1. The state Vi is close to 1 for routerbelonging to the valid path, otherwise the state is closeto 0. The term µ5 is zero when the output Vds is equalto 1. This term is introduced to ensure that the sourceand the destination routers belong to the solution (theshortest path). The main contribution of the Ali andKamoun’s approach [21] consist in keeping the synap-tic conductance constant (7), while the link costs andthe information about the connection between nodeswere associated to the bias currents Ii:

TXi,Y i = µ4δXY δij − µ3 (δXY + δij − δjX − δiY )(7)

IXi =

µ52 −

µ42 (X, i) = (d, s)

−µ12 CXi −

µ22 ρXi −

µ42 otherwise

(8)where δii = 1 ,δij = 0, for i 6= j. In this way,

the neural network algorithm becomes very attractivefor real time processing, since bias currents may be

easily controlled via external circuitry, following thechanges in actual traffic through the network. Sev-eral researches demonstrate that HNN is very effectivefor shortest or optimal path problem solution. On theother hand, the main drawbacks is the net possible in-stability, typically caused by the noise amplification inrecursive algorithms, and the not guaranteed optimalsolution convergence. However, as Hopfield demon-strated, if the obtained solution is not optimal, it willbe in a group of solutions that are very ”close to” theoptimal.

3.1.2 Modified Hopfield Neural Network.An Hopfield-type neural network has been proposedby Zhong et al. [27] for real-time collision-free robotpath planning in a non-static environment. This ap-proach is based on the propagation of the target activ-ity through the local connectivity of neurons, which isformulated using harmonic functions. The main ad-vantage in using harmonic functions lies in the localminima removal. In their application, Zhong et al.used the Laplace operator discretization applying a fi-nite difference scheme on the grid reported in Fig. 5[27].

Figure 5: Local connectivity grid [27].

The dynamics of the neural network is given byEq. (9)

dUidt

= −UiRi

+∑

e(j)∈Nr(i)

AijUi + Ii (9)

where Nr (i) represents the neighborhood of ra-dius r of the neuron e (i) and Aij is the jth element

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 31 Volume 8, 2017

Page 6: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

of the local connectivity matrix of the neuron e (i).The initial neurons activity can be modulated by us-ing the bias current Ii, which assumes the value E ifthe ith neuron is the target, otherwise it is equal to 0,as expressed by Eq. (10):

Ii =

{E if there is a target0 otherwise

(10)

Using the grid reported in Fig. 5, the local con-nectivity for each neuron assumes the shape reportedin Eq. (11). The global stability of this neural net-work has been proved using the Lyapunov’s method,even though the local connectivity is asymmetric [27].

A =(A1, A2, A3

)(11)

where,

A1 =

2h

∆sj(∆sj−1+∆sj)

2h∆ui−1(∆ui−1+∆ui)

2h∆qi−1(∆qi−1+∆qi)

(12)

A2 =

2h

∆wj(∆wj−1+∆wj)

0

2h∆wj−1(∆wj−1+∆wj)

(13)

A3 =

2h

∆qi(∆qi−1+∆qi)

2h∆ui(∆ui−1+∆ui)

2h∆sj−1(∆sj−1+∆sj)

(14)

3.2 Graph Theory

Graph representation is very effective in describingreal-world situations. Graphs are schemes consistingin points (nodes) and links (edges) connecting a pairsof nodes [1]. The basic graph form is composed of un-weighted and undirected edges. However, some realapplications could be more effectively represented bymeans of a weighted graph. The main idea is to as-sociate a weight, or cost, to each edge and the totalcost of a path in the graph is defined as the sum of thecosts of each selected edge [19]. This approach allowsfor easy representation of optimization problems aim-ing to find a graph subset with minimum or maximumweight, as the shortest route selection problem. Fur-thermore, by specifying edges directions, it is possi-ble to reproduce an asymmetrical domain. For the ap-plication under investigation, the relative distance be-tween two points is used as edge weight and the edgedirection is used to simulate one-ways only routes.

An algorithm based on graph theory was pre-sented by Dijkstra in 1959 [8]. It is able to find the

shortest route from one starting point within the spa-tial domain to all the vertices of the graph. A mod-ified version of the Dijkstra’s algorithm, which usesan heuristic function to define a preferential search di-rection, was proposed in 1968 and is called A* [22].These two algorithms do not require any parametersetting, leading to an easier implementation processwith respect to the two neural networks implemented.

3.2.1 Dijkstra’s Algorithm.Consider a graph G(V,E,w), where V is the set ofnodes, E is the set of edges and w(uv) is the weightof the edge from u tu v, a source node s and a targett. S is a subset of V such that s ∈ S and denote V \Sas S. If P = s...st is the shortest path from s to S,then, s ∈ S and the finite sequence s...s of P is theshortest path from s to s. Thus, the distance from s tot is expressed as

d (s, t) = d (s, s) + w (st) (15)

Therefore, starting from the subset containing theonly source S0 = {s}, it is possible to construct anincreasing sequence of subsets S0, S1, ..., Sn−1 of Vsuch that, at a certain step i, the shortest paths froms to all the nodes in Si are calculated. The Dijkstra’salgorithm is schematically outlined as follows, report-ing the different steps to obtain the shortest path froma generic source node to all the domain vertices.Consider a domain with n points; first of all, it is nec-essary to define some variables:

• l(v) is the length of the shortest path from thesource node s to a generic node v;

• S is the set of nodes v for which the shortest pathfrom s to v has been found (closed set);

• X is the set of nodes v for which a path has beenfound, but may be not the shortest path (openset);

• E(v) is the set of neighbors of the generic nodev.

• parent is a n × 1 vector, containing the label ofthe node that precedes v in the shortest path to v.

The Dijkstra’s algorithm can be divided in foursteps:

1. Set S = ∅, X = {s}, l(s) = 0, l(v) = ∞ forv 6= s;

2. Find v ∈ X : l(v) = minu∈X l(u), add it to Sand remove it from X;

3. ∀u ∈ E(v)

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 32 Volume 8, 2017

Page 7: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

(a) If u ∈ X∧l(v)+w(v, u) < l(u), set l(u) =l(v) + w(v, u) and parent(u) = v;

(b) If u /∈ S ∧ u /∈ X, X = {X,u}, setl(u) = l(v) + w(v, u) and parent(u) = v;

4. If X 6= ∅ repeat from Step 2.

When the algorithm terminates, the shortest pathsfrom s to all the other points are computed, and thusalso the shortest path from the source s to the targett. To save computational time, it is possible to ter-minate the process when the node t is added to S. Itcan be proved by means of Lemma 1 in [22] that Di-jkstra’s algorithm always finds the optimal (shortest)path from s to v.

3.2.2 A* Algorithm

As mentioned, the A* algorithm is an improvement ofthe Dijkstra’s algorithm obtained by adding a heuristicfunction to fasten the solution [22]. The introducedevaluation function is

f(v) = l(v) + h(v) (16)

where, h(v) is the distance from v to t. Thus,f(v) represents the distance from s to t, passingthrough v. h(v) can be estimated by means of anheuristic function h(v), for example the Euclideandistance. However, the optimal heuristic function isproblem dependent and so forth cannot be defineduniquely. Conversely to the Dijkstra’s algorithm, thus,the subsequent check-point of the path is chosen usingthe following relation:

f(v) = minu∈X

f(u) (17)

Hart et al. [22] prove that the A* algorithm findsthe optimal solution as long as the distance from vto t is underestimated, which means that the relationh(v) ≤ h(v) must be satisfied. The A* algorithmsteps are the same of the Dijkstra’s one, where thefunction l(v) is substituted by f(v).

4 Implementation and ResultsThe proposed algorithms have been implemented fortest and comparison purposes in Matlab R© environ-ment without using any existing toolbox. The code,which is optimized for airport environment, allows foran automatic discretization of the apron area of certainairports belonging to an available database.

4.1 Airport data loading and domain dis-cretization

The first operation required to apply the several al-gorithms available is to define the spatial domain interms of geographical coordinate system and properlydiscretize it. An airport official website can providethose information, as aircraft parking/docking, taxi-ways and runways locations through the aeronauticalinformation publication (AIP). It must be pointed outthat the spatial domain discretization differs whetherneural network or graph theory based algorithms arebeing used. When the HNN based algorithm is em-ployed, the whole set of available checkpoint coordi-nates are normalized to 1, indexed and stored in a 2Dmatrix. The maximum dimension of the airport do-main and the geographical distances between check-points are stored in a second matrix for the actual pathlength computation. An extra matrix, called connec-tivity matrix contains the information about the avail-able connections and directions between nodes (Fig.2). As already explained in section 3, the generic ele-ment ij of the connectivity matrix is 0, if nodes i and jare connected, 1 otherwise.As the modified HNN requires high spatial accuracy,a dense grid is needed, which implies an high numberof neurons, because of the correspondence of nodes,checkpoints and neurons for this particular neural net-work mathematical model. For the modified HNNeach neuron is connected with other 4 neurons, so a4 × 4 local connectivity matrix is defined, instead ofhaving a global matrix. In the proposed application,the four connected neurons are arranged in a + con-figuration, and the diagonal motion between nodes isso forth not allowed. In this case, the obstacle nodeindexes are stored in a different matrix and used toproperly modify the local connectivity matrix duringthe simulation of the network dynamics.As far as the graph theory based algorithm are con-cerned, the domain discretization coincides with thestandard HNN application with a different concept ofthe connectivity matrix. The generic element ij is ex-actly the distance between the i and j nodes if con-nected, otherwise is 0.A graphical user interface (GUI) has been developed,always in Matlab R© environment, to make the prepro-cessing more user friendly and to easily access differ-ent airport database. The GUI showing the discretiza-tion of the Sandro Pertini airport for the graph algo-rithms is reported in Appendix A. The whole set ofmatrices represents the airport database named withits ICAO code.

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 33 Volume 8, 2017

Page 8: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

4.2 Shortest path computation

The core of the implemented code is the shortest pathcomputation and, as far as the HNN based algorithmsare concerned, the time evolution of the state of theneural network is simulated by numerically solvingEq. (5). The net simulation corresponds to solve asystem of n (n− 1) nonlinear differential equations,where the variables are the neuron output voltagesVXi. The fourth order Runge-Kutta method has beenchosen for the numerical solution in time domain, asit is sufficiently accurate and of easy implementation.Accordingly, the simulation consists in observing andupdating the neuron output voltages at incrementaldiscrete time steps δt = 10−5sec. The time con-stant τ of each neuron is set to 1 and, for simplicity,λXi = λ and gXi = g are assumed to be independentof the subscript (X, i). Of critical importance is thenetwork initial condition, which is defined by the neu-rons initial input voltages UXi. Albeit, a null voltagecondition for the entire domain will guarantee to notpreconditioning the final solution, the symmetric net-work topology imposes the insertion of some initialrandom noise −0.0002 ≤ δUXi ≤ +0.0002 to drivethe net to one of the possible multiple shortest paths.The simulation is stopped when the system reaches astable final state. This is assumed to occur when allneuron output voltages do not change by more than athreshold value of ∆Vth = 10−5 between two timesteps. When the steady state of the net is reached,each neuron is defined either On if VXi ≥ 0.5 or Offif VXi ≤ 0.5. The described process is referred to asingle mission phase and then is repeated three timesper mission. The shortest path computed as the sumof the three phases is finally displayed on the airportsatellite map.Unlike the standard HNN, its modified version alwaysleads to an optimal solution resulting in the shortestpath from the starting node to the target. From thesource position, the activation values of the neighbornodes, belonging to the local connectivity matrix, isevaluated at each discrete time step. The highest ac-tivity value identifies the next neuron of the path. Ifnone of the neighbor nodes has higher activity valuethan the actual neuron, the path does not evolve. Thismechanism allows to simulate unsteady environmentswith, for example, moving obstacles or changing tar-gets. The simulation terminates when the vehiclereaches the target. However, for sake of clarity, thedynamics of the moving obstacle must be slower thanthe net evolution time in order to be captured. Alsoin this case, the described process is referred to a sin-gle mission phase and then is repeated three times permission. The shortest path computed as the sum of thethree phases is finally displayed on the airport satellite

map.As far as the two graph theory based algorithms areconcerned, after the airport database initialization, it-erations start by adding the source node s to the setof the found shortest paths S. The algorithm prose-cutes by repeating iteratively step 2 and 3, describedin the previous section, until the target is added to theclosed set S. As S contains the shortest path from thesource to the different nodes, the shortest path froms to t must be reversely reconstructed: starting fromthe target node, the point stored in the correspondingparent vector row is added to the path; the operationis repeated until the source node is reached.

4.3 Test case results using standard HNNTo validate the algorithms’ functioning and to com-pare their performance, a test case application for theTurin airport Sandro Pertini is implemented (Fig. 1).A network of 102 checkpoints is created correspond-ing to the real airport parking decks and taxiways.The global connectivity matrix, defined using Eq. (7),respects the airport regulations. Value 1 is given tothe matrix elements representing unconnected nodes,while the zeros are existing connections. As previ-ously discussed, the matrix is not symmetric becausesome taxiways are one way only.

For the simulated test case an appropriate param-eters’ setup is found by the general rules reported in[18]:

µ1 = 100;µ2 = 3500;µ3 = 2500;µ4 = 100;µ5 = 3500.

In particular, the suboptimal parameter setup isa compromise between obtaining legitimate tours (µ1

small) and heavily weighting the distances betweennodes (µ1 large). Furthermore, undersized or over-sized values of λ (gain) result in fuzzy VXi distribu-tion, which drives the simulation to a non-optimal so-lution. In the reported test case, this parameter is set toλ = 50. Results of the simulations are reported fromFig. 6 to Fig. 11, where two different tug missionsare analyzed. The first is an aircraft departure missionwhere the tug initial position is in its deposit area andthe airplane is located in a generic parking lot in theapron. The second is an aircraft arrival mission wherethe tug is randomly located in the apron, as its initialposition, and an appropriate parking lot is chosen forairplane. For sake of clarity, each figure shows sepa-rately one mission phase, the optimized paths are de-picted in the figures with different colors and the ini-tial and target points are indicated respectively witha magenta and black cross. It is worth pointing outthat the HNN parameters are kept constant during theentire simulation test case.

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 34 Volume 8, 2017

Page 9: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

Figure 6: Standard HNN. Departure mission, Phase1: from tractor deposit to departing aircraft parkinglot. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.

Figure 7: Standard HNN. Departure mission, Phase 2:from departing aircraft parking lot to runway thresh-old. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.

Figure 8: Standard HNN. Departure mission, Phase3: from runway threshold to tractor deposit. Cred-its: Pictures 2015 DigitalGlobe, Map data c©2015Google.

4.4 Test case results using modified HNNThe same test case is solved with the modified HNNalgorithms. For this application, a 700× 700 neuronsnet has been created and dynamic obstacles are usedto prevent convergence through unpermitted direction.This is a programming expedient to overtake the limi-tation of using a local connectivity matrix to speed up

Figure 9: Standard HNN. Arrival Mission: Phase 1,from tractor deposit to aircraft landing waiting posi-tion. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.

Figure 10: Standard HNN. Arrival Mission: Phase2, from aircraft landing waiting position to parkinglot. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.

Figure 11: Standard HNN. Arrival Mission: Phase3, from aircraft selected parking lot to tractor de-posit. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.

the solution.For this test case, the parameters are set as fol-

lows: the bias current for the target node is E = 100,while the time step is dt = 10−2. Results are shownin figures from Fig. 13 to Fig. 18. The same mis-sions considered for the previous algorithm are ana-lyzed and, for consistency, results are shown in thesame order as before.

It is worth pointing out the effectiveness of thevirtual dynamic obstacle, as the resulting path is al-

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 35 Volume 8, 2017

Page 10: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

Figure 12: ”Sandro Pertini” airport scheme for mod-ified Hopfield neural network application. Cred-its: Pictures 2015 DigitalGlobe, Map data c©2015Google.

Figure 13: Modified HNN. Departure mission, Phase1: from tractor deposit to departing aircraft parkinglot. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.

Figure 14: Modified HNN. Departure mission, Phase2: from departing aircraft parking lot to runwaythreshold. Credits: Pictures 2015 DigitalGlobe, Mapdata c©2015 Google.

ways the shortest path, Fig. 15 and Fig. 18. However,because of the higher number of checkpoints in theairport discretization, as shown in Fig. 12, the com-putational time increases with respect to the standardHopfield Neural Network.

4.5 Test case results using graph theorybased algorithms

For these test cases, the same spatial domain dis-cretization used for the standard HNN is employed(Fig. 1). For consistency purpose, the same path op-

Figure 15: Modified HNN. Departure mission, Phase3: from runway threshold to tractor deposit. Cred-its: Pictures 2015 DigitalGlobe, Map data c©2015Google.

Figure 16: Modified HNN. Arrival Mission: Phase 1,from moving tractor to aircraft landing waiting posi-tion. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.

Figure 17: Modified HNN. Arrival Mission: Phase2, from aircraft landing waiting position to parkinglot. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.

timizations are performed by means of the Dijkstra’sand the A* methods. In this cases, the optimal pathscomputed by the two algorithms is identical. Resultsare reported from Fig. 19 to Fig. 24.

4.6 Results comparisonThe result analysis suggests that the final optimizedsolutions, computed by the four implemented algo-rithms, slightly differ, as shown in Fig. 15 and Fig.21. This might be caused by the different domaindiscretization employed. However, the length of thepaths are very similar as shown in Table 1 and Table

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 36 Volume 8, 2017

Page 11: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

Figure 18: Modified HNN. Arrival Mission: Phase3, from aircraft selected parking lot to tractor de-posit. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.1

Figure 19: Algorithm 3. Departure mission, Phase1: from tractor deposit to departing aircraft parkinglot. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.

Figure 20: Algorithm 3. Departure mission, Phase 2:from departing aircraft parking lot to runway thresh-old. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.

2, for the two missions respectively.A substantial difference between the implemented al-gorithms arises when considering the computationaltime required to generate the optimal shortest path.

Figure 21: Algorithm 3. Departure mission, Phase3: from runway threshold to tractor deposit. Cred-its: Pictures 2015 DigitalGlobe, Map data c©2015Google.

Figure 22: Algorithm 3. Arrival Mission: Phase 1,from moving tractor to aircraft landing waiting posi-tion. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.

Figure 23: Algorithm 3. Arrival Mission: Phase2, from aircraft landing waiting position to parkinglot. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.

The code was executed on a Windows 8.1 Pro plat-form supported by an Intel Core i7-4810MQ CPU and8 GB RAM. Table 3 reports the required computa-tional time for each algorithm for both test cases. Itis clear that the computational time required by thegraph theory-based algorithms is some order of mag-nitude smaller than the one required by the two neuralnetworks. In particular, the modified HNN is the slow-est algorithm, because of the huge amount of nodes(neurons) required for the proposed application, espe-cially during the first phase of the computation, whenthe target activation must propagate to the initial tugposition so that it starts virtually moving.

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 37 Volume 8, 2017

Page 12: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

Table 1: Optimal trajectories length comparison for the Departure mission.

Algorithm Phase1 [m] Phase2 [m] Phase3 [m] Total length [m]

HNN 1097.20 1442.50 1342.60 3882.30mHNN 1071.90 1407.50 1376.10 3855.50Dijkstra 1097.20 1442.50 1342.60 3882.30

A* 1097.20 1442.50 1342.60 3882.30

Table 2: Optimal trajectories length comparison for the Arrival Mission.

Algorithm Phase1 [m] Phase2 [m] Phase3 [m] Total length [m]

HNN 1106.00 1619.50 455.38 3180.88mHNN 1126.40 1570.00 526.05 3222.45Dijkstra 1106.00 1619.50 455.38 3180.88

A* 1106.00 1619.50 455.38 3180.88

Figure 24: Algorithm 3. Arrival Mission: Phase3, from aircraft selected parking lot to tractor de-posit. Credits: Pictures 2015 DigitalGlobe, Map datac©2015 Google.

Table 3: Computational time comparison for bothmissions.

Algorithm Departure [s] Arrival [s]

HNN 705.01 767.83mHNN 1839.66 1272.93Dijkstra 0.01 0.01

A* 0.01 0.01

5 ConclusionThis paper presents a software solution for a routeselection problem applied to airport environment forthe path planning of innovative and automatic aircrafttugs, responding to the need of engine-off taxi in thenext airport generation. Four different algorithms,

based on artificial intelligence and graph theory, havebeen implemented and their performance compared.The developed software works with any airport andis able to properly discretize the spatial domain (e.g.taxiways, runways and aircraft parking lots) in func-tion of the employed algorithm. To solve the problem,an entire engine-off towing operation is called mis-sion and is divided into three sub-operations, calledmission phases. There are two types of mission, de-pending whether the aircraft to be towed is arriving ordeparting, whereas the phases sequence is the sameand in the following order: reach the targeted air-craft, perform the engine-off taxi towing and return tothe tug parking area. In detail, a standard Hopfieldneural network and a modified version, which con-siders a local connectivity of neurons, based on har-monic functions, a Dijkstra and a A* algorithms havebeen employed. The algorithms are conceptually dif-ferent, with their own pros and cons. In particular,the standard HNN and the two graph theory based al-gorithms minimize the entire path in once, while themodified HNN works locally, in a small neighborhoodof checkpoints, allowing for dynamic obstacles avoid-ance (i.e. moving tugs, airplanes and foreign objectsalong the path).A unique test case, referred to the real data of theSandro Pertini airport of Turin, has been performedfor each algorithm for comparison purposes. The re-sults demonstrate that all the algorithms converge to aunique shortest path, exception done for the modifiedHNN, which result in a slightly longer route. In addi-tion, the two graph theory based algorithms are severalorder of magnitude more efficient, requiring an almostnegligible computational time, making them more at-tractive for a possible real-time application.

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 38 Volume 8, 2017

Page 13: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

A Airport Discretization Tool

Figure 25: Airport Discretization Graphical User In-terface. Credits: Pictures 2015 DigitalGlobe, Mapdata c©2015 Google.

Acknowledgements: Authors would like to thankProf. Giovanni Squillero, from the Politecnico diTorino, for his advising during the implementation ofthe presented route selection algorithms.

References:

[1] Bondy A.J. and Murty U.S.R. Graph Theorywith Applications.

[2] Goldberg A.V. and Tarjan R.E. Expected per-formance of dijkstra’s shortest path algorithm.Technical report, NEC RESEARCH INSTI-TUTE REPORT, 1996.

[3] Bonet B. and Geffner H. Planning as heuristicsearch. Artificial Intelligence, 129(12):5 – 33,2001.

[4] Hilburn B. Head down time in aerodrome oper-ations: a scope study. 2004.

[5] M. Battipede, A. Della Corte, M. Vazzola, andD. Tancredi. Innovative airplane ground han-dling system for green operations. In 27th Inter-national Congress Of The Aeronautical SciencesICAS, 2010.

[6] Baker B.M. and Ayechew M.A. A genetic algo-rithm for the vehicle routing problem. Comput-ers and Operations Research, 30(5):787–800,2003.

[7] Lesire C. An iterative a* algorithm for planningof airport ground movements. In Proceedings ofthe 2010 Conference on ECAI 2010: 19th Euro-pean Conference on Artificial Intelligence, pages413–418, 2010.

[8] Dijkstra E.W. A note on two problems in con-nexion with graphs. Numerische Mathematik,1(1):269–271, 1959.

[9] S. Haykin. Neural Networks: A ComprehensiveFoundation. Prentice Hall PTR, Upper SaddleRiver, NJ, USA, 2nd edition, 1998.

[10] ICAO. Manual on the prevention of runway in-cursions. Technical Report Doc 9870 AN/463,International Civil Aviation Organization, 2007.

[11] Hopfield J.J. Neural networks and physicalsystems with emergent collective computationalabilities. Proceedings of the National Academyof Sciences, 79(8):2554–2558, 1982.

[12] Hopfield J.J. and Tank D.W. Neural computationof decisions in optimization problems. Biologi-cal Cybernetics, 52(3):141–152, 1985.

[13] Hopfield J.J. and Tank D.W. Computingwith neural circuits: a model. Science,233(4764):625–633, 1986.

[14] J.Y. Kim, Aktay K., Aktay K., and Ropp T.D.Ants-automated nextgen taxi system. FAA De-sign Competition 2009-2010, 2010.

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 39 Volume 8, 2017

Page 14: A Route Selection Problem Applied to Auto-Piloted Aircraft ... · aircraft pilot through the aircraft steering system [15]. This control setup allows to avoid regulations’ limi-tations

[15] Lufthansa. Innovative taxibot now used in realflight operations, 2015.

[16] Gendreau M., Guertin F., J.Y. Potvin, and Tail-lard . Parallel tabu search for real-time vehi-cle routing and dispatching. Transportation Sci-ence, 33(4):381–390, 1999.

[17] Xu M.H., Liu Y.Q., Huang Q.L., Zhang Y.X.,and Luan G.F. An improved dijkstras short-est path algorithm for sparse network. AppliedMathematics and Computation, 185(1):247 –254, 2007.

[18] Ali M.K.M and Kamoun F. Neural networks forshortest path computation and routing in com-puter networks. Neural Networks, IEEE Trans-actions on, 4(6):941–954, Nov 1993.

[19] Christofides N. Graph Theory: An Algorith-mic Approach. Computer Science and AppliedMathematics.

[20] Kojic N., Reljin I., and Reljin B. Route selec-tion problem based on hopfield neural network.Radioengineering, 22(4):1182–1193, 2013.

[21] Wasserman P.D. Advanced Methods in NeuralComputing. John Wiley & Sons, Inc., New York,NY, USA, 1st edition, 1993.

[22] Hart P.E., Nilsson N.J., and Raphael B. A for-mal basis for the heuristic determination of min-imum cost paths. Systems Science and Cybernet-ics, IEEE Transactions on, 4(2):100–107, July1968.

[23] S.A. Rahman, M.S. Ansari, A.A. Moinuddin,and et al. Solution of linear programming prob-lems using a neural network with non-linearfeedback. Radioengineering, 21(4):1171, 2012.

[24] Khebbache-Hadji S., Prins C., Yalaoui A., andReghioui M. Heuristics and memetic algorithmfor the two-dimensional loading capacitated ve-hicle routing problem with time windows. Cen-tral European Journal of Operations Research,21(2):307–336, 2013.

[25] Mitrovi-Mini S., Krishnamurti R., and LaporteG. Double-horizon based heuristics for the dy-namic pickup and delivery problem with timewindows. Transportation Research Part B:Methodological, 38(8):669 – 685, 2004.

[26] Zeng W. and Church R.L. Finding shortest pathson real road networks: The case for a*. Int. J.Geogr. Inf. Sci., 23(4):531–543, April 2009.

[27] Zhong Y., Shirinzadeh B., and Tian Y. A newneural network for robot path planning. InAdvanced Intelligent Mechatronics, 2008. AIM2008. IEEE/ASME International Conference on,pages 1361–1366, July 2008.

WSEAS TRANSACTIONS on ELECTRONICSGiuseppe Sirigu, Mario Cassaro,

Manuela Battipede, Piero Gili

E-ISSN: 2415-1513 40 Volume 8, 2017