domain: spi phys math info

text:
Nicolas Gobillot
email: nicolas.gobillot@ifremer.fr

Lesire Charles

Doose David

A Design and Analysis Methodology for Component-Based Real-Time Architectures of Autonomous Systems

Keywords: Robotics software, Real-time analysis, Modelling language data ports, similar

The integration of autonomous robots in real applications is a challenge. It needs that the behaviour of these robots is proved to be safe. In this paper, we focus on the real-time software embedded on the robot, and that supports the execution of safe and autonomous behaviours. We propose a methodology that goes from the design of component-based software architectures using a Domain Specific Language, to the analysis of the real-time constraints that arise when considering the safety of software applications. This methodology is supported by a code generation toolchain that ensures that the code eventually executed on the robot is consistent with the analysis performed. This methodology is applied on a ground robot exploring an area. Categories (2), (3)

Nowadays dangerous, repetitive or precision requiring jobs are done by robots like flying drones, industrial assembly arms or medical assistants. In all these cases, human beings can interact with the machines. It is therefore essential to guarantee that every part of the robot software and hardware will produce a safe behaviour. For instance, we need to ensure that these robots will not damage themselves or their environment and more importantly that they do not hurt any human-being. Safety concern has already been considered regarding several aspects of robotics: collision avoidance [START_REF] Freitas | A practical obstacle detection system for autonomous orchard vehicles[END_REF][START_REF] Haddadin | A truly safely moving robot has to know what injury it may cause[END_REF][START_REF] Lens | Investigation of safety in human-robot-interaction for a series elastic, tendon-driven robot arm[END_REF], human awareness [START_REF] Rybski | Sensor fusion for human safety in industrial workcells[END_REF][START_REF] Tamura | Development of pedestrian behavior model taking account of intention[END_REF], fault detection [START_REF] Elbaum | Reducing failure rates of robotic systems though inferred invariants monitoring[END_REF][START_REF] Nakamura | Error recovery using task stratification and error classification for manipulation robots in various fields[END_REF], or controller synthesis [START_REF] Decastro | Guaranteeing reactive high-level behaviors for robots with complex dynamics[END_REF][START_REF] Pathak | Ensuring safety of policies learned by reinforcement: Reaching objects in the presence of obstacles with the iCub[END_REF]. In this paper we are concerned with the analysis of the fulfilment of real-time constraints on the robot software. Real-time constraints are part of the non-functional requirements that arise when guaranteeing the safety of a critical software. Real-time constraints are of course not sufficient, as the functionnal part of the architecture must also be proved. Violating real-time constraints can however lead to inconsistent or unsafe behaviours of the functional part of the software architecture. For instance, [START_REF] Cervin | The Jitter Margin and Its Application in the Design of Real-Time Control Systems[END_REF][START_REF] Henriksson | On Dynamic Real-Time Scheduling of Model Predictive Controllers[END_REF] have analysed the impact of software delays in control systems regarding the system stability. Verifying real-time constraints of embedded control architectures is therefore necessary to guarantee a safe behavior of the robotic system.

Real-time analysis

Real-time guarantees are brought by timing analyses on the software. A real-time analysis is based on the computation of the Worst Case Response Time (WCRT) of tasks [START_REF] Mark H Klein | A practitioner's handbook for real-time analysis[END_REF]. The WCRT of a task represents the longest time between its activation and the end of its execution, including all the possible interruptions. During the past decades, the widely known Liu and Layland [START_REF] Liu | Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment Scheduling Algorithms for Multiprogramming[END_REF] fixed priority models, as well as dynamic priority task models such as Earliest Deadline First (EDF, [START_REF] Spuri | Analysis of Deadline Scheduled Real-Time Systems[END_REF]) have been precise enough for software analysis. Such models use a common and simple task model (see Fig. 1): each task τ i is defined by a period T i and a deadline D i . At each period, corresponding to a release date r k , the task instance has to be executed. The execution, that can possibly be preempted, takes a time C k (in the figure, C k = C (1)

k + C (2) k ).
In classical task model, this computation time is noted C i and is represented by an upper bound of its value, the Worst Case Execution Time (WCET). The response time R k is then the delay between r k and the end of execution, and we have to prove that R k < D i , ∀i, k. Due to the increasing complexity of the real-time systems, the analysis methods had to be adapted taking into account resource partitioning [START_REF] Sha | Priority inheritance protocols: An approach to real-time synchronization[END_REF][START_REF] Chen | Dynamic priority ceilings: A concurrency control protocol for real-time systems[END_REF][START_REF] Theodore | Stack-based scheduling of realtime processes[END_REF]. Other improvements needed to account for task interdependency [START_REF] Chetto | Dynamic scheduling of real-time tasks under precedence constraints[END_REF]. All these approaches for real-time analysis of software applications are based on a model of the software. It is then very important to have an execution model which is as close as possible to the practical execution that takes place on robots.

Software design in robotics

Developing autonomous robots has lead researchers to design several concepts to organise functional parts of the software architecture, including, among others, sensing, planning, and acting functions. A classical architecture concept is the 3-level architecture [START_REF] Gat | On three-layer architectures[END_REF], and other paradigms have been proposed in the past decades [START_REF] James S Albus | 4D/RCS: a reference model architecture for intelligent unmanned ground vehicles[END_REF][START_REF] Mcgann | A deliberative architecture for AUV control[END_REF][START_REF] Muscettola | IDEA: Planning at the Core of Autonomous Reactive Agents[END_REF][START_REF] Volpe | The CLARAty architecture for robotic autonomy[END_REF]. Such developments are the application part of the software architecture: they concern the implementation of the functions embedded on the robot, but they must also settle on a middleware and/or operating system in order to be eventually deployed. Moreover, the development and implementation of these applications encounter some specificity when developing robotic application. They need for fast evolutions that lead to short development cycles of several month unlike in aeronautics or in the nuclear field which have development cycles of tenth of years. Furthermore the complexity of embedded systems software architectures increases with more and more tasks involved, making the use of software design methodologies and tools mandatory. To help the software robot developer, some recent design approaches used in robotics are based both on a middleware to help the development, and on a component-based approach to help managing the development cycle. Such approaches are typically relevant when the system under study is a critical embedded system (or at least some part of the software is critical). A component-based design pattern allows the software architect to build a robotic architecture by assembling existing software components [START_REF] Brugali | Component-Based Robotic Engineering (Part I)[END_REF][START_REF] Brugali | Component-Based Robotic Engineering (Part II)[END_REF]. Table 1 summarizes several approaches regarding either middlewares for developing robotic applications (top rows) and model-based processes (bottom rows).

