Quantum Algorithm in Path Optimization for Autonomous Underwater Vehicle: Hardware-in-the-Loop experiment

2.1. The AUV kinematic model / Kinematički model AUV-a

Figure 1 Inertial frame and body-fixed frame of AUV

Slika 1. Inercijski koordinatni sustav i koordinatni sustav vezan uz AUV

The AUV motion is considered in two coordinate systems: the Earth-fixed system and the AUV-body system. The body coordinate system helps determine the velocity and direction of an AUV’s motion. The AUV motion in the two coordinate systems is described by Fig. 1 [20], which operates with six degrees of freedom. Therein, [TeX:] v = {\lbrack u,v,w,p,q,r\rbrack}^{T}$v={[u,v,w,p,q,r]}^T$ denotes the linear and angular velocity in the body coordinate system, and [TeX:] J(\eta)$J\left(\eta \right)$ is the rotation matrix. The AUV's position [TeX:] \eta_{1} = {\lbrack x,y,z\rbrack}^{T}${\eta }_1={[x,y,z]}^T$ and orientation [TeX:] \eta_{2} = {\lbrack\varphi,\partial,\psi\rbrack}^{T}${\eta }_2={[\phi ,\partial ,\psi ]}^T$ are given by [21]-[22]

[TeX:] \eta = J(\eta)v$\eta =J\left(\eta \right)v$ (1)

[TeX:] J(\eta) = \begin{bmatrix} \eta_{1} & 0_{3 \times 3} \\ 0_{3 \times 3} & \eta_{1} \end{bmatrix}\ \ $J\left(\eta \right)=\left[\begin{array}{cc}\hfill {\eta }_1\hfill & \hfill 0_{3\times 3}\hfill \\ \hfill 0_{3\times 3}\hfill & \hfill {\eta }_1\hfill \end{array}\right]$ [TeX:] (2)$\left(2\right)$

The AUV kinematic model with environmental disturbance is defined as follows [23]:

[TeX:] M\dot{v} + Cv + Dv + g(\eta) = \tau + \tau_{en}$M\dot{v}+Cv+Dv+g\left(\eta \right)=\tau +{\tau }_{en}$ (3)

where [TeX:] M$M$ denotes the inertia matrix with the Coriolis matrix [TeX:] C$C$. The matrix [TeX:] D$D$ denotes the hydrodynamic damping terms. Additionally, the vector [TeX:] g(\eta)$g\left(\eta \right)$ indicates the gravitational and propulsive force.

The matrix [TeX:] \tau = \lbrack\tau_{X},\tau_{Y},\tau_{Z},\tau_{K},\tau_{M},\tau_{N}\rbrack$\tau =[{\tau }_X,{\tau }_Y,{\tau }_Z,{\tau }_K,{\tau }_M,{\tau }_N]$ reflects the input forces and moments that account for the various influences acting on the AUV, including contributions from the rudder, fins, and propeller. The environmental disturbance represented by [TeX:] \tau_{en}${\tau }_{en}$ which affects AUV motion. In deep-sea operational conditions, the primary influencing factor is the current, which is modelled as [24]

[TeX:] \tau_{en} = \left\lbrack u_{c}^{E},v_{c}^{E},w_{c}^{E} \right\rbrack^{T}${\tau }_{en}={[u_c^E,v_c^E,w_c^E]}^T$ (4)

[TeX:] u_{c}^{E}\ = \ V_{c}\cos{\left( \alpha_{c} \right)\cos\left( \beta_{c} \right)}$u_c^E=V_{c}cos\left({\alpha }_c\right)cos\left({\beta }_c\right)$

[TeX:] v_{c}^{E}\ = \ V_{c}\sin\left( \beta_{c} \right)\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $v_c^E=V_{c}sin\left({\beta }_c\right)$ (5)

[TeX:] w_{c}^{E}\ = \ V_{c}\sin{\left( \alpha_{c} \right)\cos\left( \beta_{c} \right)}$w_c^E=V_{c}sin\left({\alpha }_c\right)cos\left({\beta }_c\right)$

