Céline Jullien
email: celine.jullien@grenoble-em.com.

Virginie Pignon
email: virginie.pignon@edf.fr

Stéphane Robin
email: robin@gate.cnrs.fr

Carine Staropoli
email: carine.staropoli@univ-paris1.fr.

Coordinating cross-border congestion management through auctions: An experimental approach to European solutions

Keywords: auctions, congestion management, electricity markets, experimental economics enchère, gestion des congestions, marchés de l'électricité, économie expérimentale JEL codes: C92, D43, D44, D49

Competition among producers within an integrated electricity system is impeded by any limited transmission capacity there may be at its borders. Two alternative market mechanisms have recently been designed to organize the allocation of scarce transmission capacity at cross-border level: (i) the "implicit auction", already used in some countries, and (ii) the "coordinated explicit auction", proposed by the European Transmission System Operators (ETSO) but not implemented yet. The main advantage of the explicit auction is that it allows each country to keep its own power exchange running. In the European institutional context, this is seen as a factor of success of a market reform, although the explicit auction (not coordinated) is known to be less efficient than the implicit mechanism. The addition of a coordination dimension in the explicit auction is intended to solve problems of international flows. We use an experimental methodology to identify and compare in a laboratory setting the efficiency properties of these two market mechanisms, given a market structure similar to the existing one in continental Europe, i.e. a competitive oligopoly. Our main result highlights the inefficiency of the coordinated explicit auction compared to the performance of the implicit auction, measured in terms of both energy prices and transmission capacity allocation. We suggest that the poor performance of the coordinated explicit auction in the laboratory is due to the level of individual expectations about both energy and transmission prices that the mechanism demands. One solution to resolve this problem when the mechanism is implemented in the field would be to design an additional and secondary market for "used" transmission capacity.

INTRODUCTION

The Internal Electricity Market (IEM) targeted by the 1996 Directive 96/92/EC is currently still far from completion, for Europe is still fragmented into a number of regions, each with its own transactional arrangement and organized marketplace for wholesale electric power. However, the recent coupling and mergers of power exchanges -as for example the German EEX Power Spot and the French Powernext Day-Ahead within EPEX Spot in 2009, the trilateral coupling of the EPEX Day-Ahead with the Day-Ahead markets of the Netherlands and Belgium, or the Swiss-German Eurex and Slovenian Borzen in 2008together with the political pressures from the Commission (European Commission, 2009) to organize the IEM, can be considered as efforts towards a more effective integration.

The creation of the IEM depends heavily on efficient coordination between national markets. One condition to ensure efficient coordination is to make sure that, as far as possible, electricity flows between Member States as easily as it currently flows within them (European Commission, 2004). This requires sufficient interconnections and adequate and efficient cross-borders congestion management schemes. At present, the main obstacle to integration is precisely the scarcity of cross-border transmission capacity across Europe. This situation leads to cross-border congestions and their related externalities: uncertainty, risk and market power problems. To mitigate these problems, the EU supports measures to increase transmission capacity while at the same time looking for efficient cross-border congestion management methods. In this paper we focus on the second issue, and examine market design mechanisms proposed to improve the management of cross-border congestion.

In the June 2003 regulation (EC) n°1228/2003 of the European Parliament and the Council on the "Conditions for access to the network for cross-border exchanges in electricity", the Commission laid down preliminary guidelines for the implementation of cross-border congestion management methods. The guidelines stipulate that these management methods should include "non-discriminatory market-based solutions that give efficient economic signals" (European Commission, 2003). To conform to the European regulation, the administrative methods traditionally used in Europe and based on pro-rata or first-come-first-served rules -i.e. typically non-market-based methods -were progressively replaced by market-based methods for day-ahead allocation in July 20041 . These are flowbased zonal methods2 which can rely on two types of auction mechanism: the implicit auction and the explicit auction3 .

The first auction mechanism is called "implicit" as the available transmission capacities are implicitly taken into account by the market operator in the selection of energy offers. It is a pricing mechanism derived from the early work on nodal pricing by Bohn, Caramanis and Schweppe (1984) and Hogan (1992). The implicit auction is currently applied in Europe to allocate transmission capacity among the Nordic countries4 (known as the "market splitting" method5 ), in the trilateral coupling of the Netherlands, Belgium and France (TLC), in the MIBEL market covering the Iberian Peninsula, and within the Italian market which is splitted into several internal zones. It already reflects a certain degree of integration, and is particularly appropriate for day-ahead capacity rights, since the flow is based on the dayahead market data from two interconnected markets. However the main argument against this method in the European context is that the meshing of the continental grid makes market splitting, as well as other related methods, inapplicable without the merger of power exchanges, which is quite unrealistic from an institutional and political point of view. As Ehrenmann and Smeers (2005) explain, the existing differences in the architecture of electricity markets in European neighbouring countries (including pool structure as well as bilateral markets now in place and the wide diversity of market rules) render integration currently difficult if not impossible. Hence, the existence of various system operators, each responsible for one control area, politically and institutionally constrains the generalization of the implementation of the implicit auction. Finally, it is worth noting that there are also technical obstacles, but these are beyond the scope of this paper. The only feasible and plausible solution in the short term is thus to link zonal markets, but that is not conducive to integration and the creation of the IEM.

In the second auction mechanism, called the explicit auction mechanism, transmission capacities are auctioned separately and before the allocation of wholesale energy. Explicit auctions are increasingly used among European countries (ETSO, 2006). They are particularly appropriate for the allocation of long-term capacity rights (sold at yearly or monthly auctions). In practical terms, they do not require a single power exchange as in the case of the implicit auction. However, as in California, it is up to the system operator to coordinate the physics of the problem after transmission and generation contracts have been signed ex ante by all the private scheduling coordinators. This coordination problem between system operators is typically not taken into account in the explicit auction mechanism, and therefore does not favour market integration. The so-called "explicit coordinated auction" mechanism has been proposed by European system operators precisely to offset this lack of coordination in the case of cross-border flows.

The spirit of the "coordinated explicit auction" mechanism was initially proposed by the Florence Regulatory Forum established in 1999. It was seen as a way to overcome political and institutional obstacles to coordination and integration of European markets. This mechanism was subsequently adopted by the European Transmission System Operators (ETSO) in 2001. In the ETSO's proposal, the auction is coordinated, in the sense that, instead of having an auction for transmission capacity at each cross-border zone (with the various system operators in charge of coordinating the physics), the transmission capacities are all auctioned off in the same process (especially across zones characterized by strong loop flows). In other words, the available transmission capacities are all covered by a single auction. At the individual level, this centralized mechanism should limit uncertainties over the allocation and prices of transmission rights, and therefore reduce the risk of productive inefficiencies. At the aggregate level, a better coordination between zones should enable a better allocation of transmission capacity (and a better estimation of capacities that could be auctioned in a secure and reliable way). Overall, the aim of this proposal is to achieve the full potential of the existing European interconnected network, through an adequate cross-border congestion management scheme, while each area may keep its own rules to manage its internal problems. In a nutshell, this solution seems to be more "institutionally friendly".! Since the ETSO's proposal, the efficiency conditions of the implementation of the coordinated auction mechanism in Europe has been studied. However, it has not yet achieved political or scientific consensus, and discussions are still on-going regarding both its efficiency in managing cross-border congestions and its properties in terms of European market integration. For instance, the Third Legislative Package approved in April 2009 recommends use of the coordinated mechanism notably for long-and medium-term allocation (EU, 2009)6 . Our contribution seeks to participate in the on-going debate on cross-border management solutions and to further investigate the efficiency of the coordinated auction mechanism.