Table 1: Summary of related references and their respective features ( when supported, ∼ when partially supported or limited, when unsupported). RTC [START_REF] Ando | Software Deployment Infrastructure for Component Based RT-Systems[END_REF] RoboComp [START_REF] Manso | RoboComp: A Tool-Based Robotics Framework[END_REF][START_REF] Martínez | Improving a robotics framework with real-time and high-performance features[END_REF] Orocos [START_REF] Soetens | Realtime hybrid task-based control for robots and machine tools[END_REF] ROS [START_REF] Quigley | ROS: an open-source Robot Operating System[END_REF] Model-based BIP [START_REF] Basu | Incremental Component-based Construction and Verification of a Robotic System[END_REF] ∼ CPAL [START_REF] Navet | CPAL: High-level Abstractions for Safe Embedded Systems[END_REF] Rock [34] [30] ∼ BRIDE [START_REF] Bruyninckx | The BRICS Component Model: A Model-Based Development Para-digm For Complex Robotics Software Systems[END_REF] [31] G en oM [START_REF] Mallet | GenoM3: Building middlewareindependent robotic components[END_REF] ∼ ∼ [START_REF] Foughali | Model Checking Real-Time Properties on the Functional Layer of Autonomous Robots[END_REF] ∼ [START_REF] Foughali | Model Checking Real-Time Properties on the Functional Layer of Autonomous Robots[END_REF] SmartSoft [START_REF] Schlegel | Design Abstraction and Processes in Robotics: From Code-Driven to Model-Driven Engineering[END_REF][START_REF] Steck | Towards quality of service and resource aware robotic systems through model-driven software development[END_REF] ∼ [START_REF] Singhoff | Cheddar : a Flexible Real Time Scheduling Framework[END_REF] Middlewares provide operating system and hardware abstractions. A middleware typically proposes an Application Programming Interface to develop and deploy tasks and threads without taking into account the operating system and thus the hardware specificities. While we can find several robotic-oriented middlewares with real-time capabilities [START_REF] Yang | Lessons Learned from the Development of Component-Based Medical Robot Systems[END_REF][START_REF] Ando | Software Deployment Infrastructure for Component Based RT-Systems[END_REF][START_REF] Martínez | Improving a robotics framework with real-time and high-performance features[END_REF][START_REF] Soetens | Realtime hybrid task-based control for robots and machine tools[END_REF], only Orocos-RTT [START_REF] Soetens | Realtime hybrid task-based control for robots and machine tools[END_REF] uses a behaviour model of components, based on a Finite State-Machine. Moreover, Orocos-RTT is widely used, in particular because of its integration with ROS [START_REF] Quigley | ROS: an open-source Robot Operating System[END_REF]. Component-based approaches are often associated with modelling languages, such as Domain Specific Languages (DSL), that allow to develop software components in more abstract languages. Interesting approaches with respect to real-time and behaviour models are summarized in Tab. 1: BIP [START_REF] Basu | Incremental Component-based Construction and Verification of a Robotic System[END_REF] and CPAL [START_REF] Navet | CPAL: High-level Abstractions for Safe Embedded Systems[END_REF] have their own execution engine; BRIDE [START_REF] Bruyninckx | The BRICS Component Model: A Model-Based Development Para-digm For Complex Robotics Software Systems[END_REF] and Rock [34] provide model-based design of components and allow to respectively generate ROS and Orocos components; G en o M [START_REF] Mallet | GenoM3: Building middlewareindependent robotic components[END_REF] proposes a rich component behaviour model, and can generate code into several middlewares (e.g., Orocos, ROS). Real-time evaluations in G en o M [START_REF] Foughali | Model Checking Real-Time Properties on the Functional Layer of Autonomous Robots[END_REF] are only based on raw measurements, and make the hypothesis that functions execution will not be preempted by the operating system. SmartSoft [START_REF] Schlegel | Design Abstraction and Processes in Robotics: From Code-Driven to Model-Driven Engineering[END_REF][START_REF] Steck | Towards quality of service and resource aware robotic systems through model-driven software development[END_REF] allows to generate real-time code based on the DDS framework and estimates the WCRT using Cheddar [START_REF] Singhoff | Cheddar : a Flexible Real Time Scheduling Framework[END_REF] without using the component behaviour model.

Contribution

The literature presented here above shows that there is no toolchain for real-time development of robotic software components that is complete, i.e. that provides a model-based development of real-time components, coupled with an accurate analysis of real-time properties. In this paper, we propose a design and real-time analysis process that is compliant with the current usage of robotic software developers, uses an accurate model of the resulting execution of the application, and provides relevant real-time analysis results that will help developpers to improve the overall safety of robotic systems. Compared to the works presented in Tab. 1, we have developed a model-based process that generates Orocos code, with accurate WCET/WCRT evaluations based on the component behaviour models. This process (Fig. 2) settles on:

-The design of architecture models using a Domain Specific Language (see Sect. 3); -Code generation using state-of-the-art robotic middlewares (see Sect. 6); -Architecture execution, along with an accurate execution model (see Sect. 4); -A real-time analysis algorithm that computes accurate WCRTs (see Sect. 5). a first version of the modelling language has been presented in [START_REF] Gobillot | A Modeling Framework for Software Architecture Specification and Validation[END_REF]; here we present an updated version of the language with its complete grammar and concrete code snapshots used in an experiment illustrating the whole process; the real-time analysis presented in [START_REF] Gobillot | Periodic state-machine aware real-time analysis[END_REF] is further detailed in this paper; the application case has been published in [START_REF] Gobillot | Measurement-based real-time analysis of robotic software architectures[END_REF] with a focus on obtaining WCET from measures; this point is briefly described in this paper, but the application is further detailed, with code snapshots and more complete results.

Case study

The contribution presented in this paper has been applied to several case studies: a ground robot for exploration of indoor environments (Fig. 3a), a ground robot for patrolling missions to secure infrastructures (Fig. 3b), a ground robot for inspection of airport traffic lights (Fig. 3c), and a UAV performing a search-and-track mission [START_REF] Watanabe | Non-cooperative ground vehicle tracking and interception by multi-RPA collaboration[END_REF]. The architectures of the ground robots are very similar regarding the control components. In this paper we use the architecture of the Pioneer P3-DX robot used in the indoor exploration mission, as it provides interesting results that lead to the final discussions of this paper (Sect. 7.3). The Pioneer P3-DX robot is made of: (1) the mobile base with two motorized wheels to drive the robot and a passive caster wheel, (2) seven front-facing ultrasonic range finders and (3) an embedded low-level controller to drive the two motors and the ultrasonic sensors. On top of this, we added a high-level computer embedding a four core 1.83GHz processor, a laser scanner and a 3D camera. The high-level computer communicates with the proprietary low-level controller through its unique serial 9600bauds RS232 interface. In the context of our work, we configured the high-level computer to run a real-time patched Linux distribution.

The MAUVE language

As stated in the introduction, we need to catch best practices of robotics software development to build an accurate execution model of the resulting application. This is done by providing a modelling language to the developer. General purposes languages, such as AADL [START_REF] Feiler | Model-Based Engineering with AADL: An Introduction to the SAE Architecture Analysis & Design Language[END_REF], UML [START_REF] Varró | A Formal Semantics of UML Statecharts by Model Transition Systems[END_REF] or MARTE [START_REF] Selic | Modeling and Analysis of Real-Time and Embedded Systems with UML and MARTE: Developing Cyber-Physical Systems[END_REF] have been defined to model complex systems and used in several applications such that in the transportation or nuclear industry. These languages may be suited to have an abstract model of a complex robotic system [START_REF] Biggs | Modelling and Analysis of a Redundant Mobile Robot Architecture Using AADL[END_REF][START_REF] Bardaro | AADL for robotics: a general approach for system architecture modeling and code generation[END_REF], but are limited when we need for an accurate model of execution. In robotics, and more generally in cyber-physical systems, a lot of works have defined and used DSLs. Contrary to general purpose languages, these DSLs are specific to some domains, then restricting their applicability, but have the good level of abstraction to model very deeply some parts of the system. Some of the works referenced in Tab. 1 have DSLs to model component-based architectures. However, none of these DSLs allows to model accurately component behaviours and their temporal execution, which are some mandatory elements to perform accurate realtime analyses. We then decided to define a new DSL, MAUVE. A first version of this DSL has been presented in [START_REF] Gobillot | A Modeling Framework for Software Architecture Specification and Validation[END_REF]. This section presents an updated version of the model with better notations, particularly for the data ports access and parameter accessors for the codels. Moreover, we provide here the complete grammar of the MAUVE language, as it is a good way to highlight the several concepts of the language. However, note that the grammar itself is not sufficient to describe all the MAUVE model, as it also settles on complementary tools such that a type checker (to check the type of ports, components, . . . ) and some semantic analysis rules (like avoiding multiple definitions of the same element). Moreover, to present MAUVE in a concise way, we have omitted some language primitives that could be trivially defined (like strings definition for type names and element ids).