for [TeX:] V_{c}$V_c$ is the flow velocity, [TeX:] \alpha_{\mathbf{c}}${\alpha }_{𝐜}$ represents the deflection angle, and [TeX:] \beta_{c}${\beta }_c$ is the slip angle describing the direction of the flow velocity vector.

Remark 1: In the subsea environment influenced by currents and uneven terrain, the AUV's path is essential to prevent collisions with obstacles.

2.2. Obstacle model / Model prepreka

Figure 2 Desired AUV path for avoiding obstacles

Slika 2. Željena putanja AUV-a za izbjegavanje prepreka

In the scenario of an AUV navigating in the presence of obstacles, a critical task is to determine the optimal path that avoids any collisions. The set of waypoints is denoted as [TeX:] W = \left( w_{1},{\ldots,w}_{i},\ldots,w_{I} \right)$W=(w_1,{\dots ,w}_i,\dots ,w_I)$, where each point [TeX:] w_{i} \in R^{3}$w_i\in R^3$ represents the positions along the path from the starting point to the endpoint (illustrated in Fig. 2). The depth is constrained between the surface and the maximum allowable depth, [TeX:] z_{\max}$z_{max}$, with the condition that [TeX:] (x,y) > 0$(x,y)>0$. Consequently, the obstacle space [TeX:] O_{obs}$O_{obs}$ is given by [25]

[TeX:] O_{obs} \triangleq \left\{ \mathbf{p} \in O_{space},\nu(p\mathcal{) \cap O \neq \varnothing} \right\}$O_{obs}\triangleq \{𝐩\in O_{space},\nu (p\mathcal{)}\mathcal{\cap }𝒪\mathcal{\ne }\mathcal{⌀}\}$ (6)

The configuration space [TeX:] O_{space}$O_{space}$ can be expressed as [26]

[TeX:] O_{space} = \left\{ \mathbf{p} \in \mathbb{R}^{3}|0 \leq z \leq z_{\max}(x,y) \right\}$O_{space}=\{𝐩\in {ℝ}^3|0\le z\le z_{max}(x,y)\}$ (7)

Let [TeX:] \nu(p) \in R^{3}$\nu \left(p\right)\in R^3$ represent the space occupied by the AUV, whereas [TeX:] \mathcal{O \in}R^{3}$𝒪\mathcal{\in }{R}^3$ denotes the obstacle space. The free space, denoted as [TeX:] O_{free}$O_{free}$, is defined as the complement of [TeX:] O_{obs}:O_{free} \triangleq O_{space}\backslash O_{obs}$O_{obs}:O_{free}\triangleq O_{space}\setminus O_{obs}$ [27]. Thus, [TeX:] O_{free}$O_{free}$ represents the area within [TeX:] O_{space}$O_{space}$ that is not occupied by obstacles, allowing the AUV to move safely. The goal is to continuously update a function [TeX:] h:\lbrack 0,1\rbrack \times \left. ⟦0,k - 1 \right.⟧ \rightarrow X$h:[0,1]\times ⟦0,k-1⟧\to X$, where [TeX:] X$X$ is a connected space, such that for [TeX:] \forall s \in \lbrack 0,1\rbrack$\forall s\in [0,1]$, and [TeX:] \forall i \in \left. ⟦0,k - 1 \right.⟧$\forall i\in ⟦0,k-1⟧$, the conditions are satisfied as

[TeX:] h(s,i) = o_{i}(s)\ \ \ \ \ $h(s,i)=o_i\left(s\right)$

[TeX:] o_{i}:\lbrack 0,1\rbrack \rightarrow O_{free}\ $o_i:[0,1]\to O_{free}$

