François David Betaille
email: david.betaille@ifsttar.fr.

François Peyret

Miguel Ortiz

David Bétaille

How to enhance accuracy and integrity of satellite positioning for mobility pricing in cities: the Urban Trench method

Keywords: geofencing, GNSS accuracy, multipath, 3D city model

Résumé

La taxation des déplacements mesurés par GNSS est assurément un levier puissant de régulation du trafic et de financement des infrastructures, sans avoir besoin d'équipements de bord de voie. Mais le positionnement GNSS en ville reste difficile, à cause de la faible visibilité et des réflexions du signal sur le bâti (multi-trajets). Celles-ci au mieux se combinent avec le signal direct, au pire, quand le signal direct est masqué, créent des biais de plusieurs dizaines de mètres sur la mesure de pseudo-distance et la position calculée au final. La méthode proposée ici est basée sur un modèle 3D simplifié du bâti de part et d'autre des rues, dénommé "Tranchée Urbaine" pour cette raison, et dont on bénéficie en termes de test de visibilité satellitaire et calcul de position. Des sections de rue homogènes sont décrites par trois paramètres: largeur, hauteur du bâti et position transversale du véhicule. Ces paramètres permettent d'identifier les satellites en vue directe et d'estimer les trajets additionnels fait par réflexions. Dans des environnements comme les Grands Boulevards à Paris, on a montré que la position calculée aux moindres carrés peut être améliorée de 70% après application de nos tests de visibilité et nos corrections de biais, sans dégradation de la disponibilité.

Mots-clé: geofencing ; précision des GNSS ; multi-trajets ; modèle 3D urbain.

Introduction

GNSS systems have significant potential in the development of Intelligent Transport Systems (ITS) and associated services. Nevertheless, a major technical issue with respect to safety-critical and liability-critical applications (urban tolling for instance) is the Quality of Service of the position, not only in terms of accuracy, continuity and availability, but also integrity, which is the level of trust in the positioning solution. In strongly constrained environments, like city centers, the propagation phenomena in the surrounding of the antenna, more precisely diffraction and multipath are responsible for severe errors on the raw observables that are measured by the receivers [START_REF] Braasch | Multipath effects. Chapter 14 in GPS: theory and applications[END_REF]. The most severe deviations (up to several tens of metres on pseudo-ranges measurements) may occur in case the reflected path is the only tracked, whereas the direct one is blocked. Such signals are called "Non-Line-Of-Sight" (NLOS) signals. In this context, the standard methods of computing a position and the associated protection level coming from the civil aviation community (MOPS, 2006) are no longer adapted and it is necessary to develop new methods customized to the specificity of the terrestrial environments, especially urban environments.

State of the art

SBAS error models and RAIM

Satellite-Based Augmentation Systems, like EGNOS, is the usual method for improving Quality of Service of GNSS receivers, and particularly their accuracy and integrity. All the signals covering a continent are permanently monitored, in order to detect any abnormal behaviour and to update the error models at the raw measurements level, these error models being finally used by the Integrity Monitoring module to estimate a reliable protection level supposed to over bound the error at the position level [START_REF] Brown | Receiver Autonomous Integrity Monitoring[END_REF]. This has been designed for the civil aviation context, and does not pay attention to multipath error sources locally, with typical measurement biases.

FDE (Fault Detection and Exclusion

) is another mechanism for integrity monitoring developed by the civil aviation community, more known under the name of RAIM (Receiver Autonomous Integrity Monitoring). FDE is totally autonomous since it is based on statistical tests applied to the available measurements. This mechanism start to be implemented in the navigation software of some receivers, coupled or not with instruments like odometer or gyroscope commonly used in the automotive sector [START_REF] Gao | Development of precise GPS/INS/wheel speed sensor/yaw rate sensor integrated vehicular positioning system[END_REF][START_REF] Marchand | Characterization of GPS multipath for passenger vehicles across urban environments[END_REF]. They help in preventing corrupted observations to false the navigation solutions, but they are based on 2 hypotheses: a good redundancy and no more than a unique defect at the same time, which is generally not satisfied. In addition, unbiased normal distributions are again assumed.

Map aided solvers

Another approach takes advantage of the digital map constraints corresponding the domain where the navigation solutions should lie, e.g. a network of streets in cities and road maps in general. The positioning problem can, for instance, be solved using particle filtering in which the particles leaving the road are eliminated [START_REF] Toledo-Moreo | Fusing GNSS, dead-reckoning and enhanced maps for road vehicle lane-level navigation[END_REF].

For a few years, in addition to navigation process improvements, researchers, have addressed the use of 3D models of the environment to analyze reception conditions and mitigate multipath phenomena: [START_REF] Bradbury | Code multipath modelling in the urban environment using large virtual reality city models: determining the local environment[END_REF], to the best of our knowledge, was the former. But the initial point where to compute the local geometry is a tricky problem! Additional information through vision brings about operational applications: in [START_REF] Meguro | GPS multipath mitigation for urban area using omnidirectional infrared camera[END_REF], the authors use a fish-eye infra-red camera to map the satellite positions with respect to the surrounding buildings. More recently, the CAPLOC project [START_REF] Marais | Accurate Localisation Based on GNSS and Propagation Knowledge for Safe Applications in Guided Transport[END_REF] addresses this issue for guided transport in urban environments, using also a fish-eye camera on the vehicle and aiming at building in real-time a 3D model from the successive images. Without vision, car turn rate and wheel speed sensors are of great interest, as well as road constraints: actually [START_REF] Obst | Multipath Detection with 3D Digital Maps for Robust Multi-Constellation GNSS/INS Vehicle Localization in Urban Areas[END_REF] suggests ray-tracing in a simplified 3D model of buildings, whilst (Peyret et al., 2011) relies on a very sophisticated data base.

The urban trench model

Previous works proved that a priori knowledge of the environment is of great use to characterize conditions of GNSS reception, leading to a significant improvement of the observables quality and, as a consequence, the quality of the computed position.

The research investigations reported in this communication addresses a new way 3D map data can improve the positioning computation, by both GPS raw data filtering and correction. The information contained in the map has been designed as simple as possible, so that it matches the requirement of usual embedded and navigable maps. This information should actually be registered as a set of attributes applicable to the standard polyline structure of digital maps.

The width, (W), height, (H), and lateral position, (P), urban trench parameters

The first step of the method consists in a characterization of the environment, defined by the triplet of parameters (W=Width of the street, H=Height of buildings, P=lateral Position of the vehicle). All the circuit that will be travelled by the vehicle is divided into homogenous sections having approximately the same constant geometric features: width of the street and height of the buildings, pluslast but not leastthe lateral position of the receiver in the street whilst travelling there. This indicator is normalized and takes the value zero for the extreme left side of the street and the value one for the extreme right side. Finally, each section of the circuit is identified by a locally applicable triplet. This 2D characterization is embedded into the navigation database in order to give, for each satellite, at each time, the urban configuration surrounding the satellite receiver.

The mask of visibility

The second step of the method is based upon the hypothesis that in an urban constrained environment, the vision space above the vehicle is limited by the buildings. In this approach, the street is modeled by namely an "Urban Trench", defined by the triplet of parameters (W, H, P), of infinite length, in which the satellite receiver is in the center. (Note that the height of the antenna above the ground is deducted from H.) From this model, the algorithm of the "mask of visibility" discriminates the satellites in LOS from the satellites in NLOS. This detection depends on the following parameters:  el b defines the critical elevation angle of the buildings imposed by the urban configuration. It is computed according to the triplet of parameters (W, H, P);  β represents the difference between the considered satellite azimuth and the orientation of the street. Its value determines if the satellite above the street is in the left side or in the right side.

A deterministic computation of the number of reflections performed by the signal can easily be made, under specular reflection hypothesis, knowing the azimuth and the elevation of the satellite. The number of reflections that may occur is supposed not to exceed 3. The algorithm is summarized for the two possible cases (left and right) in Table 1. (Note that P is replaced by (1-P) between left and right sides.)

Table 1. Definition of the critical elevation angle, i.e. the elevation angle under which 1 reflection occurs, and similarly for the occurrence of 2 and 3 reflections.

For the satellites situated on the left side of the street For the satellites situated on the right side of the street