Codels declaration

Codels are declarations of functions that may be used by the components (see Listing 1). Only the function prototype is defined at the model level, the function core being implemented in a target language. The term codel, as originally proposed by [START_REF] Mallet | GenoM3: Building middlewareindependent robotic components[END_REF], stands for elementary code.

= ' i n ' | ' o u t ' | ' i n o u t '
Listing 2 declares the codel for the A * algorithm [START_REF] Hart | A Formal Basis for the Heuristic Determination of Minimum Cost Paths[END_REF]: the astar function takes as argument a start pose s, a goal pose g, a map, and the resolution of the planning graph (argument planner_resolution). It returns the path between s and g.

Component specification

A component [START_REF] Szyperski | Component Software: Beyond Object-Oriented Programming[END_REF] is a unit of composition with contractually specified interfaces and explicit context dependencies only. A software component can be deployed independently and is subject to composition. Therefore, in order to help composition and modularity, we decompose the specification of a component into a shell and a core.

Component's Shell

The shell of a component defines its interface, i.e. its inputs and outputs. We propose four types of interfaces (see Listing 3):

constants, which are static typed values associated to a shell. Constants are defined and initialized at the shell's specification. properties, which are typed component parameters, generally set at instantiation or deployment time. Properties may also have a default value.

Constants and properties can only be modified from the architecture view, whereas ports and operations are used for component to component interactions. Values of properties, as well as connections of ports and operations are not initialized at the moment of specifying a component shell. Instead, they are defined when instantiating and connecting components, at the architecture specification step. Type and parameter lists are defined similarly to argument list of Listing 1. Property expressions (not described here by lack of place) allow to write simple arithmetic instructions on integers, floats and strings. Listing 4 shows the shell specification of the Navigation component. The role of this component is on one hand to compute a path from a starting position to a goal on a map, and on the other hand to manage the execution of this path by iteratively sending the path points one after the other. Its properties are: resolution, that specifies the resolution of the map used for path planning (in meters per cell, values between 0.1 and 1, default to 0.3), and position_threshold, the threshold used to consider that the current point has been reached (in meters, values between 0 and 1, default to 0.3). The component also has three input ports map (the current map known by the robot), pose (the current pose of the robot) and goal (the goal pose) and the output port next_point (on which the path points are published iteratively).

Component's Core

The core of a component defines its behaviour and has to be associated with a shell. It is defined by a state-machine. For specific cases where the state-machine only contains one state, the developer can just define the update function instead of the statemachine element.

The core of a component is made of several elements (see Listing 5):

variables: internal elements storing data used in the MAUVE expression language; provided operations: have been declared in the shell and must be defined here; handlers: allowing to call required operations; programs: five different programs can be defined to execute some computations:

- Programs are defined using a tiny expression language that allows to evaluate conditions (if/then/else), assign values to variables, get status of port (no_data, new_data, old_data), get status (failure, success, not_ready)) of handlers (remotely called required operations), call codels, read and write data on ports, call remote operations (send, collect), and use classical structures (blocks, parentheses).

Listing 6 shows the specification of the P3DX component's core and programs. The connection with the robot is initialized in configure. Data exchange with the robot is started in start. In update, data from the robot are published to output ports, and in case of a new command received in the input port command, it is sent to the robot. The robot is stopped (velocity set to 0) in stop. Finally, the connection is shutdown in cleanup.

State machines

The behaviour of each component is defined by a state machine. In case of a trivial one-state state-machine, the developer can directly define the update program as shown in Listing 6. A state-machine consists of a set of states linked by a set of transitions. MAUVE state-machine structure (see Listing 7) is very close to the UML/StateChart definition, also used in the Orocos middleware [START_REF] Klotzbücher | Coordinating Robotic Tasks and Systems with rFSM Statecharts[END_REF].

Each state s i contains up to four methods: entry i , run i , handle i and exit i . The entry i method contains code executed whenever the state-machine enters state s i . The run i method contains the core of the state, executed each time the state-machine is in state s i . The handle i method is executed each time the state-machine stays in state s i , after run i has been executed. The exit i method is executed when leaving state s i . Transitions are guarded and may contain a program executed when triggered. Listing 8 describes the specification of state Navigating of the Navigation component. In this state, the component executes the computed path by sending successive goals. The architecture language (see Listing 9) allows to import an existing (partial) architecture, instantiate components, connect output ports to input ports, possibly defining the size of the buffer when the connection uses a circular buffer, connect provided operations to required operations, and set property and constant initial values. Listing 10 shows the specification the architecture drawn in Fig. 4. This architecture is made of three main components [START_REF] Gobillot | A Component-Based Navigation-Guidance-Control Design Pattern for Mobile Robots[END_REF] designed to compute a path to follow (navigation), to avoid obstacles (guidance), and to control the robot speed (control). Other components provide sensor information (hokuyo), robot's status Listing 9: Part of the MAUVE grammar for architectures.

1 <a r c h i t e c t u r e > ::= ' a r c h i t e c t u r e ' <i d > ' { ' <a r c h if e a t u r e > * ' } ' 2 <a r c h if e a t u r e > ::= ' i m p o r t ' <a r c h i t e c t u r e >

Software architecture deployment

The MAUVE language has allowed to model and develop on one hand the basic components of our system, and on the other hand, architectures that assemble components to build applications. The next step is to deploy and execute these architectures on the final target. In this section, we present first the execution model of the components, and we then present how we can define the execution model using the MAUVE DSL deployment specification. As the task model will also need some information about the WCETs, we present some methods used to estimate WCET.

Task model

All the components of the software architecture are mapped onto operating system tasks. The components are designed to be temporally independent, and we then allocate each component to a specific task.

Property 1 When deploying a component, it is associated with a unique task.

Moreover the components exchange data through either asynchronous data ports and operation calls. These protocols allow a component to receive a data from another component without waiting the data to be ready.

Property 2 Data exchange between components are non-blocking.

These properties are ensured in the implementation by the Orocos middleware. Orocos first allows to execute components in threads scheduled by the OS real-time scheduler. Orocos moreover implements data sharing between components using a lock-free mechanism [START_REF] Herlihy | Wait-free Synchronization[END_REF] that guarantees non blocking read/write in bounded time, and is not subject to priority inversions.

Definition 1 A component comp i is executed by a task τ i defined by four elements:

the period T i defines the execution frequency; the deadline D i sets the moment when the task has to end its execution; the priority P i is managed by the scheduler to decide which task to execute; the behaviour SM i is defined by the internal structure of the task state-machine.

The following hypothesis is assumed true for the rest of the development.

Hypothesis 1 Deadlines are lesser or equal to the periods:

∀i, D i ≤ T i (1)
The temporal behaviour of a task depends on the activities of the tasks and on the state-machine's behaviour. Definition 2 A state-machine SM is a tuple (P, S, E, entry, exit, handle, run, guard, exec, δ) where:

-P is a set of programs; S is a set of states; -E ⊂ S 2 is a set of transitions where each transition e is a pair (src(e), tgt(e)); entry : S → P associates an entry program to a state; exit : S → P associates an exit program to a state; run : S → P associates a run program to a state; handle : S → P associates an handle program to a state; guard : E → { , ⊥} associates a guard expression to a transition; guard(e) evaluates to true ( ) when the transition is enabled, and false (⊥) when the transition is disabled; exec : E → P associates a program to a transition; δ : P → R associates an execution time to each program.

