Yingchong Ma
email: yingchong.ma@ec-lille.fr

Gang Zheng
email: gang.zheng@inria.fr

Wilfrid Perruquetti
email: wilfrid.perruquetti@inria.fr

Zhaopeng Qiu
email: zhaopeng.qiu@ec-lille.fr

Local path planning for mobile robots based on intermediate objectives *

This paper presents a path planning algorithm for autonomous navigation of non-holonomic mobile robots in complex environments. The irregular contour of obstacles is represented by segments. The goal of the robot is to move towards a known target while avoiding obstacles. The velocity constraints, robot kinematic model and non-holonomic constraint are considered in the problem. The optimal path planning problem is formulated as a constrained receding horizon planning problem and the trajectory is obtained by solving an optimal control problem with constraints.

Local minima are avoided by choosing intermediate objectives based on the real time environment.

Introduction

Autonomous navigation is an important issue in robotics research. This problem is of theoretically interesting properties and of practical importance. Navigation is a task that an autonomous robot must do correctly in order to move safely from one location to another without getting lost or colliding with other objects [START_REF] Pearsall | Concise Oxford Dictionary[END_REF]. Three general problems are involved in navigation: localization, path planning and trajectory tracking. In these problems, path planning is quite important since it enables the selection and the identification of a suitable path for robots to traverse in the environment.

When the environment is completely known before the robot moves, a collision free trajectory with lowest cost from the starting point to the target can be obtained by global path planning algorithms, the cost can be defined as the traveled distance, the expended energy, time exposed to danger, etc. In such cases, the complete information of the environment is obtained in static environment, and collision free paths are selected and planned off-line. Different kinds of approaches have been proposed, such as cell decomposition [START_REF] Brooks | A subdivision algorithm in configuration space for findpath with rotation[END_REF][START_REF] Glavaški | Robot motion planning using exact cell decomposition and potential field methods[END_REF], visibility graph [START_REF] Dudek | Computational Principles of Mobile Robotics, ser. Computational Principles of Mobile Robotics[END_REF][START_REF] Huang | Dynamic visibility graph for path planning[END_REF][START_REF] Bicchi | Planning shortest bounded-curvature paths for a class of nonholonomic vehicles among obstacles[END_REF], retraction [START_REF] Dnlaing | A "retraction" method for planning the motion of a disc[END_REF], heuristic-based algorithms [START_REF] Dijkstra | A note on two problems in connexion with graphs[END_REF][START_REF] Hart | A formal basis for the heuristic determination of minimum cost paths[END_REF], genetic algorithms [START_REF] Nearchou | Path planning of a mobile robot using genetic heuristics[END_REF][START_REF] Ismail | A mobile robot path planning using genetic algorithm in static environment[END_REF], and projection [START_REF] Schwartz | On the piano movers' problem i. the case of a two-dimensional rigid polygonal body moving amidst polygonal barriers[END_REF] etc. A wellknown algorithm of global heuristics search is A * [START_REF] Nilsson | Principles of Artificial Intelligence[END_REF], which can find the shortest collision free path through a fully mapped environment by using a priority queue. D * search [START_REF] Stentz | Optimal and efficient path planning for partially-known environments[END_REF] is an extension of A * algorithm, and has been used in many applications [START_REF] Choset | Topological simultaneous localization and mapping (slam): toward exact localization without explicit localization[END_REF]. It can modify the planned path dynamically if unknown obstacles are encountered. When a robot has only partial knowledge about the environment before it starts, the robot has to plan the path locally with the information captured by the sensor equipped on the robot [START_REF] Goto | Mobile robot navigation: The cmu system[END_REF]. The Bug1 and Bug2 algorithms [START_REF] Lumelsky | Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape[END_REF] are among the earliest and simplest sensor-based path planning algorithms, and the algorithms are based on the boundary following method. Another famous algorithm is the artificial potential field approach (APF) proposed in [START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF]. One of the main drawbacks of APF is local minima when the composition of all forces on the robot equals to zero. Some extended algorithms based on APF have been proposed [START_REF] Latombe | Edition en anglais[END_REF][START_REF] Koren | Potential field methods and their inherent limitations for mobile robot navigation[END_REF].

When considering the path planning problem for unicycle-like mobile robots, the physical limitations and kinematic constraints have to be taken into account. Due to those constraints, the algorithms mentioned above cannot be applied to this type of mobile robots, since these constraints might render many unfeasible spatial paths. Some algorithms have been proposed for this kind of robot [START_REF] Kolmanovsky | Developments in nonholonomic control problems[END_REF][START_REF] Laumond | Robot motion planning and control[END_REF][START_REF] Guo | Optimal trajectory generation for nonholonomic robots in dynamic environments[END_REF], and the algorithm proposed in [START_REF] Defoort | Performance-based reactive navigation for non-holonomic mobile robots[END_REF] describes the path planning problem as a nonlinear optimization problem with constraints, which guarantees the navigation of the robot in unknown environments. However, they either compute the path not in an optimal way, or simply represent the obstacles as circles, and there are at least two drawbacks for these algorithms: firstly only the circular obstacles are taken into account, and secondly local minima cannot be avoided when robots getting close to complex obstacles. Therefore, this algorithm is not suitable for complex environments with different shapes of obstacles. An extended algorithm is proposed in [START_REF] Kokosy | Autonomous navigation of a nonholonomic mobile robot in a complex environment[END_REF] based on the Tangent Bug algorithm [START_REF] Kamon | A new range-sensor based globally convergent navigation algorithm for mobile robots[END_REF] to treat this problem by following the obstacle boundary, which however involves unnecessary detours along obstacle boundaries and leads to non optimal trajectories. In this paper, the irregular contours of obstacles are represented by segments. The path planning problem for unicycle-like mobile robots is described as an optimal control problem by involving all physical constraints. Local minima are avoided by choosing intermediate objectives based on the real-time environment. 2 Path planning: an optimal control point of view

Problem Statement

In general cases, the environment may be complex and normally obstacles cannot be described as circles, as assumed in [START_REF] Defoort | Performance-based reactive navigation for non-holonomic mobile robots[END_REF] (see Fig. 1 for example). Moreover, due to the distance limitation of sensors equipped on robots, only a portion of an obstacle can be captured, so that the robot may not know the exact shape of obstacles. In this case, obstacles can neither be described as circles nor be described as complete polygons.

As a result, the goal of this paper is to represent obstacles in a more accurate way, and to propose an efficient path planning algorithm which guarantees the safe navigation of a robot from a known initial position to a desired target in unknown environments while satisfying the physical constraints of the robot.

Mobile robot modeling

This paper considers the unicycle-type mobile robot whose kinematic model can be described as:

               ẋ = υ cos θ ẏ = υ sin θ θ = ω (1)
where υ and ω are the linear and angular velocity respectively, θ is the orientation of the robot body with respect to X-axis, U = [ υ, ω ] T is the control input, and q = [x, y, θ] T is the system state (see Fig. 2).

✻ ✲ Om ≡ M ✯ x y - → x m - → y m ❑ θ O - → x - → y ❑ Figure 2.

Unicycle-type mobile robot

Without loss of generality, let us make the following assumptions:

Assumption 1: There is pure rolling situation (i.e., no slipping and sliding phenomenon) for robots, thus non-holonomic constraint of the robot can be described as:

[sin θ cos θ 0 ] q = 0 Assumption 2: This paper considers the unicycle mobile robot which allows turning in-place.

Assumption 3: The robot has only local view, thus only the closest obstacle in one direction can be detected.

It can be shown that x and y are flat outputs (see [START_REF] Fliess | Flatness and defect of nonlinear systems: Introductory theory and examples[END_REF] for the definition) for the robot system [START_REF] Pearsall | Concise Oxford Dictionary[END_REF]. Indeed, θ, υ and ω can be expressed by x, y and their first and second-order derivatives as follows:

               θ = arctan ẏ ẋ υ = ẋ2 + ẏ2 ω = ÿ ẋ-ẍ ẏ ẋ2 + ẏ2
(2) Thus one needs only to optimize x and y to obtain the optimal values of θ, υ and ω, where x and y are parameterized trajectories as stated in [START_REF] Defoort | Performance-based reactive navigation for non-holonomic mobile robots[END_REF], and the optimal trajectories can be obtained by optimizing the parameters of the parameterized trajectories, which is described in the following.

Optimal control problem

Nonlinear Optimization Problem Formulation

As mentioned before, the path planning problem for mobile robots with physical constraints can be formulated as an optimal control problem. Generally speaking, it is to find the optimal control U = [v, ω] for system [START_REF] Pearsall | Concise Oxford Dictionary[END_REF] and to minimize the following cost function:

J = t f t 0 F (U(t), q(t), t) dt (3)
where t 0 and t f are the initial time and the final time respectively, U = [v, ω] and q = [x, y, θ].

F is a function of U and q which defines the cost function to be minimized. F can be chosen in advance, and can take several different forms. For example, when F = 1, i.e. to minimize the time t ft 0 , it implies that the robot reaches the target as fast as possible. In this paper the cost function is chosen as the following one to guarantee the robot moving towards the objective:

F = ((x(t) -x f ) 2 + (y(t) -y f ) 2 ) (4)
where (x f , y f ) is the desired final position.

Moreover, the expected optimal control and the resulting states should satisfy the following constraints:

C 1 : the constraint on optimal control and state, i.e. the optimal control U and the states q should satisfy the kinematic model (1) for t ∈ [ t 0 , t f ].

C 2 : the constraint on initial and final conditions, i.e.

q(t 0 ) = q(0), q(t f ) = q f inal C 3 : the constraint on boundedness of control, i.e.

| υ | ≤ υ max and | ω | ≤ ω max C 4 : the constraint on collision avoidance, i.e. d(O, R) ≥ r
where d(O, R) is the distance between the robot and any obstacle, and r is the given distance which guarantees the obstacle avoidance criterion.

Receding horizon planner

When the map is large, or is partially known, it is impossible to solve the above optimal control problem to obtain the whole optimal trajectory. In order to avoid this problem, the receding horizon planner [START_REF] Mayne | Receding horizon control of nonlinear systems[END_REF] can be used to compute only a part of the trajectory from the current position to the final one over a time interval [τ k , τ k + T c ], where T c is the update period, and 0 < T c < T p , where T p is the trajectory planning horizon. As shown in Fig. 3, the robot only computes a trajectory of horizon T p and updates at each

step τ k = τ initial + kT c .
The optimal control problem with constraints over a receding horizon can be numerically solved by using the flatness property of the system [START_REF] Fliess | Flatness and defect of nonlinear systems: Introductory theory and examples[END_REF], the parameterized trajectory and constrained feasible sequential quadratic optimization algorithm, for example CFSQP [START_REF] Lawrence | User's guide for CFSQP version 2.5: AC code for solving (large scale) constrained nonlinear (minimax) optimization problems, generating iterates satisfying all inequality constraints[END_REF] (Feasible Sequential Quadratic Programming Algorithm proposed in [START_REF] Lawrence | A computationally efficient feasible sequential quadratic programming algorithm[END_REF]), for details see [START_REF] Defoort | Performance-based reactive navigation for non-holonomic mobile robots[END_REF]. Then the open loop control U = [υ, ω] T is deduced by using equation (2).

