T Sim

S Leroy
email: sleroy@laas.fr

J P Laumond

Computing good holonomic collision-free paths to steer nonholonomic mobile robots

Several schemes have been proposed in the path planning-literature to plan collision-free and feasible trajectories for non-holonomic mobile robots. A classical scheme is the two-step approach proposed in 4, 8, 5] which consists in rst computing a collision-free holonomic path, and then in transforming this path by a sequence of feasible ones. The quality of the solution and the computational cost of the second step depend on the shape of the holonomic path. In this paper, we introduce a nonholonomic cost of the geometric path to be approximated and we propose a con guration space structuring that allows us to compute an holonomic path minimizing at best the nonholonomic cost. The algorithms have been implemented and we present simulation results which illustrate the e cacy of the planner to produce good solutions with respect to the nonholonomic constraints of a mobile robot.

Introduction

This paper deals with a two-step approach of motion planning for nonholonomic mobile robots consisting in computing a collision-free geometric (holonomic) path and then approximating this path by a sequence of collision-free feasible ones. Such planning scheme works for any small-time locally controllable systems; it has been exploited along several directions for mobile robots 4, [START_REF] Latombe | Robot Motion Planning[END_REF][START_REF] Laumond | \Collision-free motion planning for a nonholonomic mobile robot with a trailer[END_REF] as well as for mobile robots with trailers 8, 5].

The quality of the solution (in terms of the number of maneuvers) and the computational cost of the approximating step depends on the shape of the rst geometric path. This dependance, already noticed in 6], is illustrated in Figure 1: a crab-wise path is more expensive to approximate than a path which follows the direction of the vehicle. The geometric planner of 6] produces good paths by using a shortest feasible paths metric for building a maximal clearance skeleton. To our knowledge the implementation was however limited to a point robot.

This paper deals with polygonal robots. We rst introduce the notion of nonholonomic cost of the geometric path to be approximated. We then propose a con guration space structuring that allows us to compute an holonomic path minimizing at best the nonholonomic cost.

The main idea consists in decomposing the con guration space into slices maintaining the orientation of the robot constant. We then apply a sweeping line algorithm to compute a convex cell decomposition of each slice into trapezoidal cells. For a given slice, the direction of the sweeping line is the orientation of the robot in this slice. The main axis of each trapezoidal cell is then supported by the orientation of the robot.

We assume that the robot and the obstacles are simple polygons. All the basic concepts used in this paper (generalized polygons, Minkowski sum, sweeping lines, roadmaps, cell decomposition,.. .) are described in 2].

Nonholonomic cost of holonomic paths

Let us consider a mobile robot corresponding to the following control system :

0 @ _ x _ y _ 1 A = 0 @ cos sin 0 1 A u 1 + 0 @ 0 0 1 1 A u 2 = Xu 1 +Y u 2
u 1 and u 2 are the linear and angular velocities respectively. When u 2 = 0 the robot moves along a straight line segment in the direction of the vehicle. When u 1 = 0, the robot turns around its xed position (x; y). Let us consider the vector eld Z = (sin ; cos ; 0). A path along Z is not feasible; it corresponds to a crab-wise path. Nevertheless, in some situations (e.g., a parking task), the only solution to reach the goal is to maneuver in order to steer the vehicle along this direction (such maneuvers exist because Z is the Lie bracket of the vector elds X and Y 1 ). Moreover the number of maneuvers varies as 1 2 with being the size of the free-space 4]; this situation corresponds to the worst case.

In the sequel we consider polygonal path in the conguration space R 2 S 1 , such that each straight line segment is either a \vertical" segment (i.e., maintaining a xed position) or an \horizontal" one (i.e., maintaining the orientation constant). A vertical segment V is feasible by the mobile robot; it corresponds to a pure rotation. Let H 0 be an horizontal segment of orientation 0 lying in the horizontal plane de ned by the con gurations with a xed orientation . The segment H 0 is feasible by the robot only if its orientation 0 veri es 0 = .

De nition: The nonholonomic cost of a vertical segment is null; the nonholonomic cost of an horizontal segment H 0 of length `is `j sin( 0 )j. The nonholonomic cost Cnh of a polygonal path consisting of an alternate sequence of vertical and horizontal segments is the sum of the nonholonomic costs of all the elementary segments. This de nition gives an account of the di culty to approximate a path by a sequence of feasible ones. Indeed, the cost of a polygonal feasible path is null; 1 See 4] for details on the Lie brackets and their geometric interpretation in nonholonomic motion planning.

the cost of straight line segments (with xed length) increases when the segments tend to crab-wise paths.

The idea of the algorithm below is to generate polygonal paths of the type above with small nonholonomic costs.

A roadmap in the con guration space

The goal of this section is to build a roadmap of the collision-free con guration space consisting of horizontal and vertical straight line segments. The principle of the construction is based on the computation of roadmaps within a xed number of horizontal slices (Section 3.1); then we compute elementary vertical paths to link two consecutive roadmaps iteratively (Section 3.2).

Roadmap in P

Let us consider a slice P (i.e., the plane gathering all the con gurations with a xed orientation ).

The obstacles in P are rst computed from the Minkowski sum between the robot at the orientation and the obstacles of the environment (Figure 2).

Then we decompose the free-space of P into trapezoidal cells. The key idea of the method is here: the trapezoidal cells are provided by a sweeping line algorithm, the direction of the line being (Figure 4). The boundaries of all the cells have at least one straight line segment with orientation . An e ect of the sweeping line algorithm is to provide cells elongated in the direction of the sweeping line. Because this direction is the main direction of the robot, moving in the cell along this direction has a null nonholonomic cost.

Two cells C i and C j in P are adjacent if they have a common straight line segment (with direction ). Let p i;j be the middle point of the segment common to the two adjacent cells. The cells being convex any straight line segment p i;j ; p i;k ] lies in the cell C i ; it then corresponds to a collision-free path. Computing all theses straight line segments provides a roadmap of P . This roadmap is exact in the sense that it solves completely the path planning problem for the robotpolygon moving in translation within P .

Notice that this roadmap method is computationally more expensive than the corresponding cell decomposition method that could have been de ned directly from the trapezoidal cells; its interest is to provide a graph of paths (and not a graph of cells) for which the evaluation of the nonholonomic costs is immediate (a path in the graph is also a path in the workspace).

Vertical paths

Let us consider two adjacent slices P and P + . Let R be the generalized polygon2 swept by the robot when it turns of an angle (from a con guration (:; :; ) and by maintaining its position xed). The collision-free space for the generalized polygon R moving in translation is obtained by computing the Minkowksi sum of this polygon with the workspace obstacles (Figure 2).

If R does not overlap the obstacles for some position (x; y), then the straight line segment (x; y; ); (x; y; + )] is a collision-free vertical path for the robot. Therefore two cells C i and C + j are adjacent if both of them contain a common point belonging to the collision-free space of R .

Roadmap in the con guration space

The roadmap in R 2 S 1 is built by rst computing the roadmaps of s slices P k for k = 2k s (0 k < s). Two roadmaps belonging to two consecutive slices P k and P k+1 are linked by vertical paths according to the following method (Figure 2 For each not empty C k i;j cell compute its intersection set with the collision-free space of R k . Select a point p i;j in each connected component of the intersection set. Each point p i;j gives rise to two new con gurations p k i;j 2 C k i and p k+1 i;j 2 C k+1 j .

Link each new con guration p k i;j (resp. p k+1 i;j ) by an horizontal path to the vertices of the roadmap belonging to the boundary of C k i (resp. C k+1 j ).

Link each pair of con gurations p k i;j and p k+1 i;j by a vertical path.

Analysis and complexity

The nal roadmap is then composed of s layers (i.e., the roadmaps in P k ) linked by vertical paths (corre- sponding to pure rotations of the robot).

Completeness: Each collision-free (and contactfree) path in the con guration space can be approximated by a polygonal line consisting of a nite sequence of horizontal and vertical straight line segments. For s su ciently high, there exists an approximation such that the horizontal segments are constrained to lie in the slices P k . Moreover there exists an homotopic path in the roadmap traversing the same cells of P k . The roadmap is then resolution complete, in the sense that the existence of a collision-free path in the con guration space is characterized by the existence of a path in the roadmap when s tends to in nity.

Complexity: Let us evaluate the computational complexity of the construction. We denote by n the number of vertices of the workspace obstacles; s is the number of slices; the number of vertices of the robot is su ciently small to not be taken into account.

Cell decomposition of a slice: The complexity of a sweeping line algorithm in the plane is in O(n logn) 1]. Then the O(n) cells in each P k can be computed in O(n log n). The complexity of the corresponding roadmap is in O(n 2 ). Linking two consecutive slices: A brute force algorithm computes the intersections C k i;j between all the cells C k i and C k+1 j in O(n 2 ). Their number can be in O(n 2 ). Checking if C k i;j intersects the collision-free space of R k can be done in O(n 3 ). Then the total cost of the vertical paths construction is in O(n 3 ). Finally the total cost of the roadmap construction is in O(sn 3 ).

