A bio-inspired algorithm in image-based path planning and localization using visual features and maps

1.1. Related work

Navigation in an unknown and unstructured environment is extremely challenging and is involved in multiple, well-known, and well-studied disciplines^{[3, 23–26]}. Within the research community, there is a body of knowledge relating to neural network (NN) architectures that apply machine learning concepts to extract features and image descriptors from scenes, thereby facilitating various tasks related to autonomous vehicles^{[27, 28]}. This is typically accomplished through the implementation of a pooling layer inspired by the Vector of Locally Aggregated Descriptors (VLAD), which pools extracted descriptors into a fixed image representation, allowing its NN parameters to be learned by back-propagation NN. VLAD descriptors accomplish visual location recognition by directly using the intermediate layer outputs of pre-trained CNNs^[29].

Visual place recognition methods can be based on directed acyclic graph matching, where feature maps extracted from deep CNNs are used to form probability distributions on image representation^[30]. Another approach is based on extreme K-means and effective extreme learning machines (EELMs), where image decomposition with curvelet transformation is used to reduce dimensionality and generates a set of distinctive features^[31] for use in future processing phases. As an example, Muthusamy et al.^[32] applied a Gaussian mixture model (GMM) in various pattern recognition applications with EELM with excellent results.

The developments in feature extraction through NNs and CNNs naturally lend themselves to the performance of tasks associated with autonomous vehicles, such as SLAM^[33]. One particular type of SLAM, Learning SLAM, can obtain camera pose and create a 3D map. However, it needs to have the prior dataset to train the network, and its performance often depends on that dataset. As a result, learning SLAM has poor generalization and is less versatile than some of its other implementations, such as geometric SLAM. This is generally owing to its 3D map being less accurate than one created via geometric SLAM. Visual SLAM, on the other hand, is a more dynamic system that typically consists of three components: (1) a visual odometry algorithm that provides an initial state estimate; (2) a place recognition system that is able to relate the currently observed scene to previously observed scenes; and (3) an optimization back-end which consistently integrates the place matches from the place recognition system with the full stream of state estimates^[34]. While visual SLAM has proven to be highly valuable in ideal environments, there are certain disadvantages to this methodology that researchers are actively addressing in current research. The fundamental issue lies in the challenges posed by environmental changes, which induce errors and make feature identification difficult. These challenges can occur due to changes in time, environment, camera posture, and other factors^[35].

Various forms of deep NNs (DNNs) and artificial intelligence (AI) techniques are utilized to make a system more robust by autonomously tuning parameters, thereby enhancing overall performance. Learned features, such as those derived from massive amounts of deep learning (DL) meta-sensor data, are aggregated into coherent large-scale maps and then classified features extracted from those DNNs, such as "lake", "road", "field", "obstacles", or "traversable terrain", assigned with corresponding cost values in a Cartesian space^[36]. Graphs are then constructed based on these maps to enable path planning. Training data can be constructed either directly from image-space features or by projecting pixel data into Cartesian space, depending on the methods employed. To create an optimal trajectory, DL-based methods are used to construct a path that takes into account the geometry of the explored areas, taking into account the starting and ending positions. Outputs of image processing techniques, such as edge detection and region segmentation, are used to determine the explorable regions of the map^[17]. Path planning inputs are derived from standard commercially available NNs, which are used to generate topological maps. Image-sensor input data are represented as a bipartite cost-graph, with disjoint nodes representing image-feature distances and their corresponding geographic distances^[37].

In a parallel research area, biologically inspired algorithms have become popular for performing optimizations and solving problems involving $$ n $$-dimensional search spaces. Evolutionary Algorithms (EAs) are widely used as global searching methods for optimization, and hybrids of EAs and analytical methods are providing a promising atmosphere for NN and CNN training applications^[38]. Ongoing research in this domain provides fuel for the integration of subsets of EA-like swarm methodologies for parameter estimation and optimization. The swarm intelligence methodology aims to optimize the conditioning of EELM, and some researchers have already proposed an effective particle swarm optimization (PSO) algorithm known as the Multitask Beetle Antennae Swarm (MBAS) Algorithm. This algorithm was inspired by the structures of the artificial bee colony (ABS) algorithm and the Beetle Antennae Search (BAS) algorithm^[39]. In fact, some research efforts even claim that the approach is so straightforward and effective that it may be possible to completely replace traditional NN training paradigms, including back-propagation^[40].

