# An Effective Algorithm for Finding Shortest Paths in Tubular Spaces
## 1 Introduction
### Related Works  
In general 3D space, the problem of finding the ESP between two given points that does not intersect with any given obstacles is known to be NP-hard [20]: special cases of this problem have been studied as follows. The authors in [21] gave a polynomial time algorithm to calculate ESP for cases in which the number of obstacles is'small' and all of them are convex. Another algorithm was proposed in [22] with the assumption that all obstacles are vertical buildings with k different heights. More recently, Ref. [23] presented algorithms for solving approximate ESPs amid convex obstacles. Other approximation algorithms for ESP calculations are detailed in [24]. These studies share common features in that a collection of finite obstacles are given as forbidden zones in space and the ESP will be found in the space surrounding these obstacles.  
In the studied problem, the obstacle is the entire space outside the tube and the ESP must pass through the inner zone of the tubular space. A similar problem can be found in [25] that computes the minimal path in tubular space. The minimal path is typically solved based on the Fast Marching Method (FMM) which only considers grid nodes as the possible vertices of the minimal paths. However, the paths detected by the FMM have been proven to be not always the exact ESPs [1]. Several approximation algorithms also exist for finding the ESP between two points in 3D space bounded by a closed surface such as cube-curves [26] or a simple polyhedron [27] using the rubberband algorithm. This method is suitable for solving various ESPs in 3D space. Even so, there is a non-trivial gap in the geometric shape between the cube-curve and the tubular space. Polyhedron seems like a better choice to represent a tubular space. However, the characteristic geometrical properties of tubular spaces should be considered for a dedicated algorithm.  
The study of a tubular surface with Bishop frame was proposed in [28]. The authors provided some characterizations about the special curves lying on this surface (e.g., geodesic and asymptotic curves). However, the problem studied herein requires considering the interior space instead of just the boundary surface. In addition, the geometrical properties of the ESP inside the tubular space also need to be investigated. The authors in [29] described a simple geometric structure of ESPs where they consist of curved paths on the obstacles connected by straight line segments (see Theorem 1). In this work, we develop the geometric structure of ESPs presented in [29] by considering the characteristic properties of tubular spaces.  
In practice, the navigation problem can be classified into planning-based and reactive algorithms [30]. Planning-based approaches require a global map representation of the environment (e.g., a graph or a network) before searching. Prior knowledge of the tubular space enables the generation of a weighted graph where the weight of each edge (or arc for the directed graph) is associated with its length [24]. Numerous algorithms are used for the shortest path calculation in graph theory (see Chapters 24 and 25 in [31]). A well-known graph-based algorithm among them is [PERSON]'s algorithm [32] in which the shortest path connects vertices in the graph. Unlike the planning-based approaches, a reactive method allows directly generating motion decisions during the movement based on observed data [30]. The reactive shortest path navigation was presented in [33] for an in-plane problem. Such a problem was also found in 3D space where the obtained path is interpolated with a spline curve [34]. In this work, we propose an algorithm based on the observed information of a virtual particle that can be used as a reactive method for the shortest path navigation inside the tubular space.