Raphael Deau
email: deau@tls.cena.frgotteland@tls.cena.fr

Jean-Baptiste Gotteland

Nicolas Durand
email: durand@tls.cena.fr

Airport surface management and runways scheduling

Keywords: airport, ground delay, conflicts resolution

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

I. INTRODUCTION

Air traffic growth was confirmed over the past few years and will certainly continue in the next years: in the european SESAR (Single European Sky ATM Research) project, a very ambitious capacity increase is expected for all of the future ATM systems.

Regarding busy airports, new technologies are available in order to improve the whole ground traffic management process (A-SMGCS: Advanced Surface Movement Guidance and Control Systems). They should moreover allow a better coordination between airport controllers and the approach sectors.

In accordance with these evolutions, this article studies how it could be possible to integrate these future systems together in order to optimise the runways sequences in busy airports while taking into account the complete taxiing constraints of each planned aircraft.

A. Framework

Optimising the trajectories of taxiing aircraft becomes a very complex problem when the number of aircraft increases and when various possible paths are available for each of them: this study concerns the ground traffic management on big international plateforms and will more precisely be applied to Roissy Charles De Gaulle airport.

On such an airport, some big efforts are now invested on the surface management process (SMAN), aiming at decreasing the taxiing times of aircraft with various procedural methods [1], [START_REF] Günther | Niederstrasser Total Airport Management (Operational Concept and Logical Architecture)[END_REF], [START_REF] Bohme | Coordinated Arrival Departure Management[END_REF]. This problem is actually more complex, especially when it is put in relation with the various other studied concepts: the arrival management (AMAN) and the departure management (DMAN), which have been too often developed separately. Most difficulties actually arise when the constraints of each management process are both considered: the coordination between SMAN and DMAN is notably identified as a very difficult challenge.

From the airport controller's point of view, arriving aircraft are considered to be the entries of the situations to manage, as far as the AMAN systems operate upstream (in the approach sectors) to sequence properly the arrival flow. However, the resulting constraints on the ground traffic management should be well anticipated to manage correctly the departures flow, especially when mixed runways (shared by both departures and arrivals) are in use.

Another kind of constraints more specific to european airports must be taken into account: the takeoff slots assigned by the Central Flow Management Unit (CFMU) to some particular departures. Airport controllers are in charge of their application, even if (and especially when) the airport traffic demand is high.

B. Known difficulties

As introduced before, the interaction between the SMAN systems and the AMAN-DMAN systems appears to be the main difficulty: the current DMAN systems do not integrate the circulation constraints of the aircraft precisely enough and thus can suggest some departures sequences ignoring the delay that can be generated around gates or taxiways intersections. Even if this kind of delay can seem low compared to those resulting from the runways separations, the intended runways sequences however become unmanageable very frequently.

Moreover, SMAN and DMAN systems do not need the same anticipation time, which makes their coordination difficult: at the SMAN level, the distances between aircraft are reduced and aircraft speeds are not well known, so that the system needs a lot of reactivity to keep aircraft separated and can hardly anticipate the traffic situations more than 5 or 10 minutes in advance [START_REF] Durand | Runways sequence and ground traffic optimisation International Conference on Research in Air Transportation[END_REF], [START_REF] Gotteland | Optimisation du trafic au roulage sur des grands aéroports[END_REF]. Conversely, the AMAN or DMAN systems deal with some higher time separations between aircraft (over one minute) and their targeted anticipation time is consequently around 30 minutes. The synchronisation between data coming from the SMAN and DMAN systems is therefore a complex problem by itself.

C. Goals

This article follows an older publication [START_REF] Durand | Runways sequence and ground traffic optimisation International Conference on Research in Air Transportation[END_REF], in which the complexity of the realisation of some optimal runways sequences at the SMAN level was first measured. Two new keypoints are studied here:

• The first section (II) is dedicated to the evaluation of the delay that would affect the departures if the only separations to apply were the ones relative to the runways (thus, ignoring any other kind of ground traffic conflict), and comparing the resulting delay with two different sequencing strategies (optimised or not). • The next sections (III, IV) try to refine some existing ground conflicts resolution methods in order to fit as better as possible with some targeted optimised runways sequences, in spite of the delay due to the ground conflicts.

II. RUNWAYS SEQUENCES ANALYSIS

This section introduces the runways sequences optimisation problem and defines a deterministic method to solve it, in order to evaluate the minimal ground delay that could be expected at the airport if the runways capacities where the only limiting factor to consider.

A. Principles

The runways sequencing process can be represented easily as a classical constraint satisfaction and optimisation problem:

• The variables of the problem are the take-off or landing slots that must be assigned to the aircraft.

• The main constraints are the runway separation rules, which can be globally described by the miminal separation time required between two aircraft (one, two or three minutes), depending on their wake turbulence categories (low, medium or high). The other constraints are the earliest possible runways access times of each aircraft (the planned landing time for an arrival and the planned off block time added to the minimal taxiing time for a departure). • The optimisation criterion can be relative to different performance measurement, as the delay generated by the runway sequence and the deviations between the assigned slots and the CFMU required slots for the regulated departures. Even if this kind of scheduling problem is well known in the litterature, it is combinatorial with the number of aircraft and cannot be solved directly by classical methods if we consider the whole daily traffic of an international airport like Roissy Charles de Gaulle (more than 1500 flights). Moreover, the purpose of a DMAN system is not to build such a complete runway sequence but to find the best (local) solution in a real time environment, within a limited anticipation time (less than one hour).

In order to remain consistent with these real time hypotheses, the runways sequences optimisation is studied on successive time periods during the day, with a limited anticipation time T RW Y . A branch & bound algorithm [START_REF] Ahuja | Network Flows, Theory, Algorithms and Applications[END_REF] is defined to explore the different runways sequences and find the best solutions.

B. Parameters

Two main parameters can affect the efficiency of the proposed runways scheduling: • The landing times flexibility: the AMAN planned landing times can be lightly modified by airport controllers, as the aircraft can be asked to anticipate or postpone the use of their flaps during the final descent. From the operationnal point of view, this is necessary for the management of the mixed runway but should not exceed λ = ±30 seconds if decided a couple of minutes in advance.

C. Minimisation criterion

The criterion p i to minimise for an aircraft i is defined as illustrated on figure 1:

• For arrivals, no sequencing penalisation is applied, because the landing times are already constrained by the AMAN scheduling. • For a regulated departure (which take-off time is constrained by a given CFMU slot), a light penalisation is assigned when the aircraft is scheduled at the end of the CFMU time period acceptance (as this is a very risky scheduling) while a high penalisation is assigned when the aircraft is scheduled after the required slot. • For other classical departures, the criterion measures the delay resulting from the aircraft scheduled take-off time.

D. The scheduling algorithm

In order to find one of the best solutions, the branch & bound algorithm can potentially explore all the aircraft permutations, but once an acceptable solution is found, the corresponding criterion value is used as an upper bound for the remaining exploration.

Moreover, a lot of permutations can be consistently removed, if it is prooved that they do not lead to a better solution than some other explored permutations:

• At first, swapping two arrivals is obviously not permitted (because the arrivals are considered to be already sequenced by the AMAN system). • Swapping two equivalent departures is useless (as the resulting delay will remain unchanged). The equivalence of two aircraft is relative to their wake turbulence category and their CFMU constraints.