At each period of execution, two execution sequences are possible depending on the transitions that are enabled. Let's assume that current state is s i , then: if no transition is triggered (2), then the component stays in state s i , and executes run(s i ) and handle(s i ) (Fig. 5a);

∀e ∈ E, (src(e) = s i ) ⇒ (guard(e) = ⊥)

if a transition e is triggered (3) then the component goes from s i to s j = tgt(e), and executes run(s i ), exit(s i ), exec(e) and entry(s j ) (Fig. 5b).

(src(e) = s i ) ∧ (guard(e) = ) (3)

t period s i s i (s i , s i ) run(s i ) handle(s i ) (a)

Estimating Worst-Case Execution Times

The task model presented in Def. 2 needs the timing function δ in order to perform the real-time analysis presented in Sect. 5. However, this execution time is generally not deterministic, and the WCET must then be estimated [START_REF] Wilhelm | The worst-case execution-time problem-overview of methods and survey of tools[END_REF]. Static analysis [START_REF] Ferdinand | Worst Case Execution Time Prediction by Static Program Analysis[END_REF] takes the control flow graph and a model of the hardware to compute the worst number of instructions. Static analysis methods have some limitations: (1) they need a model of each instruction, which is inappropriate when using IO functions for instance and (2) they need an accurate model of the hardware, meaning that the approach efficiency is processor-dependant. On the contrary, Measurement-Based Probabilistic Timing Analysis (MBPTA) [START_REF] Hansen | Statistical-Based WCET Estimation and Validation[END_REF][START_REF] Cucu-Grosjean | Measurement-based probabilistic timing analysis for multi-path programs[END_REF] uses measurements of execution times, and infer the probabilistic WCET (pWCET) estimation using Extreme Value Theory (EVT). Application of these methods is discussed in Sect. 7.

Real-Time analysis

To ensure the schedulability of the task system described by the MAUVE DSL, we provide a real-time analysis process checking if the component's WCRTs are lower than their deadlines. The real-time analysis problem has been tackled many times using more and more complex approaches. The first ones were based on the Liu and Layland model [START_REF] Liu | Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment Scheduling Algorithms for Multiprogramming[END_REF], using fixed priority preemptive tasks, later extended to dynamic priority tasks such as EDF [START_REF] Spuri | Analysis of Deadline Scheduled Real-Time Systems[END_REF]. In order to cope with increasing application complexity, the task models are more and more refined: the Multiframe model [START_REF] Mok | A multiframe model for real-time tasks[END_REF][START_REF] Noel Tchidjo Moyo | On schedulability analysis of non-cyclic generalized multiframe tasks[END_REF], the Digraph Real-Time model [START_REF] Stigge | The digraph real-time task model[END_REF] or the Digraph Synchronous Finite State-Machine model [START_REF] Zeng | Schedulability Analysis of Periodic Tasks Implementing Synchronous Finite State Machines[END_REF] further increase the complexity and the precision of the analyses using graph based algorithms to compute WCRTs. In this section, we describe a computationally efficient and precise WCRT algorithm that is applicable to our specific task model. The proposed process (see Fig. 6) needs the WCETs of the components and of their internal codels (see Sect. 4.3). From these components we extract Periodic State-Machines (PSM) which represents the component's timed behaviour (Sect. 5.1). The WCRTs are then computed from the PSMs in three steps: the first one computes traces from the PSMs, a trace being a timeline of one possible PSM execution. These traces are used to deduce an upper bound of all the possible PSM paths, then these upper bounds allow the computation of the WCRTs (Sect. 5.2). In order to analyse the components behaviour, we model them as Periodic State-Machines (PSM), with the same temporal behaviour as the task it models. Definition 3 Each component is associated with a Periodic State-Machine P SM defined by as a set of states S (similar to the states of the state-machine SM , see Def. 1) and a set of transitions Σ such that:

Σ = E ∪ {(s, s) | s ∈ S} (4)
The set of transitions Σ contains all the original transitions of the state-machine (E) plus all the loops over states of S.

Property 3 The Periodic State-Machine fires a transition at every execution period.

Property 4 A Periodic State-Machine is strongly connected: every state can be reached from any state through a sequence of transitions.

∀s i , s j ∈ S, ∃σ 1 . . . σn ∈ Σ | s i σ 1 --→ . . . σn --→ s j ( 5
)
This assumption is useful, because it avoids considering that some dead states exist in the task behaviour, and it is a needed assumption for the WCRT computation (see Sect. 5.2). Moreover, this assumption is a good practice that should be enforced when developing components: it allows to be able to put the task again in its initial state at execution when a faulty behaviour occurs.

Definition 4 A timing function δ is defined over the PSM transitions, such that:

∀σ ∈ Σ, σ = (s i , s j ), δ(σ) = δ(run(s i )) + δ(exit(s i ))+ δ(entry(s j )) + δ(exec(σ)) if s i = s j δ(run(s i )) + δ(handle(s i )) if s i = s j (6)
where the execution time of each program is defined in Def. 2.

WCRT computation

In order to compute the WCRTs (i.e., the worst time between task release and the end of its execution), we first use the PSMs structure to extract traces representing all the possible execution sequences of the state-machines.

Traces

We define a trace T as an ordered sequence of transitions:

T = σ 1 , . . . , σ N ∈ Σ N (7)
We also define operators to access the i th transition of a trace, and the number of transitions:

∀i ∈ 1..N , T [i] = σ 1 , . . . , σ i , . . . , σ N [i] = σ i (8) |T | = | σ 1 , . . . , σ N | = N (9)
The request bound function (rbf , [START_REF] Baruah | Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor[END_REF]) is the maximum processor request over a time interval. The tasks are executed periodically then the rbf is a piecewise-constant and increasing function. The rbf of a trace T at time t is noted rbf (T , t) and is defined as:

rbf (T , t) = t T i=0 δ (T [i + 1]) (10)
with δ (σ) the time taken by transition σ (see Def. 4). We then define the relation ≤ on traces by comparing the rbf of the traces:

T ≤ T ⇔ ∀t, rbf (T , t) ≤ rbf T , t (11)
The next operator represents the set of traces that follows a given trace:

next (T ) = { T , σ | σ ∈ Σ ∧ tgt (T [|T |]) = src (σ)} (12)

Traces upper bound

WCRT of tasks relies on the computation of an upper bound of all the feasible traces of a task with respect to their rbf. According to relation [START_REF] Henriksson | On Dynamic Real-Time Scheduling of Model Predictive Controllers[END_REF], we only need to reason on the maximal feasible traces: two traces arriving at the same state will be extended the same way [START_REF] Mark H Klein | A practitioner's handbook for real-time analysis[END_REF]. Therefore we only need to keep the greatest trace among the set of traces that terminate in the same state. We then compute the set of traces that are maximal using the following recursive equations:

V 1 = { σ , σ ∈ T | ∀σ ∈ T, σ = σ ∧ (tgt(σ) = tgt(σ ) =⇒ σ ≥ σ )} (13)
V n+1 = { T , σ , T ∈ V n , σ ∈ T | ∀T ∈ V n , ∀σ ∈ T, T = T ∧ T , σ ∈ next(T ) ∧ T , σ ∈ next(T ) ∧ (tgt(σ) = tgt(σ ) =⇒ T , σ ≥ T , σ )} ( 14
)
From these trace set, we can extract T + , an upper bound of all the feasible traces of the task according to (11) using the following recursive equations:

T + 1 = σ | σ = argmax σ i ∈Σ δ (σ i ) (15)
T + n+1 = T + n , T [n + 1] | T = argmax T ∈V n+1 rbf T , (n + 1) × T ( 16
)
The construction of trace T + does not ensure that the trace is feasible, i.e. that two consecutive transitions of the trace are effectively consecutive transitions of the PSM. The timing function δ has therefore no meaning on T + and the computation of the rbf on T + must use a new function δ + recursively defined while building T + by:

δ + T + [1] = δ(σ) ( 17
)
δ + T + [n + 1] = rbf (T , n + 1) - n j=1 δ + T + [j] (18)
with σ and T respectively defined in [START_REF] Sha | Priority inheritance protocols: An approach to real-time synchronization[END_REF] and [START_REF] Chen | Dynamic priority ceilings: A concurrency control protocol for real-time systems[END_REF].

WCRT

In order to compute the WCRT, we adapted the usual recursive procedure proposed by [START_REF] Liu | Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment Scheduling Algorithms for Multiprogramming[END_REF]. Instead of using the classical task's execution time, we use the upper bound trace's values: at each iteration of the recursive procedure, we use the next iteration of the upper bound trace.

R 0 i = rbf T + i , 0 (19)
R n+1 i = j∈hp(i) rbf T + j , R n i + R 0 i ( 20
)
In equation ( 20), the sum is made over all traces T + j that have a greater priority than the i-th component (i.e., j ∈ hp(i)). Two conditions stop this recursive loop:

(1) whenever two consecutive iterations have the same R i value, (2) whenever R n+1 i reaches the task's deadline D i . In the latter the component is not schedulable. Finally, if all the WCRT are lesser than the deadlines (i.e., ∀i, R i ≤ D i ), the complete software architecture is schedulable.

Code generation

In order to eventually execute the architecture on the target platform, we have set up a code generation process (see Fig. 7 Fig. 7: Code generation process components and architectures specified using the MAUVE DSL (see Sect. 3). The code generator then translates this model into source files and PSM models of the components (see Sect. 5.1) in order to apply the analysis process. The source files are completed with the definition of codels, that can either by directly implemented in the generated files, or linked with a third-party library. The resulting software architecture uses the ROS ecosystem for compiling the software, and launch files to help the deployment. The software architecture is only made of Orocos components: Orocos manages the real-time execution and data exchange between components. The generated sources also embed a tracing library, based on LTTng [START_REF] Desnoyers | The LTTng tracer: A Low Impact Performance and Behavior Monitoring for GNU/Linux[END_REF], that allows to produce tracepoints at runtime, including clock values and relevant data about the execution of components (start and end of states and programs, codel calls).

Results and discussion

The methodology presented in this paper has been fully applied to the application presented in Sect. 2. The deployment specification of the architecture of Fig. 4 is presented in Tab. 2. The period of the p3dx_driver is based on the period of the communication with the low-level processor embedded on the robot. Most of the periods are then set to 100 ms. The navigation and gmapping components are executed with a period of 1 s, as they may be quite time consuming. Moreover, the gmapping component is isolated on the second CPU core. The exploration component is set non real-time: it is executed sporadically when a new exploration point has to be defined. 1

pWCET estimations

We have first applied the pWCET estimation method based on measurements to obtain WCETs of component functions. The MBPTA approach (see Sect. 4.3) uses measures of execution times of the codels, independently of the deployment that is executed. It is then possible to perform independent measurements from several deployments and executions:

an automatic control deployment, in which we deployed the p3dx_driver, control, hokuyo, switch and guidance components; we manually sent some guidance goals to the guidance component in a good variability of input conditions such as a densely packed storage area with complex shapes, tight straight corridors and a wide open room with and without moving objects; a mapping deployment, in which we deployed the necessary components to manually control the robot from user command, while building a map; a navigation deployment, in which we only deployed the navigation component; the component has been fed with a static global map; we randomly sent several goals to the navigation component without moving the robot.

The exploration component has not been used: it is not executed in real-time, and then is not considered in the real-time analysis. The p3dx_driver state machine has only one state (Listing 6). This state executes a set of codels, for which we have to estimate the WCET. Figure 8a shows some measurements of the execution time of the aria_loop codel, on a small part of the gathered measures. may happen during an actual run of the system. Let us consider that we would like to provide a significance level of 10 -8 . Some possible design choices may be to:

do nothing: gmapping and navigation are the less priority components on their respective core, and in the case where they would pass their deadline, they will have no impact on the other components; change the affinity of the navigation component: by moving it to a core where it will be the only real-time component, it may be proved to be schedulable, which may be mandatory if its functions are critical for the safety of the system; let some components run in background mode: they will not be real-time any more, meaning that they may pass their deadline, but also that they may run faster than their period when the CPU is under loaded; it may lead to more efficient applications but can be done only for non safety critical components.

In the context of safety critical applications, it is mandatory to perform such real-time analyses to ensure that the system cannot produce unsafe behaviours. More importantly our work allows the designer to apprehend the real-time behaviour of its application and take it into account in the design phase. In the case of the P3-DX robot, violating real-time constraints may for instance lead to decreasing the localization quality (in case the map computed by the gmapping component is distorded), or to possible collisions in case the guidance or switch components are delayed.

Conclusion

Safety critical applications demand for sound development processes and for analyses that help proving that the system cannot produce unsafe behaviours. Such analyses must encompass both the functionnal properties, i.e., verifying that the algorithms provide the good results, and the non-functionnal properties, among which verifying that the algorithms execute on time. In this paper, we have focused on verifying such real-time constraints as they are necessary to guarantee a correct and safe behavior of the whole system.

In this paper, we have presented a complete toolchain for the design and analysis of component-based real-time software architectures. This toolchain settles on the MAUVE DSL to model components, architectures and deployments. The toolchain comes with code generation towards Orocos real-time tasks. The generated code moreover embeds tracepoints to provide timed traces of execution runs. The real-time analysis takes benefit of the behaviour of components to compute a WCRT less pessimistic than classical approaches that consider components as a unique function.

We have illustrated the whole process on the design of a software architecture for a ground robot performing an exploration mission. We have first shown the architecture design aspects, with code snapshots of the MAUVE models of components and architectures. We have then discussed and illustrated how timed traces can be used to estimate the WCET of the elementary functions called by each component. Finally, we have run the complete real-time analysis process, and discussed how the results can led either to prove the real-time safety of critical parts of the architecture, and help the designer make some conception choices about its deployment.

Future works are twofold. Regarding the real-time analysis, it would be interesting to avoid selecting a significance level before computing the WCRT, and we are working on how to directly propagate the pWCET continuous law inside the WCRT computation in order to compute a pWCRT. It would lead to even less pessimistic results as some probabilistic dependency between components and/or states could be taken into account.

Secondly, the WCRT computation uses an execution model that is over pessimistic because we suppose that every task clock are not synchronized; removing this assumption would lead to less complexity in the computation of traces upper bounds and WCRT; This behaviour is due to some limitations of the Orocos middleware regarding real-time synchronisation, and we are considering to make the middleware evolve to fix this behaviour [START_REF] Doose | MAUVE Runtime: a componentbased middleware to reconfigure software architectures in real-time[END_REF].

Fig. 1 :

 1 Fig. 1: Task model illustration: k-th execution of i-th task τ i .

Fig. 2 :

 2 Fig. 2: Sketch of the proposed process.

Fig. 3 :

 3 Fig. 3: Case studies

Listing 1 : 3 |

 13 Part of the MAUVE grammar defining codels.1 <c o d e l > ::= ' c o d e l ' <i d > ' ( ' <a r gl i s t >? ' ) ' ' : ' <type> 2 <a r gl i s t > ::= <a r ga c c e s s >? <i d > ' : ' <type> <a r ga c c e s s >? <i d > ' : ' <type> ' , ' <a r gl i s t > 4 <a r ga c c e s s > ::

Listing 2 :

 2 Declaration of a codel for the A * algorithm 1 codel a s t a r ( in s : PoseStamped , in g : PoseStamped , in map : OccupancyGrid , in p l a n n e r _ r e s o l u t i o n : double ) : Path

Listing 4 :

 4 Shell of the Navigation component1 s h e l l N a v i g a t i o n S h e l l { 2 property r e s o l u t i o n : double [ 0 . 1 ; 1 ] = 0 . 3 3 property p o s i t i o n _ t h r e s h o l d : double [ 0 ; 1 ] = 0 . 3 4 input port map : OccupancyGrid 5 input port p o s e : PoseStamped 6 input port g o a l : PoseStamped 7 output port n e x t : PoseStamped 8 }

Listing 5 : 3 | 4 | 6 | 7 |

 53467 Part of the MAUVE grammar defining cores. 1 <c o r e > ::= ' c o r e ' <i d > ' ( ' <s h e l lt > ' ) ' ' : ' ' { ' <c-ft> * <c-bh> * ' } ' 2 <c-ft> ::= ' v a r ' <i d > ' : ' <type> ( ' = ' <expr >)? ( ' ; ' ) ? ' h a n d l e r ' <i d > ' : ' <type> ' p r o v i d e ' <i d > ' ( ' <p a r a ml i s t >? ' ) ' ' = ' <program> 5 <c-bh> ::= ' c o n f i g u r e ' ' = ' <program> | ' c l e a n u p ' ' = ' <program> ' s t a r t ' ' = ' <program> | ' s t o p ' ' = ' <program> ' u p d a t e ' ' = ' <program> | <s t a t e m a c h i n e >

Listing 6 :

 6 Core of the P3DX Driver component core P3DXCore ( P3DXShell ) { var cmd : TwistStamped ; var v e l : TwistStamped ; var p : PoseStamped ; var r o b o t : ArRobotPtr ; var c o n n e c t o r : ArRobotConnectorPtr ; configure = { a r i a _ i n i t ( r o b o t , c o n n e c t o r , d e v i c e , b a u d r a t e ) ; return a r i a _ c o n n e c t ( r o b o t , c o n n e c t o r ) ; } s t a r t = { return a r i a _ s t a r t ( r o b o t , sonarOn , motorOn ) ; } update = { i f ( read ( command , cmd ) == new_data) then { aria_command ( r o b o t , cmd ) ; } e l s e {} a r i a _ l o o p ( r o b o t ) ; p = a r i a _ p o s e ( r o b o t , odometry_frame ) ; write ( pose , p ) ; v e l = a r i a _ v e l o c i t y ( r o b o t , robot_frame ) ; write ( v e l o c i t y , v e l ) ; } stop = { a r i a _ s t o p ( r o b o t , true , true ) ; } cleanup = { a r i a _ d i s c o n n e c t ( r o b o t ) ; } } Listing 7: Part of the MAUVE grammar for state machines.

Listing 8 :} 3 . 3

 833 <s t a t e m a c h i n e > ::= ' s t a t e m a c h i n e ' ' { ' <sm-feature> * ' } ' <sm-feature> ::= ' v a r ' <i d > ' : ' <type> ( ' = ' <expr >)? ( ' ; ' ) ? | <s t a t e > <s t a t e > ::= ( ' i n i t i a l ' ) ? ' s t a t e ' <i d > ' { ' <st-method> * <t r a n s > * ' } ' <st-method> ::= ' e n t r y ' ' = ' <program> | ' e x i t ' ' = ' <program>| ' r u n ' ' = ' <program> | ' h a n d l e ' ' = ' <program> <t r a n s > ::= ' t r a n s i t i o n ' <i d > ( ' i f ' <expr >)? ' t o ' <i d > (<program >)? StateNavigating of the Navigation component s t a t e N a v i g a t i n g { entry = { c u r r e n t _ g o a l = get Pat hEl eme nt ( path_ , ne x t _ i n d e x ) ; write ( next , c u r r e n t _ g o a l ) ; } run = { n e w _ r e c e i v e d = ( read ( g o a l , g ) == new_data) ; read ( pose , p ) ; p r e v _ i n d e x = ne x t _ i n d e x ; } e x i t = { ne x t _ i n d e x = n e x t _ i n d e x + 1 ; } t r a n s i t i o n n e w _ g o a l _ r e c e i v e d i f ( n e w _ r e c e i v e d ) to P l a n n i n g t r a n s i t i o n path_done i f ( ( d i s t ( p , c u r r e n t _ g o a l ) < p o s i t i o n _ t h r e s h o l d ) && ( ne x t _ i n d e x == l a s t _ i n d e x ) ) to A r r i v e d t r a n s i t i o n next_waypoint i f ( d i s t ( p , c u r r e n t _ g o a l ) < p o s i t i o n _ t h r e s h o l d ) to N a v i g a t i n g Architecture model

3 | 4 | 6 | 7 | 8 | 4 instance hokuyo : Hokuyo 5 instance p 3 Fig. 4 :

 346784534 Fig. 4: The component-based exploration architecture

Fig. 5 : 3 | 5 ' 6 '

 5356 Fig. 5: Execution model of state machines

Fig. 6 :

 6 Fig. 6: Real-time analysis process

Fig. 8 :

 8 Fig. 8: MBPTA applied to the aria_loop codel.

  configure: this program is called to initialize the component; start: this program is used to start the component execution. It can only be called if the configure step has executed successfully; update/statemachine: this program is executed when the component is running. It can only be called if the component has been started; stop: this program is used to stop the execution of the component; cleanup: this program is called to clean the component.

  ). It takes as input the MAUVE models of

			LTTng tracing
	MAUVE models *.mal	Code generator	Generated sources	Executable binaries OROCOS+ROS
		PSM Structure	Manually written codels