[TeX:] o_{i}(0) = \left\{ \begin{array}{r} p,\ i = 0 \\ \omega_{i},\ else \end{array} \right.\ $o_i\left(0\right)=\{\begin{array}{c}\hfill p,i=0\\ \hfill {\omega }_i,else\end{array}$ (8)

[TeX:] o_{i}(1) = \omega_{i + 1}\ \ \ \ \ \ \ $o_i\left(1\right)={\omega }_{i+1}$

Remark 2: The AUV motion can pass through multiple waypoints [TeX:] w_{i}$w_i$ while adhering to the [TeX:] O_{free}$O_{free}$ space constraint along various feasible paths in the 3D space. As a result, it is essential to determine the optimal path for the AUV's movement to ensure it safely avoids collisions with obstacles.

3.1 Optimizing AUV path based on the Quantum-Inspired Optimization Algorithm / Optimizacija putanje AUV-a temeljena na kvantno-inspiriranom optimizacijskom algoritmu

The proposed QA solution aims to optimize the AUV's path in a 3D environment with obstacles. The development process is divided into two phases: establishing a simulation environment and performing path planning based on a quantum model, followed by verification using a HIL model. The overall process, illustrated in Fig. 3, demonstrates the linkage between simulation, QA algorithm, and system performance evaluation. In this study, the QA algorithm is defined as a quantum-inspired optimization approach. The methodological basis of the proposed algorithm is developed by adapting and integrating concepts from quantum-inspired optimization (such as Q-bit representation, the Quadratic Unconstrained Binary Optimization (QUBO) model, Hamiltonian mapping, cost Hamiltonian, mixing Hamiltonian, and bit-string measurement) to solve the deviation problem of the AUV path in an obstacle environment. The optimization process is performed in sequential steps, including discretizing the operating space, encoding waypoints with binary variables, constructing the QUBO function, mapping the cost function into the Hamiltonian representation, and decoding the obtained bit strings into feasible paths for the AUV.

Figure 3 Overview of AUV optimal path using QA

Slika 3. Pregled optimalne putanje AUV-a korištenjem kvantnim algoritmom (QA)

Phase 1: Developing a 3D simulation environment for an AUV, where obstacles are strategically arranged within a defined space to compute the safe movement areas. The QA algorithm is employed to build the search space and determine an optimal waypoint list based on the cost function (8) and the QUBO function [28]. Quantum states are encoded by using Q-bits (13) and evolve according to the Hamiltonian, which incorporates two Hamiltonians, [TeX:] H_{C}$H_C$ and [TeX:] H_{B}$H_B$. This approach aims to identify the optimal path, guaranteeing collision avoidance while defining the shortest feasible path.

Phase 2: Building the HIL model to verify the effectiveness of the QA algorithm. The HIL model's operating data and cost weights are continuously updated. In addition, the QA implements the quantum superposition [TeX:] \psi(\gamma,\beta)$\psi (\gamma ,\beta )$ (21), which is applied in bit-string decoding to compute the cost function [TeX:] C(X)$C\left(X\right)$ (15). The iteration process stops when the convergence condition (12) is achieved, thereby obtaining the optimal bit-string corresponding to the best waypoint for the AUV path. Furthermore, this study compares the proposed QA solution with other pathfinding algorithms (such as Dijkstra's algorithm and Fast Marching) to confirm the effectiveness of the proposed solution in obstacle avoidance.

In the simulation phase, the 3D operating space for the AUV is discretized into a set of candidate waypoints, and the waypoint selection process is then encoded using binary variables. Based on this representation, a path planning is formulated as a QUBO model, in which the objective function combines path length, waypoint selection constraints, start and target conditions, and obstacle-avoidance penalty terms. The QUBO model is mapped into the Hamiltonian representation, where low-energy states correspond to paths with lower cost values. In the HIL phase, the bit strings obtained after measurement are decoded into waypoint sequences, and the path with the lowest cost while satisfying the safety constraints is selected as the optimal path for the AUV. To determine the optimal path for an AUV, it is essential to minimize the total path length while adhering to safety constraints that prevent collisions with obstacles. Let's consider the AUV navigating through a series of discrete points in 3D space. The distance between two consecutive points, [TeX:] P_{i}$P_i$ and [TeX:] P_{j}$P_j$, is computed as [29]

[TeX:] d_{(i,j)} = \sqrt{\left( x_{i} - x_{j} \right)^{2} + \left( y_{i} - y_{j} \right)^{2} + \left( z_{i} - z_{j} \right)^{2}}$d_{(i,j)}=\sqrt{{(x_i-x_j)}^2+{(y_i-y_j)}^2+{(z_i-z_j)}^2}$ (9)

Let the set of waypoints in space be denoted by [TeX:] P = \lbrack P_{1},\ \ \ldots,\ P_{n}\rbrack$P=[P_1,\dots ,P_n]$. The order in which the AUV moves through these points is represented by a permutation [TeX:] p = \lbrack p_{1},\ldots,\ p_{n}\rbrack$p=[p_1,\dots ,p_n]$. The objective of finding the permutation [TeX:] p$p$ is to minimize [TeX:] L$L$, while adhering to the obstacle avoidance conditions in the 3D environment, while transitioning from the starting point to the endpoint. Thus, the total path length is defined as

[TeX:] L = \sum_{i = 1}^{n - 1}d_{p_{i},\ p_{i + 1}}$L={\sum }_{i=1}^{n-1}{d}_{p_i,p_{i+1}}$ (10)

The QA identifies the optimal solution through population evolution, where each element is represented as a quantum state. This representation enables parallel simulation of possible outcomes, assisting in computation of the best path for the AUV. The population consists of [TeX:] N$N$ elements, with each element corresponding to a different feasible path within a [TeX:] d$d$-dimensional multi-solution space. The position of the [TeX:] i^{th}$i^{th}$ element at the current iteration is given by [30]

[TeX:] X_{i} = \lbrack x_{i1},\ x_{i2},\ \ldots,\ x_{id}\rbrack$X_i=[x_{i1},x_{i2},\dots ,x_{id}]$ (11)

During the process of finding the optimal path, each element stores its best value, referred to as [TeX:] p_{i}^{best}$p_i^{best}$. Thus, the set of optimized elements derives the global optimal value, [TeX:] g^{best}$g^{best}$ [31].

[TeX:] g^{best} = \frac{1}{N}\sum_{i = 1}^{N}p_{i}^{best}$g^{best}=\frac{1}{N}{\sum }_{i=1}^N{p}_i^{best}$ (12)

The global optimum value shows how the group is moving toward the best path for the AUV. To update the position of particle [TeX:] i$i$ in the next step, we look at the distance between the local best solution and the global solution, as described by

[TeX:] X_{i}^{t + 1} = p_{i}^{best} + \alpha rand(0,1)(g^{best} - X_{i}^{t})$X_i^{t+1}=p_i^{best}+\alpha rand(0,1)(g^{best}-X_i^t)$ (13)

where 𝛼 represents the convergence speed adjustment factor, and [TeX:] rand(0,1)$rand(0,1)$ is a random variable that is uniformly distributed in the interval (0,1). The execution of the QA will stop when either the maximum number of iterations, [TeX:] iter_{\max}$ite{r}_{max}$, is reached, or the change in the cost function between two consecutive steps is smaller than the threshold [TeX:] \varepsilon$\epsilon$.

[TeX:] \left| L^{t + 1} - L^{t} \right| < \varepsilon$|L^{t+1}-L^t|<\epsilon$ (14)

This condition ensures that the convergence process is stable and stops at the solution with the smallest difference. In QAs, the solutions to the path optimization problem are encoded using Q-bit, allowing each decision variable to exist in a superposition of |0⟩ and |1⟩. Here, [TeX:] \alpha$\alpha$ and [TeX:] \beta$\beta$ represent complex probability amplitudes, and a Q-bit can be expressed as follows [32]:

[TeX:] |\psi\rangle\ = \alpha|0\rangle\ + \ \beta|1\rangle$|\psi ⟩=\alpha |0⟩+\beta |1⟩$ (15)

[TeX:] |\alpha|^{2} + |\beta|^{2} = 1${\left|\alpha \right|}^2+{\left|\beta \right|}^2=1$

The solution values are shown in QUBO, which uses binary variables. This approach aims to improve the variety of the search by creating multiple binary solutions during the measurement process. It covers a wider range of options than traditional coding methods. The binary variable [TeX:] x_{i,k}$x_{i,k}$ is set to 1 when waypoint [TeX:] i$i$ is chosen at position[TeX:] \ k$k$, and 0 if it is not. The path of the AUV is represented by the matrix [TeX:] X$X$ as

[TeX:] X = \left\lbrack x_{i,k} \right\rbrack_{n \times m}$X={\left[x_{i,k}\right]}_{n\times m}$ (16)

The total cost function is defined by [33]

[TeX:] C(X) = w_{1}f_{1}(X) + w_{2}f_{2}(X) + w_{3}f_{3}(X) + w_{4}f_{4}(X)$C\left(X\right)=w_1{f}_1\left(X\right)+w_2{f}_2\left(X\right)+w_3{f}_3\left(X\right)+w_4{f}_4\left(X\right)$ (17)

therein [TeX:] f_{1}$f_1$ and [TeX:] f_{2}$f_2$ represent one-hot constraints applied to rows and columns, respectively. [TeX:] f_{3}$f_3$ accounts for the cost associated with relocating between waypoints, while [TeX:] f_{4}$f_4$ sets the starting and ending conditions. The weights [TeX:] w_{1},\ w_{2},\ w_{3}$w_1,w_2,w_3$ and [TeX:] w_{4}$w_4$ are selected to balance the cost function with the constraints for determining the optimal path.

The objective function is designed to combine both path optimality and path feasibility. The one-hot constraints ensure a valid structure of the waypoint sequence, the relocation cost guides the algorithm toward paths with shorter total distances, and the start and end conditions ensure that the generated path is consistent with the AUV navigation task. The corresponding weights are used to balance the path-length minimization objective with satisfying the constraint requirements. From this objective function, the QUBO model is mapped into the Hamiltonian representation to support the search for the lowest-energy state. In addition, [TeX:] Z_{i}$Z_i$ is the Pauli-Z operator acting on the [TeX:] i^{th}$i^{th}$ Q-bit, while [TeX:] h_{i}$h_i$ and [TeX:] J_{ij}$J_{ij}$ are linear and quadratic coefficients. The lowest energy state of [TeX:] H$H$ corresponds to the optimal solution of the problem. Thus, the cost function in QUBO [34] is mapped to the Hamiltonian [35]-[36] to represent it in quantum form as

[TeX:] H = \sum_{i}^{}{h_{i}Z_{i}} + \sum_{i < j\ }^{}{J_{ij}Z_{i}Z_{j}}$H={\sum }_i^{}{h}_i{Z}_i+{\sum }_{i<j}^{}{J}_{ij}{Z}_i{Z}_j$ (18)

Binary variables are mapped as follows:

[TeX:] x_{i} = 1 - Z_{i}/\ 2$x_i=1-Z_i/2$ (19)

The elements within a QUBO problem are transformed into combinations of [TeX:] Z_{i}$Z_i$ and [TeX:] Z_{i}Z_{j}$Z_i{Z}_j$. This transformation incorporates one-hot constraints and the relocation cost (17), which are represented as connections between qubits in quantum space. The cost Hamiltonian [TeX:] H_{C}$H_C$ guides the quantum system towards low-energy states, indicating scenarios in which the optimal path has been identified. Additionally, a mixing Hamiltonian [TeX:] H_{B}$H_B$ is introduced to facilitate movement between qubit states, thereby allowing the exploration of alternative paths. The dual Hamiltonian approach enables the quantum annealing algorithm to effectively balance the exploitation of the Q-bit structure with the expansion of the search space [37], ultimately enhancing its capability to identify the global optimal path.

[TeX:] H_{B} = \sum_{i}^{}X_{i}$H_B={\sum }_i^{}{X}_i$ (20)

where [TeX:] X_{i}$X_i$ represents a Pauli-X operator, enabling bitwise inversions and facilitating the exploration of the solution space. Thus, the two values [TeX:] H_{C}$H_C$ and [TeX:] H_{B}$H_B$ are applied sequentially during the quantum evolution, resulting in an overall Q-bit state described by

[TeX:] \left| \left. \ \psi(\gamma,\beta) \right\rangle = U_{B}(\beta)U_{C}(\gamma) \right.\ \left| \left. \ s \right\rangle \right.\ $|\psi (\gamma ,\beta )⟩=U_B\left(\beta \right)U_C\left(\gamma \right)|s⟩$ (21)

for [TeX:] U_{C}(\gamma) = e^{- i\gamma H_{C}}$U_C\left(\gamma \right)=e^{-i\gamma H_C}$, [TeX:] U_{B}(\beta) = e^{- i\beta H_{B}}$U_B\left(\beta \right)=e^{-i\beta H_B}$ and [TeX:] \left| \left. \ s \right\rangle \right.\ $|s⟩$ express the initial superposition state. The parameters [TeX:] (\gamma,\beta)$(\gamma ,\beta )$ are adjusted to minimize the expected value of the system energy as [38]

[TeX:] \min_{\gamma,\beta}\left\langle \psi(\gamma,\beta) \middle| H \middle| \psi(\gamma,\beta) \right\rangle${min}_{\gamma ,\beta }⟨\psi (\gamma ,\beta )\left|H\right|\psi (\gamma ,\beta )⟩$ (22)

After the optimization process, the resulting quantum states are mapped to bit strings that correspond to feasible path. The state with the lowest energy is then selected as the optimal path for the AUV. The QA allows us to represent the AUV path planning problem as a QUBO model and to solve the optimization problem using quantum mechanisms. The structure comprises two Hamiltonians, [TeX:] H_{C}$H_C$ and [TeX:] H_{B}$H_B$, which help satisfy the path constraint while minimizing the total path length. The proposed method is implemented in a HIL environment to verify its practical performance and evaluate the efficiency of the algorithm, which will be detailed in the next subsection.

3.2. Building the AUV virtual reality model / Izgradnja AUV modela u virtualnoj stvarnosti

The AUV experimental model is implemented using a HIL application to evaluate the proposed solution within a virtual reality environment. Specifically, the control algorithm is developed in the MATLAB computing environment to process sensor data and compute control values that interact with the HIL model. To enhance visualization, this study employs the Unreal Engine software to create a 3D sea environment for the AUV's real-time movement. The ARM Cortex M7 processor is used as a classical embedded processor to execute the C/C++ code of the quantum-inspired optimization algorithm under real-time conditions. This microprocessor kit was selected because it is suitable for embedded control applications, supports floating-point computation, and enables deterministic real-time execution. The ARM Cortex M7 kit is compatible with code generation in the MATLAB computing environment. Thus, the role of the processing kit is to verify the feasibility of implementing the algorithm modeled after quantum optimization mechanisms in the HIL model. The structure of the HIL model for the AUV test is illustrated in Fig. 4.

Figure 4 The HIL structure in virtual reality model

Slika 4. Struktura HIL sustava u modelu virtualne stvarnosti

The hardware implementation is achieved by converting the QA into C/C⁺⁺ using Simulink Coder and Embedded Coder, and then loading the proposed algorithm onto the STM32 microcontroller to perform system control. The HIL operation process (expressed in Algorithm 1) is executed in the following steps:

4. RESULTS AND DISCUSSIONS / Rezultati i rasprava

4.1. Configuration parameters / Konfiguracijski parametri

The proposed solution is implemented using MATLAB R2024a on a computer equipped with an Intel Core i7-4800MQ processor and 16GB of RAM. The simulation space is designed with dimensions of 500 m × 200 m × 120 m. Obstacle configurations within the space are represented as polyspherical shapes to provide a clear visualization of the reef conditions on the seabed. The parameters utilized during the testing phase are summarized in Table 2.

Table 2 Parameters applied for QA training

Tablica 2. Parametri primijenjeni za treniranje QA (kvantnog algoritma)

During the simulation and testing of the QA algorithm for the AUV, technical parameters were established to ensure the model's accuracy and feasibility. The AUV's initial position was defined at the coordinates [0 m, 0 m, 0 m], with an initial orientation angle of [0 deg, 0 deg, 0 deg]. The moving target for the AUV was positioned at [270 m, 180 m, 0 m], maintaining a speed of 2 m/s. The AUV's specifications include a body length of 3 m and a radius of 2 m, thereby reflecting its navigation capabilities within a 3D environment. The QA algorithm is configured with a particle count ranging from 60 to 120, and the landmark parameter [TeX:] W$W$ is set between 8 and 65. The maximum iteration number, itermax, is established within the range of 600 to 800. To ensure high resolution in state updates and sensor data processing, the simulation time step is fixed at 0.1 s. The selection of these parameters not only aids in accurately simulating reality but also enhances the evaluation of performance in complex navigation environments, which include both moving and static objects.

4.2. Simulation cases / Simulacijski slučajevi

In this study, the path-optimization algorithms are implemented on the MATLAB environment. To assess the effectiveness of the proposed solution, the results were compared with FMA and DA, which use propagation models to identify optimal paths under complex conditions. All algorithms are initialized under identical conditions in a 3D environment to assess the AUV's navigation performance in obstacle-laden settings. In the simulation cases, the randomly shaped obstacles are initialized to reflect natural seabed conditions such as coral reefs. In the first simulation case, the AUV begins at the origin O [0 m, 0 m, 0 m], then moves towards a destination point A [250 m, 100 m, 100 m]. The arrangement of obstacles forces the algorithms to optimize the navigation to avoid collisions during path planning.

The simulation results for Case 1 are shown in Fig. 5a and Table 3. The QA algorithm provides the shortest path of 285.4 m, thus proving it is effective at optimizing routes. The FMA comes next, with a path of 298.7 m, which is still acceptable but longer than QA. The DA’s results in the longest path at 342.1 m, highlighting that it is not optimal for this grid layout. In terms of speed, QA finishes the move in 241 s, which is much faster than FMA at 310 s and DA at 281 s. In the number of iterations for finding a path, the FMA only takes 10 due to its smart search feature. However, the QA requires 150 iterations to reach the best solution, and the Dijkstra takes up to 500 iterations because of its random approach. QA keeps an average safe distance of 12.3 m, ensuring high safety. FMA achieves 8.7 m, and DA only gets 5.1 m, which could bring it too close to obstacles. These results show that QA is the best choice for path length, moving time, and safety, even though it has a higher cost function value of 15, thereby satisfying the conditions stated in Remark 1. The FMA works well in static environments with known conditions, while DA is better for navigating AUVs in larger areas.

In the second case, the author sets up a 3D environment with terrain containing two obstacles. The AUV's planned path from A [0 m, 0 m, 0 m] to B [600 m, 0 m, 0 m] passes through two spherical obstacles simulating natural terrain, such as reefs or coral reefs, creating obstacles in path planning. During the movement, the AUV follows the path planned by the comparison solutions to avoid collisions in a limited space.

The comparison results are summarized in Table 4, which shows that the QA algorithm achieves the best performance among the compared solutions. In terms of path length, the result with QA is 602 m, the shortest among the three algorithms, while FMA and DA are 614 m and 625 m, respectively. The moving times clearly indicate the differences between the solutions: the QA completed the process in 268 s, which is faster than the FMA of 74 s and the DA of 37 s. In terms of iterations, the FMA only required 12 iterations thanks to its method of solving the Eikonal equation. Furthermore, the QA algorithm needs 180 iterations to converge, while DA algorithm requires 620 iterations because it involves traversing the entire graph. Despite needing a higher number of iterations, the QA still demonstrated strong performance, thus meeting the requirements specified in Remark 2. Regarding safety distance from obstacles, QA achieved an average of 10.9 m, which is significantly higher than FMA’s 7.4 m and DA’s 4.3 m. The visual results (expressed in Fig. 5b) indicate that QA is highly reliable in environments with collision risks, making it suitable for applications such as autonomous vehicles. The proposed QA solution continues to be tested in the HIL model to shorten the gap between simulation and implementation on actual models.

4.3. Experimental scenarios / Eksperimentalni scenariji

To demonstrate the effectiveness of the QA algorithm, the authors built a virtual reality environment using the HIL. In this approach, two experimental scenarios not only simulate actual operating conditions but also integrate realistic disturbances. The HIL model aims to verify the adaptability of the QA algorithm in environments similar to the actual operations.

In scenario 1, the AUV operates in an underwater environment with the shortest distance from the start point to the end of the path being 200 m. At the planning stage, an obstacle needs to be considered while evaluating the QA algorithm's ability to determine an optimal path. The results of Scenario 1 are illustrated in Fig. 6, where the red line represents the optimal path identified by the QA.

The comparison results are presented in Table 5, indicating that the QA met the optimal path for a length of 214 m, which is 13 m shorter than the DA, and ensures a safe distance of 5.49 m. Although the number of QA iterations is 12, equal to FMA and DA, it still indicates a good balance between accuracy and processing speed. Meanwhile, FMA has a longer path time of 113.5 s and a higher safe distance of 6 m, reflecting its effective obstacle avoidance ability, but not optimal in terms of time. The DA provides a longer path length of 225 m, a moving time of 112.9 s, and a safe distance of 6 m, showing high accuracy but not superior in terms of response. In summary, the experimental results show that the QA algorithm has an advantage in optimizing the path to ensure AUV safety for moving through an obstacle.

In experimental scenario 2, the AUV is planned a path from point A to point B in a HIL environment with two randomly placed obstacles. The goal of this scenario is to evaluate the QA algorithm's ability to plan an optimal path in a more complex environment, where the AUV simultaneously maintains a safe path and minimizes the path length. The results of the second scenario are presented in Fig. 7, where the red line shows the optimal path searched by the QA.

The results presented in Table 6 express that the QA performs better than the comparison algorithms, with the shortest path length of 603 m, and the lowest moving time of 301 s, while maintaining an average safety distance of 5 m between the AUV and obstacles. Although the number of algorithm iterations of the QA is 13, which is equal to the FMA, it is still significantly more efficient than the DA with 12 iterations, resulting in a path longer than 645 m and a safety distance lower than 5.5 m. The FMA has a low number of iterations similar to the QA, but a longer moving time of 322 s and a safety distance higher than 6.50 m, showing good obstacle avoidance but not optimal in terms of time and path length. The Fig. 7 illustrates the AUV's path from point A to B, navigating through two obstacles, expressing the flexibility of the proposed solution. Based on the testing results of the two-obstacle scenario, the QA algorithm has the ability to balance well between safety and path optimization, making it suitable for practical applications in complex underwater environments.

In this study, the HIL plays a crucial role in evaluating the QA performance in the path optimization. The HIL application allows integration of the actual AUV control hardware with the virtual model, thereby demonstrating its effectiveness for close-to-actual operating conditions. Through two experimental scenarios with different numbers of obstacles, the QA verifies its ability to navigate effectively, guaranteeing a safe distance and optimal moving time. In particular, the QA iteration number, although higher than FMA, is significantly lower than the DA, reflecting the balance between accuracy and processing speed. The implementation of HIL not only helps validate the algorithm in real-time physical conditions but also evaluates the interaction between the virtual reality model and the control hardware, thereby improving the reliability and applicability of QA in AUV systems operating in actual environments.