• Some aircraft pairs are independant and must not be swapped: this is the case when the earliest runway access time of an aircraft comes far after (more than the required separation time) the initial feasible scheduling of another aircraft.

E. Results

The different optimisation methods are compared by simulating a heavy day of traffic at Roissy Charles de Gaulle airport, in a complex configuration: a mixed runway (on which both arrivals and departures are planned) and two specialised runways (one for the departures and the other for arrivals) are in use and the arriving aircraft have to cross the departures runway after landing.

The optimised runways sequences (OPT) are compared to the first come first served (FCFS) ones and to some older (OLD) ground simulations taking into account all the aircraft ground taxiing constraints [START_REF] Durand | Runways sequence and ground traffic optimisation International Conference on Research in Air Transportation[END_REF] with the same traffic sample.

The following The first observation concerns the order of magnitude of the delay assigned to departures (that are not regulated), which is much lower than the ones measured by the older simulations (the mean delay is globally reduced more than twice in the optimised scenario). This result allows to quantify the importance of the delay coming from the SMAN constraints compared to the ones coming from the AMAN-DMAN systems: both appear to be more or less equivalent as far as these systems are not sufficiently coordinated.

Another suprising result is the stability of the mean delay obtained (36 seconds for the optimised As far as all the SMAN constraints are not involved, the runways sequences could be correctly optimised with an apparently short anticipation time of 10 minutes. However, a higher anticipation time is required for the coordination with approach sectors. On the contrary, figure 2 shows the good influence of the landing times flexibility on the delay generated by the mixed runway: these figures show that the interaction with the landing times is necessary to manage this particular runway configuration (the delay increases significantly when λ is close to 0). We can also notice that the ±30 seconds value recomended by the airport controllers appears to be a great compromise between the operational complexity of these interactions and the potential benefits provided to the departures.

III. RUNWAYS SEQUENCES INTEGRATION IN THE SURFACE MANAGEMENT

A. Simulation of the surface management (SMAN)

A more detailed description of the ground traffic simulator used in this study in order to simulate the surface management at Roissy can be found in [START_REF] Gotteland | Handling CFMU slots in busy airports Proceedings of the Air Traffic Management R&D Seminar[END_REF]: this section only summarizes the main ideas that are directly involved in the next sections.

1) General overview: The airport is modeled as a graph of taxiways, linking its gates to its runways (see figure 3). This graph allows to assign to each aircraft a set of various possible paths [START_REF] Martins | A new algorithm for ranking loopless paths[END_REF] taking into account the maximal taxiing speeds on each taxiway portion and respecting the exploitation procedures in use (as oneway taxiways for example). The traffic sample is described by the actual flightplan data of one day at Roissy airport. Each flightplan gives all the information needed to reproduce an aircraft evolution and its constraints, including the aircraft type, the gate and runway used, the readyto-go time for a departure, the landing time for an arrival, etc. For a regulated departure, the flightplan also provides the special take-off slot required by the CFMU.

The traffic simulation of a complete day at Roissy airport is carried out by iterations, using a prediction time window T w and a resolution period ∆ < T w : at each time t in the simulation (every ∆ minutes), a traffic prediction is performed within the time window [t; t + T w ]. The possible future positions of each aircraft are computed relatively to a given speed uncertainty, defined as a fixed percentage of the nominal speed: this uncertainty makes aircraft positions become lines of possible positions in the prediction (see figure 3).

2) Aircraft separation rules: Separation rules between active aircraft are modeled as follows:

• Aircraft waiting at the gate position are considered separated from all other aircraft (while any other aircraft attempts to access the gate). • The distance between two moving aircraft must always be above 60 meters. • After each take-off or landing, a minimal separation time is required to clear the next move from the wake turbulence.

• When an aircraft is taking off or landing on a given runway, the other aircraft can be crossing this runway area or taxiing in it, as long as they are behind it (in accordance to current controllers practices). When two aircraft trajectories does not respect these rules in the prediction, the aircraft pair is in conflict. The transitive closure of this relation gives the clusters of conflicting aircraft. The conflicts of each cluster can be solved separately as far as the resulting decisions do not create new conflicts between aircraft of different clusters (in which case, the concerned clusters would have to be joined together).

3) Optimisation criterion: The separation rules described in the previous section represent the constraints of the problem to solve in each ground traffic situation. Among all the acceptable solutions, some are better than others in terms of aircraft delay or runways sequences optimisation: the optimisation criterion allows to evaluate each solution in order to compare them and select the best.

For the purpose of this article, the selected optimisation criterion is a function to minimise, defined as the sum of each particular criterion relative to each aircraft: (see figure 4):

• For classical departures (not regulated by the CFMU): the criterion measures the ground delay assigned to the aircraft, and is twice more penalising when the resulting take-off time of the aircraft comes over its targeted runway slot. • For regulated departures: the criterion measures also the application of the CFMU slot (with respect to the CFMU official acceptance). • For arrivals: the criterion measures the ground delay assigned to the aircraft with a smaller ponderation, in order to give a higher priority to the departure flights. 4) Conflicts resolution: In order to solve a cluster of conflicting aircraft (i.e. ensure the separations between all the concerned aircraft), some decisions must be taken by the controllers. In the simulation, these decisions concern:

• The path that each aircraft must follow;

• If needed, one or more positions to hold by some aircraft; • For the arrivals, the exact landing time can be lightly moved compared to the one forecasted by the AMAN system, as described in II-B. Thus, the problem is to find the most appropriate control decisions to ensure aircraft separations on the taxiways and in the runways areas, while minimising the global optimisation criterion. Thus formulated, this optimisation problem is obviously combinatorial with the number of aircraft and cannot be solved by exact methods: sections III-D and III-E describe the two different methods used.

B. Runways sequences integration

To be relevant, the runways sequences planned by the departure manager (DMAN) must be taken into account in advance, during all the surface management process and the resolution of each ground traffic situation. Different strategies can be developed to fit as often as possible to these planned sequences:

• A first idea is to solve the ground conflicts by delaying first the departures that are the most ahead of their runway slot in the targeted sequence. This can be quantified by the following measure:

α = T OT -R -t
where:

-T OT is the targeted take-off time for the aircraft -R its minimal remaining taxiing time t the current time

• Another common principle is to lead the departure aircraft to reach the runway threshold in the right order and at the right moment (not too late but not too early either). For this purpose, a strategic off block time can be computed for each departure: this point is detailed in section III-C. However, the runways sequences anticipation time (T RW Y ≃ 30 minutes) is far greater than the ground traffic situations anticipation (T w ≃ 5 minutes) and it seems unavoidable that some of these situations eventually conflict with the initial targeted sequences (especially when some departure times are delayed too much). When such a situation occurs, the latest As a consequence, the targeted runways sequences must be regularly updated (every ∆ minutes) in accordance with the ground traffic situation, before and after each conflict resolution, and the scheduling must be kept as close as possible to the previous one. For these reasons, the airport simulations are carried out with the following iterative process (see figure 5):

1) Predict the traffic at time t, with the DMAN anticipation time, on the period [t; t + T RW Y ]; 2) Update the runways scheduling; 3) Solve the conflicts with the SMAN anticipation time, on the period [t; t + T w ]; 4) Build the new situation applying the SMAN decisions on the period [t; t + ∆] and go on with the next situation: t ← t + ∆.

C. Strategic departures off block times

