Rodrigo Castiñeira
email: rcastineira@indra.es

Jose Eugenio Naranjo

Mauro Gil

Felipe Jimenez

Pedro Serra

Alerto Valejo

Alireza Asvadi

Cristiano Premebida

Mohammad Y Abualhoul

Fawzi Nashashibi

Indra Sistema

AUTOCITS -Regulation study for interoperability in the adoption of autonomous driving in European urban nodes

des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

A series of initiatives have taken place in Europe since the publication of the C-ITS platform report in January 2016, which have highlighted the interest of the European Commission in making the EU a world leader in autonomous driving, following the ideas set out in the European Commission's strategy in Annex I of directive 2010/40/EU or later in 2011 White Paper on Transport "Roadmap to a Single European Transport Area -Towards a Competitive and resource efficient transport system", which already indicated the need for 2020 to harmonize and deploy road safety technologies, such as driving aids, intelligent speed limits, etc. Cooperative systems are considered as catalysts for the actual deployment of autonomous driving, in order to overcome the limitations inherent in a vehicle circulating without any interaction with others. For this reason, various deployment projects are being carried out involving both technologies: V2X communications and vehicles automation.

EU Commissioner for Transport Ms. Violeta Bulc said in the presentation of the C-ITS report in January, 2016: "Digitisation of transport is a priority of my mandate as it has the potential to create new growth and smarter mobility. I want to see connected cars on European roads by 2019 and today's report (C-ITS Platform Report) is an important milestone towards that objective. It is nevertheless only a first step, more deliverables will come throughout 2016". In this regard, AUTOCITS (www.autocits.eu) aims to contribute to this mentioned C-ITS Platform report as well as to other related policy and reference documents on connected and autonomous road vehicles.

The remaining of this paper is organized as follows. Section 2 briefly introduces the AUTOCITS project and explains the structure and aims of the three pilots that will be deployed. Section 3 provides an overview of the project. Section 4 presents the initial results of the analysis of the regulation framework related to autonomous driving at European and international level. Section 5 explains each of the pilot projects to achieve interoperability between C-ITS services. Section 6 provides the description of the International Cooperation Group. Section 7 concludes with a discussion on the next results that are expected to achieve.

3

The Project

The AUTOCITS project, co-financed by the European Union through the CEF Program, proposes 3 pilots with different cooperative systems in 3 European locations: Madrid, Paris and Lisbon. The scenarios presented in the project include the following main characteristics:

 Include different types of roads in urban environments (urban roads, motorway connections, etc.);

 Provide an open testing environment where several C-ITS services, connected, instrumented and autonomous vehicles will be tested;  Different parties involved in the different levels of traffic management will be considered, involving both transport operators and traffic authorities together with industrial and academic entities in Spain, France and Portugal;  Demonstrate the maturity of C-ITS services in urban environments, based on the state-of-the-art deployment of C-ITS deployments on European highways;  Enable the assessment of the potential C-ITS services to increase road safety and improve traffic.

AUTOCITS includes autonomous driving tests in both open and closed traffic environments to assess the applicability of traffic regulations and V2X services under different conditions and scenarios. Different elements will be addressed for the deployment of cooperative services and autonomous driving, such as: real-time monitoring, vehicular communications, maneuver strategies in complex traffic situations, and high-level strategies in control center for the management of autonomous driving.

In addition, the project studies the technical and legal requirements for an interoperable transnational navigation, contributing to different standardization groups, the creation of certification processes and homologations. Thus, the AUTOCITS project is organized around two types of activities:

 Regulation study: study of regulations on autonomous driving at European and international level  Pilot deployment: deployment of three pilots in urban nodes to assess the link between C-ITS services and autonomous driving

Regulation Study

The regulation study follows the guidelines set out in recent years by the European Commission and, although there is currently no harmonized regulatory framework, there are a number of initiatives working towards this. In the study of the regulations for the circulation of autonomous vehicles in conditions of free traffic in urban nodes, it has been analysed the regulation framework mainly at European level -starting with the countries involved in the project (Spain, France and Portugal) and other advanced European regulations-, but other international regulations has been also considered, such as the US, Singapore, South Korea, China, Japan or Australia.

Another entity that has been taken into account for this initial study is the activity GEAR2030, a group of experts created by the Commission in January 2016 to coordinate the challenges of autonomous driving. This initiative has delivered a publication highlighting that no major legal impediments to the deployment of partially automated vehicles (Level-3) are identified, but for higher levels of automation and automobile connectivity, changes in UE legislation are required (such as traffic rules, connectivity, driving license, road safety, liability framework, traffic signs, insurance, theft and cybersecurity, privacy and data protection, etc.).

Table 1 shows the initial results of the regulation study, an analysis of the most advanced regulations in Europe.

It is relevant to highlight the importance of this exercise as several analyses have been found about the deployment of C-ITS services or automated driving but none of them addressing the regulation framework. The analy-sis has considered aspects such the link to the Vienna Convection, the current legislation and the testing procedures, the status of the current legislation and its requirements, of European and international countries, being the results of the European countries shown in the Based on the analysis of the current legislations in the European countries, it has been drawn that the countries that are not linked to the Vienna convention are the more progressed ones in terms of testing possibilities, as they present less legislative obstacles and restrictions. But regardless of the Vienna Convention's ratifications, although Spain and UK are non-ratified members, some member states have made the amendments and/or exceptions necessary to allow testing and deployment, under specific conditions, of AVs in real-world traffic scenarios. This indicates that the interest of the countries in this direction is becoming more and more evident. AUTO-CITS will continue monitoring the different regulation activities in order to provide authorities with guidelines at the end of the project.

Pilots

The AUTOCITS project will carry out a comprehensive assessment of cooperative systems and autonomous driving through a set of pilots in the Atlantic Corridor of the European transport network. The pilots will be deployed at several European test sites in Madrid, Paris and Lisbon. Therefore, the characteristics for each pilot site have some differences that will be presented in the following sub-sections. In addition to their heterogeneous appearance the test sites are operated by different entities with different vehicles and different infrastructure equipment.

In these three pilots, the connected and autonomous vehicles will circulate along the urban traffic interconnection zones with interurban in the pilot cities to analyze the continuity of autonomous driving and V2X information flow when moving from one urban area to another and to ensure interoperability between countries. They will receive information from the control center through ITS (Road Side Units) equipment and through hybrid communications using the ITS-G5 (Vehicular Communications) and LTE (Mobile Communications) communications technologies in an approximation to what it would imply the 5G communication, which seeks to integrate the different communication technologies on a single specification

Madrid Pilot

The selected pilot in Madrid includes the highway between the M50 and the M40. It is a dedicated high occupancy reversible lane whose direction is configured according to the needs of the traffic, and involves traffic flow of about 20,000 vehicles per day. Three C-ITS services have been selected to be deployed in the pilot of Madrid, being part of the C-ITS Day one service set defined by the C-ITS platform:

 Slow or stationary vehicle(s) & traffic ahead warning: The function aims at avoiding (fatal) rear end collisions which are often caused by traffic jams on highways. With help of V2X-communication, vehicle systems are able to warn the driver even before the traffic jam could be noticed by the driver himself. Thus, the driver is informed in time and can react smoothly and safe.  Road works warning: The traffic management center, through V2I communications, provides information about a construction zone to vehicles by broadcasting messages to vehicles in the vicinity of the dangerous location.  Weather conditions: Information about bad weather conditions ahead is generated by the traffic management center and communicated to oncoming traffic to avoid entering of areas with adverse weather conditions at too high speed.

These C-ITS services have been selected because they are representative use case extensions of the functionalities the current traffic management centers perform that can be deployed under the existing infrastructure and available services. Additionally, they are based in V2I communications and allow demonstrating the benefits of the upgrading of the existing technology installed in the Spanish roads.

These services will allow the traffic control center (TCC) to send incidents or events to the connected and to the autonomous vehicles to enhance the information sent to the drivers through the variable message signs. The final objective of these services is to improve mobility and road safety by sending warnings of stopped vehicles, vehicles broken down, information of adverse road conditions such as icy surface, etc.), or other information such as traffic information road works, etc.

The tests in this environment will be carried out according to the regulation approved by the DGT (Spanish Road Authority), which makes available to companies and research centers an open standard for testing, as it is not conditioned by the Vienna Convention.