EELM is not the only area benefiting from swarm methodologies such as PSO. The controller of autonomous vehicles has seen significant improvements as well, particularly in the case of four-wheel steer four-wheel drive (4WS4WD) vehicles. The improved PSO-based controller takes into account all the slip forces acting on the vehicle, leading to a notable enhancement in its robustness^[41–43]. Population-based algorithms have been used in a more generalized way to solve optimization problems that are typically challenging for traditional deterministic algorithms, such as the issue of the local optima. One novel population based on an optimization strategy involves leveraging the different behaviors of mosquitoes during the foraging process^[44]. Another biomimetic swarm intelligence optimization algorithm, pigeon-inspired optimization (PIO), has also been introduced as a novel approach in this field. PIO simulates the homing behavior of pigeons using magnetic fields and landmarks. PIO has also been further improved to enhance its effectiveness in solving many-objective optimization problems (MaOPs) ^[45]. The list of EA research is extensive. Some of the optimization algorithms currently published include bacterial colony chemotaxis (BCC) optimization^[46], the "swarm of bees" or BSO algorithm^[47], and the discrete artificial bee colony (DABC) algorithm^[48].

One important bio-inspired optimization algorithm is the Bat Algorithm (BA). The BA is the focus of our current research and has been the subject of many research papers. Various variations to the BA have been proposed, demonstrating its versatility and effectiveness in solving a wide range of optimization problems across multiple fields. This study showed that the proposed BA algorithm clearly outperformed competing methods, such as the Pareto concept, in terms of performance and solution quality. Furthermore, due to the similarities between the BA and the PSO, BA has also been applied to solve the Wireless Sensor Network (WSN) coverage problem. In the context of wireless sensor node development research, the sensor node itself is regarded as a bat, and its position is regarded as the position of the bat. By implementing the BA, significant improvements in the accuracy of node positioning in practical and complicated environments have been demonstrated^[49]. Additionally, an improved version of the BA combined with Differential Evolution (DE), known as IBA, has been proposed to optimize the three-dimensional path planning problem for Uninhabited Combat Air Vehicles (UCAV) ^[50]. This application of BA in UCAV path planning is notable because it was a novel approach at the time. The knowledge of this fact serves as the primary motivator for our current research. If BA can be used to plan and optimize 3D paths in combat aircraft, it is reasonable to believe that it could yield similar benefits for autonomous ground vehicles^[51].

In the related work reviewed, it is found that no BA (or any other biologically inspired optimization) has been applied to the SLAM path planning problem. Since SLAM and seqSLAM utilize visual features and CNNs to produce a global path through a sequence of images, the implementation of a BA would be a novel and useful application of the optimization capabilities for optimizing the shortest path. This would involve computing a local path once the global trajectory has already been computed.

1.2. Proposed framework and original contributions

Studies on image-based navigation have become increasingly popular due to the increasing interest in their numerous applications in the field of autonomous vehicles^{[52, 53]}. In particular, several frameworks have been proposed and prototyped for image-based navigation. For example, Thoma et al.^[37] developed a framework for image-based mapping, localization, and navigation of autonomous vehicles, and the algorithms for map constructions and self-localizations were discussed in detail. However, the algorithms required for path planning play an irreplaceable role in making an integrated imaged-based navigation system successful. Although limited work has been done on integrating path planning algorithms into learning systems, it has been noted that a reliable, biologically inspired, or nature-inspired optimization algorithm is missing from the image-feature-based navigation path planning models^[54]. Therefore, this paper aims to develop a more robust path planner and evaluate the improved navigation results in comparison with Thoma et al.^[37]. The BA is proposed and integrated as the state-of-the-art path planner into the program flow, and it is verified by measuring the performance of the outcomes based on the same datasets in the reference^[55]. The flowchart of the proposed framework is presented in Figure 1.