In order to dispatch the departure traffic on the taxiways in accordance with the targeted runways sequences, some strategic off block times can be assigned to the aircraft (asking them to hold at the gate position even if ready). The main idea is to ensure that after leaving the gate, an aircraft cannot preceed another aircraft if its take-off time comes after chronologically. Thus, if a departure i is planned before another departure j in the runway sequence, then the following relation must be verified:

OBT i + t i ≤ OBT j + t j
where:

• OBT i is the off-block time of aircraft i • t i is the minimal taxiing time of aircaft i This relation gives a recurrent definition of the strategic off-block times (SOBT) for the departures planned in the same runway sequence (if the aircraft are indexed in respect with the sequence):

SOBT 0 = EOBT 0 SOBT i+1 = max(EOBT i+1 , SOBT i + t i -t i+1 )
where EOBT is the earliest possible off-block time for the aircraft.

D. The sequential resolution method

In order to solve the ground conflicts between aircraft, a first sequential method consists in simplifying the described problem by assuming a classification of the concerned aircraft: the first aircraft is considered to have the highest priority and is assigned its shortest path without any holding position. Then, the (n + 1) th aircraft trajectory is found by solving the conflicts with the n previously optimised and trajectories. A deterministic branch & bound algorithm [START_REF] Horst | Global Optimization: Deterministic Approaches[END_REF], [START_REF] Ahuja | Network Flows, Theory, Algorithms and Applications[END_REF] can easily test if a solution exists for each aircraft, and in such a case, finds the best solution (relatively to the global criterion to minimise) for each of them.

When the considered classification comes to a problem without any solution for an aircraft, the classification can be adapted (by upgrading the priority level of the concerned aircraft) and the process restarted with this new classification. Past simulations [START_REF] Gotteland | Optimisation du trafic au roulage sur des grands aéroports[END_REF] have shown that this deterministic method improved with the possible adaptation of the classification could solve correctly all the ground situations at Roissy.

Moreover, this resolution method has the great advantage to be directly compatible with the constraints coming from the DMAN and AMAN systems: the initial classification can be provided by the targeted runways sequences. Thus, the priority levels of aircraft can be defined as follows:

P rio i = Slot i
where P rio i is the priority level of aircraft i and Slot i its landing or take-off slot in the targeted runway sequence.

It is also interesting to decrease the priority level of the already landed aircraft in order to favour the taxiing departure flow (as often recommanded by operationnal controllers):

For a landed aircraft i: P rio i = Slot iδ ARR For practical purposes, δ ARR is a duration parameter allowing to adjust the priority level of the departure flow and can be experimented with values varying from a few minutes (light penalisation of the arrivals) to one or more dozens of minutes (departures always favored).

E. The genetic algorithms based method

1) Goals: The sequential method described in the last section presents some various disadvantages:

• It deals with a simplification of the global optimisation problem, so that all the possibilities ar not explored and the best solution is hardly obtained. • It requires a total classification of aircraft. Even if this classification should not be penalising for aircraft sharing the same runway (as they must anyway use the runway one after the other), it can appear unadapted between aircraft of different runways when they are moving near gates and taxiways areas.

To overcome these drawbacks, the conflict resolution problem must be considered in its general formulation and its solutions explored with different types of methods like genetic algorithms, as presented in the litterature [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF], [START_REF] Durand | Automatic aircraft conflict resolution using genetic algorithms Proceedings of the Symposium on Applied Computing[END_REF].

2) Implementation: In this article, the sequential method is compared to an hybrid optimisation method, based on a genetic algorithm exploring the possible combinations of paths and priority levels assignments and using the branch & bound algorithm to develop each solution:

• A chromosome is defined by 2N integer variables {(n i , p i )} 1≤i≤N , where N is the number of aircraft in the cluster to solve, n i the path assigned to aircraft i and p i its priority level. • The evaluation of a chromosome is performed by the branch & bound algorithm used in the sequential method, limited to the paths and the classification described by this chromosome. • The fitness function f is defined in accordance to the constraints that have to be respected and the global criterion to minimise:

-For a chromosome with n c > 0 aicraft without any solution:

f = 1 1 + n c (< 1 2 )
-For a chromosome corresponding to an acceptable solution:

f = 1 2 + 1 2 + N i=1 p i (> 1 2 )
where p i is the criterion to minimise for aircraft i, as described in section III-A3. With this definition, the fitness function is partially separable as defined in [START_REF] Durand | Genetic crossover operator for partially separable functions[END_REF] and can be associated with some improved crossover and mutation operators to speed up and improve the genetic algorithm convergence.

IV. RESULTS

A. Simulations

different optimisation methods are compared by simulation, using the same traffic sample (and the same runways configuration) than in section II.

The anticipation time of the AMAN-DMAN process is set to 30 minutes (for the runways sequences optimisation) while the SMAN anticipation time (for the ground conflicts resolution) is set to 5 minutes.

Three scenarios are compared:

• One using the sequential resolution method with a basic runways sequencing process (first come first served); • The second one using the same sequential method but with the optimised runways sequencing process, as described in section III-D; • The last one concerns the hybrid genetic algorithm associated with the optimised runways sequencing, as described in section III-E.

B. Departures delay

Figure 6 shows the variations of the delay assigned to the classical departures during the day, in the three studied scenarios. The delay generated by the three traffic peaks (around 10am, 2pm and 7pm) can be quantified. We can notice the significant delay reduction due to the optimisation on the runways sequences (between one and two minutes per aircraft are saved during these traffic peaks).

We can also observe the improvment provided by the hybrid genetic algorithm compared to the sequential resolution method. Figure 7 shows the departures mean delay as a function of the number of moving aircraft by time periods of 10 minutes and confirms the efficiency of the runways sequences optimisation process, especially during traffic peaks.

C. Arrivals delay

Figure 8 enlightens the most important difference between the two compared resolution methods: the ground delay assigned to the arriving aircraft (after landing) is reduced from 140 seconds down to 40 seconds during the traffic peaks with the genetic algorithms method. This result shows up the lack of flexibility of the aircraft classification made in the sequential method, in which a higher priority level has to be given to the departures in order to apply correctly the targeted runways sequences. The runways sequences analysis carried out in section II evaluates the ground delay that would result from the only runways capacities limits at Roissy Charles de Gaulle airport: this delay appears to be half less important than the delay measured by a complete ground simulation of the same traffic sample, in which the whole taxiing constraints of aircraft are considered (even if some efficient optimisation methods are used to solve the ground conflicts between aircraft). These results show all the complexity of the surface management process on such a busy airport and enlightens the challenge that must be performed in the next years concerning the conception of some well coordinated AMAN-DMAN and SMAN systems.

In the following sections, the ground conflicts resolution algorithms are refined. These kind of algorithms could be integrated in the SMAN system of the airport, in order to minimise the impact of the taxi delay and to fit to an evolutive runways scheduling: the use of a more global optimisation method, associated with the definition of some strategic off-block times for departures allows to reduce significantly the ground delay, despite of the considered aircraft speed uncertainties and the well known gates and taxiways congestion areas.

This way, the SMAN system should take a great advantage of its synchronisation with the AMAN-DMAN systems: the efficiency of a basic sequential resolution method is largely enhanced when the needed aircraft classification is deduced from the optimal runways scheduling. Obviously, keeping in mind this scheduling allows to select some more consistent solutions for the ground traffic situations, especially when the concerned aircraft are far from the runways. The resulting ground delay should be reduced and the traffic predictions of the DMAN system should become more relevant.

  Fig. 1. Minimisation criterion