From a theoretical point of view, under the assumption of benevolent generators that truthfully reveal their marginal costs, it is demonstrated that both mechanisms -the coordinated explicit auction and the implicit auction -should lead to: (i) an efficient allocation of available transmission capacity, and (ii) an efficient production in which the least-cost generation units are successively required to produce, given the capacity constraints of the network. However, as Pérez-Arriaga et al. (2005) point out, this analysis is based on perfect and rational individual expectations, which is a strong behavioural hypothesis. Ehrenmann and Smeers (2005) emphasize how the perfect anticipation assumption strongly constrains the model, while the aggregation of the network limits the results (to keep traders from investigating the intricacies of the electrical network).

From an empirical point of view, the international experiences of a separation of the energy and transmission markets underlying coordinated auction have raised some doubts about its efficiency (Ehrenmann, Smeers 2005), while the coordinated explicit auction -as proposed by ETSO -has never been applied. Consequently, there is a lack of data to be able to assess its efficiency.

In this article we use the experimental methodology to collect data enabling us to assess whether and how the implicit auction and the coordinated explicit auction mechanism succeed in efficiently allocating scarce transmission capacity, while reducing generators' ability to exercise market power. Part of our contribution is methodological: in the laboratory setting we recreate a reasonable level of complexity enabling us to analyze in depth the two market mechanisms currently used or under scrutiny in Europe. We construct an experimental environment, using smart computer-assisted markets with a three-node network and its consequential constraints like loop flows and congestions, including the stochastic nature of the loads on the lines, the associated need to respect the physical constraints in the network, and the location variability of transmission losses. Our experimental design reproduces an industry structure akin to the current one in Continental Europe: a competitive oligopoly where major players are emerging, each of which is relying on a geographical stronghold and is present both at the production and at the supply level. Actually, in Europe there are neither "pure" generators nor "pure" suppliers in the electricity industry. 7 We reproduce these individual characteristics in our experimental design by endowing "generators/suppliers" with both supply and demand functions which implicitly define individual net positions in each market as net buyer or net seller.

We examine the effects of the two auction mechanisms -the implicit auction and the coordinated auction -on the pattern of both energy prices and capacity prices, and on the transit volume. Our main result highlights the superiority of the implicit auction mechanism over the coordinated explicit auctions. The coordinated explicit auction is inefficient in terms of global efficiency, and in terms of allocation of transmission capacity. Energy prices are highly volatile in the coordinated auction treatment and the transmission capacities are inefficiently used.

The paper is organized as follow. In Section 2, we present the experimental design and procedure, i.e. the characteristics of the electric power network (nodes, transmission capacity and power flows), the characteristics of the market participants (portfolio of generation units, individual supply and demand functions, and localization in the network), and the market institutions (the implicit auction and the coordinated explicit auction). In Section 3, we present our results on the global efficiency of the two auction mechanisms, the patterns of market prices for transmission capacity and energy, and the management of congestions. Section 4 concludes.

EXPERIMENTAL DESIGN AND PROCEDURES

Our experimental design seeks to represent the main features of the continental european market, in a laboratory setting. In terms of market structure, the experiment reproduces the same magnitude of market shares of continental european generators, and their localization in the network, which together characterize potential market power. The network configuration reproduces the existence of capacity limitations, but we do not take the intracountry situations into account (in particular, we do not consider internal congestions). We first present the electric power network, and then turn to the description of the two market mechanisms.

The network

The network is modelled in the experiments as a three-node network with loop flows. In our model, a node refers to a country. The three nodes are called A, B and C. The transmission lines between nodes are defined by: (i) their maximum capacities -50 units of energy between A and B, 30 between A and C, and 30 between B and C -; and (ii) the power flows in the network, given the Power Transfer Distribution Factors (PTDF) matrix. These PTDF give the flows through the lines A-B, A-C and C-B respectively, resulting from injections at all nodes of the network and withdrawals at node C (taken here as the "hub"). The market structure in the experiments consists of 4 generators (G1 through G4 in Figure 1), unevenly located in the network. Generator G1 is dominant at node A, while generator G4 is dominant at node C, and generators G2 and G3 are together dominant at node B. At each node, a generator is endowed with an individual supply function and an individual demand function. These demand and supply functions are designed in order to model individual willingness to buy or to sell energy in the three different markets. The inverse demand function gives the limit price under which a generator is willing to buy energy.

Symmetrically, the inverse supply function gives the limit price above which the generator is willing to sell energy. Limit prices reflect the opportunity cost for using production facilities and the commitment to a must-serve demand. For instance, a generator with a must-serve demand constraint is a potential buyer in the market at any price below its own production cost. Symmetrically, a generator with an excess of production capacity is a potential seller at any price above its production cost. Demand and supply functions are reproduced in the experiment according to the redemption-value theory principle (Smith, 1976). Accordingly, a generator in the laboratory is informed about the value (redemption value) it receives for each unit it buys and the value (marginal cost) it supports for each unit it sells. Table 2 reproduces as an example the redemption values and marginal costs of Generator 1 at node B. The market demand and supply for energy at each node is the aggregation of individual demand and supply functions. The market demand is cyclic, from both an individual and an aggregate point of view with two levels, namely the peak-load and base-load levels8 .

Aggregate demand and supply at each node for, respectively, peak-load and base-load levels are described in Figures 2 and3. The optimal flows in the network and the competitive equilibrium market prices in these two situations are described in Figure 4 below. These equilibrium prices are computed under

the assumption that at each node each generator submits its limit prices to buy and sell. For base-load and peak-load periods, we compute the maximum global surplus by summing the four generators' profits plus the congestion rent at the equilibrium. The value of the maximum global surplus is 5,170 ECU for base-load periods and 2,830 for peak-load periods 9 .

Finally, the information released to all participants during the course of the experiment concerns the basic characteristics of the network, that is, the PTDF-matrix and the maximum capacity of each line (both held constant across sessions), the market prices at each node, as well as the flows on each line as an historical informational feedback.

The market institutions

In the following subsections we present the two alternative market institutions, namely, the implicit auction and the coordinated explicit auction, as we modelled them in the lab. The central feature of the auctions that we want to test is the sequence of events: simultaneity of allocation of transmission capacity and energy in the implicit auction versus the sequential allocation of transmission capacity and energy in the explicit auction. We provide rationale in the section for the structures of energy markets and identify which features of the market are going to be tested.

The implicit auction

The implicit auction consists in simultaneously allocating transmission and energy capacities, in respectively a centralized and a decentralized way. Figure 5 represents the sequence of events and the information structure for the implicit auction.

Participants may submit offers to either sell or buy units of electricity. Each offer is made for a dedicated node, and is composed of a unit price/quantity pair. We use an optimization algorithm to determine the set of offers that maximizes the total surplus, and that is compatible with two constraints: (i) the aggregate supply must equal the aggregate demand of the whole system, and (ii) the transmission constraints (capacities, flows and loop-flows)

have to be respected 10 .

9 These values are used as a reference to assess the efficiency of the allocation obtained during the experiment. If the computed global surplus equals these values, this corresponds to an efficiency rate of 100%. 10 The bidding process and the optimization algorithm are detailed in Appendix 1.

