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={A_i, A_j } – 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:

u_i: X→ that assign propositions to non-negative real numbers.

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:

or

(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 Z_i 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:

u_i (x_i) – the utility function of agent i at its proposal x_i

u_i (x_j) – the utility function of agent i at agent j's proposal x_j

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:

T_p – total distance flown according to the original flight plan

T_z – total distance flown after trajectory modification

H_Z – 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., U₁(1) is the utility function for the solution suggested by AC1 to itself, and U₂(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 U_i). 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 Z_i parameter should be calculated (in column Z_i) in accordance with the formula (2). Based on the Z_i 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, such that ,,

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 as: ;

– the set of inputs of tranistion t,

– the set of outputs of transition t.

M₀: P→Z₊×R – initial marking such that (where is the family of all multisets built over the set C) which means that M₀ is a function that assigns to each place a multiset over the type assigned to that place

τ: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:

– the type of a set of variables G,

– the set of variables present in the claim of transition t.

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:

– the type of a set of variables E,

– the set of variables included in expressions that are the weights of the arcs surrounding that transition t.

S – set of timestamps (also called time points) . It is a function definied on a set of places such that:

where:

r₀ –initial time, r∈ R.

– function determining the priority of transition t; this function applies only for transitions that are simultaneously active; in this situation a free choice of transition to be fired is possible.

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 T_confl, 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

t_h– time horizon

– time in conflict of aircraft i.

Based on the T_confl the safety and efficiency of the proposed solution are evaluated. The value of the parameter is in the range T_confl ∈[0,1]. The higher the value of the parameter T_confl, 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 T_confl 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 T_confl, N_los, 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