## 3 Proposed Post Triangular Processing of the Midpoint Interpolation Method  
The proposed post triangular processing of the midpoint interpolation method can be applied to path planning algorithms that do not guarantee optimality, such as the RRT algorithm, and rewiring and midpoint interpolation based on the triangular inequality principle. The assumptions of the proposed method are as follows:  
1. The destination point may change gradually over time, but there is only one start point and one destination point for each tree. 2. If the mobile robot cannot perform the omnidirectional motion, local planning or kinodynamic planning is performed separately on the path planning result. The basic principle is that the node serving as a waypoint in the planned path checks whether an obstacle collides with its own grandparent node, and if it is free from obstacle collision, the grandparent node rewires to the parent node. If it is not free from obstacle collision, as shown in Figure 3, the locally piecewise linear path created between the node, its parent node, and its grandparent node is made a more optimal path through the interpolation process. In this process, a new node is interpolated into the path and deviates from the piecewise linear path, so it has the advantage of being able to somewhat solve the sharp path problem (the problem facing a mobile robot that has kinematic constraints because the slope is not smooth). This post triangular processing of the midpoint interpolation method was designed based on the polygon approximation algorithm [18; 19], so, as shown in Figure 4, the path is calculated through a constant value called \(\epsilon\) (the threshold of minimum clearance) (\(\epsilon>0\)). It determines how closely the obstacle is approximated or, in other words, how close to the optimal path it is. Here, in Figure 4, \(d\) follows Equation (1):  
\[d_{n}(q_{i})=\left\{ \begin{array}{ll}\left(d_{n-1}(q_{i})\right)/2,&n>0\\ \left(2\sqrt{s(s-\alpha)(s-\beta)(s-\gamma)}\right)/\gamma,&n=0\end{array}  \right. (s=(\alpha+\beta+\gamma)/2) \tag{1}\]  
Figure 4: Interpolation function of post triangular processing of the midpoint interpolation method: (**a**) height \(d_{0}\) of the triangle formed by waypoints \(q_{0}\), \(q_{1}\), and \(q_{2}\) of the path is greater than \(\epsilon\) (interpolation continuation); (**b**) height \(d_{1}\) of the triangle formed by midpoints \(m_{F}(q_{0}\),1) and \(q_{1}\) of \(q_{0}\) and \(q_{1}\) and midpoint \(m_{F}(q_{0}\),1) is the midpoint of \(q_{0}\) and \(q_{1}\), also \(m_{F}(q_{1}\),1) is the midpoint of \(q_{1}\) and \(q_{2}\). Figure 3: Summary of post triangular processing of the midpoint interpolation method: (**a**) line segment \(\gamma\) with node \(q_{0}\) and its grandparent node \(q_{2}\) in tree \(R\) is not free from obstacle collision; (**b**) Parent node \(q_{1}\) of \(q_{0}\) is deleted, and \(q_{a}\) between \(q_{0}\) and \(q_{1}\), and \(q_{b}\) between \(q_{1}\) and \(q_{2}\) are inserted as waypoints of a new path between \(q_{0}\) and \(q_{2}\). Here, \(\xi()\) is a function that receives the node as a variable and returns the parent node of that node. The \(n\)-squared (\(n\geq 0\)) of the \(\xi()\) function can be expressed as \(\xi^{n}(q_{i}):=\langle\overline{\left(\xi\circ\xi\circ\ldots\circ\xi\right)}(q_ {i})\rangle\), and if \(n\) is 0, \(\xi^{0}(q_{i}):=q_{i}\) holds. For the waypoint \(q_{i}\), the value of \(d\) decreases by \(1/2\) as interpolation proceeds (\(n\)). The initial value \(d_{0}\) is the height of the triangle formed by the three line segments \(\alpha\), \(\beta\), and \(\gamma\) (\(\gamma<\alpha+\beta\)), and the value of \(d_{n}\) becomes \((d_{n-1})/2\). Based on \(q_{i}\), let \(\alpha\) be the line segment from itself to the parent node, \(\beta\) be the line segment from the parent node to the grandparent node, and \(\gamma\) be the line segment from itself to the grandparent node. This \(d\) value serves as a measure to confirm the clearance of the obstacle compared to \(\varepsilon\).