Madrid C-ITS Infrastructure.

It includes the ITS equipment on road and Traffic Management Center. The infrastructure that the pilot of Madrid will need is formed by the typical subsystems of a Cooperative ITS application. Each of these subsystems, that are interconnected to build up the pilot, will be considered as an ITS station. The following types group the different stations that will be part of the pilot:

 Traffic central control (TCC). In charge of the high level information management and operated by the Spanish traffic Agency.  ITS Center (C-ITS). Responsible of analyzing the information retrieved by the TCC and of launching the C-ITS messages when necessary.  Roadside ITS Units (R-ITS or RSU). The ITS V2X equipment installed in the road, including the interconnection with the intermediate networks to connect the road with the ITS center.  Vehicle ITS (V-ITS or OBU). Onboard V2X units able of receiving the C-ITS data. They are installed in the connected vehicles as well in the autonomous ones.  Personal ITS (P-ITS). Devices to transmit to the drivers visual information about C-ITS messages.

Madrid C-ITS equipment

The Madrid Pilot also defines the equipment for communication and data packets definition, including the message exchange architecture and protocols, the communication networks equipment and the associated software to support the services. Four elements have been defined to support the deployment of the C-ITS services of the Madrid pilot:

 ITS central station: this server connected to the current DGT TCC will collect incidents, road works, and weather information through the DATEX II interface and will send this information to the RSU-Master to order the broadcast of an event.  RSU-Master: roadside station responsible for broadcasting an event to vehicles coming from the TCC. It is necessary that this device has direct connection with the C-ITS station and is equipped with antennas with ITS G5 (802.11p) technology. The manufacturer "Codha wireless" is the provider of this kind of equipment that will be used in Madrid.  RSU-Repeater: roadside station responsible for repeating events from the main RSU where these do not have coverage. These devices will not have direct connection to the C-ITS station and will not process events; they will only repeat the signal through the ITS G5 antennas. This equipment used as repeaters are the INSIA-V2X technology.  OBU-Autonomous and connected cars: The INSIA-V2X ITS stations will also be used to support the onboard units. The OBUs are equipped with ITS G5 (802.11p) technology in order to receive the RSU information, as well as all sensors and actuators necessary for the connected and autonomous vehicles.

Madrid Connected & Autonomous Vehicles.

Two kinds of vehicles will take part in the Madrid pilot, in order to demonstrate the performance of the C-ITS deployment. Connected vehicles, that are manually driven and equips V2X onboard units and human machine interfaces to transmit to the driver the C-ITS messages. Autonomous vehicles, whose automatic driving system is connected to the V2X onboard unit and is able of automatically reacting to the cooperative messages received.

Four testbed vehicles will be used in the pilots of connected vehicles. All of those vehicles are equipped with INSIA-OBU V2X units in order to connect and receive information from the installed RSUs, needed to enable the planned deployment of the C-ITS. Two autonomous vehicles are part of the equipment that will take part on the pilots: a Citroën C3 Pluriel and a Mitsubishi iMIEV (Figutr 2). These vehicles are considered of automation level 2 and 3 respectively, and are also equipped with INSIA-OBU V2X units.

Paris Pilot

The French Pilot defined to deploy a 10-km segment of A13 highway that belongs to the French part of the Atlantic Corridor. The chose pilot location is considered as one of the main traffic veins toward Paris city. As for Day 1 C-TS services deployment, two driving-assistance I2-based services were elected for the French pilot, together with a third V2X service we list as Other hazardous notification as follows:

 Road works warning: On-road working zones, such as construction, reparation, or maintenance activities are pre-identified geo-graphically and reported to the Traffic Management Center (TMC). The TMC will then notify all RSU's before and after these zones to start broadcasting these warning messages over I2V.  Weather conditions: Weather conditions updates are acquired by a third-party online-service and fed to the TMC which will identify the geographical location of what can be considered hazardous weather conditions. TMC will process and notify the corresponding RSU about the situation, and trigger warning messages varies from slow-down up to stop traffic in severe hazard situations.  Other hazardous notifications: These kind of notifications are mainly about any in-vehicle local fatal or error may affect the autonomous vehicle behaviour and cause hazardous situation either in traffic flow or lane blocking. In this scenario, the V2X communication is broadcasting a Decentralized environmental Notification Message (DNM) locating and identifying the affected vehicle.

The three French C-ITS services are selected to cope with both Spanish and Portuguese essential functionalities and to establish interoperability between the three pilots. Moreover, the chosen services are demonstrating both I2V and V2X and using CAM and DENM standardized messaging for vehicular communications.

Paris C-ITS Infrastructure

The infrastructure of the pilot contains several connected subsystems that allow proper information exchange and ensures the C-ITS services functionality. The following sub-systems are defining the pilot general infrastructure:

 ITS Central Station: The central station is a server connected to the Y-cloud and meant to collect incidents, updates, events, road works, and weather information through the Y-Smart middleware and then send this information to the RSU's to trigger the broadcast of the specific event.  Roadside ITS (R-ITS or RSU): Roadside stations are installed along the pilot and responsible for passing the TMC event to vehicles. This unit has a direct connection with the C-ITS station over 4G and with the surrounding vehicles over ITS G5.  Vehicle ITS (V-ITS or OBU): On-board V2X units able of receiving the C-ITS data. They are installed in both connected and autonomous vehicles.  Personal ITS (P-ITS): HMI interface devices used to display visual information to the drivers about C-ITS messages.

Paris C-ITS equipment

Four elements have been defined to support the deployment of the C-ITS services in the Paris pilot, including the communication equipment, the message exchange architecture and protocols, the communication networks equipment and the associated software to support the services:

 ITS central station: this server connected to the Y-cloud and will collect incidents, updates, events, road works, and weather information through the Y-Smart Middleware provided by YoGoKo and then send this information to the RSU-Master to trigger the broadcast of an event.  RSU-Master: Roadside stations Y-RSU are deployed by the French Pilot, where the equipment that hosts this software will be of the local French manufacturer "YoGoKo wireless". The units certified to communicate over ITS G5, 4G and read in-vehicle read CAN-bus.  OBU-Autonomous and connected cars: The YoGoKo boxes Y-Box OBU's are equipped with ITS G5(802.11p) technology and fully compatible with the RSU's to transceive the RSU information, as well as all sensors and offering actuators necessary for the vehicle.

Paris Connected & Autonomous Vehicles.

For the French Pilot Four identical vehicles of model Citroen-C3 will be used in the French pilots as connected vehicles. Each connected vehicle has a single highly accurate GPS, an on-board computer and direct access to the CAN bus, with 3/4G Internet access together with an OBU supporting the 802.11p. All the four vehicles are also equipped with OBU V2X units, IMU, Camera, V2X antennas and some other sensors. Moreover, one autonomous vehicle will take part on the French pilots. The vehicle is a Citroën C1 Evie, fully electric autonomous vehicle. This vehicle is fully equipped with communication and represents an excellent opportunity to test the interoperability between different pilot sites.

Lisbon Pilot

The Lisbon's Pilot will be held at two locations. The first location will be at highway A9 -CREL ("Circular Regional Exterior de Lisboa"), beginning near National Stadium in Jamor and ending at A1. This A9 intercepts with others highways, like A5, A16, A8 and A10, and major regional roads, like IC19, IC22. The section of the highway where the pilot will be deployed is a fragment with 7km between the beginnings, near of National Stadium and exit number 2C, intersection with A16. This selected site in Lisbon involves a traffic flow of about 19 500 vehicles per day. In the second location, autonomous shuttles will be used in an urban node over a national road that connects the beginning of A9 to the Faculty of Human Kinetics, enabling also the test of C-ITS services under an urban environment. For Lisbon's pilot, three C-ITS services have been selected to be deployed:

 Slow or stationary vehicle(s) & Traffic ahead warning: This service provides warning messages regarding slow or stationary vehicle on the road (due to an accident, a breakdown, traffic ahead or any other reason), diminishing the risk of accident associated to such dangerous situations, e.g. avoiding the risk of cause a succession of collisions and also contribute to traffic management. In this case, it is required that connected vehicles detects potential dangerous conditions and broadcast the situation using V2X communication;  Weather conditions: The weather information service is broadcasted using V2X communication, allowing the connected vehicles to receive warnings messages that may have impact in their vehicles safety, e.g.: tyres adhesion, visibility or extreme weather conditions;

 Other hazardous notifications: This case aims to inform the connected vehicles of any hazardous location either temporary or permanent to reduce the risk of accident, like surface condition and obstacle on the road. For this the vehicle must be capable to detect the hazardous location and broadcast this information.