Fig. 2 .

 2 Fig. 2. Influence of the landing times flexibility

Fig. 3 .

 3 Fig. 3. Clusters of conflicting aircraft

Fig. 4 .

 4 Fig. 4. Criterion to minimize

Fig. 5 .

 5 Fig. 5. Runways sequence optimisation and conflicts resolution

Fig. 6 .Fig. 7 .

 67 Fig. 6. Departures delay during the day

Fig. 8 .

 8 Fig. 8. Arrivals delay as a function of the number or aircraft

  table gives the global results of this comparison:

		OLD FCFS OPT
	Dep. mean delay (sec)	85	54	36
	Missed CFMU slots	14	16	14

• The anticipation time T RW Y , that will vary from

AUTHORS


Stéphane Chatty

Stéphane Sire

Jean-Luc Vinot
email: vinot@cena.fr

Patrick Lecoanet

Alexandre Lemort

Christophe Mertz
email: mertz@intuilab.comlecoanet

Revisiting Visual Interface Programming: Creating GUI Tools for Designers and Programmers

Keywords: visual design, vector graphics, SVG, software architecture, GUI tools, model-driven architecture CATEGORIES: H5.2 [Information Interfaces and presentation] User Interfaces -GUI; D2.11 [Software engineering] Software Architectures design, human factors, languages

Involving graphic designers in the large-scale development of user interfaces requires tools that provide more graphical flexibility and support efficient software processes. These requirements were analysed and used in the design of the TkZinc graphical library and the IntuiKit interface design environment. More flexibility is obtained through a wider palette of visual techniques and support for iterative construction of images, composition and parametric displays. More efficient processes are obtained with the use of the SVG standard to import graphics, support for linking graphics and behaviour, and a unifying model-driven architecture. We describe the corresponding features of our tools, and show their use in the development of an application for airports. Benefits include a wider access to high quality visual interfaces for specialised applications, and shorter prototyping and development cycles for multidisciplinary teams.

INTRODUCTION

The work of graphic designers in user interface projects was popularised with the Web and desktop interfaces [START_REF] Mullet | Designing Visual Interfaces[END_REF]. With the growing understanding that this work can improve users' performance and acceptance of new products, it is now sought in the design of specialised user interfaces, from aircraft cockpits to plant supervision systems. For instance, Figure 1 illustrates a graphic designer's work for air traffic control. This evolution raises an important engineering issue: how can companies design and produce such design-intensive software at reasonable costs? For standalone applications with no complex functional core, tools such as Flash and Director allow designers to produce high quality products. But for more complex software, programmers and designers still have to choose between cost and flexibility. On the one hand, pre-designed widgets offered by interface builders are simple to assemble. However programmers often produce poor layouts, and designers resent the low control over the look and interaction style. On the other hand, graphical libraries offer greater flexibility: programmers can reproduce designs provided by graphic designers within certain limits. But even then the limits are sometimes too strict for designers, and the cost of re-coding their work is too high to support both iterative design and a profitable industry. Efficiently involving graphic designers in the production of interactive software calls for tools that meet the requirements of both graphic design and software engineering. It requires graphical capabilities that match the working methods of designers. It also challenges the architecture of common user interface tools and the notion of predefined widgets, which were introduced solely for programming purposes. This article describes these two sets of issues and the solutions that we implemented respectively in TkZinc and In-tuiKit. TkZinc is a graphical library provided as a replacement for the Canvas component in the Tk toolkit [START_REF] Ousterhout | Tcl and the Tk toolkit[END_REF]. It is available at www.tkzinc.org. Co-designed with a graphic designer, its features are aimed at providing programmers with graphical capabilities and concepts that give them a common vocabulary with designers. IntuiKit is an interface design suite aimed at making the prototyping and development of multimodal user interfaces more accessible to industrial companies. Its model-driven architecture [START_REF] Jespersen | Investigating user interface engineering in the model driven architecture[END_REF] supports software engineering processes that involve iterative design and designers from multiple disciplines. In this paper, we focus on the features of IntuiKit that are aimed at graphic designers: the use of the Scalable Vector Graphics (SVG) standard as the graphical model of the environment, and an architecture that focuses on combining the graphical facet of interactive components with the other facets that are produced by programmers. We then illustrate the use of IntuiKit on a real application, and discuss implementation details, related work and the limitations and perspectives of our work. All illustrations in this paper except diagrams are screen shots of applications created with TkZinc and IntuiKit.

MATCHING DESIGNERS' WORK

Art does not reproduce the visible; rather, it makes visible.

Paul Klee, 1920 Producing efficient visuals is not just a matter of good taste and having tools with a rich graphical model. Graphic designers are trained to use methods evolved by artists over centuries, whatever the media and tools. Understanding those methods helps selecting which features are most needed by designers and in what form. That is what guided the development of TkZinc: the goal was to make user interface design an experience similar to illustration design, notwithstanding the fact that user interfaces are dynamic programs.

Being implemented as a Tk widget, TkZinc benefits from standard GUI mechanisms: windowing, event management, etc. The originality of TkZinc lies in its graphical primitives, chosen and organised as a mix of GUI programming libraries and drawing tools such as Adobe Photoshop and Illustrator. All other features, such as the programming interface or distribution of events to graphical items, are modelled after the Tk Canvas. The main graphical characteristics of TkZinc are vector-oriented graphics and visual effects, a 2D scene tree where groups play an important role, and a graphical model that includes shape construction, gradients, clipping, transparency and shading. Some of these features are classical and available in standards such as SVG, whereas others are more radical or only available in 3D tools such as OpenGL.

In this section we show how they were chosen, through the observation of visual designers.

When working on a display or a user interface, a designer takes several types of information into account:

• the characteristics of the media to be used, for instance the size and resolution of a screen; • the data to be displayed, which is the main focus of software engineers; • context information, provided by observation or more often by marketing or internal communication departments: what is the message to be conveyed to users (as opposed to mere data display); • efficiency considerations, based on psychological laws or know-how.

Designing a display starts with a holistic approach: building a global picture that conveys the desired message. The goal is to evoke things known to the user and not to reproduce them, by tricking the spectator's eye if necessary. Once this global picture is defined in their mind, designers work on solutions to reproduce it, using the available range of visual elements and techniques. We now examine in more details the techniques used, and how TkZinc supports them.

A palette of visual techniques

Artists and designers use many ways to convey the meanings they desire: contrasts, harmonies, light, etc. Combining these signals allows them to communicate data, but also context, culture or feelings, which contribute to the global interface usability and performance. The ideal designer's palette is made of shapes (including type), colours, textures, light and rhythm. In practice, they have always had to approximate it with available tools, whether physical or digital.

For that reason, we observed that designers sometimes use graphical tools in unexpected ways for programmers. This has guided the design of many parts of TkZinc.