Fig. 5 -Sequence of events in the implicit auction

If no congestion occurs, then the selection process simply follows the merit order: offers are selected according to the increasing order of unit prices to equalize the market supply and demand. In this case, the energy prices at the three nodes are equal. If congestion occurs, then the merit order is corrected according to the network constraint and the localization of offers.

In practice, this implies that some offers that would have been retained without any congestion are finally not accepted; while others that were too high to be retained at first glance will finally be accepted. Energy prices at each node are obtained using the shadow prices computed from the Lagrangian maximization program. The bidding constraints associated with the congested transmission line give the price of the congestion. The marginal price of electricity at each node is then inferred from this price through the PTDF-matrix 11 .

Each generator receives private information concerning the acceptance rate of each of its offers, along with public information about the price at each node and the flows on each line. The profits of a generator for a period equal the sum of the profits it is making at each node. At a given node, its profits correspond to the sum of the redemption values of the units it owns and the revenue from the units it has sold.

The coordinated explicit auction

One of the main features of the coordinated explicit auction is that it affords any generator in a given power network the opportunity to buy and sell energy at each node of the 11 The calculation of the energy prices from the shadow prices computed from the Lagrangian of the maximization program is detailed in Appendix 1.

Generators submit at each zone: offers to sell and buy energy

Multi-zone merit order under network constraints: Uniform-price sealed-bid auction Generators obtain market information: Energy offers accepted, prices and flows Time Generators derive profits network, even if it is (or not) physically producing energy at that node. Since the auction for transmission capacity and energy are clearly separated, the only condition for a generator who wishes to sell at a node where it is not present, is to have bought the corresponding transmission capacity to transport energy to this node prior to the energy auction. Figure 6 represents the sequence of events in the coordinated explicit auction, as modelled in the experiment.

Fig. 6 -Sequence of events in the coordinated explicit auction

The coordinated explicit auction is a two-stage mechanism. In the first stage, a uniformprice auction is organized for the allocation of the sole transmission capacity between nodes in the network. In the second stage, an energy market opens at each node. These energy markets at each node work independently of one another, using a uniform-price mechanism to equilibrate the corresponding nodal market supply and demand. In other words, this second stage works as a procurement auction, run to allocate the right to inject energy into or withdraw it from the network.

A crucial characteristic of the coordinated explicit auction considered in the ETSO proposal is the "must use" attribute of the capacity allocated to a generator. In the capacity allocation stage, generators bid for "obligations" rather than "options" to use transmission capacity. Obligations are needed to allocate the maximum transmission capacity of a line

Stage I: Auction for transmission capacity

The first stage of the coordinated explicit auction is the allocation of the existing transmission capacity. The participants bid to buy only transmission capacity that are sold by a factitious central auction house on the basis of the information given by the transmission system operators. At this stage, each participant is allowed to submit bids to buy a right to use transmission capacity from one node to another node for one period. The proposal is thus defined by the injection node, the withdrawal node, the amount of energy units transmitted, and the per-transmission-capacity unit price. The bidders identify the line as well as the direction of the flow.

The auction for transmission capacity ends before the starting of the auction for energy.

Consequently, the bids for transmission capacity depend on the market participants' anticipations of energy market prices.

To allocate transmission capacity, a uniform-price sealed-bid auction is used. Given the received bids, and taking into account the network constraints, the central auctioneer determines which bids will be accepted and the price paid for them. The selection of the bids and the determination of the equilibrium price result from the maximization of the profits from the auction under the transmission constraints. The transmission capacity should be 12 The netting of the flows is automatically taken into account in the implicit auction through the optimization program and the PTDF. Since in the explicit auctions the market participants bid for transmission capacities for one zone to another, we have to assume that they bid for obligations so that they can use the same amount of capacity as with the implicit auction. Otherwise the implicit auction would de facto be more efficient than the explicit one. 13 For example, a generator who has bought capacities to transport units from zone A to zone C has to inject -to produce or to buy -the adequate quantity in zone A at any cost, and to withdraw -to sell or use -the same amount in zone C even if it yields zero revenue. At the extreme, to respect transmission commitment, the generator who failed to buy the adequate quantity at the exportation zone could suffer important production costs with no revenue in return. allocated to those who value them the most, under the constraint that the amount allocated at the end of the process should not exceed the maximum capacity of each line (taking into account both the flows and counter flows). Given that the transmission rights are directional, each line is characterized by a double capacity limit constraint. We use an optimization algorithm to determine the set of bids that are finally accepted 14 . If there is no congestion, all bids are accepted. If one or more congestions occur, some bids have to be partly accepted and even rejected.

At the end of the auction process, each generator receives private information concerning the acceptance rate of each of its bids, and public information on the price and the flows of each directional transmission line, and on the congestions. Prices for transmission rights are obtained using the shadow prices computed from the Lagrangian maximization program. The bidding constraints associated with the congested transmission lines give the price of the congestion. The marginal price of transmission rights for each line is calculated by multiplying the shadow prices by the PTDF factor 15 . In general, to accept or reject part of a bid, the software calculates the price at which each generator agrees to pay for using the congested line. It then gives priority to those bids that value the congested line most. It orders bids by increasing prices, which have been normalized by the Power Transmission Distribution Factors (PTDF) of the concerned injection node and for the requested transmission line. The software accepts bids until all the transmission capacities are exhausted (after checking that it does not create any additional congestion). The price that each generator has to pay equals the last bid accepted by the auctioneer, weighted by the PTDF of each of its bids on the constrained line. At the end, a generator pays a price for transmission that corresponds to its contribution to the congestion, related to the flow that it wants. If the flow contributes to relieving the congestion, the price the generator has to pay is negative i.e. it is paid for its transmission. If the allocation implies no congestion, no generator is charged for the capacity allocated.

Stage II: Auction for energy

The second stage consists of three independent and simultaneous energy markets, one for each node. Generators are allowed to participate in the three auctions simultaneously.

However, they expose themselves to considerable costs if they do not own the corresponding 14 The bidding process and the optimization program are set out in Appendix 2. 15 The calculation of prices for transmission right from the shadow prices computed from the Lagrangian of the maximization program is detailed in Appendix 2. transmission capacity for the unit that they are selling in any market where they are not present. This design features aims at capturing the "must-use" rule.

The three energy auctions are uniform-price sealed-bid auctions, where the offers (either to sell or to buy) are composed of a price/quantity of energy pair. The allocation of energy through each auction results from the maximization of the total surplus. It therefore follows a simple merit order (the offers are selected according to the increasing order of prices to meet the must-serve demand of the node considered).

At the end of the three energy auctions, generators receive the information concerning the acceptation rate of each of their offers, and public information is given on the market prices at each node.

The profits of a generator for a period are composed of three elements: (i) the sum of the gains16 and losses from the use of transmission capacity, (ii) plus the sum of the profits and losses from market exchanges on the three energy marketplaces, (iii) plus the sum of the redemption values of the units consumed minus the marginal cost of the units produced at each node, subject to the final individual injections and withdrawals resulting from the transmission commitments and the energy market transactions.

RESULTS

The experiments were run in the experimental laboratories of the GATE (Lyon) and of the GAEL (Grenoble), using a dedicated market software developed with the experimental software Regate, the Internet-Based Software for Experimental Economics of the GATE (Zeiliger 2000). Undergraduate students were recruited from a business school, an engineering school and economic departments of the universities of the two locations.

