Force extrapolation

Our aim is to generate forces at a rate of 500Hz from forces computed by the deformable object simulation at a rate of about 30Hz. A solution could have been to introduce a time delay which value is the time needed to compute one simulation step, and to interpolate retrospectively the computed forces. But two major drawbacks prevent us from using this solution. First, this delay is not acceptable for a surgical gesture. Second, the time needed to compute one simulation step can vary somewhat. Thus we choose to estimate the current force by extrapolating the previously computed ones.

The force extrapolation process is described next.
The simulation loop gives us a discrete series of parameters $(t_n,\P_n,\ensuremath{\mathbf{F}} _n)$ representing the force $\ensuremath{\mathbf{F}} _n$ applied on the tool in position $\P_n$ at time t_n. The time step between two successive t_n is about 0.04s (visual real-time) and is not necessarily constant. Good quality force feedback can be reached by an update of the force at about 500Hz. So, we must choose an extrapolation function $\ensuremath{\mathbf{F}} (t)$ providing an estimation of the force to apply to the tool at time t $(t_n \leq t<t_{n+1})$ according to already known data $(t_i,\P_i,\ensuremath{\mathbf{F}} _i),\;i=0..n$.

A very popular method for this kind of estimation is Kalman filtering. As defined in preface of [10], Kalman filtering is an optimal state estimation process, which gives a linear, unbiased, and minimum error variance algorithm to estimate the unknown state of a dynamic system from noisy data taken at discrete real-time intervals. But in our case, the absence of random perturbations directs our research towards a simple model of extrapolation.
In order to validate our approach, we have tested different extrapolation functions.

Constant extrapolation

The easiest way to produce the unknown data from the known one is to use the latest computed force as a guess for the current one.

$$\ensuremath{\mathbf{F}} ^{cst}(t) = \ensuremath{\mathbf{F}} _n \hspace{2cm}t_n \leq t < t_{n+1}$$

This extrapolation method has several advantages. First, it needs no computation. Then, as the applied force results from the deformation computation, such an extrapolation scheme ensures us to apply only valid forces. There is no risk of applying too large a force which could damage the device. In most force feedback devices, this extrapolation scheme is a part of the hardware and is automatically applied. This is the case of the Laparoscopic Impulse Engine hardware. Obviously, this method takes into account only the last computed force and produces a false estimation of the force as soon as it changes to another step. The main problem with this method is the discontinuity of the applied force which gives the sensation of touching a rough surface as soon as the refresh rate becomes too low (under about 300Hz).

Linear extrapolation over time

Another way to estimate the current value of a signal changing over time is to extrapolate it over time. As our deformable model sketches a linear elastic behavior, we only consider linear extrapolation.

Let us call t^e_n+1 and $\ensuremath{\mathbf{F}} ^e_{n+1}$ the time and the force estimated for the next data triplet, extrapolating the force linearly is equivalent to interpolating linearly on the interval of time [t_n,t^e_n+1] the forces $[\ensuremath{\mathbf{F}} _n,\ensuremath{\mathbf{F}} ^e_{n+1}]$.
Assuming that the simulation runs at a constant frequency, we have:

t^e_n+1=t_n+(t_n-t_n-1).

If we suppose that the force variation is linear in time, we have the following definition of the force function:

$$\ensuremath{\mathbf{F}} ^{t}(t) = \frac{t - t_n}{t_n - t_{n-1... ... + \ensuremath{\mathbf{F}} _n \hspace{2cm}t_n \leq t < t_{n+1}.$$

This method gives better results than the previously described one. The force discontinuities are less noticeable. But we must face a new problem, as the applied forces are not the ones that the simulation of the deformable model computes, they can be arbitrarily large. These force amplitude peaks occur especially when simulation time step increases $(t_n-t_{n-1} \ll t_{n+1}-t_n)$.

Linear extrapolation over position

The force changes are mainly due to the tool movement. In the case of a dynamic deformable model, the force also changes slightly over time, even if the tool doesn't move, when the model evolves towards its rest position. The tool position is thus vital for guessing what is the force applied to it by the deformable model. Although computing physically based deformation at the needed frequency is not yet possible, nothing prevents us from querying the force feedback device to know the tool position at such a high frequency. These observations lead us to develop a force estimator based on the tool position.

  

Figure: Tool position projection for extrapolation over position

As the tool position is not a scalar value, we can not directly apply the algorithm previously presented. A way to obtain comparable scalar values is to project the current tool position in ' on the line defined by the two precedent tool position $\P_{n-1}$ and $\P_n$ (figure 2). We can then consider the norm ratio for extrapolation:

$$\ensuremath{\mathbf{F}} ^p(t) = \ensuremath{\mathbf{F}} _n + ... ...ensuremath{\mathbf{F}} _{n-1}) \hspace{2cm}t_n \leq t < t_{n+1}$$

We can notice that the error induced by the tool position projection is null, when $\P_{n-1}$, $\P_n$ and are aligned, in other words when the tool trajectory is a line.

All of these three extrapolation methods were implemented in our surgery simulator. In order to compare and to evaluate them, several experiments were performed. The results are presented in the next section.