Once the roadmap R is constructed, holonomic paths between two arbitrary start and nal con gurations q i and q f are computed by rst considering an augmented roadmap R 0 obtained by connecting both con gurations to the roadmap R, and then by searching R 0 for a minimum-cost path.

Connecting the roadmap

Let q = (x q ; y q ; q ) be the start (or nal) con guration and let P and P + denote the consecutive slices such that the orientation q belongs to the interval ; + . The procedure used to connect q to the roadmap R is the following: Check that the generalized polygon R placed at position (x q ; y q ) does not intersect the obstacles (otherwise return failure). Let q = (x q ; y q ; ) and q + = (x q ; y q ; + ) denote the projections of q onto P and P + .

Find the cell C i (resp. C + i 0

) of the slice P (resp. P + ), containing the con guration q (resp. q + ). Link q (resp. q + ) by an horizontal path to all vertices p i;j (resp. p + i 0 ;j 0 ) of R belonging to the boundary of the cell C i (resp. C + i 0

). Link q by a vertical path to both intermediate con gurations q and q + .

Arc costs in the roadmap

Let q i = (p i ; i ) i=1;2 be two con gurations and let 12 denote the orientation of segment p 1 p 2 in R 2 . We de ne a distance in R 2 S 1 by: Dist(q 1 ; q 2 ) = j 1 12 j + d euc (p 1 ; p 2 ) + j 12 2 j with d euc for the euclidian distance.

Let us consider the path between q 1 and q 2 consisting of a pure rotation from q 1 to the intermediate con guration (p 1 ; 12 ), followed by the horizontal path p 1 p 2 ] in the slice P 1;2 and a pure rotation from (p 2 ; 12 ) to q 2 . According to the distance de ned above, this path is a shortest feasible path.

The cost of an (horizontal/vertical) segment of the roadmap is de ned by Dist(q 1 ; q 2 ) and an additional term re ecting (as de ned in section 2) the nonholonomic cost Cnh(q 1 ; q 2 ) of the segment:

Cost(q 1 ; q 2 ) = Dist(q 1 ; q 2 ) + Cnh(q 1 ; q 2 ) A minimum-cost path between two given con gurations is searched in the roadmap with an A algorithm using Dist(q; q f ) as heuristic function.