Given the relative complexity of the experimental design, we organized each experimental session over two days, lasting two and a half hours on each day. The first day, students were taught the rules and trained with the instructions. The second day, they participated in the experimental session itself, taking the results into account for the payment.

The data and results reported below were collected from these second-day sessions.

In the lab, the duration of one period of an implicit session is shorter than one period of an explicit session 17 . This explains why the number of periods per session collected for the explicit treatment in our early experiments was lower than for the implicit treatment. In order to control for this difference, we conducted four additional explicit treatment sessions with extended sessions lasting at least 20 periods. Finally, we ran sixteen sessions in total, using the two market mechanisms as treatment variables. We have six independent findings for the implicit mechanism and ten for the explicit mechanism (see Table 3). Subjects were paid a !20 fixed payment for the "learning session" and, on average, !26 for the "data session". We report our results as a series of five findings, one related to the global efficiency of the system (i.e. the evaluation of the global surplus) and four concerning the economic performance of each auction design in terms of energy prices and flows.

Global efficiency

The efficiency is equal to the ratio of the observed global surplus and the theoretical maximum global surplus. For the implicit treatment, we calculated the global surplus by summing the four generators' profits plus the congestion rents in the implicit treatment. In the explicit treatment, the global surplus is the sum of the four generators' profits plus revenues 17 A period of coordinated explicit auction with a sequence of two interdependent auctions takes more time than a period of implicit auction with a single auction. obtained from the sale of transmission rights. We observe extensive individual losses during some periods conducted under the explicit treatment. In order not to sidestep the analysis in favour of the implicit treatment, we decided to reduce negative efficiency rates to zero. We present the results in two graphs: the first one is based on the sessions lasting 14 periods, while the second one is based on the sessions lasting at least 24 periods 18 . 18 Although all sessions lasted for at least 14 periods, only 9 lasted for 24 periods. These longer sessions represent a reduced sub-sample of our observations and should therefore be treated apart.

The implicit auction appears as the most efficient mechanism (Fig. 7). For the sessions conducted under the implicit treatment, efficiency increases rapidly and remains close to the 90% level. Overall, we observe only 5 periods, out of the 166 periods collected, which have a zero or negative efficiency rate whereas for 38 periods the efficiency rate is over 95%. In the sessions of the explicit treatment, the observed efficiency rate is significantly lower and erratic (especially for the session lasting over 24 periods). Negative global surplus and zero efficiency are even observed in 25 of the 187 periods collected. The mean efficiency rate for the coordinated explicit auction treatment over all the periods is 50% whereas the figure obtained for the implicit auction treatment is 81%.

Finding 1: The implicit auction is more efficient than the coordinated explicit auction.

Evidence: In all sessions and all periods taken together, the mean global efficiency for the implicit treatment is 81% against 50% for the explicit treatment.

• In the implicit auction treatment, the global surplus increases with the number of periods, which suggests that generators are learning how to be more efficient. Furthermore, the efficiency is higher for peak periods.

• In the coordinated explicit treatment the evolution of the efficiency rate is erratic and it is not possible to conclude on any learning effect, even when taking into account the session with up to 24 periods.

We use the following linear panel data model as the basis for a quantitative support to Finding 1. The model explains the efficiency of a session as a function notably of the level of demand and the dynamic convergence toward 100% efficiency. The sixteen independent sessions are modelled as random effects . 19 By definition, the efficiency indicator is limited at the 100% level. Nevertheless, we observe no specific concentration in the distribution of our data and decided not to use a model for limited dependant and qualitative variables.

! Eff it = " 0 + " 1 D it DH + " 2 D it Exp + " 3 t 2 + # it

Table 4 -Estimates of the linear model for efficiency (using between-effect specification)

Table 4 reports the estimateS of the linear model for efficiency. The coordinated explicit treatment significantly contributes to reducing the efficiency. The loss of efficiency is estimated at 32%. The efficiency observed in peak-load periods is significantly greater than that observed in base-load periods (10.6%). Efficiency increases significantly as the periods are repeated. This could be interpreted as a learning dynamic. Learning is nevertheless minimal compared the efficiency gap between coordinated explicit and implicit auction.

Even in this experimental environment favourable to learning (at least 24 periods), it could take very long before explicit auctions become as efficient as implicit auctions. Note that the experimental environment is particularly favourable for learning as all variables are stable from one period to another. We can anticipate that observations under a more unstable environment would reinforce our conclusion about the superiority of the implicit treatment for efficiency.

These differences in efficiency between the two treatments can be explained by the joint effect of two factors: the evolution and convergence of energy prices (3.2) and the flows between nodes (3.3). We will now analyze these two effects separately.

Energy prices

The market prices observed at each node are compared to the competitive equilibrium (CE) price computed when assuming that each generator offers energy at a price equal to its marginal value with the implicit treatment. Average distance from CE prices and standard deviations by period and by treatment are represented in Figures 9, 10 for node A, 11 and 12 for node B and 13 and 14 for node C, for the 14 firsts periods with all the sessions. The differences between treatments are unambiguous. The dispersion of energy prices and the volatility of prices from period to period rapidly decrease in the implicit auction sessions: there is a strong convergence toward a single, specific price at each node. We find higher price dispersion between sessions with the coordinated explicit auction and higher volatility from period to period in each session.

"#$! "%$! %$! #$! &$! $! &$! %$$! %&$! %! #! &! '! (!%%! %#! !"#$%&'()*+,-)./) 0+"'() 1$%&2%+2)2(3"%$",&) "#$! "%$! %$! #$! &$! $! &$! %$$! %&$! %! #! &! '! (!%%! %#! !"#$%&'()*+,-)./) 0+"'() 1$%&2%+2)2(3"%$",&) ")$! $! )$! *$! +$! $! &$! %$$! %&$! %! #! &! '! (!%%! %#! !"#$%&'()*+,-)./) 0+"'() 1$%&2%+2)2(3"%$",&) ")$! $! )$! *$! +$! $! &$! %$$! %&$! %! #! &! '! (!%%! %#! !"#$%&'()*+,-)./) 0+"'() 1$%&2%+2)2(3"%$",&) "#$! "%$! %$! #$! &$! $! &$! %$$! %&$! %! #! &! '! (!%%! %#! !"#$%&'()*+,-)./) 0+"'() 1$%&2%+2)2(3"%$",&) "#$! "%$! %$! #$! &$! $! &$! %$$! %&$! %! #! &! '! (!%%! %#!

!"#$%&'()*+,-)./) 0+"'() 1$%&2%+2)2(3"%$",&)

Energy prices observed with the implicit treatment converge towards a single equilibrium price for each node and for each demand level. The estimated prices of convergence are statistically significant and have a small standard deviation. The price of convergence for node A and base-load periods equals 59.7 and is significantly higher than the competitive market price of 50. Likewise, the price of convergence for node C and base-load periods equals 102.1, that is, less than the competitive market price of 108. These observations suggest the use of market power from generator G1 at node A and generator G4 at node C. Apart from these two situations, the observed market prices converge to the competitive market price.

Finding 3: Energy prices in the coordinated explicit auction sessions fail to converge to a single equilibrium price.