These C-ITS services, in the same way as in the pilot sites of Madrid and Paris, have been selected to demonstrate the benefits over the existing technology installed in the Portuguese roads (e.g. variable message signs), by providing information for and from the autonomous and connected vehicles, and thus improving mobility efficiency and safety. Moreover, another relevant aspect that will be tested is the interoperability of the C-ITS, as vehicles from other pilot sites will be used on Lisbon pilot.

Lisbon C-ITS Infrastructure

The Lisbon pilot site will include a Traffic central control (TCC) and ITS equipment. The TCC system operates using a third-party Cooperative ITS application, gathering information coming from different ITS equipment along several highways, and it is operated by the company that has the A9 highway concession, being therefore responsible for to manage the traffic management. The infrastructure needed for Lisbon's pilot at A9 highway is composed by the typical subsystems of a C-ITS application. Each of these sub-systems, that are interconnected to build up the pilot, will be considered as an ITS station and they could be grouped as follow:

 Centre ITS station: This station is the gateway of TCC with the C-ITS application, receives the information on DATEX II format from TCC and deals with the alerts broadcasted through the RSUs and OBUs.  Roadside ITS (RSU): This station is the one that acts as a bond between the Centre ITS station and the vehicles on the road, by exchanging information between the vehicles and the control centre, disseminating alerts from the control centre to the vehicles, depending on what kind of C-ITS service is deployed.  Vehicle ITS station (OBU): This station equips the vehicle and has two roles. As an emitter it is responsible for collecting information from vehicle sensors to provide information on both the condition of the vehicle and different incidents that may take place in the road; as a receiver it is responsible to receive the events sent from the R-ITS (RSU) or from other V-ITS stations.

Lisbon C-ITS equipment

The C-ITS services to be deployed at Lisbon pilot site will need the following equipment:

 ITS-G5 from A-to-Be: This equipment can work as RSU or OBU, depending of the services to be installed.  INSIA-OBU V2XOBU used in UPM autonomous car: The "INSIA" partner will supply an autonomous car equipped with an INSIA-OBU V2XOBU, able to interpret the information that RSU disseminates and to act accordingly.

Lisbon Connected & Autonomous Vehicles.

The Lisbon pilot will have three types of vehicle technologies:

 Autonomous Vehicles (AV) -One autonomous vehicle, a Mitsubishi iMIEV testbed from Madrid Pilot Site, representing a good opportunity to test the interoperability between pilot sites.  Instrumented Vehicles -One instrumented vehicle from ATLASCAR research group from the Department of Mechanical Engineering of the University of Aveiro.  Autonomous Shuttles -Two autonomous shuttles based on an ITS technology called MOVE developed by IPN; they are driverless electric vehicles, designed to be easily used for small trips at low speed, with the aim to be a "horizontal lift" able to connect buildings of private or semi-private spaces.

The autonomous and instrumented vehicles to be deployed in the highway, depending on the technology level of each one, would be tested under three conditions: dedicated lane, shared lane and road without restrictions (intended scenario). The autonomous shuttle would be tested under only one condition, dedicated lane. The test events used on these scenarios, some will be simulated (they will be generated virtually at the Traffic Management Centre and broadcasted by the Road Side Unit) and others will be realistic (e.g. the vehicles used for this purpose will be at the roadside and will generate the event messages).

International Cooperation Group

In other to involve different experts outside the project, AUTOCITS has created the International Cooperation Group (ICG) that brings together experts from the automated and autonomous driving field, which represents one of the target audiences that AUTOCITS aims to reach and crate synergies to disseminate the action activities. It involves Road Operators (both private and public), Road Authorities, Insurance Companies, Car manufacturers and other entities, that can join through the project webpage. This stakeholders group has been created in order to have an on-going open dialogue within the sector. Members of this group are invited to attend the workshops organized by project partners and main action results (Press Release, Deliverables, etc). With this group, the Action aims to incorporate their guidelines and recommendations into the project results.

Conclusion

The AUTOCITS project starts from the premise that in the coming years, autonomous driving will replace conventional driving as we know it today, with the aim of increasing the efficiency and safety of transportation. Today there is a defined strategy for this, but there is a process of harmonization and standardization to go, which guarantees, on the one hand the reliability and safety of automated driving, and on the other, interoperability at different levels between different countries, different manufacturers, different technologies, etc. From AUTOCITS we expect to contribute in the following points:

 C-ITS services as catalysts for autonomous driving: With the deployment of C-ITS services in the three pilots, the project seeks to provide a vision of how C-ITS services can facilitate the deployment of autonomous vehicles and especially in the connection between the main road network with urban nodes, where the complexity of the environment requires additional technologies to those of the vehicle.  Progress in interoperability: C-ITS services has been defined in the pilots to ensure interoperability that will be validated through a set of cross-tests between Spain, Portugal and France. Initial tests between different RSUs from different manufactures have been performed so far.  Encouraging cooperation and knowledge: Through the International Collaboration Group, AUTO-CITS seeks to capture the vision of the transport sector on how C-ITS services can contribute to the deployment of autonomous driving and in which aspects Autonomous vehicles regulations should evolve.  Collaboration with the C-ROADS platform: During the project, AUTOCITS has shared its initial results with this platform to contribute to the specifications and agreements for harmonized and interoperable infrastructure deployments; as well as with the C-ITS platform to identify new services that facilitate the deployment of the autonomous vehicle  Advances in standardization: Road Works Warning messages allow infrastructure to send parameters such as recommended speed, change of lane, etc. that can be used to enhance autonomous driving. Further modifications on other standardised messages could be suggested at ETSI (European Telecommunications Standards Institute) in order to allow cooperative systems to send added-value information from traffic control centers, in order to facilitate autonomous driving, and that currently do not contemplate the ETSI standards.  Added value: Tests with connected and autonomous vehicles allow us to analyze what added value information can be provided to the control centers to improve mobility management. So far, it has been identified how road works information stored in the control centers can be sent in advance to vehicles to enhance their safety maneuvers.  Contribute to the new regulatory framework: unlike other previous studies more focus on technical aspects of autonomous driving, AUTOCITS has performed a global analysis on legal aspects in order to generate recommendations in order to contribute to a more homogeneous legislation in European countries 8

Table 1 Initial

 1 table. A more detailed analyses of the current regulations can be found at www.autocits.eu: Results of the Regulation Study within the AUTOCITS project.

									The Nether-
	Elements		Spain	Paris	Portugal	UK	Germany	Sweden	lands	Italy	Denmark
	Linked	to
	Vienna		No	Yes	Yes	No	Yes	Yes	Yes	Yes	Yes
	Convention
	Current
	Legislation
	Testing Procedures		Yes. Auton-omous driving is allowed, regulation in November 2015	Yes. Auton-omous driving is allowed for testing purposes	Agreement between road administrations and conces-sionaires	Yes. Auton-omous driving is allowed for testing purposes.	Yes. A section of the A9 autobahn is to be set up	Yes. Auton-omous driving is allowed for testing purposes	Yes. Autono-mous driving is allowed for testing pur-poses	Generally are not allowed on public roads for safety reasons	Yes. Auton-omous driving is allowed for testing purposes
	Certification Procedures	Vehicle manufacturer shall provide certification	Authorities shall provide a certifica-tion	No certifica-tion / proce-dures	No certifica-tion / proce-dures	No certifica-tion / proce-dures	Yes	Companies must first that the tests will be conducted safely	-	Permission to the Transport, Construction and Housing Ministry
	Laws to be modified	Code for Vehicles and Traffic Law and Code for Traffic Rules	Code for Vehicles and Traffic Law Rules Traffic and Code for	-	The High-way Code, rules and vehicle road safety	Federal Government, Road Traffic Amend the Draft Act to	-	-	Codice della Strada and ne di Attuazio-Regolamento	-
			Regulation	Fully auton-			Law in the
	Initial Modi-fications for SAE3-5	on assisted parking of motor vehi-	omous discussed in context of	-	Liability Initiatives	Cabinet: driving on Automated	-	-	-	-
			cles	road safety			the way