3 Path planning algorithm with intermediate objectives

Representation of obstacles

In real situations, as stated in the problem statement, obstacles can neither be described as circles nor as complete polygons. portion of the i th obstacle contour can be approximated by a succession of segments S j i , where j = 1, 2, ..., q, and q is the number of segments on an obstacle. Each segment is represented by its two end points p j i and p j+1 i , and each point has their coordinates (x

p j i , y p j i ) and (x p j+1 i , y p j+1 i )
respectively. The functions of the segments can be obtained by applying the image processing algorithms [START_REF] Graham | An efficient algorithm for determining the convex hull of a finite planar set[END_REF], which is beyond the scope of this paper. Thus, this paper assumes that the irregular obstacles are represented by a serial of segments.

Remark 1 If the distance between two obstacles d obs < 2r, where r is the given distance which guarantees the obstacle avoidance criterion, then the two obstacles are considered as one, since the robot can not pass through the space between the two obstacles.

Distance between robot and segments

Since obstacles are represented by segments, the obstacle avoidance constraint C 4 in the optimal control problem (3) becomes the distance constraint between the robot and segments.

Denote O(x o , y o ) the robot position,

p j i (x j i , y j i ), p j+1 i (x j+1 i , y j+1 i
) the two end points of segment

S j i .
Then one can define the distances between those points:

d(O, p j i ) = (x o -x j i ) 2 + (y o -y j i ) 2 d(O, p j+1 i ) = (x o -x j+1 i ) 2 + (y o -y j+1 i ) 2 d(p j i , p j+1 i ) = (x j i -x j+1 i ) 2 + (y j i -y j+1 i ) 2
Thus, the distance between the robot and the segment S j i , noted as d(O, S j i ), can be calculated according to the relative position of the robot and the segment. There are three possible cases

(see O 0 , O 1 , O 2 in Fig. 5) : ✉ ✉ ✉ ✉ ✉ S j i p j+1 i (x j+1 i , y j+1 i ) p j i (x j i , y j i ) O 0 O 1 O 2 R 0 R 2 R 1
) 2 > d(O, p j i ) 2 + d(p j i , p j+1 i ) 2 .
d(O, S j i ) = 2 L(L -d(O, p j i ))(L -d(O, p j+1 i ))(L -d(p j i , p j+1 i )) d(p j i , p j+1 i ) where L = d(O,p j i )+d(O,p j+1 i )+d(p j i ,p j+1 i ) 2
. See the red dotted line in R 1 .

Summary, the distance between the robot and segment S j i is determined by the following equation:

d(O, S j i ) =                d(O, p j i ), case 1 d(O, p j+1 i ), case 2 2 √ L(L-d(O,p j i ))(L-d(O,p j+1 i ))(L-d(p j i ,p j+1 i )) d(p j i ,p j+1 i ) , case 3 (5)
However, it will be explained in the next section that this algorithm of using segments to represent obstacles suffers from local minima problems.

Local minima

It is worth noting that using of segments to represent obstacle contours inevitably involves local minima problems. This phenomenon happens when a robot arrives a point where the distance between the robot and the objective is minimum under the constraint of obstacle avoidance. For example, in Fig. 6, one can choose intermediate objectives {p 1 i , p 2 i , G} instead of the final objective {G}, navigating the robot to reach p 1 i , then p 2 i and finally G. Then the optimal sub trajectories: O → p 1 i , p 1 i → p 2 i and p 2 i → G can be calculated by solving the optimal control problem stated in section 2. It can be seen that if the robot follows this way, there will be no local minima phenomena.

t t S 1 i S 2 i S 3 i ❯ ❑ ❯ ❑ d(O, G) = min((x(t) -x f ) 2 + (y(t) -y f ) 2 ) Objective G(x f , y f ) Robot O(x, y)

Path planning algorithm with intermediate objectives

The "following the obstacle boundary mode" proposed in [START_REF] Kokosy | Autonomous navigation of a nonholonomic mobile robot in a complex environment[END_REF] can guarantee the avoidance of obstacles without local minima, but the robot needs to unnecessarily detour along with the contour of obstacles. For example in Fig. 7, robot need follow the contours {p 4 i , p Finally the robot can reach G by following this list.

Remark 2 Although the optimization method can be applied to any kind of mobile robots to drive the robot from one point to another one, however the approach described in this paper might not be applicable for a general non-holonomic robot (like car-like mobile robot) if the approaching direction to the intermediate point is not considered. The reason is that, after achieving the intermediate point, some kinds of robots will not have enough space to turn (due to the non-holonomic constraint) in order to achieve the next trajectory. However, the unicycle model considered in this paper has not such a problem since it allows turning in-place.

From the above description, the proposed algorithm contains the following three aspects:

1. Select intermediate objectives from local information to generate a temporary list IO -List;

2. Be sure that the robot can reach another region (for example, R s in Fig. 7);

3. Judge when the robot arrived at this region.

Before explaining these three aspects, let us give some notations which will be used in the sequel. Define P = {P i } for 1 ≤ i ≤ N to be all sets of the obstacle boundaries detected by the equipped sensors, where N is the number of detected obstacle boundaries. Note P i = {p j i } for 1 ≤ j ≤ N i as the set of joint points to represent the i th obstacle boundary, where N i is the number of points. Each segment S j i is defined by its endpoints

S j i = (p j i , p j+1 i ). Let IO -List = {p k , G} for 1 ≤ k ≤ m

The intermediate objectives selection

Whenever the robot detects several obstacles around its surrounding, it always chooses the one with which the begin-final segment OG has an intersection. If OG has no intersection with all obstacles, then the robot can see the target G directly and thus the optimal path is the straight line OG. Otherwise, OG can have only one intersection with all obstacles, since it can detect only visible part of obstacles. For example, in Fig. 8, OG intersects with P i , and the possible optimal trajectory might from p 1 i or p 5 i , but it is absolutely not possible from the obstacles P i+1 or P i+2 since those paths from P i+1 or P i+2 are obviously larger than the ones from P i .

✉ ✉

Robot O(x(t), y(t))

Target G(x f , y f )

P i+2 P i P i+1 S 1 i S 2 i S 3 i S 4 i p 1 i p 2 i p 3 i p 4 i p 5 i

Figure 8. Intermediate objectives generation

After determining the exact obstacle (in Fig. 8, it is

P i since segment p 2 i p 3 i in P i = {p 1 i , • • • , p 5 i }
intersects with OG), we search intermediate objectives from both sides of OG. Take the right region of OG for example, one has the segment p 3 i p 4 i , and check whether the segment Gp 4 i has an intersection with P i . If not, that means the robot can see the final objective G after passing over the point p 4 i , thus the point p 3 i does not need to be added on List -T . If segment Gp 4 i has an intersection with P i , which implies that the robot is not able to see G after passing over p 4 i , thus the robot needs to go to point p 3 i in order to see G, and p 3 i should be added on List -T . Iteratively search next segment ( p 4 i p 5 i in Fig. 8) until the end of the segment of P i , one obtains

List -T = {p 5 i , p 4 i , G}
By applying the same procedure for the left region of OG, one gets

List -H = {p 1 i , p 2 i , G}
Finally, the temporary list of intermediate objectives is then determined by the path cost of these two lists, i.e. if

dis(O, List -T ) > dis(O, List -H) then IO -List = List -H, otherwise IO -List = List -T .
The routine to generate the list of intermediate objectives is given in Algorithm 1.

Reach switching region

In order to clearly explain the algorithm, let us consider the following simple segment obstacle depicted in Fig. 9, and suppose that one has obtained the following list of intermediate objectives:

IO -List = {p 1 i , p 2 i , G}
Thus the robot is guided to reach the first element in IO -List, i.e. p 1 i , then p 2 i and finally G.

Then one can solve the optimal problem with constraints C 1 -C 4 by minimizing the cost function with respect to current intermediate objective, i.e.

min Tp O -p 1 i 2 dt, s.t. C 1 -C 4 (6)
The solution of this optimal problem yields optimal parameterized trajectories x and y, then one can get optimal control (v, ω) according to [START_REF] Brooks | A subdivision algorithm in configuration space for findpath with rotation[END_REF].

Segment Obstacle Objective G(x f , y f ) Robot O(x, y) ✈ ✈ p 3 i p 4 i ✈ p 2 i p 1 i t t V 1 V 2 V 3 R s A C p1 i ⑥ ✰ r t

Figure 9. Intermediate objectives selection

However, choosing directly p 1 i as final target in (6) results in local minima again. For example, as shown in Fig. 9, where r is the collision free distance, point A is on the boundary satisfying the obstacle avoidance criterion. In this situation, the robot may stop at point A since no other trajectories are better than to stay at this point (it has already minimized the cost function [START_REF] Bicchi | Planning shortest bounded-curvature paths for a class of nonholonomic vehicles among obstacles[END_REF] under the constraints C 1 -C 4 ). Finally, the robot cannot pass over the segment p 1 i p 2 i to see the

second intermediate objective p 2 i .
In order to make sure that the robot can always pass over the endpoint of the obstacle, let us give the following notations. Denote V 1 the top region of line p 1 i p 2 i (the region where the second intermediate objective p 2 i is visible), and V 2 the left region of line Op 1 i (the region where robot can reach freely). Define V 3 the collision constraint region:

V 3 = {(x, y) : (x -x i ) 2 + (y -y i ) 2 ≤ r 2 , ∀(x i , y i ) ∈ p 1 i p 2 i }
Then define the switching region R s as follows:

R s = (V 1 ∩ V 2 ) ∩ V 3 where V 3 is the complement of V 3 .
As the switching region is defined, one can see that the optimal path for the robot is to go directly into the switching region, as a result one can choose p1 i ∈ R s and replace p 1 i by p1 i in [START_REF] Bicchi | Planning shortest bounded-curvature paths for a class of nonholonomic vehicles among obstacles[END_REF] to ensure that the robot goes into the switching region and avoids detours around the endpoint of the obstacles. Finally this optimal problem can be solved without local minima, since the robot can always pass over the segment p 1 i p 2 i to see the second intermediate objective p 2 i .

In this paper, the modified intermediate objective p1 i is determined as follows (see Fig. 9): firstly find out the point C at a distance of r to the point p 1 i on the extension of segment from the endpoint p 2 i to the endpoint p 1 i , and then select p1 i at a distance of r to the point C on the extension of segment from the robot to the point C.

It is worth noting that the connection between the modified intermediate point p1

Simulation results

In order to show the feasibility and efficiency of the proposed algorithm, three simulations for different scenarios are made, and comparisons with visibility graph with expanded obstacles are made in the latter two simulations. The simulation settings are as follows: the range of robot sensors is 3 m; the maximum speed of robot is 1.0 m/s, the maximum acceleration is 1.0 m/s 2 , the maximum angular velocity is 1.0 rad/s, the maximum angular acceleration is 1.0 rad/s 2 . The planning horizon interval T p is 2 s, and the update period T c is 0.2 s.

For the simple scenario, depicted in Fig. 10, black polygons represent obstacles, containing a concave obstacle and a triangle obstacle. In this scenario, there exists a broad zone of local minima. The robot starts from the initial point (6, 4.5) to the target [START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF][START_REF] Khatib | Real-time obstacle avoidance for manipulators and mobile robots[END_REF]. The red crosses in One can see that in Fig. 11 several local minima exist, the robot starts from (7, 2) to [START_REF] Nearchou | Path planning of a mobile robot using genetic heuristics[END_REF][START_REF] Koren | Potential field methods and their inherent limitations for mobile robot navigation[END_REF] and avoids all local minima by choosing intermediate objectives and reaches the target successfully by using only local sensor information. In Fig. 12, where there is a long winding corridor, the robot starts from (7, 2) to [START_REF] Kokosy | Autonomous navigation of a nonholonomic mobile robot in a complex environment[END_REF][START_REF] Nearchou | Path planning of a mobile robot using genetic heuristics[END_REF]. It can be seen that the robot manages to walk through the long corridor and reach the target successfully while avoiding local minima and all the obstacles.

Comparisons with visibility graph are made. Normally visibility graph is used in global planning when the map is completely known, in order to use visibility graph in local planning with unknown map, the algorithm needs to generate expanded polygon for each obstacle in the local map and search for the shortest path among all the obstacles, then iterate until the robot reaches the target.

Instead, in our proposed algorithm the robot search for the shortest path only in some obstacles (normally one or two) in each iteration, which reduces the computational complexity compared to visibility graph approach.

As we can see in the figure 11, 12 and table 1, there are no big differences between the trajectories generated by two different methods, however it costs less time by using the method proposed in this paper. Remove the 1st element p 1 i from IO -List 6:

Add p 1 i into CloseList 7: end if

Figure 1 .

 1 Figure 1. Description of the environment

Figure 3 .

 3 Figure 3. Planning and update horizons

Figure 4 .

 4 Figure 4. Approximation of obstacles with complex shape

Figure 5 .

 5 Figure 5. The three cases for distance calculation

4 iFigure 6 .

 46 Figure 6. Local minima

3. 4

 4 Avoidance of local minima by choosing intermediate objectivesThis local minima problem cannot be avoided by the optimal path planning algorithm stated above. However one can notice that local minima problems might occur when the connection between the current robot position and the objective crosses with the segment (see in Fig.6the segment GO crosses S 2 i ). As a result, one can introduce some intermediate objectives for the robot if these intermediate objectives can guide the robot to escape local minima and to achieve the final objective. Generally, the selection of intermediate objectives is according to the information detected by the sensor equipped on the robot. Once the intermediate objectives are chosen, optimal path

Figure 7 .

 7 Figure 7. Complex environment

  save the selected intermediate objectives. Denote dis(p k p k+1 ) for 1 ≤ k ≤ m -1 the function to calculate the distance between point p k and point p k+1 , and note dis({O} ∪ IO -List) = dis(Op 1 ) + m-1 k=1 dis(p k p k+1 ) + dis(p m G) as the function to compute the complete path cost from the robot current position O to the final target G by following IO -List. For the reached intermediate points which have already treated, we remove them from IO -List and save them on a CloseList to avoid unnecessary returns. Thus for an endpoint belonging to CloseList, the path cost from this path is set to be +∞. List -H and List -T are defined to save two possible lists of intermediate objectives from the head and the tail of IO -List, being initialized as List -H = List -T = {G}.

  i and robot position may crosses with another obstacle, if the line connected between p1 i and robot crosses the list of intermediate objectives IO -List, calculates the modified intermediate objective p1 i and solves the optimal problem over T p and implements the optimal controls for [0, T c ]. The algorithm stops when the robot reaches the final target G. The routine is detailed in Algorithm 4.

Figure 10 .

 10 Figure 10. Scenario 1: Simple environment

Figure 11 Figure 12 .

 1112 Figure 11. Scenario 2: Complex environment

4 :i p 2 i ); 5 : 1 : 2 : 4 :

 45124 Compute point C s.t. f (x c , y c ) = 0, dis(Cp 1 i ) = r dis(Cp 2 i ) = r + dis(p 1Determine the function g(x, y) = 0 for the segment OC;6: Select p1 i s.t. g(x p1 i , y p1 i ) = 0, dis(C p1 i ) = r dis(O p1 i ) = r + dis(OC); Function Switch ((x(0), y(0)), (x(T c ), y(T c )), IO -List) Get the first segment p 1 i p 2 i from IO -List 3:Get the function f (x, y) = 0 for this segment; if f (x(0), y(0)) × f (x(T c ), y(T c )) < 0 then 5:

  In this case the robot locates in the left region R 0 of S j i . It is easy to see that d(O, S j i ) = d(O, p j i ), which is the red dotted line in R 0 .

	Case 2 d(O, p j i ) 2 > d(O, p j+1 i	) 2 + d(p j i , p j+1 i	) 2 . In this case the robot locates in the right region R 2
	of S j i . It is obvious that d(O, S j i ) = d(O, p j+1 i	), which is the red dotted line in R 2 .
	Case 3 If not in case 1 and case 2, the robot is in region R 1 . The distance between the robot
	and the segment d(O, S j i ) can be obtained by simply using Heron's formula. A straightforward
	computation yields:

  The procedure of the proposed algorithm with intermediate objectives can be illustrated in Fig.7. At the first time, the robot detects via sensors a serial of joint segments: {p 1 i , • • • , p 7

	i } around
	its local environment. Since the dotted part {p 8 i , • • • , p 14 i } is invisible for this moment, the robot
	assumes that there is no obstacle in the invisible part, thus it thinks that the obstacle is only
	{p 1 i , • • • , p 7 i }. Then the robot chooses a temporary set of intermediate objectives in order to avoid
	local minima, noted as IO -List = {p 7 i , p 6 i , p 5 i , G}. The robot gets the head of IO -List, i.e. p 7 i ,
	then it generates an optimal sub trajectory O → p 7 i by solving optimal control problem defined
	3 i , p 2 i , p 1 i } or {p 5 i , p 6 i , p 7 i }
	to avoid the concave obstacle. The proposed algorithm in this paper takes into account only the
	disjoint endpoints (the head p 1

i and the tail p 7 i ) of a serial of joint segments which is used to represent the detected partial obstacle. in section 2. When the robot arrives in the region R s , i.e. the region where robot can always see the second element in IO -List, p 6 i in this scenario, we remove the reached point p 7 i into a close list, noted as CloseList ← p 7 i . Robot scans again its surrounding and detects new obstacles represented by {p 7 i , p 14 i }. Since the head point p 7 i belongs to CloseList, which means that the robot has already reached this point, thus the intermediate objectives should be deduced from the tail point p 14 i , and the temporary list of intermediate objectives is updated as: IO -List = {p 14 i , G}.