Table 2 :

 2 Deployment specification

	component	period (ms)	deadline (ms)	priority	CPU
	p3dx_driver	100	100	10	1
	hokuyo	100	100	9	1
	switch	100	100	8	1
	pose	100	100	7	1
	guidance	100	100	6	1
	control	100	100	5	1
	teleop	100	100	4	1
	navigation	1000	1000	2	1
	gmapping	1000	1000	3	2
	exploration	-	-	background	-

a non real-time component is not scheduled by the real-time scheduler, and consequently does not disturb the behaviour of real-time components.

This codel is responsible of making the actual communication with the robot controller through a serial connection. Therefore, the communication time with the hardware is taken into account into the measurements. The pWCET estimation of the aria_loop codel is shown in Fig. 8b. From this pWCET estimation, the WCET of the p3dx_driver component is estimated according to several possible significance thresholds. Figure 9 shows the PSM for a significance level of 10 -7 .

Update update [0..17] Fig. 9: PSM of the p3dx_driver component for a significance level of 10 -7

Schedulability results

From the MAUVE models and the estimated WCETs, we have built the PSM models for all the components and all the desired significance levels.

Evaluating the impact of pWCET threshold

Table 3 shows the resulting WCRT for the several components according to the selected significance level. At 10 -5 , the navigation component cannot be proved to be schedulable. At 10 -9 , only the p3dx_driver component is schedulable. As the hokuyo WCRT overshoots its deadline, it is not possible to compute a WCRT for the less priority components. The gmapping component runs on a separate CPU core.

The component is schedulable down to a significance of 10 -7 .

Evaluating the impact of state-machines