Acknowledgments

We cordially thank all our colleagues from the AUTOCITS project for their contributions, inspiring discussions and fruitful collaborations. Research leading to these results received funding from the Connected Europe Facility (CEF) Program under grant agreement no. 2015-EU-TM-0243-S (www.autocits.eu).

Code for Vehicles and Traffic Law and Code for Traffic Rules Code for Vehicles and Traffic Law Portuguese Road Code The Highway Code, road safety and vehicle rules German Highway Code Code for Vehicles and Traffic Law Reglement verkeersregels en verkeerstekens Codice della Strada and Regolamento di Attuazione Code for Vehicles and Traffic Law


Mohamed Wahbi
email: mohamed.wahbi@insight-centre.org

Younes Mechqrane
email: ymechqrane@gmail.com

Christian Bessiere
email: bessiere@lirmm.fr

Kenneth N Brown
email: ken.brown@insight-centre.org

A General Framework for Reordering Agents Asynchronously in Distributed CSP

Reordering agents during search is an essential component of the efficiency of solving a distributed constraint satisfaction problem. Termination values have been recently proposed as a way to simulate the min-domain dynamic variable ordering heuristic. The use of termination values allows the greatest flexibility in reordering agents dynamically while keeping polynomial space. In this paper, we propose a general framework based on termination values for reordering agents asynchronously. The termination values are generalized to represent various heuristics other than min-domain. Our general framework is sound, complete, terminates and has a polynomial space complexity. We implemented several variable ordering heuristics that are well-known in centralized CSPs but could not until now be applied to the distributed setting. Our empirical study shows the significance of our framework compared to state-of-the-art asynchronous dynamic ordering algorithms for solving distributed CSP.

Introduction

Distributed artificial intelligence involves numerous combinatorial problems where multiple entities, called agents, need to cooperate in order to find a consistent combination of actions. Agents have to achieve the combination in a distributed manner and without any centralization. Examples of such problems are: traffic light synchronization [START_REF] Junges | Evaluating the performance of dcop algorithms in a real world, dynamic problem[END_REF], truck task coordination [START_REF] Ottens | Coordination agent plans trough distributed constraint optimization[END_REF], target tracking in distributed sensor networks [START_REF] Jung | Argumentation as Distributed Constraint Satisfaction: Applications and Results[END_REF], distributed scheduling [START_REF] Maheswaran | Taking DCOP to the real world: Efficient complete solutions for distributed multi-event scheduling[END_REF], distributed planning [START_REF] Bonnet-Torrés | Multiply-constrained dcop for distributed planning and scheduling[END_REF], distributed resource allocation [START_REF] Petcu | A Value Ordering Heuristic for Distributed Resource Allocation[END_REF], distributed vehicle routing [START_REF] Léauté | Coordinating Logistics Operations with Privacy Guarantees[END_REF], etc. These problems were successfully formalized using the distributed constraint satisfaction problem (DisCSP) paradigm.

DisCSP are composed of multiple agents, each owning its local constraint network. Variables in different agents are connected by constraints. Agents must assign values to their variables distributively so that all constraints are satisfied. To achieve this goal, agents assign values to their variables that satisfy their own constraints, and exchange messages to satisfy constraints with variables owned by other agents. During the last two decades, many algorithms have been designed for solving DisCSP. Most of these algorithms assume a total (priority) order on agents that is static. However, it is known from centralized CSPs that reordering variables dynamically during search improves the efficiency of the search procedure. Moreover, reordering agents in DisCSP may be required in various applications (e.g., security [START_REF] Silaghi | Generalized English Auctions by Relaxation in Dynamic Distributed CSPs with Private Constraints[END_REF]).

Agile Asynchronous Backtracking (AgileABT) [START_REF] Bessiere | Agile asynchronous backtracking for distributed constraint satisfaction problems[END_REF] is a polynomial space asynchronous algorithm that is able to reorder all agents in the problem. AgileABT is based on the notion of termination value, a tuple of agents' domain sizes. Besides implementing the min-domain ( [START_REF] Haralick | Increasing tree search efficiency for constraint satisfaction problems[END_REF]) dynamic variable ordering heuristic (DVO), the termination value acts as a timestamp for the orders exchanged by agents during search. Since the termination of AgileABT depends on the form of the termination value, the use of other forms of termination values (implementing other heuristics) may directly affect the termination of the algorithm.

In this paper, we generalize AgileABT to get a new framework AgileABT(α), in which α represents any measure used to implement a DVO (e.g., domain size in min-domain). AgileABT(α) is sound and complete. We define a simple condition on the measure α which guarantees that AgileABT(α) terminates. If the computation of the measure α also has polynomial space complexity, then AgileABT(α) has polynomial space complexity. This allows us to implement for the first time in Distributed CSP a wide variety of DVOs that have been studied in centralized CSP. To illustrate this, we implement a number of DVOs, including dom/deg [START_REF] Bessiere | MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems[END_REF] and dom/wdeg [START_REF] Lecoutre | Backjump-Based Techniques versus Conflict-Directed Heuristics[END_REF], and evaluate their performance on benchmark DisCSP problems.

The paper is organized as follows. Section 2 gives the necessary background on distributed CSP and dynamic reordering materials. It then discusses the Agile Asynchronous Backtracking algorithm for solving distributed CSP. Our general framework is presented and analyzed in Section 3. We show our empirical results in Section 4 and report related work in Section 5. Finally, we conclude in Section 6.

Background

Distributed Constraint Satisfaction Problem

The Distributed Constraint Satisfaction Problem (DisCSP) is a 5-tuple (A, X , D, C, ϕ), where A is a set of agents {A 1 , . . . , A p }, X is a set of variables {x 1 , . . . , x n }, D = {D 1 , . . . , D n } is a set of domains, where D i is the initial set of possible values which may be assigned to variable x i , C is a set of constraints, and ϕ : X → A is a function specifying an agent to control each variable. During a solution process, only the agent which controls a variable can assign it a value. A constraint C(X) ∈ C, on the ordered subset of variables X = (x j1 , . . . ,

x j k ), is C(X) ⊆ D j1 × • • • × D j k ,
and specifies the tuples of values which may be assigned simultaneously to the variables in X. For this paper, we restrict attention to binary constraints. We denote by C i ⊆ C all constraints that involve x i . A solution is an assignment to each variable of a value from its domain, satisfying all constraints. Each agent A i only knows constraints relevant to its variables (C i ) and the existence of other variables involved in these constraints (its neighbors). Without loss of generality, we assume each agent controls exactly one variable (p = n), so we use the terms agent and variable interchangeably and do not distinguish between A i and x i .

Each agent A i stores a unique order, an ordered tuple of agents IDs, denoted by λ i . λ i is called the current order of A i . Agents appearing before A i in λ i are the higher priority agents (predecessors) denoted by λ - i and conversely the lower priority agents (successors) λ + i are agents appearing after A i in λ i . We denote by λ i [k] (∀k ∈ 1..n) the ID of the agent located at position k in λ i .

Asynchronous Backtracking -ABT

The first complete asynchronous search algorithm for solving DisCSP is Asynchronous Backtracking (ABT) [START_REF] Yokoo | Distributed constraint satisfaction for formalizing distributed problem solving[END_REF][START_REF] Bessiere | Asynchronous backtracking without adding links: a new member in the ABT family[END_REF]. In ABT, agents act concurrently and asynchronously, and do not have to wait for decisions of others. However, ABT requires a total priority order among agents. Each agent tries to find an assignment satisfying the constraints with what is currently known from higher priority agents. When an agent assigns a value to its variable, it sends out messages to lower priority agents, with whom it is constrained, informing them about its assignment. When no value is possible for a variable, the inconsistency is reported to higher agents in the form of a no-good (an unfruitful value combination). ABT computes a solution (or detects that no solution exists) in a finite time. However, the priority order of agents is static and uniform across the agents.

No-goods and Explanations