Revisiting shapes Although our understanding of the world is made of shapes, our perception of it is not. Usually, artists do not use "graphical objects" to produce shapes. Graphical designers sometimes do, when they want to produce high contrast and visual simplicity. But generally, they rather see them as "construction lines" used to apply visual effects such as color strokes, shadows or light which produce the desired perception. For this reason, TkZinc offers shapes that can be used both as graphical objects or as geometrical templates. Furthermore, with graphical models based on objects, designers often lack intuitive notions such as holes and clipping. For that purpose, TkZinc provides two complementary solutions. Shape operations make it possible to build shapes by assembling or subtracting other shapes, thus providing solutions for holes. Clipping is also available: a shape can be used as a clip mask for any graphical object or group. Revisiting colour Perception is based on contrast, and colour contrast is the easiest to create. However, designers often want to use gradients rather than mere colour juxtaposition. This is why TkZinc provides a rich gradient model, where gradients can be defined from shapes. That includes linear and radial gradients, but also conical gradients, and gradients computed from arbitrary paths. Figure 2 illustrates how gradients can be used to simulate shapes, perspective effects, and shadows. The button on the left is made of a circular black arc filled with a conical gradient, then cloned, translated and filled with a path gradient. Most shapes and shadows on the right are built with similar techniques.

Rhythm A complement to materials is visual rhythm, provided for instance by repeated pencil lines or strokes on a drawing. Rhythm can be provided by filters applied to images or by line textures (the richer version of dashed lines). It can also be produced by the cloning and layout of visual objects along "networks". TkZinc provides geometrical grids that automatically clone and translate shapes and gradients. For instance, the top of figure 3 is made of one object built by mapping a square path on a grid, filled with a pixmap texture. Light The contrast between light and shade is an important way of signalling information as well as driving the order in which users read displays. It is also a way to structure the visual space, make it consistent and create 2-1/2D effects. The designer in our group likes to manage light as a "skin" added on top of shapes, colours and textures. For that purpose, TkZinc offers a combination of groups and transparency, as do recent versions of Adobe Illustrator. Objects can be hierarchically organised as groups, and a transparency can be associated to any group, making it behave as a semitransparent layer. Figure 1 makes heavy use of groups and transparency.

Image construction

The above techniques are basic blocks for designers' work. However, some images cannot be obtained with a single operation. Oil painting, for instance, involves the progressive construction of pictures with several layers of paint. Designers are used to building images in several successive operations. Several features of TkZinc support this process, sometimes perceived as sub-optimal by programmers: rather than being pre-computed, images are recomputed during the interaction, which allows designers to manage interactive displays while keeping the appropriate graphical control. Shape operations Building some shapes is easier through the combination of simpler shapes. For that purpose, TkZ-inc offers a set of algebraic operations on shapes: addition, subtraction, intersection. Shapes are successively built, filled with textures or gradients, used to build other shapes, etc.

Objects such as those shown on the left of Figure 4 can also be built by assembling triangles and shading the resulting tessellation.

Hierarchical structure The successive operations must often be applied to sets of objects rather than just one object. The combination of groups, transparency and clip masks that we described earlier plays an important role in this process. The picture on the right of Figure 4 is made of four shapes created from seven circles and a gradient each, which are grouped and cloned. The cloned group is translated and scaled, then clipped to produce the "magic lens" effect.

Attenuation and blending

The iterative construction of images involves sequences such as making an operation then subtly attenuating it on some parts of the display, or making two shapes and merging them with a superimposed layer that blends the contours. Groups, gradients and transparency can be used for that purpose. Filters such as blurring are not yet available in TkZinc but would also be desirable.

Parametric, interactive displays

Many of the above features are available, though often in different forms, in drawing tools, graphical libraries, SVG players, and in some UI toolkits. However, one should distinguish between drawing and creating representations. What is needed to create high-quality user interfaces is a set of objects that can be computed from application data, modified at run-time, and used to capture users' action. Dynamicity is central, and TkZinc allows designers to create dynamic interactive objects, not just draw.

Extreme vector graphics There is a debate in the UI toolkit community about bitmap and vector graphics: the former provide pixel-precise control to designers, whereas the latter offer scalability. The design of TkZinc represents a radical position in this debate: TkZinc aims at being a vectoronly toolkit (with a slight concession to imported textures and icons). Graphical objects are made of vectors of course, but gradients, clips, and grids are also based on geometrical vectors and can be changed at run-time. Similarly, all vertices of paths and curves can be accessed and changed individually. No new feature is added to TkZinc if it cannot be parameterised and related to the geometrical model. The reason for this choice is interactivity: all graphical constructs must be able to be bound to evolving data or interaction, and thus be recomputed at run-time.

Object selection Providing feedback often implies changing the visual attributes of several objects at the same time.

It is not always possible to put those objects in one group, because they may be grouped with other objects for other purposes: clipping, blending, etc. Another way of addressing several objects must be provided. TkZinc provides a system of tags inspired from Tk [START_REF] Ousterhout | Tcl and the Tk toolkit[END_REF]: an object can have several tags and it is possible to apply an operation to all the objects that share a given tag. We will see that in IntuiKit this system is extended to full XPath queries.

GRAPHIC DESIGN AND SOFTWARE ENGINEERING

Augmenting the palette offered by GUI tools to designers is an important first step. However, in many contexts this is not enough. First, this leads to a linear production process: graphic designers do their work, then programmers take over. Second, this involves a duplication of effort: programmers have to reproduce part or all of the graphics. We observed that these two factors often prevent software development groups from involving graphic designers, because of the related cost and project management issues.

Wider acceptance of iterative design and graphic design requires solutions that preserve the ability to redesign graphics, and avoid duplication of effort. The direction we chose in the design of IntuiKit was to explore software engineering processes that give graphic designers a more central role in the production of software, while preserving the ability of programmers to structure their code appropriately. Designers become software producers. Their artwork becomes a new type of software component that can be managed in its own way then merged with other components, just like software components obtained from different source files have to be merged by compilers and link editors in traditional software engineering.

IntuiKit is a software suite aimed at designing and prototyping multimodal user interfaces, then transferring them to industrial production. It is not centered around a modality but rather organised as an execution environment for models of software components, which makes it closer in many respects to a language interpretor than to a GUI toolkit. With IntuiKit, a user interface is the result of the instantiation and combination of several models. These are all provided by extensions to the core software component model that is used both for structuring programs and merging models. The set of models used depends on the type of interface and the preferred modelling approach: for instance, models of graphical objects and behaviours for GUIs, or speech and grammar rules for speech interfaces. These models can be built and managed independently, each with the appropriate tools. They are then loaded by IntuiKit from XML files or instantiated through a programming interface, linked together with application code or non-modelled UI code, and "executed".

In this section, we describe and illustrate the parts of IntuiKit that are central to the involvement of designers in the software engineering process: the general architecture and software component model, the SVG graphical model, the discrete behaviour model, and how they are combined to produce applications.

Architecture and components

The central structure of an IntuiKit application is a tree of Elements and Components. Elements are the nodes of the tree, and the basic blocks of all models: graphical objects, windows and behaviours are Elements. The execution of the application consists of a series of traversals of the tree, in which elements are activated. Initialisation, rendering and control flows triggered by events are example of such traversals. A special kind of Element is the Reference, which allows shared objects in the tree. Elements can be declared as models, making them insensitive to rendering traversals.

Elements can be cloned, thus giving IntuiKit some features of prototype languages. Elements can be loaded from XML files. They can be parameterised through a property mechanism: they export the names of their properties, which can be set from Cascading Style Sheets (CSS) files [START_REF] Lie | Cascading style sheets, designing for the Web[END_REF]. References can be defined using XPath expressions [START_REF]W3C Recommendation[END_REF] to select their target.