Let us illustrate the cost on the example depicted in Figure 3. The rst arc (path 1 ) corresponds to a crabwise motion of length `in a direction perpendicular to the orientation of the slice. Its cost is + `:(1 + ) while the total cost of the three arcs (path 2 ) passing through the slice aligned with the direction of the segment would only be + `(this is a shortest path). Also, note that a less direct holonomic path (path 3 ) composed by two horizontal segments in the same slice can be better than path 1 depending on . This parameter allows the length increase to be tuned with respect to the improvement of the nonholonomic cost of the holonomic path.

Results

The algorithms described above for constructing and searching the roadmap have been implemented in C++ on a Sparc 20 workstation.

The example shown in Figure 5 is aimed at illustrating the interest of the proposed algorithms for improving the global e cacy of the two-step motion planning approach for nonholonomic mobile robots.

Figure 4 shows some of the roadmap's slices that were computed to solve this example. For the indicated robot's orientation, the free-space is represented in grey on the left gures, and the result of the trapezoidal decomposition along the main direction of the robot is displayed on the right.

The geometric path obtained for this illustrative example is shown in Figure 5-a. It consists of an alternate sequence of segments (horizontal paths in R) and pure rotations (vertical paths) For example, the segments start-2]; 11-12]; 12-goal] were found in the rst slice of Figure 4 and 3-4]; 5-6]; 7-8] respectively in the three next displayed slices. Figure 5-a also shows the feasible path derived from this geometric path by the nonholonomic planner 4] of the two-step approach. We simply recall that the method consists of successively substituting collision-free feasible subpaths (Reeds and Shepp curves 7]) for portions of the geometric path until the entire path is feasible. The feasible path is then optimized by repeatedly selecting random con gurations along the path and by joining them by collision-free feasible curves. For this example, the optimization required less than one second to produce the solution displayed in Figure 5-a which only contains four (necessary) maneuvers in the vicinity of the goal.

This path has to be compared with the solution obtained without considering the nonholonomic cost 3 (ie. for a null value of ). As shown in Figure 5-b, the shorter geometric path found in this case leads to an unrealistic feasible path containing a huge number of maneuvers.

Figure 4: Trapezoidal cell decomposition of freespace's slices 3 Note that a similar solution would have been produced by previous planners 4, 3] using this two-step approach.

Conclusion

The two-step approach has previously proven to be an e ective scheme for planning with nonholonomic constraints. The main advantage of the method is to limit the combinatorial complexity of the problem to the one of the geometric problem. Its drawback is that a/ in some situations, the generated path may include a much larger number of maneuvers than is actually needed. To circumvent this problem, we have introduced in this paper the notion of nonholonomic cost associated to an holonomic path. This cost indicates the di culty of transforming the path into a feasible one. We have also described a geometric planner based on a con guration space structuring which allows to produce holonomic paths minimizing the nonholonomic cost. This work has been speci cally developped for carlike robots. Possible extensions would be to formalize the nonholonomic cost for other systems (eg. tractortrailer robots), and also to consider more complex metrics (eg. introducing the clearance to the obstacles) for the evaluation of the nonholonomic cost.

Figure 1 :

 1 Figure 1: Two holonomic paths (left) and the associated feasible trajectories (right)

Figure 2 :

 2 Figure 2: The roadmap's slices

Figure 3 :

 3 Figure 3: Arc costs in the roadmap

Figure 5 :

 5 Figure 5: a/ An example of problem solved by the planner compared to b/ the solution obtained without considering the nonholonomic cost...

A generalized polygon is constituted of straight line segments and arcs of a circle.


T Sim

S Leroy
email: sleroy@laas.fr

J P Laumond

A collision checker for car-like robots coordination

This paper presents a geometric algorithm dealing with collision checking in the framework of multiple mobile robot coordination. We consider that several mobile robots have planned their own collision-free path by taking into account the obstacles, but ignoring the presence of other robots. We rst compute the domain swept by each robot when moving along its path; such a domain is called a trace.

Then the algorithm computes the coordination con gurations for one robot with respect to the others, i.e. the con gurations along the path where the robot enters the traces of the other robots or exits from them. This information may be exploited to coordinate the motions of all the robots.

Introduction

This paper presents a geometric algorithm dealing with collision checking in the framework of multiple mobile robot coordination. Path planning for multiple robots has been addressed along two main axis: centralized and decentralized approaches.

In the centralized approaches the search is performed within the Cartesian product of the con guration spaces of all the robots. While the problem is PSPACE-complete 3], recent results by Svestka and Overmars show that it is possible to design planners which are e cient in practice (up to four mobile robots) while being probabilistically complete 10]: the underlying idea of the algorithm is to compute a probabilistic roadmap constituted by elementary (nonholonomic) paths admissible for all the robots considered separately; then the coordination of the robots is performed by exploring the Cartesian product of the roadmaps.

In 1], Alami reports experiments involving ten mobile robots on the basis of a fully decentralized approach: each robot builds and executes its own plan by merging it into a set of already coordinated plans involving other robots. In such context, planning is performed in parallel with plan execution. At any time, robots exchange information about their current state and their current paths. Geometric computations provide the required synchronization along the paths. If the approach is not complete (as a decentralized scheme), it is su ciently well grounded to detect deadlocks. Such deadlocks usually involve only few robots among the eet; then they may be overcome by applying a centralized approach locally.

In this paper we propose an algorithm to solve the following problem. Several mobile robots plan their own collision-free path by taking into account the obstacles and ignoring the presence of other robots. The domain of the plane swept by each robot when moving along its path called a trace. The objective is to compute the coordination con gurations for one robot with respect to the others, i.e., the con gurations along the path where the robot enters the traces of the other robots or exits from them. This information may be exploited to coordinate the motions of all the robots.

Swept volume computation has already been proposed for collision detection along a given path (see 4] for a survey). For instance, in 2] the authors propose an approximated method based on an approximation of the trace by bounding boxes.

The algorithm presented in this paper does not make any approximation of the traces. It is dedicated to the following case: the paths of the robots are sequences of straight line segments and circular arcs of angle lesser than (e.g., Reeds and Shepp paths 9]). This hypothesis is realistic from a path planning point of view: it holds for any mobile robot (the existence of a collision-free feasible path is equivalent to the existence of such a special sequence); moreover numerous existing nonholonomic path planners compute solu-tions of this type (eg. [START_REF] Latombe | Fast Path Planner for a Car-Like Indoor Mobile Robot[END_REF][START_REF] Jim Enez | \Collision Detection Algorithms for Motion Planning[END_REF][START_REF] Laumond | motion planner for nonholonomic mobile robot[END_REF][START_REF] Mirtich | \Using skeletons for nonholonomic motion planning among obstacles[END_REF]).

For a polygonal robot, the trace is a domain bounded by arcs of a circle and straight line segments, i.e. a so-called generalized polygon. In the following developments we restrict ourselves to a rectangular robot; the extension to a polygonal robot would need technical and tedious developments in the computation of the traces that would not add any value to the approach.

In the following section we present the geometric structure of the traces. Then, we give an algorithm to compute the collision subpaths with a generalized polygon. The last section presents experimental results and we conclude on the interest of the algorithm with respect to coordinated motion planning.

Computing robot traces

Computing the trace swept by a rectangular robot along a path segment is obvious; it simply corresponds to the rectangle elongated by the length of the path segment.

Therefore, this section only concerns the case of arc paths. Given a rectangular robot, a rotation center c and a rotation angle , we want to compute the generalized polygon swept during the motion. For symmetry reasons, the presentation is limited to the following canonical case: the robot moves along a forward left motion and bl > fl with fl (forward length) and bl (backward length) as de ned by Figure 1 (also remind that the angle is smaller than

). Also note onto the gure the two situations that may occur depending whether the rotation center c is located inside or outside the robot.

Rotation center inside the robot

For a small the trace contains four circular arcs (centered at c) and eight segments (see Fig. 2-a). Each arc goes from a vertex of the rectangle to the same vertex rotated by . Consecutive arcs (eg. A a !A and The four critical values only depend on the robot geometry. Figure 4 explains how their expression can be easily deduced from the parameters r; l; bl and bl. Note however that their order may change depending on the location of the rotation center c. More precisely, one can establish that the order only depends on the relative situation of the two intervals fl; bl] and r-l; r+l]. Figure 5 resumes the order associated to each such case.

A I A θ B θ B I C θ C I D θ D I B A c D C A' c a/ < A b/ = A D' c C' c c/ = D d/ = C D" c c e/ = D 0 f/ > D 0
bl fl As illustrated by Figure 6, this case introduces a concave arc (issued from the trace swept by the edge DA) which connects the two points E = (0; l) and E (point E rotated by ). This case is however much simpler than the previous one since the arcs swept by the vertices A and D always remain interior to the trace. Therefore, only the critical value C may occur in this case.

(θ θ θ θ ) A D C D' bl fl (θ θ θ θ ) C D' A D bl fl (θ θ θ θ ) A D C D' r+l r-l bl fl (θ θ θ θ ) A C D' D fl bl (θ θ θ θ ) C A D' D bl fl (θ θ θ θ ) A C D D'

Collision subpaths

In this section, we present an algorithm which will be used in section 4 to compute the coordination congurations for a robot with respect to the paths of other ones.

The inputs of the algorithm are: an edge e = A; B] moving along a path (straight-line segment or circular arc) and a generalized polygon PG.

The output is the set of collision subpaths for which the moving edge e collides with PG. Let s 2 0; 1] be the curve length along path and e(s) be the edge placed at position s along . The collision subpaths coll are represented by the ordered set of collision intervals S i de ned by the s values at which the i st collision either begins or stops between e(s) and PG.

Case of segment subpaths

Let us illustrate the algorithm on the canonical example of gure 7. The gure shows the collision subpaths that should be produced by the algorithm. The bolded curves of PG's contour represent the only curves that need to be considered for this computation. Let us consider the points resulting from the intersection of PG's contour with the two lines A and B swept by the edge's endpoints along . The contour of PG can be decomposed into elementary parts (i.e. sequences of curves) connecting two such points. Obviously, we only need to consider the parts that are interior to the domain D lying between A and B . Also note that these parts have to be treated di erently according to their intersection with A and B . Some parts de ne a start point (eg. c2; c6), an end point (eg. c5; c7) or both endpoints (eg. c1; c8) of a collision subpath, while others do not produce any endpoint (eg. c3; c4). Figure 8 shows how a part resulting from PG's decomposition can be classi ed according to the labels of its start/end points. Each intersection point is labeled as follows: when PG's contour (oriented clockwise) enters into the domain D, the point is labeled a + or b + according to its location onto A or B . Labels a or b are similarly assigned to the points at which the contour exits domain D. Consider now for example a part starting at a point labeled a + . This part either ends at a point b (type 1) or at a point a (type 2a and 2b). In the rst case, the part corresponds to the beginning of a collision subpath. The end of the collision subpath will be given by the next b + ! a part (type 3) encountered while following the contour. In the second case, both endpoints belong to A and the part possibly generates a complete collision subpath when the start a + is located to the left of the exit endpoint a (type 2a). In the other case (type 2b), the part does not need to be considered since the corresponding collision subpath is necessarily included into a larger one obtained from other parts of the contour.

Since each part corresponds to a connected sequence of segments and circular arcs, one can easily check that the collision subpaths endpoints only occur at some points of the sequence (a vertex x v or a tangency point x t between a circular arc and the edge e). Let s(x) be the s-value along at which such point x belongs to e(s). A start (resp. end) point is obtained by considering the minimal (resp. maximal) value of all the s(x) computed along the part.

The algorithm is rst initialized by following PG's contour (from any starting point), until a rst intersection x 1 with A or B is found. Then the algorithm continues to loop over the curves of PG until the next intersection x 2 . Between x 1 and x 2 , it iteratively records the extremal values of the s(x) computed at the encountered vertices or tangent points. When x 2 is found, the collision subpath of the part is obtained from extremal values, according to the labels of x 1 and x 2 . The algorithm next considers the part starting at point x 2 , and continues until PG's contour has been completely scanned. At the end, some of the produced collision intervals may intersect. Therefore an additional step is required to compute their union. The algorithm returns the ordered set of non overlapping intervals included into the interval 0; 1] (i.e. the collision subpaths of ).

Case of arc subpaths

The principle of the algorithm remains similar to the one described above for the case of segment subpaths. Let us consider the trace swept by the edge e along an arc of a circle with radius r and centered at c. Two situations occur depending on the relative position between e and c (Fig. 9). When the orthogonal projection c 0 of c onto the line supporting e does not belong to the edge (case 1), the domain D is limited by an inner circle C A and an outer circle C B , both centered at c and going through one of both edge's endpoints. When c 0 belongs to edge e (case 2), the inner circle corresponds to the circle C t that is tangent to the edge, and the outer circle remains C B . The gure also shows for each case, the relevant parts of PG's contour. These parts are limited by the intersections with domain D and are labeled as explained in section 3.1. For a given part, Figure 10 shows that di erent sets of points have to be considered: the vertices x v (black points onto the gure) and the tangency points x t . Moreover, case 2 requires to consider additional points x A resulting from the intersection between C A and the part. Remark: The tangency points x t between the moving edge e and a circular arc, are obtained by computing the common tangents between circle C t and the support circle of the arc (see Figure 11). Points x t are the tangent points of C arc which also belong to the arc and to the domain D swept by the edge.

Complexity of the algorithm

The algorithm takes O(n) to loop over the n curves of PG's contour and to compute its decomposition into k parts connecting the 2k intersections with domain D. At most one collision interval is computed for each part. Therefore, O(k) (possibly) overlapping intervals are produced at the end of the loop. The algorithm then computes the sorted union of these O(k) intervals; its overall complexity is therefore O(n + klogk).

Application to car-like robot coordination

The algorithms introduced in both previous sections are now applied in the framework of the motion coordination problem.

Let us consider two paths 1 and 2 independently planned by two car-like robots. Our objective is to compute the coordination con gurations for the rst robot with respect to the trace of the second one (i.e. the con gurations where the rst robot enters or exits the trace of the second one).

The trace of the second robot along 2 is rst computed (by using the algorithm of Section 2). This trace is a generalized polygon.

The path 1 is a sequence of straight line segments and arcs of a circle. For each element of the sequence we have to compute the enter/exit con gurations with respect to the trace of the second robot. The robots being rectangles, we apply the algorithm of Section 3 to the four edges of the rst robot1 . Each application of the algorithm gives rise to collision subpaths along 1 . The union of the all collision subpaths provides the nal solution, i.e., the set of collision-free con gurations along 1 with the trace of the second robot.

Figure 12: A rst example: a/ the paths 1 and 2 and b/ the computed collisions subpaths show some examples computed by the algorithm. For the rst example, the left gure shows two paths 1 and 2 and the traces swept by each robot along these paths. The collision subpaths are represented in bold onto the right gure which also shows the robots placed at the extremities (the coordination con gurations) of these subpaths. The other gures show two examples involving three robots. The collision checker algorithm presented in this paper may be used in several frameworks. When all the start and goal con gurations of each robot are outside the traces of all the other ones, there exists a coordinated motion allowing each robot to execute its own motion in a coordinated way. The continuous nature of the motion coordination problem is transformed into a graph search working from the coordination con gurations computed by our algorithm (see 1] for an example of application).

Consider now the cases where a start or goal conguration of a robot belongs to the trace of another robot; these cases are easily detected by our algorithm. We can imagine a (random) method computing a conguration (replacing the start or goal con guration) outside all the traces. This new con guration appears as an intermediate goal to reach before (or after) executing the motions of all the other robots. Such an operation may be repeated on all the robots generating deadlock situations.

Figure 1 :

 1 Figure 1: Canonical case: the rotation center c belongs to one of the two grey regions

Figure 2 :Figure 3 :Figure 4 :

 234 Figure 2: Trace evolution and critical angles B a ! B ) are connected by two segments (eg. A s ! A I s !B). The full description of the trace obtained in this case, is given by the outside sequence of Figure 3.

Figure 5 :Figure 6 :

 56 Figure 5: The sorted critical values This analysis allows us to derive a very simple algo-

Figure 7 :

 7 Figure 7: Collision subpaths of a generalized polygon

Figure 8 :

 8 Figure 8: The three elementary cases

Figure 9 :

 9 Figure 9: The two cases of arc subpaths

Figure 10 :

 10 Figure 10: Relevant points considered by the algorithm

Figure 11 :

 11 Figure 11: Tangent points between the moving edge e and a circular arc

Figure 13 :

 13 Figure 13: Coordination of three robots of di erent size

This assumes that the trace of the second robot is not small enough to be included into the rst robot at any point of 1 !. . .


Stefano Bonciolini

Antonio Pulcinella

Matteo Leone

Debora Schiroli

Adrian Luguera Ruiz

Andrea Sorato

Maryne A J Dubois

Ranganath Gopalakrishnan

Geraldine Masson

Nicola Della Ca

Adrián Luguera Ruiz

Nicola Della Ca'

Stefano Protti

Maurizio Fagnoni

Eli Zysman- Colman

Magnus Johansson

Timothy Noël
email: t.noel@uva.nl

Metal-free Photocatalytic Cross-Electrophile Coupling enables C1 Homologation and Alkylation of Carboxylic Acids with Aldehydes

Keywords: Sulfonyl Hydrazones, Cross-Electrophile Coupling, Deoxygenative Coupling, Arylethylamine, Homologation, Late-stage Functionalization

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

Introduction

In drug discovery, the 3D structure of proteins is crucial for the success of drugs. The increased use of sp [START_REF] Clemons | Proc. Natl. Acad. Sci[END_REF] -hybridized carbon atoms (Fsp [START_REF] Clemons | Proc. Natl. Acad. Sci[END_REF] ) is key, as it correlates with a drug's effectiveness and safety. [1] This trend, known as 'Escape from Flatland', [2] involves increasing Fsp 3 in drugs for better alignment with protein structures, enhancing selectivity and efficacy. [START_REF] Clemons | Proc. Natl. Acad. Sci[END_REF] This strategy improves target interaction and reduces side effects, balancing effective treatment with minimal negative effects.

Historically, classical cross-coupling reactions have been a linchpin in synthetic chemistry, enabling the straightforward construction of C(sp 2 )-C(sp 2 ) bonds and thereby propelling the production of planar, biaryl structures. This entrenched reliance on cross-coupling has inadvertently sculpted a discernible bias in small molecule drug design, steering the generation of libraries that predominantly feature structurally analogous, two-dimensional compounds. [START_REF] Brown | [END_REF] While there have been laudable strides made within the domain of C(sp [START_REF] Clemons | Proc. Natl. Acad. Sci[END_REF] )-C(sp 3 ) cross-coupling, contemporary methodologies are oftentimes plagued by several pragmatic limitations. [5,6] They typically necessitate sizable excesses of one coupling partner and frequently hinge upon non-abundant starting materials, such as air-and moisture-sensitive alkyl organometallics, thereby constraining the reaction scope and practicality in a drug discovery context. Consequently, the quest for alternative strategies that circumvent these limitations while facilitating the construction of three-dimensional molecular structures persists as an imperative in medicinal chemistry research. [7] In recent years, nickel-mediated cross-electrophile (XEC) coupling has emerged as a potent strategy for constructing C(sp 3 )-C(sp 3 ) bonds, utilizing various native and bench-stable aliphatic coupling entities, thus circumventing the use of moisture-sensitive organometallic species. [8][9][10][11][12][13][14][15] Despite substantial strides within this sphere, exploiting varied, ubiquitous functional groups such as aldehydes as coupling partners has lingered in a state of underdevelopment. Traditionally, aldehydes have been harnessed as carbonyl electrophiles with Mg or Li-based organometallic species or within Nozaki-Hiyama-Kishi (NHK) type reactivity to yield alcohols, [16,17] yet their employment to forge C(sp 3 )-C(sp 3 ) bonds via a reductive deoxygenative pathway remains, to our knowledge, uncharted. A pioneering approach, that enables the direct coupling of sp 2 and sp 3 electrophiles, such as aldehydes and carboxylic acids, heralds an unprecedented disconnection in the cross-electrophile coupling domain (Figure 1A). Aryl sulfonyl hydrazones are considered as a bench-stable, activated form of aldehydes due to their known propensity to undergo both radical and polar addition, ultimately yielding deoxygenated, cross-coupled products upon thermal decomposition of alkylated hydrazide intermediates (Figure 1B). [18][19][20][21][22][23][24][25][26][27] Utilizing abundant aliphatic carboxylic acids activated as NHPI-based redox-active esters (RAEs) to serve as sp [START_REF] Clemons | Proc. Natl. Acad. Sci[END_REF] electrophiles, and employing visible light-mediated decarboxylation to yield carbon-centered radicals, [28][29][30][31] we envisioned a trapping mechanism with aldehyde sulfonyl hydrazones to, upon sulfinate and dinitrogen extrusion, afford the coveted product (Figure 1C). In this study, we realise such a metal-free cross-electrophile coupling, leveraging Eosin Y as an economical organophotocatalyst under visible light irradiation. [32] Illustrating the potential of our synthetic strategy becomes particularly appealing when reflecting upon the strategic C1 homologation of carboxylic acids, traditionally achieved through the Arndt-Eistert reaction. [33][34][35][36] Although this protocol, developed in the 1950s, bears chemical reliability, significant limitations persist, particularly those pertaining to the generation, purification, and utilization of toxic and explosive diazomethane, hindering its widespread adoption and applicability. While flow technology has provided a partial answer to these safety challenges, [37,38] a truly general and practical alternative for such transformation has been elusive. [39,40] Indeed, polar variants such as the Kowalsky Ester homologation suffer from the use of organolithium bases, strongly limiting the substrate scope of the transformation and its scalability. [41,42] For seminal radical variants, Barton proposed a photoinduced C1 homologation of N-hydroxy-2-thiopyridone esters, although this strategy suffered from low functional group compatibility, a narrow scope, and requisite lengthy synthetic sequences. [43,44] In this context, we present the utilization of ethyl glyoxalate-derived sulfonyl hydrazone 2a as a bench-stable and easy-to-handle crystalline radical acceptor to realize the C1 homologation of carboxylic acids under mild conditions (Figure 1D). As a subsequent, potent application of this synthetic paradigm, our attention was drawn by the synthesis of β-arylethylamines, a prevalent structural motif within numerous drugs and natural products. [45] Although various synthetic routes have been delineated, an intuitive retrosynthetic strategy entailing a cross-coupling reaction between a benzyl electrophile and α-amino nucleophile has remained underrepresented. [45][46][47][48] We posit that the advanced cross-electrophile coupling between NHPI esters and aldehyde sulfonyl hydrazones will provide a straightforward and direct route for the efficient preparation of substituted cyclic and acyclic β-arylethylamines (Figure 1E).

Concluding with a third robust synthetic application of this strategy, the methodology demonstrates significant utility in the late-stage functionalization (LSF) of peptides on solid-phase, enabling the modification of complex peptides under mild conditions and obviating the need for tedious de-novo synthesis (Figure 1F). [49][50][51] We initially commenced to develop a direct decarboxylative C1 homologation, beginning with N-Boc (L)-Proline, but we were met with failure to produce the desired product 3 (see Supporting Information, section 5.1). This result was linked to the noted sensitivity of aldehyde sulfonyl hydrazones to bases, which are indispensable to promote the decarboxylation process. [18,21] Consequently, our investigation focused on the use of well-established N-(acyloxy)phthalimides (NHPI-based esters) as redox-active esters (RAEs) in an effort to sidestep the necessity for bases during the decarboxylative generation of nucleophilic carbon radicals. An exhaustive screening of all reaction parameters (see Supplementary Information, section 5.2) led us to discover that the targeted homologated product 3 could be obtained in excellent yields (Table 1, Entry 1, 90% yield) when a dichloromethane (0.1 M) solution composed of ethyl glyoxalate-derived 4-trifluoromethyl-phenyl sulfonyl hydrazone 2a (1.0 equiv.) as the radical acceptor, N-Boc (L)-Proline RAE 1a (1.0 equiv.) as the radical precursor, Hantzsch ester (HE, 1.5 equiv.) as the reductive quencher, and disodium Eosin Y (EYNa2, 10 mol%) as the photocatalyst was irradiated with blue LEDs (40W Kessil, 456 nm, PR160L) for 12 hours. The yield reflects the one obtained for the final product 3, achieved when the hydrazinyl intermediate was swiftly subjected to cleavage conditions in ethanol, according to our previous report. [27] Evaluating a two-step one-pot procedure, with trifluorotoluene as the solvent, revealed diminished yields of 3, underscoring the pivotal role dichloromethane plays in the photocatalytic cycle (Table 1, Entry 2). Surprisingly, an excess of radical acceptor 2a did not markedly influence the reactivity (Table 1, Entry 3). Noteworthy is the underperformance of more expensive organophotoredox catalysts like 4CzIPN, 3DPA2FBN or the widely-used transition-metal based photocatalyst Ru(bpy)3PF6 (Table 1, Entries 4-6). [52,53] HE played a major role in the transformation, as other reductive quenchers, such as DABCO, DIPEA, or tetramethylguanidine entirely inhibited the reaction (see Supplementary Information, Table S5).

Remarkably, incorporating acidic additives, such as HFIP, TFA, and various amino acids, did not substantially impact the reactivity (see Supplementary Information, Table S3 andS8). Control experiments conducted to explore the formation of donor-acceptor complexes between RAE 1a and HE, performed at 456 and 390 nm without EYNa2, either yielded no product or achieved lower yields (Table 1, Entries 7-8), underscoring the crucial role of the photocatalyst in photoinitiating the reaction, thus securing higher yields. [54,55] Running the reaction in the dark resulted in the quantitative recovery of all starting materials (Table 1, Entry 9). Notably, applying the optimized conditions to the less electrophilic 4-CF3-benzaldehyde-derived sulfonyl hydrazone 2c as the radical acceptor yielded the corresponding β-arylethylamine product 46 in a 58% NMR yield. Additional screening of reaction parameters did not produce any enhancements in yield (see Supplementary Information, section 5.3).

Table 1. Optimization of the photochemical step for the C1 homologation of RAE 1a.

[a] Yields were determined by 1 H NMR using trichloroethylene as external standard (0.2 mmol scale, 0.1 M). See Supplementary Information for experimental details.

Scope of the C1 Homologation

Having established optimal reaction conditions, we next investigated the scope of the photochemical C1 homologation of RAEs derived from readily available carboxylic acids (Figure 2). As expected, N-Boc protected cyclic amino acids afforded the desired products (3-5) in good yields. Moreover, linear proteogenic amino acids underwent homologation to the respective ethyl esters (6-13) under the standardized reaction conditions. Noteworthy is the performance of challenging substrates, such as the redox-sensitive methionine and thiophene-derived amino acid, which, despite providing the target compounds (8 and 10), did so in somewhat attenuated yields. The protocol's generality was highlighted through the homologation of sterically hindered cyclic tertiary amino acids, producing the target products in synthetically useful yields (14-16). A subsequent examination of various inactivated primary, secondary, and tertiary RAEs revealed that all coupled with glyoxalate-derived sulfonyl hydrazones 2a, presenting moderate to good yields (17-22). In a particularly notable development, two dipeptides underwent photochemical homologation, yielding the targeted homoproline-analogues (23-24). [56] Importantly, the mild conditions of this photocatalytic C1 homologation protocol facilitated the conversion of natural products like biotin and enoxolone-each harboring different sensitive functional groups-to their corresponding ethyl esters (25-26), not accessible by the aforementioned methods.

Scope of the alkylation

We next aimed to explore further the generality of our developed reaction conditions, applying them to the cross-electrophile coupling of RAEs, derived from a diverse set of carboxylic acids, with various aldehyde-derived sulfonyl hydrazones (Figure 3). We envisioned providing streamlined access to cyclic and acyclic β-arylethylamines, thereby presenting a new, intuitive radical disconnection for practitioners in the field. [45] Regarding the scope of the α-amino RAEs, a myriad of medicinally pertinent cyclic structures-encompassing azetidine, piperazine, indoline, and isoquinoline-were successfully coupled, achieving synthetically useful yields in all cases (27-33). [57] Significantly, the methodology enabled the conversion of even challenging tertiary RAEs, facilitating the creation of quaternary centers, albeit with somewhat reduced yields (34-36). Beyond cyclic structures, the protocol also exhibited proficiency with a range of linear amino acids, yielding the corresponding βarylethylamines in moderate to good isolated yields (37-41). An assessment of the sulfonyl hydrazones scope indicated optimal performance with electron-poor groups (see Supplementary Information, section 11). Noteworthily, the metal-free nature of the protocol tolerated halogenated arenes and heterocycles, providing convenient handles for subsequent synthetic elaboration (30, 47, 48, 50-53). A noticeable limitation of the scope was observed: electron-rich sulfonyl hydrazones yielded only traces https://doi.org/10.26434/chemrxiv-2023-fcl2j ORCID: https://orcid.org/0000-0002-3107-6927 Content not peer-reviewed by ChemRxiv. License: CC BY 4.0 of the desired product, with a notable reduction of the carboxylic acid. Additionally, under slightly modified reaction conditions (see Supplementary Information, Table S7), unactivated aliphatic aldehyde-derived sulfonyl hydrazones acted as effective coupling partners, delivering alkylated secondary amines in synthetically useful yields, and underlining the method's simplicity and versatility (54-58). Reaction conditions: RAE (0.3 mmol, 1 equiv.), Sulfonyl Hydrazone (1 equiv.), Hantzsch ester (1.5 equiv.) and EYNa2 (0.10 equiv.) in 3 mL of CH2Cl2 (0.1 M). For further experimental details see the Supplementary Information.

Late-stage modification of peptides on solid phase

Having demonstrated the generality of the photochemical cross-electrophile coupling between sulfonyl hydrazones and RAEs, we turned our inquiry toward the potential extension of this protocol to facilitate the late-stage functionalization (LSF) of more complex molecules, such as peptides. Given the increasing prominence of peptides as therapeutic modalities, the development of methods capable of https://doi.org/10.26434/chemrxiv-2023-fcl2j ORCID: https://orcid.org/0000-0002-3107-6927 Content not peer-reviewed by ChemRxiv. License: CC BY 4.0 functionalizing extensive amino acid sequences directly on resin becomes especially valuable, enabling the generation of diversity without necessitating the development of de-novo synthetic methods. [58,59] Moreover, on-resin modification brings forth substantial practical advantages, addressing key challenges related to purification and solubility that are often encountered in peptide chemistry in solution. Specifically, considering the well-documented compatibility of redox-active ester synthesis with solid-phase approaches, [49,60,61] and the mild basic condition of our two-step protocol, we hypothesized that adapting this photochemical transformation to heterogeneous conditions on resin would be an attainable objective.

At the outset of our investigation, a sensitivity/robustness screening was undertaken to determine which amino acids would be compatible with our reaction conditions and, consequently, could be possibly incorporated into the peptide sequence (see Supplementary Information, Section 5.4). Pleasingly, all screened amino acid residues, when added as additives, did not interfere with the model reaction.

Following a minor re-optimization of the reaction parameters and modification of the experimental setup (see Supplementary Information, Sections S7.1-S7.3), we discovered that crude peptides, synthesized using Rink Amide resin via SPPS, could be readily engaged in the photocatalytic alkylation (Figure 4). Illustratively, heptapeptide P1 was subjected to LSF, yielding the corresponding homoproline-containing analogue 59 in a 28% isolated yield after 21 steps from resin loading (74% LCAP for the decarboxylative alkylation step, with LCAP defined as LC Area % of the product peak in the ultra-performance liquid chromatography (UPLC) chromatogram of the reaction crude. See Supplementary Information, Section 7.5). Highlighting the efficacy of our method, a 28% yield robustly demonstrates the potential of our cross-electrophile coupling for synthesizing complex structures with high selectivity and notable yield conservation. Similarly, a late-stage incorporation of a benzylic unit was accomplished efficiently, demonstrating utility in the context of lipophilicity modulation (60) (72% LCAP for the decarboxylative alkylation step, See Supplementary Information, Section 7.6). To our delight, a derivative of afamelanotide-a therapeutic peptide indicated for patients affected by erythropoietic protoporphyria-was also successfully engaged in the protocol, affording derivative 61 in an overall 9% yield from resin loading (71% LCAP for the decarboxylative alkylation step. See Supplementary Information, Section 7.7). [62] Figure 4. Scope of the cross-electrophile coupling of peptide RAEs and benzenesulfonyl hydrazones on resin. Reaction conditions: RAE (0.03 mmol, 1 equiv.), Sulfonyl Hydrazone (3 equiv.), Hantzsch ester (4.5 equiv.) and EYNa2 (0.30 equiv.) in CH2Cl2 (33 mM). For full experimental details, see the Supplementary Information.

Mechanistic Investigations

In our pursuit to elucidate the mechanism, we executed a series of experiments to explore the radical pathway and identify the catalytic species facilitating the photochemical transformation. Confirmation of the radical nature of the reaction was achieved through radical trapping and radical clock experiments (Figure 5A). [63] Indeed, ESI-HRMS analysis substantiated the formation of TEMPO adduct 62, while GC-MS analysis convincingly demonstrated carbon radical formation through the production of 64 via a 5-exo-trig radical cyclization.

In light of these observations and based on the reported Single Electron Transfer (SET) mechanism of EYNa2, we propose the ensuing catalytic cycle (see Figure 5B). [64,65] Upon absorption of visible light, the triplet excited state of EYNa2 is reductively quenched by the sacrificial electron donor HE to generate HE +‧ . Following the findings of Overmann and König, [66][67][68] the redox-active ester is subsequently reduced by the EYNa2 radical anion, thereby completing the catalytic cycle and yielding the nucleophilic alkyl radical 66 upon decarboxylation. The emergent alkyl radical is then captured by the electrophilic site of sulfonyl hydrazone, resulting in the formation of the hydrazinyl radical intermediate 67. Finally, a plausible Hydrogen Atom Transfer (HAT) step from HE +‧ or neutral HE to 67 is considered, generating the pyridium co-product 68 and the targeted product 69.

https://doi.org/10.26434/chemrxiv-2023-fcl2j ORCID: https://orcid.org/0000-0002-3107-6927 Content not peer-reviewed by ChemRxiv. License: CC BY 4.0

Scale up

Finally, we demonstrate the scalability of our photochemical C1 homologation using flow technology (Figure 5C). In batch settings above 1 mmol, the heterogeneous reaction mixture led to a significant drop in yield of the desired product 3 (see Supplementary Information, Section 9.1). Suspecting nonuniform irradiation and limited light penetration at larger scales, we transitioned the photochemical alkylative step to continuous flow. [69][70][71] After an extensive optimization conducted at 0.2 mmol scale (see Supplementary Information, Section 9.2), we established conditions for the protocol using a

CONCLUSION

In conclusion, we have developed a visible light mediated metal-free cross-electrophile coupling approach that stands as a powerful and versatile C(sp 3 )-C(sp 3 ) cross-coupling platform. It combines carboxylic acid-derived redox-active esters with aldehyde sulfonyl hydrazones, utilizing Eosin Y as an efficient organophotocatalyst under visible light, leading to the desired cross-coupled products through subsequent fragmentation. Our approach provides a safer alternative to the traditional Arndt-Eistert https://doi.org/10.26434/chemrxiv-2023-fcl2j ORCID: https://orcid.org/0000-0002-3107-6927 Content not peer-reviewed by ChemRxiv. License: CC BY 4.0 reaction for C1 homologation of carboxylic acids and enables direct synthesis of cyclic and acyclic βarylethylamines using diverse aldehyde-derived sulfonyl hydrazones. Furthermore, the method proves also effective for late-stage functionalization (LSF) of peptides on solid-phase. Given these capabilities, we are confident our method will enable the exploration of sp 3 -hybridized molecules in contemporary drug discovery and development.

Figure 1 .

 1 Figure 1. Design and applications of the cross-electrophile coupling of carboxylic acids with aldehydes.

Figure 2 .

 2 Figure 2. Scope of the C1 homologation of carboxylic acids using ethyl glyoxylate-derived 4-trifluoromethylphenyl sulfonyl hydrazones 2a. Reaction conditions: redox active ester (0.3 mmol, 1 equiv.), 2a (1 equiv.), Hantzsch ester (1.5 equiv.) and EYNa2 (0.10 equiv.) in 3 mL of CH2Cl2 (0.1 M). For further experimental details see the Supplementary Information. [a] > 20:1 d.r. [b] 3:1 d.r. [c] 2.5:1 d.r.

Figure 3 .

 3 Figure 3. Scope of the cross-electrophile coupling of RAEs with aromatic and aliphatic aldehyde-derived sulfonyl hydrazones.Reaction conditions: RAE (0.3 mmol, 1 equiv.), Sulfonyl Hydrazone (1 equiv.), Hantzsch ester (1.5 equiv.) and EYNa2 (0.10 equiv.) in 3 mL of CH2Cl2 (0.1 M). For further experimental details see the Supplementary Information. [a] 1:1.4 d.r. [b] 2 equiv. of N-Boc (L)-Proline RAE 1a was used.

  Figure 3. Scope of the cross-electrophile coupling of RAEs with aromatic and aliphatic aldehyde-derived sulfonyl hydrazones.Reaction conditions: RAE (0.3 mmol, 1 equiv.), Sulfonyl Hydrazone (1 equiv.), Hantzsch ester (1.5 equiv.) and EYNa2 (0.10 equiv.) in 3 mL of CH2Cl2 (0.1 M). For further experimental details see the Supplementary Information. [a] 1:1.4 d.r. [b] 2 equiv. of N-Boc (L)-Proline RAE 1a was used.

  Vapourtec UV-150 photochemical flow reactor (ID: 0.8 mm; V = 3.33 mL, flow rate = 0.412 mL min -1 ,  = 8 min) set at 30 °C, irradiated with 60 W 450 nm LEDs. Subsequent thermal cleavage of the alkylated hydrazide intermediate yielded the targeted C1 homologated product in 60% isolated yield.

Figure 5 .

 5 Figure 5. Mechanistic investigation and scale-up in flow.

https://doi.org/10.26434/chemrxiv-2023-fcl2j ORCID: https://orcid.org/0000-0002-3107-6927 Content not peer-reviewed by ChemRxiv. License: CC BY 4.0

Acknowledgement

We are grateful to have received generous funding from the European Union H2020 research and innovation program under the Marie S. Curie Grant Agreement (PhotoReAct, No 956324, S.B., M.L., A.L., G.M., E.Z.C., T.N.; CHAIR, No 860762, A.P., M.J., T.N.). We also would like to thank Ed Zuidinga for help with the HRMS measurements.


C Van Geem

T Sim

J-P Laumond

J-L Bouchet

J-F Rit

Mobility Analysis for Feasibility Studies in CAD Models of Industrial Environments

This paper presents a variant of a probabilist approach to motion planning. The objective is to face large, complex industrial environments for maintenance purpose. The contribution is based on a structuring of the workspace into boxes that limits the size of the graph to be searched. The algorithm was integrated in a commercial CAD system and real-size experiments are presented.

Introduction

Feasibility studies for the planning of maintainance interventions at industrial sites are often done using CAD systems. Scenes have high complexity (more than 10000 polyhedral facets). Commonly devices like carts and cranes (with up to 4 DOFs, occasionally up to 8 DOFs, a tree-like kinematic structure) intervene and must carry objects through the scene. Searching for collision free motions through densely populated scenes tried by hand is a di cult and time consuming task. Automated mobilityanalysis therefore would considerably help to improve quality and to reduce the cost of such feasibility studies.

We chose to implement a probabilistic path planner constructing a connectivity graph in con guration space (C-Space), for the following reasons. Firstly, that approach plans a path for a point in C-Space and thus is independant as a method from the particularities of the device. Speci cities of the device can be expressed by the use of a particular strategy (local planner) for the connection of two con gurations in the graph. Due to the modularity of the probabilistic path planning approach implementing and adding another local planner is an easy programming task.

Due to the high complexity of the industrial scenes we concentrated our e orts on the strict limitation of supported by Electricit e de France (EDF-DER) the size of the graph and the costly operations like collision detection and search for connections between nodes in the graph. We reject obsolete nodes corresponding to easy to attain parts, and aim at attaining narrow passages in the Workspace. A graph consisting of a forest of trees su ces to capture connectivity of C-Space.

In recent years the Probabilistic Roadmap approach has become a popular method for path planning problems [START_REF] Kavraki | Analysis of probabilistic roadmaps for path planning[END_REF], 2]), and rst results of the analysis of the method's behavior exist [START_REF] Hsu | On nding narrow passages with probabilistic roadmap planners[END_REF]). The performance of the method can be increased by strategies which guide the algorithm in its random search for the connectivity properties of free C-Space [START_REF] Ferbach | Planning nonholonomic motions for manipulated objects[END_REF], 1]). A rst step toward the application of the method in evolving industrial environments was done in 4] and 3], as well as in 8] where an o -line pre-computed roadmap is updated during execution of a path.

The contributions presented here are the use of a partitioning of Workspace in boxes (Section 3) in order to lter and select nodes on which costly operations are executed, the use of several local methods for expressing particularities of the device and the integration of the planner in the CAD system ROBCAD, product of Tecnomatix and used by EDF (Section 4). Experimental results are presented in Section 5.

Algorithm

The probabilistic path planner approach consists of two phases: a learning phase and a query phase. In the learning phase a graph is constructed in C-Space. Con gurations are choosen randomly. If the device in a new con guration is not in collision, the con guration is added as a node to the graph. Then the new node is connected by arcs to some other nodes in the graph if a collision free path between them is found. Such a path is searched for by a local method. Usually the choice of con gurations is not entirely ran-dom, but in uenced by guidelines chosen by the implementor. Moreover, usually the generated graph is re ned further by some dedicated methods in order to increase its quality. In the query phase an initial and a goal con guration is connected to the graph using a local planner, and the solution is obtained by a graph search. The graph can be re-used for several queries.

The main steps of our implementation are illustrated in the pseudo-code below. In the learning phase the choice of con gurations and the re nement is based upon a precomputed partitioning of the Workspace in boxes (see Section 3 for details). In the learning phase calls to random generation of nodes and calls for re nement of the graph constructed so far alternate until the graph reaches a certain quality. The loop in step 2 is stopped based upon an analysis of the evolution of the number of trees in the graph as well as their relative sizes. When a query resulted in a path, the quality of the path initially found can be enhanced using an optimization routine. Each of the four steps are accessible seperately by the end-user through the interface.

Boxes and Learning Phase

Preprocessing the Workspace: As a preprocessing step, we partition Workspace in boxes of di erent sizes (PartitionWorkspace()). The goal is to reduce the number of poses of the device in easily reachable parts of the Workspace and to augment the number of poses in parts where obstacles are densely present and holes (like door openings) in obstacles occur. We attempt to create automatically large boxes in easily reachable areas and small boxes elsewhere. We start o the construction of the partitioning with a bounding box around Workspace. This bounding box might be de ned by the end-user using the interface, or is a huge box by default. We recursively cut the box in two smaller boxes (usually of a di erent size) by a cutting plane, if there are many (polyhedral) obstacles which have at least one vertex in the box. We cut alternately along the X, the Y, or the Z-direction of the global coordinate system of the scene.

In order to cut a box B in two, we must select its cutting plane. Suppose the box should be cut by a plane perpendicular to the X-axis of the global coordinate system. Then for each vertex v on the outer facets of a polyhedral obstacle, v lying in B, we consider the plane P v

x perpendicular to the X-axis. If all vertices on the outer facets adjacent to v lie on the same side of P v

x , we call P v x a candidate plane for B. We order the candidate planes P v

x according to increasing X-coordinate value of the corresponding vertices v. The cutting plane is the middle one in this ordered list. Figure 1 illustrates this procedure. The cutting is stopped once a threshold on the total number of boxes is reached, or when no box contains more than a minimal number of obstacles.

In the following we will say that `con guration c corresponds to a box' if a user de ned point on the device, usually at the end-e ector, ends up being positioned in the box when the device is put in con guration c. Since a node in the graph is a con guration added to the graph, we say that `box B contains node n' if the con guration corresponds to B. We will say that two boxes are `neighbors' if their intersection is non-empty.

Use of Boxes in Learning Phase: We use boxes on four places in the learning phase:

Firstly, when a random con guration c is chosen (ExtendGraphRandomly()) it is rst determined to which box it corresponds. If that box already contains more than M nodes, we reject c. The parameter M is increased at the end of each visit of the loop.

After a while we only test new con gurations when they correspond to poorly visited boxes.

Secondly, during the rst re nement step (Re-nePoorlyVisitedBoxes()) we consider all nodes in boxes which contain less than m nodes). The parameter m is increased at each visit of the loop. We randomly perturbate some or all of the C-Space coordinates of these nodes. Doing so we make more nodes in probably di cult to reach areas.

Thirdly, in the re nement step we also try to attain boxes which contain no nodes (Re neUnreached-Boxes()). These boxes might not be reachable at all, or only with extreme di culty. In the re nement step we consider all nodes in all boxes neighboring empty box B e and from thereon we try to move toward B e until the device is in B e or until we give up.

Fourthly, we never call the local planner to try to connect two nodes in two di erent non-neighboring boxes.

Both the random generation of con gurations and the re nement step tend to produce small trees. In the re nement step Re neSmallTrees(), by randomly perturbating some nodes in small trees, some small trees get merged.

Performance: In Figures 2 and3 each dot indicates the position of a cart corresponding to a node (a conguration in C-Space). Figure 2 shows the node distribution when just ExtendGraphRandomly() (that is, without boxes) is used. Figure 3 shows the boxes and nodes generated using re nement and boxes. The table below shows for the same example that connectivity is captured better with fewer nodes and after fewer calls to local planner and collision checker. In this table: the number of nodes, arcs, trees in the graph; the number of calls to local planner and collision checker. In the case where boxes were not used, the largest tree contained 273 nodes, whereas the few other nodes were scattered about a tree of 15 nodes, a tree of 4 nodes and 8 trees of one isolated node. When boxes and re nement were used, the number of nodes per tree where 121, 45, 36, 27, 11, 11, 7, 3, and 3. In this table: the number of con gurations generated, ltered (by boxes, and thus tested for collision), accepted during the phase of random extension and during the re nement phases.

The table below shows the evolution of the connectivity during the graph construction for the rst experiment in Section 5. In the fth column (rej.) the number of randomly generated poses which were rejected through the ltering mechanism with boxes is listed. In the last column (lp.) the number of calls to the local planner is mentioned. 4 Integration into a CAD system ROBCAD: The CAD system ROBCAD allows to design complex scenes as well as to de ne the kinematic properties of devices. It also provides a Clibrary of functions which give access to geometrical and kinematical data of the scene as well as to some of its operations. In our implementation we used the function of ROBCAD for static collision checking. Very likely the path planner would bene t from a wellperforming function for distance computation, but we estimated the e ort needed to implement one too big and decided for functionalities with a higher priority.

Genericity: Particularities of certain devices (for instance, for safety and controllability reasons it might not be allowed to move more than one DOF of a crane at a time), and kinematic constraints (carts, for instance) can be expressed by the use of a particular local planner. We provide a library currently containing four local planners. Through the interface, in each stage of the algorithm the user can modify the choice of the local planner used. The rst local planner (LIN) tries to connect two con gurations by a simple move along a straight line in C-Space. This local planner is fast, but does not always perform well in graph construction.

The second local planner (STEP) moves only one joint at a time (a `Manhattan walk'). Sometimes such a path can be found when a linear move in C-Space is unsuccessful. Also, using the Manhattan walk in the learning phase or for replacement of the path in the path quality enhancement step, a path is found taking into account this particularity of cranes.