During a solution process, agents can infer inconsistent sets of assignments, called no-goods. No-goods are used to justify value removals. A no-good ruling out value v i from the domain of a variable x i is a clause of the form x j = v j ∧. . .∧x k = v k → x i = v i . This no-good, which means that the assignment x i = v i is inconsistent with the assignments x j = v j ∧. . .∧x k = v k , is used by agent A i to justify removal of v i from its domain D i . The left hand side (lhs) and the right hand side (rhs) of a no-good are defined from the position of →. The variables in the lhs of a no-good must precede the variable on its rhs in the current order because the assignments of these variables have been used to filter the domain of the variable in its rhs. These ordering constraints induced by a no-good are called safety conditions in [START_REF] Ginsberg | GSAT and dynamic backtracking[END_REF]. For example, the no-good

x j = v j ∧ x k = v k → x i = v i
implies that x j ≺ x i and x k ≺ x i that is x j and x k must precede x i in the variable ordering (i.e., x j , x k ∈ λ - i ). We say that a no-good is compatible with an order λ i if all agents in its lhs appear before its rhs in λ i .

The current domain of a variable x i , maintained by A i , is composed by values not ruled out by a no-good. 4 The initial domain size (before search starts) of A i is denoted by d 0 i while its current domain size is denoted by d i . Let Σ i be the conjunction of the left hand sides of all no-goods ruling out values from D i . We explain the current domain size of D i by the following expression e i : Σ i → d i , called explanation of x i (e i ). Every explanation e i induces safety conditions:

{∀x m ∈ Σ i , x m ≺ x i }.
When all values of a variable x i are ruled out by some nogoods (Σ i → 0), these no-goods are resolved, producing a new no-good from Σ i . There are clearly many different ways of representing Σ i as a directed no-good (an implication). In standard backtracking search algorithms (like ABT), the variable, say x t , that has the lowest priority in the current order (among variables in Σ i ) must change its value. x t is called the backtracking target and the directed no-good is ng t : Σ i \ x t → x t = v t . In AgileABT the backtracking target is not necessarily the variable with the lowest priority within the conflicting variables in the current order.

Agile Asynchronous Backtracking

In AgileABT, an order λ is always associated with a termination value τ. A termination value is a tuple of positive integers (representing the sizes of the domains of other agents seen from A i ). When comparing two orders the strongest order is that associated with the lexicographically smallest termination value. The lexicographic order on agents IDs (< lex ) is used to break ties, the smallest being the strongest.

In AgileABT, all agents start with the same order. Then, every agent A i is allowed to change the order asynchronously. In the following we describe AgileABT by illustrating the computation performed within agent A i . A i can change its current order λ i only if it receives a stronger one from another agent or if itself proposes a new order (λ i ) stronger than its current order λ i . A i can only propose new orders (λ i ) when it tries to backtrack after detecting a dead-end (Σ i → 0).

In AgileABT, agents exchange the following types of messages to coordinate the search (where A i is the sender):

-ok? message is sent by A i to all lower agents (λ + i ) to ask whether its assignment is acceptable. Besides the assignment, the ok? message contains an explanation e i which communicates the current domain size of x i , the current order λ i , and the current termination value τ i stored by A i .

-ngd message is sent by A i when all its values are ruled out by Σ i . This message contains a directed no-good, as well as λ i and τ i . -order message is sent to propose a new order. This message includes the order λ i proposed by A i accompanied by the termination value τ i .

Each agent needs to compute the size of the domain of other variables to build its termination value. Hence, each agent A i stores a set E i of explanations sent by other agents. During search, A i updates E i to store new received explanations and to remove those that are no more relevant to the search state or not compatible with its current order λ i . If e k ∈ E i , A i uses this explanation to justify the size dom(k) of the current domain of x k , i.e., d k . Otherwise, A i assumes that the size of the current domain of x k is equal to d 0 k .

Algorithm 1: Computing termination value using heuristic α.

function T V α (λ) 1.
τ is an array of length n;

2. for ( j ← 1 to n ) do τ[j] ← α(λ[j]) ; 3. return τ;
In AgileABT, the termination value

τ i = [tv 1 i , . . . , tv n i ] computed by agent A i is such that tv k i = dom(λ i [k]), ∀k ∈ 1.
.n. τ i depends on the order λ i and the domain sizes of agents given by the set of explanations E i (Algorithm 1, using

T V α (λ i ) with α = dom).
In standard backtracking search algorithms, the backtracking target is always the variable that has the lowest priority among the variables in the detected conflict (i.e., Σ i ). AgileABT relaxes this restriction by allowing A i to select the target of backtracking x t among conflicting variables Σ i . The only restriction for selecting x t as a backtracking target is to find an order λ i such that τ i = T V α (λ i ) with α = dom (Algorithm 1) is lexicographically smaller than the termination value associated with the current order λ i and x t is the lowest among variables in Σ i w.r.t. λ i .

When a dead-end occurs, AgileABT iterates through all variables x t ∈ Σ i , considering x t as the target of the backtracking, i.e., the directed no-good is ng t : Σ i \ x t → x t = v t . A i then updates E i to remove all explanations containing x t (after backtracking x t assignment will be changed). Next, it updates the explanation of x t by considering the new generated no-good ng t (i.e., e t ← [Σ t ∪ lhs(ng t ) → d t -1]). Finally, A i computes a new order (λ i ) and its associated termination value (τ i ) from the updated explanations E i . λ i is obtained by performing a topological sort on the directed acyclic graph (G) formed by safety conditions induced by the updated explanations

E i (∀x m ∈ Σ k |e k ∈ E i , (x m , x k ) ∈ G) and τ i is obtained from T V α (λ i ) with α = dom (Algorithm 1)
. Let λ i be the strongest computed order over all possible targets in Σ i . If the termination value τ i associated to λ i is lexicographically smaller than the τ i associated to the current order λ i , A i reorders agents according to λ i and informs all agents about the new order λ i and its associated termination value τ i . The backtracking target is that used when A i computed λ i . If no λ i stronger than λ i exists, the backtracking target x t is the variable that has the lowest priority among Σ i in the current order λ i . For more details we refer the reader to [START_REF] Bessiere | Agile asynchronous backtracking for distributed constraint satisfaction problems[END_REF][START_REF] Wahbi | Algorithms and Ordering Heuristics for Distributed Constraint Satisfaction Problems[END_REF].

Example of running AgileABT

A 1 A 2 A 3 A 4 A 5 x 1 x 2 x 3 x 4 x 5 . = . = . x 1 = |x 5 -2| . = . < . ≥ ∀i ∈ 1..4 D i = {1, 2, 3, 4} (a) The constraint graph Data structures maintained by A 5 ∀i ∈ 1..5, λ i = [1, 2, 3, 4, 5], τ i = [4, 4, 4, 4, 4] Σ 5 : x 1 = 1 ∧ x 2 = 2 ∧ x 4 = 3 incoming messages ok? 1→5 : e 1 , x 1 = 1, λ 1 , τ 1 ok? 2→5 : e 2 , x 2 = 2, λ 2 , τ 2 ok? 3→5 : e 3 , x 3 = 2, λ 3 , τ 3 ok? 4→5 : e 4 , x 4 = 3, λ 4 , τ 4 e 1 : [] → d 1 = 4 e 2 : [x 1 = 1] → d 2 = 3 e 3 : [x 1 = 1] → d 3 = 3 e 4 : [x 3 = 2] → d 4 = 2 explanations (E 5 ) [x 1 = 1] → x 5 = [x 2 = 2] → x 5 = [x 1 = 1] → x 5 = [x 4 = 3] → x 5 = no-goods (D 5 = ∅) (b)
Explanations and no-goods maintained by A5

A 5 : when choosing x 1 as backtracking target for Σ 5

Updated explanations (c) A5: updated explanations with x1 as target

e 1 : [x 2 = 2 ∧ x 4 = 3] → d 1 = 3 e 2 : [] → d 2 = 4 e 3 : [] → d 3 = 4 e 4 : [x 3 = 2] → d 4 = 2 e 5 : [x 2 = 2 ∧ x 4 = 3] → d 5 = 2
A 5 : target selection Selected no-good: ng 1 : [x 4 = 3 ∧ x 2 = 2] → x 1 =1 λ 5 = [1, 2, 3, 4, 5] τ 5 = [4, 4, 4, 4, 4]
target agent ordering termination value