Table 1 . Comparison of simulation results

 1

		Method	Running Time (s) Time-saving Trajectory Length (m)
	Scenario 2	Our method Visibility Graph	3.02 3.74	19.2%	22.2 22.1
	Scenario 3	Our method Visibility Graph	3.21 4.02	20.1%	30.2 29.8

  Algorithm 1 The Intermediate Objectives List Generation Function 1: Function IO -Generation (G(x f , y f ), O(x(t), y(t)), P) 2: for each P i do List -T = List -H = {G} 8: for k=j+1: 1:m-1 do ⊲ m is the number of points on P i Selection of the Intermediate Objective 1: Function IO -Selection (O(x(t), y(t)), IO -List) 2: Get the first segment p 1 i p 2 i from IO -List 3: Get the function f (x, y) = 0 for this segment;

	3:	if ∃p j i , p j+1 i	∈ P i s.t. p j i p j+1 i	OG = ∅ then
	4:	select P i , break
	5:	end if
	6: end for
	7: 9:	if Gp j+2 i	P i = ∅ then
	10:	List -T = {p j+1 i	} List -T
	11:	end if
	12: end for
	13: List 15: if Gp j-1 i	P i = ∅ then
	16:	List -H = {p j i } List -H
	17:	end if
	18: end for
	19: List -H = {p 1 i } List -H
	20: if p m i ∈ CloseList then
	21:	dist(List -T ) = +∞
	22: end if
	23: if p 1 i ∈ CloseList then
	24:	dist(List

-T = {p m i } List -T 14: for k=j:-1:2 do -H) = +∞ 25: end if 26: if dist({O} List -T ) ≤ dist({O} List -H) then 27: Return List -T 28: else 29: Return List -H 30: end if 28 Algorithm 2

* This work was supported by EU INTERREG IVA 2 Mers Seas Zeeen Cross-border Cooperation Programme under SYSIASS project 06-020. It was also supported by Ministry of Higher Education and Research Nord-Pas de Calais Regional Council and FEDER through the "Contrat de Projets Etat Region (CPER) CIA 2007-2013".

1

with another obstacle, the intermediate objective should be selected from the obstacle that crosses with the line, and add the new intermediate objective to IO List, then generate new modified intermediate objective p1

i from new IO List. (See line 10-16 in Algorithm 4)

The routine to select intermediate objectives is given in Algorithm 2.

Judge the switching time

Suppose that one has IO -List = {p 1 i , p 2 i , • • • , G} and the associated switching region R s . Since the robot reinitializes and solves the optimal problem after every T c , thus one can use the position of robot at t = 0 and t = T c (named as (x(0), y(0)) and x(T c ), y(T c )) to judge whether it enters R s . For this, note the function f (x, y) = 0 representing the first segment

one can judge that the robot has already entered the region R s , which implies that the robot has passed over p 1 i and now can see p 2 i . Then we move p 1 i from IO -List to CloseList.

The routine to judge the switching time is given in Algorithm 3.

Algorithm Description

Given the temporary list of intermediate objectives IO -List, which enables to define the switching region R s and calculate the modified intermediate objective p1 i , one can solve optimal problem over T p to get an optimal trajectory, which yields the optimal controls v and ω for robot over [0, T p ]. Then one applies those optimal controls only for an interval [0, T c ]. When t = T c , one iterates the same procedure as before, i.e., scans the surroundings to get obstacles P, generates Algorithm 4 Path Planning 1: Function P athP lanning(G(x f , y f ), Ini. conditions)

Get P from sensor 5:

if add -List = IO -Generation(p 1 i , O(x(0), y(0)), P) Reset t = 0 25: end while


Ricardo M Ribeiro

Frédéric Lucarz
email: frederic.lucarz@telecom-bretagne.eu

Bruno Fracasso

Proposal and Design of an All-Optical Encoder for Digitising Radio-over-Fibre Transceivers

Keywords: analogue-digital conversion, encoder, microwavephotonics, optical signal processing, semiconductor optical amplifier I

In this paper it is proposed and designed an original all-optical Encoder (o-Encoder) intended, but not exclusively, to be part of future optical digitising radio-over-fibre (o-DRoF) transceiver. It is based on the Semiconductor Laser Amplifier Loop Mirror (SLALOM) configuration exploiting the nonlinearities of a semiconductor optical amplifier (SOA) in cross-switching regime. The proof-of-principle is established using 40-ps RZ control pulses at 2.5 GHz in the C-band. It outputs serially encoded, quantized and amplified optical RZ bits. Computer simulations of the proposed o-Encoder have shown promising results. The proposed device is rather compact, potentially optically integrable and requires much less input optical power (by several orders of magnitude) than other photonic-encoders and can also naturally convert wavelengths in the optical domain.