The coordinated explicit auction does not induce price stability in the system. Figures 10, 12 and 14 show price dispersions between sessions. These price dispersions are significant. For instance, for the 14 th period, we observe a standard deviation of 90 ECU at node A, 126 ECU at node B and 28 ECU at node C. These dispersions between sessions do not disappear with period repetitions. The volatility of energy prices has a direct consequence on the efficiency of the auction for transmission capacity. An accurate valuation of these capacities requires stable energy prices at each node of the network. Without this stability generators cannot correctly assess the inter-node market price differences, and therefore can hardly bid appropriately during the transmission auction. As a consequence, the energy price instability leads to a misallocation of transmission capacity.

Flows, congestions and transmission prices

Given the market structure at each node and maximum capacities for each line, line AC appears as the critical resource in the search for the optimal energy allocation through the three-node network. We can therefore expect permanent congestion on this line with an efficient allocation of transmission capacity. Rates of congestion reported in Tables 6 and7 show a significant difference in the allocation of transmission capacity between sessions with implicit auction and with coordinated explicit auction. We observe that transmission lines are saturated with both mechanisms especially during peak-load periods when the demand on the network is greater. During base-load periods, for the critical line AC, congestion is observed in almost every period in the implicit treatment. In the explicit treatment, congestion rate of line AC is above 75%. The capacity of line AC is thus not fully allocated for one period out of four. These results show that, under explicit treatment, there is an under-use of the network, with inadequate flows and at least efficiency waste.

Finding 5. Transmission prices exhibit high dispersion throughout the repetition of periods in the coordinated explicit auction sessions

The price dispersion between and within sessions is such that a structured analysis of the price convergence cannot be used. We thus restrict our study to a descriptive analysis. We find that prices are lower than competitive equilibrium prices for transmission capacity at each node and for both base-load and peak-load periods. This result is a direct consequence of an under-use of the transmission capacity, for the price of transmission capacity is reduced to zero in periods without congestion. The standard deviations as the maximum and minimum values indicate that the prices are spread over a wide range of values. These prices are highly volatile and this volatility does not decrease with period repetition.

CONCLUSION

Using the experimental methodology in the laboratory setting, we tested and compared the efficiency of two alternative cross-border congestion management methods for electricity networks. Compared to the implicit mechanism, the coordinated explicit auction reveals its relative inefficiency in the laboratory, with mispricing and misallocation through the sequence of auctions. This is due to the necessary "must use it" rule: once bought, the transmission capacities have to be used otherwise there is a high penalty. Given this rule, a generator could have the incentive to sell energy at a very low price or to buy energy at a very high price to be able to meet its commitment. Price volatility on energy markets is an immediate consequence of the "must use rule" that makes it difficult for generators to accurately assess the inter-node market price differences, and therefore to bid efficiently during the transmission auction. It can consequently destabilize cross-border flows compared to the optimum flows and in return, destabilize the energy markets.

Our results provide evidence that the implicit auction is more efficient than the coordinated explicit auction for the allocation of both transmission capacity and energy. They contribute to the current discussions on cross-border congestion methods. They show that even in a simple environment such as the one we created in the laboratory, subjects are not able to correctly anticipate what will happen in the energy markets with the coordinated explicit auction, and therefore do not individually take the right decisions in the capacity market.

One explanation for this difference is the level of individual expectations that a subject needs in the experiment. In the coordinated explicit auction, individuals have to form expectations about both the transmission prices and the three energy market prices. The transmission prices depend on individual expectations about future energy prices, and in a repeated environment the energy prices in turn affect expectations about future individual decisions on transmission capacity. Overall, in the laboratory setting, the experiment reveals that even in longer sessions, individuals are constantly learning throughout the repetition of periods, collectively experiencing a "trial and error process" regarding their expectations of others' behaviors. The laboratory experiments suggest that the learning process is long and demanding at the individual level. Complementary results using simulation models on a much longer timeline should help to shed light on the timing of the learning process. Our findings furthermore suggest the need to design and add rules to accelerate the learning process and thereby improve the efficiency of the coordinated explicit auction. We suggest that the addition of a secondary market on transmission capacity would operate as a way to price and value individual and collective over-investment or under-investment in transmission capacity.

Another suggestion would be to add the possibilities to sell or to buy back transmission capacity to/from the system operator, adding a price corridor for transmission capacity to buy or to sell in order to give generators the financial incentives to do so.

The introduction of the coordinated explicit auction however still raises many practical and institutional issues in Europe. Together with efficiency issues, they seem to have condemned the coordinated explicit auction for the IEM. Recent propositions are oriented more towards the implementation of a hybrid implicit/explicit auction (Frontier Economics Limited Consentec, 2004) or towards the use of the implicit auction in its open-market coupling version, as applied between Belgium, France and the Netherlands.

Finally, the economic systems-design experiments presented in this paper raise a general methodological question. As we use the lab to test-bed market mechanisms, trying to integrate a certain level of parallelism with reality (meaning a level of complexity in the electric power case) in order to inform the liberalization process, we rely on experienced students to learn and perform individual decisions. Markets are used as an "impersonal exchange" system (Smith, 2003) to render these decisions as fundamental as we need them to be. Allocations and prices are determined according to the following optimization process.

Constraint (1) indicates that offers can be either accepted or refused, partly or entirely.

Constraint (2) indicates that the total supply has to equal the total demand. Constraints (3) correspond to transmission constraints on each line, in both senses of the flows. Therefore there are two constraints for each line. Prices are the shadow prices computed from the Lagrangian maximization program: Then, the marginal price of electricity at each node can be inferred from and ! µ XY by using the PTDF-matrix.

! L(s,d,µ) = p jX D d jX " p iX S s iX i # j # $ % & & ' ( ) ) X * A ,B,C { } # + µ e d jX j # X * A ,B,C { } # " s iX i # $ % & & ' ( ) ) + µ XY (F XY " F MAX XY ) X =A,B ,C Y =A,B ,C X +Y # with
With C taken as the swing node in our experiment, it results in:

! ˆ p A = µ e + µ XY .PTDF(A, X "Y) X =A,B ,C Y =A,B ,C X #Y $ ! ˆ p B = µ e + µ XY .PTDF(B, X "Y) X =A,B ,C Y =A,B ,C X #Y $ APPENDIX 2

: BIDDING PROCESS AND OPTIMIZATION ALGORITHM FOR THE TRANSMISSION AUCTION OF THE COORDINATED EXPLICIT AUCTION

MECHANISM

For each period, each generator has the opportunity to submit a set of bids to buy transmission rights on the three lines of the network. A bid to buy a transmission right is a price-quantity ordered pair such that is a bid to buy of one generator for a transmission right from node X to node Y, the per unit maximum price that generator agrees to pay, and the transmission capacity from node X to node Y that he requests. We also assume that . Individual demand and supply at node C

!

Figure 1

 1 Figure 1 represents our experimental network.

Fig. 1 -

 1 Fig. 1 -Three-node experimental network with loop flow effects (injection at node A and withdrawal at node C).

Fig. 2 -

 2 Fig. 2 -Supply and demand curves for base-load periods at each node

Fig. 4 -

 4 Fig. 4 -Optimal flows and competitive equilibrium prices for base-load (left) and peak-load (right) periods

Figures 7

 7 Figures 7 and 8 summarize the average global efficiency, and the minimum and maximum levels observed by treatment.

Fig. 7 -Fig. 8 -

 78 Fig. 7 -Average global efficiency (14 periods)