x 1 = 1 λ 5 = [3, 4, 2, 5, 1] τ 5 = [4, 2, 4, 2, 3] x 2 = 2 λ 5 = [1, 3, 4, 5, 2] τ 5 = [4, 3, 2, 1, 2] x 4 = 3 λ 5 = [1, 2, 5, 3, 4] τ 5 = [4, 3, 1, 3, 1] (d) A5: selection of target (x1)
Σ 5 : {x 1 = 1 ∧ x 2 = 2 ∧ x 4 = 3}.
A 5 iterates through all variables x t ∈ Σ 5 , considering x t as the target of the backtracking. Figure 1c shows the updates on the explanations stored in A 5 (E 5 ) when it considers x 1 as the target of the backtracking (i.e., x t = x 1 ). A 5 updates E 5 to remove all explanations containing x 1 (i.e., e 2 and e 3 ) and considering the new generated no-good ng 1 in the explanation of x 1 , i.e., e 1 (fig. 1c, left). Finally, A 5 computes a new order (λ 5 ) and its associated termination value (τ 5 ) from the updated explanations E 5 . λ 5 is obtained by performing a topological sort on the directed acyclic graph formed by safety conditions induced by the updated explanations E 5 (fig. 1c, right). Figure 1d presents the computed orderings and their associated termination values (by topological sort) when considering each x t ∈ Σ 5 as backtracking target. The strongest computed order (e.g, λ 5 = [3, 4, 2, 5, 1], τ 5 = [4, 2, 4, 2, 3]) is that computed when considering x 1 as backtracking target. Since λ 5 is stronger than λ 5 , A 5 changes its current order to λ 5 and proposes this ordering to all other agents through order messages (i.e., order : λ 5 , τ 5 ). Then, A 5 sends the no-good ng 1 to agent x 1 .

Algorithm 2: AgileABT(α): Procedures for changing the order by A i .

procedure processOrder(λj, τj) changeOrder(λ i , τ i ) ;

5.

sendMsg: order λi, τi to all agents in A ; procedure changeOrder(λ , τ ) 6. λi ← λ ; τi ← τ ; 7. remove no-goods and explanations incompatible with τi ;

It has been proved that AgileABT is sound, complete and terminates [START_REF] Bessiere | Agile asynchronous backtracking for distributed constraint satisfaction problems[END_REF][START_REF] Wahbi | Algorithms and Ordering Heuristics for Distributed Constraint Satisfaction Problems[END_REF]. The termination proofs of AgileABT are based on the fact that the termination value is a tuple of positive integers (representing the expected sizes of the domains of other agents) and, as search progresses, these tuples can only decrease lexicographically. Thus, any change to the form of the termination values (i.e. implemented heuristic) may directly affect the termination of AgileABT.

Generalized AgileABT

In AgileABT, the termination value can be seen as an implementation of the dom dynamic variable ordering heuristic. In this section, we generalize Ag-ileABT to get a new framework AgileABT(α), in which α represents any measure used to implement a DVO. The original AgileABT [START_REF] Bessiere | Agile asynchronous backtracking for distributed constraint satisfaction problems[END_REF] is then equivalent to AgileABT(dom).

Due to space constraints, we only present in Algorithm 2 the pseudo-code of AgileABT(α) related to the cases where an agent (A i ) may change its current order λ i (i.e., calling procedure changeOrder) where ≺ tv is an ordering on the termination values and tv = represents the equality. A i can change its current order λ i and its associated termination value τ i (procedure changeOrder, line 6) in two cases. The first case is when A i receives a stronger order λ j associated with the termination value τ j from another agent A j (processOrder, line 1). The second case occurs when A i itself proposes a new order (λ i ) associated with a termination value τ i that is preferred (w.r.t. ≺ tv ) to the termination value τ i associated to its current order λ i (procedure proposeOrder, lines 3 and 4).

The soundness, completeness and polynomial space complexity 5 of AgileABT(α) are directly inherited from original AgileABT, i.e., AgileABT(dom). The only property that could be jeopardized is the termination of the algorithm. In the following we define a sufficient condition on termination values and the ordering ≺ tv which guarantees that AgileABT(α) (Algorithm 2) terminates. Next, we will discuss a condition on the measure α that allows the termination values to obey the required condition.

Condition 1

The priority ordering ≺ tv is a well-ordering on the range of function T V α . Proposition 1. AgileABT(α) terminates if ≺ tv obeys condition 1.

Proof. Following the pseudo-code of AgileABT(α), an agent A i can only change its current order in two cases (lines 1 and 3). The termination values can only decrease w.r.t. the well-ordering ≺ tv , or remain the same and have a lexicographically decreasing agent order (line 1). The agent order cannot decrease lexicographically indefinitely and by condition 1 the termination values cannot decrease indefinitely w.r.t. ≺ tv . Therefore, AgileABT(α) cannot change the order indefinitely. Once the order stops changing, all agents will eventually have the same termination value and the same order to which it is attached (line 5, Algorithm 2). This order corresponds to the strongest order computed in the system so far. Since the agent order is now common and static, AgileABT(α) will behave exactly like ABT, which terminates.

To guarantee that AgileABT(α) terminates we need to define a well-ordering ≺ tv on the termination values. Let α be the measure applied to the agents, and let the function T V α be as defined in Algorithm 1. Let S be the range of α and let ≺ α be a total preference order on S. Definition 1 Let λ i and λ j be two total agent orderings, τ i = T V α (λ i ) and τ j = T V α (λ j ). The termination value τ i is preferred (w.r.t. ≺ tv ) to τ j (i.e., τ i ≺ tv τ j ) if and only if τ i is lexicographically less than τ j (w.r.t. ≺ α ). In other words,

τ i ≺ tv τ j iff ∃ k ∈ 1..n such that α(λ i [k]) ≺ α α(λ j [k]) and ∀p ∈ 1..k-1 α(λ i [p])=α(λ j [p]).
Condition 2 The priority ordering ≺ α is a well-ordering on the range of measure α. Proposition 2. AgileABT(α) terminates if ≺ α obeys condition 2.

Proof. Suppose condition 2 is satisfied but AgileABT(α) does not terminate. Then, by proposition 1, condition 1 is not satisfied. Therefore, ≺ tv is not a well-ordering on the range of T V α . In other words, we can obtain an infinite decreasing sequence of termination values using a lexicographic comparison w.r.t. ≺ α . Therefore we must have an infinite decreasing sequence of α(λ[k]) values, for some k ∈ 1..n. But this contradicts condition 2 that forces ≺ α to be a wellordering on S. Therefore AgileABT(α) must terminate.

In the following, we consider a number of different heuristics that are known to be effective in reducing search in centralized CSP, but which could not before now be applied to distributed CSP. We show how the measures that inform these heuristics can obey condition 2, and thus can be applied in the general AgileABT(α) framework.

Neighborhood based variable ordering heuristics

In the first category we try to take into account the neighborhood of each agent. We implemented three DVOs (dom/deg, dom/f deg and dom/pdeg) to obtain respectively AgileABT(dom/deg), AgileABT(dom/f deg), and AgileABT(dom/pdeg). In AgileABT(dom/deg), each agent A i only requires to know the degree deg(k) of each agent A k in the problem. deg(k) (i.e., the number of neighbors of A k ) can be obtained before the search starts as is the case for d 0 k of each agent. Afterwards,

A i computes τ i = T V dom/deg (λ i ) using α(k) = dom(k) deg(k) (Algorithm 1, line 2).
In AgileABT(dom/f deg) and AgileABT(dom/pdeg) each agent A i is required to know the set of neighbors of each agent A k because it will need to compute the incoming degree pdeg(k) and the outgoing degree f deg(k) of A k for any proposed order. Again this information can be known in a preprocessing step before running AgileABT(α). Afterwards,

A i computes τ i from T V dom/f deg (λ i ) (resp. T V dom/pdeg (λ i )) using α(k) = dom(k) f deg(k) (resp. α(k) = dom(k) pdeg(k) )
where the incoming degree pdeg(k) in λ i is the number of neighbors of A k that appear before k in λ i and the outgoing degree f deg(k) in λ i is the number of neighbors of A k that appear after k in λ i .

Conflict-directed variable ordering heuristic