A third local planner (RS) is dedicated to carts with a non-holonomic constraint. It looks for a path commonly known as a Reeds-Shepp path (made up of straight line segments and circular arcs, 9]).

The fourth local planner (POT) uses a pseudopotential eld approach. It looks for a path along the linear line in C-Space. In case of a collision along that line, the planner tries to circumvene the obstacle by a small random walk away from the straight line. This local planner is useful in the query phase when initial or goal con gurations are close to an obstacle.

Quality Improvement of a Path: Once a path was found, the interface (EnhanceQuality()) allows the end-user to improve a path to the needs of the application. Two functionalities allow so.

The rst tries to shorten the path. It selects randomly two points on the path and tries to connect them with the local planner choosen by the user. In case of success, the part between these two points on the curve is replaced. By repeatedly calling this procedure the path gets shorter. This is particularly true since the initial path was found in a tree.

The second tries to replace the whole path by a new path using the local planner choosen by the user. For a cart (X; Y; ) with non-holonomic constraint any geometrical path can be transformed in a path of the type Reeds-Shepp under some often ful lled topological condition. It therefore is useful to use a simple local planner (LIN, STEP) in learning and query phase, resulting in a geometrical path, and to replace that path afterwards using RS. For a crane it can be useful to transform a path generated with LIN by a path computed with STEP so that no two joints move simultaneously. In the rst (academical) experiment, a traveling crane must move a (heavy) load up through the hole in the middle oor on the right, and down again through the hole on the left. Figure 5 shows initial and goal con gurations. The connectivity of the scene was captured by a graph of 70 nodes (consisting of 1 tree), constructed in 170 seconds. The initial path was smoothened afterwards in 35 seconds. Figure 6 shows an example of a path found by the planner. In the second experiment, a rotating crane must evacuate a bar from the centre of the scene to a position on the left. Figure 7 shows initial and goal con guration. A graph was constructed until a path was found. Since our implementation uses a static collision detector along local paths, the size of a discrete step between two calls of the collision checker along a local path in this scene must be very small. The graph was constructed in 570 seconds. The path shown in Figure 8 was generated after a smoothening phase which took 40 seconds. Reusing the same graph for other queries (other initial and goal con gurations) delivered paths as well except at some positions very di cult to reach. In the third experiment, a cart in a nuclear power plant must enter a door and set itself underneath the steam generator. Figure 9 shows initial and goal conguration. In a simpli ed model of the environment (model 1) a graph was constructed until a (geometrical) path was found in 5 minutes. The transformation of the geometrical path to a path taking into account the non-holonomical constraints (using local planner RS) took less than a minute. The resulting path is shown in Figure 10. The graph did not capture well enough the connectivity of C-Space. However, the interface allows to de ne new initial and goal con gurations and to relaunch the algorithm. The graph was enriched during another 3 minutes, and the maneuver shown in Figure 11 was found. We repeated this experiment in the original more complex model (model 2), where we used local planner RS during graph generation. In 20 minutes a path was found and a good quality graph of 46 nodes was generated. Note that the same algorithm was used for all three experiments. Constraints related to the devices were expressed in the choice of the local planner. The interface allows two ways of use. A learning phase can be launched as a pre-processing step and the resulting graph can then be re-used for several queries. Also, in a more interactive fashion, a graph can be constructed until a particular pair of initial and goal con gurations is connected, and extended each time a new query is needed. All experiments were carried out on a SUN Ultra-1, 170 Mhz. [START_REF] Hsu | On nding narrow passages with probabilistic roadmap planners[END_REF]