where!

  Eff it denotes the efficiency of session i at period t, ! D it DH a dummy variable which takes the value one for high-level demand periods and zero otherwise, takes the value one for periods under the explicit treatment and zero otherwise.! t 2 , the square of period, fits the dynamics of the convergence to 100% efficiency observed in the data 19 .

Fig. 9 -

 9 Fig. 9 -Node A for implicit treatment Fig. 10 -Node A for explicit treatment

Finding 4 .

 4 The implicit auction leads to a better allocation of transmission capacity in the network, compared to the coordinated explicit auction, which leads to an under-use of the transmission capacity.

  energy at node X (energy prices are shadow prices computed from the Lagrangian of the maximization program).

  s, the set of allocated quantity to sell d, the set of allocated quantity to buy ! µ, the set of Lagrange multipliers ! F XY , the flow on line (X,Y) ! F XY , the maximum capacity on line (X,Y) , the Lagrangian multiplier associated with the system equilibrium constraint and ! µ XY , the Lagrangian multiplier associated with the transmission constraints on line (X,Y). Once the Lagrangian is optimized, we can compute the value of and ! µ XY . The multiplier corresponds to the marginal price for electricity (it corresponds to the marginal price of electricity at the swing node or at any bus if there are no network constraints). The Lagrangian multiplier ! µ XY represents the marginal price associated with the transmission constraints on line (X,Y). It is thus the price to transmit one additional unit of electricity from node X to node Y, or alternatively, the price of the congestion.

!µ,

  the set of Lagrange multipliers ! F XY , the flow on line (X,Y) ! F XY , the maximum capacity of line (X,Y) ! µ XY , the Lagrangian multiplier associated with the transmission constraints for line XY. Once the Lagrangian is optimized, we can compute the value of ! µ XY . The Lagrangian multiplier ! µ XY represents the marginal price associated with the transmission constraints on the line (X,Y). It is thus the price to transmit one additional unit of electricity from node X to node Y, or alternatively, the price of the congestion. Then, the marginal price of electricity at each line can be inferred from ! µ XY by using the PTDF-matrix.! ˆ p AB = µ AB "1/3.µ BC +1/3.µ AC ! ˆ p AC = µ AC "1/3.µ AB +1/3.µ BC ! ˆ p BC = µ BC "1/3.µ AC +1/3.µ ACIf the allocation implies no congestion, generators are not charged for the capacity allocated.

Table 1 -

 1 PTDF matrix for a withdrawal of one unit of energy at node C.

	Interconnection

Table 2 -

 2 Individual demand and supply of Generator 1 at node B for base load period (values are given in ECU, an experimental currency)

	Individual supply function		Individual demand function
	Marginal Cost (MC)		Redemption value (RV)
	From unit: …	To unit ….	UC	From unit: …	To unit ….	RV
	0	30	80	0	70	79
	31	80	130	71	170	0
	81	180	200

  they enable an operator to net the electricity flows running in opposite directions12 . In practice, in the experiment, through individual demand and supply functions, generators are individually penalized if the flows that they have generated do not correspond to the transmission capacity that they acquired in the first stage, i.e. if they use more or fewer capacity than they previously bought13 . A generator which fails to use the transmission capacity allocated to it for the period is penalized through high production costs at the node where it should have had injected energy, and a zero redemption value at the node where it should have withdrawn energy. This acts as a penalty high enough to discourage such a behaviour.

	Generators submit	Generators get market information:	Generators submit offers	Generators
	offers for	Transmission obligations, line	to sell and buy energy	get profits
	transmission	prices and flows
	capacities
				Time
	Multi-line maximization of the profits from the	Independent Merit order for offers in each
	auction under transmission constraints:	zone:
	Line by line uniform-price sealed-bid auction	Three uniform-price sealed-bid auctions

since

Table 3 -

 3 Summary of experiments

	Session	Date	Treatment	Number of periods
	Implicit-S1	25&26 May 2005	Implicit	26
	Implicit-S2	25&26 May 2005	Implicit	26
	Implicit-S3	25&26 May 2005	Implicit	24
	Implicit-S4	8&9 June 2005	Implicit	30
	Implicit-S5	8&9 June 2005	Implicit	30
	Implicit-S6	8&9 June 2005	Implicit	30
	Explicit-S1	6&7 June 2005	Explicit	14
	Explicit-S2	6&7 June 2005	Explicit	15
	Explicit-S3	6&7 June 2005	Explicit	14
	Explicit-S4	15&16 June 2005	Explicit	15
	Explicit-S5	15&16 June 2005	Explicit	17
	Explicit-S6	15&16 June 2005	Explicit	17
	Explicit-S7	12 November 2009	Explicit	19
	Explicit-S8	12 November 2009	Explicit	24
	Explicit-S9	12 November 2009	Explicit	25
	Explicit-S10	12 November 2009	Explicit	26

!

  Eff it = " 0 + " 1 D it DH + " 2 D it Exp + " 3 t it 2 + # it

	Coef	Std. Err.	z	P > | z |
	0. 6632	0. 0485	13.67	0.001
	0.1066	0. 0317	3.37	0.000
	-0.32	0. 0582	-5.49	0.000
	0.0003	0. 0001	5.55	0.000
	353 Obs
	Rsquare overall = 0.3401
	! between-i = 0.0969

Table 6 -

 6 Congestion with implicit treatment

		Base-load period Peak-load period
	Line AB AC BC AB AC BC
	Obs. 83	83	83	83	83	83
	Mean flow 22	30	8	11	29	19
	Congestion observed	17	81	24	0	81	30
	Rate of congestion	21% 98% 29% 0% 98% 36%
		Base-load period Peak-load period
	Line AB AC BC AB AC BC
	Obs. 98	98	98	89	89	89
	Mean flow 11	27	17	4	29	25
	Congestion	5	74	43	1	84	50
	observed

Table 7 -

 7 Congestion with explicit treatment

	Rate of	5% 76% 44% 1% 94% 56%
	congestion

Table 8

 8 reports price levels and dispersions in high-demand and low-demand periods.

Table 8 -

 8 Price of transmission capacity in the coordinated explicit session

	Base-load period (98 obs.)	A!B	A!C	B!C
	Competitive equilibrium price for transmission capacity 22	29	58	29
	Mean price	7.57	19.33	11.73
	Standard deviation	10.10	15.29	8.88
	Maximum price	26	52	60
	Minimum price	-30	0	0
	Peak-load period (98 obs.)	Peak-load	Peak-load	Peak-load
		period	period	period
		(98obs.)	(98obs.)	(98obs.)
	Competitive equilibrium price for transmission capacity	16	32	16
	Mean price	7.62	18.80	11.19
	Standard deviation	7.03	11.76	6.70
	Maximum price	21	42	35
	Minimum price	-18	0	0

  The limitations of the experiments lie in two opposite directions: reducing the level of complexity would render the experiments simpler but lower the informative value of the results, given the specificity of the mechanism studied. On the other hand, increasing the level of complexity seems inappropriate in the laboratory setting, and rather calls for

			APPENDIX 1: BIDDING PROCESS AND OPTIMIZATION ALGORITHM WITH
		IMPLICIT AUCTIONS
			For each period, each generator has the opportunity to submit a set of offers to sell and
		bids to buy. An offer to sell is a price-quantity ordered pair such that	(	p iX S ,S iX	) is an offer to
		sell of one generator at node X, where	p iX S is the unit price at which the generator agrees to
		sell and	! S iX the quantity he proposes to sell. Symmetrically, (	p jX D ,D jX	) is an offer to buy of
		! one generator at node X where	p jX D is the unit price at which the generator agrees to buy and
		!	! D jX the quantity he proposes to buy. For all offers, the submitted quantities have to be
		complementary methods, like agent-based modelling that would improve generalised ! positive ( D jX > 0and S iX > 0 ) as do the submitted prices p iX S > 0 and p jX D > 0.
	!	laboratory results. The outcome of the allocation process is	s iX and	d jX , respectively the allocated quantity
		We would like to thank Romain Zelinger (GATE) for the development of the software for the ! ! ! ! corresponding to the submitted offers to sell p iX S ,S iX
		experiments.	!	!
					!