INTRODUCTION

Analogue Radio-over-Fibre (ARoF) is a key-technology for the convergence of fibre-based wireline and wireless networks [START_REF] Williamson | RF Photonics[END_REF]. ARoF allows a relatively simple distribution of RF signals over optical fibres connecting a Central Station (CS) to Base Stations (BSs) or Remote Antenna Units (RAUs). Therefore, all signal processing may be centrally carried out at the CS [START_REF] Williamson | RF Photonics[END_REF][START_REF] Nirmalathas | Digitized Radio-Over-Fiber Technologies for Converged Optical Wireless Access Network[END_REF], leading to simple RAUs design that only needs to implement optoelectronic conversion and power amplification.

However, ARoF systems are constrained by two basic requirements, which are inherent to analogue transmissions [START_REF] Williamson | RF Photonics[END_REF]: all used devices should be highly linear and the received signal should have higher SNR (Signal to Noise Ratio) than those obtained with digital systems.

In order to circumvent the limitations of ARoF networks, the use of digitised radio-over-fibre (DRoF) technologies [START_REF] Williamson | RF Photonics[END_REF][START_REF] Nirmalathas | Digitized Radio-Over-Fiber Technologies for Converged Optical Wireless Access Network[END_REF][START_REF] Abdollahi | Fully-Photonic Analogue-to-Digital Conversion Technique for Super-Broadband Digitized-Radio over Fibre Link[END_REF][START_REF] Abdollahi | Digital Radio over Fibre for Future Broadband Wireless Access Network Solution[END_REF][START_REF] Abdollahi | Non-Uniform Wavelength Allocation in All-Photonic Digitized-Radio over Fibre Access Network[END_REF][START_REF] Viglienzoni | Net! Works -Next Generation Network: Wireless-Optics Technology[END_REF] is an interesting alternative. In electronic DRoF links the analogue RF input signal is first digitised by an analogue-todigital converter (ADC), the generated electrical bits drive a light source thus generating optical bits then transported over an optical fibre and finally are reconstructed by a digital-toanalogue converter (DAC) at the output of a photo-detector.

Each BS (or RAU) comprises one ADC and one DAC, while more complex digital signal processing is carried out in the CS [START_REF] Nirmalathas | Digitized Radio-Over-Fiber Technologies for Converged Optical Wireless Access Network[END_REF]. Due to the digital nature of the optical link, the dynamic range is independent of the fibre length as long as the power of the received signal is lower than the link sensitivity. Electronic DRoF technologies still exhibit some advantages over ARoF [START_REF] Nirmalathas | Digitized Radio-Over-Fiber Technologies for Converged Optical Wireless Access Network[END_REF][START_REF] Abdollahi | Fully-Photonic Analogue-to-Digital Conversion Technique for Super-Broadband Digitized-Radio over Fibre Link[END_REF] except for its relative higher complexity, but include further characteristics as follows: centralised digital signal processing such as digitisation itself, enhanced sharing capacity, better compatibility of digital equipments and communication channels, significant increase in transmission distance using optical fibre (larger dynamic range), larger coverage capacity or larger number of RAUs, possible cost reduction and energy saving.

The signal conversion and high-speed processing (including switching and routing) in the all-photonic domain are required for next-generation networks due to the accelerated growth of demanded traffic reaching Exabyte per month. All these processes when performed in the electronic domain require optical/electrical (O/E) conversion that introduces complexities and delays. Therefore, by using allphotonic DRoF more operations and signal processing centralisation at the CS would be achievable. The main challenges in the electronic DRoF link implementation are: high-speed ADC and DAC, dispersions, nonlinearities (in electrical and optical domains), additive noise, integration of system and devices, size and system cost.

An o-DRoF transmitter may comprise an RF interface circuit connected to an optical sampler, which is it connected to an all-optical encoder. Alternatively, if an analogue RoF signal is already available, the o-DRoF transmitter comprises the optical sampler and the all-optical encoder. After the encoder an additional circuit (thresholder) is generally needed in order to enhance the contrast between the optical bits [START_REF] Ribeiro | A Thresholder for All-Optical Digitising Radio-over-Fibre Transceivers[END_REF].

To the best of our knowledge, no complete experimental o-DRoF communication system has been reported in the literature. However, some recently published papers [START_REF] Abdollahi | Fully-Photonic Analogue-to-Digital Conversion Technique for Super-Broadband Digitized-Radio over Fibre Link[END_REF][START_REF] Abdollahi | Digital Radio over Fibre for Future Broadband Wireless Access Network Solution[END_REF][START_REF] Abdollahi | Non-Uniform Wavelength Allocation in All-Photonic Digitized-Radio over Fibre Access Network[END_REF] from Brunel University (UK) report valuable theoretical simulations of an o-DRoF system but without any detailed description of the operational principles of both all-optical ADC and DAC.

At least, an optical ADC (o-ADC) should be able to optically sample the incoming analogue signal, to encode, to quantize and eventually to automatically amplify the output optical bits [START_REF] Abdollahi | Digital Radio over Fibre for Future Broadband Wireless Access Network Solution[END_REF][START_REF] Ribeiro | A Thresholder for All-Optical Digitising Radio-over-Fibre Transceivers[END_REF]. In this paper, we propose the use of chained optical circuits based on the SLALOM configuration in the cross-switched regime to provide an o-Encoder. Computer simulation results on VPI Transmission Maker TM software are presented for the 1550 nm wavelength window, 2.5 GHz repetition rate with 40-ps RZ control pulses. Since the proposed optical circuits use a laser amplifier as the nonlinear optical element, they may potentially perform additional functions, such as: wavelength conversion (present paper), data regeneration, clock recovery [START_REF] Phillips | Simultaneous demultiplexing, data regeneration, and clock recovery with a single semiconductor optical amplifier-based nonlinear-optical loop mirror[END_REF] and modulation format conversion [START_REF] Yang | Application of Semiconductor Optical Amplifiers in High-Speed All-Optical NRZ to RZ Format Conversion, ICTON 2007[END_REF]. The o-DRoF systems may well integrates into the next generation of all-photonic telecommunication networks [START_REF] Abdollahi | Fully-Photonic Analogue-to-Digital Conversion Technique for Super-Broadband Digitized-Radio over Fibre Link[END_REF][START_REF] Abdollahi | Digital Radio over Fibre for Future Broadband Wireless Access Network Solution[END_REF][START_REF] Abdollahi | Non-Uniform Wavelength Allocation in All-Photonic Digitized-Radio over Fibre Access Network[END_REF][START_REF] Viglienzoni | Net! Works -Next Generation Network: Wireless-Optics Technology[END_REF] and provides the connection between the access and the metropolitan network or even the high-capacity transport networks.

II. ALL-OPTICAL DIGITISING RADIO-OVER-FIBRE

TRANSMITTER (O-DROF-T) This section proposes an o-DRoF-T able to simultaneously perform signal digitisation and wavelength conversion in the optical domain. The transmitter essentially comprises an o-ADC assuming the analogue RoF signal is already available.

Electronic ADC and DAC boards seem to exhibit an intrinsic limitation in their stability, "bit resolution x input frequency" product and data conversion rates of up to a few tenths of GSa/s [START_REF] Abdollahi | Fully-Photonic Analogue-to-Digital Conversion Technique for Super-Broadband Digitized-Radio over Fibre Link[END_REF][START_REF] Abdollahi | Digital Radio over Fibre for Future Broadband Wireless Access Network Solution[END_REF][START_REF] Abdollahi | Non-Uniform Wavelength Allocation in All-Photonic Digitized-Radio over Fibre Access Network[END_REF][START_REF] Viglienzoni | Net! Works -Next Generation Network: Wireless-Optics Technology[END_REF][START_REF] Miyoshi | All-Optical Analog-to-Digital Conversion Using Splitand-Delay Technique[END_REF].

Since the end of the 1970's, the vast majority of all-optical ADC and DAC systems have always been separately reported and for various types of applications, but excluding any communication link application. To our knowledge, no complete experimental o-DRoF link system has ever been reported in the literature.

Figure 1 depicts a flowchart of the basic transmitter module architecture of an o-DRoF link [START_REF] Miyoshi | All-Optical Analog-to-Digital Conversion Using Splitand-Delay Technique[END_REF][START_REF] Currie | High-Performance Photonic Analog-to-Digital Converter and Low-Noise Mode-Locked Fiber Laser[END_REF] able to digitise RoF signals.

The o-DRoF-T comprises at least five main optical submodules: (1) optical pulse generator or o-Generator, (2) optical sampler or o-Sampler [START_REF] Ribeiro | An All-Optical Sampler for Digitising Radio-over-Fibre Transceivers[END_REF], (3') and (3'') temporal interleavers or o-Interleaver, (4) optical encoder or o-Encoder and (5) optical thresholder or o-Thresholder [START_REF] Ribeiro | A Thresholder for All-Optical Digitising Radio-over-Fibre Transceivers[END_REF]. The o-Sampler [START_REF] Ribeiro | An All-Optical Sampler for Digitising Radio-over-Fibre Transceivers[END_REF] carries out the optical sampling of an input analogue RoF signal and is driven by an optical pulse comb that in turn is generated by the o-Generator. This pulse comb is also used as a reference clock signal by the o-Encoder that optically encodes the sampled signal, thereby accomplishing the photonic AD-conversion itself. The o-Thresholder [START_REF] Ribeiro | A Thresholder for All-Optical Digitising Radio-over-Fibre Transceivers[END_REF] is provided mainly to significantly enhance the contrast between the "0" and "1" optical bits at the output of the o-Encoder and automatically providing amplification. The o-Generator is rather implemented by a mode-locked laser, a key component used to generate a series of picoseconds pulses at GHz rates with high temporal stability, i.e. with very low jitter in the femtoseconds time-scale [START_REF] Miyoshi | All-Optical Analog-to-Digital Conversion Using Splitand-Delay Technique[END_REF][START_REF] Currie | High-Performance Photonic Analog-to-Digital Converter and Low-Noise Mode-Locked Fiber Laser[END_REF]. Therefore, these pulses can be used as the clock signal for the optical sampling and encoding steps. The interleavers (3') and (3'') essentially multiply the repetition rate of the clock signal generated by the o-Generator (1) as is explained further in section III.B.

III. THE OPERATIONAL PRINCIPLE OF THE O-ENCODER

A. General

Sagnac interferometric fibre rings have been used as a nonlinear device based on self-phase modulation (SPM) or cross-phase modulation (XPM) -Nonlinear Optical Loop Mirrors (NOLMs) -that are very useful for many ultrafast signal-processing applications [START_REF] Miyoshi | All-Optical Analog-to-Digital Conversion Using Splitand-Delay Technique[END_REF][START_REF] Huang | All-Optical OOK to 16-QAM Modulation Format Conversion Employing Nonlinear Optical Loop Mirror[END_REF]. However, for fibre lengths greater than a few hundred meters, the stability of the NOLM is significantly degraded. Furthermore, the long fibre introduces excessive latency for some optical processing applications [START_REF] Cotter | Nonlinear Optics for High-Speed Digital Information Processing[END_REF].