The method we have presented in this paper takes explicitly state-machines into account when computing the WCRT of components using an upper bound of traces T + (let's note this WCRT R + ). We have compared with the computation of the WCRT using the classical method, i.e. by considering that each task has only one WCET. It corresponds to defining for each component a PSM with only one state (like in Fig. 9), whose WCET would be the maximum of the WCET values of the original PSM transitions. Let's note this WCRT R * . The R * for the components running on CPU first core are shown in Tab. 4. Regarding the schedulability of components, the only noticeable situation is for the navigation component at a level of 10 -4 : it can be proved schedulable using R + but not with R * . The gain obtained with our method can be computed as:

The value of Γ for the navigation component (i.e. for the whole architecture as the navigation is the less priority component) is 0.077 for a significance level of 10 -4 (meaning that our method is around 7% less pessimistic), and up to 0.957 for a level of 10 -8 (meaning that our method is about 95% less pessimistic). The gain is clearly greater when considering components with state machines that have quite different WCET values, like for the navigation component, where the WCET of transitions is of 297 ms when executing the astar codel, while other transitions have a WCET lower than 3 ms.

Discussion

The results of Tab. 3 lead to the following conclusions:

the whole architecture is schedulable if a significance level of 10 -4 is acceptable; if we need a lower level, down to 10 -7 , all the architecture is proved to be schedulable, but the navigation component. at a significance level of 10 -8 , all the architecture is proved to be schedulable, but the navigation and gmapping components.

In the other cases, nothing can be deduced regarding the schedulability: we compute an upper bound of the WCRT, and then we cannot conclude that the components are actually schedulable or not.

Besides the direct conclusion regarding schedulability, these results can help designing the architecture. They indeed emphasize some real-time behaviours that


Judicaelle Andeme Edzang

Zhongrui Chen

Hassib Audi

Gabriel Canard

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Transamination at the crossroad of the one-pot synthesis of Nsubstituted quinonediimines and C-substituted benzobisimidazoles Judicaelle Andeme Edzang, Zhongrui Chen, Hassib Audi, Gabriel Canard and Olivier Siri* Centre Interdisciplinaire de Nanoscience de Marseille (CINaM), UMR 7325 CNRS, Aix-Marseille Université, Campus de Luminy, case 913 13288 Marseille cedex 09 (France) ABSTRACT: A green and very efficient synthesis of N-substituted benzoquinonediimines or C-substituted benzo-bis(imidazole) derivatives is described under similar conditions. The different reaction pathway is only controlled by the nature of the primary amines which tunes the reactivity of the intermediates.

Quinoid compounds are attracting considerable attention because of their specific properties and their numerous applications in a wide spectrum of science. [START_REF] Pataï | The Chemistry of the Quinonoid Compounds[END_REF][START_REF] Hettegger | [END_REF][3][4] More specifically, benzoquinonediimines (BQI) of type 1 (R = alkyl or aryl) have been extensively investigated because of their remarkable fundamental and applied aspects. The former results from the unique distribution of their overall 12-π electrons system which is best described as constituted by two 6-π electrons subunits chemically connected through two C-C single bonds, but electronically not conjugated (i. e. the so-called "coupling principle"), 5 giving rise to fascinating optical properties. 6 The applied aspects correspond to the use of BQI of type 1 as reagents in three main axis: (i) in organic chemistry as precursors of benzobisimidazole derivatives, [7][8][9] (ii) in analytical chemistry as unusual proton sensors, 6,10 and (iii) in coordination chemistry as new ligands for the preparation of complexes that recently revealed unprecedented properties for many technological sectors, [11][12][13][14][15][16][17] highlighting the crucial role of the metal center but also and importantly of the N-substituents.

As such, different synthetic strategies giving access to N-substituted BQI 1 have been reported. In 1875, Kimish reported the first preparation by self-condensation of aniline affording 1 with R = phenyl exclusively (i.e. azophenine, route a, Scheme 1). 18 In order to extend the nature of the N-substituents, we described in 2000 a stepwise procedure from tetraaminobenzene 24HCl which required the need for highly reactive acid chlorides R'C(O)Cl and the use of metallic and strong reducing agents. 6,19 In addition, this approach affords exclusively N-methylenic molecules 1 (N-CH 2 -R'), limiting the tuning of R (route b, Scheme 1). To overcome this limitation, Harlan et al. reported in 2004 an efficient alternative based on the Pd-catalyzed aryl amination of the 1,2,4,5-tetrabromobenzene (Buchwald-Hartwig coupling reaction, see route c, Scheme 1). 20,21 This route allows the use of primary amines with highly versatile R groups, but requires however Pd(II) catalyst which is not environmentally friendly. Finally, Harvey et al. described more recently (2014) another metal-based strategy from benzoquinone and a primary amine catalyzed by TiCl 4 . 22 Scheme 1. Syntheses of 1 (limiting factors on the narrows) Therefore, elaborating a new synthesis of molecules 1 that would be simultaneously versatile (to overcome route a, b and d) and metal-free (to overcome routes b, c and d) is objectively of major importance in quinoid chemistry. During the course of this work,

Br Br Br Br N N HN NH R R R R route c route b 1 O O NH 2 NH 2 H 2 N H 2 N NH 2 route a route d R'C(O)Cl self-condensation Ti(IV) Pd(II)
we developed -by serendipity -a new preparation of C-substituted benzobisimidazoles 3 which have recently attracted major interests in numerous applications ranging from photonic 8,9,23 and sensing [24][25][26][27] to coordination chemistry 28,29 and materials science. 30 Molecules 3 have been prepared previously by using three different strategies that revealed drawbacks such as the need of a metal center 31 and/or of an electrophile of type R'C(O)X (X = H or Cl) 8,9,[23][24][25][26][27] that limits the nature of R'.

Herein, we report a new and efficient metal-free preparation of N-substituted BQI 1 in MeOH for which the N-alkyl substituents (i.e. the properties) can be easily varied by using a transamination reaction on a key intermediate A1. When the same reaction was conducted with primary amines of type R'-CH 2 -NH 2 (R' = aryl), the formation of unexpected benzobisimidazoles 3 could be observed in good yields.

24HCl reacted with a large excess of various aliphatic primary amines RNH 2 in MeOH at room temperature under air to form a precipitate that could be isolated by filtration affording BQI 1a-j in 12-88% yields depending on the nature of R (Scheme 2, route 1). Their 1 H NMR spectra showed in solution a structure of high symmetry in agreement with a fast intramolecular double proton transfer involving two degenerate tautomers (See Supporting Information SI). 6,32 A single crystal X-ray analysis of new 1c confirmed the presence of four alkyl groups and established its p-benzoquinonediimine form (Fig. 1). Examination of the bond distances within the N(1)-C(2)-C(1)-C(3)-N(2) moiety of 1c reveals a localized pi system and a C(2)-C(3) distance of 1.502(4) Å corresponding to a single bond as already observed for this class of 12 electrons quinones. 6 The one-pot formation of the BQI 1a-j can be explained by: i) deprotonation of 24HCl in the presence of amines RNH 2 generating RNH 3 + , ii) air oxidation of 2 to afford intermediate 4 which being more basic than RNH 2 can deprotonate in turn RNH 3 + and form a monocation A1 that underwent iii) a transamination reaction by nucleophilic attack of RNH 2 to give the target compounds of type 1. In order to demonstrate the key role of A1, the synthesis of BQI 1a-j was also carried out directly from 4 33 in presence of acid HCl, generating in situ the monoprotonated species A1 for which the positive charge is shared between the lower (form A2) and upper (form A3) parts of the molecule (i.e. average structure (A1) in solution resulting from the two tautomers A2 and A3 in equilibrium in solution). 6 Interestingly, the reaction from 4 does not proceed in absence of acid supporting the crucial role of the iminium functions in A1 (Scheme 2). This behaviour parallels the case of zwitterionic quinoneimines for which transamination reaction occurs on the positively charged subunit. 34,35 Reaction with bulky primary amines (for which the amino function is attached to a secondary carbon) could also proceed to give 1e, 1h and 1j. Futhermore, this efficient synthesis allows the preparation of BQI 1 with interesting functionalities such as OH (1e and 1f) or a C=C double bond (1h) that might be a precursor of choice for polymerization processes. At this stage, three additionnal remarks can be made: i) depending on the nature of the primary amine (i.e. its acido-basic character), transmination reactions on the diprotonated species of 4 can not be excluded, ii) in contrast to the related amino p-quinones, 36 partly transaminated compounds could not be isolated owing the need of primary amine RNH 2 in excess and the difficult purification of the mixture (only tetra-N-substituted QDIs precipated in solution), and iii) the use of aromatic primary amines did not succeed even under high temperatures and longer time reactions probably due to a weaker nucleophilic character of the amine precursors.