For an overview of the current cross-border congestion management methods in Europe, cf.[START_REF] Etso | An Overview of Current Cross-Border Congestion Management Methods in Europe[END_REF].

Flow-based methods use the so-called power transfer distribution factors (PTDF) to convert the commercial exchanges into their physical influence on the cross-border flow. Another aspect of these methods, which cannot be considered within the scope of this paper, is that they convert bottlenecks or border capacities into physical limitations of those flows.

For a review of congestion management methods, see De[START_REF] De Vries | Securing the public interest in electricity generation markets[END_REF].

Denmark (west and east), Finland, Sweden and Norway.

The market-splitting approach assumes an existing integrated market where injections and withdrawals of several nodes are assigned to a specific zone (so that there is only one energy price per zone).

For example, the next step has been the ETSO-EuroPex's proposal[START_REF] Etso-Europex | Flow-based Market Coupling, A Joint ESTO-EuroPEX Proposal for Cross-Border Congestion Management and Integration of Electricity Markets in Europe[END_REF] which is conceived as the merging of ETSO and the EuroPex proposals. The European Commission subsequently recommended use of the coordinated explicit auction for the allocation of long-term capacities (annually, monthly, weekly), and the implicit auction through flow-based market coupling for the allocation of day ahead and intra-day capacities.

This is also the case in the US where most electricity firms are utilities which are vertically integrated.

This specification aims at reproducing in a simple way two characteristics of electricity demand: variability and cyclic variation. It is a simplification of the typical daily load curve that exists in reality with two higherlevel periods (between 7.00

and 9.00a.m. and 5.00 and 7.00p.m.) and two lower-level periods (between 3.00 and 6.00a.m. and 9.00 and 12.00a.m.).

Gains result from the fact that a generator can be paid for transmission if the flows that it requests relieve congestion.

The price dynamics for the coordinated explicit auction treatments do not fit the assumption of this model. As a result, we cannot conduct the same analysis for the data collected in this treatment.

The complete results of the estimation are available upon request.

The competitive equilibrium price for transmission capacities is computed under the assumption that allocation of transmission capacities is efficient and that prices on the energy market at each node are equivalent to the competitive equilibrium price.

Finding 2: Energy prices observed in the implicit auction sessions converge towards a single equilibrium price.

To assess quantitatively the evolution and convergence of market prices, we use a convergence model inspired by Noussair, Plott and Riezman (1995) for data collected with the implicit auction treatment 20 . ! p it = D i i " # 1i 1/t ( ) + # 2 (t $1) /t + % it where is the average price of session i for period t and a dummy variable which takes the value one for session i and zero otherwise. This model is relevant to estimate the convergence process which could occur in a market experiment. Even if each session has its own starting point, they should converge -if a convergence occurs -to the same ultimate point. The model is estimated as a linear panel data model and the six independent sessions are modelled as random effects . We estimate the model for the price of each node, distinguishing between base-load and peak-load periods. As the prices observed at the beginning of each session are not really relevant to our analysis, we focus our presentation on price convergence 21 . Table 5 reports the estimates for for each node and for base-load and peak-load periods.

{ } and for all the offers at node X 2 ( )


Dr Isabelle Quidu
email: isabelle.quidu@ensta-bretagne.fr

Alain Bertholom

Yann Dupas

DEFERRED ESTIMATION OF VERTICAL POSITION OF A FLOATING OBSTACLE BY MINIMISING DEFECTS OF TRACKING

Keywords: Forward looking sonar images, AUV, Obstacle avoidance

This work follows previous works on tracking of targets on Forward Looking Sonar images. A Kalman filter based on a process model of the vehicle was implemented considering two strong assumptions: firstly, the obstacle is fixed in relation to the world reference frame and secondly, it lies proud on the seabed. Consequently, Kalman filtering leads to a biased estimation of successive positions of an obstacle floating in the water column. Starting with this observation a new algorithm has been developed to allow a deferred estimation of the z-coordinate (along the absolute z-axis) of the obstacle related to the vehicle. This is performed offline by minimizing at each step of the sequence the root mean squared deviation (RMSD) between measured sonar positions and predicted positions, i.e. by minimizing the innovation values of the

Kalman filtering. Results are given on real data recorded in March 2009 and April 2010 during sea trials organized by GESMA involving the Rapid Environment Assessment (REA) "Daurade" AUV with its BLUEVIEW P450 obstacle avoidance sonar. Tethered mines and other floating obstacles like plastic chains were laid.

INTRODUCTION

This paper concerns obstacle avoidance issues by processing forward looking sonar (FLS) images and navigation data. In previous works, we first derived a process model in order to predict the motion of a ground target detected in a sonar image [START_REF] Quidu | Theoretical optical Flow for Traget Position Prediction on FLS Images[END_REF]. Then a Kalman filter based on this model was implemented in order to track an incoming obstacle by taking navigational data as inputs [START_REF] Quidu | Ground Obstacle Tracking on Forward Looking Sonar Images[END_REF]. According to the assumed condition of a seafloor object, tracking of a tethered object in the water column is not performed especially well. Indeed the obstacle appears to be moving faster than the predicted positions. Here, this defect of the tracking procedure has been used offline to estimate the tether length. This is performed by minimizing the root mean squared deviation (RMSD) between measured sonar positions and positions predicted by means of a new version of our process model. This piece of information is of particular interest for obstacle avoidance but it is generally unavailable because of little or no sampling of the sonar data along the vertical axis.

The paper is organized as follows. Section 2 describes sonar and navigational data used. Our process model and the derived tracking procedure are briefly recalled in section 3. Then the method for a deferred estimation of the vertical position of a floating obstacle is presented in section 4. Some results on real data are showed in section 5.

DATA DESCRIPTION

The Daurade vehicle is a multi-purpose experimental AUV for Rapid Environment Assessment (REA) applications [START_REF] Ayreault | Un Nouveau AUV Experimental pour des Etudes de REA[END_REF]. It has been developed in the context of a project conducted by SHOM (Service Hydrographique et Océanographique de la Marine) in cooperation with GESMA (Groupe d'Etudes Sous-Marines de l'Atlantique). The obstacle avoidance system is a Blueview P450 Forward Looking Sonar. The system can obtain a beamformed image over a 15° (vertical) × 45° (horizontal) sector with an across-track sampling rate ∆δ equal to 0.18° and an along-track sampling rate ∆d equal to 0.17m. The sensor looks straight ahead (see Fig. 1).

Data used in this paper have been collected by GESMA during two sea trials near Brest (France) in March 2009 and in April 2010.

TRACKING PROCEDURE

Process model

