Constrained Controlled Coverage | Projects

Robotic spray painting of car bodies motivates our work in constrained controlled coverage. Painting requires that the spray gun deposit paint at each point on the target surface such that the variation of the resultant paint deposition is within acceptable limits; we term this the uniform coverage problem. To generate a spray gun trajectory termed a coverage trajectory that uniformly covers (i.e., deposits paint on) the target surface, the path planning algorithm must determine the orientation of the passes in the path, the spacing between them and the speed along the passes. If the distribution of material coming out of the applicator has a complex form, automating the process of generating coverage trajectories for uniform coverage is a challenging task even on the simplest of target surfaces such as a planar sheet. When the target surface is a non-Euclidean surface embedded in R^3, the interaction of the complex deposition pattern with the surface geometry makes the goal of achieving uniform coverage even more challenging. Moreover, the dimensionality of the variables required to specify the orientation of the passes, the spacing between them termed the index width, and the end effector speed along the passes is huge. Therefore, global optimization procedures that attempt to determine all coverage variables simultaneously are computationally expensive and often not practical. Our approach makes the optimization of coverage variables tractable by decomposing the coverage problem into relatively independent subproblems using concepts from differential geometry and standard optimization techniques.

Our approach decomposes the uniform coverage problem into four sub-problems : 1) Cellular decomposition: Segment the target surface into surface patches that are "simple"-- that is a surface that is geodesically convex and have no holes. A surface is said to be geodesically convex if the shortest curve joining any two points on the surface is a geodesic curve. 2) Start curve selection: We initiate the trajectory generation procedure by laying an initial pass termed the start curve on the surface. The cycle time required for the material deposition process as well as the uniformity of material deposition are critically dependent on the choice of start curve, or more specifically, the orientation of the start curve and its relative position with respect to the surface boundary. 3) Index width optimization: We optimize the spacing between adjacent passes termed the index width to minimize the cycle time subject to the constraint that the resultant material deposition uniformity is within acceptable levels. 4) Speed optimization: the interaction between the material deposition pattern and the surface geometry typically produces non-uniform material deposition on the target surface if the end-effector moves along the coverage path with constant speed. Speed optimization attempts to compensate for the surface curvature related results and improves the uniformity of material deposition in the direction of the passes.

We have developed procedures to solve the problems of start curve selection, index width optimization and speed optimization. The choice of the start curve has impacts the spatial orientation as well as the geodesic curvature of the resultant passes. Recall that the geodesic curvature of a curve measures how much the curve bends sideways within the surface. High geodesic curvature of the start curve typically leads to self-intersections of the resultant offset curves; these self-intersections are undesirable because they have a drastically adverse effect on the resultant uniformity of material deposition. Clearly, to minimize the possibility of self-intersections on the offset curves, the start curve should have minimum geodesic curvature, that is, the start curve should be a geodesic curve. However, the offsets of a geodesic curve on a surface with non-zero Gaussian curvature (a measure of how much a surface bends in two directions at a given point on the surface) are not geodesics. In such cases, the relative position of the start curve with respect to surface boundary determines the geodesic curvature of the offset curves. Using the Gauss-Bonnet theorem from differential geometry, we determine the optimal relative position of the start curve by finding a curve that splits the given target surface components into two parts such that the integral of Gaussian curvature on each part is the same as the other. We term such a curve as a Gaussian curvature divider. Thus, a start curve that is a geodesic and a Gaussian curvature divider minimizes the geodesic curvature on the offset curves, and equivalently maximizes the uniformity of material deposition. However, there are infinitely many Gaussian curvature dividers on a C^2 surface, loosely speaking, at least one for each orientation of the passes. To optimize the cycle time, we will select the orientation of the start curve that minimizes the number of passes and equivalently the cycle time for the coverage path.

Once we have selected the start curve, we focus towards optimizing the end-effector speed along the passes and selecting the spacing between the passes to optimize the uniformity of material deposition on the target surface. Typically, the profiles of material deposition in the direction orthogonal to that of a pass have a relatively consistent structure as we along the pass. Therefore the uniformity of material can be thought of as having two components: one along the direction of the passes, and the second in the direction orthogonal to the passes. On a planar surface, the material deposition profiles have the same structure as we move along the pass, and thus resultant material deposition is uniform in the direction of the passes. However, on curved surfaces, the deposition pattern "warps" according to surface curvature and hence, in general, the material deposition profiles vary in shape and magnitude as we move along a pass. Speed optimization attempts to compensate for these curvature related differences in the deposition profiles and improves uniformity in the direction of the passes. In our speed optimization formulation, we evaluate the uniformity of paint deposition on the entire surface for each updated time profile (equivalently velocity profile) along the path in the quadratic optimization problem. In Figure 3(b), D is the matrix [D(p_i,p_j)] which gives the deposition flux at point p_i when the spray gun is at point p_j along the path. We assume that the path is discretized into linear segments of length l_i, and t_i is the time spent by the spray gun over segment of length l_i. v_max and v_min are the maximum and minimum permissible velocities and a_max is the maximum permissible acceleration and deceleration.



Figure 3(a): Deposition profiles: the profiles of material deposition have consistent structure as we along the pass.	Figure 3(b):Speed optimization problem formulation

Finally, we want to select the optimal spacing between the passes so that the paint profiles from individual passes overlap in a manner that produces acceptable levels of material deposition on the target surface. To optimize the index width between passes on arbitrary surfaces, we first subsample the start curve at a finite number of "marker" points depending on the total curvature of the pass. At each marker point, we trace out a geodesic curve termed indexing curve that is orthogonal to the start curve, and compute a local extruded surface approximation of the target surface using the indexing curve. Along each indexing curve, we carry out a brute force optimization of an objective function that penalizes uniformity as well as cycle time over a set of possible index widths and determine the optimal index width along each marker point, and accordingly obtain the offset of the marker point along the indexing curve. The offset of the start curve is the approximated by computing the linear interpolation between the obtained offset marker points (see Figure 4).

Figure 4: At each marker point (A,B,C,D and E here) along the start curve, we first compute a local extruded surface approximation to the target surface. Then, determine the optimal index width along the orthogonal indexing curve and obtain the corresponding offset marker points A_1, B_1, C_1, D_1 and E_1.

The following figures show some results in simulation for start curve selection and speed optimization for auto-painting application .


The start curve selection method is based on a Gauss map method modified for spray painting application. The resultant path results in passes that self-intersect and hence the uniformity of standard deviation is drastically poor (45% normalized standard deviation).	When the start curve is selected as the geodesic Gaussian curvature divider, the resultant path is free from self-intersection and yields a significantly better resultant paint deposition uniformity. (16%)
Figure 5: Results for start curve selection


Resultant paint distribution simulation on a planar sheet where the end-effector speed is optimized semi-globally, that is, by optimizing the end-effector on pass by pass basis by evaluating the paint deposition uniformity over the surface "band" surrounding the given pass. (Norm Std. Deviation = 21%)	Resultant paint distribution in simulation for the same planar sheet where the end-effector is optimizing by considering the uniformity of paint deposition over the entire surface. (Norm Std. Deviation = 8%)
Figure 6: Speed optimization results.