Experiments

Conclusions

In this contribution we described the choices we made to ful ll the needs of a tool for mobility analy-sis for feasibility studies of maintenance interventions. We described how we implemented a path planner that is well-adapted to the applications, and its interface.

The algorithm is generic in nature and successfully applicable to realistic problems appearing in industrial applications as reported here.

The current level of performance is promising but can certainly be improved. Future developments should include the development of a dedicated dynamical collision checker based upon distance measurement and distance estimation, and applied to the local paths. Also, during the learning phase an automatical decision procedure to switch to another local planner should speed up the convergence of the graph to optimal connectivity.

Figure 1 :

 1 Figure 1: Candidate Planes and Cutting Planes.The cutting is stopped once a threshold on the total number of boxes is reached, or when no box contains more than a minimal number of obstacles.In the following we will say that `con guration c corresponds to a box' if a user de ned point on the device, usually at the end-e ector, ends up being positioned in the box when the device is put in con guration c. Since a node in the graph is a con guration added to the graph, we say that `box B contains node n' if the con guration corresponds to B. We will say that two boxes are `neighbors' if their intersection is non-empty.

Figure 2 :

 2 Figure 2: Node distribution (without boxes).

Figure 3 :

 3 Figure 3: Node distribution (with boxes).

Figure 4 :

 4 Figure 4: Devices.Figure4shows three devices on which we carried out the experiments. The rst is a traveling crane with 4 DOFs (TTTR), the second a rotating crane with 4 DOFs (RTTR), the third a cart (X, Y , ). Typically devices with such kinematic structures are used for maintenance purposes in power plants of EDF. Joints of cranes are not allowed to move but one at a time. Carts usually have non-holonomic constraints.