The use of a laser amplifier as a nonlinear medium instead of the optical fibre leads to an interesting class of devices usually named as SLALOM [START_REF] Eiselt | Optical Loop Mirror with Semiconductor Laser Amplifier[END_REF] or Terahertz Optical Asymmetric Demultiplexer (TOAD) [START_REF] Sokoloff | A Terahertz Optical Asymmetric Demultiplexer (TOAD)[END_REF] depending on application.

The optical circuits of the o-Sampler, o-Interleaver, o-Encoder and o-Thresholder were designed and simulated using VPI Transmission Maker TM software. However, in this paper only the results for the o-Encoder are presented. All circuits were probed at 1550 nm wavelength window with 2.5 GHz repetition rate (5.0 Gbit/s), 20-ps time-width RZ pulse stream (40-ps for the control pulses). The peak power (P control ) of the control pulses could be varied from few µW to mW in order to obtain the transfer function, i.e. the P output x P control curves.

The input probe and control pulses at 1554.0 nm and 1562.1 nm wavelengths, respectively, were both generated from a continuous-wave laser diode with null linewidth after traversing a Mach-Zehnder modulator (MZM). The MZM is biased at the quadrature point and is driven by 5.0 Gbit/s RZ electrical pulses in an alternate pattern with 0.1 or 0.05 dutycycle.

The optical circuits of the o-Encoder, o-Sampler and o-Thresholder [START_REF] Ribeiro | A Thresholder for All-Optical Digitising Radio-over-Fibre Transceivers[END_REF] are Sagnac interferometers using fibrecouplers with a coupling ratio equal to 50:50, thus allowing a maximum interference visibility contrast. The insertion of an attenuator (passive component) in the Sagnac fibre ring provides the breaking of reciprocity and an increase in optical power equalisation between the clockwise (CW) and counterclockwise (CCW) pulses. This is because there are different amplifying gains. The SOA is modelled as to be isotropic. The CW and CCW pulses polarisation are assumed to be always aligned. The polarisation alignment can be achieved in practice by using polarisation controllers in the optical circuits or by using polarisation-maintaining fibres.

B. The o-Interleaver

Figure 2 shows the proposed fibre-optic circuit of the o-Interleavers (3') and (3'') suitable for 3-bits resolution.

The circuit uses four 3-dB fibre-couplers (FC), two delay lines and two variable optical attenuators (Att). By appropriately setting the attenuations and the delays, it is possible to generate three temporally interleaved pulses from each sampled pulse. Such three pulses frame may presents either required pattern of peak power. As will be explained ahead, such a pattern as the one generated by the (3') o-Interleaver is needed to correctly operate the o-Encoder. The (3'') o-Interleaver is setting with Att1 = Att2 = 0-dB attenuation thus producing interleaved pulses with the same amplitude. Each sampled pulse generated by the o-Sampler [START_REF] Ribeiro | An All-Optical Sampler for Digitising Radio-over-Fibre Transceivers[END_REF] submodule at sampling frequency f S is processed by the o-Interleaver (3'), thus producing three temporally interleaved pulses at 3f S repetition frequency. The most intense of these pulses will present P 3 peak power, while the second will present P 2 =P 3 /2. For an ideal transfer function (following (1)) the amplitude of the first (weaker) pulse would be P 1 = P 2 /2 = P 3 /4.

C. The chained o-Encoders

Figure 3 shows two chained nonlinear Sagnac fibreinterferometers where the transmitted output of the first ring after traversing an optical attenuator, is launched in the second fibre ring as to be the control light. The chain may be extended to contain three or more Sagnac rings following the same pattern. The transfer function of an ideal Sagnac interferometer is given by (1).

€ P T 1 = P IN 1 2 1-cos Δφ ( ) [ ] (1)
In ( 1), P IN , € P T 1 , and Δφ represent respectively the input peak power, transmitted peak power and the differential phase-shift between the CW and CCW pulses. The differential phase-shift depends on the optical nonlinear strength γ, the length L SOA of the SOA inserted in the ring and the control power (peak) P C. as given by [START_REF] Nirmalathas | Digitized Radio-Over-Fiber Technologies for Converged Optical Wireless Access Network[END_REF].

€ Δφ = 2γL SOA P C (2)
The SOA inserted in the Sagnac ring is an active element and the output signal will be optically amplified, i.e. P T > P IN and usually P T > P C . Therefore, an optical attenuator (of α attenuation) should be inserted between each pair of Sagnac rings in order to fit the amplitude of the control pulses at P T /α, in such a way that (P T ) max /α = (P IN ) max . As a result, the output € P T 2 from the second Sagnac ring is given by (3).

€ P T 2 = P IN 1 2 1-cos 2γL SOA P T 1 α             (3)
After inserting (2) in (1) and then substituting the resulting equation in (3), one obtains the response (transfer function) of the two cross-chained Sagnac rings as given by (4).

€ P T 2 = P IN 1 2 1-cos 2 γ α L SOA P IN 1 2 1-cos 2γL SOA P C ( ) [ ]             (4)
Figure 4 shows comparatively the plots of 1-stage and 2stage chained o-Encoders based on an ideal Sagnac fibre-optic interferometer.

The 1-stage transfer function reaches Δφ max = 2π and is suitable for 2-bit resolution (see the explanation accompanying Figure 6 and reference [START_REF] Miyoshi | All-Optical Analog-to-Digital Conversion Using Splitand-Delay Technique[END_REF]). The 2-stage transfer function can reach Δφ max = 4π using the same peak power of the control light. One extra bit resolution is achieved for each o-Encoder stage added in the circuit of Figure 3. The 1-stage transfer function now reaches Δφ max = 4π and is suitable for 3-bit resolution (see Figure 6 and reference [START_REF] Miyoshi | All-Optical Analog-to-Digital Conversion Using Splitand-Delay Technique[END_REF]). However, the 2-stage transfer function now can reaches Δφ max = 16π using the same peak power of the control light. Now, two extra bit resolution is achieved for each o-Encoder stage added in the circuit of Figure 3.

Figure 6 reproduces the 2-stage plot of Figure 4 (Δφ max = 2π) and illustrates the process of digital coding using the (2stage) o-Encoder able to provide the Gray-code with 3-bits resolution [START_REF] Miyoshi | All-Optical Analog-to-Digital Conversion Using Splitand-Delay Technique[END_REF][START_REF] Taylor | An Optical Analog-to-Digital Converter-Design and Analysis[END_REF].

In order to enable the 3-bit resolution, the threshold level is placed at ~20% of the maximum transmitted power instead of the conventional 50% [START_REF] Miyoshi | All-Optical Analog-to-Digital Conversion Using Splitand-Delay Technique[END_REF]. The abscissa of Figure 6 is sectioned in eight (2 3-bit =8) "slots" of the same width. As an example of generation of the digital Gray-code, assume an optical sample of P 3 = 5.86 rad amplitude that lies in the middle of the rightmost "slot". The circuit of Figure 2 when properly set is able to generate interleaved pulse replicas with P 2 = P 3 /2 = 2.93 rad and P 1 = P 2 /2 = 1.47 rad. By simply inspecting Figure 6, P 1 , P 2 and P 3 corresponds to "1", "0" and "0" bits, respectively, i.e. the "100" sequence. Now, following the reasoning and starting with P 3 = 5.09 rad that lies in the middle of the next "slot", P 2 = 2.55 rad and P 3 = 1.27 rad are generated by the o-Interleaver circuit. The "101" digital code sequence is now generated. The remaining Gray-code sequences may be generated unambiguously in the same way.

The same procedure may be performed for the 2-stage transfer function suitable for 5-bit resolution as shown in Figure 5. A simple inspection shows that the cycles are steeper and the threshold level should be placed at < 20% of the maximum transmitted power. It is a relatively difficult task to obtain an ideal transfer function even using optical fibres as the nonlinear optical element [START_REF] Miyoshi | All-Optical Analog-to-Digital Conversion Using Splitand-Delay Technique[END_REF]. The deviation from ( 1) is usually more severe when a SOA is used instead of an optical fibre (see section IV).

D. The o-Thresholder

The o-Thresholder based on the use of SOA as the nonlinear optical element is described in details in reference [START_REF] Ribeiro | A Thresholder for All-Optical Digitising Radio-over-Fibre Transceivers[END_REF]. Figure 7 depicts the general fibre-optic circuit of the proposed o-Thresholder operating in self-switching regime.

The typical transfer function of the o-Thresholder [START_REF] Ribeiro | A Thresholder for All-Optical Digitising Radio-over-Fibre Transceivers[END_REF] resembles that of the laser diode. From P input = 0 to a threshold P input = P th input power, the device is able to practically block the transmitted output light. This is because P input is very low and the differential phase-shift is not enough to produce significant switching from the reflection to the transmission port of the interferometer. From P input = P th to P input = P lim input power, the device presents a transition region thus reaching a limited output power for P input > P lim . The limiting region is achieved due to saturation of available carriers thus significantly decreasing the self-phase modulation strength when the input light power continues to increase. All characteristic powers and speed of the o-Thresholder transfer function may be tuned once the circuit parameters are properly set, e.g. attenuation Att, bias current I DC of the SOA and the asymmetry x. It should be observed that the real control peak power is the half of those shown in the abscissa of Figure 8 (and of Figure 9). The reason is because a conventional 3 dB fibreoptic coupler is used instead of a WDM-coupler to launch the control power in the SOA (see Figure 3). The 1-stage transfer function achieved is highly asymmetric. Only P π ~ 60 µW is needed to achieve a complete switching, i.e. from Δφ = 0 to Δφ = π rad, while P 2π ~ 230 µW is needed to reach Δφ = 2π rad. A ratio of P 2π / P π = 2.00 should be presented by a symmetric transfer function, but the P 2π / P π = 230/60 = 3.83 ratio was really achieved. One reason behind this asymmetry is the fact that the SOA is operating in a non-saturated regime where the non-linearity is very strong and highly dependent on the number of carriers. When the control power is increased the number of available carriers decreases and the non-linearity strength also decreases. Therefore, more power (> 60 µW) is needed for switching from Δφ = π to Δφ = 2π. The consequence of such asymmetry is seen in the 2-stage transfer function plot also shown in Figure 8. Although, the transfer function still presents two cycles as in the ideal o-Encoder of Figures 4 and6, now it is no longer possible to unambiguously generate the Gray-code digital sequences.

Figure 9 shows the result of the computer simulation of the 1-stage o-Encoder circuit of Figure 3 using L SOA = 300 µm and I DC = 250 mA. Now, P π ~ 275 µW is needed to achieve a complete switching, while P 2π ~ 675 µW. The P 2π / P π = 675/275 = 2.45 ratio was achieved meaning that the transfer function is now reasonably closer to the symmetric shape when compared with Figure 8. Because the L SOA is reduced from 500 to 300 µm, the nonlinear optical effects are weaker since π and P 2π are both increased, even taking into account that the I DC is increased from 200 to 250 mA. The choice of 12 dB attenuation between the stages of chained o-Encoder is because the 7.25 mW maximum power transmitted from the first circuit should be reduced to reach 460 µW (before the 3dB fibre-coupler) maximum as is required for Δφ = 2π rad. The SOA itself is a relatively complex device to be designed, even though specific SOAs intended to optical signal processing are already available in the market. It should be treated not only as an optical amplifier but also as a nonlinear waveguide where the control and probe pulses are propagating and interacting with each other. Its dynamics of operation is not trivial. When the SOA is placed in a fibreoptic Sagnac ring (see Figure 3) and control and probe light is launched, the 1-stage or 2-stage o-Encoder has to be even more complex to be properly designed. Besides those parameters which are adjusted here, many others can (or should be) simultaneously be taken into account such as wavelengths of the control and probe pulses, asymmetry of the SOA in the Sagnac ring, the use of a continuous wave holding beam [START_REF] Manning | Three-wavelength device for alloptical signal processing[END_REF] to obtain gain saturation and faster nonlinearities, semiconductor structure and length of the SOA, etc.

According to section III, since at least a symmetric transfer function of (Δφ) max = 2π rad (one cycle) using 1-stage o-Encoder is achieved, it turns out to be possible to reach 2-bit, 3-bit, 4-bit,…(n+1)-bit resolution by using 1, 2, 3,…n chained o-Encoders as the scheme of Figure 3. Nevertheless, if a symmetric transfer function of (Δφ) max = 4π rad (two cycles) using 1-stage o-Encoder could be achieved, now it turns out to be possible to reach 3-bit, 5-bit, 7-bit,…(2n+1)bit resolution by using 1, 2, 3,…n chained o-Encoders. Therefore, the bit resolution is highly enhanced. It should be noted that the bit resolution is increased by increasing the number of "o-Encoder links" and the speed can be maintained fast if the P out x P control response of each "link" is bounded to (Δφ) max = 2π, i.e. with reduced optical nonlinear effect (XPM) strength.

For the sake of simplicity, the 2-stage plot of Figure 8 was calculated with the same control and probe wavelengths as were used in the 1-stage simulation.

Fig. 1 .

 1 Fig. 1. The flowchart of the basic o-DRoF-T. The o-Encoder sub-module treated is this paper is highlighted and numbered as (4).

Fig. 2 .

 2 Fig. 2. The general fibre-optic circuit of the o-Interleavers suitable for 3-bits resolution.

Fig. 3 .

 3 Fig. 3. The general fibre-optic circuit of two chained o-Encoders.

Fig. 4 .

 4 Fig. 4. The plots of the 1-stage (Δφmax = 2π) -2-bits -and 2-stage -3-bitstransfer function o-Encoders based on an ideal Sagnac fibre-optic interferometer.

Figure 5

 5 Figure 5 shows comparatively the plots of 1-stage and 2stage chained o-Encoders based on an ideal Sagnac fibre interferometer, but now starting with Δφ max = 4π (1-stage).

Fig. 5 .

 5 Fig. 5. The plots of the 1-stage (Δφmax = 4π) -3-bits -and 2-stage -5-bitstransfer function o-Encoders based on an ideal Sagnac fibre interferometer.

Fig. 6 .

 6 Fig. 6. The transfer function plot of the 2-stage o-Encoders illustrating the process of generation of the Gray-code based optical bits with 3-bits resolution. An ideal Sagnac fibre interferometer is assumed. The threshold level is the dotted horizontal line placed at ~20% of the maximum transmitted power.

Fig. 7 .

 7 Fig. 7. The general fibre-optic circuit of the o-Thresholder.

Figure 8

 8 Figure 8 shows the result of the computer simulation of the 1-stage and 2-stage o-Encoder circuit of Figure 3 using L SOA = 500 µm, I DC = 200 mA and 12 dB attenuation between the circuits.

Fig. 8 .

 8 Fig. 8. Simulations of the transfer function as designed with 1-stage and 2stage chained o-Encoders fibre-optic circuit using 12 dB attenuation, LSOA = 500 µm and IDC = 200 mA.

Fig. 9 .

 9 Fig. 9. Simulations of the transfer function as designed with 1-stage o-Encoder fibre-optic circuit for LSOA = 300 µm and IDC = 250 mA. The asymmetry is reduced.

Ricardo M. Ribeiro thanks Foundation Capes/MEC-Brasil for the financial support through a Post-Doctoral fellowship under the grant BEX 9096/11-6.

ACKNOWLEDGMENT Ricardo M. Ribeiro thanks the team at Département d'Optique of Telecom Bretagne and the CapilR TM platform for hosting his Post-Doctoral study during which the present work was carried out. The authors also thank INCT-Fotonicom/CNPq.

V. CONCLUSIONS

To the best of our knowledge, neither experimental nor commercially available o-DRoF links or networks have been reported as they are still under R&D stage. This paper proposes a transmitter module comprising at least five optical sub-modules for use in an o-DRoF link. It was designed and simulated here only the o-Encoder sub-module operating at 1550 nm wavelength window. The proposed chained o-Encoders when compared with similar devices built using fibre as an nonlinear optical element [START_REF] Miyoshi | All-Optical Analog-to-Digital Conversion Using Splitand-Delay Technique[END_REF] may provide some advantages: compactness, prone to optical integration, requirement of ~10 3 less optical power and amplified output optical bits. D. Cotter et al also describe the implementation of a SLALOM circuit on a single 1x2 mm InP semiconductor chip [START_REF] Cotter | Nonlinear Optics for High-Speed Digital Information Processing[END_REF] that supports the possibility of optical integration of the proposed o-DRoF-T.

In this paper, the simulations were constrained to only 2.5 GHz & 40-ps RZ input control pulses mainly to demonstrate the proof-of-principle of the o-Encoder. However, SOAs operating at 80 Gb/s are already commercially available [START_REF]Nonlinear SOA from Amphotonix[END_REF]. Furthermore, SOAs in R&D stage able to operate up to 160 Gb/s [START_REF] Szuki | Error-free demultiplexing of 160 Gbit/s pulse signal using optical loop mirror including semiconductor laser amplifier[END_REF] and beyond [START_REF] Liu | Error-Free 320-Gb/s All-Optical Wavelength Conversion Using a Single Semiconductor Optical Amplifier[END_REF] have already been reported.

Simulations and experiments of the chained o-Encoders operating at higher pulse rate with shorter timewidth, other independent sub-modules of the proposed o-DRoF-T as well such transmitter as a whole are currently planned or in progress and will be presented in a near future.


Michel Granger
email: granger@univ-angers.fr

Mathias Schulze
email: mschulze@mathematik.uni-kl.de

DERIVATIONS OF NEGATIVE DEGREE ON QUASIHOMOGENEOUS ISOLATED COMPLETE INTERSECTION SINGULARITIES

Keywords: Mathematics Subject Classification. 13N15, 14M10 (Primary) 14H20 (Secondary) complete intersection, derivation, singularity

Wahl conjectured that every quasihomogeneous isolated normal singularity admits a positive grading for which there are no derivations of negative weighted degree. We confirm his conjecture for quasihomogeneous isolated complete intersection singularities of either order at least 3 or embedding dimension at most 5. For each embedding dimension larger than 5 (and each dimension larger than 3), we give a counter-example to Wahl's conjecture.

Introduction

By a singularity we mean a quotient A of a convergent power series ring over a valued field K of characteristic zero (see §1). We use the acronym negative derivation for a derivation of negative weighted degree on a quasihomogeneous singularity. The question of existence of such negative derivations has important consequences in rational homotopy theory (see [START_REF] Meier | Rational universal fibrations and flag manifolds[END_REF]Thm. A]) and in deformation theory (see [Wah82, Thm. 3.8]).

