Introduction

When Bernard Ziegler (former Technical Director of Airbus) asked me (JeanMarc Garot) to give a presentation on failures in the automation of air traffic control, I was part of the panel assessing the thesis submitted by Nicolas Durand to the Institut National Polytechnique de Toulouse (doctoral school: information technology and communications) with a view to obtaining accreditation to supervise research entitled Algorithmes génétiques et autres outils d'optimisation appliqués à la gestion du trafic aérien [Genetic algorithms and other optimisation tools applied to air traffic management] http://www.recherche.enac.fr/opti/papers/notice.html?todo=abstract&type=thesis&file=t hesend.txt

The viva was held on 2 November 2004.

Nicolas Durand is one of the researchers at the Global Optimization Laboratory (http://www.recherche.enac.fr/opti/). As far as I (JeanMarc Garot) am aware, the GOL is one of the few research centre with a scientific approach to air traffic control. The laboratory was set up by JeanMarc Alliot, who is still running it today.

Durand's thesis made me (JeanMarc Garot) realise that in fact THERE HAS NEVER BEEN A SERIOUS ATTEMPT TO "AUTOMATE" AIR TRAFFIC CONTROL.

This is what I (JeanMarc Garot) shall try to demonstrate, drawing upon the work of the GOL and in particular that of Nicolas Durand, in order to:

 explain what is meant by "automation of air traffic control";  explain the "ground/air" or "centralised/decentralised" debate;  list all attempts to date, explaining their features and limitations.

It will also be noted that no attempt has gone beyond the "laboratory" stage and that even if most of them were halted for non"scientific" reasons, automating air traffic control is really a complex problem.

The current components of air traffic control

For those new to the world of air traffic control, it is concerned, at best, with issuing clearances to aircraft to take off and land without "crashing into one another". However, it has been known for quite some time [Vil 68] that air traffic control is a series of filters.

Historically, aircraft followed "visual flight rules" and used the Rules of the Air to ensure their separation, respecting the principle of "see and be seen". The improvement in aircraft performance and the increase in traffic volume has led to the development of an air traffic management system based on a series of filters, each filter having different objectives and managing separate volumes of airspace and time horizons.

In Europe, these can be roughly divided into five levels:

The five levels apply in all European airspace. France, for example, is divided between five control centres (Paris, Reims, Brest, Bordeaux and Aix en Provence), each managing a volume of airspace. Each control centre manages between 15 and 20 basic sectors, which can be collapsed depending on the density of traffic and the teams of controllers available.  In the long term (more than six months), traffic is organised macroscopically. This involves, for example, traffic interpretation diagrams, scheduling committee measures, agreements between centres and agreements with the army which allow civilians to use military airspace to ensure the smooth flow of traffic during Friday afternoon peaks.  In the shorter term, preregulation is often mentioned. This consists in organising a day's traffic one or two days in advance. At this stage, the majority of flight plans are available, we know the control capacity each centre is able to offer, depending on its staff, and the maximum throughflow of aircraft able to enter a given sector, i.e. the sector capacity. This is the role of the CFMU (Central Flow Management Unit, located at Brussels and managed by EUROCONTROL).

 On the day itself, modifications are made based on the most recent events. Transatlantic traffic, for example, may be taken into account at this stage, the routes and takeoff times of additional aircraft are assigned, unused slots may be reallocated and the day's weather forecast is taken into account. This is generally the role of the FMPs (Flow Management Positions) at each centre.

 The last filter of the air traffic control chain is the technical filter. This involves control within a sector. The average time an aircraft spends in a sector is approximately 15 minutes. The controller's overview is a little better because he/she has access to the flight plans several minutes before the aircraft enters the sector. The controller carries out surveillance, conflict resolution and coordination tasks with adjacent sectors. It would be useful to provide a precise definition of a conflict: two aircraft are said to be in conflict when the horizontal distance between them is less than five nautical miles5 and the difference in altitude is less than 1000 feet6. Conflict resolution methods applied by air traffic controllers rely above all on the controller's experience.

When several pairs of aircraft interact in the same conflict, controllers begin by separating out the problems in order to have only the basic conflicts to resolve.

 Recourse to the emergency filter should occur only when there is no air traffic control system or there is a fault in it. For the controller, the safety net predicts each aircraft's flight path within a time frame of several minutes, based on radar positions passed and tracking algorithms, and triggers an alarm in the event of conflict. It does not propose resolutions for the detected conflicts. On board the aircraft, the TCAS7 is designed to prevent a potential collision. Predictions arrive with less than a minute's warning and vary between 25 and 40 seconds. At this stage it is too late for a controller to intervene since it has been estimated that he/she requires between one and two minutes to analyse a situation, find a solution and communicate it to the aircraft. Currently, TCAS detects approaching aircraft and provides the pilot with a resolution advisory (for the time being in the vertical plane). This filter must resolve unforeseeable conflicts such as, for example, an aircraft exceeding a flight level given by control, or a technical malfunction which would considerably degrade aircraft performance.

We therefore tend to reduce the problem of air traffic control to that of "conflict resolution" at the technical filter level and therefore to the following problem: knowing the positions of aircraft at any given time and their future positions (to a fixed degree of accuracy), what manoeuvring instructions are to be given to these aircraft so that their flight paths do not generate conflicts and delay is kept to a minimum ?

Given that aircraft today are generally optimised and automated, it might seem surprising that control duties are mostly still carried out in the traditional way, calling on human expertise rather than the computational power of a computer.

CONSEQUENTLY, THE QUESTION ALWAYS ASKED IS WHY HAVE CONFLICT DETECTION AND RESOLUTION, AND HENCE AIR TRAFFIC CONTROL, NOT YET BEEN "AUTOMATED"?

We are not talking here about how information is presented to the operators, or about tools to support decisionmaking, but about complete automation, since this is how the question is often raised and has been raised in the preparation of this symposium.

In this document we shall therefore completely disregard the difficult question of interaction between the operator and the computer.

Another subject we will also not touch upon here is the equally difficult question of the transition between the current system and an entirely "automated" system.

ANOTHER FREQUENTLY ASKED QUESTION IS: GIVEN THAT IN THE PAST AIRCRAFT FOLLOWED "VISUAL FLIGHT RULES", NOW THAT THEY ARE EQUIPPED WITH SOPHISTICATED ELECTRONIC EQUIPMENT, WHY NOT IMPLEMENT ELECTRONIC VISUAL FLIGHT RULES?

The ATLAS Project (Air Traffic Land and Airborne System, an EEC/DG XIII study to define a single ATM/CNS system for Europe) was one of the first projects to have envisaged the possibility of autonomous aircraft. Unfortunately, owing to a difference of opinion between the European Commission (DG XIII) and the main consultant, PA Consulting, the ATLAS documents were never made public.

The Free Flight "concept" was first used in the United States around ten years ago, following pressure from airlines.

The word "concept" is symptomatic of air traffic control's propensity to failure. It consists in bringing together "experts" who have either put themselves forward or been coopted, whose job it is to obtain a "consensus" in reality the lowest common denominator of received ideas. It is then approved by someone at the highest political level possible, who reads it without necessarily understanding it but contents himself/herself with the unanimous opinion of the experts. As a result, the shelves are bulging with concepts from the likes of ICAO, the FAA, EUROCONTROL, ECAC and Germany (CATMAC for example), the only contribution of which is to the quality of the word processing. I should know. I, like many others, have been a participant, and the European Commission continues to finance the drawing up of "concepts". Relatively speaking, it is as if we believed that the laws of gravity, thermodynamics, quantum mechanics, relativity, etc. had been the outcome of working groups voted on by the UN General Assembly! The best summary of "concepts" in the field of air traffic control is that made by Dominique Colin de Verdière: "when we lack ideas, we create a concept". It would be interesting to trace the history of such concepts, if only to understand that the day when we stop "developing concepts" will be a blessing for us all. The word concept will not be used in the remainder of this document.

Let us return to Free Flight. The airlines were at the time seeking to overcome the constraints imposed on them by air routes and control costs. The American vision of Free Flight differs considerably from the European vision. The Americans have fewer enroute capacity problems and the airlines' main concern was to reduce their aircraft's flight times by using direct routes from the airport of origin to the airport of destination. In their notion of Free Flight, they did not discard the possibility of retaining a centralised system of control.

The Europeans have a slightly different approach, since traffic is limited by enroute capacity. Free Flight was therefore envisaged as a means of replacing centralised control with airborne control, while at the same time using direct routes, so as to relieve the controller's workload.

The problem is that Free Flight has today assumed a political significance, and it is no longer clear exactly what is covered by the term.

In the United States, since Free Flight was initiated by the airlines and the RTCA (Radio Technical Commission for Aeronautics) (http://www.rtca.org), the FAA (Federal Aviation Administration) tried to "claim it back" by calling everything it did "free flight". The culmination was Free Flight Phase I, which was nothing short of everything that the FAA was doing or intending to do, such as the Display System Replacement (i.e. new Sony screens). Moreover, since 11 September 2001, Free Flight is no longer fashionable and, as happens in Europe, the FAA regularly invents new acronyms to describe the same programmes, for example FAA Operational Evolution Plan (OEP).

In Europe, the NLR (Dutch aeronautical research centre the most privatised of all, along with Qinetic in Great Britain) is practically the only body which, like a good businessman looking for contracts, still defends "free flight". However, the idea of Free Routes, i.e. freeing navigation infrastructures on the ground, continues to be advocated by some people, in particular at the EUROCONTROL Agency.

Hereinafter we will use two orthogonal notions, which will allow us to define things more clearly.

-Direct routes or standard routes: in a system using direct routes, aircraft fly directly from their origin to their destination. With standard routes, they must follow existing air routes.

-Centralised control or autonomous control: centralised control is a mechanism in which a ground system ensures the safe flow of traffic. In an autonomous system, aircraft must ensure their own safety.

In the latter case (as with "automation", concerning which this document is not interested in "hybrid" solutions) we are not interested in "hybrid" solutions consisting in the reapportionment of tasks between the ground and the air, but in giving aircraft complete autonomy.

Abandoned automation projects led by Civil Aviation Authorities

The American attempt: AERA Automated EnRoute Air Traffic Control

The research work carried out by MITRE on AERA [Cel90, SPSS83, NFC+83, Nie89b, Nie89a, PA91] was financed by the FAA.

The first phase of this project, AERA 1, allowed aircraft flight paths to be planned according to pilots' intentions, and any potential violations of the standard separation or of flow restrictions for existing flight plans or those designated by a controller to be detected. It was therefore first and foremost a tool to aid decisionmaking which did not propose any solutions for operators.

AERA 2 [START_REF] Celio | Controller perspective of AERA2[END_REF] proposed significant new aids for operators, in particular a list of "resolutions recommended by the computer" for possible basic conflicts detected by AERA. AERA 2 also introduced tools to aid coordination between controllers (controllers monitor and intervene in control sectors; when an aircraft passes from one sector into another, it must be released by the first and taken over by the second). With AERA 2, however, the controller had the ultimate responsibility for separating aircraft.

With AERA 3, [NFC+83, Nie89b, Nie89a, PA91], the responsibility for separating aircraft was left to the machine. AERA 3 had a hierarchical structure. At national level, the ATMS (Air Traffic Management System) remained unchanged. It ensured a level of traffic flow management acceptable to AERA 3. AERA 3 comprised three hierarchical levels:

-ASF (Automated Separation Function) separated pairs of aircraft.

-MOM (Maneuver Option Manager) ensured that ASF (which only managed separated pairs of aircraft) respected the global context.

-AMPF (Airspace Manager Planning Functions) ensured that MOM could operate successfully. By preventing traffic density from becoming too high, it was able to stop aircraft having too few possibilities for manoeuvre. ASF and MOM were the two levels in which complete automation was envisaged. Nevertheless, the only AERA 3 level detailed clearly was ASF, which resolved only conflicts between two aircraft. MOM's objectives were defined reasonably clearly. Its operation, however, remained very vague and unconvincing. Research into global optimisation does not feature at all in AERA 3.

The ASF was provided by an algorithm called "GentleStrict" (GS), the aim of which was to automatically resolve horizontal crossing conflicts between two aircraft through the use of lateral offset manoeuvres (an offset is a comparison with the aircraft's initial flight path).

GS provided for:

-a lateral offset manoeuvre for one of the two aircraft, termed "gentle" according to a predetermined meaning; -a "strict" instruction to the other aircraft to maintain its flight path so as to avoid deviations above a certain tolerance threshold in relation to its nominal flight path.

GS resolved only conflicts in the horizontal plane and never changed aircraft speeds or flight levels. GS acted as late as possible so as to avoid pointless manoeuvres.

The algorithms used or envisaged in MOM were never referred to in the available reports. As regards modelling, AERA 3 may be of interest. However, the Project does not offer a solution to the problem of global optimisation once more than three aircraft are involved.

The AERA Project was completely swallowed up in the disastrous Advanced Automation System. I (JeanMarc Garot) think that the FAA's biggest mistake was to call a halt to the AAS Project. These days it is fashionable to criticise the AAS and say that it failed because it was too ambitious and had not made provisions for intermediate stages. This is not true and the FAA is currently trying to implement the stages that it had provided for in the AAS, for example screen replacement (DSR), replacement of the approach systems (STAR), the processing of flight plans (ERAM), etc. but less coherently and ultimately at a much higher cost.

Regarding AERA, the FAA, LockheedMartin (which took over the IBM Federal System Division, which had the AAS contract) and MITRE consider that URET is the operational implementation of AERA 1 and partly of AERA 2. In order to be fully informed on URET's many qualities see the MITRE site http://www.mitrecaasd.org/work/project_details.cfm?item_id=156). However, AERA 3, the "automation" project, has been abandoned.

A first attempt by the EUROCONTROL Experimental Centre: ARC2000 and its derivatives

The Project for the complete automation of European enroute air traffic control, ARC2000 [START_REF] Krella | Arc 2000 scenario (version 4.3)[END_REF][START_REF] Fron | Arc 2000: Automatic radar control[END_REF], has seen some radical changes since it was first conceived.

Nevertheless, the modelling of aircraft flight paths into "4D tubes" has remained unchanged and has enabled the definition of innovative controller decisionmaking aids [START_REF] Meckiff | PHARE: Highly interactive problem solver[END_REF].

Where it is possible to very accurately predict an aircraft's flight path, it can be represented by a curve in R4, the first three variables representing the aircraft's spatial position at time (t), the fourth variable. Because of inaccuracies in the measurement of positions and the holding of 4D flight paths, the curve is transformed into a "tube" by attributing to it a given crosssection in the interests of ensuring a realistic picture. In order to separate aircraft flight paths, a "tube" must therefore be constructed for each aircraft in such a way that the various tubes have empty intersections. To this end, ARC2000 uses a 'gradient' local optimisation algorithm which, for n tubes with an empty intersection, allows the construction of a tube n + 1 with an empty intersection with all the preceding tubes, and minimising the delay of aircraft n + 1.

Originally therefore, the principle of ARC2000 was as follows: the first aircraft to enter the system was allocated an optimal tube respecting its flight plan. As soon as a new aircraft arrived, its optimal tube was calculated by considering the tubes previously assigned as fixed constraints. In other words, a tube that had already been assigned was not adjusted. Global optimisation was not therefore sought. If an aircraft did not respect the tube that had been assigned to it, it had to negotiate a new tube respecting all the other tubes. The weakness of this principle was its lack of robustness. After all, it is possible that failure to respect a 4D tube is linked to meteorological events, for example, and that it doesn't affect just one aircraft but several. We might therefore fear a chaotic incident which would call into question the principle adopted.

The initial working hypotheses for ARC2000 took it well beyond 2000. However, the negotiation of 4D tubes presupposed that the aircraft would be equipped with FMS 4D (Flight Management System in four dimensions), which was not realistic in the short term. ARC2000's strategy consisted in guaranteeing conflictfree flight paths within a 20 minute time frame. It was thus necessary to find the right balance between predicting conflict free flight paths a long time in advance and not taking account of the conflicts in advance so continually readjusting the flight paths. The compromise ARC2000 found was to predict the entire flight path with the least possible number of conflicts, while at the same time monitoring possible conflicts. The conflicts were eliminated 20 or 30 minutes in advance. Before this period, only conflicts which had been diagnosed with certainty could lead to a reorganisation of flight paths. ARC2000 immediately adopted more realistic hypotheses. A modelling of the entire flight path without conflict (from origin to destination) seems to have been abandoned in favour of management of groups of conflicts or clusters, 20 or 30 minutes in advance. The search for optimal solutions also went through changes, since the principle of "last come, last served" was succeeded by a series of rules allowing aircraft to be dealt with according to priority and the convenience of manoeuvres. Crucially, it will be noted that the search for a global optimum has always been abandoned in favour of a tree path, in an order governed by empirical rules.

It should be noted that the research by EUROCONTROL enabled the production of very innovative tools to aid decisionmaking such as HIPS (Highly Interactive Problem Solver) [START_REF] Meckiff | PHARE: Highly interactive problem solver[END_REF], which is no longer concerned with the automatic optimisation of the flight path but provides the controller with flight path and conflict display support tools.

Lastly, we should note that ARC2000 was tested on real traffic. As with AERA 3, the modelling of the problem is interesting but the cluster resolution algorithms do not tackle the issue of the global optimisation of flight paths. Some time after my engagement as Director of the EUROCONTROL Experimental Centre, I (JeanMarc Garot) called a halt to this Project because it seemed to me to be based on false premises.

A first attempt by the French Air Navigation Study Centre (CENA): the SAINTEX Project

In the SAINTEX Project (SAINTEX refers to a book by the famous author and pilot SaintExupéry:

"Night Flight". The Project was scheduled to be implemented in times of low traffic density, at night for example.) [START_REF] Angerand | Bilan du projet SAINTEX[END_REF], three approaches to the automation of enroute control were addressed.

-The "Detection/Resolution" scenario was based on an expert system. It sought to reproduce the controller's behaviour. Conflicts were detected by extrapolating aircraft flight paths 10 minutes ahead (6 minutes for aircraft changing level19). Upon detection a conflict was categorised according to various criteria, such as the angle formed by the flight paths, the relative speeds, etc. For each category of conflict, a predefined manoeuvre was applied. The specialist system could resolve only a conflict between two aircraft.

-In the "4D" scenario, a conflictfree flight path was generated for all aircraft entering the sector. A flight path was represented by a set of points and vertical constraints. For each aircraft, a 4D tube was constructed representing its flight path, taking account of the uncertainties concerning its speed and position. SAINTEX made many attempts to construct an acceptable tube (conflictfree), starting from the ideal flight path (direct) towards increasingly problematic flight paths which still resolved conflicts. The time devoted to finding an acceptable flight path led to the quality of the resolution. The aircraft's flight path was then monitored so as to ensure that the aircraft was respecting the flight path it had been assigned. This scenario, purely algorithmic, strongly resembled that described in ARC2000.

-In the hybrid scenario, aircraft in level flight (as opposed to climbing or descending aircraft) were managed by the Detection/Resolution system and the others by the 4D system. Using a specialised system to resolve a conflict between two aircraft is not justified. The SAINTEX Project, by definition, was concerned with automated management of lowdensity airspace. The problem of resolving clusters of aircraft was raised, but not resolved. I (JeanMarc Garot) launched the Project while I was managing CENA. This proves that, whatever certain people may think and say, I am not opposed to the principle of studying "automation".

The Project was closed when the people working on it left CENA and it was not followed up because there were too many design errors.

A second attempt by the EUROCONTROL Experimental Centre: the FREER Project

The FREER Project (Free Route Experimental Encounter Resolution) was conceived in 1995 at EUROCONTROL, Brétigny, when I (JeanMarc Garot) had just been appointed Director. It has seen several changes. To begin with [DHN97, DH97], two approaches could be distinguished: in FREER1, the aircraft were entirely autonomous in lowdensity airspace, such as for example airspace above FL 390 or the Mediterranean. In this case, there was no longer any infrastructure on the ground to manage the traffic. The forecasting and resolution of traffic was done six to eight minutes in advance. The conflicts could not, however, involve more than four aircraft otherwise the onboard algorithms could no longer guarantee conflict resolution. FREER2 was expected, 15 to 20 minutes in advance, to ensure that this last constraint was respected. It was a pretactical filter managed from the ground, responsible for checking that the Free Flight airspace was not saturated.

The premises of FREER1 were as follows: the airspace concerned is the FFA (Free Flight Airspace) defined by the EATMS (European Air Traffic Management System) in which EFR (Extended Flight Rules) are applied [START_REF] Duong | Extended flight rules to apply to the resolution of encounters in autonomous airborne separation[END_REF]. These are an extension of the Rules of the Air used in accordance with visual flight rules in uncontrolled airspace for example.

We will not give an exhaustive description of the extended rules of the air. The interested reader can refer to the bibliographical references on FREER. The designers of FREER were compelled to complete the rules of the air on the one hand to take account of all the conflict configurations for two aircraft and on the other hand to define a definitive order for all aircraft, as soon as three or more aircraft were concerned. For example, if three aircraft simultaneously arrive at the same point by following the northbound routes 120 degrees and 240 degrees, the rule of giving way to the right does not help determine which of these three aircraft should have priority. An order based on the transponder code can, for example, relieve the uncertainty in this case.

Modifications to flight paths are managed by the aircraft, which respect the rules of the air and the procedures in place. The onboard algorithms proposed for the definition of avoidance manoeuvres are based on HIPS (Highly Interactive Problem Solver), a tool derived from ARC2000, which allows the visualisation in real time of the NoGoZones (conflict zones) as the aircraft flight paths progress.

HIPS nevertheless presupposes that the flight path of the aircraft to be avoided is known.

The operation of FREER2 in this context was never described in detail.

Subsequently, FREER2 has changed considerably [START_REF] Duong | On the applicability of the freeflight mode in European airspace[END_REF]. A tool had to be proposed for the partial delegation of basic conflict resolution (involving two aircraft) in various volumes of airspace with higher traffic density. The aircraft had to be equipped with an ASAS (Airborne Separation Assurance System).

Tests are currently being carried out to evaluate the feasibility of delegating separation tasks to flight crews in order to determine whether this might lighten controller workload (COSPACE Project).

Although the conclusions are quite optimistic, it is clear that this is no longer a question of "automation".

An original attempt by another French research centre, ONERA (Office National d'Etudes et de Recherches Aérospatiales): the repulsive forces method

The oldest attempt at an "automated" solution is that studied by Karim Zeghal [Zeg93, Zeg94] in his thesis, in which he introduces the notion of the coordination of actions, thanks to various forces being exerted on agents, in our case the aircraft.

Karim was a researcher at ONERA, but CENA, which I (JeanMarc Garot) was managing at the time, "sponsored" his thesis. Karim Zeghal defines three types of force that will contribute, depending on the level of urgency:

-Attractive forces, which allow aircraft to achieve their objective (a beacon or their final destination for example).

-Repulsive forces, which allow aircraft to avoid a nearby, therefore dangerous, obstacle. This obstacle may be an aircraft or a prohibited area.

-Sliding forces, which allow aircraft to bypass obstacles. The aircraft coordinate their actions in this case. A sliding force is defined as follows: if we look at the equipotential of danger running through the aircraft, a sliding force is tangential to the equipotential whereas the repulsive force is perpendicular to the equipotential. There are, therefore, several possible sliding forces. If we remain in the horizontal plane, we can define two directions of sliding (to the right or to the left). The optimal direction (this involves local optimisation for the aircraft concerned) is that which favours approaching the objective. In the event of a moving obstacle, Karim Zeghal defines coordinated evasive action. If two aircraft arriving at the same point follow complementary sliding forces, the conflict can be avoided very effectively. In the simple example of two aircraft, we project for example the relative speed onto the equipotential of danger for each aircraft and thus obtain two coordinated sliding forces. Subsequently, in order to limit radical changes in direction, the intensity of the various forces must be managed. Since aircraft are limited by rate of turn, rate of climb and rate of descent, they cannot carry out any manoeuvre too quickly. The various forces exerted on the aircraft combine with the variable coefficients, depending on how imminent the danger is.

To manage conflicts involving more than two aircraft, Karim Zeghal suggests adding together the forces for each aircraft. "Intuitively, except in certain rare cases, this should allow us to obtain force directions which are consistent with one another and in relation to obstacles". This hypothesis is based on the examination of case studies only. Nevertheless, the practical results seem promising for low densities.

The coordination of actions through sliding forces is not aimed at optimisation but above all at efficiency and robust solutions.

The study into the possible use of a coordination of actions theory for air navigation purposes was begun at CENA in 1994. Three systems were envisaged:

-If the individual process requires only information local to the aircraft, it can operate autonomously through a perception of its surroundings. Karim Zeghal therefore suggests a "hybrid" autonomous aircraft system (The equivalent of the American TCAS (Traffic alert and Collision Avoidance System) but with a longer leadtime).

The main advantage of this system is its robustness. An aircraft defect does not compromise the safety of the system. There is a kind of redundancy in the system which consolidates its robustness. This system should be able to manage conflicts between 4 and 10 minutes in advance, which presupposes that another master system continues to manage local traffic density so as to avoid saturation.

-Karim Zeghal also proposes a support system for the controller. For this purpose, all that is required is to use the individual process as a centralised process and to simulate future flight paths.

The result of a simulation is therefore a series of flight paths ensuring conflict avoidance in the time period set aside for all aircraft. This could, in his opinion, be extremely advantageous when planning flight paths and making proposals to the controller.

Given that the proposed resolutions using these techniques are continuous commands, it seems unlikely that these could be put into practice if the pilot and controllers remain within the system. It seems to me that this last point is a major obstacle to using these techniques.

-Lastly, we might imagine an "intermediate" dual system. In this scenario, certain aircraft are autonomous, others are not. The controller is therefore more available and the capacity in his sector increases.

The robustness of solutions is one of the advantages of Karim Zeghal's work. However, many problems remain to be resolved. If we wish to continue entrusting to humans the role of piloting aircraft, we must be able to transmit instructions for manoeuvres that are executable and therefore simple. For example, we can instruct a pilot to change heading for a time, to prolong a climb or to adjust the start time for a descent. We cannot, however, ask him/her to permanently change his/her heading, speed or rate of climb/descent. It would therefore be necessary to review the modelling of flight paths in order to simplify them and make them more accessible to pilots.

Moreover, although we wish to prove that these techniques can resolve all conflicts involving two aircraft, the generalisation of n aircraft (which consists in adding together the forces generated by each aircraft) has been tested only on examples. Lastly, the selected modelling does not allow any research into global optimisation. Similar approaches using fields of potential were tested by the Berkeley aeronautical department [START_REF] Gosh | Maneuver design for multiple aircraft conflict resolution[END_REF], but as yet they do not allow for conflict resolution involving more than three aircraft, as in the case of the neuronal methods tested in Part 6.1. The Project was not followed up and Karim Zeghal has since started working at the EUROCONTROL Experimental Centre, where he is one of the mainsprings of the COSPACE Project (see above).

A provisional conclusion?

It therefore seems clear that THERE HAS NEVER BEEN A SERIOUS ATTEMPT TO "AUTOMATE" AIR TRAFFIC CONTROL.

If we had attempted it, what would the transition problems have been, and during the transition would it have been possible to manage the development in relations between operators and computers?

Clearly, since we are talking about aeronautics, comparisons with airborne events are inevitable. I (JeanMarc Garot) will attempt to present my interpretation, no doubt marked by my limited knowledge of airborne developments.

The Airbus A320 team, "those magnificent men in their flying machines" (led by Bernard Ziegler) decided to "automate" an aircraft. However:

 there was already a long history with previous Airbuses;  being the underdog, Airbus needed to distinguish itself from Boeing;

 there had been a real setto with the pilots of Air Inter in particular;  the pilots were reinstated, with different responsibilities but with a role nevertheless.

The result is one of the contributing factors to Airbus' success: "safe" aircraft;

 above all, scientific experience was gained concerning flight mechanics, etc.

However, this is what is most lacking in air traffic control.

A scientific approach

As we have just seen, attempts at automation, generally at the initiative of air traffic control authorities, as a rule take the operational context largely into account but do not always tackle the underlying problem of optimisation. What is more, they have all been abandoned, in certain cases leaving several interesting "byproducts".

Theoretical approaches, which have appeared more recently, effectively tackle the complexity of the problem by occasionally developing unrealistic hypotheses in an operational context. It is rare for such approaches to raise the combinatory aspect of the problem while at the same time seeking to respect operational constraints.

The complexity of the conflict resolution problem

Yes! The conflict resolution problem is complex.

Let us begin with a definition. Within a given time window for a predicted flight path, a potential conflict between two aircraft is defined as any conflict detected within the time frame of the forecast, taking into account uncertainties linked to the flight paths.

The relationship "is in conflict with" or "is in potential conflict with" defines a relationship of equivalence. The categories of equivalence associated with this relationship will be called "clusters" of aircraft in conflict or quite simply "clusters".

If we limit ourselves to the horizontal plane, in the event of a cluster of n aircraft, there may be n (n-1)2 potential conflicts. It can be demonstrated [START_REF] Durand | Optimisation de Trajectoires pour la Résolution de Conflits en Route[END_REF] that all the acceptable solutions contain 2n (n-1) 2 related components, which presupposes, if we wish to use a local optimisation method (continued deformation of flight paths) that the search algorithm must be used an equal number of times. Thus, for a cluster of six aircraft, this represents 32,768 related components. In practice, taking aircraft performance into account, it is not necessary to explore all related components. Nevertheless, the fact that so many unconnected sets exist in theory and the impossibility of knowing a priori which one contains the optimal solution makes this a highly combinatorial problem. Relaxing the separation constraints does not dispose of the problem of global optimisation comprising at least as many local optima as related components.

Adding the vertical dimension does not reduce the combinatory character of the problem, since an aircraft is not instructed to carry out a manoeuvre in the two planes simultaneously.

The constraints

A certain number of constraints should be indicated -An aircraft cannot modify its speed (or only very slightly), except during the descent phase.

-An aircraft cannot be considered to be flying at a constant speed except possibly while it is cruising if there is no wind. Moreover, while climbing and descending, its flight path is not rectilinear. It cannot therefore be described analytically. The evaluation of an aircraft's future positions requires the use of a simulator.

-Aircraft are restricted by their turn rate; pilots generally prefer lateral over vertical manoeuvres, except during the climb or descent phases.

-Although automatic pilots are now much more efficient than human pilots (under normal flying conditions), it does not currently seem realistic to envisage flight paths not carried out by a human pilot.

-Uncertainty with the rates of climb and descent is very high (between 10% and 50% of vertical speed). In cruising flight, the uncertainty concerning speed is lower (approximately 5%). Laterally, uncertainty does not increase with time, in the same way that a cruising aircraft generally maintains its altitude well.

The need for a simulator to calculate the future positions of aircraft makes it impossible to research analytical solutions to the problem of resolution of aircraft conflict. The same applies to the use of classic optimisation methods having recourse to the gradient or Hessian of the criterion to be optimised.

However, the main difficulty is linked to the complexity of the problem itself rather than to the aforementioned constraints.

A scientific method

Air traffic management is a source of largescale problems, with mixed variables, generally of a very combinatory nature and as difficult to model as the contextrelated constraints are difficult to grasp. Furthermore, the problems encountered are closely interlinked. It is difficult, for example, to separate the problems of airport traffic from the problems of approach traffic, since both depend on the management of takeoff slots. Similarly, the problem of organising the air route network has a marked impact on sectorisation and conflict resolution, etc. For all the reasons set out above, the problem identification and modelling phase is probably the researcher's most difficult task. Above all, care must be taken to respect the basic operational constraints while not getting bogged down in all the details, in order to identify problems of a reasonable size which merit the application of optimisation methods. It is also necessary to constantly keep in mind the constraints initially put to one side and make sure that they can be subsequently reintegrated once the resolution methods are identified. In this context, we were able to observe, via the various approaches to the problem of conflict resolution, that the various algorithms chosen imposed modelling systems which did not always allow the reintegration of operational constraints. It is therefore necessary to take account not only of the algorithm's performance on the chosen model but also its capacity to integrate operational constraints.

Once a problem has been identified, the approach can be summarised as follows:

 mathematical modelling of the problem;  calculation of its complexity;  research into suitable algorithms;  validation of the results obtained, at experimental level through a simulation, and at scientific level through publication.

The validation of the results obtained at experimental level is an extremely delicate and timeconsuming task, since the quality of the data has to be carefully checked. Processing of raw data is often painstaking.

Another difficulty is to acquire the skills necessary to use the various algorithms in order to implement them efficiently and thus obtain relevant comparisons.

Centralised approaches

In this section are listed the various resolution methods that I (Nicolas Durand) have explored over the past ten years, following a centralised approach to the problem of conflict resolution, namely:

-the results obtained during Durand's doctoral thesis, thanks to Genetic Algorithms [START_REF] Durand | Optimisation de Trajectoires pour la Résolution de Conflits en Route[END_REF]; -an approach using a Genetic Algorithm combined with a linear programming algorithm, which was the subject of Frédéric Médoni's postgraduate diploma course, co supervised by JeanMarc Alliot [START_REF] Medioni | Algorithmes génétiques et programmation linéaire appliqués a la résolution de conflits aériens[END_REF]; -a branch and bound method using intervals, set out in the thesis of Frédéric Médioni [START_REF] Médioni | Méthodes d'optimisation pour l'évitement aérien : systèmes centralisés[END_REF]; -a semidefined programming method, presented by Eric Féron [START_REF] Frazzoli | Aircraft conflict resolution via semi definite programming[END_REF], and set out in Pierre Dodin's postgraduate diploma course [START_REF] Dodin | Résolution de conflits via la programmation semi définie[END_REF], cosupervised by JeanMarc Alliot.

-an original attempt by MIT: résolution by integer linear programming: in the context of resolution of aircraft conflicts in the horizontal plane only, assuming that aircraft move at a constant speed, Pallatino, Feron and Bicchi [START_REF] Pallottino | Conflict resolution problems for air traffic management systems solved with mixed integer programming[END_REF] demonstrated that it was possible to linearise the problem in the context of resolutions through speed or heading adjustment, subject to the addition of a certain number of Boolean variables. Thus in the case of a speed resolution, a conflict involving n aircraft gives rise to a problem with 2 n2 -n variables and 4n(n-1)2 + 2 n constraints. In the case of a heading resolution, the problem gives rise to 11n (n-1)2 + n + 1 variables and 35n(n-1)2 + 2 n constraints. The use of CPLEX [IL099] allows the authors to resolve conflict situations involving 15 aircraft, but the hypotheses required for the flight path profiles are quite restrictive (stable aircraft, constant speeds, no return management on the flight path).

These studies are some of the very few in existence which take account of the combinatory aspect to the problem of conflict resolution. In this respect they are one of the all toorare attempts to seriously tackle the problem. These approaches differ greatly in terms of modelling. Using genetic algorithms avoids the need to make restrictive hypotheses concerning aircraft flight paths. The four other modelling methods are more restrictive. The approach combining a Genetic Algorithm and a linear programming algorithm requires the use of offsets and cannot take into account the uncertainty over an aircraft's speed. The approach implementing a branch and bound method using intervals presupposes that the aircraft fly at a constant speed, which does not allow account to be taken of descending and climbing aircraft. The semidefined programming method and the integer linear programming methods also presupposes that the aircraft fly at a constant speed on rectilinear flight paths.

In terms of efficiency, only genetic algorithms, thanks to the use of partial separability, allows the resolution of largescale conflicts involving more than 20 aircraft.

Autonomous or airborne approaches to conflict resolution

In this section are listed the various resolution methods which use an autonomous or dispersed approach to the problem of conflict resolution.

An avoidance system can be said to be airborne (or possibly dispersed) when the avoidance flight path of each aircraft is generated individually (in the context of application of such a method, it would be most often generated on board the aircraft itself, hence the term airborne).

It is useful in this respect to distinguish between two main approaches, depending on whether the aircraft manoeuvre simultaneously or sequentially:

-among the reactive approaches, where the aircraft react simultaneously, we will address a method based on neuronal networks, mapped out in Frédéric Médioni's thesis [START_REF] Médioni | Méthodes d'optimisation pour l'évitement aérien : systèmes centralisés[END_REF]; -among the sequential approaches, we will set out a method for allocating tokens combined with an algorithm A, allowing conflicts to be managed in a Free Flight context. This approach was the subject of a post graduate diploma by Géraud Granger [START_REF] Granger | Résolution de conflits embarquée dans les espaces de faible densité[END_REF] and Nicolas Archambault [START_REF] Archambault | Optimisation du solveur de conflits du simulateur de trafic cats[END_REF], cosupervised by JeanMarc Alliot.

Airborne or autonomous approaches have proven considerably less efficient than centralised approaches for the resolution of largescale conflicts. Modelling via a neuronal network does not seem to be easily extendable to three aircraft. Modelling via the allocation of tokens is, however, very interesting because it guarantees the coordination of resolution manoeuvres and could prove effective in lowdensity airspace. The choice of order of priority nevertheless remains an open problem.

6 What does the future hold?

It seems essential to continue the efforts undertaken to develop scientific research teams within the air navigation bodies, as this is the only way to reach an understanding of the air traffic management environment and to access the operational data. Access to this data is vital in order to check, via simulations, the effectiveness of the methods developed.

However, the survival of a research team integrated in this way is difficult since the expectations of the world of research and that of operations are different. Although air traffic management is generally an attractive field of application for researchers, initiating those in the operational sector to certain scientific approaches can be more timeconsuming.

A new research theme for GOL is the resolution of conflicts through speed adjustment. The uncertainty surrounding the speed of an aircraft, in the horizontal plane and certainly in the vertical plane, leaves a margin for manoeuvre to resolve conflicts without adjusting an aircraft's flight path. N. Archambault is currently pursuing his thesis work on the subject. This work requires significant cooperation with aircraft manufacturers in order to identify the possibilities offered by aircraft FMSs (Flight Management Systems).

The availability of new or envisaged means of communication (DataLink) and navigation (GPS) offer us new perspectives on air traffic control.

Furthermore, efforts should focus on improving flight path prediction. All the work carried out in the laboratory over the past ten years has shown the importance of reducing uncertainties in flight path prediction.

Will this scientific approach allow us to overcome the problems of transition, and within this transition the problems of the changing relationship between controllers and pilots on the one hand and computers on the other? Certainly not but it is one of the necessary conditions for progress.

Ground/air or centralised/autonomousThe resolution of air conflict is currently performed centrally. It is the controller, with an overview of the problems to be resolved, who instructs aircraft how to manoeuvre.


Barry Laffoy

Saraansh Dave

Mahesh Sooriyabandara
email: mahesh.sooriyabandara@toshiba-trel.com

Automated Trading For Smart Grids: Can It Work?

This paper applies basic economic principles which have been developed in financial markets to a future smart grid scenario. Our method allows for autonomous bidding for electricity units to create an emerging market price for electricity. We start with replicating the popular Zero-Intelligence-Plus algorithm and setting it in a electricity supplier-consumer scenario. We identify significant weaknesses of applying this in an electricity market especially when intermittent sources of energy are present or when the supplier to consumer ratio is very small. A new algorithm (ZIP-260) is proposed which includes a measure of fairness based on minimising the deviation across all un-matched demand for a given period. This approach means that no consumer in the system is constantly experiencing an electricity supply deficit. We show and explain how market conditions can lead to collective bargaining of consumers and monopolistic behaviour of suppliers and conclude with observations on automated trading for smart grids.

Introduction

Financial markets have been used in recent history as a robust method for matching buyers and sellers. Since the late 1990's computers have been increasingly used as intelligent agents to trade on behalf of human operators at a much higher frequency. High frequency trading has been bolted onto pre-existing system regulation and this may enhance the effects where billions of dollars have been lost in a span of just 15 minutes [START_REF] Cliff | The Flash Crash of May 6 2010: WTF?[END_REF] [START_REF] Nuti | Algorithmic Trading[END_REF]. The root cause of some of these 'dips' such as the flash crash of May 2006 have not been unilaterally agreed on but have been classed as a systemic failure [START_REF] Cliff | The Flash Crash of May 6 2010: WTF?[END_REF]. However, financial markets can be said to be a very efficient method for solving resource allocation problems in decentralised systems with multiple actors.

Smart grids carry the promise of real-time energy management, diagnostics and fault correction with the aim of integrating renewable energy sources and decarbonised transport solutions [START_REF] Amin | Toward a Smart Grid[END_REF]. The smart grid is characterised as integrating information and communication technologies with the electricity network to create a responsive and adaptable network. The primary challenge with intermittent energy sources and real-time balancing is trying to match demand patterns to those of supply. In a future where decarbonisation of energy is paramount, the ability to respond to demand fluctuations will become more difficult. Demand response [START_REF] Albadi | Demand Response in Electricity Markets: An Overview[END_REF] as a method of addressing this balancing issue can be described as reflecting the value of electricity at a point in time given the state of the system. This view resembles the resource allocation problems found in real-time trading markets and we propose to investigate the application of algorithmic trading as an efficient mechanism to manage electricity demand for households with variable electrical supply. We apply the Zero-Intelligence-Plus (ZIP) algorithm [START_REF] Cliff | Minimal-Intelligence Agents for Bargaining Behaviors in Market-Based Environments[END_REF], a well known automatic trading algorithm, to this problem scenario. Initially the algorithm is directly mapped onto a scenario including electricity suppliers and domestic consumers. After evaluating its performance, changes are made to allow for a more fair consumption distribution. Even after promoting fairness in our system we identify inefficient market behaviour and monopolistic behaviour when there is a supply surplus. This observation of different behaviour between deficit and surplus states of the market lead us to implementing a 2-state switching algorithm for the suppliers which accounts for this. We identify some key limitations of applying the ZIP algorithm and provide regulatory and aglorithmic requirements that are needed for real-time pricing of electricity when trying to balance supply and demand.

This paper is organized as follows; §2 covers relevant literature, §3 outlines the system model, §4 details the simulation scenarios used and results, §5 presents our analysis and §6 concludes on the work and outlines areas for further research.

Background Literature

Demand response has been classified as incentive based or priced based programs (IBP or PBP respectively). IBP includes more direct aspects such as direct load control or emergency demand response while PBP utilises more market oriented solutions such as real time pricing or time of use pricing. Time of use pricing has been shown to create a bias of consumer behaviour [START_REF] Ramchurn | Agent-Based Control for Decentralised Demand Side Management in the Smart Grid[END_REF] which causes 'rebound' peaks to be seen during the off-peak tariff period. Clearly this method is limited in its approach and can have undesirable consequences when the solution is scaled up. Game-theoretic approaches show how the market can converge to a Nash equilibrium while improving the aggregate demand curve [START_REF] Mohsenian-Rad | Autonomous Demand-Side Management Based on Game-Theoretic Energy Consumption Scheduling for the Future Smart Grid[END_REF] but are somewhat limited as they usually assume a central coordinating agent (e.g. the utility) which makes it difficult to implement on a large scale. Real time pricing is more favourable towards the principle of using price as a signal of the value of electricity at that specific moment in time but there has been little work in the application and understanding of real time trading in such a system. The closest work in the smart grid domain applies transmission constraints and novel balancing mechanisms to trading agents which perform bidding and acceptance of electricity units [START_REF] Vytelingum | Trading Agents for the Smart Electricity Grid[END_REF].

More directly relevant work falls into the domain of agent-based computational economics [START_REF]Handbook of Computational Economics[END_REF] and continuous double auctions (CDA). CDA's are a market system where buy and sell prices are quoted continuously and asynchronously for commodities and is widely used around the world. Previous work on CDA's applied to automatic trading show that very simple behaviour of agents have high levels of allocative efficiency [START_REF] Gode | Allocative Efficiency of Markets with Zero-Intelligence Traders: Market as a Partial Substitute for Individual Rationality[END_REF] and can be improved to also provide a high level of profit dispersion (an indicator of market equality) [START_REF] Cliff | Minimal-Intelligence Agents for Bargaining Behaviors in Market-Based Environments[END_REF]. The Zero Intelligence (ZI) traders' [START_REF] Gode | Allocative Efficiency of Markets with Zero-Intelligence Traders: Market as a Partial Substitute for Individual Rationality[END_REF] private information only included the limit price for that trader, but by giving the agents an internal, mutable expected profit margin and memory of the last shout on the market, simple machine-learning techniques could give the traders more sophisticated behaviour [START_REF] Cliff | Minimal-Intelligence Agents for Bargaining Behaviors in Market-Based Environments[END_REF]. The resulting Zero-Intelligence Plus (ZIP) agents would observe each shout on the market and remember if the last one was a bid or an offer, for how much, and whether or not it resulted in a trade. Based on this, the agent would update its internal profit margin and shout price.

This research also falls into the domain of current electricity markets which operate differently depending on country specific contexts. In the U.K. contracts are agreed between those demanding electricity and generators in half-hourly periods. When there is a difference between the contracted amount and generator supply the system operator (National Grid) is responsible for real-time balancing through bids and offers [START_REF] Elexon | The Electricity Trading Arrangements: A Beginner's Guide[END_REF]. This basic model may have to be reviewed to allow for smart grid implementation such that the effect of wholesale prices can be observed by the consumer and thus influence demand patterns. Currently there is a buffer between real-time consumption and the price of electricity. The role of the system operator will still apply as the real-time management must be controlled to avoid grid failures.

Directly applying the ZIP alogrithm needs careful thought and experimentation as there are a few fundamental differences between electricity and financial markets. Financial markets have liquidity which assumes that a seller is able to sell their stock on the market if they wish to do so at a given price, additionally, a seller is able to withold stock in anticipation of better prices in the future. In an electrical market, it is not possible to withold a unit for a better price as electricity cannot be stored. Financial markets also have a large number of buyers and sellers which is in stark contrast to electricity generators and consumers where there is a much bigger difference. These differences make the application of ZIP to electricity markets non-trivial but also enhances the view that a real-time solution should be used in order to allow the system to respond at a similar rate, especially as more renewable energy is integrated into the grid.

System Model

This section outlines the scenario we use to test our algorithms and measure the behaviour of the system. Our simulation consists of 100 households and two electricity suppliers; fossil fuel (Supplier F) and wind power (Supplier W) suppliers. Supplier F is modelled as having constant power output reflecting a non-renewable energy source (e.g. coal or nuclear) while Supplier W has a variable power output modelled as following a Weibull distribution [START_REF] Qian | Benefits of energy storage in power systems with high level of intermittent generation[END_REF]. By including suppliers with different output profiles, we will be able to investigate whether the real-time (half-hourly) changes in supply affect the market price and whether the mechanism is efficient in allocating resources. The households are able to bid for units of electricity through the exchange (which could be organised by the utility) where Suppliers F and W are able to sell units of electricity. Households bid for a total number of units every half hour depending on their individual consumption profile whilst the suppliers are able to sell units every half hour depending on their plants output. Empirical smart meter data measured at half-hourly intervals in an Irish study [START_REF]Electricity Smart Metering Customer Behaviour Trials ( CBT ) Findings Report[END_REF] is used as the demand profile for households in the simulation. This also represents the future scenario of a decarbonised electricity supply where centrally generated base load capacity will support intermittent and decentralised sources. Both the heterogeneity in demand profiles and changes in aggregate supply and demand will create an environment with different market states which will test the algorithms' performance. A genetic algorithm was used to search the parameter space in order to find an optimal solution (we note that due to the nature of genetic algorithms this may well be a local optimum) where each genome expresses a phenotype in the form of a vector [µ, β, λ, ρ, ]. The fitness function can be chosen according to the aim of the algorithm; a popular choice is Smith's α [START_REF] Smith | An Experimental Study of Competitive Market Behavior[END_REF] which is a measure for how well the market converges to an equilibrium price. This measure did not promote fairness over the agents, especially in a situation where there is an overall deficit of supply. As a result we decide to use a measure which minimises the demand deficit variance across all the households (9). In the the remainder of this section, §3.1 introduces the original ZIP algorithm and §3.2 explains the limitations of directly applying this to electricity markets and the significant changes we made to the algorithm and §3.3 covers price and fitness functions.

The ZIP Algorithm

This sub-section is a recap and overview of the ZIP algorithm as first proposed by Cliff [START_REF] Cliff | Minimal-Intelligence Agents for Bargaining Behaviors in Market-Based Environments[END_REF]. ZIP agents have an internal, mutable expected profit margin (µ i ) which can be used with the current shout price (λ i ) to calculate the current shout price (p i,t ) as shown in [START_REF] Cliff | The Flash Crash of May 6 2010: WTF?[END_REF]. Based on this, it might alter it's internal profit margin. The rate at which an agent's profit margin converges to the observed shout price is determined by a simple version of the Widrow-Hoff delta rule for machine learning. This gives an update rule between the times of t and t+1 as shown in [START_REF] Nuti | Algorithmic Trading[END_REF], where ∆ i,t is defined in [START_REF] Amin | Toward a Smart Grid[END_REF].

p i,t = λ i × (1 + µ i,t ) (1)
µ i,t+1 = (p i,t + Γ i,t )/λ i -1 (2)
∆ i,t = β i × (τ i,t -p i,t ) (3)
τ i,t = q i,t × (1 + ρ) + (4) Γ i,t+1 = λ i,t × Γ i,t + (1 -λ i,t ) × ∆ i,t (5)
Here, β i is the agent's learning rate, which must be added to the private information of each agent. τ i,t is the target price, towards which the shout price is being moved and Γ i,t is the learning momentum. There is a distinction between the target price and the most recent market shout price, q i,t as otherwise the agents will no longer test the market if p i,t ≈ q i,t , since this would lead to a value of ∆ i,t close to zero and thus µ i,t+1 ≈ µ i,t . The ZIP agents calculate the target value using a randomly generated relative multiplier (ρ) of the last shout price, plus a randomly generated absolute perturbation ( ) shown in [START_REF] Albadi | Demand Response in Electricity Markets: An Overview[END_REF]. Finally, the agents were given a learning momentum coefficient Γ i,t , so that when updating prices, they could take into account the history of price updates. This dampens the impact of a series of price updates in alternate directions, and reinforces the effect of a series all in the same direction. Thus the complete behaviour of a ZIP agent is defined by the initial profit assumption µ and the values of β, λ, ρ, and . One variant of the ZIP algorithm (ZIP60) [START_REF] Cliff | Zip60: an enhanced variant of the zip trading algorithm[END_REF] allowed agents to distinguish up to six different scenarios under which prices can be changed and create a rule-set for each. The ZIP algorithm also allows buyers and sellers to start with different assumptions hence embracing heterogeneity that is present in most trading environments.

ZIP-260

Unlike ZIP, we do not impose any scenario under which prices cannot be updated. To increase flexibility the agent considers five binary factors relating to the previous shout at every time step:

1. Am I still active? 2. Am I buying or selling? 3. Was the last shout accepted or not? 4. Was the last shout a bid or an offer? 5. Would I have traded at the price of the last shout?

This leads to thirty-two distinct scenarios where each scenario is associated with a four element vector [β, λ, ρ, ] which defines the price update rule as shown in [START_REF] Ramchurn | Agent-Based Control for Decentralised Demand Side Management in the Smart Grid[END_REF].

∆ t = [p t -(q t × (1 + ρ) + )] × (1 -λ) × β + λ × ∆ t-1 (6)
Each element of the vector is set by a uniform random distribution between a maximum and minimum provided at the outset. This means that each simulation has 2 5 ×4×2 = 256 parameters associated with price updates. An additional four parameters are associated with the initial profit assumption which leads to this algorithm being named 'ZIP-260', in keeping with the naming convention of the ZIP variants.

One major difference between using ZIP in finance and in electricity markets is the notion of trading at a loss. In finance, it is possible to withold selling a unit to avoid trading at a loss if required. In electricity systems, once a unit of electricity is produced it must be distributed and consumed. Clearly, a supplier could store the energy but currently this has limited large-scale availability. As such, we assume the supplier has no storage capabilities and so must dispose of the electricity generated in some way once it is produced. We also assume that the supplier would sell the electricity at a loss instead of incurring the costs associated with disposing of generated electricity. ZIP shows this behaviour because there is a strict budget constraint on the agents in the form of the limit price, λ i , which sets an absolute value on the price they are willing to meet. This represents the maximumim value that a consumer will buy at and a minimum price that suppliers will sell at. Removing this constraint would return the ZIP algorithm to behaviour characterised by the ZI agents [START_REF] Gode | Allocative Efficiency of Markets with Zero-Intelligence Traders: Market as a Partial Substitute for Individual Rationality[END_REF]. To resolve this issue we allow agents to enter a loss accepting state in certain situations. After updating the price as described earlier ( 6), a second simple algorithm using a Markov chain controls the state of the agent. If a trade was achieved at time t then all the agents will revert to profit-seeking behaviour. However, if a shout at time t -1 was unmet then there is a small probability (P L ) that an agent will return to a loss accepting state. The internal profit assumption remains unchanged in this state but they accept any price that is quoted on the market. Figure 1 shows the distribution of unmatched supply and demand with and without the loss accepting mechanism. Positive values of units before simulation indicate a supplier while a negative value of units indicates a consumer. Figures 1(c) and 1(d) shows how well the resources are allocated. In these simulations, there is an overall deficit in supply.

Price and Fitness Functions

Two general pricing schemes are used throughout the paper; constant and varying demand price. The price for the ith agent's jth unit is given by λ i,j . The constant price function is give by [START_REF] Mohsenian-Rad | Autonomous Demand-Side Management Based on Game-Theoretic Energy Consumption Scheduling for the Future Smart Grid[END_REF] whilst the varying price is given by ( 8) where u i is a utility function parameter. The suppliers price has been set to be a constant value of 1.5, which, while being simplistic is justified by considering only one trading day where the cost of fossil fuel powered energy and wind powered energy is assumed to be stable.

λ i,j = 2.5 (7)
λ i,j = 1.20 + 10 9 + j + u i (0.05) (8)
Throughout the paper two measures of fitness are used, Smith's α [14] and we introduce a measure of unit variance (σ 2 ) which we define in [START_REF]Handbook of Computational Economics[END_REF] where N is the number of consumers and x is a vector representing the units that an agent demands and x is the population mean.

σ 2 = 1 N N i (x i -x) 2 (9)

Simulation Scenarios and Results

We start by defining the supply patterns for Supplier F and Supplier W. In the case of Supplier F we simplified the plant to supply a constant and highly predictable power output, mirroring a fossil fuel plant. On the other hand, Supplier W has been modelled using a Weibull distribution with a probability distribution function as shown in [START_REF] Gode | Allocative Efficiency of Markets with Zero-Intelligence Traders: Market as a Partial Substitute for Individual Rationality[END_REF]. Where c, the scale parameter, and k, the shape parameter, take values 5.428ms -1 and 1.4128 [START_REF] Qian | Benefits of energy storage in power systems with high level of intermittent generation[END_REF] respectively. The power generated, P (v), by a turbine is not a direct mapping from this distribution. A turbine has a cut-in speed (v cut-in ), below which it will not generate any power; a rated speed (v rated ), at which it produces maximum power; and a cut-out speed (v cut-out ), above which it will not produce power (for safety reasons). Between the cut-in and rated wind-speeds, it is assumed here that the power generated is a linear interpolation between zero and the rated power output as shown in [START_REF] Elexon | The Electricity Trading Arrangements: A Beginner's Guide[END_REF]. For the simulation analysis Supplier W was assumed to own a small wind farm consisting of five turbines. Each turbine is modelled as behaving according to [START_REF] Gode | Allocative Efficiency of Markets with Zero-Intelligence Traders: Market as a Partial Substitute for Individual Rationality[END_REF] and [START_REF] Elexon | The Electricity Trading Arrangements: A Beginner's Guide[END_REF] with no interactions between turbines. MICON turbine specifications [START_REF] Yeh | A Study on Generator Capacity for Wind Turbines Under Various Tower Heights and Rated Wind Speeds Using Weibull Distribution[END_REF] as shown in Table 1 were taken to simulate power output for Supplier W sampled half-hourly over a 24 hour period. This gives the wind generation a more unpredictable production pattern as would be the case when integrating renewable energy to the grid.

f (v, c, k) = k c v c k-1 e -( v c ) k v > 0; c > 0; k > 0 (10)
P (v) =        0 0 ≤ v < v cut-in P rated × v-vcut-in v rated -vcut-in v cut-in ≤ v < v rated P rated v rated ≤ v < c cut-out 0 v ≥ v cut-out (11)
Table 1: MICON turbine parameters

Parameter Value vcut-in 4ms -1 v rated 14ms -1 vcut-out 25ms -1 P rated 200kW

ZIP Performance

We implement the ZIP60 algorithm using a fixed price mechanism with Supplier F as the sole source of electricity. Figure 2(a) shows the demand and supply positions before and after trading for the entire day whilst Figure 2(b) shows the corresponding average price that trades were executed at. This indicates there are two key issues with the simulation, firstly, the fixed price function is very simplistic and allows monopolistic tendencies. Secondly, it indicates a problem with the α measure itself in very uneven market conditions; as long as there is a consistent excess of demand over supply the equilibrium price will favour the supplier. While not shown here, a simulation for only Supplier W showed the same behaviour.

ZIP-260

We first implement the ZIP-260 algorithm with a fixed price function and without the loss-accepting behaviour. Figures 3(a) and 3(b) show that ZIP-260 behaves similarly to ZIP60 when optimised for α which means that by changing the fitness function we have not adversely affected the market mechanism. Figure 4 shows ZIP60's behaviour when optmised for α and σ 2 under a variable pricing function which achieves worse α performance than the ZIP-260 algorithm shown in Figure 5. Having shown that the ZIP-260 algorithm is in fact an improvement on the ZIP60 variant, and that the fitness function σ 2 is preferred to α as it encourages all available units to be traded, we implement the ZIP-260 algorithm as outlined in §3.2 and introduce σ 2 as the fitness parameter as well as a variable pricing function. We examine a system where both suppliers are operating to investigate whether fossil fuels can complement wind in this algorithmic market. Figure 6 shows the supply and demand positions before and after trade has been completed. In this 3.0 shout price q q q q q q q qq qq q bid accepted bid offer accepted offer (a) ZIP 60 behaviour. 3.0 shout price q q q q q q q q q bid accepted bid offer accepted offer (b) ZIP-260 behaviour. scenario we deliberately ensure that there is an excess of supply in the market in order to test the algorithm's ability to distribute all units of supply. Figure 7 shows the trading activity and price equilibria for different trading periods of the system when the probability of accepting a loss (P L ) is set at 0.1. The consumers are constantly shouting zero priced bids which the loss-accepting suppliers are matching. This shows that the consumers are using their collective bargaining power to set the price very low because they have learned that the suppliers will accept it. We then reduce the probability of accepting a loss (P L = 0.001) and observe the trades and equilibria at the same periods, shown in Figure 8. This now shows a more equitable market with the equilibria following the price curve of the consumers.

Analysis

We show that the direct application of automated trading in the traditional sense of profit maximizing is actually not appropriate for electricity markets as it leads to 3.0 shout price q q q q q q q q q q q q q qq q q q q q q q qqq q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q qqqq q q q q q q q q q q q q q qq q q q q q qq q qqq q q q q q q q q qqq qq q q q q q q q q q q q q q q q q q q q q q bid accepted bid offer accepted offer 3.0 shout price q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q qq q q q q q q q q q q q q qqq q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q theoretical actual (b) Equilibira at hour 5. 3.0 shout price q q q q q q q q q q q q q q q q q q q q q q q q q qqq q q q q q q q q q qqq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q qq q q q q qq q q qq q qq q q q q q q q q q q q q q q q q q q q qq q q qq q q q q q q q q q q q q qq q q q q q q qq q q q qq q q q qqq qq q q q q q q q q q q q q q q qq q bid accepted bid offer accepted offer 3.0 shout price q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q theoretical actual (d) Equilibria at hour 19.

Fig. 7: Joint supplier scenario where P L = 0.1 monopolistic behaviour by the suppliers. The imbalance of consumers and suppliers seriously affects the performance of the algorithm as the suppliers display monopolistic tendencies. To overcome this issue, we introduced a notion of unit variance as a fitness function which optimises for an equal distribution of outstanding demand units across all the consumers which allows for all available supply units to be allocated, as shown by Figure 1. We compare the performance of the new ZIP-260 algorithm with ZIP60 and see that both measures of performance (α and σ 2 ), are greatly improved which can be observed by comparing Figures 4 and5. Unfortunately, when this is implemented in a joint supplier scenario with the probability to accept a loss set at 0.1 (P L = 0.1), we see the consumers learning to abuse this loss making behaviour by consistantly shouting zero priced bids. This indicates that the collective bargaining power can have a large effect such that the suppliers are not being compensated at all for the electricity they produce. This can be explained by considering the cumulative effect of the learning algorithm used in the price update for the agents. An increased acceptance of lower prices on the market causes consumers to update their prices towards that lower price. This is compounded by the frequency with which the suppliers accept loss making prices, until a price of zero is reached as shown by Figure 7. This effect can be alleviated by reducing P L to 0.001, as shown in Figure 8 where the bid prices now follow a similar pattern to the consumers' variable 3.0 shout price q q q q q q q q q q q qqq q q q q qq q q qq q q q q q q qq q q q q q q q q q q qq q q q q q q q q qq q q q bid accepted bid offer accepted offer 3.0 shout price q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q theoretical actual (b) Equilibira at hour 5. 3.0 shout price q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q qq q q q q q q q q q qq q q q q bid accepted bid offer accepted offer 3.0 shout price q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q q theoretical actual (d) Equilibria at hour 19. price curves. This highlights a high sensitivity to P L which may indicate that it is an unsuitable solution or this value should be allowed to evolve over the trading period.

Conclusion

Using ZIP like algorithms directly leads to non-functioning and undesirable market effects as the ratio of consumers to suppliers is uneven. To allow for this imbalance we have introduced a notion of loss-acceptance in the suppliers as well as aiming to minimise the unit variance of un-matched demand across all consumers. It was hoped that these additions would allow market prices to emerge based on the level of supply in the market which varies due to the wind powered supplier in the joint supplier scenario. However, we found that the market now becomes sensitive to the probability of loss acceptance by the suppliers where a value of 0.001 was found to promote fairer trading prices by not promoting collective bargaining power by consumers. Based on the extensive simulations and scenarios we have investigated we have to conclude that neither ZIP or ZIP-260 is, at this stage, a suitable candidate for algorithmic trading of electricity in real time. However, as we have noted, there are signs that a fair market mechanism can be created but this requires further research and testing on a wide variety of market situations.

  After simulation with loss accepting algorithm.

Fig. 1 :

 1 Fig.1: Distribution of units to agents before and after the simulation runs for a single day, with and without a loss accepting algorithm. Positive units indicate an excess of supply whist negative units indicate an excess of demand.

  Equilibrium prices-fossil fuel.

Fig. 2 :

 2 Fig. 2: Units traded and average trading price over one day.

Fig. 3 :

 3 Fig. 3: The trading activity for hour 12 of the fossil fuel market for both ZIP60 and ZIP-260 algorithms.

  α measure for fossil fuel market.

  σ 2 measure for fossil fuel market.

Fig. 4 :

 4 Fig. 4: Performance of the ZIP60 fossil fuel market for the two fitness measures under variable pricing.

Fig. 5 :

 5 Fig. 5: Performance of the ZIP-260 fossil fuel market for the two fitness measures under variable pricing.

Fig. 6 :

 6 Fig. 6: Supply and demand positions of the joint market shown before and after trading has occured.

Fig. 8 :

 8 Fig. 8: Joint supplier scenario where P L = 0.001.