The second category covers the conflict-directed variable ordering heuristic: dom/wdeg. In order to compute τ i using α(k) = dom(k) wdeg(k) , each agent A i in AgileABT(dom/wdeg) requires to know the weighted degree wdeg(k) of each other agent A k . A i maintains its weighted degree, wdeg(i), that it computes and the weighted degrees received from other agents, wdeg(k). In order to compute the weighted degree, wdeg, (Algorithm 3) each agent A i maintains a counter weight[C] for each constraint C(X) in C i . Whenever a domain (D j where x j ∈ X) is wiped-out while propagating C(X) (line 3, Algorithm 3), weight[C] is incremented. Before assigning its variable and sending an ok? message to lower priority agents, A i computes its weighted degree, wdeg(i), by summing up (line 6, Algorithm 3) the weights of all constraints in C i having at least two unassigned variables ( [START_REF] Lecoutre | Backjump-Based Techniques versus Conflict-Directed Heuristics[END_REF]). However, to guarantee that AgileABT(dom/wdeg) terminates we only update wdeg(i) if the new computed weighted degree (wdeg) does not exceed a limit W on which all agents agree beforehand (line 7, Algorithm 3). In AgileABT(dom/wdeg), whenever A i sends an ok? message it attaches to this message the largest weighted degree computed so far wdeg(i).

Theoretical Analysis

Lemma 1. All measures α above are a well-ordering on a subset of Q w.r.t. <.

Proof. We proceed by contradiction. Suppose there is an infinite decreasing sequence of values of α(k). In all measures above, α(k) = dom(k) ω(k) , for some ω(k). dom(k) is the expected domain size of the agent A k . It is obvious that dom(k) is a well-ordering on N w.r.t. <, and so cannot decrease indefinitely. Therefore, ω(k ) must increase indefinitely. ω(k ) is a positive integer whose value depends on the measure used. Two cases were explored in this paper. The first case concerns the family of degree-based heuristics (deg, pdeg, f deg). In this case, all of the ω(k ) are greater than or equal to 1 and smaller than the number of agents in the system (i.e., n) because an agent is at most constrained to n -1 other agents. Thus, 1 ≤ ω(k ) ≤ n -1. The second case is related to the heuristic wdeg. We have outlined in section 3.2 that an agent is not allowed to increment its weight when it has reached the limit W set beforehand (Algorithm 3, line 7). Thus, 1 ≤ ω(k ) ≤ W . In both cases ω(k ) cannot increase indefinitely. Therefore for all measures presented above, of the form α(k) = dom(k) ω(k) , cannot decrease indefinitely, and so α(k) is a well-ordering w.r.t. <.

Empirical Analysis

In this section we experimentally compare AgileABT(α) 6 using different DVO heuristics to three other algorithms: ABT, ABT DO with nogood-triggered heuristic (ABT DO-ng) [START_REF] Zivan | Dynamic Ordering for Asynchronous Backtracking on DisC-SPs[END_REF] and ABT DO with min-domain retroactive heuristic (ABT DO Retro(mindom)) [START_REF] Zivan | Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF]. All experiments were performed on the DisChoco 2.0 platform [START_REF] Wahbi | DisChoco 2: A Platform for Distributed Constraint Reasoning[END_REF], 7 in which agents are simulated by Java threads that communicate only through message passing.

When comparing distributed algorithms, the performance is evaluated using two common metrics: the communication load and computation effort. Communication load is measured by the total number of exchanged messages among agents during algorithm execution (#msg) [START_REF] Lynch | Distributed Algorithms[END_REF]. Computation effort is measured by the number of non-concurrent constraint checks (#ncccs) [START_REF] Zivan | Parallel Backtrack search on DisCSPs[END_REF]. #ncccs is the metric used in distributed constraint solving to simulate computation time, but for dynamic reordering algorithms its variant generic #ncccs is used [START_REF] Zivan | Message delay and DisCSP search algorithms[END_REF]. Algorithms are evaluated on three benchmarks: uniform binary random DisCSPs, 6 For AgileABT(dom/wdeg), we fixed W = 1, 000. But, varying W made negligible difference to the results.

Uniform binary random DisCSPs

Uniform binary random DisCSPs are characterized by n, d, p 1 , p 2 , where n is the number of agents/variables, d is the number of values in each domain, p 1 is the network connectivity defined as the ratio of existing binary constraints to possible binary constraints, and p 2 is the constraint tightness defined as the ratio of forbidden value pairs to all possible pairs. We solved instances of two classes of random DisCSPs: sparse problems 20, 10, 0.2, p 2 and dense problems 20, 10, 0.7, p 2 . We varied the tightness from 0.1 to 0.9 by steps of 0.05. For each pair of fixed density and tightness (p 1 , p 2 ), we generated 20 instances, solved 5 times each. We report average over the 100 execution.

Figures 2 and3 show the results on sparse respectively dense uniform binary random DisCSPs. In sparse problems (Figure 2), AgileABT(α) outperforms all other algorithms on both #msg and #ncccs. ABT with AC-2001 is significantly the slowest algorithm but it requires fewer messages than ABT DOng. Regarding the speedup, AgileABT(α) shows almost an order of magnitude improvement compared to ABT and they all improve on ABT DO-ng and ABT DO Retro(mindom). Comparing AgileABT(α) algorithms, neighborhood based heuristics (i.e., deg, pdeg and f deg) show an almost two-fold improvement over dom and wdeg on #ncccs. This improvement is even more significant on #msg. wdeg requires fewer messages than dom. In dense problems (Figure 3), neighborhood based heuristics outperform all other algorithms both on #msg and #ncccs. ABT requires almost half the #msg of ABT DO Retro(mindom), AgileABT(dom), and AgileABT(dom/wdeg). ABT DO-ng is always the algorithm that requires more messages. AgileABT(dom/wdeg) shows poor performance. It is slower and requires more messages than AgileABT(dom).

Distributed graph coloring problems

Distributed graph coloring problems are characterized by n, d, p 1 , where n, d and p 1 are as above and all constraints are binary difference constraints. We

Composed random instances:

We also evaluate all algorithms on two sets of unsatisfiable composed random instances used to evaluate the conflict-directed variable ordering heuristic in cen-tralized CSP [START_REF] Roussel | Xml representation of constraint networks: Format XCSP 2[END_REF][START_REF] Boussemart | Boosting systematic search by weighting constraints[END_REF]. 8 Each set contains 10 different instances where each instance is composed of a main (under-constrained) fragment and some auxiliary fragments, each of which being grafted to the main one by introducing some binary constraints. Each instance contains 33 variables and 10 values per variable, and as before, each variable is controlled by a different agent. We solved each instance 5 times and present the average over 50 executions in Table 2. The results show that AgileABT(dom/pdeg) outperforms all other algorithms in both classes. The second best algorithm for solving these instances is AgileABT(dom). ABT shows very poor performance on solving these problems followed by ABT DO-ng that cannot solve instances in the second class (25-1-40) within the limits we fixed for all algorithms (10 8 #msg and 10 9 #ncccs). Regarding AgileABT(α) DVOs, wdeg seems to pay off on these instances compared to dom/deg and dom/f deg.

In 25-1-40, AgileABT(dom/deg) outperforms ABT DO Retro(mindom), but the opposite happens for 25-1-25.

Discussion

Looking at all results together, we come to the straightforward conclusion that AgileABT(α) with neighbourhood-based heuristics, namely deg, f deg and pdeg perform very well compared to other techniques. We think that neighbourhoodbased heuristics perform well thanks to their ability to take into account the structure of the problem [START_REF] Bessiere | MAC and Combined Heuristics: Two Reasons to Forsake FC (and CBJ?) on Hard Problems[END_REF]. Distinctly, among these three heuristics dom/pdeg seems to be the best one because of the limited changes on the agent at the first position. In dom/pdeg τ [START_REF] Bessiere | Agile asynchronous backtracking for distributed constraint satisfaction problems[END_REF] = dom(λ [START_REF] Bessiere | Agile asynchronous backtracking for distributed constraint satisfaction problems[END_REF]) because pdeg(λ[1]) = 1. Thus, the number of order changes (cost on messages) in AgileABT(dom/pdeg) is reduced. Note that the strength of AgileABT(α) is that it enables any ordering to be identified and executed as the algorithm runs. However, each change invokes a series of coordination messages, and so too many changes of order will have a negative impact.

On the other hand the AgileABT(α) with the conflict-directed variable ordering heuristic, namely wdeg, shows a relatively poor performance. This fact can be explained by the limited amount of constraint propagation performed by DisCSP algorithms. Furthermore, asynchrony affects reception and treatment of ok? and ngd messages and has a direct impact on the computation of weights and new orders. For some instances of the coloring problem, the performance of the conflict-directed heuristic varies significantly from one execution to another, indicating it is more sensitive to the asynchrony than the other heuristics.

Related Work

Bliek ( [START_REF] Bliek | Generalizing partial order and dynamic backtracking[END_REF]) proposed Generalized Partial Order Dynamic Backtracking (GPODB), an algorithm that generalizes both Partial Order Dynamic Backtracking (PODB) [START_REF] Ginsberg | GSAT and dynamic backtracking[END_REF] and Dynamic Backtracking (DBT) [START_REF] Ginsberg | Dynamic Backtracking[END_REF]. This generalization was obtained by relaxing the safety conditions of PODB which results in additional flexibility. AgileABT has some similarities with PODB and GPODB because AgileABT also maintains a set of safety conditions. However, both PODB and GPODB are subject to the same restriction: when a dead end occurs, the backtracking target of the generated no-good must be selected such that the safety conditions induced by the new no-good satisfy all existing safety conditions. By contrast, AgileABT overcomes this restriction by allowing the violation of existing safety conditions by relaxing some explanations.

Silaghi et al. proposed Asynchronous Backtracking with Reordering (ABTR) [START_REF] Silaghi | Framework for modeling reordering heuristics for asynchronous backtracking[END_REF][START_REF] Silaghi | Generalized Dynamic Ordering for Asynchronous Backtracking on DisCSPs[END_REF][START_REF] Silaghi | ABT with Asynchronous Reordering[END_REF]. In ABTR, a reordering heuristic identical to the centralized dynamic backtracking [START_REF] Ginsberg | Dynamic Backtracking[END_REF] was applied to ABT. The authors in [START_REF] Zivan | Dynamic Ordering for Asynchronous Backtracking on DisC-SPs[END_REF] proposed Dynamic Ordering for Asynchronous Backtracking (ABT DO) [START_REF] Zivan | Dynamic Ordering for Asynchronous Backtracking on DisC-SPs[END_REF]. When an ABT DO agent assigns a value to its variable, it can reorder lower priority agents. In other words, an agent on a position j can change order of the agents on positions j +1 through n. The authors in [START_REF] Zivan | Dynamic Ordering for Asynchronous Backtracking on DisC-SPs[END_REF] proposed three different ordering heuristics to reorder lower priority agents: random, min-domain and nogood-triggered inspired by dynamic backtracking [START_REF] Ginsberg | Dynamic Backtracking[END_REF]. Their experimental results show that nogood-triggered (ABT DO-ng), where the generator of the no-good is placed just after the target of the backtrack, is best.

A new kind of ordering heuristics for ABT DO is presented in [START_REF] Zivan | Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF] for reordering higher agents. These retroactive heuristics enable the generator of a no-good (backtrack) to be moved to a higher position than that of the target of the backtrack. The resulting algorithm is called ABT DO Retro. The degree of flexibility of these heuristics depends on the size of the no-good storage capacity K, which is predefined. Agents are limited to store no-goods with a size equal to or smaller than K. The space complexity of the agents is thus exponential in K. However, the best of those heuristics, ABT DO Retro(mindom) [START_REF] Zivan | Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF][START_REF] Mechqrane | Corrigendum to "Min-Domain Retroactive Ordering for Asynchronous Backtracking[END_REF], does not need any no-good storage. In ABT DO Retro(mindom), the agent that generates a no-good is placed between the last and the second last agents in the no-good if its domain size is smaller than that of the agents it passes on the way up.