3 N H N N N H R' R' C(1) C(2) C(3) N(1) N(2) C(3)
Scheme 2. Syntheses of 1 and 3: *not isolated Remarkably, when the same reaction was carried out under similar conditions with primary amines of type R'CH 2 NH 2 (R' = aryl instead of alkyl group), we now observed the unexpected formation of fluororescent benzobisimidazoles 3a-d in 40-89% yields (Scheme 2, route 2). These latters could be fully characterized (see SI) including by X-ray diffraction for 3a which showed a anti NH configuration (Fig. 2). This observation contrasts with the syn NH isomer of 3a which was previously determinated resulting from a different packing in the solid state. The formation of compounds 3a-d proceeds probably also by transmination reaction from intermediate A leading to C which would be then rearranged into D because of the presence of the aryl group that stabilizes the intermediate by conjugation (Scheme 3). D would then be oxidized into E that underwent a similar rearrangement providing intermediates of type 6 that could be isolated in the case of 6d (see SI).

: R = R-NH 2 R-NH 3 R-NH 3 R-NH 2 [Ox] 4HCl . R-NH 2 NH 4 R'-CH 2 -NH 2 NH 2 H 2 N N N R' R' [Ox]
H N H N N H N H R' R' B (not isolated) route 2 H N N H H N N H A1 (not isolated) 1/2 1/2 H H NH H 2 N H 2 N NH 2 A3 (not isolated) H-transfer 12 -88% 40 -89% N H N N N H R' R' N(1) N(2) C(1) C(2) C (8)
C( 9)

C(10)
When 24HCl was reacted simultaneously with equimolar we observed the formation of a large mixture of pro reaction rates between the two primary amines.

Scheme

To the best of our knowledge, the isolation of this class of compounds ( synthesis as 1,3-diaminobenzene precursors (only one exemple alcohol gives intermediates B which are readely oxidized under air to afford the C The 1 H NMR spectrum of 6d showed the presence of two characteristic resonances at 5.66 and 8.72 ppm corresponding to the amine (NH 2 ) and imine (H-C=N) protons, respectively. Intramolecular cyclization of (Fig. 3) and emission (Fig. S17, see SI) spectroscopy which clearly demonstrated (rt). It is noteworthy that this conversion is much faster in presence of water or acid. In conclusion, we described a new synthesis of tw tetraaminobenzene 2. 1) N-substituted BQI A1. Unlike all the previous routes, our approach is simultaneously versatile and environmentally friendly because it allows the introduction of new functionalities, hitherto unknown, and it proceeds one 3a-d were also obtained in good yields by using primary amines of type R'CH the reactivity (route 1 vs route 2). The versatility and simplicity of these "green" approaches pave the way for new perspectives in quinoid chemistry and photonic (benzobisimidazole 4HCl was reacted simultaneously with equimolar quantities of methylamine and benzylamine under similar conditions, mixture of products that could not be separated. This observation amines.

ASSOCIATED CONTENT

Scheme 3. Mechanism for the formation of intermediates 6

To the best of our knowledge, the isolation of this class of compounds ( 6) is very seldom reported despite its potential in diaminobenzene precursors (only one exemple reported in the literature). 37 Intramolecular cyclization of which are readely oxidized under air to afford the C-substituted benzobisimidazoles showed the presence of two characteristic resonances at 5.66 and 8.72 ppm corresponding to the C=N) protons, respectively. Intramolecular cyclization of 6d in EtOH could be followed by absorption ee SI) spectroscopy which clearly demonstrated its full conversion into (rt). It is noteworthy that this conversion is much faster in presence of water or acid. nclusion, we described a new synthesis of two major classes of conjugated -systems from the commercially available substituted BQI 1a-j could be isolated through a transamination reaction on a key cationic intermediate all the previous routes, our approach is simultaneously versatile and environmentally friendly because it allows the introduction of new functionalities, hitherto unknown, and it proceeds one-pot with no heat and no metal. 2) Benzobisimidazoles also obtained in good yields by using primary amines of type R'CH 2 NH 2 bearing an aromatic unit (R') that modulates The versatility and simplicity of these "green" approaches pave the way for new perspectives in benzobisimidazole-based fluorophores). quantities of methylamine and benzylamine under similar conditions, ucts that could not be separated. This observation suggests similar relative ) is very seldom reported despite its potential in organic Intramolecular cyclization of 6a-d in substituted benzobisimidazoles 3a-d (Scheme 2). showed the presence of two characteristic resonances at 5.66 and 8.72 ppm corresponding to the in EtOH could be followed by absorption full conversion into 3d at room temperature systems from the commercially available could be isolated through a transamination reaction on a key cationic intermediate all the previous routes, our approach is simultaneously versatile and environmentally friendly because it allows the pot with no heat and no metal. 2) Benzobisimidazoles bearing an aromatic unit (R') that modulates The versatility and simplicity of these "green" approaches pave the way for new perspectives in Experimental details and characterization data of the molecules are described. CCDC 1496322 and 1496323 for 3a and 1c, respectively.

NH 2 NH N H N R' HN N NH NH 2 R' R' NH 2 NH N H H 2 N R' R' H 2 N N N H NH R' R' H Rearrangement A -NH 2 NH 2 NH N N R' C C [Ox]

Figure 1 .

 1 Figure 1. X-ray structure of 1c.

30

 30

Figure 2 .

 2 Figure 2. Molecular structure of 3a

  = CH 3 1b : R = C 3 H 7 1c : R = C 4 H 9 1d : R = C 8 H 17 1e : R = CH(CH 2 OH) 2 1f : R = CH 2 -(CH 2 ) 5 OH 1g : R = (CH 2 ) 2 -CH=CH 2 1h : R = CH(CH 3 )Ph 1i : R = (CH 2 ) 3-4 -Mor 1j

  1a-j 6a : R' = Ph* 6b : R' = 3,4,5-(OMe) 3 -C 6 H 2 * 6c : R' = 3-Py* 6d : R' = 2-Py 3a : R' = Ph 3b : R' = 3,4,5-(OMe) 3 -C 6 H 2 3c : R' = 3-Py 3d : R' = 2-Py A2 (not isolated)

Figure 3 .

 3 Figure 3. Intramolecul

Figure 3 .

 3 Figure 3. Intramolecular cyclization of 6d into 3d (EtOH at rt)

AUTHOR INFORMATION

Corresponding Author * olivier.siri@univ-amu.fr

Author Contributions

The manuscript was written through contributions of all authors. All authors have given approval to the final version of the manuscript. ACKNOWLEDGMENT J. A.E gratefully acknowledges the Agence Nationale des Bourses du Gabon (ANBG) for financial support. This work was supported by the Centre National de la Recherche Scientifique and the Ministère de la Recherche et des Nouvelles Technologies (PhD grant to Z. C.). O.S. thanks Dr Pierre Braunstein (Univ. of Strasbourg) for discussions on transmination reactions. We also thank Valérie Monnier and Christophe Chendo for the analyses by mass spectrometry (Spectropole, Marseille).