By a result of Kantor [START_REF] Kantor | Rectificatif à la note: "Dérivations sur les singularités quasi-homogènes: cas des courbes[END_REF], quasihomogeneous curve and hypersurface singularities do not admit any negative derivations. J. Wahl [Wah82, Thm. 2.4, Prop. 2.8] reached the same conclusion in (the much deeper) case of quasihomogeneous normal surface singularities. Motivated by his cohomological characterization of projective space in [START_REF] Wahl | A cohomological characterization of P n[END_REF], he formulates the following conjecture in [START_REF] Wahl | Derivations, automorphisms and deformations of quasihomogeneous singularities[END_REF]Conj. 1.4].

Conjecture (Wahl). Let R be a normal graded ring, with isolated singularity. Then there is a normal graded R, with R ∼ = R, so that R has no derivations of negative weight.

In case R is a graded normal locally complete intersection with isolated singularity, R becomes a quasihomogeneous normal isolated complete intersection singularity (ICIS) and Wahl's conjecture can be rephrased as follows (see Lemma 5 and Remark 7).

Conjecture (Wahl, ICIS case). Any quasihomogeneous normal ICIS has no negative derivations with respect to some positive grading.

For quasihomogeneous normal ICIS, there is an explicit description of all derivations due to Kersken [START_REF] Kersken | Reguläre Differentialformen[END_REF]. Based on this description, we prove our main Theorem 1. For any quasihomogeneous normal ICIS of order at least 3 there are no negative derivations with respect to any positive grading.

Proof. This follows from Corollary 12 and Proposition 16.

Our investigations lead to a family of counter-examples to Wahl's Conjecture. In order to describe it, we first fix our notation. A quasihomogeneous singularity can be represented as (0.1) A = P/a, a = g 1 , . . . , g t K x 1 , . . . , x n =: P where g 1 , . . . , g t are homogeneous polynomials of degree p i := deg(g i ) with respect to weights w 1 , . . . , w n ∈ Z + on the variables x 1 , . . . , x n (see §1). We order these weights and degrees decreasingly as

w 1 ≥ • • • ≥ w n > 0, (0.2) p 1 ≥ • • • ≥ p t .
Example 2. Let n ≥ 6 and pick c 7 , . . . , c n ∈ K \ {1} pairwise different such that c 9 i + 1 = 0 for all i. Assigning weights 8, 8, 5, 2, . . . , 2 to the variables x 1 , . . . , x n , the equations

g 1 :=x 1 x 4 + x 2 x 5 + x 2 3 -x 5 4 + n i=7
x 5 i (0.3)

g 2 :=x 1 x 5 + x 2 x 6 + x 2 3 + x 5 6 + n i=7 c i x 5
i define a quasihomogeneous complete intersection A as in (0.1) with isolated singularity. On A there is a derivation

(0.4) η := ∂ 1 ∂ 2 ∂ 3 x 4 x 5 2x 3 x 5 x 6 2x 3 = 2x 3 (x 5 -x 6 )∂ 1 -2x 3 (x 4 -x 5 )∂ 2 + (x 4 x 6 -x 2 5 )∂ 3
of degree -1. We work out the details of this example in §4.

We show that Example 2.8 gives a counter-example to the ICIS case of Wahl's conjecture of minimal embedding dimension n = 6. Theorem 3. Exactly up to embedding dimension 5, all quasihomogeneous ICIS have no negative derivations with respect to some positive grading.