Conclusion

We proposed a general framework for reordering agents asynchronously in DisC-SPs which can implement many different dynamic variable ordering heuristics. Our general framework is sound, complete, and has a polynomial space complexity. We proved that a simple condition on the measure used in the heuristics is enough to guarantee termination. We implemented several DVOs heuristics that are well-known in centralized CSP but were not able to be used before in the distributed CSP. Our empirical study shows the significance of these DVOs on a distributed setting. In particular, it highlights the good performance of neighborhood based heuristics. Future work will focus on designing new DVOs that can be used in AgileABT(α).

Figure 1

 1 Figure 1 presents an example of a possible execution of AgileABT on a simple problem. This problem (fig. 1a) consists of 5 agents with the following domains ∀i ∈ 1..5, D i = {1, 2, 3, 4} and 6 constraints among these agents c 12 : x 1 = x 2 , c 13 : x 1 = x 3 , c 15 : x 1 = |x 5 -2|, c 25 : x 2 = x 5 , c 34 : x 3 < x 4 , and c 45 : x 4 ≥ x 5 . All agents start with the same initial ordering λ i = [1, 2, 3, 4, 5] associated with

Fig. 1 :

 1 Fig. 1: An example of a possible execution of AgileABT on a simple problem.

Algorithm 3 :

 3 Compute the wdeg of agent A i (wdeg(i)). // Filtering xj ∈ X by propagating C(X) function revise(C(X), xj) 1. foreach ( vj ∈ Dj ) do 2. if ( ¬hasSupport(C(X), vj, xj) ) then Dj ← Dj \ vj; 3. if ( Dj = ∅ ) then weight[C] ← weight[C] + 1 ; 4. return Dj = ∅; procedure computeWeight() 5. wdeg ← 1; 6. foreach ( C(X) ∈ Ci | nbU nassigned(X) > 1 ) do wdeg ← wdeg + weight[C]; 7. wdeg(i) ← min(wdeg, W ) ;

Fig. 2 :

 2 Fig. 2: Sparse uniform binary random DisCSPs

Fig. 3 :

 3 Fig. 3: Dense uniform binary random DisCSPs

Table 1 :

 1 Distributed graph coloring problems

	Algorithm	15, 5, 0.65	25, 5, 0.45
		#msg #ncccs	#msg #ncccs
	AgileABT(dom/wdeg)	90,630 188,991 2,600,016 2,783,132
	AgileABT(dom/f deg)	51,820 104,517 940,481 937,861
	AgileABT(dom/pdeg)	47,949 89,514 454,998 434,540
	AgileABT(dom/deg)	44,083 78,050 607,927 505,140
	AgileABT(dom)	79,518 204,012 3,001,538 3,836,301
	ABT DO Retro(mindom) 73,278 115,850 1,089,024 830,423
	ABT DO-ng	157,873 282,737 4,547,565 3,639,791
	ABT	58,817 288,803 1,626,901 3,836,391

Table 2 :

 2 Composed random instances report the average on 100 instances of two classes n = 15, d = 5, p 1 = 0.65 and n = 25, d = 5, p 1 = 0.45 in Table1. Again, AgileABT(α) using neighborhood based DVO are by far the best algorithms for solving both classes. ABT DO-ng shows poor performance on solving those problems. ABT DO Retro(mindom) outperforms AgileABT(dom) in both classes. Comparing AgileABT(dom) to AgileABT(dom/wdeg), dom is slower than wdeg but it requires fewer messages. In n = 15, d = 5, p 1 = 0.65 , only AgileABT(α) using neighborhood based DVO outperform ABT on messages while other asynchronous dynamic ordering algorithms require more messages.

	Instances	25-1-25	25-1-40
	Algorithm	#msg	#ncccs	#msg	#ncccs
	AgileABT(dom/wdeg)	85,521	30,064	89,804	33,461
	AgileABT(dom/f deg)	146,668	219,980 1,337,552 2,830,906
	AgileABT(dom/pdeg)	57,079	16,043 54,667	17,704
	AgileABT(dom/deg)	122,735	309,064 740,669 2,793,670
	AgileABT(dom)	57,451	20,944	59,859	23,405
	ABT DO Retro(mindom)	67,022	41,401	96,783	59,980
	ABT DO-ng	1,329,257 1,614,960	> 10 8	> 10 9
	ABT	2,850,137 22,042,094 9,429,088 72,524,742

To stay polynomial, Ai keeps only one no-good per removed value.

If the computation of the measure α also has polynomial space complexity.

http://www.cril.univ-artois.fr/∼lecoutre/benchmarks.html