0      or    2          2 or     0 ) ( 1  sin PW H arctg el el b   ) ( ) 1 ( 1  sin W P H arctg el el b    ) ( ) 2 ( 2  sin W P H arctg el   ) ( )) 1 ( 2 ( 2  sin W P H arctg el    ) ( ) 2 ( 3  sin W P H arctg el   ) ( )) 1 ( 2 ( 3  sin W P H arctg el   
Finally, the condition of visibility by a receiver is given according to the value taken by the satellite elevation: if the satellite elevation angle is lower than the elevation of the buildings, then the satellite is in NLOS (outside the "mask of visibility"), otherwise it is in LOS (inside the "mask of visibility"). An illustration obtained by such method is given in Figure 2, corresponding to the street configuration depicted in Figure 1.

The additional distance

Once the number of reflections has been determinated, the additional path Δ d performed by the signal can easily be computed, as shown in Figure 3. Geometrical rules of specular reflection apply. Table 2 gives the additional distances corresponding to 1, 2 or 3 specular reflections. Note that an even number of reflections will make a similar additional distance for both sides of the street Table 2. Additional signal travelled distances for 1, 2 and 3 reflections resp.

For the satellites situated on the left side of the street For the satellites situated on the right side of the street

0      or    2          2 or     0 ) ( ) ( ) 1 ( 2 1  sin el cos P W d    ) ( ) ( )) 1 ( 1 ( 2 1  sin el cos P W d     ) ( ) ( 2 2  sin el Wcos d   ) ( ) ( 2 2  sin el Wcos d   ) ( ) ( ) 2 ( 2 3  sin el cos P W d    ) ( ) ( )) 1 ( 2 ( 2 3  sin el cos P W d    

Experimental validation

The LOS-only and mixed solutions

The navigation process chosen is a basic un-weighted least squares solver, with no filtering like Kalman, in order to emphasize the impact of the satellite LOS/NLOS separation. It runs epoch per epoch with a strategy that is twofold:  First, LOS-only: one computes solutions at the epochs when at least 4 LOS satellites remain after NLOS satellites have been removed, which diminishes the availability of the final position;  Second, mixed: the NLOS pseudo-range measurements are kept in the computation, but they are corrected in accordance to the local geometry characterized by Urban Trench modeling.

They are introduced progressively, starting from the highest elevation with 1 reflection, plus 2 and 3 reflections if needed, and applying the additional distance correction corresponding.

Experimental set-up and test cases

VERT, the Ifsttar Geolocalization test vehicle (cf. Figure 4), has been equipped with an IXSea inertial unit, and a dual-frequency Novatel GPS receiver. In post-processing with a base station, this equipment makes it possible the determination of the trajectory performed with an accuracy of less than 10 cm. The receiver and antenna in test are set up on board too.

The leverarm (i.e. the 3D vector) between the Novatel antenna and that of the receiver in test being compensated, the "true" position of the antenna of the receiver in test is finally determined. In term of positioning accuracy, the gainin the streets where the model applieshas been experimentally valued at between 30% in Nantes and Toulouse, and up to 70% in Paris, with the same availability as with a standard solver considering all satellites (cf. Figures 5a to 5d).

Conclusions and perspectives

The Urban Trench Model and a verification of its ability to enhance accuracy and availability are the main contributions of the paper. An improvement of up to 70% of the 3D positioning accuracy has been obtained in Paris Grands Boulevards, with the same availability as a standard solution. The method is potentially applicable in other cities with similar urbanisation.

Further steps in the process are twofold :  suggest an algorithm that automatically determine the Urban Trench Model parameters starting from a usual 3D city model;  test the sensitivity of the method with respect to the lateral position of the vehicle, and develop a multiple hypotheses strategy for that purpose.

Fig. 1 .

 1 Fig. 1. Overview of the characteristics of a street in Nantes (W=10 m, H=8 m, P=0.5), typical of an urban trench.

Fig. 2 .

 2 Fig. 2. The corresponding mask of visibility.

Fig. 3 .

 3 Fig. 3. Urban trench W, H, P triplet and 2 NLOS satellites: one with an azimuth orthogonal to the street direction, i.e. β=-/2.

Fig. 4 .

 4 Fig. 4. Vert, the Ifsttar Geolocalization test vehicle.

Fig. 5 .

 5 Fig. 5. Cumulative distribution functions of the absolute error in 3D for standard and Urban Trench solutions, in Nantes, Paris XIIth district, Grands Boulevards, and Toulouse.

Table 3a .

 3a Results in Nantes (feasibility test).

		ALL SVS SOLUTIONS		LOS ONLY SOLUTIONS
	nb of ep.	av. %	nb. svs.	error med.	av. %	nb. svs.	error med.	gain
	1455	100%	7.2	8.3 m	88.1%	5.76	5.0 m	39.5%
					MIXED SOLUTIONS
					av. %	nb. svs.	error med.	gain
					100%	5.81	5.4 m	35.1%
	Table 3b. Results in Paris XIIth district.
		ALL SVS SOLUTIONS		LOS ONLY SOLUTIONS
	nb of ep.	av. %	nb. svs.	error med.	av. %	nb. svs.	error med.	gain
	11635	100%	7.3	22.4 m	68.6%	5.1	6.1 m	72.6%
					MIXED SOLUTIONS
					av. %	nb. svs.	error med.	gain
					100%	5.3	8.5 m	61.9%

Table 3c .

 3c Results in Paris Grands Boulevards.

		ALL SVS SOLUTIONS		LOS ONLY SOLUTIONS
	nb of ep.	av. %	nb. svs.	error med.	av. %	nb. svs.	error med.	gain
	57938	99.7%	7.3	32.9 m	82%	4.84	8.8 m	73.3%
					MIXED SOLUTIONS
					av. %	nb. svs.	error med.	gain
					99.7%	4.88	9.9 m	70.0%
	Table 3d. Results in Toulouse.
		ALL SVS SOLUTIONS		LOS ONLY SOLUTIONS
	nb of ep.	av. %	nb. svs.	error med.	av. %	nb. svs.	error med.	gain
	5 845	100%	7.6	23.7 m	69.5%	5.5	14.5 m	38.7%
					MIXED SOLUTIONS
					av. %	nb. svs.	error med.	gain
					100%	5.7	16.0 m	32.6%

Peyret, F.,Bétaille, D., & Mougel, F. (2011). Non-Line-Of-Sight signal detection using an on-board 3D model of buildings. In Proceedings of the 11 th International Conference on Telecommunications for Intelligent Transport Systems, Saint Petersburg.

Acknowledgements

This research has been funded by the French Ministry of Transportation, in a project named Inturb.


David Betaille
email: david.betaille@ifsttar.fr

Stéphan Miquel

Frédéric Godan

François Peyret

David Bétaille

Miquel Stéphan

3D-city-model-aided GNSS accurate positioning with integrity provision using simplified geometry of buildings

published or not. The documents may come

INTRODUCTION

GNSS positioning in the urban environment remains challenging, because of the occurrence of many satellite signal reflection and diffraction, also called multipath, that, in the best case, combine with the direct signal, but -in the worst case when the direct signal is obscured -make signal tracking drift unboundedly.

Recent research investigations carried out in the GEOLOC laboratory of the Ifsttar (the French institute of science and Technology for transport, development and network) with the SCM (Société de Calcul Mathématique) have shown that a simplified 3D modelling of buildings at both sides of streets, named "urban trench" for that reason, can benefit in the process of satellite visibility check and GNSS positioning.

These urban trenches can be computed from 3D-city-model using road and buildings layers. Initially, the rover is assumed to occupy the arc segment that represents the street. That way, only left and right distance and height attributes depict any urban trench section, which has the advantage of being easily compliant with the existing formats of navigable maps.

Using the satellite positions in azimuth and elevation, our algorithm determinates whether their signal is in Line-Of-Sight or Not (NLOS), with respect to the modelled facades all around. In case of NLOS, a correction of the pseudorange measurement is made.

The geometry of this model being simplified, and the initial position approximated, the first deterministic approach has been modified: a probabilistic approach is proposed. From this second approach, an urban trench protection level can be computed (UTPL), which provides an integrity indicator adapted to the urban environment. This article is divided into 2 main parts: the first part gives an overview of the deterministic approach, whilst the second part concerns the probabilistic approach. Afterward experimental results are presented, with improvement not only in terms of accuracy, but also in terms of accuracy.

DETERMINISTIC APPROACH

First, the main cause of degradation of GNSS signals in urban areas is due to the morphology of the environment and in particular the geometry of the buildings. These not only cause multipath (i.e. interference between direct and reflected signals) which deviates the tracking loops and thus cause positioning errors, but also hide some satellites whose signal is no longer received. The signals received from satellites that are not in direct line of sight but undergoing one (or several) reflection (s) before being received cause the biggest measurement errors. They are called: NLOS (non-line-ofsight).

There are different solutions investigated to reduce the effects of NLOS multipath: • depending on the reception signal-to-noise ratio: actually, a reflection attenuates the signal. This method gives interesting results in terms of detection and exclusion; • filtering measurements based on a predictable dynamics of the receiver. This method assumes velocity, acceleration, turn rate or requires additional sensors: it is also valuable to perform NLOS detection and exclusion; • using a 3D city model, and determining a trust area where the sky visibility is good [START_REF] Bradbury | Code multipath modelling in the urban environment using large virtual reality city models: determining the local environment[END_REF]. The problem is that this visibility area is obviously dependent on the position (unknown) of the mobile. Some works propose to use a fisheye camera pointing to the zenith [START_REF] Marais | Accurate Localisation Based on GNSS and Propagation Knowledge for Safe Applications in Guided Transport[END_REF]. Without this, it is necessary to make one (or more) assumption(s) on an initial position and then refine this position. The main contributions are: [START_REF] Groves | Height Aiding, C/N0 Weighting and Consistency Checking for GNSS NLOS and Multipath Mitigation in Urban Areas[END_REF], [START_REF] Obst | Multipath Detection with 3D Digital Maps for Robust Multi-Constellation GNSS/INS Vehicle Localization in Urban Areas[END_REF], [START_REF] Miura | GPS Multipath Detection and Rectification using 3D Maps[END_REF], and [START_REF] Bétaille | Applying Standard Digital Map Data in Map-aided, Lane-level GNSS Location[END_REF] to which the present research investigations consist in a continuation.

The geometry of the buildings we propose is simplified, to such an extent that, between nodes (i.e. intersections), we consider that the width of a street is constant as well as the height of left and right facades. Another approximation we still make is to project to predicted position of the mobile onto the local road arc segment. So, 4 parameters only depict the geometry we set per arc segment: left and right distances between this arc segment and the footprint of both facades (W1 and W2), and the height of the building on both sides (H1 and H2).

Such modelling is easy to extract from usual data base like IGN BD Topo ® in France.

The format, i.e. the fact that the urban trench parameters are attached to the road arc segments, makes it really ease-ofuse in any real-time embedded map-matching process for car navigation. The information to store is more than 2 orders of magnitude lower than that of a typical detailed 3D model one sets up in a ray-tracing approach of this problem.

An example of a street view in Paris, Grands Boulevards, and the corresponding BD Topo ® extract is given in Fig. 1.

The diagram of visibility, also called mask of visibility, has this rugby ball shape due to the infinite length assumption of the urban trench where one travels. Assuming specular reflection, the LOS/NLOS boundary obeys to (1):

β sin arctan 1 1 1 / W H el nlos los = (1)
where β measures the angle difference between the satellite azimuth and the street direction. A similar equation gives the boundary between NLOS with 1 reflection and NLOS with 2 reflections, and it applies in case high enough buildings are facing each other.

A large data set has been collected in Nantes, Paris and Toulouse in 2012, aggregating 10 hours of observation in the usual traffic, with a GPS receiver typically used in car navigation systems: automotive and high-sensitivity GPS Ublox LEA6-T, 5 Hz, mounted on the roof of the vehicle. The ground truth was given in post-processing by a Novatel kinematic receiver coupled with an IXSea Inertial Measurement Unit [START_REF] Ortiz | From Lab to Road Test[END_REF]. We have established that the urban trench modelling, despite its approximation of both the geometry of buildings and the transversal position in streets, classifies properly LOS and NLOS.

Time series, e.g., have been obtained in Paris, Grands Boulevards, and a histogram of pseudo-range errors is given in Fig. 2a. The total number of epochs aggregated is 102335 (approximately 5½ hours at 5 Hz). 7 satellites per epoch are visible in average; note that the highest is used for the receiver clock offset correction, which makes a total population of 614723 errors (5½ hours at 5 Hz for (7-1) satellites).

One notices a positive tail in the distribution of the pseudo-range errors, but a rather normal distribution of the Doppler errors (Fig. 2b). On Fig. 2a, the proportion of the urban trench model-based NLOS identified satellites have been blued, those responsible of this long positive tail in the error distribution. Assuming specular reflections in the environment modelled with urban trenches, the pseudo-range errors can be estimated and the additional distance corrected (Fig. 3). This supposes that an approximate position of the receiver is first made, and, as concerns the present approach and experimental results, projected onto the nearest road arc segment in a simple map-matching process. The additional distance obeys to (2):

el W d nlos cos sin 2 1 1 β = (2)
where el designs the satellite elevation. In the eventuality of 2 consecutive reflections, a similar equation applies.

Additional path

β = π/2 W1 H1 el

Satellite with

Fig. 3. Additional path performed in case of 1 reflection for a satellite azimuth perpendicular to the street. Fig. 4, from [START_REF] Bétaille | Applying Standard Digital Map Data in Map-aided, Lane-level GNSS Location[END_REF], aggregates all epochs and all test sites (i.e. 10 hours of data). The cumulative 3D error distribution is displayed, for the standard estimator (least-mean squares), for the estimator using LOS satellites only, and for the estimator mixing LOS and NLOS satellites, applying the correction given by the modelled urban trenches.

The LOS only method availability is around 80%, while the standard and NLOS corrected methods reach almost 100%. The median error in 3D has been reduced from 21.7 m down to 9.4 m, i.e. 56% improvement globally. 4. Cumulative distribution function of the absolute error in 3D, for standard and urban trench solutions, for all epochs and all test sites in Nantes, Paris and Toulouse (10 hours of data); note that the asymptote is lower when using LOS only, because solutions are often not computable, which can also be interpreted as an infinite error.

PROBABILISTIC APPROACH

Using a model with simplified geometry (Urban Trench), and approximating the initial position, [START_REF] Bétaille | Applying Standard Digital Map Data in Map-aided, Lane-level GNSS Location[END_REF] presented a first deterministic approach, that has been modified into a probabilistic approach [START_REF] Bétaille | Improving accuracy and integrity with a probabilistic Urban Trench modeling[END_REF].

In this approach, are proposed empirical laws modelling the probabilities that signals come LOS or NLOS (with 1 or 2 reflections) depending on the geometry. These laws (Fig. 5) depend on deterministic considerations, but they are probabilistic to take into account the random aspects due to difference between the real geometry of the streets and the modelled trenches (gaps between the buildings, differences of heights, etc.). Fig. 5. Model of probabilities that a satellite, depending on its elevation relatively to the thresholds el01 (cf. equation 1) and el12, be LOS (P0), NLOS with 1 reflection (P1), NLOS with 2 reflections (P2).

Every combination of the probabilities is considered in the positioning estimation, which averages 3 n solutions, each one being weighted by its own P0*P1*P2 product of probabilities. From this second approach, an urban trench protection level can be computed, which provides an integrity indicator adapted to urban environments. This indicator, computed in 3D, is obtained by multiplying the semi-major axis of the ellipsoid that encompasses the set of 3 n solutions by the usual K factor (6.18) read in the chi² statistic table. Fig. 6 shows that the proposed 3D Urban Trench Protection Level (UTPL) outperforms the standard protection level, which does not consider the local sources of multipath. A total duration of approximately 10 hours of tests have been carried out and processed. Misleading Information (MI) occurred half-time in standard, i.e. without urban modelling, whereas the 3D UTPL occurrence of MI is less than one thousand over the 161 724 epochs where the computation was applicable (epochs with only 4 satellites were not considered).

CONCLUSION AND PERSPECTIVES

This communication gives results in urban environments not only in terms of accuracy improvement, but also in terms of accuracy. Full scale experiment, in Nantes, Paris and Toulouse, for a total duration of 10 hours, have been carried out, which makes a data set large enough to claim for an integrity risk of the order of magnitude of 10 -3 with a 10% confidence. The 3D modelling is simple and compatible with today's embedded digital maps. Additional tests and investigations to optimize the Urban Trench probabilistic method are ongoing.

Fig. 1 .

 1 Fig. 1. A street view in Paris, with road and building layers of BD Topo ® locally, and the parameters of our model: next polar subplot figures out the diagram of visibility resulting from applying the urban trench model.

  Fig. 2. a: LOS/NLOS pseudo-range errors and b: Doppler errors.

Fig.

  Fig.[START_REF] Obst | Multipath Detection with 3D Digital Maps for Robust Multi-Constellation GNSS/INS Vehicle Localization in Urban Areas[END_REF]. Cumulative distribution function of the absolute error in 3D, for standard and urban trench solutions, for all epochs and all test sites in Nantes, Paris and Toulouse (10 hours of data); note that the asymptote is lower when using LOS only, because solutions are often not computable, which can also be interpreted as an infinite error.

Fig. 6 .

 6 Fig. 6. Stanford diagrams with no modelling of multipath and when the Urban Trench model of probabilities is applied.

ACKNOWLEGMENTS

The authors would like to thank the Ministry responsible for transport in France, DGITM (general directorate for infrastructure, transport and the sea), which funded this research work in the frame of the project named Inturb.


Z Li

F Giannini

B Falcidieno

J-P Pernot

P Vé

Towards a new approach for the description of shapes from multimodal data

Keywords: geometric modeling, CAD, multimodal data, virtual reality, semantics, shape description

The construction of a Virtual Environments (VE) requires a long iterative modeling and modification process. Depending on the final purposes, many actors can be involved both in the early conception and in the detailed specification of what has to be included and how it has to be organized. These actors may have different knowledge and expertise. It is therefore important to define tools easy usable even by nonprofessionals in order to facilitate the VE specification and setup. Such tools should allow the incomplete specification of details and the reuse of existing assets and data, either 2D images or 3D models. In this perspective, the work presented in this paper proposes a new shape description model for the management of objects and assemblies, resulting from the combination of multimodal data, together with their intrinsic properties. Based on such a model high level methods and tools directly working on components (either 2D or 3D) can be developed. Thus making easier the solution specification by the application domain experts, which can thus better integrated within the VE design process. This new shape description model is thought to be used as an intermediary model shared between the various actors in the generation process of VEs to keep the link and digital chain between them. The concepts of this model are proposed and illustrated through a first implementation.

I. INTRODUCTION

Nowadays, VEs are more and more used in different application domains. For example, in architecture area [START_REF] Waly | A virtual construction environment for preconstruction planning[END_REF], in education domain [START_REF] Antonis | Educational virtual environments: A tenyear review of empirical research (1999-2009[END_REF], in product conception [START_REF] Kan | An internet virtual reality collaborative environment for effective product design[END_REF], etc. In general, the global VE construction process remains the same (Fig. 1). It may involve many actors from different disciplines and expertise in all the definition phase of what has to be included and how it has to be organized. From functional specifications defined by the end user, a certain number of 3D models are generated (or imported from some database) and enriched by various properties (texture, gravity, reflection, etc.) and then they are inserted in the VE with behaviors and functions. This last step requires the programming of each object and of the whole VE. After this step, the end users test the application, and changes are generally required most of the time because of misunderstanding or not sufficiently detailed conceptual specification. Despite the big improvements in the implementation of detailed modelling systems, the modification process of a VE is still very long and tedious. For example, if the form of an object in the scene does not satisfy the end user, changes are applied to the 3D model. As a consequence, the textures need to be modified, the physical properties have to be recalculated (collision, gravity, light reflection, etc.), the animations may need to be redefined and the related scenarios rescheduled. Under this context, the description of 3D objects in the scene becomes the key problem in the construction of a VE.

Currently, there are no suitable tools to support the conceptual design phase of VEs efficiently. In this phase, the actors should have the possibility to make hypotheses such as: on which assets to consider and how to arrange them possibly taking advantages of already existing resources, etc. They should be able to communicate their ideas easily by mocking up rough and incomplete solutions without requiring deep modelling expertise. It is then crucial to define systems that take into consideration basic cognitive aspects regarding the selection and combination of shapes while guaranteeing model re-editing and processing. In this perspective, it is necessary to develop intuitive user interfaces but also new modelling techniques dealing with multidimensional data (e.g. images and 3D models). The work presented in this paper proposes a new shape description model for the management of objects and assemblies, resulting from the combination of multimodal data, together with their intrinsic properties. Such a model is conceived according to two main purposes. The second aim is to provide high level methods and tools directly working on components (either 2D or 3D) rather than on the low level geometric models. Such a modeling simplification improves the brainstorming activity and lets the application domain expert integrate within the VE design process, which will simplify the later on modification process. This new shape description model is conceived to be used as an intermediary model shared between the various actors in the generation process of VEs to keep the link and digital chain within them. Here the underlying concepts of this model are proposed and illustrated through a first implementation.

The paper is organized as follows. Section II is structured in two parts: Section II.A describes the generation process of 3D objects for VEs and motivates the need of a new shape description model from multimodal data; Section II.B lists the necessary characteristics the new shape description model has to satisfy. Then, Section III presents a first idea of this new shape description model according to a multi-layer information approach for shape description. Section 4 shows the initial implementation results. Finally, Section 5 concludes the work presented in this paper and leaves some perspectives for future works.

II. 3D OBJECT GENERATION PROCESS FOR VE

This section describes the current process for generation of VEs together with a possible alternative for a better integration of the application experts in the definition loop. This is obtained through the development of tools allowing an easier and more intuitive idea generation for the wished assets.

A. The digital chain for creation of VEs

Independently on the application contexts considered, i.e. the purposes of the VE created, the generation process is generally following the steps indicated in Fig. 1. The 3D object generation step involves four main actors (see Fig. 2). Each of them has different expertise and perspective on the object. The whole process is mainly a sequential chain with several exchanges among the actors, which have different objectives:

-Expert of the application domain. This is the person demanding a VE to realize some virtual tasks. He/she knows very well the application domain but he/she may not have any knowledge in programming or computer graphics. The tools that he/she can use to express his/her ideas are composed of key words, handmade sketches, pictures or existing 3D models found in certain database. He/She will explain his/her idea of an object or of the whole VE using these multimodal data while indicating the rules of the application domain. Unfortunately, with current tools these multimodal data cannot be used directly into the digital chain.

-Expert of CAD usage: They are product designers who create CAD models from the description of previous actor respecting the technical criteria of the object model purposes. For instance, if the object model represents a product to be manufactured, then such a model will describe all the details of the product needed to its manufacturing (size, surface roughness, tolerance, adjustment, etc.). For realizing virtual tasks in a VE, these models are too heavy. Some information might be not necessary for the VE (the criteria of manufacturing, details of inner parts, etc.) and the resolution of the 3D model might be too high and not adapted to the capacity of the rendering engine for a VE.

-Expert of VE Design: They are the people who simplify the CAD models and associate them with rendering properties (material, texture, light reflection, etc.) to make sure that they will be well exposed in a VE. This step is manual, thus breaking the digital chain.

-Expert of VE Development: People in this step add functions and behaviors to each 3D model. First, they need to enrich the models generated by Expert of VE Design with functional properties such as gravity, skin textures, skeleton, animation, etc. Then they add interactions (between objects, between objects and users) and virtual tasks to the object to realize a useful VE finally.

As shown in Fig. 2, with the idea given by the expert of the application domain, the digital chain starts from the CAD designer and then pass to the VE designer and the VE developer. In each phase, there is a specific digital model (Industry 3D model, Enriched 3D Model and Interactive 3D model) which follows strictly the aspects (right part in fig. 2) defined by their own domains. In the end, the end user will test the VE and provide feedbacks. If he/she identifies that some modifications need to be done on the objects' shape, all the steps, both digital and manual, of the preparation sequence are re-done. The generation process is linear with different feedbacks.

To reduce this modification cycle and facilitate communication between the actors we foreseen a new 3D object generation process for VEs that can limit the break of the digital flow during the process (see Fig. 3). Compared with the classical process presented in Fig. 2, this process is no longer linear, and feedbacks outside this process are limited. We identify two important key characteristics that permit this process: -Input of this process is multimodal data (key words, 2D images, sketches, 3D models, etc.). They are easy to be acquired by anyone. Thus, no knowledge is required on specific systems, such as CAD or programming.

-A new shape description model able to support such multimodal data composition, shared by the various actors as a common source of information and data for the process. Thus, this generic model integrates the views of the four actors making easier their collaboration and brainstorming activities than in the classical process.

In conclusion, the new process presented takes multimodal data as input and describes an object with a generic description model that becomes the reference model for all the various actors working on the VE creation. The process provides more freedom and support the end user expressing their own desires. The specification of the generic shape description model and of the functionalities of its creation and modifications become the central problem to solve.

B. Requirements for the multimodal data representation model

As discussed in Section II.A, a key element to define the new 3D object generation process is the generic shape description model for handling multimodal data. Such a model should present some essential characteristics:

-Independency to the application domain. That means this model can be a reference for any application and actor.

-Capability to manipulate multimodal data. This model should be able to combine, modify and handle all different kinds of multimodal data, namely 2D images, texts and 3D models, while keeping the link between the original data. It should take into consideration the fact that each of them has its own data format, data structure, characteristics and associated semantics.

-Easy to generate by anyone. As discussed in previous section, the one who create this model could be someone who has no any CAD or programming skill. This means that the model should be suitable for developing some high level approaches and tools for the object creation.

To conclude, in this section we showed the classical process for generating a 3D object in a VE and proposed a new process. This new process is based on a generic shape description model, which is generated from multimodal data by anyone and can integrate with the four actors present in the classical process.

III. TOWARDS A GENERIC SHAPE DESCRIPTION MODEL (GSDM)

The first question we need to answer is what the shape of an object is exactly. Which information have to be stored in order to manipulate them easily and meaningfully? In the project called Aim@Shape [START_REF]Aim@Shape[END_REF], a new paradigm for understanding and representing shapes has been proposed. Aim@Shape define a shape as any individual object having a visual appearance, which exists in some (two-, three-or higher-dimensional) space. Such a definition includes a great variety of elements, such as pictures, sketches, images, 3D objects, videos, 4D animations, etc. The defined paradigm explains shapes according to three different levels of information: Geometry, Structure and Semantics (GSS). The three levels can be understood as follows:

Geometry level: corresponds to the spatial extent of the object.

Structure level: an abstraction according to the main characteristics of the object, i.e. features and part-whole decomposition

Semantics level: information associated to the object or a part of the object that specifies the meaning or purpose related to the context of use.

This paradigm shows us a new way to understand a shape. It could also set criteria to compare different shape representations/descriptors as shown in the table 1.

In literature, we have different kinds of shape descriptors, some of them are applicable at only one specific level, and others are dealing with two or more. Some of them are focusing on the geometric level of shapes only (mesh, voxels, wireframe, point cloud, etc.), some are strongly linked to special application domain/semantics (Circularity descriptor, rectangularity descriptor, etc.) and some shows the structure of decomposition or partition of the shape (Reeb graph, Skeleton, segmentations, etc.). The existing descriptors and description today are all related to some specified dimension of the data, so they might be not general enough to cover all the three aspects of Geometry, Structure and Semantic for multimodal models.

Therefore, here we propose a new Generic Shape Description Model (GSDM). This model describes shapes according to all the three aspects in the modelling paradigm introduced by Aim@Shape. We also assume that the input multimodal data for the new GSDM approach contain the geometry already enriched with structural information such as part segmentation [START_REF] Paul | Image segmentation based on the integration of colour-texture descriptors-A review[END_REF], medial axis [START_REF] Aichholzer | Medial axis computation for planar free-form shapes[END_REF] and skeletons [START_REF] Biasotti | Skeletal structures[END_REF]. We make this hypothesis because many shape analysis approaches [START_REF] Zhang | Review of shape representation and description techniques[END_REF] already exist today for each type of multimodal data. We consider such a structural decomposition since it allows a meaningful subpart selection for both the composition and positioning thus reducing the cognitive effort from the end user side.

The GSDM can be seen as a hypergraph, whose nodes correspond to Components and hyperarcs, i.e. arcs connecting nodes, to Relations among them. The scene graph can be built using the same GSDM structure to associate specific information and actions of the VE under construction. A Component is the most basic element in the GSDM and is itself organized according the GSS approach. Different input data will supply different types of "Component", as shown in table 1.

Relations are used to link together Components.

More than one Relation can link the same Components. Different kinds of Relations are considered specifying the operation to perform. Depending on the type of operation, it can also include Constraints, which indicate the basic elements for the operation. Relation is a complex concept in our GSDM. It crosses all the three levels of the GSS model, see Table 2.

The concept of constraint we are discussing here is not the same as the traditional CAD assembling. The traditional assembling constraints work only on the assembly structure level. The constraints discussed here could work on all the three levels of semantic, structure and geometry and are used for positioning the multimodal elements constituting the final object and guiding the planned operation. We considered four types of Operation: Shaping, Merging, Union and Grouping. Shaping modifies the geometric, e.g. morphing, bending, subtraction, and possibly the structural layers of information. Merging indicates the traditional union operation in CAD. Thus, it works at all the three GSS layers of the component. Union works on the semantic and the high structure level. It corresponds to put together elements without generating the geometry of the result. Finally Group works only on the semantic level. It is used to logically join components, such as, "the legs of a table", "the arms of a human body". These various group relations can be applied depending on different usage contexts.

If we look on the whole scene, then only the Union and Group Relation can be applied to build the structure of the scene, telling us how different objects are positioning the one to the other by adding constrains.

Fig. 1 .

 1 Fig. 1. Global VE construction process.

Fig. 2 .

 2 Fig. 2. Classical 3D object generation process.

Fig. 3 .

 3 Fig. 3. Proposed new 3D object generation process.

Table 1

 1 Examples of Components according to the type of data

	Multimodal data	Component
	text	sentences, key words
	2D Images	Segmented part (e.g. pixels group with a label)
		With enriched information (e.g. media axis,
		skeleton, etc.)
	3D Meshes	Segmented part (e.g. triangle group with a label)
		With enriched information (e.g. media axis,
		skeleton, etc.)

ACKNOWLEDGMENT The work has been partially supported by the VISIONAIR project funded by the European Commission under grant agreement 262044. It is part of the Co-DIVE project funded by Arts et Mé tiers ParisTech.

Acting on information level

Object Scene

Table 2 The information layer affected by the various types of relations

To make easy the user interaction and relation specification, we take advantage of key entities of the components at structural and/or geometric level, e.g. the symmetry axis or the skeleton elements and points or pixels on them. In general, there are two types of key entity, geometric entity and parametric entity. Geometric entity lays on the local reference frame so it is changed during the transformation of the local reference frame, i.e. it will not follow the transformation or deformation of the Component. Parametric entity is linked to the Component/Components with parameters, it follows the transformation or deformation of the reference frame and the Component/Components depending on the parameters. Key entity is created automatically by importing a new input data or by user during the design process.

In Fig. 4 an example of GSDM is depicted: green nodes represents Component, red array means the Union/Merging Relation and blue circle shows a Group Relation. The details of this graph are hidden to the user.

IV. FIRST IMPLEMENTATION

To verify the feasibility of our approach, we are implementing a prototype using Unity 3D environment (Fig. 5). In reality, the GSDM model is independent of any system. We selected Unity 3D because it is a powerful engine for the creation of VEs. This implementation works in four steps to realize the generation of the GSDM: There is no a fixed order of these four steps, user can do them separately. And in the end user can display the graph of GSDM in the 3D scene (Figure 6-5). Once the components have been instantiated and the relations specified, the associated optimization problem is solved and the solution is displayed. In the proposed approach, we try to minimize the displacements and deformations between the initial configuration and the one which satisfies the relations.

V. CONCLUSIONS AND PERSPECTIVES

In this paper we showed a new 3D object generation process for VEs by proposing the concept of Generic Shape Description Model (GSDM). This model could be used to describe the shape of one object or the whole scene. For now, we are working on the details of the data structure of this model (e.g. different kinds of constraints) and on completing the formalization of the model. For the work in the future, we plan to go on the implementation of the prototype and to solve problems related to the modification of the GSDM: for example, the constraint satisfaction problem, the combination of shape skeleton, etc. Secondly, as the work presented in this paper is a part of the (Conceptual Design in Virtual Environment), we also plan to integrate the modeler with the touch screen user interface under development by ENSAM Cluny partners who are working on the manipulation of objects in the scene and integration mode with VE. As long term future work we plan to integrate, when possible, or to develop algorithms that can transform our GSDM into different representations of the object like a 3D mesh or a rendered 2D picture.


Yukiko Yamauchi
email: yamauchi@inf.kyushu-u.ac.jp

Taichi Uehara

Shuji Kijima

Masafumi Yamashita

Plane Formation by Synchronous Mobile Robots in the Three Dimensional Euclidean Space

Keywords: Mobile robots in the three dimensional space, plane formation, rotation group, symmetry breaking

Creating a swarm of mobile computing entities frequently called robots, agents or sensor nodes, with self-organization ability is a contemporary challenge in distributed computing. Motivated by this, this paper investigates the plane formation problem that requires a swarm of robots moving in the three dimensional Euclidean space to reside in a common plane. The robots are fully synchronous and endowed with visual perception. But they have neither identifiers, access to the global coordinate system, any means of explicit communication with each other, nor memory of past. Though there are plenty of results on the agreement problem for robots in the two dimensional plane, for example, the point formation problem, the pattern formation problem, and so on, this is the first result for robots in the three dimensional space. This paper presents a necessary and sufficient condition to solve the plane formation problem. An implication of the result is somewhat counter-intuitive: The robots cannot form a plane from most of the semi-regular polyhedra, while they can from every regular polyhedron (except a regular icosahedron), which consists of the same regular polygon faces and the robots on its vertices are "more" symmetric than semi-regular polyhedra.

Introduction

Self-organization in a swarm of mobile computing entities frequently called robots, agents or sensor nodes, has gained much attention as sensing and controlling devices are developed and become cheaper. It is expected that mobile robot systems perform patrolling, sensing, and exploring in a harsh environment such as disaster area, deep sea, and space. For robots moving in the three dimensional Euclidean space (3D-space), we investigate the plane formation problem, which is a fundamental self-organization problem that requires robots to occupy distinct positions on a common plane from initial positions, mainly motivated by an obvious observation: Robots on a plane would be easier to control than those deployed in 3D-space.

In this paper, a mobile robot system consists of autonomous robots that move in 3D-space and cooperate with each other to accomplish their tasks without any central control. A robot is represented by a point in 3D-space and repeats executing the "Look-Compute-Move" cycle, during which, it observes, in Look phase, the positions of all robots by taking a snapshot, which we call a local observation in this paper, computes the next position based only on the snapshot just taken and using a given deterministic algorithm in Compute phase, and moves to the next position in Move phase. This definition of Look-Compute-Move cycle implies that it has full vision, i.e., the vision is unrestricted, the algorithm is oblivious, i.e., it does not depend on a snapshot of the past, and the move is an atomic action, i.e., each robot does not stop en route to the next position and we do not care which route it takes. A robot has no access to the global x-y-z coordinate system, and all actions are done in terms of its local x-y-z coordinate system. We assume that it has chirality, which means that it has the sense of clockwise and counter-clockwise directions. In particular, we assume that local coordinate systems are right-handed.

The robots can see each other, but do not have direct communication capabilities; communication among robots must take place solely by moving and observing robots' positions, tolerating possible inconsistency among the local coordinate systems. The robots are anonymous; they have no unique identifiers and are indistinguishable by their looks, and execute the same algorithm. Finally, they are fully-synchronous (FSYNC); they all start the i-th Look-Compute-Move cycle simultaneously, and synchronously execute each of its Look, Compute and Move phases.

The purpose of this paper is to show a necessary and sufficient condition for the solvability of the plane formation problem. The line formation problem in the two dimensional Euclidean space (2D-space or plane) is the counter-part of the plane formation problem in 3D-space, and is unsolvable from an initial configuration P (i.e., positions of the robots), if P is a regular polygon, intuitively because anonymous robots forming a regular polygon cannot break symmetry among themselves, and lines they propose are also symmetric, so that they cannot agree on one line from them [START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF]. Hence symmetry breaking among robots would play a crucial role in our study on the plane formation in 3D-space, too.

The pattern formation problem requires robots to form a target pattern from an initial configuration, and our plane formation problem is a subproblem of the pattern formation problem in 3D-space. To investigate the pattern formation problem in 2D-space, which contains the line formation problem as a subproblem, Suzuki and Yamashita [START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF] used the concept of symmetricity to measure the degree of symmetry of a configuration consisting of the robots' positions on the plane. 1Let P be a configuration of robots on a plane, where we regard the configuration as a set of points. Then its symmetricity ρ(P ) is the order of the cyclic group of P , where its rotation center o is the center of the smallest enclosing circle of P , if o ∈ P . That is, its rotational symmetry is ρ(P ) and ρ(P ) is the number of angles such that rotating P by θ (θ ∈ [0, 2π)) around o produces P itself, which intuitively means that the ρ(P ) robots forming a regular ρ(P )-gon in P may not be able to break symmetry among themselves. However, when o ∈ P , the symmetricity ρ(P ) is defined to be 1, independently of its rotational symmetry. This is the crucial difference between the rotational symmetry and the symmetricity, and reflects the fact that the robot at o can break the symmetry in P by leaving o. Then the following result has been obtained [START_REF] Fujinaga | Pattern formation by oblivious asynchronous mobile robots[END_REF][START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF][START_REF] Yamashita | Characterizing geometric patterns formable by oblivious anonymous mobile robots[END_REF]: A target pattern F is formable from an initial configuration P , if and only if ρ(P ) divides ρ(F ).

In order to investigate the plane formation problem in 3D-space, we measure the symmetry of a configuration in 3D-space with the rotation group of the configuration. In 3D-space, rotation groups with finite order are classified into the cyclic groups, the dihedral groups, the tetrahedral group, the octahedral group, and the icosahedral group. The cyclic groups and the dihedral groups are said to be two-dimensional (2D), in the sense that the plane formation problem is obviously solvable, since there is a single rotation axis or a single principal rotation axis, and all robots can agree on a plane perpendicular to the single (or principal) axis and containing the center of the smallest enclosing ball of themselves. Then FSYNC robots can easily solve the plane formation problem by moving onto the agreed plane.

The other three rotation groups are defined by the rotations of corresponding regular polyhedra, and these rotation groups are called polyhedral groups. A regular polyhedron consists of regular polygon faces and has vertex-transitivity, that is, there are rotations that replace any two vertices with keeping the polyhedron unchanged as a whole. For example, we can rotate a cube around any axis containing two opposite vertices, any axis containing the centers of opposite faces, and any axis containing the midpoints of opposite edges. For each regular polyhedron, rotations applicable to the polyhedron form a group, and, in this way, the three rotation groups, i.e., the tetrahedral group, the octahedral group and the icosahedral group, are defined. We call them three-dimensional (3D) rotation groups.

When a configuration has a 3D rotation group, the robots are not on any plane. In addition, the vertex-transitivity among the robots may allow corresponding robots to have an identical local observation, and the robots may result in an infinite execution, where they keep symmetric movements and never agree on a plane. A vertex-transitive set of points is in general obtained by specifying a seed point and a set of symmetry operations, which consists of rotations around an axis, reflections for a mirror plane (bilateral symmetry), reflections for a point (central inversion), and rotation-reflections [START_REF] Cromwell | Polyhedra[END_REF]. However, it is sufficient to consider vertex-transitive set of points constructed from transformations that preserve the center of the smallest enclosing ball of robots, and keep Euclidean distance and handedness, in other words, direct congruent transformations, since otherwise, the robots have chirality and can break the symmetry. Such symme-try operations consist of rotations around some axes. (See e.g., [START_REF] Coxeter | Regular polytopes[END_REF][START_REF] Cromwell | Polyhedra[END_REF] for more detail.)

Let P and γ(P ) be a set of points in 3D-space and its rotation group, respectively. Then the points (i.e., the robots) are partitioned into vertex-transitive subsets by the group action of γ(P ). Hence, for each subset, the robots in it may have the same local observation. We call this decomposition γ(P )-decomposition of P . The goal of this paper is to show the following theorem: Theorem 1. Let P and {P 1 , P 2 , . . . , P m } be an initial configuration and the γ(P )-decomposition of P , respectively. Then oblivious FSYNC robots can form a plane from P if and only if (i) γ(P ) is a 2D rotation group, or (ii) γ(P ) is a 3D rotation group and there exists a subset P i such that |P i | ∈ {12, 24, 60}.

Theorem 1 implies the following, which is somewhat counter-intuitive: The plane formation problem is solvable, even if P is a regular polyhedron (except a regular icosahedron), i.e., even if the robots initially occupy the vertices of such regular polyhedron, while it is unsolvable for most of the semi-regular polyhedra.

We can rephrase this theorem as follows: Oblivious FSYNC robots cannot form a plane from P if and only if γ(P ) is a 3D rotation group and |P i | ∈ {12, 24, 60} for each P i . The impossibility proof is by a construction based on the decomposition of the robots. Obviously 12, 24, and 60 are the orders of 3D rotation groups, and when the cardinality of a vertex-transitive set of points is in {12, 24, 60}, the corresponding rotation group enables "symmetric" local coordinate systems that imposes an infinite execution, where the robots' positions keep the axes of the rotation group. We will show this fact by constructing the worst-case local coordinate systems.

For the possibility proof, we present a plane formation algorithm that breaks regular polyhedra for solvable cases. In the 2D-space, the symmetricity of a configuration is defined to be 1 when a robot is on the rotation axis of the cyclic group, because the robot on the center can break the symmetry by leaving the center. In the same way, a rotation axis of a 3D rotation group disappears when a robot on it leaves the axis. Fortunately, there is always a robot on a rotation axis, if the cardinality of a vertex-transitive robots is not in {12, 24, 60} and we can use it to reduce the number of rotation axes. Although there are multiple rotation axes in a 3D rotation group, the proposed algorithm transforms a configuration whose rotation group is a 3D rotation group into another configuration whose rotation group is a 2D rotation group, by reducing the number of rotation axes.

Related works.

We roughly review some of works on robots in 2D-space, since there is few research on robots in 3D-space, although an autonomous mobile robot system in 2D-space has been extensively investigated (see e.g., [3-7, 9, 11]). Besides fully synchronous (FSYNC) robots, there are two other types of robots, semi-synchronous (SSYNC) and asynchronous (ASYNC) robots. The robots are SSYNC if some robots do not start the i-th Look-Compute-Move cycle for some i, but all of those who have started the cycle synchronously execute their Look, Compute and Move phases [START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF], and they are ASYNC if no assumptions are made on the execution of Look-Compute-Move cycles [START_REF] Flocchini | Arbitrary pattern formation by asynchronous, anonymous, oblivious robots[END_REF]. The book by Flocchini et al. [START_REF] Flocchini | Distributed computing by oblivious mobile robots[END_REF] contains almost all results on ASYNC robots up to year 2012.

As for the pattern formation problem in 2D-space, which includes the line formation problem as a subproblem, the solvable cases are determined for each of the FSYNC, SSYNC and ASYNC models [START_REF] Fujinaga | Pattern formation by oblivious asynchronous mobile robots[END_REF][START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF][START_REF] Yamashita | Characterizing geometric patterns formable by oblivious anonymous mobile robots[END_REF], which are summarized as follows: (1) For non-oblivious FSYNC robots, a pattern F is formable from an initial configuration P if and only if ρ(P ) divides ρ(F ). ( 2) Pattern F is formable from P by oblivious ASYNC robots if F is formable from P by non-oblivious FSYNC robots, except for F being a point of multiplicity 2.

This exceptional case is called the rendezvous problem. Indeed, it is trivial for two FSYNC robots, but is unsolvable for two SSYNC (and hence ASYNC) robots [START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF]. Therefore it is a bit surprising to observe that the point formation problem for more than two robots is solvable even for ASYNC robots. The result first appeared in [START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF] for SSYNC robots and then is extended for ASYNC robots in [START_REF] Cieliebak | Distributed computing by mobile robots: gathering[END_REF]. As a matter of fact, except the existence of the rendezvous problem, the point formation problem (for more than two robots) is the easiest problem in that it is solvable from any initial configuration P , since ρ(F ) = n when F is a point of multiplicity n, and ρ(P ) is always a divisor of n by the definition of the symmetricity, where n is the number of robots.

The other easiest case is a regular n-gon (frequently called the circle formation problem), since ρ(F ) = n. A circle is formable from any initial configuration, like the point formation problem for more than two robots. Recently the circle formation problem for n robots (n = 4) is solved without chirality [START_REF] Flocchini | Distributed computing by mobile robots: Solving the uniform circle formation problem[END_REF].

Organization. After explaining the model in Section 2, we introduce the rotation group of points in 3D-space and show some properties of vertex-transitive set of points in Section 3. In Section 4, we then prove Theorem 1. Finally, Section 5 concludes this paper by giving some concluding remarks. Because of the page limitation, we omit detailed proofs. Please see the full version [START_REF] Yamauchi | Plane formation by synchronous mobile robots in the three dimensional Euclidean space[END_REF].

Robot Model

Let R = {r 1 , r 2 , . . . , r n } be a set of n anonymous robots represented by points in 3D-space. We use the index just for description. Without loss of generality, we can assume n ≥ 4, since all robots are already on a plane when n ≤ 3. By Z 0 we denote the global x-y-z coordinate system. Let p i (t) ∈ R 3 be the position of r i at time t in Z 0 , where R is the set of real numbers. A configuration of R at time t is denoted by P (t) = {p 1 (t), p 2 (t), . . . , p n (t)}. We assume that the robots initially occupy distinct positions, i.e., p i (0) = p j (0) for all 1 ≤ i < j ≤ n. In general, P (t) can be a multiset, but it is always a set throughout this paper since the proposed algorithm avoids any multiplicity. 2 The robots have no access to Z 0 . Instead, each robot r i has a local x-y-z coordinate system Z i , where the origin is always its current location and the direction of x-y-z axes and unit distance are arbitrary. However, we assume that Z 0 and all Z i are right-handed. By Z i (p) we denote the coordinate of a point p in Z i .

We investigate fully synchronous (FSYNC) robots in this paper. They all start the t-th Look-Compute-Move cycle simultaneously, and synchronously execute each of its Look, Compute and Move phases. We specifically assume without loss of generality that the (t + 1)-th Look-Compute-Move cycle starts at time t and finishes before time t + 1. At time t, r i (and all other robots simultaneously) looks and obtains a set 3 We call Z i (P (t)) the local observation of r i at t. Next, r i computes its next position using an algorithm ψ, which is common to all robots. Formally, ψ is a total function from P 3 n to R 3 , where P 3 n = (R 3 ) n is the set of all configurations (which may contain multiplicities). Finally, r i moves to ψ(Z i (P (t))) in Z i before time t + 1. An infinite sequence of configurations E : P (0), P (1), . . . is called an execution from an initial configuration P (0). Observe that the execution E is uniquely determined, once initial configuration P (0), local coordinate systems Z i at time 0, and algorithm ψ are fixed.

Z i (P (t)) = {Z i (p 1 (t)), Z i (p 2 (t)), . . . , Z i (p n (t))}.
We say that an algorithm ψ forms a plane from an initial configuration P (0), if, regardless of the choice of initial local coordinate systems Z i of r i ∈ R, the execution P (0), P (1), . . . eventually reaches a configuration P f that satisfies the following three conditions:

(a) P f is contained in a plane, (b) |P f | = n, i.
e., all robots occupy distinct positions, and (c) Once the system reaches P f , the robots do not move anymore.

Symmetry in 3D-Space

In 3D-space, we consider the smallest enclosing ball and the convex hull of the positions of robots, i.e., robots are vertices of a convex polyhedron. We do not care for non-convex polyhedra. A uniform polyhedron is a polyhedron consisting of regular polygons and all its vertices are congruent. The family of uniform polyhedra contains the regular polyhedra (Platonic solids) and the semi-regular polyhedra (Archimedean solids). Any uniform polyhedron is vertex-transitive, i.e., for any pair of vertices of the polyhedron, there exists a symmetry operation that moves one vertex to the other with keeping the the polyhedron as a whole.

In general, symmetry operations on a polyhedron consists of rotations around an axis, reflections for a mirror plane (bilateral symmetry), reflections for a point (central inversion), and rotation-reflections [START_REF] Cromwell | Polyhedra[END_REF]. But as briefly argued in Section 1, since all local coordinate systems are right-handed, it is sufficient to consider only direct congruent transformations, and those keeping the center are rotations around some axes that contains the center. We thus concentrate on rotation groups with finite order. A rotation axis is a k-fold axis if the rotation around it is π/k, 2π/k, . . . , 2π. There are five kinds of rotation groups of finite order [START_REF] Coxeter | Regular polytopes[END_REF][START_REF] Cromwell | Polyhedra[END_REF]: The cyclic group C k consists of the single k-fold rotation axis (k ≥ 1), the dihedral group D consists of the single -fold principal axis and 2-fold axes ( ≥ 2) perpendicular to the principal axis. The remaining three groups, the tetrahedral group T , the octahedral group O, and the icosahedral group I are called polyhedral groups, because they are defined by the rotations of corresponding polyhedra (Figure 1). Table 1 shows for each of the rotation groups T , O, and I, the number of elements around its k-fold rotation axes (k ∈ {2, 3, 4}).

In the group theory, we do not distinguish the principal axes of D 2 from the other two 2-fold axes. Consider a sphenoid consisting of 4 congruent isosceles triangles (Figure 2). Rotation operations on such a sphenoid are those of D 2 , however we can recognize, for example, the vertical 2-fold axis from the others by their lengths (between the midpoints connecting). The family of sets of points on which only D 2 can act are lines, rectangles, such sphenoids, and their compositions. Actually, we can easily show that a set of points to which D 2 can act but we cannot distinguish the principal axis have four 3-fold rotation axes, thus T can also act on the set. Hence, the sets of points to which only D 2 can act have the principal axis. Later we will show that the robots can form a plane if they can recognize a single rotation axis or a principal axis. Based on this, we say that the cyclic groups and the dihedral groups are two-dimensional (2D), while the polyhedral groups are three-dimensional (3D) since polyhedral groups cannot act on a set of points on a plane.

Let S = {C k , D , T, O, I |k = 1, 2, . . . , and = 2, 3, . . .} be the set of rotation groups, where C 1 is the rotation group with order 1; its unique element is the identity element (i.e., 1-fold rotation). When G is a subgroup of G (G, G ∈ S), n , by B(P ) and b(P ), we denote the smallest enclosing ball of P and its center, respectively. We now define the rotation group of a set of points in 3D-space. For a set of points P ∈ P 3 n , the rotation group that acts on P and no proper supergroup of it acts on P is uniquely determined. We call such group the rotation group of P and denote it by γ(P ). Hence, even when the points of P are on one plane, its rotation group is chosen from cyclic groups and dihedral groups. For example, the rotation group of four points forming a square is D 4 . 4 It is worth noting that each robot r i can obviously calculate γ(P ) from P (more specifically, from its local observation Z i (P )), by checking all rotation axes that keep P unchanged.

A point on the sphere of a ball is said to be on the ball, and we assume that the interior or the exterior of a ball does not include its sphere. For a set of points P , when all points of P are on B(P ), we say P is spherical. We say that a set of points P is vertex-transitive regarding a rotation group G, if (i) for any two points p, q ∈ P , g * p = q for some g ∈ G, and (ii) g * p ∈ P for all g ∈ G and p ∈ P , where * denotes the group action. Note that a vertex-transitive set of points is always spherical.

Given a set of points P , γ(P ) determines the arrangement of its rotation axes. We thus use the name of a rotation group and the arrangement of rotation axes interchangeably. We define an embedding of a rotation group to another rotation group. For two groups G, G ∈ S, an embedding of G to G is an embedding of each rotation axis of G to one of the rotation axes of G so that any k-fold axis of G overlaps a k -fold axis of G satisfying k|k with keeping the arrangement of the axes of G, where a|b denotes that a divides b. For example, we can embed T to O, and T to I, but cannot embed O to I. In fact, group G can be embedded to an arrangement of group G if G G .

Theorem 2. Let P ∈ P 3

n be any initial configuration. Then P can be decomposed into subsets {P 1 , P 2 , . . . , P m } in such a way that each P i is vertex-transitive regarding γ(P ). Furthermore, the robots can agree on a total ordering among the subsets.

Proof. (Sketch.) For any point p ∈ P , let Orb(p) = {g * p ∈ P : g ∈ γ(P )} be the orbit of the group action of γ(P ) through p. By definition Orb(p) is vertextransitive regarding γ(P ). Let {Orb(p) : p ∈ P } = {P 1 , P 2 , . . . , P m } be its orbit space. Then {P 1 , P 2 , . . . , P m } is obviously a partition which satisfies the first part of the statement. Such a decomposition is unique as a matter of fact.

Then, we can show that there exists a translation of a local observation of a robot to a "local view" that satisfies the following two properties:

1. All robots in P i have the same local view for i = 1, 2, . . . , m. 2. Any two robots, one in P i and the other in P j , have different local views, for all i = j.

We will show the idea of the translation. Let L(P ) be the largest empty ball that is centered at b(P ), contains no point of P in its interior, and contains at least one point of P on its sphere. Intuitively, the local view of r i ∈ R is constructed by considering L(P ) as the earth and line p i b(P ) as the earth's axis, where p i is the position of r i . Then, the positions of each robot is represented by its amplitude, longitude, and latitude. This local view does not depend on any local coordinate systems, and each robot can compute the local view of other robots. Then, the robots can agree on the total ordering of the subsets.

We call {P 1 , P 2 , . . . , P m } the γ(P )-decomposition of P . The robots can agree on the decomposition and the ordering of the subsets, and each robot can recognize which subset it resides. In the following, we assume that {P 1 , P 2 , . . . , P m } is ordered in this ordering, thus P 1 is on L(P ) and P m is on B(P ).

We go on to the analysis of the structure of a set of points that is vertextransitive regarding a 3D rotation group. Any vertex-transitive (spherical) set of points P is specified by a rotation group G and a seed point s as the orbit Orb(s) of the group action of G through s. Not necessarily |G| = |Orb(s)| holds. For any p ∈ P , we call µ(p) = |{g ∈ G : g * p = p}| the multiplicity of p. 5 We of course count the identity element of G for µ(p), and µ(p) ≥ 1 holds for all p ∈ P . We can show that the multiplicity of p ∈ P is identical, and µ(p) > 1 when it is on the µ(p)-fold rotation axis of G.

For a set of points P ∈ P 3 n and its γ(P )-decomposition {P 1 , P 2 , . . . , P m }, if γ(P ) is a 3D rotation group, each P i is one of the polyhedra shown in Table 2.

Proof of Theorem 1

This section proves Theorem 1. In Subsection 4.1, we show the necessity of Theorem 1 by showing that any algorithm for oblivious FSYNC robots cannot form a plane if an initial configuration does not satisfy the condition in Theorem 1.

In Subsection 4.2, we show the sufficiency by presenting a plane formation algorithm for oblivious FSYNC robots.

Necessity

Provided |P | ∈ {12, 24, 60}, we first show that when a set of points P is a vertextransitive set of points regarding a 3D rotation group, there is an arrangement of local coordinate systems of robots forming P such that the execution from P keeps a 3D rotation group forever, no matter which algorithm they obey.

Lemma 1.

Assume n = |R| ∈ {12, 24, 60}. Then the plane formation problem is unsolvable from an initial configuration P (0) for oblivious FSYNC robots, if P (0) is a vertex-transitive set of points regarding a 3D rotation group.

Proof. (Sketch.) The idea of the proof is to show that we can construct local coordinate systems in P (0) that keep the rotation axes of group G forever in the execution of any algorithm, where G is given as follows:

G =    T if n = 12, O if n = 24, I if n = 60.
We construct a set of symmetric local coordinate systems based on the fact that P (0) is vertex-transitive regarding G. If G = γ(P (0)), this property clearly holds. The only case where G = γ(P (0)) is when G = T and γ(P (0)) ∈ {O, I}, but we can show that there exists an embedding of T to γ(P (0)) such that no robot is on the rotation axes of T . With the fact that |P (0)| = |T |, P (0) is vertex-transitive regarding T . Let P (0) = {p 1 , p 2 , . . . , p n } where p i is the position of r i ∈ R. We fix a local coordinate system Z 1 arbitrarily for r 1 ∈ R, that is fixed by the origin, the positions of (1, 0, 0), (0, 1, 0), and (0, 0, 1) of Z 1 in Z 0 . Then, because for each r i ∈ R there exists a distinct element g i ∈ G such that p i = g i * p 1 , we obtain the local coordinate system of r i by applying g i to Z 1 . The local coordinate systems of the robots are symmetric regarding G, local observations of the robots are identical, and the output of the algorithm that the robots execute are identical at the robots, i.e., the destination of robots are symmetric regarding G. After the movement, the positions and local coordinate systems of the robots are still symmetric regarding G. Let P (1) be this new configuration. In the same way, in P (1), the next destinations are symmetric regarding G. In this way, robots repeat symmetric movement regarding G forever and any configuration that appears in the execution keeps G.

From Lemma 1, the plane formation problem is unsolvable from each of the semi-regular polyhedra except an icosidodecahedron consisting of 30 robots. Some of the minimum unsolvable instances are a regular icosahedron, a truncated tetrahedron, and a cuboctahedron, each of which consists of 12 robots.

When an initial configuration P is not vertex-transitive, we obtain the following theorem by applying Lemma 1 to each of the subsets of the γ(P )decomposition of P . Theorem 3. Let P and {P 1 , P 2 , . . . , P m } be an initial configuration and the γ(P )-decomposition of P , respectively. Then the plane formation problem is unsolvable from P for oblivious FSYNC robots, if γ(P ) is a 3D rotation group, and

|P i | ∈ {12, 24, 60} for i = 1, 2, . . . , m.

Sufficiency

This subsection proves the following theorem by showing a plane formation algorithm for oblivious FSYNC robots.

Theorem 4. Let P and {P 1 , P 2 , . . . , P m } be an initial configuration and the γ(P )-decomposition of P , respectively. Then oblivious FSYNC robots can form a plane from P if either (i) γ(P ) is a 2D rotation group, or (ii) γ(P ) is a 3D rotation group and there exists a subset P i such that |P i | ∈ {12, 24, 60}.

A very rough idea behind the plane formation algorithm is the following: Let P (0) and {P 1 , P 2 , . . . , P m } be an initial configuration and the γ(P (0))decomposition of P (0).

If γ(P (0)) is a 2D rotation group, since there is a single rotation axis or a principal axis, which is obviously recognizable by the robots, they can agree on the plane perpendicular to this axis and containing b(P (0)), and indeed the robots can select distinct landing points on the plane.

Suppose otherwise that γ(P (0)) is a 3D rotation group. Then there is a subset P i such that |P i | ∈ {12, 24, 60}. That is, |P i | < |γ(P (0))| (γ(P (0)) = γ(P i )), and all robots in P i are on some rotation axes of γ(P (0)). The proposed symmetry breaking algorithm moves the robots of P i so that none of them will be on any rotation axes of γ(P (0)). This move cannot maintain γ(P (0)), otherwise Fig. 3. Two robots on a plane do not agree on the clockwise direction even when they have chirality.

these robots form a vertex-transitive set of points with multiplicity one regarding γ(P (0)), thus |P i | = |γ(P (0))| which is a contradiction. Specifically, such P i forms a regular tetrahedron, a cube, a regular octahedron, a regular dodecahedron, or an icosidodecahedron from Table 2. Our symmetry breaking algorithm breaks the symmetry of these (semi-)regular polyhedral configurations, and as a result configuration P (1) yields such that γ(P (1)) is a 2D rotation group.

In the following, we assume that b(P (0)) ∈ P (0) because the robots trivially can translate a configuration P (0) with b(P (0)) ∈ P (0) to another configuration P (1) with γ(P (1)) = C 1 by the robot on b(P (0)) leaving the center.

The proposed plane formation algorithm consists of three phases. The first phase selects P s with the smallest index among the subsets whose size is not in {12, 24, 60}, and shrinks P s so that it becomes the innermost subset in the next configuration P (1), i.e., only the robots that formed P s is on L(P (1)) and these robots form the same (semi-)regular polyhedron as P s . This phase is necessary to keep the center of the smallest enclosing circle of robots.

The second phase breaks the (semi-)regular polyhedron formed by the robots on L(P (1)) and configuration P (2) yields whose rotation group γ(P (2)) is a 2D rotation group. We call this phase "go-to-center" phase. Intuitively, this phase makes the robots on L(P (1)) select an adjacent face of polyhedron that they form and approach the center, but stop before the center. We will show that the destinations of robots do not have any 3D rotation group, and the robots succeeds in breaking their symmetry.

Finally, in the third phase, the robots agree on the plane F perpendicular to the single rotation axis (or the principal axis) and containing b(P (2)). Then, they land distinct positions of F . Each robot selects the foot of the perpendicular line from its current position to F as its destination. Let P 1 , P 2 , . . . , P be the γ(P (2))-decomposition of P (2). For each P i , at most two robots select the same destination, however, these robots can easily select new different destinations. Because all local coordinate systems are right-handed, if the negative z-axis of the two robots points to F , the clockwise directions (e.g., rotation from the positive y-axis to positive x-axis) of the two robots are different (Figure 3). By using this property and b(P (2)) as a reference point, the two robots select different points on a small circle centered at their common foot as their destinations.

Because of the page restriction, we focus on the second phase. The proposed symmetry breaking algorithm is shown in Algorithm 4. Proof. (Sketch.) Let {P 1 , P 2 , . . . , P m } be the γ(P )-decomposition of P . Because of the assumption, we have |P 1 | ∈ {12, 24, 60}. Thus, P 1 is either a regular tetrahedron, a regular octahedron, a cube, a regular dodecahedron or an icosidodecahedron by Table 2.

In Algorithm 4.1, only the robots in P 1 move. Each robot p ∈ P 1 selects a face F of P 1 incident on p, and moves to d which is at distance from the center c(F ) of F on line segment pc(F ), with a restriction that p needs to select a regular pentagon if P 1 is an icosidodecahedron. Note that is common to all robots in P 1 . Then, letting D be the set of points consisting of the candidates for d (for p ∈ P 1 ), D forms one of the polyhedra shown in Figure 4. Specifically, Figure 4(a) illustrates an -cantellated tetrahedron, which corresponds to the candidate set D when P 1 is a regular tetrahedron. Figure 4(b) illustrates an -cantellated cube, which corresponds to the candidate set D when P 1 is a regular octahedron. Figure 4(c) illustrates an -cantellated octahedron, which corresponds to the candidate set D when P 1 is a cube. Figure 4(d) illustrates an -cantellated icosahedron, which corresponds to the candidate set D when P 1 is a regular dodecahedron. Finally, Figure 4(e) illustrates an -truncated icosahe- dron, which corresponds to the candidate set D when P 1 is an icosidodecahedron. We would like to emphasize the difference between -cantellated icosahedron and an -truncated icosahedron.

Let S ⊂ D be any set such that |S| = |P 1 |. Then it is sufficient to show that γ(S) is a 2D rotation group. To derive a contradiction, suppose that there is an S such that γ(S) is a 3D rotation group. We first claim b(S) = b(D), otherwise γ(S) is a 2D rotation group because the intersection of two balls is either a point, a circle, or a ball. For each of the polyhedra that P 1 can be, we can show that γ(S) is a 2D rotation group for each of the five cases by contradiction.

First, when P 1 forms a regular tetrahedron, D is an -cantellated tetrahedron (Figure 4(a)). If γ(S) is a 3D rotation group, S must be a regular tetrahedron, since |S| = |P 1 | = 4. Since S is a regular tetrahedron, one point should be selected from the four faces of P 1 . Then we can show the non-existence of a desirable S by checking, for each candidates for S in an exhaustive way, its inconsistency.

Second, when P 1 forms a regular octahedron, D is an -cantellated cube (Figure 4(b)). If γ(S) is a 3D rotation group, because |S| = 6, S must be a regular octahedron, since otherwise S was the union of a regular tetrahedron and a 2-set, and γ(S) would be a 2D rotation group. Obviously S cannot be a regular octahedron, since D is an -cantellated cube and all vertices are around vertices of a cube.

The above two cases show the two basic techniques that we use for the remaining three cases. When P 1 forms a cube, a regular dodecahedron, or an icosidodecahedron, S must contain either a regular tetrahedron, a regular octahedron or a cube as a subset. However, we can show that D does not contain any of these regular polyhedra and we conclude that γ(S) is a 2D rotation group for any |P 1 |-subset of D, which implies that γ(P ) is a 2D rotation group.

Finally, as already mentioned, from a configuration P , robots can agree on a common plane and land distinct points on it if γ(P ) is 2D rotation group. Consequently, we obtain Theorem 4.

Conclusion

In this paper, we have investigated the plane formation problem for anonymous oblivious FSYNC robots in 3D-space. To analyze it, we have used the rotation group of a set of points in 3D-space, and presented a necessary and sufficient condition for the plane formation problem. Since real systems work in a 3Dspace, many natural problems would arise from practical applications.

Fig. 1 .

 1 Fig. 1. Rotation groups: (a) the cyclic group C4, (b) the dihedral group D5, (c) the tetrahedral group T , (d)(e) the octahedral group O, and (f)(g) the icosahedral group I. Figures show only one axis for each fold of axes.

Fig. 2 .

 2 Fig. 2. A sphenoid consisting of 4 congruent isosceles triangles. Its rotation group is D2. Since the vertices are not placed equidistant positions from the three axes, we can distinguish an axis as the principal axis from the others.

Fig. 4 .

 4 Fig. 4. Candidate set D. White circles are the points of D. (a) -cantellated tetrahedron, (b) -cantellated cube, (c) -cantellated octahedron, (d) -cantellated icosahedron, and (e) -truncated icosahedron.

Table 1 .

 1 Rotation groups T, O and I, and their elements.

	Rotation group 2-fold axes 3-fold axes 4-fold axes 5-fold axes Order
	T	3	8	-	-	12
	O	6	8	9	-	24
	I	15	20	-	24	60

Table 2 .

 2 Vertex-transitive sets of points generated by 3D rotation groups: rotation group, order, multiplicity, and cardinality.

	Rotation group Order Multiplicity Cardinality Polyhedron
			3	4	Regular tetrahedron
	T	12	2	6	Regular octahedron
			1	12	Infinitely many polyhedra
			4	6	Regular octahedron
	O	24	3 2	8 12	Cube Cuboctahedron
			1	24	Infinitely many polyhedra
			5	12	Regular icosahedron
	I	60	3 2	20 30	Regular dodecahedron Icosidodecahedron
			1	60	Infinitely many polyhedra

  1. Symmetry breaking algorithm for robot r i ∈ R Let P be a configuration such that γ(P ) is 3D rotation group and |P 1 | ∈ {12, 24, 60} where {P 1 , P 2 , . . . , P m } is the γ(P )-decomposition of P . Then the robots execute Algorithm 4.1 at P and suppose that a configuration P yields as the result. Then γ(P ) is a 2D rotation group.

	Algorithm 4.1 Notation
	P : Current configuration with γ(P ) ∈ {T, O, I} observed in Zi.
	{P1, P2, . . . , Pm}: γ(P )-decomposition of P where |P1| ∈ {12, 24, 60}.
	: An arbitrarily small distance compared to the distance between any two
	centers of the faces of P1 and determined by using the radius of B(P ).
	pi: Current position of ri (i.e., the origin).
	Algorithm
	If pi ∈ P1 then
	If P1 forms an icosidodecahedron then
	Select an adjacent regular pentagon face.
	Destination d is the point before the center of the face
	on the line from pi to the center.
	Else
	// P1 forms a regular tetrahedron, a regular octahedron,
	// a cube or a regular dodecahedron.
	Select an adjacent face of the regular polyhedron.
	Destination d is the point before the center of the face
	on the line from pi to the center.
	Endif
	Move to d.
	Endif
	Lemma 2.

The symmetricity was originally introduced in[START_REF] Yamashita | Computing on anonymous networks: Part I-Characterizing the solvable cases[END_REF] for anonymous networks to investigate the solvability of some agreement problems.

It is impossible to break up multiple oblivious FSYNC robots (with the same local coordinate system) on a single position as long as they execute the same algorithm, and thus our algorithm avoids any multiplicity. However, we need to take into account any algorithm that may lead R to a configuration with multiplicities, when proving the impossibility result by reduction to the absurd.

Since Zi changes whenever ri moves, notation Zi(t) is more rigid, but we omit parameter t to simplify its notation.

This is the major difference between the rotation group of robots in 3D-space and the symmetricity of robots on 2D-plane. In our context, existing works assume that robots agree on the "top" direction against the plane where robots resides and their symmetricity is chosen from cyclic groups[START_REF] Fujinaga | Pattern formation by oblivious asynchronous mobile robots[END_REF][START_REF] Suzuki | Distributed anonymous mobile robots: Formation of geometric patterns[END_REF][START_REF] Yamashita | Characterizing geometric patterns formable by oblivious anonymous mobile robots[END_REF].

The word "multiplicity" is also used for a multiset. Here, the multiplicity of a point p is the size of the stabilizer of G respect to p[START_REF] Rotman | An introduction to the theory of groups[END_REF]. Readers can identify the meaning clearly from the context.

This work was supported by a Grant-in-Aid for Scientific Research on Innovative Areas "Molecular Robotics" (No. No. 24104003 and No. 15H00821) of The Ministry