Introduction

In the last decades, more and more minimally invasive procedures are introduced in the clinical work place [2]. At the otobasis, the focus of research has been the drilling of either a single [12, 20] or multiple [25] linear access paths through the temporal bone to the cochlea and initial reports on clinical studies have been presented [4, 17]. In such interventions, several obstacles or risk structures, e.g., the facial nerve and its small branch (Fig. 1, yellow objects), severely limit the space that is available for drilling.

Unlike these linear approaches, nonlinear drilling provides several potential advantages: larger distances to risk structures, correcting misalignments while drilling, and optimization of orientation at the goal point (e.g., for the insertion of the electrode during a cochlear implantation or for instrument alignment). Yet, nonlinear planning at the otobasis is difficult to deploy due to the limited space and time constraints on intra-interventional planning. To the best of our knowledge, such an approach has never been investigated. In this paper, we consider the use of a curvature constrained drilling unit and propose two new RRT-Connect [18] algorithms to quickly (re-)compute feasible access paths for said robot: once at the beginning of the intervention and regularly in between if navigation errors occur (Fig. 1).

Fig. 1
figure 1

A nonlinear access path (orange) has to be drilled through the temporal bone (empty space) by a surgical robot (colored) to reach the target of an intervention. Various organs (different colors) form obstacles that our planning algorithms have to avoid (e.g., blue and green search graph of a RRT-Connect)

Full size image

In recent years, significant progress has been made in the development of continuum robots and instruments for minimally invasive medical applications [3]. Many of these can be categorized as “curvature constrained objects.” These include, for example, steerable needles [6, 7] for interventions in soft tissue [8, 21] or flexible endoscopes [10]. If such underactuated systems are used, where instrument steering is limited to certain directions, nonholonomic motion planning based on the Rapidly Exploring Random Tree [1, 18] or even optimal randomized motion planners [11, 15] are used to plan feasible trajectories around obstacles for the underlying instrument.

In medical applications, the main focus mainly lies on steerable needles where planning is done with variants of the RRT. These methods consider, for example, special distance functions [21] or the reachable set of the nearest states [24]. Other methods speed up the convergence via potential fields [29] or utilize heavy parallelization [19].

The planning of trajectories for (unmanned) aerial vehicles such as drones or missiles also requires curvature constrained motion planning. Here, the development of an analytical solution of the 3D Dubins Problem [14] leads to an RRT*-solver [22] in the case that start and goal regions are sufficiently far away. Moreover, Yang et al. [27, 28] presented an RRT* with Bézier splines as local planning technique.

However, curvature constrained motion planning for temporal bone surgery requires fast and precise algorithms with start and goal regions in \(\mathrm{SE}(3)\) within a small and dense environment. Although we were able to show the general feasibility of such trajectories within the otobasis [9], a reliable method does not yet exist.

The main contribution in this paper is then twofold: First of all, we present two RRT-Connect algorithms which achieve fast path planning for nonlinear temporal bone surgery. Secondly, we address a novel evaluation strategy in case of limited annotated data sets: The robustness of such planners is shown on synthetic anatomies based on statistical shape models from real CT patient data.

Objective

Minimally invasive procedures require a planning step that computes feasible trajectories while respecting potential constraints such as clearance to organs or instrument mobility. After the computation of a set of solutions, these are then optimized according to a cost function or other optimization strategies [13, 25].

In motion planning, relevant parameters are usually expressed in a specific Problem Formulation [18]. In this section, we describe the details for temporal bone surgery and how they are incorporated in the following Formulation:

Fig. 2
figure 2

a Prototype of the hydraulically driven robot with a drill bit at the front. b Model of the robot based on geometric primitives and its local coordinate frame

Full size image