Components are Elements that contain children. They implement encapsulation and parameterisation through a namespace system. All element and property names exported by children are visible to their siblings. These names can in turn be exported (with an optional renaming) by the parent Component to its own siblings and parents. Properties can also be merged by the parent, which means that two sibling elements will share the merged property. Control in IntuiKit relies on a classical event model, in which any Element and Component can emit events. Programmers can implement their own Components in native code. The IntuiKit tree can be understood as an extended scene graph. We prefer to interpret it as the abstract tree of a language, because it is aimed at structuring software more than rendering graphics.

The core of IntuiKit only provides structuring and communication mechanisms. All interactive capabilities are provided by IntuiKit extensions; defining an extension consists of defining new Element types and their semantics when rendered. Element types can be taken from existing standards, as are the SVG elements for graphics or VoiceXML for speech. They can also be defined specifically, as are the finite state machines that are used below for defining the basic discrete behaviour of interactive components. Its object-oriented graphical model covers an important part of the requirements described earlier in this article, which makes it a good candidate for storing user interface graphics. SVG is also convenient as a graphical file format: it can be generated from graphic design tools such as Adobe Illustrator or Corel Draw. For these reasons, and despite some disparities with the features described earlier, the GUI module of IntuiKit implements the SVG model, using TkZinc as its graphical rendering engine. SVG elements are considered as IntuiKit Elements, and SVG groups as Components. In-tuiKit offers two equivalent ways for manipulating graphics: by loading SVG files or through a programming interface. Using files, one can manage graphics as an independent part of the software, produced for instance with Adobe Illustrator by saving the artwork in SVG format.

The two fragments of Perl code below show how the GUI module of IntuiKit is used. The first example uses the programming interface and opens a window that displays a text. It illustrates how the position of Elements in the tree influences the result just like in a scene graph: the window (Frame), font and text are added to the root Component in such an order that the text appears with the appropriate font in the window. $root->run;

The second example illustrates the use of an SVG file. It acts as a basic SVG player, by adding a window and an Element to a root Component. This is illustrated in Figure 5 with the SVG file from a very simple application that we will use in the rest of this section: a digital pet inspired from a popular electronic toy. The pet, named Henry-the-Frenchie, is totally useless and has a simple behaviour: it grumbles when hungry and can be fed by pressing a button.

$root = new Component;

new Frame ( -parent => $root );