Proof. This follows from Kantor [START_REF] Kantor | Rectificatif à la note: "Dérivations sur les singularités quasi-homogènes: cas des courbes[END_REF], [Wah82, Thm. 2.4, Prop. 2.8], Proposition 18, Example 2 and Corollary 12.

As a consequence of our arguments we obtain a simple special case of the following conjecture due to S. Halperin.

Conjecture (Halperin). On any graded zero-dimensional complete intersection there are no negative derivations.

The following result bounds the degree of negative derivations (see also [START_REF] Aleksandrov | Vector fields on a complete intersection[END_REF]Prop.]). The bound does not require a complete intersection hypothesis and it is independent of further hypotheses as for instance in [Hau02, Thm. 2].

Proposition 4. For any quasihomogeneous zero-dimensional singularity A as in (0.1) there are no derivations of degree strictly less than p n -p 1 . In particular, Halperin's conjecture holds true if p 1 = p n .

Proof. As A is assumed to be zero-dimensional, condition A(k) on page 4 must hold true for all k = 1, . . . , n. Then the claim follows from Remark 14 and Lemma 15.

Acknowledgments. The second author would like to thank the LAREMA at the University of Angers for providing financial support and a pleasant working atmosphere during his research visit in February 2014.

Graded analytic algebras

Consider a (local) analytic algebra A = (A, m A ) over a (possibly trivially) valued field K of characteristic zero. We assume in addition that A is non-regular and can be represented as a quotient A = P/a of a convergent power series ring P := K x 1 , . . . , x n a. In the sequel such an A will be referred to as a singularity. We choose n minimal such that n = embdim A and set d := dim A.

A K + -grading on A is given by a diagonalizable derivation χ ∈ Der K A =: Θ A which means that m A is generated by eigenvectors x 1 , . . . , x n (see [START_REF] Scheja | Über Derivationen von lokalen analytischen Algebren[END_REF](2.2),(2.3)]). Such a derivation is also called an Euler derivation. We refer to w 1 , . . . , w n defined by w i := χ(x i )/x i as the eigenvalues of χ. More generally, we call χ-eigenvectors f ∈ A homogeneous and define their degree to be the corresponding eigenvalue denoted by deg(f ) := χ(f )/f ∈ k. We denote by A a the K-vector space of all such eigenvector f ∈ A with deg(f ) = a. This defines a K-subalgebra

(1.1) Ā := a∈K A a ⊂ A ⊂ Â.
The derivation χ ∈ Θ A lifts to χ ∈ Θ P := Der K P (see [SW73, (2.1)]). In particular, P is K + -graded and a P is a χ-invariant ideal and hence homogeneous (see [START_REF] Scheja | Über Derivationen von lokalen analytischen Algebren[END_REF] (2.4)]). Pick homogeneous g 1 , . . . , g t ∈ a inducing a K-vector space basis of a/m A a. Then a = g 1 , . . . , g t by Nakayama's Lemma. We set p i := deg(g i ) ordered as in (0.2). To summarize, we can write A as in (0.1).

A K + -grading is called a positive grading if w i ∈ Z + for all i = 1, . . . , n (see [SW73, §3, Def.]). We call A quasihomogeneous if it admits a positive grading. In this case, we shall always normalize χ to make the w i coprime and order the variables according to (0.2). Positivity of weights enforces

g i ∈ P = K[x 1 , . . . , x n ] and that (1.2) Ā = i≥0 A i = P /ā, ā = g 1 , . . . , g t K[x 1 , . . . , x n ] = P , is a (positively) graded-local k-algebra with completion (1.3) Â = Â
and graded maximal ideal m Ā = mA := i>0 A i . The preceding discussion enables us to reformulate Wahl's Conjecture in the language of Scheja and Wiebe as follows.

Lemma 5. The following supplementary structures on a singularity A are equivalent:

(1) an Euler derivation χ on A with positive eigenvalues, (2) a positive grading on A, (3) a positive grading on Â, (4) a (positively) graded K-algebra Ā such that  = Â.

Proof. The equivalences of (1), (2), and (3) are due to Scheja and Wiebe (see [START_REF] Scheja | Über Derivationen von lokalen analytischen Algebren[END_REF] (2.2),(2.3)] and [SW77, (1.6)]). For the equivalence with (4), note that the obvious Euler derivation on a graded K-algebra Ā lifts to an Euler derivation on the completion  = Â. The converse follows from from (1.1), (1.2) and (1.3).

Let us assume now that A is an isolated complete intersection singularity (ICIS). We may then take g 1 , . . . , g t to be a regular sequence and d + t = n. The isolated singularity hypothesis can be expressed in terms of the Jacobian ideal (1.4)

J A := ∂g ∂x ν | |ν| = t A of A as follows.
Proposition 6. A complete intersection singularity A is isolated if and only if J A is m A -primary. An analogous statement holds for Ā.

Proof. We denote by Ω 1 A/k the universally finite module of differentials of A over k. By the standard sequence

a/a 2 / / A ⊗ P Ω 1 P/k / / Ω 1 A/k / / 0, the Jacobian ideal J A is the 0th Fitting ideal F 0 A Ω 1 A/k
. By [SS72, (6.4),(6.9)], reducedness of

A is equivalent to rk Ω 1 A/k = d and A p is regular if and only if Ω 1 Ap/k is free. Hence, A p being regular is equivalent to p ⊃ F 0 A Ω 1 A/k = J A by [BH93, Lem. 1.4.9].
In particular, A having an isolated singularity means exactly that A/J A is supported at m A and hence that J A is m A -primary as claimed. The analogous statement for Ā is proved similarly.

Remark 7. Let A be a quasihomogeneous singularity. By (1.2), (1.5)