Figure 4

 4 Figure 4: Devices.Figure4shows three devices on which we carried out the experiments. The rst is a traveling crane with 4 DOFs (TTTR), the second a rotating crane with 4 DOFs (RTTR), the third a cart (X, Y , ). Typically devices with such kinematic structures are used for maintenance purposes in power plants of EDF. Joints of cranes are not allowed to move but one at a time. Carts usually have non-holonomic constraints.

Figure 5 :

 5 Figure 5: initial and goal pose.

Figure 6 :

 6 Figure 6: a path.

Figure 7 :

 7 Figure 7: initial and goal pose.In the second experiment, a rotating crane must evacuate a bar from the centre of the scene to a position

Figure 8 :

 8 Figure 8: a path.

Figure 9 :

 9 Figure 9: initial and goal pose.In the third experiment, a cart in a nuclear power plant must enter a door and set itself underneath the steam generator. Figure9shows initial and goal conguration. In a simpli ed model of the environment (model 1) a graph was constructed until a (geometrical) path was found in 5 minutes. The transformation of the geometrical path to a path taking into account the non-holonomical constraints (using local planner RS) took less than a minute. The resulting path is shown in Figure10. The graph did not capture well enough the connectivity of C-Space. However, the interface allows to de ne new initial and goal con gurations and to relaunch the algorithm. The graph was enriched during another 3 minutes, and the maneuver

Figure 10 :

 10 Figure 10: a path.

Figure 11 :

 11 Figure 11: a maneuver. The table below indicates the geometrical complexity of the respective scenes: the number of solids and the number of facets. traveling rotating cart in cart in crane crane model 1 model 2 solids 18 270 374 1226 facets 124 8028 17089 27973