Article citation information:
Żuchowska,
D., Stelmach, A. Modeling a negotiation process between aircraft using Petri
Nets. Scientific Journal of Silesian
University of Technology. Series Transport. 2023, 121, 267-285. ISSN: 0209-3324. DOI: https://doi.org/10.20858/sjsutst.2023.121.17.
Daria
ŻUCHOWSKA[1], Anna STELMACH[2]
MODELING A NEGOTIATION PROCESS BETWEEN AIRCRAFT USING PETRI NETS
Summary. New air
traffic control ideas are sought. Many studies point out the delegation of the
responsibility for ensuring separation from air traffic controllers to the
aircraft crews, but it should be assumed that the transition from centralized
to decentralized air traffic control will occur in stages. It is, therefore,
necessary to ensure effective communication between conflicting aircraft and to
define the negotiation process between aircraft. The concept of the process of
negotiation and communication between aircraft in conflict using a monotonic
concession protocol is presented. The proposed solution was modeled using a
Petri Net, which allowed us to analyze all the dependencies present in the
system. The analysis allowed us to evaluate the method in the context of
safety. The conducted research showed that, under the assumed conditions, the
negotiation method allows obtaining the desired effect of negotiations while
maintaining an adequate level of safety.
Keywords: air
traffic control, ICT systems, airborne separation assurance system, Petri Nets,
transportation systems
1. INTRODUCTION
The
primary function of air traffic control is to ensure and maintain minimum
separation between aircraft in such a manner as to ensure an adequate safety
level as well as the flow of air traffic. Currently, the responsibility for
ensuring separation lies with air traffic controllers (ATCOs), who maintain
voice communication with aircraft crews and provide traffic information based
on data gained from surveillance systems. Each ATCO works
in a designated airspace block. The capacity of a sector depends
on the individual air traffic controller's ability to process data on the
aircraft in his sector at any given time. As the number of aircraft in an
airspace block increases, its throughput decreases due to more data being
processed by ATCO [1].
Air
traffic is increasing all the time, despite its drastic decline in 2020 and
2021 due to the global COVID-19 pandemic. As air traffic increases, so does the
likelihood of conflicts between aircraft, which results in an increased air
traffic controller workload. As a result, new methods of air traffic
control are being sought. One idea is to delegate the responsibility for
ensuring separation between aircraft from the air traffic controller to the
aircraft crews, as presented in the work [2-6]. The first aspect that is
taken into consideration when creating such a concept is to ensure an
adequate level of safety. Therefore, the first ideas of the concept
of delegating air traffic control to aircrews focused on creating a new
concept of air traffic control in a completely separated airspace [7-9].
Most of
the work assumed complete preparation of the system for flight operations
in accordance with the ASAS concept (Airborne Separation Assurance
System). However, taking into account the technical constraints resulting from
the structure of the information network, it should be assumed that the
transition from a centralized air traffic control system
to a decentralized air traffic control system will occur in stages.
The main element is to transform the information network and move from a star
architecture to a point-to-point architecture. The star architecture is
characterized by the presence of a hub (which is the air traffic controller),
to which the nodes (aircraft) are connected. The undeniable disadvantage
of this architecture is that the information flow is blocked when the hub
fails. A distributed system consists of a set of independent technical
devices that form a single, coherently logical whole. The system is viewed as a
set of elements that communicate with each other. In a distributed
network, there may be one main system cooperating with the remaining elements;
nevertheless, it should be remembered that each of the elements may operate
independently of the main system. The undeniable advantage of this system is
that the workload is distributed among the individual elements. Moreover, the
system is scalable, and many of its processes are concurrent [10].
The
phase of transition from a star to a point-to-point architecture requires the
provision of appropriate communication methods to avoid hazardous
situations resulting from erroneous data processing or no data at all.
The
delegation of responsibility for ensuring separation between aircraft to
aircrews involves the need to increase situational awareness, thus equipping
aircraft with systems that would provide that awareness. The purpose of these
systems is to detect conflicts between aircraft and, under appropriate
conditions, also to resolve them. In the case of last resort systems, such
as TCAS, conflict resolution consists of a command issued by TCAS to which
pilots must absolutely comply. But if a sufficiently long time horizon is
specified (greater than in last resort systems), it may be possible to use a
conflict resolution negotiation process, considering the preferences of the
conflicting parties. Therefore, this paper focuses
on the communication and negotiation processes between a pair of
conflicting aircraft.
An
example of the integration of two types of traffic currently occurring in air
traffic is the integration of manned traffic and Unmanned Aerial Vehicles
(UAV’s) traffic, which is increasingly used for various
applications, such as precision agriculture applications [11], various types of
inspection (such as building inspection or bridge inspections) [12],
or services for the aviation industry, i.e., flight inspection of ILS
(Instrumental Landing System) [13] or runway pavement inspection [14].
Integrating these two types of traffic is a huge challenge for the current and
future air traffic management systems, as the growth of airspace density is
unknown, especially for low-level flights [15-16]. It also means
a significant increase in the flow of information, which, if not used and
processed properly, will lead to inefficient and unsafe flight operations
[17].
UAVs
can operate autonomously or be controlled by a pilot using an advanced remote
control system. For autonomous or semi-autonomous flights, operations are based
on onboard sensors, including vision and ultrasound, control signals, and
positioning systems. The algorithms used, often using artificial
intelligence, make it possible to detect conflict situations based on the
signals received. The operation of these aircraft at low altitudes poses
a number of problems and risks in both uncontrolled and controlled
airspace. The air transportation system is becoming more complex. In order for
this system to operate efficiently, it is necessary to provide innovative, multifaceted,
and multidimensional air traffic management while maintaining at least the
current level of safety. Currently, in most cases, there is a dedicated system
that enables electronic coordination of UAV flights and digitally manages
requests and approvals for flights in the airspace (as permission to fly an
unmanned aircraft in the airspace is required in specific cases). The goal of
such a system is to reduce the workload of air traffic services while preparing
for the expected increase in UAV operations in the future. These measures are
aimed at safely and efficiently integrating the two types of traffic [18-20].
It is worth looking at such solutions, which can be a starting point
for integrating two types of traffic in manned aviation.
Some research was
conducted to investigate that issue. The main problem was determining how to
avoid conflicts between two types of air traffic. As stated in the paper [21]
there are three main maneuvers to perform to avoid conflict: horizontal,
vertical, and change in speed. The paper [22] analyzes loss-of separation
scenarios when an UAV enters conflict with an aircraft at the same altitude. A
set of pre-planned separation maneuvers is proposed that aim to improve the
situational awareness of both the air traffic controller and UA pilot –
in – command. In a paper [23] a
horizontal detect and avoid algorithm for Unmanned Aerial Vehicles (UAVs)
flying in the lower airspace was tested to check the ability of such
an algorithm to ensure the separation with commercial aviation. Most of
the papers propose using horizontal maneuvers to avoid conflict
between UAV and conventional aircraft. The main reason is that most of the
UAV’s has much worse flight performances than conventional aircraft,
according to the vertical maneuvers.
The paper is organized as follows: chapter one
presents the background of the research conducted; chapter two discusses the
assumptions made about the traffic rules in the transition period and discusses
the communication and negotiation process; chapter three discusses the model of
mixed air traffic in the analyzed airspace block; chapter four discusses the
conducted experiment and its results; and finally, chapter five contains the
summary
2. AIRCRAFT RULES AND NEGOTIATION PROCESS
BETWEEN AIRCRAFT IN THE ANALYZED AIRSPACE BLOCK DURING THE TRANSITION PERIOD
2.1. Integration of two types of air
traffic
In this paper, mixed air traffic in
one airspace block is analyzed. That means that there are two types of air
traffic in one airspace block. The first of them, called centrally controlled
traffic (hereinafter referred to as NON-ASAS aircraft), is the air traffic
managed by the Air Traffic Controller (ATCO). The second one, called
distributed air traffic, is all aircraft flying according to the ASAS concept
(hereinafter referred to as ASAS aircraft). In that concept, in most cases,
aircraft flies directly from the point of entry to the exit point in a given
airspace.
The integration of two types of air
traffic is possible based on access to traffic situation data. There are three
possible ways to integrate the air traffic into one airspace block:
1. ASAS aircraft does not see
NON-ASAS aircraft (which means do not identify that kind of air traffic).
NON-ASAS aircraft does not ASAS, but can be seen by ATCO. This solution forces
the controller to ensure separation between all aircraft, which increases his
workload, thereby reducing airspace capacity.
2. ASAS aircraft does not see
NON-ASAS aircraft. NON-ASAS aircraft does not have ASAS, but there is an
external entity that controls all air traffic and is responsible for ensuring
separation between aircraft. This solution is similar to that described in the
previous section.
3. ASAS aircraft does see
NON-ASAS aircraft, because it transmits their position and velocity data. But
NON_ASAS aircraft do not receive data from other aircraft so ASAS aircraft can
not be identified by NON-ASAS aircraft. Therefore, the ASAS aircraft can ensure
their own separation from centralized air traffic. So, the aircraft crew of
ASAS aircraft is responsible for detecting a conflict situation and
initiating the negotiation process. A diagram of the air traffic organization
is shown in Figure 1.
Fig. 1. Negotiation process scheme
in the transition period
(source: own elaboration)
The
assumptions defined above require clear air traffic rules that allow for an
unambiguous resolution of conflicts. It was assumed that the current rules of
separation assurance would be maintained during the transition period. This
means that a safety buffer in the shape of a cylinder with a radius of 5
nautical miles and a height of 1000 feet has been set around the aircraft. Loss
of separation occurs when the aircraft safety zones intersect. The solution to
the conflict is to perform one or a sequence of evasive maneuvers, which
include altitude change, heading change, and speed change. If the
responsibility for ensuring separation between aircraft is delegated to
aircraft crews, which are supported by appropriate technical systems, the
technical limitations of the operation of these systems (range of operation)
must be taken into account. Therefore, tactical planning must be implemented
here. Therefore, a time horizon of 5 minutes was adopted for the analysis.
Since the assumed time horizon is quite short, it is necessary to assume the
execution of evasive maneuvers in pairs to speed up the conflict resolution
process.
2.2. Negotiation process between
aircraft
Negotiation
is a sophisticated communication process involving two or more parties with partially
divergent interests. These parties seek to reach a solution that satisfies each
of them. In the literature [24], two main types of negotiation strategies can
be found: non-cooperative and cooperative. In the first one, agents have
conflicting interests, so they act independently, trying to urge each other to
make concessions. An agreement is concluded when the agents’ goals
converge and reach a mutually acceptable value [24]. Cooperative negotiation
involves parties collaborating to jointly meet each other's needs and satisfy
their interests.
As
mentioned before, it is up to the ASAS aircraft crew to detect a conflict
situation and initiate the process of resolving it. It is also assumed that the
resolution of conflict situations will be supported by tools that search for
optimal solutions to an incident. In addition, for the effective resolution of
the situation, adequate communication between the negotiating parties is
required in order to conduct negotiations between stakeholders. These assumptions
will allow the creation of tools to support the work of both the air traffic
controller and the aircraft crew in the process of ensuring separation during
the transition period.
As
mentioned before, conflict resolution is done in pairs, so the Monotonic
Concession Protocol (MCP) described in [25-27] is implemented to select a
solution to the conflict. This protocol is dedicated to the negotiation between
two agents. Let set:
A={Ai, Aj }
– set of two agents
X – a finite set of
proposals for resolving conflict
Each
agent belonging to set A has a certain utility function defined as:
ui: X→
Negotiations
take place in rounds. For the purpose of this paper, it was determined to be
5 rounds. In each round, each agent simultaneously submits his proposal
from set X. In each subsequent round, the proposal cannot be worse than the one
proposed previously. Both agents can accept the proposal, but also propose a
solution that is more preferred by the other agent. Each agent can also reject
the other's proposal and stay with his own. Agreement (and thus the resolution
of the conflict situation) is reached when one agent makes a proposal that his
opponent rates at least as highly as his own current proposal, which can be
written as:
|
|
(1) |
It is
assumed that a solution proposal consists of two elements: an evasion maneuver
for the agent making the proposal and an evasion maneuver for the other agent.
If both negotiating parties agree that the proposals are equally good and
neither of them can be chosen unambiguously (or neither of them is good), then
they proceed to the next round of negotiations. If it is the last round of
negotiation, then the solution is chosen based on the parameter Zi
defined as the risk willingness of agent i, as shown in equation (2). The agent
who has the smaller value of the parameter Z should concede. If these values
are equal, the conflict remains unresolved.
|
|
(2) |
where:
ui (xi)
– the utility function of agent i
at its proposal xi
ui (xj)
– the utility function of agent i
at agent j's proposal xj
It has
been assumed that the utility function will reflect the efficiency of the
traveled route, which boils down to an analysis of the distance traveled and a
comparison with the original plan. The goal is to modify the route as little as
possible. In the case of a flight level change, the goal is to make as few
altitude change maneuvers as possible. Therefore, the utility function can be
written as the formula (3) states:
|
|
(3) |
where:
Tp – total
distance flown according to the original flight plan
Tz – total
distance flown after trajectory modification
HZ –
total flight level change.
During
the negotiation in selecting a solution, it is aimed that the trajectory
modification is no more than 15% of the original plan.
2.3. Communication process between aircraft
The
process of communication involves the exchange of information between
a sender and receiver through a specific channel and means of communication.
This paper proposes the automation of communication processes, which is greatly
accelerated by the progressive standardization of data scope and format.
Unambiguous interpretation of information is important for effective
negotiation. Messages between negotiators were assumed to be sent as shown in
Table 1, which was created based on the negotiation algorithm presented in
Figure 2. Since the form of the table results from the algorithm shown in
Figure 2, the following description applies to both the figure and the table.
AC is the aircraft that suggests a solution. There are two aircraft
participating in the conflict, which are AC1 and AC2. An evasion maneuver is a
maneuver for a specific Aircraft suggested by the other one being in conflict,
i.e., in the row AC1 evasion maneuver for AC1 is the maneuver suggested by
itself to execute to avoid the conflict. The evasion maneuver for AC2 is a
maneuver suggested by AC1 to be executed by AC2 to avoid conflict. U is the
utility function for a given solution calculated in accordance with the formula
(3), i.e., U1(1) is the utility function for the solution suggested
by AC1 to itself, and U2(1) is the utility function calculated based
on the solution suggested by AC1 to be executed by AC2 to avoid conflict. Based
on the utility function, the resolution can be selected in accordance with the
formula (1) and AC1 is notified about that in the column Resolution (based on Ui).
If there is no solution in this round, and it is not the last round,
proceed to the next round, which is included in column Resolution (based on the
negotiation algorithm). If it is the last round and no solution can be selected
based on the utility function, the Zi parameter should be calculated
(in column Zi) in accordance with the formula (2). Based on the
Zi parameter, a solution is selected in the last round.
Tab. 1
Negotiation message template
(source: own elaboration)
|
AC |
Resolution |
Ui |
Resolution (based
on Ui) |
Resolution
(based on negotiation algorithm) |
Z |
Resolution (based on Zi) |
|
AC1 |
Evasion
maneuver for AC1 |
U1(1) |
Select/reject
the proposal from AC1/AC2 |
Select a proposal from AC1/AC2 or next round or Set a
risk willingness (Zi) |
Z1 |
AC1/AC2 or Conflict |
|
Evasion
maneuver for AC2 |
U2(1) |
|||||
|
AC2 |
Evasion
maneuver for AC1 |
U1(2) |
Select/reject
the proposal from AC1/AC2 |
Z2 |
||
|
Evasion
maneuver for AC2 |
U2(2) |
3. THE MODEL OF AIR TRAFFIC IN THE
AREA CONTROL AIRSPACE BLOCK
3.1. Modelling tool
Petri
Nets were chosen to model the proposed solution. Petri nets are usually used to
model data processing systems with concurrent events and processes [28]. Petri
nets provide a graphical representation of the system structure as a
bipartite-directed graph. The graph of Petri Nets itself consists of three
types of elements: places, representing system states, shown graphically as a
circle; transitions, representing actions occurring in the system, shown
as rectangles; and arcs, showing the flow of actions in the network.
Tokens are used to indicate the state of the system and are stored in various
places. A change in the state of the system occurs when a transition is fired,
which causes the tokens to move from the input places of the transition to the
output places of the fired transition.
Hierarchical
timed colored Petri Nets have been used to model aircraft traffic [29].
Building complex systems involves the creation of an elaborate net consisting
of many elements [30]. To make the net transparent, it is possible to use a
hierarchical structure where the different modules of the model, called pages,
are modeled separately and then synchronized to the model using either fused
places or substituted transitions.
Fused
places are places labeled in the left-bottom corner. Fused places marked with
identical labels are identical. Substituted transitions are marked with a
double-line frame. A substituted transition can represent an entire piece of a
net structure.
Fig. 2. Negotiation process
algorithm
(source: own elaboration)
Distinguishability
of data types is provided by the ability to define different token types. These
correspond to the data types that exist in programming languages. The name
"colored" comes from the fact that each place in the network is
assigned a color, which determines what type of data can be stored in that
place. Tokens can either, in a similar concept, denote traffic participants or
represent specific values such as coordinates or aircraft speed. Token flow
rules specify expressions that describe arcs and transitions, which contain
information about which tokens can be moved to the next location and what
conditions must be met to move tokens.
The
dynamics of actions in the network can be represented by the use of timed Petri
Nets, in which it is possible to apply time constraints to the flow of
individual tokens, meaning that a given state can occur at a point in time
specified in the token.
An
example of the use of Petri Nets in air traffic modeling can be found in
[31-33], among others.
The
presented solution is shown using Petri Nets using CPN Tools software [28-30,
34].
3.2. Petri Net for the model of mixed air
traffic
The
model of mixed air traffic MS
presented in this paper can be written as the formula (4), which is:
|
|
(4) |
where:
P – the finite nonempty set of places,
T – the finite nonempty set of transitions,
A – the set of arcs of the network,
I, O – the functions describing respectively the
inputs and outputs of the network. These functions are defined for a given
transition
M0: P→Z+×R
– initial marking such that
τ:T×P→R+ -
delay function, delay function, which determines the static delay τ(t) of a transition t carrying token to the place p.
F – nonempty,
finite set of colors, each of which is a nonempty set.
C – function
determining what color of tokens can be stored in a given place, C: P→F,
G – unction
defining the conditions that must be satisfied for the transition before it can
be fired; these are the expressions containing variables belonging to Γ,
for which the evaluation can be made, giving, as a result, a Boolean value. It
is described as:
where:
E
– function describing the so-called weights of arcs, i.e. expressions
containing variables of types belonging to Γ for which the evaluation can
be made, giving as a result, a multiset over the type of color assigned to
a place that is at the beginning or the end of the arc. It is described as:
where:
S – set of
timestamps (also called time points)
where:
r0
–initial time, r∈ R.
3.3. Network structure
The
network shown has a hierarchical structure with the main network (called a
page) and four subnetworks (called subpages), as shown in Figure 2. All
subnetworks are synchronized with the main network using fusion points. The
InitA and InitB subpages generate information about the initial state of the
aircraft; that is, they contain information about aircraft coordinates, speed,
heading, and flight mode (ASAS or NON-ASAS). The page called Main network analyzes the traffic
geometry between the two aircraft, that is, the distance between the aircraft
and the time to conflict, if any. If there is a conflict, solutions are
generated in the Search Reso subpage,
based on which negotiations are conducted in the Select Reso subpage. The Select
Reso subpage will be discussed in detail later in this paper.
Fig. 3. The structure of a modelled
network
(source: own elaboration)
3.4. Select Reso Subpage
In the
Select Reso subpage, the process of selecting a solution to the conflict from
the solutions list (generated in the Search Reso subpage) is modeled. Each
agent randomly selects a set of solutions, which are included in the transition
code segment, meaning respectively:
· PropAA
– Aircraft A's proposal to perform a maneuver by Aircraft A;
· PropBA
– Aircraft A's proposal to perform a maneuver by Aircraft B;
· PropAB
– Aircraft B's proposal to perform a maneuver by Aircraft A;
· PropBB
– Aircraft B's proposal to perform a maneuver by Aircraft B.
Based
on this selection, the utility function U for each solution is calculated and
the information about them is stored in the places UAA, UBA, UAB, and UBB
(designations analogous to those mentioned above). Considering the analysis of
the proposed solution under the disturbance conditions resulting from the
lengthening of the negotiation time, timestamps have been added on the arcs
between the transitions selecting the solution proposal and the places storing
information about the utility function for the selected proposal. The timestamp
has a notation of the form @+ranstn(), where "@" is the timestamp
designation and ranstn() is a function that selects a random value from a given
range denoting the time to select a given proposal. The values for the given
ranges were chosen arbitrarily based on [1-2]. In the Check UA and Check UB
transitions, a comparison of the utility functions (according to formula 1)
takes place, based on which a solution selection is made. If it is not possible
to select a solution based on the utility function, the GotoZ transition should
be used to check in which round the negotiation is taking place. If it is the
last round, the parameter Z should be calculated, which is done in the Calc Z
transition. Based on it, a solution should be selected, which is done in the ZR
SOL transition. The NRAF place stores the information that the negotiation
failed to resolve the conflict situation.
The
structure of the Select Reso subpage is shown in Figure 3. Some of the arcs
have been given colors to help identify the condition assigned to that
particular arc.
Fig. 4. Select Reso Subpage
(source: own elaboration)
4. SIMULATION EXPERIMENTS WITH THE
MODEL
4.1. Assumptions
The following assumptions
were made:
· The aircraft are considered as moving mass points, thus the
aerodynamic characteristics of the aircraft are not taken into account when
performing maneuvers;
· The aircraft are moving at the same altitude;
· Only two aircraft are involved in the analysis, the movement
of other aircraft is not taken into account;
· The initial positions of the aircraft, their speeds, and
heading are known;
· The speed of the aircraft is constant throughout the
simulation.
4.1. Test scenario
Experiments were conducted
based on four test scenarios:
1.
Scenario 1, in which
nominal conditions are considered, that is, the collision situation is detected
within the predefined time horizon (5 minutes), and the solution is selected in
no more than 180 seconds. The time to select a final solution depends on the
time to select a solution proposal, which is done in the transitions PropAA,
PropAB, PropBA, and PropBB. In scenario 1, an averaged value of the proposal
selection time was determined, which is a random variable with a normal
distribution N (14, 1). This value will be added as a time stamp for tokens
appearing after the above-mentioned transitions.
2.
Scenario 2, in which the
collision situation is detected within the predefined time horizon
(5 minutes) and the solution is selected in no more than 180 seconds. The
time to select a final solution depends on the time to select a solution
proposal, which is done in the transitions PropAA, PropAB, PropBA, and PropBB.
There are disturbances in the solution proposal selection stage that may
increase the proposed solution selection time. Keeping the above in mind,
scenario 2 is set to average the proposal selection time, which is a random
variable with a normal distribution N (17, 3) and will only be active for one
of the conflict parties.
3.
Scenario 3 has the same
conditions as Scenario 1, except that the time horizon for the detected
situations is reduced by one minute, which is equivalent to 60 seconds less
time to solve the collision situation.
4.
Scenario 4 has the same
conditions as Scenario 2, but the time horizon for the detected situations is
shortened by one minute, which is equivalent to the time to solve the collision
situation being shorter by 60 seconds.
The results of the
experiment will allow evaluating the proposed method in terms of safety, which
is defined in terms of the number of conflicts occurring, and the total time
spent in a conflict situation.
The time in conflict of
an aircraft is defined as the time measured from the detection of a
conflict situation to the selection of a solution in the negotiation process.
On the basis of this measurement, in a further step, the parameter Tconfl, which shows what
percentage of the time the operations are performed is time spent in conflict,
is written as formula (5):
|
|
(5) |
where:
n – number of aircafts
th– time horizon
Based on the Tconfl the safety and
efficiency of the proposed solution are evaluated. The value of the parameter
is in the range Tconfl ∈[0,1].
The higher the value of the parameter Tconfl,
the more effective the solution, since this score indicates a short dwell time
in a conflict situation, which also converts into the safety level of the
solution. Therefore, it is natural to conclude that a low value of the
parameter indicates an inefficient solution, which forces the agents to perform
sudden evasive maneuvers, which affect, among other things, the comfort of the
travelers. In addition, it should be remembered that with time, the distance
between aircraft decreases, which significantly reduces the level of safety of
the operation.
The experiment also
analyzed the efficiency of the negotiation process, which was defined using the
utility function assigned to the chosen solution. This evaluation made it
possible to determine to what extent the proposed solution was effective in the
context of the operations performed, that is, to what extent the negotiation
changed the route taken by the aircraft compared to the original route. The events
for which the solution was found were investigated, and it was analyzed how the
value of the change in course changed depending on when the maneuver was
started. In the next step, it was checked how the change in route was affected
by the moment of the start of the execution of the evasive maneuver. An
analysis was also carried out of the dependence of the speed at which the
aircraft is moving, the timing of the evasive maneuver, the angle of course
change, and the effect of these factors on the amount of course change.
5. EXPERIMENT RESULTS
The analysis of the
presented model was performed based on a simulation that was repeated 1000
times for each scenario. During the experiment, an analysis of the time that
aircraft are in conflict situations was performed, as shown in Table 2. Table 3
contains the information about the percentage of events with a loss of
separation among all events that occurred in the simulation.
Tab. 2
Time in conflict results
(source: own elaboration)
|
|
Scenario1 |
Scenario
2 |
Scenario
3 |
Scenario
4 |
|
|
0,853 |
0,797 |
0,817 |
0,744 |
Tab. 3
Events with a loss of separation in the
simulation performed
(source: own elaboration)
|
|
Scenario1 |
Scenario
2 |
Scenario
3 |
Scenario
4 |
|
Nlos [%]
|
7,1% |
11,3% |
14,9% |
22,1% |
It can
be seen that the performance of the proposed solution deteriorates depending on
the adopted scenario. In scenarios taking into account the occurrence of
disturbances, the negotiation process is naturally prolonged, so for the
conditions set in the scenarios, the parameter Tconfl has a smaller
value. This parameter takes the smallest value for the conditions set in
scenario 4, where the occurrence of interference is considered and the time
horizon for the event is reduced by 20%.
The
extended negotiation time resulting from the occurrence of interference affects
the distance at which the aircraft are located. With each successive second,
the distance decreases, so that the later the moment of selection and execution
of evasive maneuvers, the more dangerous and severe the event. The results
obtained are not without influence on the number of unresolved events, which
increases with each successive scenario. Unresolved events are those for which
no solution was found during negotiations or the negotiation process was so
long that the minimum separation between aircraft was violated.
The
obtained results were shown in Figure 4.
Fig. 5. Dependence of the Tconfl, Nlos, and Sev
values
(source: own elaboration)
As
mentioned above, an analysis was also carried out of the relationship between
the speed at which the aircraft is moving, the timing of the evasive maneuver,
the angle of route change, and the effect of these factors on the amount of
course change. The analysis was carried out for events in which a heading
change was chosen as the solution to the conflict. From the results obtained,
it can be seen that the later the maneuver started, the greater the angle of
heading change, as shown in Figure 5. It can also be noted that for higher
values of speed, the angle of heading change is smaller than for operations
performed at the same time but by aircraft moving at lower speeds. Figure 6
shows the relationship between the timing of the evasive maneuver and the total
amount of course change. The results are shown for operations performed at
different speeds. The analysis indicated that the later the maneuver was
performed, the greater the change in the length of the route taken. This change
is also greater the lower the speed of the aircraft. Given the assumption that
the route modification is to be no more than 15% of the original plan, it can
be concluded that the best time to start executing the evasive maneuver would
be the first 20 seconds of the solution implementation time. For higher speeds,
this action can be delayed by another 5 seconds.
Fig. 6. Dependence of the reroute angle on the time
when the evasive maneuver was executed and on the speed of the aircraft
(source: own elaboration)
Fig. 7. Dependence of the ratio of the route change to the
original pan on the time when the evasive maneuver was executed and on the
speed of the aircraft
(source: own elaboration)
5. CONCLUSIONS
This paper proposes a
process of communication and negotiation between aircraft in conflict during
the transition period. The most important element was to determine how to
integrate two types of air traffic, based on which it was possible to further
outline the rules of air traffic in the airspace and the rules of communication
between aircraft. An algorithm for resolving conflict situations was also
presented, including an algorithm for negotiating between traffic participants,
which are tools to support the work of both aircraft crews and the air traffic
controller.
The part of the air
traffic model in the air traffic control sector responsible for the process of
negotiation between aircraft is also presented. The model was created using hierarchically timed colored
Petri nets. A developed algorithm for resolving conflict situations was
implemented in the model. A series of
experiments was conducted based on four test scenarios - one scenario for
nominal conditions of operation execution and three scenarios to introduce
disturbances that affect the performance of the algorithm. The introduced
disturbances worsen the parameters for evaluating the method in the context of
the safety of the operations performed. This is related to the assumed time
horizon for event prediction, a reduction of which can lead to situations
in which a last resort solution must be applied. Nevertheless, the conducted
analysis showed that with the assumed evaluation criteria, the method is safe
in nominal conditions of operation.
It should be noted that
the developed model represents the resolution of conflict situations between
two agents, which gives us a local solution. The approach presented in this
paper to conflict resolution does not consider the implementation of the solution
or its impact on the traffic of other agents. The solution proposed in this
paper cannot manage multi-aircraft conflicts satisfactorily. Even more, it can
trigger a domino effect, which is characterized by creating a new
conflict situation by solving the current one. It is therefore necessary to
define a further direction of work, involving the search for methods to
generate solutions on a global scale. This entails research aimed at developing
new methods for multilateral negotiation that would allow stakeholders to
manage the conflict in a collaborative way.
References
1.
Dmochowski Piotr, Jacek Skorupski. 2017.
“Air Traffic Smoothness. A New Look at the Air Traffic Flow
Management”. Transportation
Research Procedia 28: 127-132. ISSN: 2352-1465.
2.
Beers Christopher, Hans Huisman. 2001.
“Transition between Free Flight and Managed Airspace”. In: Proceedings of 4th International Air Traffic
Management R&D Seminar. FAA/Eurocontrol,
Santa Fe, NM, USA. December 2001, Santa Fe, NM, USA.
3.
Chen Yu Fan, Miao Liu, Michael Everett,
Jonathan P. How. 2017. “Decentralized non-communicating multiagent
collision avoidance with deep reinforcement learning”. Robotics and Automation (ICRA): 285-292.
DOI: https://doi.org/10.1109/ICRA.2017.7989037.
4.
Endsley Mica, Richard Mogford, Kenneth
Allendoerfer, Michael Snyder and Earl Stein. 2002. “Effect of Free Flight
Conditions on Controller Performance, Workload and Situation Awareness”.
Tech. Report DOT/FAA?CT-TN97/12. Atlantic City.
5.
Goodchild Collin, Migueal Vilaplana,
Stefano Elefante. 2000. “Co-operative Optimal Airborne Separation
Assurance in Free Flight Airspace”. In: 3rd USA/Europe Air Traffic Management R&D Seminar. 13-16 June
2000. Napoli, Italy.
6.
Hoekstra Jacco Marco,
Rob Ruigrok, Ronald van Gent D. 2000. “Free Flight in a crowded
Airspace?”. Progress in
Astronautics and Aeronautics 193: 533-546.
7.
Yousefi Arash, George
Donohouse, Lance Sherry. 2004. “High-volume tube-shape sectors (HTS): A
network of high capacity ribbons connecting congested city pairs”. In: Proceedings
of the 23rd Digital Avionics Systems Conference (IEEE Cat. No 04CH37576): 594. Institute of Electrical and
Electeonic Engineers. 24-28 October 2004. Salt Lake City, UT, USA. ISBN: 9780780385399. DOI: https://doi.org/10.1109/DASC.2004.1391296.
8.
Hoffman Eric, Jean-Pierre
Nicolaon, Christian Pusch, Karmi Zeghal. 2001. “Limited Delegation of Separation Assurance to Aircraft: The Freer
Flight Evolutionary Air Ground Cooperative ATM Concepts”. In: New Concepts and Methods in Air Traffic
Management. Transportation Analysis. Edited by Luciano Bianco, Paolo
Dell’Olmo, Amadeo Odoni. Germany, Berlin, Heidelberg: Springer. ISBN:
978-3-642-07491-2.
9.
Hoffman
Eric, Karmi Zeghal,
Anne Cloerec, Isabelle Grimaud, Jean-Pierre Nicolaon. 2000. “Is limited delegation of
separation assurance promising?”. In: 3rd USA/Europe Air Traffic Management
R&D Seminar. 13-16 June 2000. Napoli, Italy.
10.
Kareem Tope, Karel Matthee, Anthony Chan,
Ntsibane Ntlatlapa. 2008. “Adaptive Priority Based Distributed Dynamic
Channel Assignment for Multi-radio Wireless Mesh Networks”. In: Ad-hoc,
Mobile and Wireless Networks. ADHOC-NOW: 321-332. Edited by
David Coudert, David Simplot_Ryl, Ivan Stojmenovic. Germany, Berlin, Heidelberg: Springer. ISBN: 978-3-540-85208-7.
11.
Tsouros Dimosthenis, Stamatia Bibi, Pangiotis Sarigiannidis. 2019. “A Review on UAV-Based
Applications for Precision Agriculture”. Information 10(11): 349. DOI:
https://doi.org/10.3390/info10110349.
12.
Ayele Yonas Zewdu, Mostafa Aliyari, David Griffiths, Enrique
Lopez Droguett. 2020. “Automatic
Crack Segmentation for UAV-Assisted Bridge Inspection”. Energies
13:
6250. DOI: https://doi.org/10.3390/en13236250.
13.
Liu
Xinqiao, Shihui Zheng. 2019. “Research on Flight Inspection Using
Unmanned Aircraft”. Journal of
Physics: Conference Series 1237(4): 042053. DOI: https://doi.org/10.1088/1742-6596/1237/4/042053.
14.
Tomić Lidija, Olja Cokorilo, Dragana Macura. 2020. „Runway Pavement Inspections
Using Drone -Safety Issues and Associated Risks”. International Journal for Traffic and Transport Engineering 10(3):
278-285. DOI: https://doi.org/10.7708/ijtte.2020.
20(3).01.
15.
Huttunen
Mikko. 2019. “The U-space Concept”. 2019. Air and Space Law 44(1): 69-89. DOI: https://doi.org/10.54648/AILA2019005.
16.
Xie
Yibing, Nichakorn Pongsakornsathien, Allesandro Gardi, Roberto Sabatini. 2021.
“Explanation of Machine-Learning Solution in Air-Traffic
Management”. Aerospace 8(8):
224. DOI: https://doi.org/10.3390/aerospace8080224.
17.
Kistan Trevor,
Allesandro Gardi, Roberto Sabatini, Subramanian Ramasamy, Eranga Batuwangala. 2017.
„An evolutionary outlook of air traffic flow management
techniques”. Progress in Aerospace
Sciences 88: 15-42. ISNN: 0376-0421. DOI: https://doi.org/10.1016/j.paerosci.2016.10.001.
18.
Pongsakornsathien Nichakorn, Suraj Bijjahalli, Allesandro Gardi,
Angus Symons, Yuting Xi, Roberto Sabatini, Trevor Kistan. 2020. “A
Performance-Based Airspace Model for Unmanned Aircraft Systems Traffic
Management”. Aerospace 7(11):
154. DOI: https://doi.org/10.3390/aerospace7110154.
19.
Barrado
Cristina, Mario Boyero, Luigi Brucculeri, Giancarlo Ferrara, Andrew Hately,
Peter Hullah, David Martin-Marrero, Enric Pastor, Anthony Peter Rushton,
Andreas Volkert. 2020. “U-Space Concept of Operations: A Key Enabler for
Opening Airspace to Emerging Low-Altitude Operations”. Aerospace 7(3): 24. DOI: https://doi.org/10.3390/aerospace7030024.
20.
Burnham
Colin. 2018. “U-Space & UTM for VLL (very low level operations):
review of EEA and USA approaches from concept to implementation of UAV
integration into existing operations”.
21.
Pérez Castán Javier Alberto, Alvaro
Rodriguez-Sanz, Victor Fernando Gomez Comendador, Rosa Maria Arnaldo
Valdés. 2019. “ATC
Separation Assurance for RPASs and Conventional Aircraft in En-Route
Airspace”. Safety 5(3): 41.
DOI: https://doi.org/10.3390/safety5030041.
22.
Pérez-Batlle
Marc, Enric Pastor, Xavier Prats. 2012. “Evaluation of
separation strategies for Unmanned Aerial Systems”. In: Proceedings of the 5th International
Congress on Research in Air Transportation: 1-8. University of California,
Berkeley, CA, USA. 22-25 May 2012. Berkeley, CA, USA.
23.
Allignol Cyril,
Nicolas Barnier, Nicolas Durand. 2016. “Detect & Avoid UAV
integration in the lower airspace traffic”. In: Proceedings of the 7th International Conference on Research in Air
Transportation (ICRAT). Drexel University, Philadelphia, PA, USA. 20-24
June 2016. Philadelphia, PA, USA.
24.
Lewicki Roy, Bruce Barry,
David Saunders. 2018. Essentials of
negotiation. Sixth edition. Columbus: McGraw-Hill. ISBN: 978-0077862466.
25.
Zeuthen Frederik. 1968. Problem of Monopoly and Economics Warefare.
London: Routledge. ISBN: 9780815371588.
26.
Endriss Ulle. 2006. “Monotonic concession protocol for multilateral
negotiation”. In: Proceedings
of the 5th International Joint Conference on Autonomous Agents and multiagents
systems: 392-399. 8-12 May 2006. Hakodate, Japan. DOI: https://doi.org/10.1145/1160633.1160702.
27.
Johnson Mark, Tim Miller, Peter McBurney.
2007. Modelling Multi-Agent Interaction
Protocols using Categories Enriched over Pointed Sets. Technical Report.
University of Liverpool, Liverpool, UK.
28.
Sibertin-Blanc Christophe. 1985.
“High level Petri Nets with data structure”. In: Proceedings of the 6th European Workshop on
Application and Theory of Petri Nets: 141-168. July 1985. Espoo, Finland.
29.
Huber Peter, Kurt
Jensen, Robert Shapiro. 1989. “Hierarchies in coloured Petri
Nets”. In: Advances in Petri
Nets 1990. Edited by Grzegorz Rozenberg, Germany,
Berlin, Heidelberg: Springer. ISBN: 978-3-540-53863-9.
30.
Jensen Kurt, Grzegorz Rozenberg. 1991. High-level Petri Nets - theory and
application. Berlin: Springer-Verlag. ISBN: 978-354054125X.
31.
Skorupski Jacek. 2015. “Airport
operation safety assessment with the use of coloured Petri Nets”. In: Safety and Reliability of Complex Engineered
Systems: 613-621. Edited by Luca Podofillini, Bruno Sudret, Bozidar
Stojadinovic, Enrico Zio, Wolfgang Kroger. Switzerland: Taylor&Francis
Group.
32.
Dudoit
Anrieta, Vytautas Rimša, Marijonas Bogdevičius, Jacek Skorupski.
2022. “Effectiveness of Conflict Resolution Methods in Air Traffic
Management”. Aerospace 9(12): 112. DOI: https://doi.org/10.3390/aerospace9020112.
33.
Skorupski Jacek, Anrieta Dudoit. 2019.
“A Simulation-Based Approach for the Conflict Resolution Method
Optimization in a Distributed Air Traffic Control System”. In: Research Methods and Solutions to Current
Transport Problems.ISCT212019. Advances in Intelligent Systems and Computing
1032: 104-114. Edited by Mirosław Siergiejczyk, Karolina Krzykowska. Ryn,
Cham: Springer. ISBN: 978-3-030-27686-7. DOI: https://doi.org/10.1007/978-3-030-27687-4_11.
34.
Jensen Kurt. 1997. Coloured Petri Nets. Basic Concepts, Analysis Method and Practical Use.
Springer Publishing Company, Incorporated. ISBN: 978-3-642-08243-6.
Received 15.09.2023; accepted in
revised form 06.11.2023
Scientific Journal of Silesian University of Technology. Series
Transport is licensed under a Creative Commons Attribution 4.0
International License
[1] Faculty of Transport, Warsaw
University of Technology, Koszykowa 75 Street, 00-662 Warsaw, Poland. Email: zuchowska.daria@gmail.com.
ORCID: https://orcid.org/0000-003-4390-925X
[2] Faculty of Transport, Warsaw
University of Technology, Koszykowa 75 Street, 00-662 Warsaw, Poland. Email: anna.stelmach@pw.edu.pl.
ORCID: https://orcid.org/0000-0002-2301-6908