Figure 1. Proposed framework for Bat Algorithm in image-based path planning and localization using visual features and maps.

The main contributions of this paper are summarized as follows:

● A biologically inspired image-based path planning and localization framework is proposed for robust, reliable, and effective image-based navigation.

● An image-based navigation is developed to use visual features and mapping that satisfy the requirements for image-based navigation and self-localization.

● The BA for image-based path planning is proposed to navigate the autonomous vehicle through the landmark identification on image-based reference query sequences.

The rest of this article is organized as follows. In Section 2, the image feature-based localization and map creation for image-based navigation are introduced. Section 3 presents the proposed BA for image-based navigation. In Section 4, the results of test cases, comparison studies, and simulations are presented, and performance characterization is provided for various maps, challenge datasets, and environments. Several important properties of the presented framework are summarized in Section 5.

2.1. Image feature-based localization

Recently, there have been advances in camera technologies that allow them to be used in robotic applications as navigational sensors^[30]. Cameras are used to provide the basic sensor input for localization, using robot pose in each world environment^[37]. Cameras deliver high quality image streams that enable feature identification, which may be employed to determine the location of the robot within the defined world environments. Images, for example, can still contain embedded information in the form of features such as points, lines, conics, spheres, and angles, which might be valuable for image-based navigation.

When images are coupled with the CNNs and appropriate filters are used to extract these features, localization can be possible. Image-based localization is a large topic that includes two main types of "worlds": those environments that are known a priori and others that are unknown. The method using a known environment consists of online and real-time mapping, and the latter is commonly known as SLAM^[34]. SLAM methods can incorporate geometric, learned, topographical, and marker identification techniques^[30]. The method considered in this study involves using a known environment of learned features, which will be integrated with the BA.

The method is a form of learned mapping that examine features that have been identified using two types of sources^[30]. The first source is based on the VGG16 CNN coupled with off-the-shelf NetVLAD weights^[29], while the second source is simply the fully connected output from the last VGG16 FC3 layer^[37]. These features serve as the basis for lookup queries against the landmarks that have been established by a reference dataset of known location and geometry in this paper.

The geometric distances in the test data are calculated algorithmically and defined in the paper. The results of the query are then used to establish anchors and sensitivity values, which are used to identify the best waypoints between the identified landmarks. This network of points is best represented by a graph, representing the features where the Network Flow algorithm is then used to find the path with the lowest cost from source to destination.

The graph is represented by $$ \mathcal{G}=\{\mathcal{V}, \mathcal{E}\} $$, where utilizing cost values $$ c_{ij} $$ and capacity values $$ \omega_{ij} $$ to represent the edge $$ e_{ij} \in \mathcal{E} $$ between images $$ \mathcal{I}_i $$ and $$ \mathcal{I}_j $$.

where $$ \eta_\mathcal{X} $$ and $$ \eta_\mathcal{F} $$ are weights of geometric and visual measures, respectively. Thus, $$ \mathbf{d}(\mathcal{X}_i, \mathcal{X}_j) $$ and $$ \mathbf{d}(\mathcal{F}_i, \mathcal{F}_j) $$ denote the geometric and visual distances between images $$ \mathcal{I}_i $$ and $$ \mathcal{I}_j $$, respectively.

To generate visually comparable matches, the visual distance between landmarks $$ \mathcal{V'}=\{v'_i\}^n_{i=1} $$ and a sequence of images $$ \mathcal{I_\rho} $$ is utilized to calculate the flow cost rate at corresponding locations $$ \{x_i\}^n_{i=1} $$. The flows from the source to landmarks and from query pictures to the target incur no additional cost. In addition, we offer a robust loss for feature matching with associated cost values $$ c_{ij} $$ and capacity values $$ \omega_{ij} $$ defined as:

where $$ \mathcal{L}(.) $$ is the Huber loss function. Images are matched to (at most) a single landmark, so the maximum absolute flow at each query image is limited to a value of one, thus creating the capacity constraint:

with $$ \mathcal{E}_{v'} $$ and $$ \mathcal{E_{\pi}} $$ representing the directed edges spanning the partition of a bipartite graph between vertices of landmarks and image sequences, respectively. Given a radius of navigation $$ r $$, and source and target vertices $$ \{s, t\} $$, the flows $$ \{y_{ij}\} $$ are solved for by application of Second Order Cone Programming (SOCP) to the resulting convex optimization problem:

The solution of Equation (4) is used as the location, $$ x_l $$, of the query image $$ \mathcal{I}_l $$ indicated by the vertex $$ \pi_l \in \Pi $$.

2.2. Map creation from neural network features

The output from the NN is a feature map matrix of nodes, edges, and geographic distances between objects that correspond to actual physical locations from a small reference query (see Figure 5a). Therefore, in our developed model, a graph is created to represent the map of free space that is to be explored/traversed by our bats (Figure 6). All nodes in this graph correspond to geographic coordinates of features extracted from along the global path taken by the Oxford RobotCar (Figure 5b). These coordinates are also provided as a matrix of Northing/Easting values used in most GPS navigation systems. Section 3 provides further details on the use of the Bat Algorithm for image-based navigation in this research.

Figure 5. Neural network image feature space. (a) Matched reference sequence feature space. (b) Features space extracted from the RobotCar dataset.

Figure 6. Feature graph nodes (spatial coordinates) and edges (geographic distance between features). (a) Closeup of feature graph. (b) Relative feature graph.

3.1. Bat algorithm

The BA is a fresh technology inspired by the social behaviors of bats and their use of echolocation for distance sensing. It pertains to the swarm intelligence family of optimization algorithms. The BA is based on the premise that certain echolocation qualities are idealized, as specified in the following specific rules.

● Bats apply echolocation to sense distance and always have knowledge of their surrounding environment.

● Bats fly randomly with a velocity \(v_{i}\) and a fixed frequency \(f_{min}\) at a position \(x_{i}\), varying the wavelength \(\lambda\), and loudness \(A_{0}\) as they hunt for prey. They are able to instantly sense the wavelength of their emitted pulses and adjust the rate of the pulse emission \(r \in [0, 1]\) based on the proximity of their target.

● The loudness of the emission varies from a minimum constant (positive) \(A_{min}\) to a large \(A_{0}\).

In the BA, each bat is defined by its position $$ x_i^t $$, velocity $$ v_i^t $$, frequency $$ f_i $$, loudness $$ A^t_i $$, and the emission pulse rate $$ r_i^t $$ in a $$ d $$-dimensional search space. The new solutions $$ x_i^t $$ and velocities $$ v_i^t $$ at time step $$ t $$ are given by

where $$ \beta \in [0, 1] $$ is a random vector drawn from a uniform distribution. $$ \boldsymbol{x}_* $$ is the current global optimized solution from among all $$ n $$ bats. In general, the values that are typically assigned to the frequency range of the BA fall between 0 and 100, such that $$ f_{min} = 0 $$ and $$ f_{max} = 100 $$, and initially, each bat in the population is given a frequency that is drawn uniformly from $$ [f_{min}, f_{max}] $$.

During the search portion of the algorithm, the current best solution is used to calculate a new solution for each bat using a random walk.

where $$ \epsilon \in [-1, 1] $$ is a random number scaling factor and $$ A^t = \langle A_i^t \rangle $$ is the average loudness of all bats at some time step $$ t $$. Velocities and positions are updated in a similar manner to the standard updates in a PSO, where $$ f_i $$ essentially controls the pace and range of movement of bats.

Indeed, the BA can be considered a balanced combination of standard PSO and an intensive local search controlled by loudness and pulse rate. The loudness and rate of the pulse are updated as follows:

where $$ \alpha $$ and $$ \gamma $$ are constants set to $$ \alpha = \gamma = $$ 0.9 for the purposes of this paper.

3.2. Image-based bat algorithm path planning

Now that a primer to the BA and the computer-vision-based navigational topics have been presented, the integration method with the BA used to realize the combined algorithm is discussed in this section.

It is desirable to build an implementation that can integrate the essential features of the straightforward BA with the image-based navigation optimization technique. Instead of using external optimization libraries, such as the MOS optimization library, for selecting landmarks using visual features, our version of the BA is enhanced to include Dijkstra's Algorithm (DA) with the shortest path finding. The DA is incorporated into the BA to provide solutions for the routes created by individual bats.

Algorithm 1: Bat Algorithm for Image-based Navigation

Initialize the generation counter $$ t = 1 $$; Randomly initialize population of $$ N_P $$ bats and each bat $$ P $$ corresponding to a potential solution to the given problem; Initialize loudness $$ A_i $$, pulse frequency $$ Q_i $$, pulse rate $$ r_i $$, and initial velocities $$ v_i (i = 1, 2, . . . , N_P) $$; while:$$ t < $$ MaxGeneration do end Post-processing results and visualization

In algorithm 1, the BA is shown with two principal procedures defined. The first procedure is used to initialize all of the algorithm parameters required during the iterations of the computational steps, and the second procedure describes the actual computational flow. In the compute solution procedure, random adjustments to frequencies and velocities generate and select new solutions from the individual bats at any given time step. The best solution is carried forward to subsequent time steps until either the maximum iterations are reached or the optimal solution is found. The Equation (5)-Equation (7) are used for each of the operations referred to by the psuedocode presented below. Figure 6 illustrates the normalized feature coordinates in the Northing/Easting plane as nodes, and the length of the interconnecting line segments correspond to the distances between each feature illustrated in Figure 6. Thus, finding the shortest path through this network will also be the shortest path through the real geometry that is represented by the elements of the graph in this paper. By using both the graph and the coordinate matrices in this paper, a reference topological map and its coordinates can be created and then provided as arguments to the BA.

3.3. Algorithm complexity

The proposed image-based navigation involves the following steps:

$$ (1) $$ Capturing images of the environment;

$$ (2) $$ Processing and extracting visual features from the images;

$$ (3) $$ Identifying the location of the vehicle using the extracted features;

$$ (4) $$ Generating a path for the vehicle based on the location information.

The time complexity of image processing and feature extraction depends on the complexity of the algorithms used, the size and resolution of the images, and the number of features extracted. For example, CNNs used for feature extraction can have a time complexity of $$ O(n^2) $$, where $$ n $$ is the number of pixels in the image. However, various optimization techniques, such as down sampling and parallel processing, can be used to reduce the computational complexity.

The time complexity of BA used for image-based navigation in this paper depends on the complexity of the BA and the size of the environment. The worst-case time complexity of the BA is $$ O(\mathscr{N} * \mathscr{I} * \mathscr{C}) $$, where $$ \mathscr{N} $$ is the number of bats, $$ \mathscr{I} $$ is the maximum number of iterations, and $$ \mathscr{C} $$ is the time complexity of the objective function evaluation. However, in practice, the number of iterations required is much smaller, making the algorithm computationally efficient. The time complexity of the BA is dependent on the size and complexity of the input image datasets (landmarks) and the convergence rate of the algorithm. Besides, the BA is known for its efficiency and effectiveness in solving complex optimization problems.

The time complexity of the proposed image-based navigation is dependent on the properties of the environment being explored. The BA, as an efficient algorithm and optimization technique, is used to reduce the computational complexity and improve the performance of image-based navigation.

4.1. Simulation and comparison studies in various environments

To evaluate our proposed BA model, we first use it within a grid map and compare it with the PSO algorithm, Fuzzy NN (FNN), and Hybrid PSO and FNN Algorithm (HPFA) from^[38] in Scenario 1. Two grid-based maps are selected in Figure 7 and Figure 8. The size of the map is $$ 30 \times 30 $$. The population size of BA is set to 50. The parameter settings and experimental results of other algorithms are in^[38]. The comparative results of a variety of path planning methods are illustrated in Figure 7, which demonstrates that all four algorithms can effectively plan the way from the start to the target points in the grid map environment. However, the trajectory planned by the proposed BA is much shorter than the paths generated by the other three techniques. Table 1 summarizes the qualitative comparison between the features of our algorithm and selected algorithms, including maximum path length, minimum path length, and average processing time.

Figure 7. Path planning results in Scenario 1 from^[38]. (a) Generated trajectories of PSO, FNN, HPFA, and proposed BA. (b) Convergence of PSO, FNN, HPFA, and proposed BA.

Figure 8. Path planning results in Scenario 2 from^[38]. (a) Generated trajectories of ACO, GA, AAO, HPFA, KSPA, and proposed BA. (b) Trajectories length of ACO, GA, AAO, HPFA, KSPA, and proposed BA.

The simulation results in terms of the convergence of various methods are shown in Figure 7(b). The fitness function converges to a pretty high value after around 100 iterations of the PSO algorithm, as shown by the findings, which indicate that the method first converges more quickly and subsequently slows down significantly. The FNN method is distinct in that its convergence speed increases, and it converges after around 120 iterations; nevertheless, the fitness function converges to a higher value than the PSO algorithm. The HPFA method has a relatively better convergence result, while its convergence speed is slow. After around 50 iterations, the proposed BA method converges to the lowest fitness function among the four methods, and thus the convergence curve turbulence is minor.

In order to further verify the optimization and path planning capabilities of the proposed BA, we conducted another grid-based environment comparison study with Ant Colony Optimization (ACO), Genetic Algorithm (GA), A* Algorithm Optimization (AAO), Kth Shortest Path Algorithm (KSPA), and HPFA in Scenario 2. The simulation results provided in Figure 8(a) reveal that the path length of the proposed BA algorithm is substantially smoother and shorter than the other five methods. Figure 8(b) summarizes the length findings of the trajectories. When compared to previous grid map path planning algorithms, our developed BA approach has superior convergence and optimal solution. This might highlight the viability of the proposed BA in path planning.

To validate the adaptability and efficiency of our algorithm in various environments, one map with resolution $$ 1500 \times 1500 $$ from Massachusetts Roads Dataset^[56] is then selected for simulation and comparative studies. The initial and multiple target positions of the autonomous vehicle are randomly set. The initial position is $$ (1108, 1433) $$, target positions are $$ T_1 = (189, 1062) $$, $$ T_2 = (381, 163) $$, $$ T_3 = (1431, 640) $$, and $$ T_4 = (728, 611) $$, as shown in Figure 9. Two cutting-edge path planning algorithms, Probabilistic Roadmap (PRM) and Rapidly Exploring Random Tree* (RRT*), are utilized for comparative studies. PRM is a well-known and effective path planning method based on sampling. This approach can seek a solution utilizing a limited number of random sampling points and takes minimal processing time. It generates random sampling points in the free space of a given workspace to create a route network graph. Then, use Dijkstra to search the created route network graph for suitable routes. The number of PRM sampling points in this study is 1500. RRT* is also a sampling-based path planning algorithm similar to PRM. From the initial location, it randomly generates the sampling point to the spanning tree in the workspace and links it to the nearest obstacle-free point on the path tree to the sampling point. In all situations, the maximum RRT* iteration time is set to 500000, and the maximum connection distance is set to 4. We repeatedly execute 40 times in the selected scenario. Table 2 provides a qualitative assessment of the path length, smoothness rate, and execution time of the algorithm in comparison to other algorithms. The path smoothness rate $$ \psi $$ is based on the sum of the angles differences between adjacent path segments calculated by Equation (8).

Figure 9. Illustration of the real-world map from Massachusetts Roads Dataset, composed of $$ 1500 \times 1500 $$ nodes. The pink circle marks are starting and target points. The green line, blue line, and orange line denote the trajectory of PRM, RRT*, and our proposed BA, respectively.

The results indicate that path planning methods, such as PRM and RRT*, are insufficient when the sample points are inadequate or the distribution of the map is inappropriate. Although the RRT* method has a lower execution time, the proposed BA approach has a significant advantage in terms of path length and smoothness.

4.2. Image-based navigation with simulated datasets

Image-based navigation utilizes reference pictures as a collection of landmarks in a video sequence to meet image-based navigation and self-localization navigation techniques. However, due to insufficient datasets, the navigation experiment is conducted by utilizing simulated images as landmarks in this paper. It should be noted that since the reference image or the captured video is dependent extremely on the road segment passed by the previous video car, its generated landmarks are limited and random in the environment. The image-based landmarks we simulated have the same limitations, being only within a random portion of the map [Figure 10]. Therefore, to evaluate our proposed BA model, the image-based landmarks that are simulated have the same limitations, being only within a random portion of the map (Figure 10). Two algorithms, Dijkstra's algorithm and Slime Mound Algorithm (SMA) ^[57], are selected for comparison. The test workspace is a real-world map, as New York City map from the benchmark^[58]. 100 landmarks and 150 landmark data are simulated in Figure 10(a) and Figure 10(b), respectively. Among them, in Figure 10(a) and Figure 10(b), the green and yellow lines indicate the feasibility of connecting between landmarks (spatial coordinates) in the topological map, which are geographic distances between features. Purple, pink, and orange lines in Figure 10(a) and Figure 10(b) represent the final trajectories of Dijkstra's algorithm, SMA, and the proposed BA, respectively. Table 3 outlines the length of the trajectory planned by the tested algorithms. The results demonstrate that in the complex connection topological map, our proposed BA algorithm can obtain shorter paths than the Dijkstra's algorithm and SMA.

Figure 10. Comparison of the trajectory by the proposed Bat Algorithm image-based navigation with basic Dijkstra's algorithm. The image-based landmark datasets are randomly generated in the New York benchmark map^[58].

4.3. Image-based navigation with Oxford RobotCar Datasets

The simulation and comparison studies in this section aim to validate the proposed image-based BA navigation in real-world datasets. The image-based datasets are taken by the Oxford RobotCar. The proposed BA path planner initially obtains the solid green trajectory with the real world maps, as illustrated in Figure 11. While the updated dataset finds that the road segment is interrupted by an obstacle (as a blue polygon-shaped obstacle in Figure 11), BA can replan the trajectory in light of the existing dataset. The dashed purple and pink trajectories reveal the proposed image-based BA navigation with the replanned procedure. The detail of the proposed image-based BA navigation is accomplished by modifying and building the BA algorithm with an integrated Dijkstra's algorithm. The input to the BA algorithm is the graph representation of the reference query sequence shown in Figure 6 and a matrix of indices that corresponds to the feature coordinates.

Figure 11. Illustration of the overall trajectory by the proposed image-based Bat Algorithm navigation. The image-based datasets are taken by the Oxford RobotCar.

Once the BA algorithm is functional, it is converted and integrated at the correct location to process the image-feature graph. Output compares with the Thoma's output^[37]. The BA generated a series of graphs that are superimposed on the images presented in Section 3. Figure 12 also displays the best-fit values of each BA iteration to illustrate how swiftly the BA converges to its optimal solution. Several simulations were carried out utilizing our integrated technique, and the findings shown here are illustrative of typical worst-case convergence times. Each simulation result is accompanied by a brief caption and a zoomed-in view, allowing the reader to gain a clearer sense of the volume and scale of each of the features being processed in the graph. The intention is to demonstrate how the BA output compares to the Thoma's output^[37].

Figure 12. Number of iterations until Bat Algorithm convergence.

As can be seen in Figure 12 above, the BA was able to converge upon an optimal solution in 33 iterations. This represents the worst-case results observed during the experimentation phase of this project. On average, convergence occurs in approximately 5-10 iterations in our studies. In the results shown in Figure 13 and Figure 14, the BA output is overlayed against the original simulation outputs from the^[37]. It is clear from these plots that the BA finds the optimal path through the given topography and does not hinder or otherwise alter the effectiveness of the global navigation strategy.

Figure 13. Reference query with Bat Algorithm solution superimposed. UTM is Universal Transverse Mercator. (a) Bat Algorithm solution vs. reference query. (b) Zoomed solution vs. reference query.

Figure 14. Raw feature topology with Bat Algorithm solution superimposed. (a) Bat Algorithm solution vs. raw feature topology. (b) Zoomed Bat Algorithm solution vs. raw feature topology.

4.4. Analysis and discussions

Several simulations using our developed hybrid model were performed during the course of testing this implementation, with the results of the BA proving to be adept at traversal of the known topography produced by the image feature-based recognition. This is an encouraging result since new feature identification strategies are the topic of much research today and are likely to achieve even better results over the next few years. The true test of whether or not the algorithm can be used in real world environments will come once a dynamic obstacle avoidance method can be added to the algorithm.

We made many attempts to integrate the BA algorithm at various locations in the processing pipeline, but it became clear that the geographic feature distances were not calculated in the^[37] algorithm but were instead processed by the algorithm. This makes the identification of the best place to perform the task of integration very difficult and may point to the need to have optimization algorithms performed up front in the process, potentially eliminating the need for other proposed methods entirely (future work). Nevertheless, the best implementation of BA would take place where the path-optimizer and the graph-traversal libraries can be switched out with their equivalent optimization biologically inspired implementation.

The full image feature extraction process was explored here to process the raw image features into the format that is best suited to a dynamic real-time path planner with inherent obstacle avoidance such as the D*-Lite algorithm^[59]. Thoma et al.^[37] integrated a localization method against a reference map, but to be fully integrated with a path planning algorithm, it needs to be more functional in a real-world sense. Other researchers have focused on competing technologies, such as using PSO methodology to train FNNs^[38] focusing on the optimization of parameters during the front-end NN feature extraction. Yet, others have used reinforcement learning techniques to select an optimal path in ultra-dynamic emergency environments through hybrid NNs and A* algorithms^[54]. Their reasoning is to focus entirely on the back-end processing to help intelligent vehicles plan dynamic routes around traffic emergency conditions, including limitations on vehicle height, width, weight restrictions, or accidents and traffic jams.

These approaches differ from the current research in that they focus on optimizing both before and long after map building occurs. The need for a simultaneous SLAM-like solution remains. When compared with other biologically inspired algorithms for path planning in image-based systems, the BA has shown that it is capable of the challenge, but it will also need to prove that it can be deployed in a mature and accurate localizing methodology (which has been demonstrated on a known dataset, but not on a live video camera feed). For these reasons, it would make the most sense to integrate a parallel architecture with the path planner that has access to those same raw features as the SLAM method given in the article. The local map that is built by the raw camera feed is used to generate a current coordinate location for the autonomous vehicle body within the region of the visible and identified map. The path planning algorithm, however, would be capable of resolving a path to the goal location from the current localized coordinates up to the extreme edge of the map, which could presumably be incomplete or inaccurate due to the sensor errors. A heuristic distance to the end goal coordinate could be used as a guideline to navigate in the local region, avoiding and replanning based on dynamic obstacle avoidance, and as new information becomes available in the dataset, continue to work toward that goal location.

In future research, an experiment and design to implement the BA into a Field Programmable Gate Array (FPGA) would also help to keep the burden of constant re-calculation down and help to distribute the task of feature extraction to a specific piece of parallel modular hardware. An interface to the input camera feed can be sent to the SLAM module and, simultaneously, to the embedded hardware housing the FPGA.

Acknowledgments

The authors would like to thank the editor-in-chief, the associate editor, and the anonymous reviewers for their valuable comments.

Authors' contributions

Made substantial contributions to the research, idea generation, algorithm design, and simulation and wrote and edited the original draft: Short D, Lei T, Carruth D, and Luo C

Performed critical review, commentary, and revision and provided administrative, technical, and material support: Carruth D, Bi Z

Financial support and sponsorship

This research was supported by the Mississippi Space Grant Consortium under the NASA EPSCoR RID grant.

Availability of data and materials

Not applicable.

Conflicts of interest

All authors declared that there are no conflicts of interest.

Ethical approval and consent to participate

Not applicable.

Consent for publication

Not applicable.

Copyright

© The Author(s) 2023.