Problem Formulation For Temporal Bone Surgery

  1. 1.

    Let \(O\subset \mathrm{SE}(3)=\mathbb {R}^3\times \mathrm{SO(3)}\) be the obstacle region, defined by the location of several risk structures \(\{\mathscr {R}\}_i\subset \mathbb {R}^3, 0\le i\le N\). That is, \(O := \{q=(x,h)\in \mathrm{SE}(3)\vert \exists i, 0\le i\le N : x\in \mathscr {R}_i\}\). Let \(C_{\mathrm{free}} = \left\{ q\in \mathrm{SE}(3)\vert q\notin O \right\} \) be the free space of the configuration space.

  2. 2.

    Let \(C_I\subset C_{\mathrm{free}}\) be the initial region.

  3. 3.

    Let \({M_G\subset C_{\mathrm{free}}}\) be a set of states. The goal region \(C_G\) is then defined as

    $$\begin{aligned} C_G\equiv & {} C_G(\varepsilon _G, \phi _G) = \{ q(x,h)\in \mathrm{SE}(3)~|\nonumber \\&\Vert x-y\Vert _{\mathbb {R}^3}<\varepsilon _G, \rho (h,g)<\phi _G,\\&\text {for a}~\hat{q}(y,g)\in M_G\}, \end{aligned}$$

    where \(\rho \) is defined as in Eq. (1) and

    1. (i)

      \({\varepsilon _G \in \mathbb {R}^+}\) is the maximally allowed Euclidean distance and

    2. (ii)

      \(\phi _G\in [0, \pi ]\) is the maximally allowed angular difference at a specific goal state.

  4. 4.

    Let \({d_{\mathrm{max}}\in \mathbb {R}^{0+}}\) be the safety distance to risk structures. Let \(r_d\in \mathbb {R}^+\) be the radius and \({\kappa _{\mathrm{max}}\in \mathbb {R}^+}\) the maximum curvature constraint of the drilling robot.

  5. 5.

    Let \(T_{\mathrm{max}}\in \mathbb {R}^+\) be the maximum time constraint available for planning.

  6. 6.

    Task: Find a path \(\gamma (t) : [0,1] \rightarrow \mathrm{SE}(3)\) satisfying

    1. (i)

      \(\gamma (0)\in C_I\)

    2. (ii)

      \(\gamma (1)\in C_G\)

    3. (iii)

      \(\forall t\in (0,1): \left\| \gamma ''(t)\right\| < \kappa _{\mathrm{max}}\)

    4. (iv)

      \(\forall t\in [0,1], o\in O: \left\| \gamma (t)-o\right\| _{\mathbb {R}^3} > r_d + d_{\mathrm{max}}\)

    or report that no path could be found in the available time \(T_{\mathrm{max}}\).

Item 1 of this Problem Formulation introduces obstacles in \(\mathbb {R}^3\) (e.g., the facial nerve) that have to be circumnavigated, as well as the free space, which defines potential positions the drilling unit can occupy. Item 2 corresponds to potential positions at the skull’s surface that serve as entry points of instruments, whereas Item 3 defines a spherical volume in \(\mathbb {R}^3\) as the intervention’s target together with a threshold \(\phi _G\) that limits the potential orientation within this target volume. The orientation between two configurations is compared in the quaternion metric (see e.g., [18])

$$\begin{aligned} \begin{aligned}&\rho (h_1, h_2) = \text {min}\left\{ \rho _S(h_1,h_2),\quad \rho _s(h_1,-h_2)\right\} \\&\rho _s(h_1,h_2) = \cos ^{-1}(a_1a_2+b_1b_2+c_1c_2+d_1d_2). \end{aligned} \end{aligned}$$
(1)

In this paper, we consider the use of a prototype robot (Fig. 2) currently under development for the creation of nonlinear access paths. If we consider the z-axis in the local coordinate frame of the model as the robot’s line of view, we want to match its pose with the ones at start and goal states: Initial states should be close to the skull’s surface normal in order to minimize deviation from the desired trajectory due to forces applied during drilling. For a cochlear implantation, for example, goal states at the round window would represent the optimal insertion angle. Here, work has been done to limit the deviation from the optimum to less than \({5}^{\circ }\) [26].

The robot’s limitations are then included via Item 4: The radius of the drill bit and an additional safety distance to account for navigation errors or heat generation are combined to a distance constraint. Additionally, the maximum turning angle of the prototype results in a curvature constraint. Item 5: Potential misalignments during navigation require an intra-interventional replanning step to either provide a new corrected trajectory or stop the drilling. Therefore, an algorithm has to be fast enough to provide a smooth intervention. Item 6: A motion planning algorithm for this procedure will then try to find a feasible path in the available time which would result in a trajectory connecting both a start and a goal state (i, ii), observing a maximally allowed curvature (iii) and last, a necessary distance to risk structures (iv).