J Ā := JA = ∂g ∂x ν | |ν| = t Ā
is the Jacobian ideal of Ā defined analogous to (1.4 Scheja and Wiebe [SW77, (3.1)] (see also [Sai71, Satz 1.3]) proved that any K + -graded ICIS is quasihomogeneous unless t = 1 and g 1 / ∈ m 3 P . Their starting point (see [SW77, (2.5)] and [Sai71, Lem. 1.5]) is that A being an ICIS implies, by Proposition 6, that for each k = 1, . . . , n one of the following two conditions must holds true.

A(k) For some m ≥ 2 and 1 ≤ j ≤ t, the monomial x m k occurs in g j . B(k) For some pairwise different 1 ≤ ν 1 , . . . , ν t ≤ n, each g j contains a monomial x m j k x ν j for some m j ≥ 1. The following result gives numerical constraints for A to be a quasihomogeneous ICIS.

Lemma 8. If A is a quasihomogeneous ICIS then (1.6) p 1 + • • • + p j ≥ w 1 + • • • + w j + j
for all j = 1, . . . , t.

Proof. We proceed by induction on j. Assume that

p 1 +• • •+p j-1 ≥ w 1 +• • •+w j-1 +j -1 but p 1 + • • • + p j ≤ w 1 + • • • + w j + j -1.
Then p j ≤ w j and hence g i = g i (x j+1 , . . . , x n ) for all i = j, . . . , n. Then J A maps to zero in A/ x j+1 , . . . , x n = K x 1 , . . . , x j / g 1 , . . . , g j-1

and hence J A cannot be m A -primary as required by Proposition 6.

Negative derivations

Let A be a quasihomogeneous singularity as in §1. The target of our investigations is the positively graded A-module Θ A = Der K A of K-linear derivations on A. More precisely, we are concerned with the question whether its negative part

Θ A,<0 = Θ Ā,<0 = i<0 Θ A,i
is trivial. A priori this condition depends on the choice of a grading. In Proposition 9 below, we shall prove the independence of this choice for a general singularity under a strong hypothesis satisfied in the ICIS case (see Corollary 12). To this end, we write (see [SW73, (2.1)]) Proposition 9. Let A be a quasihomogeneous singularity with positive grading given by χ and assume that Θ a⊂P = P χ + Θ ′ P + aΘ P , (2.2)

for some Θ ′ P ⊂ m 2 P Θ P . (2.3)
Then the condition Θ A,<0 = 0 and the p 1 , . . . , p t in (0.2) are independent of the chosen positive grading.

Proof. Consider a second positive grading with corresponding Euler derivation χ ′ (see Lemma 5). By (2.1) and (2.2), any δ ∈ Θ A lifts to an element of Θ a⊂P of the form (2.4) δ = cχ + δ + , δ + = aχ + η, c ∈ K, a ∈ m P , η ∈ Θ ′ P , denoted by the same symbol. By (2.3) and the Leibniz rule, (2.5)

χm k P ⊂ m k P , δ + m k P ⊂ m k+1 P
for all k ≥ 1. Specializing to δ = χ, this implies that χ + = 0 and χ ′ = cχ on m A /m 2 A = m P /m 2 P and hence c = 1 by the definition of a positive grading and our normalization of weights.

Using (2.1), we equip Θ A with the decreasing m P -adic filtration F • induced from Θ P which is defined as follows F k Θ A = (Θ a⊂P ∩ m k P Θ P )/(aΘ P ∩ m k P Θ P ). Due to (2.3), (2.4) and (2.5) this is a filtration by (k, P )-Lie ideals and

δ + F k Θ A ⊂ F k+1 Θ A
for the adjoint action of δ + . Therefore, for any k ≥ 1, the adjoint action of χ ′ = χ + χ + on the truncation

F ≤k Θ A := Θ A /F k+1 Θ A
is triangularizable with semisimple part equal to that of χ. Thus, χ ′ and χ have the same eigenvalues on F ≤k Θ A for any k ≥ 1. The first claim then follows by choosing k sufficiently large. A similar argument yields the second claim.

For a Gorenstein singularity A, there is a natural way to produce elements of Θ A . The A-submodule Θ ′ A ⊂ Θ A of trivial derivations is by definition the image of the inclusion

(2.6) Ω d-1 A/K ֒→ ω d-1 A/K = Hom A (Ω 1 A/K , ω d A/K ) = Θ A ⊗ A ω d A/K ∼ = Θ A .
We return to the case of an ICIS singularity A. For 1

≤ ν 0 < • • • < ν t ≤ n with complementary indices 1 ≤ µ 1 < • • • < µ d-1 ≤ n, the lift to P of the image of dx µ 1 ∧ • • • ∧ dx µ d-1
can be written (up to sign) explicitly as

(2.7)

δ ν := ∂ ν 0 • • • ∂ νt ∂ ν 0 g 1 • • • ∂ νt g 1 . . . . . . ∂ ν 0 g t • • • ∂ νt g t . Note that deg δ ν = p 1 + • • • + p t -w ν 0 -• • • -w νt , (2.8) δ ν g j = 0
(2.9) for all j = 1, . . . , t and ν. Consider the P -module (2.10)

Θ ′ P := δ ν | 1 ≤ ν 0 < • • • < ν t ≤ n P ⊂ Θ P .
The key to our investigations is the following result due to Kersken [Ker84, (5.2)]. From now on we assume in addition that A is quasihomogeneous and normal, that is, dim A ≥ 2.

Theorem 10 (Kersken). Let A be a quasihomogeneous normal ICIS. Then the module Θ A of K-linear derivations on A is generated by the Euler derivation χ and the trivial derivations Θ ′ A .

Although Kersken only states that Θ ′

A is minimally generated by the δ ν in (2.7), his arguments show that together with χ they form a minimal set of generators of Θ A . We denote by µ(-) the minimal number of generators.

Corollary 11. Let A be quasihomogeneous normal ICIS. Then Θ A is minimally generated by the Euler derivation χ and the trivial derivations δ ν in (2.7). In particular,

µ(Θ A ) = n t + 1 + 1.
Proof. Since the case d = 2 is covered by [Wah87, Prop. 1.12], we may assume that d ≥ 3. In this case, the inclusion (2.6) fits into the following commutative diagramm with exact rows and columns (see [Ker84, Proof of (4.8)] or [Wah87, Prop. 1.7]).

(2.11) 0 0

0 / / H 1 m A (Ω d A/K ) O O χ ∼ = / / H 1 m A (Ω d-1 A/K ) O O / / 0 0 / / ω d A/K O O χ / / ω d-1 A/K O O χ / / ω d-2 A/K O O 0 / / Ω d A/K O O χ / / Ω d-1 A/K O O χ / / Ω d-2 A/K ∼ = O O 0 O O 0 O O It follows that χ(ω d-1 A/K ) ∼ = χ(Ω d-1 A/K ) ∼ = Ω d-1 A/K /χ(Ω d A/K ) where χ(Ω d A/K ) ⊂ m A Ω d-1 A/K and hence µ(χ(Ω d-1 A/K )) = µ(Ω d-1 A/K ) = µ(Θ ′ A ).
Now the middle row of (2.11) yields an exact sequence

0 / / A χ / / Θ A / / χ(ω d-1 A/K ) ⊗ (ω d A/K ) -1 / / 0 Since χ / ∈ m A Θ A , the claim follows.
Note that Θ ′ P in (2.10) satisfies (2.3) due to (2.7) unless t = 1 and g 1 / ∈ m 3 P . As a consequence of Proposition 9 and Theorem 10 we therefore obtain the following result. It is crucial for Example 2 to be a counter-example to Wahl's Conjecture.

Corollary 12. Let A be a quasihomogeneous normal ICIS. Unless t = 1 and g 1 / ∈ m 3 P , the condition Θ A,<0 = 0 and the p 1 , . . . , p t in (0.2) are independent of the choice of a positive grading.

We shall now derive numerical constraints for minimal negative trivial derivations. To this end, suppose that 0 = η ∈ Θ A,<0 . For reasons of degree (see (0.2)), η can be written as (2.12)

η = q 1 ∂ 1 + • • • q n ∂ n , q i = q i (x i+1 , . . . , x n )
By Theorem 10, we may assume that η = δ ν = 0 is a trivial derivation as in (2.7). By (0.2) and (2.8), we may further assume that ν i = i + 1 for i = 0, . . . , t. Explicitly, we may write (2.13)

q i = (-1) i-1 ∂ 1 g 1 • • • ∂ i g 1 • • • ∂ t+1 g 1 . . . . . . . . . ∂ 1 g t • • • ∂ i g t • • • ∂ t+1 g t , q t+2 = • • • = q n = 0.
Now (2.8) and (2.9) specialize to the following simple Lemma 13. For η as in (2.12) with (2.13), we have

(2.14) ηg j = 0 for all j = 1, . . . , t. If Θ A,<0 = 0 for a quasihomogeneous normal ICIS then

(2.15)

p 1 + • • • + p t < w 1 + • • • + w t+1 .
Remark 14. For degree reasons (see (0.2)), the identity (2.14) holds true for any η ∈ Θ A,<pt-p 1 and any quasihomogeneous singularity A as in (0.1).

We now link the conditions A(k) and B(k) from page 4 to the existence of a negative derivation as in (2.12).

Lemma 15. Assume that the identity (2.14) holds true for all j = 1, . . . , t. Then A(k) implies q k = 0 in (2.12) for a suitable choice of coordinates.

Proof. Pick k ∈ {1, . . . , t + 1} such that A(k) holds. Then some g j contains x m k , m > 1, and all other monomials in g j contain only strictly lower powers of x k by homogeneity. Let t k,j = t k,j (x 1 , . . . , x k , . . . , x n ) denote the coefficient of x m-1 k in g j , and assume, without loss of generality, that the coefficient of x m k is 1 m . Note that t k,j is independent of variables of weight larger than w k . Expanding (2.14) with respect to the variable x k and taking the terms involving x m-1 k gives

q k x m-1 k = q k ∂ k 1 m x m k = - i =k q i ∂ i (t k,j x m-1 k ) = - i =k q i ∂ i (t k,j )x m-1 k and hence (2.16) η = i =k q i • (∂ i -∂ i (t k,j )∂ k ).
The χ-homogeneous coordinate change

x ′ i = x k + t k,j , if i = k, x i , else. replaces ∂ i -∂ i (t k,j )∂ k in (2.16
) by ∂ ′ i , and thus q k in (2.12) by 0. Iterating this process yields the claim.

Our main technical result is the following Proposition 16. Let A be a quasihomogeneous normal ICIS such that Θ A,<0 = 0. Then B(k) holds for at least two indices k ≤ t + 1. Each such k satisfies k ≥ t -d + 2 and g k , . . . , g t / ∈ m 3 P . Proof. By hypothesis and Lemma 15, B(k) holds for some k ≤ t+1 with q k = 0. Assuming that k is unique, (2.9) reads q k ∂ k g j = 0 which would imply that g j is independent of x k for all j = 1, . . . , t. By the isolated singularity hypothesis, this is impossible.

Combining (1.6) and (2.15), we obtain (2.17)

p j + • • • + p t + j ≤ w j + • • • + w t+1
for all j = 1, . . . , t. Using (0.2), B(k) and (2.17) for j = k, we compute

m k w k + • • • + m t w t ≤ (m k + • • • + m t )w k = deg(∂ ν k g k • • • ∂ νt g t ) = p k + • • • + p t -w ν k -• • • -w νt ≤ w k + • • • + w t+1 -k -w ν k -• • • -w νt .
and hence

(m k -1)w k + • • • + (m t -1)w t ≤ w t+1 -k -w ν k -• • • -w νt .
By (0.2), this forces

m k = • • • = m t = 1, (2.18) w t+1 ≥ w ν k + • • • + w νt + k.
In particular,

(2.19) ν k , . . . , ν t ≥ t + 2 and hence k ≥ t -d + 2.

ICIS of embedding dimension 5

Lemma 17. Let A be a quasihomogeneous normal ICIS such that Θ A,<0 = 0. Then A(k 1 ) and B(k 2 ) for {k 1 , k 2 } = {1, 2} is impossible.

Proof. Assuming the contrary, one of the g j has a monomial divisible by x 2 k 1 by A(k 1 ) and each of the g j has a monomial divisible by x k 2 by B(k 2 ). In particular,

p 1 + • • • + p t ≥ 2w k 1 + (t -1)w k 2 ≥ w 1 + • • • + w t+1 contradicting (2.15).
Proposition 18. For any quasihomogeneous ICIS A as in (0.1) with n = 5 and t = 2, we have Θ A,<0 = 0.

Proof. Assume that Θ A,<0 = 0. By Proposition 16 and Lemma 17, we must have B(1) and B(2). Using (0.2), (2.18), and (2.19), we may write

g 1 = x 1 x 4 + c 1 x j 2 x k 1 + • • • g 2 = x 1 x 5 + c 2 x 2 x k 2 + • • •
with {k 1 , k 2 } = {4, 5} and c 1 , c 2 ∈ K * . As in the proof of Lemma 17, the inequality (2.15) can only hold true if j = 1. In this case, A/(J A + x 3 , . . . , x n ) = K x 1 , x 2 / ∂g ∂(x 4 , x 5 ) .

for degree reasons (see (0.2)), and hence J A is not m A -primary. This contradicts to the isolated singularity hypothesis.

Counter-examples

Proof of Example 2. The sequence g is clearly regular and defines a complete intersection as in (0.1). Note that η in (0.4) agrees with η = δ 1,2,3 in (2.12). Since deg(g 1 ) = 10 = deg(g 2 ), (2.9) shows that η has negative degree deg η = -1.

It remains to check that A has an isolated singularity, that is, the Jacobian ideal J A from (1.4) is m A -primary. To this end, we may assume that K = K which enables us to argue geometrically on the variety X := Spec Ā ⊂ A n K with Ā as in (1.2) using the Nullstellensatz. The ideal J A is the image in A of the Jacobian ideal Jg P of g generated by the 2 × 2-minors M i,j := ∂g ∂(x i x j )

  (2.1) Θ A = Θ a⊂P /aΘ P as a quotient of a (k, P )-Lie algebra Θ a⊂P := {δ ∈ Θ P | δa ⊂ a} aΘ P of logarithmic derivations along a by the (k, P )-Lie ideal aΘ P .

The research leading to these results has received funding from the People Programme (Marie Curie Actions) of the European Union's Seventh Framework Programme (FP7/2007-2013) under REA grant agreement n o PCIG12-GA-2012-334355.

of the Jacobian matrix of g which reads

With this notation we have to show that Sing X = V (g, Jg ) = {0}.

Due to those 2 × 2-minors of ∂g ∂x which involve only the columns 3, 7, 8, 9, . . . , n, only one of components x 3 , x 7 , x 8 , x 9 , . . . , x n of any x ∈ Sing X can be non-zero. We may therefore reduce to the case n ≤ 7.

Because of the 3rd column of ∂g ∂x , we have Jg ∩ K[x 1 , . . . , x 6 ] ⊇ x 3 I where

4 , x 2 + 5x 4 6 . Note that V (I) is the x 3 -axis which is not contained in V (g). It follows that Sing X∩V (x 7 ) is contained in the hyperplane V (x 3 ). Similarly because of the 7th column of ∂g ∂x and setting c := c 7 , we have Jg ∩ K[x 1 , . . . , x 3 , . . . , x 7 ] ⊇ x 7 I ′ where

4 , x 2 + 5x 4 6 . Using c 9 + 1 = 0, we find that V (I ′ ) is the x 7 -axis and conclude Sing X ∩ V (x 3 ) ⊂ V (x 7 ) as before. Summarizing the two cases, Sing X is in fact contained in V (x 3 , x 7 ).

Fix a point (x 1 , x 2 , 0, x 4 , x 5 , x 6 , 0) ∈ Sing X. Successively using the the equations

Similarly x 6 = 0 leaves no possibility except x = 0 and x 5 = 0 reduces to one of these two cases by M 1,2 = 0. Assume now that x 4 , x 5 , x 6 are all non zero. Then the minors M 1,5 , M 2,4 , M 2,5 , M 2,6 give equations

6 . Substituting into g, we obtain g 1 = 2x 1 x 4 -x 5 4 = 9x 5 4 , g 2 = 2x 2 x 6 + x 5 6 = -9x 5 6 and hence x 4 = x 6 = 0 contradicting our assumption.