$henry = load Element ( -parent => $root, $root->run;

Considering structured graphics files as a software component allows designers to deliver successive versions and thus to work in parallel with programmers. However, conventions must be established. IntuiKit uses Element names for that purpose: just like function or component names must be determined in advance between programmers, SVG element names must be agreed upon by designers and programmers. As an example, Figure 6 shows an extract of the Adobe Illustrator palette that represents the artwork for Henry-the-Frenchie. These layers and groups are saved in SVG as a tree of groups with the names that were set in the palette. Consequently, the palette reflects the contract passed between the designer and the programmer. Programmers must be able to capture events on graphical objects and change their appearance upon user events or messages from the functional core. For instance, Figure 7 illustrates event flows in the Henry-the-Frenchie application. The "start eating" and "stop eating" events are generated when the user depresses and releases the "eat" button. A simplified functional core (FC) manages an internal numerical value that grows while the button is depressed, then decreases periodically. It notifies "increase" and "decrease" events that correspond to Henry's status changing from starved to satiated or stuffed and back.

Describing behaviour is a different facet than graphics. The core module of IntuiKit provides an event system based on a classical binding mechanism. A binding associates an action with an event source (clock, graphical object, etc) and a specification (button click, key press, etc); a binding can be dynamically enabled or disabled. The GUI module that implements the SVG model defines graphical objects as event sources like the Tk Canvas: when the user clicks, the first visible object under the mouse with an active binding has its binding triggered. Bindings on groups can be specified as "atomic" so that events are detected in all elements of a group. This binding system provides the foundation for programming behaviour as a set of callback functions, or for using more elaborate models. The literature provides various models of discrete or continuous behaviour in user interfaces, such as StateCharts, finite state machines, Petri nets, data flows, constraints, etc. Any of these models could be offered as a set of Elements in In-tuiKit, provided that the appropriate semantics are defined and implemented (some of these models may require improvements to the core of IntuiKit). For discrete behaviours, IntuiKit currently implements finite state machines (FSMs). Although its limits are well known, this model is rich enough to define basic interactive components, and it illustrates how such a model can be combined with graphical Elements. Continuous behaviours such as scaling or translation are also available; they rely on the ability of the GUI module to change the attributes of SVG elements once they are instantiated.

Finite state machines:

IntuiKit defines FSMs as a set of states and a set of transitions labelled with event specifications and actions. When in a state, a binding is activated for each outgoing transition. Actions include traditional callbacks and event emission. Event specifications can refer to all Element names that are visible from the FSM (the names exported by its siblings). This makes it possible to associate behaviours to events occurring on graphical Elements defined in the same Component.

IntuiKit FSMs are local to their parent Component. They can be used to store its state and to emit events or trigger callbacks when certain sequences of events occur. They can also be used for basic graphical feedback by triggering the display and hiding of graphical Elements that are associated to its states. This takes advantage of a method often used by graphical designers who use Adobe Photoshop to build behaviours in Web pages: they store the different states of their objects into different layers and manually simulate the transitions by turning the visibility flag of the different layers on and off. IntuiKit offers this possibility by using property merging and the Switch Element. In SVG, a Switch is a special group that renders only one of its children depending on the value of a variable of the run-time context, such as the preferred user language. IntuiKit extends the semantics of the Switch, by defining an implicit property named "branch" which controls which child of the Switch will be rendered. If the Switch is present in the same Component as a FSM, one can synchronise the Switch and the FSM by merging the "branch" property of the Switch and the "state" property of the FSM: when the FSM changes state, it triggers a partial traversal of the tree, and the Switch is rendered according to its new active branch. Figure 8 shows the FSM-Switch pair used for Henry's stomach. The FSM receives "increase" and "decrease" events from the FC. It is associated with a Switch that activates the group containing the appropriate picture for Henry. Figure 9 gives a more complete view of the tree, and shows another aspect of combining models: Switches can actually control any type of Elements, not only SVG ones; in the case of FSMs, the semantics of "being hidden" is to be disabled, which means that no event binding is activated. This provides control similar to that of hierarchical FSMs, and it is used at two levels of depth for Henry: Idle or Eating, then Starved, Satiated or Stuffed when Idle. The code fragment below illustrates the creation of the tree with XPath references, FSMs, including event specification, and the merging of properties which synchronises a FSM and a Switch.

Adjusting parameters

User interface environments must support the management of parameters: colours, text labels, etc. In IntuiKit, this is obtained with CSS: all properties defined by Elements can be set from a style sheet file. For instance, let us assume that the Functional Core (FC) of Henry is implemented in Perl as a Component, and that the values of its "appetite" and "digestion" control its internal algorithms. The corresponding properties would then be defined as follows: IntuiKit is developed and distributed by IntuiLab since 2003. It offers a prototyping environment programmed and accessible in Perl, that has been used to develop car displays, touchscreen-based workstations for various domains, as well as prototype multimodal applications. It runs on Linux and Windows. A C port accessible in C++ and Java and aimed at small devices and production code is under development.

EXAMPLE APPLICATION

IntuiKit is used to develop prototypes or pre-operational products in various domains: automotive, aerospace, manufacturing, telecommunications and defence. This has given us the opportunity to test the concepts described in this article on real applications. Four graphic designers were involved in the projects, one at a time. Some had no previous experience of working with programmers. In all cases the collaboration was remote, meetings being reserved for participatory design sessions. These experiences allowed us to refine the proposed process and communication conventions between project managers, graphic designers and programmers. They also provided data to assess the gains brought by the chosen architecture in terms of schedules and effort.

We now describe the development of a departure manager for airports, which was designed and developed over a period of a few weeks in late 2003. It is a good example of how professional applications can benefit from giving designers more expressive power, and of the work process supported by our choice of software architecture. A company had developed algorithms to optimise the sequence of departures and coordinate controllers who guide taxiing aircraft. Air traffic controllers are known to be very demanding professional users, and the company wanted to embed their algorithms in touch-screen workstations that would both provide excellent usability and seduce users and decision makers. The application was meant for pre-operational tests, and consequently had to offer full functionality. The company also had a very tight schedule because they wanted to exhibit the product at a professional convention so as to gain customers. This strict deadline obviously played a key role in the organisation of the project.

The project team was composed of two programmers (one being the lead interface designer and the other a domain expert), and a graphic designer. The project started with a discount participatory design session that produced a paper prototype for every interface to be built in the project. Figure 10 shows one of the prototypes. This prototype served as the reference for all further developments on the interface, in several ways. First, the layout of the different parts of the interface was the result of collective work and served as the basis for future composition work by the designer. Second, all parts of the prototype were given a name: static parts ("printer", "column", "timeline", etc) as well as a template name for dynamic parts ("strip", "plan"). The names served as a basis for informal communication between participants, who never met again until the end of the project. Third, immediately after the session the lead interface designer decomposed the prototype into a tree of components, starting with the top-level parts. This tree represented the architecture of the application, both in terms of software components and graphical components. She used the tree as a collective contract and interface between project actors, especially between UI programmers and the graphic designer.

From then on, the programmers and the designer worked independently, contacts being limited to clarification questions or visual design proposals and feedback. The designer started working on the general impression he wanted to convey, and tested ambiances, colours, harmonies, textures, etc. Figure 11 gives a sample of his work. Meanwhile, programmers used the reference component tree to code the application. For each component they defined the behaviours, the computations, and the connection to the functional core. They also created basic graphics, which were needed for testing the code. They used a professional drawing tool to produce some of the graphics, others being coded with the IntuiKit Perl API. The result of their work is shown in Figure 12. The application was of very limited visual quality, but sufficient to test its usability as well as the connection to the functional core, implemented as a server.

Three to four weeks before the deadline, the designer had finished maturing the design and preparing his elements: fonts, Having a computer equipped with IntuiKit and being regularly sent new versions of the application, he was able to test the elements in context himself: for that, he just had to drop SVG files in the appropriate places. When satisfied with the result, he sent the SVG files to the programmers by email. Figure 13 shows two SVG designs that are perfectly equivalent from the application's point of view, though not exactly equivalent for the user. Finally, after a period of design, test, feedback, redesign, and integration, the final graphics were produced a few days before the deadline. The very low cost of integrating graphics as well as the ability to work in parallel allowed for these very late iterations while programmers were busy testing and debugging the application. This process allowed every actor of the project to manage time in their own way to work until the last limit, without excessive tension. The final result is shown in Figure 14. As a final note, the product was a great success with potential users and customers at the exhibition, and its interface was perceived by all as an important competitive advantage. This is one more empirical proof of the potential of graphic design for professional systems and the importance of supporting it.

DISCUSSION AND PERSPECTIVES

Practical experience with TkZinc and IntuiKit such as the one we just described has evidenced both benefits and remaining limitations. The most obvious benefit of using rich graphical models is the visual quality of the resulting user interfaces, when designed by professionals. But we consider the efficiency gains as equally important. The project described above has allowed us to compare figures with a project of similar size and complexity executed by the same team a few months earlier without Intuikit. The earlier project involved the same effort by the graphic designer (15 days) and the same amount of non-graphical UI code (15 kloc). It was built with a more traditional process: the designer produced visual elements that the programmers reproduced with their programming language (Perl, used in object-oriented style). We have observed three major improvements in the execution of the second project with IntuiKit:

• a 20-30% reduction in programming effort, obtained by avoiding the re-coding of graphics; • a 50-70% reduction in overall project length, obtained with the parallel production process, even though a pipe-line process was set up in the earlier project to incorporate visual elements as they were produced; • a reduction in coordination costs that we did not measure but that we estimate at 50-70% in terms of number and duration of telephone calls.

We also have identified several limitations and possible improvements:

• Freeing graphic designers from certain constraints has a major impact on performance: they create much more complex visual representations. Between the two projects mentioned above, memory use has more than doubled (from 30 Mb to 70 Mb with IntuiKit). Similarly, graphical performance becomes an issue again, even with recent GPUs. Animations in the application illustrated in Figure 14 are not smooth enough with low-end GPUs. • The standard SVG format does not support all types of blending between layers, neither does TkZinc. Some designers consider that as a constraint, since they use blending in their iterative construction of visual effects. An option might be to support SVG extensions provided by some graphical tools. • IntuiKit does not yet support SVG filters, which could be useful to designers especially in terms of rhythm and light. However, performance issues would have to be monitored. • Some of the features of TkZinc are lost when using In-tuiKit and SVG. That forces a trade off between development cost and visual richness. Evolutions of the SVG standard could help avoid that trade off. • The use of OpenGL in TkZinc provides expressiveness and performance. However, extra care had to be taken when implementing features with OpenGL and there still are a few conceptual flaws caused by it. OpenGL is not primarily aimed at 2D graphics design, and some operations lead to inappropriate results as far as visual designers are concerned: lack of pixel-precise control in certain cases, and unnatural results for certain colour combinations.

IntuiKit was tested successfully on projects where the initial iterative design was done with low-fidelity prototypes, and production started once the general structure of the interface was decided upon. It has not been tested for early design phases. Regarding the response of teams, experience showed that many programmers are not yet used to programming user interfaces as components communicating through We are considering the use of rules or constraints [START_REF] Szekely | A user interface toolkit based on graphical objects and constraints[END_REF], as well as data-flow techniques inspired from [START_REF] Chatty | Extending a graphical toolkit for two-handed interaction[END_REF], [START_REF] Jacob | A software model and specification language for non-WIMP user interfaces[END_REF] or [START_REF] Dragicevic | Input device selection and interaction configuration with icon[END_REF].

Future work also includes the implementation of new models. For GUIs, that would include layout, non-linear geometric transformations, and animation. Finally, access for nonprogrammers would require tools for building models, when no commercial tools are already available. This includes a graphical editor for building behaviours and associating them to graphics. This could also include other techniques from the literature to build or infer models, such as programming by demonstration.

RELATED WORK

Although mostly aimed at 3D rendering, the wide availability of OpenGL-capable graphics cards stimulates the introduction of richer 2D tools. For instance, the new Java 1.5 adds OpenGL-based rendering for Java2D. Similarly, the scene graph of 3D toolkits such as Open Inventor [START_REF] Wernecke | The Inventor Mentor, programming object-oriented 3D graphics with Open Inventor[END_REF] has also inspired the design of toolkits for programming post-WIMP user interfaces [START_REF] Bederson | Jazz: an extensible zoomable user interface graphics toolkit in Java[END_REF][START_REF] Beaudouin-Lafon | The architecture and implementation of CPN2000, a post-WIMP graphical application[END_REF][START_REF] Lecolinet | A molecular architecture for creating advanced GUIs[END_REF]. The focus of these toolkits is on providing extendable architectures for developing novel in-teraction and visualisation techniques. Ubit for instance is based on a scene graph model for combining visual elements with behavioral elements and layout elements [START_REF] Lecolinet | A molecular architecture for creating advanced GUIs[END_REF]. These elements are defined in a declarative C++ style, and thus are not accessible to graphic designers. CPN2000 is a graphical Petri net editor [START_REF] Beaudouin-Lafon | The architecture and implementation of CPN2000, a post-WIMP graphical application[END_REF]. It has been built with a programming toolkit that supports transparency and non-rectangular windows rendered with OpenGL, and uses SVG to display icons. Many SVG renderers such as the Batik toolkit [START_REF]The Apache XML project[END_REF] are available, as well as SVG extensions to existing toolkits. Most of them are limited to displaying graphics and do not provide programmers with access to graphical objects so as to manage interaction. Similarly, little consideration is given to work processes and the role of graphic designers.

Previous work on involving graphic designers in the production of user interfaces can be analysed according to the level of flexibility given to designers. At one end are designermade widgets that can be reused by programmers. Then some tools incorporate designers' know-how for producing semi-automated designs: the Kandinsky system [START_REF] Fogarty | Aesthetic information collages: generating decorative displays that contain information[END_REF] provides programmers with templates they can transform for presenting data; the Kinetic typography engine [START_REF] Lee | The kinetic typography engine: an extensible system for animating expressive text[END_REF] encapsulates animation techniques from cartoons. At the other end, Hudson et al [START_REF] Hudson | Supporting dynamic downloadable appearances in an extensible user interface toolkit[END_REF][START_REF] Hudson | Providing visually rich resizable images for user interface components[END_REF] propose solutions for splitting widgets into several pixmap zones, which allows programmers to resize them at will while designers can still propose interchangeable designs. By using vector graphics, the IntuiKit GUI module avoids the problem of resizing. By not relying on a predefined set of widgets, it gives the designers total con-trol on the look and behaviour of interactors, but does not support the creation of themes. With IntuiKit, designers produce the graphical part of the interface, rather than providing styles for graphical objects assembled by programmers.

Regarding software architecture, IntuiKit can be compared to the model-driven tools that use the XML format [START_REF] Souchon | A review of XMLcompliant user interface description languages[END_REF]. The closest are the XUL [START_REF] Boswell | Creating Applications with Mozilla[END_REF] and XAML widget sets, which allow vendors to provide variants of widgets as long as they implement the specification. IntuiKit is more oriented towards post-WIMP interfaces and allows one to freely manipulate graphical objects and behaviours, whereas XAML widgets are provided as compiled C# code. Current efforts by the W3C are aimed at extending SVG with other markup languages such as XForms [START_REF] Quint | SVG and XForms: A primer[END_REF] for describing behaviour, but put less stress than IntuiKit on separating concerns.

CONCLUSION

We have described the design and features of the IntuiKit interface design suite and its graphical engine TkZinc aimed at supporting designers' needs when developing user interfaces. The features of TkZinc allow programmers to better match the work of designers. The architecture of IntuiKit, based on the combination of models, allows teams to manage graphics separately from behaviour and other software concerns then merge them in a structured tree of components. It organises the collaborative work of designers and programmers. The SVG format, though sometimes restrictive, is key to this process because it allows designers to use their own tools to produce parts of the interface. The architecture of IntuiKit helps bridge the gap between iterative design and software engineering cycles, and is ready for integrating new models and making them available to development groups.

Figure 1 :

 1 Figure 1: Visual techniques, when used by graphic designers, can enrich the message conveyed.

Figure 2 :

 2 Figure 2: Complex gradients used to create a rubberlike appearance (left) or to simulate a 3D design (right)

Figure 3 :

 3 Figure 3: Rhythm can be obtained by repeating shapes along networks and combining them

Figure 4 :

 4 Figure 4: Hierarchical groups, simple transformations, clipping, shape operations and gradients help shape the scene light and provide great expressiveness

Figure 5 :

 5 Figure 5: Henry-the-Frenchie

$

  root = new Component; new Frame ( -parent => $root ); new Font ( -parent => $root, -family => 'Helvetica' ); new Text ( -parent => $root, -text => 'EAT!!!' );

Figure 6 :

 6 Figure 6: Structure of the SVG file for Henry

Figure 7 :

 7 Figure 7: Event flows in Henry

Figure 8 :

 8 Figure 8: The FSM-Switch pair for Henry's stomach Switches:In SVG, a Switch is a special group that renders only one of its children depending on the value of a variable of the run-time context, such as the preferred user language. IntuiKit extends the semantics of the Switch, by defining an implicit property named "branch" which controls which child of the Switch will be rendered. If the Switch is present in the same Component as a FSM, one can synchronise the Switch and the FSM by merging the "branch" property of the Switch and the "state" property of the FSM: when the FSM changes state, it triggers a partial traversal of the tree, and the Switch is rendered according to its new active branch.

Figure 9 :

 9 Figure 9: The complete IntuiKit tree for Henry

$

  eat_model = $svg->find( -ref => './/Eating' ); $eat_model->clone( -parent => $Henry ); ... $switch = new Switch( -parent => $Henry, -branches => { 'eating' => '../Eating', ... $fsm = new FSM( -parent => $Henry, -states => [ 'eating', 'idle' ], -transitions => { {-from => 'idle', -to => 'eating', -on => [$eat_button, 'StartEating']}, ... $Henry->merge( -names => [$fsm->state, $switch->branch] );

  = new Component; $self->define( -name => 'appetite', -default => '10'); $self->define( -name => 'digestion', -default => '5'); ... Then, the functional component could be created as follows: $root = new Component ( -name => 'Henry' ); $fc = new FC ( -parent => $root, -name => 'fc' ); And finally, the properties could be changed with the following style sheet file: free software graphical library distributed by CENA since 1998. Aimed at prototyping, it is built as a widget in the Tcl-Tk environment, and can be used from the Tcl, Python and Perl scripting languages. Its core structure is coded in C and originally based on the X Window System. Many advanced visual features of TkZinc require OpenGL. TkZinc runs on Windows, Linux and Mac OSX. Initially developed for safety-critical displays, TkZinc has good CPU performance and reliability: earlier versions of TkZinc were used in operational air traffic control workstations from 1998 to 2003 for interactive displays composed of thousands of graphical objects. Benchmarking against the Java-based Batik SVG player revealed that TkZinc was more than 10 times faster when loading and displaying a figure made of 2600 curves amounting to 84000 vertices.

Figure 10 :

 10 Figure 10: The paper prototype that served as a reference for group work

Figure 11 :

 11 Figure 11: The designer's work on "the global picture"

Figure 12 :

 12 Figure 12: The application, with programmer-made graphics

Figure 13 :

 13 Figure 13: Detail: two skins for the "strips"

Figure 14 :

 14 Figure 14: The final application, after full integration

ACKNOWLEDGEMENTS

Frédéric Lepied (now with Mandrakesoft), Dominique Ruiz and Stéphane Valès contributed to the implementation of TkZinc and IntuiKit. Yves Rinato (Intactile Design) designed the departure manager, which is shown with the kind permission of Sofréavia. Michel Beaudouin-Lafon was of great help in improving earlier versions of this paper.