Note 1 This formulation remains valid in the case of replanning where the initial region \(C_I\) of Item 2 will be set to the current pose of the robot.

Note 2 This formulation extends the problem of trajectory planning in soft tissue for bevel-tip needles, where alignment of instruments [23] and regular fast replanning [21] is needed, by introducing constraints on both start and goal orientations. We expect our planners to be useful for this kind of application as well.

Methods

The main difficulty of this problem is the fast and precise matching of the goal’s pose. An intuitive way to address this problem is to use an RRT-Connect algorithm [16]. This method, unlike basic RRTs, grows search trees from both the goal and the initial region in an attempt to connect these two. With this strategy, more possible connections are available than just those between search tree and goal regions. Thus, successfully finding an access path is more likely. The general RRT-Connect can be described as follows (Algorithm 1):

Two trees \(\mathscr {T}_I, \mathscr {T}_G\) are initialized with states of the initial and the goal region, respectively. Both trees are iteratively extended until either the maximally allowed time \(T_{\mathrm{max}}\) is reached or the graphs are connected successfully. In each iteration, the two search trees take turn in the following procedure: A random state is drawn from the free space \(C_{\mathrm{free}}\). Then, the nearest neighbors to the current tree are computed according to a previously defined distance function. For each of these configurations, the local steering function computes an expansion toward the random state. If no collision with obstacles occurs along this path, the state is added to the tree. Last, the algorithm tries to connect both trees according to the state space’s constraints (in our case the path needs to be two times continuously differentiable). If both trees are connected within the given time threshold \(T_{\mathrm{max}}\), the resulting path is returned. Otherwise, failure is reported.

figure a

In the following, we shortly recall two local steering methods, one based on circular arcs of varying curvature and one based on Bézier–Splines. We then present two individual solutions that extend these planners to RRT-Connect versions.

Bevel-Tip-RRT & k-B-RRT-Connect: We use the local steering function developed for Bevel-tip needles presented in [21] to create access paths of variable curvature. This method extends the search tree along circular arcs of variable radii. The RRT-Connect version uses Dubins Paths in 3D to connect the search trees as, unlike circular arcs, this is a technique to connect states in \(\mathrm{SE}(3)\).

Spline-Based-RRT & k-SB-RRT-Connect: The second RRT utilizes cubic Bézier–Splines to interpolate in \(\mathrm{SE}(3)\), resulting in an approximation of states in the search tree and a two times continuously differentiable trajectory [28]. Here, the local steering method can be used naturally to attempt a connection.

The individual steps in Algorithm 1 (lines 4, 6, 8, 12) are then as follows:

sample_state: Sampling in \(\mathrm{SE}(3)\)would require solving a two point boundary value problem, i.e., matching both location and orientation at the random state. This is not possible with either steering function. Instead, a state is merely sampled in \(\mathbb {R}^3\), and the direction is implicitly defined according to the respective method.

k_nearest_neighbors: The nearest neighbor function and its underlying metric have significant impact on the time efficiency and the theoretical properties of the algorithm. For curvature constrained instruments, the Euclidean metric does not represent a good approximation on the actual distance. On the other hand, the computation of a more complex metric like the reachable set of a particular state [24] can be very time consuming. As the main interest in this application lies in the fast computation of a feasible path, we return the k-nearest neighbors in terms of the efficiently computable metric

$$\begin{aligned}&d(q_1(x,h_1),q_2(y,h_2)):\mathrm{SE}(3)\times \mathrm{SE}(3)\rightarrow \mathbb {R}^3\\&\quad :=\Vert x-y\Vert _{\mathbb {R}^3} + \rho (h_1,h_2) \end{aligned}$$

steer: \(\kappa \)-B-RRT-Connect propagates the search along states on circular arcs. The local planner of \(\kappa \)-SB-RRT-Connect uses a spline consisting of two Bézier–Spirals to expand the search tree. We refer to the original papers [21] and [28] for a detailed description.

attempt_connection: The original RRT-Connect does not address nonholonomic planning and considers the trees connected if both trees meet at the random sample. This approach would result in a discontinuous orientation at the connecting state as we sample only in \(\mathbb {R}^3\) and do not enforce a specific orientation. Instead, a two point boundary value problem has to be solved in our approach to match both position and orientation:

First, we search for a state of the other tree in the vicinity of \(q_{\mathrm{next}}\). Specifically, we check if a state lies within a cone that apex and direction are described by the location and orientation of \(q_{\mathrm{next}}\). If such a state is found, we try to connect these two:

The \(\kappa \)-B-RRT-Connect algorithm connects two corresponding states by solving the 3D Dubins problem with the geometric approach presented in [14]. A similar method is used in [22]. Both papers address the computational complexity of their approach. However, our c++ implementation requires on average only 45 microseconds to solve the underlying nonlinear system of equations which makes it suitable for fast computation.

The \(\kappa \)-SB-RRT-Connect algorithm iteratively uses the local steering function to steer from \(q_{\mathrm{next}}\) to its counterpart and vice versa. This procedure is repeated until either the interpolation criterion of the Bézier–Spline is satisfied during an iteration or the states missed each other, and thus no connection was possible.

Fig. 3
figure 3

Examples of the access paths (Cochlea-/SSC-/RL-Access) for real (a) and synthetic (b) anatomies

Full size image
Table 1 Parameters for the problem formulations (see “objective” section) of the three access paths
Full size table

Scenarios for the temporal bone

We address three typical medical interventions for the experiments to show the general suitability for temporal bone surgery (Fig. 3): one access to the cochlea via the facial recess (Cochlea-Access) and two accesses to the internal auditory canal: through the superior semicircular canal (SSC-Access) and via the retro-labyrinthine region (RL-Access). Parameters for each Problem Formulation (see “Objective" section) are listed in Table 1. The curvature constraint reflects our current robot prototype. We tested with higher values of \(r_d\) and \(d_{\mathrm{max}}\) for the RL- and SSC-Access as there is usually more space between obstacles. The time and orientation constraints were chosen according to real applications [23, 26].

The risk structures, i.e., organs in the vicinity of access paths that must not be harmed, were extracted from real CT data of patients. To this purpose, our clinical partners manually segmented the internal carotid artery and jugular vein bulb, facial nerve and chorda tympani, cochlea, ossicles and labyrinth as well as the internal and external auditory canal in 40 high quality, but typical routine CT scans of the human temporal bone (Siemens Somatom, average resolution \(0.18\times 0.18\times 0.4\,\mathrm{mm^3}\)).

The manual assembly of such real scenarios is a necessary but extremely laborious and time consuming task. However, a statistical analysis of the motion planner’s performance requires a much larger number of samples than this manual procedure can provide. Consequently, we divided the experiments into two setups:

Real anatomies: For the first 22 data sets, we also segmented the brain and the skull’s surface. In the resulting 3D environment, entry and target positions of potential interventions were manually placed in each individual data set with the help of a custom planning tool to provide samples on real patients (Fig. 3a).

Synthetic anatomies: First, we created statistical shape models [5] of the manually segmented risk structures of the otobasis in all 40 data sets. Then, we generated 100 synthetic anatomies based on the real ones. For each new synthetic anatomy, one of the real anatomies was chosen randomly to serve as an atlas, including its risk structures and its goal regions of the three potential interventions. A variation of the statistical shape models was then registered to the atlas to replace each original structure with an altered variant (Fig. 3b).

Fig. 4
figure 4

Box plots for each access canal about the number of paths found by the individual planners in 22 real anatomies (higher = better)

Full size image
Table 2 Performance of each planner for the real anatomies. Measured in median number of paths (#), median number of paths per second (#/s) and percentage of failed scenarios (F)
Full size table

Experiments

In the following, we describe in detail the setup of real and synthetic anatomies as well as the parameters of our motion planners.

Real anatomies:

In each data set and for each of the three applications (RL-, SSC-, Cochlea-Access), we placed one state within the temporal bone and one state on the skull’s surface to define the regions \(C_I\) and \(C_G\) of the Problem Formulations. Start states were positioned at the bottom of the internal auditory canal, at its top and next to the round window for the RL-, SSC- and Cochlea-Access, respectively. This resembles a potential position of an acoustic neuroma (RL-, SSC-Access) or the entry point of the electrode in a cochlear implant (Cochlea-Access). The directions at these start states were defined as a compromise between the respective organ’s normal at this position and a direction toward the skull’s surface. Last, three states were placed on the skull with orientations approximately orthogonal to its surface which serve as goal states for the individual access paths.

Synthetic anatomies:

For each new synthetic anatomy, random variations of the individual statistical shape models’ modes were computed by sampling the corresponding eigenvalues between \(\pm \,1.0\) times of their standard deviation. The resulting model was then registered with the reference atlas. For the respective goal states, we used the ones in the atlas. The start states required a new strategy for positioning, as their original pose in the atlas might be invalid. Thus, new start states were placed above/below the center of mass of the internal auditory canal (SSC-/RL-Access) and below the center of mass of the cochlea (Cochlea-Access). For orientation, individual reference points \(P_{\mathrm{ref}}\in \mathbb {R}^3\) were computed: for the RL-Access slightly inferior to the lower side of the bounding box of the facial nerve; for the SSC-Access above the center of mass of the semicircular canals and for the Cochlea-Access in the center of mass of the chorda tympani. The start states were then oriented so that the z-axis of the local coordinate frame points to the respective reference point.

Motion planning: In both setups, we let each of the four planners of “Methods” section calculate as many paths as possible within 20 s for all three applications. We used the number of found paths to quantify the performance of each planner. In order to compare the quality of paths computed by each planner, we measured for each trajectory both the deviation at the goal state and the minimal distance to risk structures.

For goal biasing, we chose a value of \(25\%\). The attempt_connection method of \(\kappa \)-RRT-Connect was most successful with parameters \(h=5.0\) mm and \(\alpha ={20}^{\circ }\) for height and angle of the cone. A kd-Tree was used for collision checking between states and obstacles. All experiments were performed on a system with an Intel Core i5-6500 CPU @ 3.20 GHz and 32,0 GB RAM.

Results

We start with analyzing the motion planners’ results on real anatomies. Then, we discuss their generalization on synthetic data.

Fig. 5
figure 5

Box plots about the deviation at the goal for the real anatomies (lower = better)

Full size image
Fig. 6
figure 6

Close-up of the narrowest region of each access canal. The corresponding table shows the mean and max distance of each planner over all real anatomies together with the percentage of how often each planner found the best path according to the maximum distance

Full size image

Real anatomies: First, we look at the number of paths found in a specific time to ensure a planner is fast enough for intra-operative replanning [21]. Figure 4 and Table 2 show the statistical distributions: For both the Cochlea- and the SSC-Access, our RRT-Connect algorithms clearly outperformed standard RRT planners. In the case of the RL-Access, the Spline-Based-RRT showed similar performance but none of the three algorithms really stands out. The number of paths found per second and the low number of failures indicate that \(\kappa \)-RRT-Connects work very well for the first two access canals, and we can expect that successful intra-operational planning can be performed in minimal time. In contrast, the search through the retro-labyrinthine region was unsuccessful for almost half of the anatomies. This is, however, not unexpected because the risk structures vary highly between patients: In case of a narrow passage between facial nerve and chorda tympani, a small semicircular canal or a high reaching bulb of the jugular vein, the creation of a feasible access path was impossible. Indeed, a careful inspection showed that in the 6 cases algorithm C failed and a high reaching jugular vein bulb made a trajectory of the requested size completely impossible. The discrepancy between the first two problem formulations and the latter is also due to the nature of relevant obstacles in the respective area. In the first two cases, a bottleneck had to be passed (two nerves/the SSC), whereas for the RL-Access the facial nerve and the jugular vein had to be circumnavigated.

Now we look at the matching of the goal’s pose. Naturally, RRT-Connect algorithms matched the orientation of goal states perfectly, whereas the RRTs were limited to an approximation (Fig. 5). We also note that in all three cases both Bevel-Tip-RRT and Spline-Based-RRT tended to accomplish the maximal allowed deviation rather than a perfect match.

Next, we focus on the minimal distance an access path had to risk structures as this is usually the most relevant metric to clinicians. To this purpose, we interpolated between the states of the search tree at a resolution of 0.1 mm. For each of those interpolated states, we then sampled points on a circle with radius \(r_d\) and orthogonal to the state’s direction and computed the minimal distance to the next obstacle. Figure 6 shows in small images the narrowest region that had to be passed together with three statistics for each planner across all 22 anatomies: the percentage how often it computed the best path for a specific anatomy (Best), the mean minimal distance its best path had to risk structures (Mean) and the overall best path it computed across all anatomies (Max). Clear superiority of a specific algorithm was not observable although the Spline-Based-RRT tended to find paths with the largest distance more often. Hence, our new \(\kappa \)-RRT-Connect did not suffer from lower quality. From the observed distances, we also got an impression of the average size of the passed bottleneck. This can help in the design for the robot prototype. According to Table 2, for example, \(\kappa \)-RRT-Connect always found trajectories for an SSC-Access with the specifications in Table 1, having on average still a minimal distance above 1.0 mm to the nearest obstacle.

Fig. 7
figure 7

RL-access planned by a standard RRT (pink tube) with safety distance 1.0 mm and by a \(\kappa \)-RRT-Connect (green, orange) with safety distances 1.0 and 1.5 mm, respectively

Full size image
Fig. 8
figure 8

Box plots about the success rates of the planners in 100 synthetic anatomies (higher = better)

Full size image

Last we address the issue that in many scenarios the Spline-Based-RRT found paths with the highest minimal distance. A closer inspection showed that the \(\kappa \)-RRT-Connect just quickly found a solution as soon as the relevant obstacle had been passed. When we enlarged the allowed safety distance, the \(\kappa \)-RRT-Connect computed paths with similar minimal distances. Figure 7 shows an example of this behavior for the RL-Access with safety distance 1.0 and 1.5 mm.

Synthetic anatomies: To study the generalization of these specific cases, we then looked at synthetic scenarios. Instead of real anatomies we now worked with variances based on atlases of real data combined with the shape space of the statistical shape models. Our evaluations then included a much broader variety of anatomies. By randomly sampling the shape space, we also made sure that the individual real anatomies did not provide edge cases for the algorithms, a standard approach in motion planning [11, 15].

Table 3 Measured in median number of paths (#), median number of paths per second (#/s) and percentage of failed scenarios (F)
Full size table
Fig. 9
figure 9

Close-up of the narrowest region of each access canal. The corresponding table shows the mean and max distance of each planner over all synthetic anatomies together with the percentage of how often each planner found the best path according to the maximum distance

Full size image
Fig. 10
figure 10

Box plots about the deviation at the goal for 100 random synthetic anatomies (lower = better)

Full size image

The results in Figs. 8 and 9 and Table 3 show how the planners performed for each access canal. From the box plots, we can conclude that \(\kappa \)-RRT-Connect again tended to find many more paths. Their performances according to Table 3 supported the results of the real cases: For the given parameters of Table 1, access paths for the Cochlea- and SSC-Access were always possible, whereas for the RL-Access a high reaching jugular vein often prevented a feasible trajectory to be found. The number of paths found per second again indicated that bidirectional RRTs are suitable for intra-operational planning. An analysis of the orientation at the goal showed equivalent results to the real cases: RRTs hardly realize a good match of the desired orientation (Fig. 10). Although this was expected, it clearly supports our claim that bidirectional planners are required, if precise replanning is necessary.

Conclusion

In this paper, we address a minimally invasive procedure with demands on fast computation and high precision of both initial and goal pose. We present two suitable RRT-Connect motion planners, one based on Bézier–Splines, the other on circular arcs and 3D Dubins Paths, which quickly compute feasible curvature constrained access paths for the proposed interventions. The efficiency of these planners is shown in real CT data of patients as well as on randomized anatomies created from variations of statistical shape models. These tailored RRT-Connect algorithms outperform state-of-the-art one-directional planners and provide a reliable and fast method for planning access paths in temporal bone surgery.

In the future, we want to improve the approach for both methods with an optimization of planned paths regarding larger distances to risk structures or more advanced metrics. We also expect that an improvement of the connection method of our RRT-Connects will result in better performances for difficult cases like passing the retro-labyrinthine region. Moreover, we would like to investigate the applicability of these general purpose planners for other medical interventions such as needle insertion in soft tissue [23] or flexible endoscopes [10]. We believe such precise nonlinear planning procedures are expected to be instrumental in improving interventions and advancing patient safety at operating rooms of the future.