The process model provides the sonar coordinates ) , ( δ d of a detected object given the AUV motion. It is derived from two main sets of equations and their derivatives.

The Euler rotation matrix R euler is composed of three rotations that move the relative reference frame (O r , x r , y r , z r ) (O r : centre of gravity of the vehicle, x r : in the direction of movement of the vehicle, y r : towards its right, z r : down) to the world reference frame (O a , x a , y a , z a ) (O a : centre of gravity of the Earth, x a : geographical North direction, y a : East direction, z a : gravity direction). This allows deriving the first set that gives the relation between target positions (or speeds by differentiation) in the two reference frames:

( ) r a a m m p ⋅ - = - ψ θ ϕ , , euler R (2)
where ( )

z a y a x a p p p , , = a p
are the coordinates of the AUV (we assume that its location is coincident with all the other sensors) and

( )

z a y a x a m m m , , = a m
are the coordinates of the object in the world reference frame.

The second set gives the localization of a seafloor target in the relative reference frame (see Fig.

Fig.2: Operational configuration

As explained in [START_REF] Quidu | Theoretical optical Flow for Traget Position Prediction on FLS Images[END_REF], the final expression for a moving object is a non linear function of its initial position and navigational data:

z r m x r z r y r d δ δ δ δ target β x r m y r m h O r ( ) ( ) ψ θ ϕ ψ θ ϕ δ δ , , , , , , , , , r
V d f d = (3) where (
)

z r y r x r r v v v , , = V
is the speed of the AUV in the relative reference frame.

Kalman filtering

Prediction stage

The state vector is composed of the sonar coordinates, i.e.

(

)

T d δ = x
. The state equation (in the discreet domain) is based on the previous model such that:

( )

1 k 1 k 1 k k v u x x - - - + = , f . ( 4
)
where k x is the state vector at the k th filtering step,

1 k u -is the input vector at step k-1
which is composed of navigational data and 1 k v -stands for the white Gaussian state noise.

The prediction stage computes the new state

1 k/k x - ˆ
given the previous one

1 1/k k x - - ˆ
thanks to the above equation. Given the strong non linearity of the state function f , the computation of

1 k/k x - ˆ
is carried out by performing an unscented transform of

1 1/k k x - - ˆ [4].

Correction stage

The correction stage is based on the following measurement equation:

1 k k k w x y - + = k H . ( 5
)
where the measurement vector k y is comprised of obstacle coordinates on the screen at step k, 1 k w -stands for the white Gaussian measurement noise whose covariance matrix is

1 - k R at step k-1, and [ ] [ ]           ∆ ∆ = = δ 1 0 0 1 d H H k is the measurement matrix.
This stage corrects the predicted sonar coordinates

1 k/k x - ˆ
given the new measurement y k . After computing

1 k/k 1 k/k x y - -= Ĥ
we can correct the state by applying the Kalman equations in the linear case this once:

( ) ( ) ( ) ( )      - = = + = - + = - - - - - - - - T k k k k k k k k T k k k k T k k k k T k k k k k K R K P P R H P R H P H H P K K υ υ 1 / / 1 1 / 1 1 / 1 / ˆ1 k/k k 1 k/k k/k y y x x (6)
The difference

LENGTH ESTIMATION OF A MINE TETHER

An estimation of the z-coordinate of the obstacle can be achieved by minimizing at each step of the sequence the root mean squared deviation (RMSD) between measured sonar positions (deduced from measurements y k ) and predicted positions. These predicted points only depend on the first measurement y 0 and prediction given by a new process model derived from the previous one with a new parameter related to the z-coordinate.

This new model is obtained by modifying the third equation of ( 1) in order to put the distance d st between the sonar and the target along the z-axis in the world reference frame in the place of the altitude h of the sonar. This leads to: • In the first step, the predicted sonar position is computed by taking into account the first measurement y 0 such that:

0 0 y x H ( = ~
where [ ]

      ∆ ∆ = δ 0 0 d H ( .

•

For steps k greater than 0, we compute predicted sonar positions ( )

st d f , , ~1 k 1 k k u x x - - =
given the previous one

1 k x - ~.
Finally, we estimate the vertical distance from the sonar to the target as:

[ ] ( ) ( ) 1 min arg ˆ0 2 2 . 1 , 0 + - = ∑ = × ∈ N d d N k st h d st st k k x x ,
where N+1 is the number of pings used, and

k k y x H ( = for k>0.
By noticing that ( )

k k k k k υ y y x x H H ( ( = - = -
, we can therefore say that the estimation consists in finding st d ˆ that minimizes the new innovation term k υ ~ of a Kalman filter based on the new model.

EXPERIMENTAL RESULTS

In the following, we will call the experimental measurements those given by a detection algorithm based on a goodness-of-fit test and described in [START_REF] Quidu | Ground Obstacle Tracking on Forward Looking Sonar Images[END_REF], and the theoretical measurements those we estimated visually.

The Daurade sea trials in April 2010 were designed to assess the performance of the present method for estimating the length of the tether of a moored mine. Two tethered spherical targets were deployed: the rubber one with a tether of 15m and the steel one with a tether of 12m. Fig. 3 shows results concerning the first target. The top part of Fig. 3 shows a sonar altitude about 15m and the RMSD minimisation that gives an estimated distance st d ˆ of 0.5m. That was exactly the case: GESMA was testing avoidance capability in the case of an obstacle in the direction of travel of the vehicle. In this case, the estimation was as good on experimental measurements as on theoretical measurements. Predicted points and measurements points are plotted in the bottom part of Fig. 3 in case of d st =0.5 that is to say when these two sets of points are close from each other.

This task was more difficult for data gathered in March 2009 on a large obstacle shown in Fig. 4. Indeed, the estimated value st d ˆ (11m) based on experimental measurements differs from estimated value (8m) based on theoretical measurements as shown in Fig. 5. This is probably due to noisy experimental measurements. Moreover, as the three Nokalon floats are not clearly visible, we can assume that the obstacle was pushed down by current forces. Under this assumption, the echo area does not represent the Nokalon floats nor the chains nor the bar but probably a mix of them that leads to a value of 8m between obstacle and sonar along the z-axis.

CONCLUSION

This paper proposes an original mean for estimating the vertical position of an obstacle in the vertical axis. The estimation is achieved offline by minimizing, along the sonar image sequence, the innovation term of a Kalman filtering of the successive obstacle positions. This is an important piece of information to help the vehicle to revise its trajectory and to induce a good avoidance strategy.

The method has been tested on real data supplied by the French organisation GESMA, a division of the French Ministry of Defense (DGA).

Future work concerns the modification of the process model so as to make this estimation at the same time as the tracking.

Fig. 1 :

 1 Fig.1: Configuration of the Blueview P450 FLS on DAURADE AUV

  coordinates of the seafloor target, h is the AUV altitude and ( ) ψ θ ϕ , , are the Euler angles that define the attitude of the vehicle.

  term and the associated covariance matrix is υ k R . The impact of this term is controlled by the Kalman filter gain K k .

  this, the previous f function becomes a new function f ~. For different possible values of d st ≥0, we compute all of the predicted positions as follows:

Fig. 3

 3 Fig. 3 Relative obstacle altitude estimation Up: RMSD vs. d st and sonar altitude vs. ping number Down: Predicted points (green) and measurements (blue) for d st =0.5

& & & & &

Fig. 5 Relative obstacle altitude estimation for track shown on Fig. 4 Up: RMSD vs. d st based on experimental measurements Down: RMSD vs. d st based on theoretical measurements