Optimized Frontier-Based Path Planning Using the TAD Algorithm for Efficient Autonomous Exploration

Abstract

A novel path-planning method utilizing the trapezoid, adjacent, and distance, (TAD) characteristics of frontiers is presented in this work. The method uses the mobile robot’s sensor range to detect frontiers throughout each exploration cycle, modifying them at regular intervals to produce their parameters. This well-thought-out approach makes it possible to choose objective points carefully, guaranteeing seamless navigation. The effectiveness and applicability of the suggested approach with respect to exploration time and distance are demonstrated by empirical validation. Results from experiments show notable gains over earlier algorithms: time consumption decreases by 10% to 89% and overall path distance for full investigation decreases by 12% to 74%. These remarkable results demonstrate the efficacy of the suggested approach and represent a paradigm change in improving mobile robot exploration in uncharted territory. This research introduces a refined algorithm and paves the way for greater efficiency in autonomous robotic exploration. This study opens the door for more effective autonomous robotic exploration by introducing an improved algorithm.

1. Introduction

Autonomous vehicles (AVs) can reduce human error and irresponsibility, which is the main cause of auto accidents. To ensure safe and efficient navigation, AVs need to consider time, energy, and distance. Path-planning algorithms are crucial for identifying and evaluating feasible paths to achieve these objectives. When it comes to navigation, robots may perform a variety of tasks, including dynamic navigation, obstacle avoidance, boundary recognition, localization, environmental modeling, and navigation control. Motion control, mapping, perception, localization, and path planning are the four primary navigational problems.

Among these challenges, path planning—which consists of three primary components—stands out as the most crucial task for mobile robot navigation. The targeted path must first begin at a specified place and terminate at a predefined point. The second prerequisite is that the path should facilitate the robot’s movement while avoiding obstacles. Third, out of all feasible possibilities that satisfy the first two requirements, the optimal course should be selected. When path-planning algorithms are examined, they are grouped according to a variety of criteria. Thanks to clever technology, these algorithms may be separated into heuristic and traditional techniques. Depending on the features of the environment, planning techniques can be classified as either static or dynamic. Additionally, the degree of comprehensiveness of the environmental data may be used to differentiate between different planning strategies. Global path planning refers to methods that have access to all accessible information, whereas local route planning often consists of knowledge limited to the robot’s immediate surroundings. Local path planning is more suited because of the changing nature of the environment, which sometimes results in insufficient knowledge about it [1,2,3,4,5,6,7].

A route can be designed using a variety of techniques, including optimization strategies, cell decomposition techniques, potential field techniques, tree and graph-based approaches, and intelligent technology-based systems that employ behavioral methodology.

Exploration approaches in unexplored regions may now be divided into three primary categories: mapping, pathfinding, collision-free route design, and localization.

• Random-based traversal is a technique that involves approaching a barrier by moving ahead and then randomly selecting a new path to investigate. However, this approach consumes a lot of time and gasoline for traveling long distances [8,9,10].

• Path discovery in this type of research is based on environmental models, such as grid mapping and cell decomposition. Pathfinding for exploration is done using these grid or cell reference points. Grids or cells are used to depict the various sections of the environment [11,12].

• Sensor-based traversal without prior environment information: These techniques employ algorithms to guide the robot’s motion based on real-time sensor data gathered by laser or camera sensors [13,14,15,16,17].

These three fields cover a broad spectrum of methods that scholars have studied over the last 30 years and are all pertinent to autonomous exploration and navigation in unexplored locations. An innovative convex decomposition technique is presented by Nielsen and Gao [18,19] for defining the autonomous units’ coverage path. This innovative method surpasses its predecessors in breaking down sub-polygons and investigating solution spaces, solving the optimality and complexity issues of current convex decomposition strategies. The new algorithm in our study significantly improves autonomous path planning by integrating cutting-edge tactics for mobile robots traversing unfamiliar terrains, all while taking inspiration from such creative approaches.

Random frontier points’ optimization (RFPO) and the multistep path-planning algorithm proposed by Fang et al. [20] enhance exploration efficiency by dynamically evaluating frontier points based on information gain, navigation cost, and localization precision. The multistep strategy further reduces redundant paths by updating target frontier points after a predefined movement step size, ensuring adaptive and efficient exploration.

A recent hierarchical path planner using RL-based frontier selection improves exploration by reducing the search space with edge detection and leveraging trust region policy optimization (TRPO) for optimal frontier selection [21]. This method enhances training efficiency, shortens path lengths, and increases exploration completeness by up to 14.3%. These advancements align with our TAD algorithm’s focus on efficient frontier prioritization and adaptability in unknown environments.

By suggesting and combining three coverage route planning strategies, Horvatha et al. [22] make a substantial contribution with the Iterative Structured Orientation Coverage (ISOC) algorithm. This method uses original map data to computationally create primary segments and ancillary lines, mirroring the ideas of efficient exploration. The ISOC technique comprises calculating parallel line beams and minimal-length auxiliary lines, which aligns with the new algorithm’s sophisticated approach. This alignment emphasizes how advanced navigation techniques are a typical feature of autonomous systems. To accomplish optimum coverage route planning in the face of various decision-making scenarios under dynamic operating conditions, Pham et al. [23] employ an integrative strategy that combines adaptation, knowledge reasoning approaches, and hedge algebras. Their study’s practical application in a mobile vacuum cleaner demonstrates how cutting-edge approaches may be applied in the real world. These useful additions, like the efficacy-focused methodology of the suggested algorithm, make strategic use of LIDAR sensor data to expedite exploration and improve navigation effectiveness.

A complete autonomous ground vehicle designed for usage in ionizing radiation zones, such as those around closed nuclear power reactors, is presented by Groves et al. [24]. This car uses cutting-edge software that converts radiation measurements into navigable data to avoid high radiation locations and avoid issues and impediments. Inotsume et al. [25] focus on path planning for rovers on sloping, deformable terrain where slippage is a problem. Chance-constrained planning is suggested to traverse these terrains securely. By integrating optimal control and lattice-based planning, the approach put out by Bergman et al. [26] successfully resolves path planning in unstructured scenarios. This strategy leverages the benefits of both methods for optimal results.

Recent advancements in predictive modeling, such as the work by Peng et al. [27] on flexible electrohydrodynamic (EHD) pumps using Kolmogorov–Arnold Networks (KANs), underscore the growing importance of computational methods in optimizing system performance. The KAN model demonstrated significant improvements in predictive accuracy and interpretability by replacing fixed activation functions with learnable spline-based functions. The principles behind KANs, such as adaptive learning and the integration of symbolic formula extraction for better interpretability, align with the objectives of our TAD algorithm. While the application domains differ—KAN focuses on pressure and flow rate prediction in flexible EHD pumps, and TAD addresses frontier-based exploration—the underlying emphasis on adaptive optimization and computational efficiency is highly relevant. Both approaches aim to improve system performance through advanced modeling techniques that reduce redundancy and enhance decision-making accuracy.

Recent advancements in predictive modeling, such as the work by Peng et al. [28] on predicting flow status in flexible rectifiers using cognitive computing, highlight the efficacy of advanced computational techniques in complex system analysis. Their study employed cognitive computing methods to accurately predict flow status, demonstrating the potential of integrating machine learning algorithms for enhanced system performance. This approach aligns with our objectives of improving exploration efficiency and adaptability in dynamic environments. By incorporating similar predictive modeling strategies, our TAD algorithm could further optimize path selection and decision-making processes, leading to more efficient and accurate exploration outcomes.

An inventive exploration technique based on the topological characteristics of a grid hybrid map was presented by Liu and associates [29]. This approach comprises the establishment of a resilient topology node in addition to the production of target points based on well-defined geometry criteria. Zhang et al. [30] presented a state-of-the-art topological and semantic grid map-based indoor navigation method in keeping with their groundbreaking study. One unique aspect of their approach is the use of natural language for goal point selection, a calculated improvement that significantly improves the security, effectiveness, and general resilience of mobile robot navigation.

Shi et al. [31] proposed a hierarchical frontier-based path-planning framework challenges in environments with large obstacles, such as expansive walls and towering structures. By using point cloud voxel down-sampling, frontiers are transformed into a spatially uniform point set. An optimized decision function then identifies the best local guide point to streamline UAV navigation. Simulations and real-world experiments show significant improvements in adaptability and path efficiency. This approach complements the objectives of our TAD algorithm by emphasizing efficient frontier processing and optimal decision-making for navigation in complex environments. An effective computational approach was proposed by Senarathne et al. [32] to address the computational problems related to map data updates. This technique produces secure and trustworthy border information by skillfully handling locally updated map data. The program handles the database’s progressive updating, which includes borders between mapped and unknown cells that are considered safe for the robot. It also goes into figuring out whether the database’s frontiers are feasible. Delineation of contours along the borders facilitates the extraction of attained frontiers.

In unstructured situations, Lu et al. [33] experimented with a frontier exploration algorithm based on RGB-D sensors. This method uses Octomap to split the environment strategically, and a well-crafted cost function for information collection is used to identify the ideal frontier. Jiang et al. [34] presented a laser-based SLAM method in a parallel study. The robot’s decision-making process for planning the next objective location in the exploratory voyage is informed by their technique, which uses input from eight directions of the environment to calculate path vector likelihood. Together, these innovative studies offer a thorough investigation of state-of-the-art approaches in the broad field of robotic navigation and exploration in unfamiliar settings.

This work presents a novel path-planning approach that builds upon traditional frontier-based exploration by introducing three unique parameters, distance, adjacent, and trapezoid, that contribute to more efficient and informed decision-making for autonomous navigation. By focusing on optimization within unknown environments, the proposed algorithm aims to improve exploration coverage and resource utilization, marking a significant advancement over existing methods.

Motivation

To show information about a multi-cell region, mobile robots and SLAM algorithms frequently use a grid map [35,36]. However, mobile robots have memory and computational overheads due to the grid map’s enormous cell count, particularly when comprehensive map representation is needed. In our earlier study, we suggested a novel mapping method called Rmap [37] and a path-planning algorithm called Rmap+ [38] to alleviate these overheads. In Figure 1, the mapping strategy is shown. The Rmap technique uses rectangles rather than grid map cells to lower overhead in SLAM. This method enables effective exploration during SLAM processing in uncharted settings.

Additionally, the mapping scheme provides a means to discover new data in unchartered environments.

The initial phase of the Rmap process commences with the gathering of fundamental data when a sensor-equipped robot operates within an uncharted territory, as illustrated in Figure 2a. At this juncture, the robot constructs a primary map of the prevailing environment by capturing raw sensory data while rotating, visually depicted as the white expanse in Figure 2b. The determination of the primary map’s boundaries involves the Minimal Bounding Rectangle (MBR) module, which generates a rectangle outlined by the blue dashed box in Figure 2b. The MBR, constituting the smallest rectangle enveloping all areas obtained during the primary map setup, defines the spatial confines.

The subsequent phase entails the creation and selection of an internal rectangle denoted as R1 within the MBR. Specifically, R1 represents the most substantial rectangle compatible with the dimensions of the MBR. The Rmap algorithm employs the rectangle tiling algorithm, a mathematical approach for identifying adaptable rectangles within a grid, to formulate R1. For a rectangle of height m × width of n, all rectangle candidates can be computed in the generated MBR using the tiled rectangle algorithm as shown in Equation (1).

(1)$N\left(m,n\right)={\sum }_{i=0}^{m-1}{\sum }_{j=0}^{n-1}\left(m-i\right)\left(n-j\right)={\displaystyle \frac{1}{4}}m(m+1)n(n+1)$

Once R1 is established, the robot initiates exploration to accumulate fresh information within the area. In a preceding study, the exploration path planning involved tracing the perimeters of the newly generated R1, illustrated by the red line in Figure 2c. Upon the conclusion of the exploration phase, the robot gains access to new areas, expanding the white region as depicted in Figure 2d.

This navigation technique is deliberately used by the Rmap framework to create an exploration route that reduces unnecessary travel over uncharted territory. The significant decrease in grid map overhead that Rmap facilitates is supported by empirical results. When compared to a traditional grid map, the Rmap scheme’s memory space efficiency was shown to be 84% poorer, depending on the environment’s structural characteristics. This validates the Rmap approach’s effectiveness and resource optimization in the context of robotic exploration in unexplored areas.

Using the largest rectangle created during the previous exploration period, the Rmap algorithm used the rectangle tiling algorithm to define an exploration path in our earlier studies. To get around the rectangle following path planning, we used the Rmap+ path-planning algorithm to gather new environmental data. However, because the robot carefully followed the rectangle’s boundaries to gather new data, both approaches led to long journey lengths and incorrect conclusions. This study addresses this issue by presenting a novel path-planning technique that improves the previous Rmap’s Exploration sub-module for more efficient path planning.

Researchers have proposed many path-planning algorithms, such as the Frontier-based exploration approach proposed by B. Yamauchi [39]. However, this algorithm has two significant shortcomings: it gives all frontiers equal importance and spends time and space thoroughly investigating each frontier. There have been other suggestions, such as the cost-utility functions for border selection put out by Gomez et al. [40]. But according to their research, the robot could run into problems, requiring more journey distance for thorough investigation.

In this publication, we present the novel path-planning algorithm, which is an improvement on the frontier-based exploration approach [40] and our earlier research [37,38]. By improving the Rmap method’s Exploration submodule, we hope to suggest an improved version of the original algorithm. We presented the Rmap+ method [38], which makes use of frontier pairings. Furthermore, we aim to overcome the path-planning restrictions of the original Rmap technique by drastically reducing the overall path distance and exploration time.

The paper is structured as follows: Section 2 presents the methodology of the proposed algorithm, detailing the novel multi-parameter frontier selection strategy and the specific algorithms. In Section 3, we describe the experimental setup, including the test environments, robot dimensions, parameter configurations, and results of our experiments, comparing the performance of the proposed method with existing algorithms. Finally, Section 4 provides conclusions and highlights potential directions for future research.

2. Materials and Methods

The new method, presented in this research, is founded on the frontier-based concept introduced by Yamauchi [39]. The block diagram depicted in Figure 3 outlines the structure of the Rmap Exploration module [37], comprising two integral components:

• Mobile Robot Module: The Mobile Robot module initiates the collection of data from the LIDAR sensor. Upon receipt of position data from the Goal point generation sub-module, the robot commences movement toward the designated target point using the Navigation sub-module.

• Frontier Selection Module: The Autonomous Frontier Selection module processes data from the LIDAR sensor, identifies optimal frontiers, computes parameters, generates a goal point, and updates the map through various sub-modules, including Scanning environment, Frontier detection, Computation of frontiers’ parameters, Frontier selection, Mapping procedure, and Goal point definition.

To delve into further specifics, this framework integrates a localization module for the execution of the SLAM process. The Mobile Robot module establishes the initial state of the robot based on odometer and rangefinder data [37,41,42,43]. Throughout each exploration round, the mobile robot undergoes a series of six distinct steps to determine the most informative frontiers:

• The environment scanning sub-module collects preliminary data about the environment.

• The robot determines frontiers and their length according to sensing data. These frontiers represent the boundaries between known and unknown regions that the robot needs to explore.

• The robot estimates the frontier parameters, encompassing distance, adjacent, and trapezoid costs within the unknown area.

• The robot selects the best frontier according to the parameter’s values of each frontier.

• The robot generates the rectangle and adds to the topology map or the Rmap database, contingent on the implementation procedure. This update ensures that the robot has the latest information about the environment, facilitating better navigation decisions.

• The center of the frontier is designated as the subsequent goal point for robot navigation.

This objective point directs the robot’s efficient navigation toward new locations to gather additional data. The robot does not dynamically alter the target while it is on its journey. Until the robot gets to the chosen objective location, it stays there. By eliminating frequent objective changes that might lead to unpredictable behavior and ineffective exploration, this method guarantees a clear and deterministic path-planning technique. By reducing needless navigation and increasing exploration efficiency, this technique aims to improve autonomous path planning for mobile robots. This is especially helpful in complex interior settings [42].

2.1. Frontier Parameters and Selection Policy

The proposed frontier selection method is designed to ensure robust autonomous navigation in unknown environments by leveraging three key parameters: distance, adjacent, and trapezoid. These parameters are mathematically integrated to provide a balanced decision-making process that optimizes exploration efficiency while maintaining adaptability to various environmental layouts.

• Distance parameter—d_n prioritizes frontiers farther from the rectangle’s sides’ position, aiming to maximize the unexplored area. This contributes to the robustness of the algorithm by ensuring consistent coverage and preventing redundant exploration. The process of determining the distance parameter is shown in Figure 4a and Table 1.

(2)$d_n=\sqrt{{(x_f-x_r)}^2+{(y_f-y_r)}^2}$

where n—number of frontiers; x_f, y_f—coordinates of frontiers’ center; and x_r, y_r—coordinates of rectangle’s position.

In environments where frontiers are unevenly distributed due to clustered obstacles, the algorithm incorporates additional mechanisms to ensure effective exploration and prevent the robot from getting trapped in local minima. Specifically:

Dynamic distance scaling—the distance parameter dynamically adjusts its weight based on the dispersion of frontiers. When frontiers are concentrated in a small area, the algorithm applies a scaling factor to prioritize frontiers farther from the robot’s current position. This ensures that the robot explores new areas rather than revisiting already explored regions.

Frontier clustering and prioritization—frontiers within a certain proximity are grouped into clusters. The algorithm evaluates clusters rather than individual frontiers, selecting the cluster with the highest combined score (Fn). This prevents the robot from repeatedly selecting frontiers within the same cluster and encourages exploration of dispersed areas.

Exploration bias factor—an exploration bias is introduced into the distance parameter to favor frontiers that maximize the expansion of the explored map. For each frontier n, the exploration potential is calculated as:

$d_n^{adjusted}=d_n\times \left(1+{\displaystyle \frac{{Area}_{unexplored}}{{Area}_{total}}}\right)$

where ${Area}_{unexplored}$—represents the size of the unexplored area connected to the frontier. This adjustment ensures that the robot prioritizes frontiers leading to larger unexplored areas.

Local minima detection—the algorithm monitors the robot’s trajectory for repetitive patterns. If the robot revisits the same region within a predefined threshold, it triggers a “reset” mechanism that forces the selection of a distant frontier, overriding the standard scoring criteria. This mechanism prevents the robot from being trapped in local minima caused by clustered obstacles.

The distance parameter contributes to robustness by ensuring both adaptability and efficiency.

Adaptability: By dynamically recalculating d_n as the robot moves, the algorithm ensures responsiveness to changing environments.

Efficiency: Larger d_n values are prioritized to avoid redundant revisits, maximizing the area covered per movement cycle.

• Adjacent parameter a_n quantifies the connectivity between rectangles by evaluating the proximity of neighboring rectangles directly connected to the main rectangle. The parameter’s value lies within the range [1, n], where n is the total number of detected frontiers (Fn). A higher a_n value indicates that the corresponding rectangular side or frontier encompasses a larger unexplored area, making it a high-priority target for navigation. The process defining the adjacent parameter value is as follows and presented in Figure 4b and Table 1.

In environments of increasing complexity, where the number of obstacles and frontiers rises, the robot ensures scalability by:

Rectangle generation in sensor range—within the robot’s sensor range, rectangles are dynamically generated for all detected frontiers, regardless of the environment’s complexity. This guarantees comprehensive coverage and ensures that no potential exploration areas are overlooked.

Localized adjacency evaluation—the robot calculates adjacency only for frontiers within a localized zone defined by its sensor range. This approach limits the number of adjacency computations required, ensuring that the algorithm remains efficient even in environments with numerous obstacles.

Dynamic complexity adaptation—in complex environments, the algorithm prioritizes frontiers with higher a_n values. These frontiers correspond to areas with higher connectivity and potential for exploration, reducing redundant computations for less significant frontiers.

Incremental updates—as the robot moves and explores, the adjacency relationships are updated incrementally, recalculating only for new or modified rectangles. This strategy prevents the need for full recalculation at every step, minimizing computational overhead.

Scalability and efficiency—by focusing computations within the sensor range and dynamically updating only affected adjacency relationships, the algorithm effectively handles complex environments. The rectangle generation mechanism ensures that the robot adapts seamlessly to varying levels of environmental complexity without sacrificing performance.

Let us denote: The first rectangle by R₁(x₁, y₁) (x₂, y₂). The second rectangle by R₂(x₃, y₃) (x₄, y₄).

Horizontal Adjacency: They will overlap in the y-axis. The overlapping area’s y-coordinates are between max(y₁, y₃) and min(y₂, y₄).

Vertical Adjacency: They will overlap on the x-axis. The overlapping area’s x-coordinates are between max(x₁, x₃) and min(x₂, x₄).

For Horizontal Adjacency segment calculation: Set x-coordinates as x₂ for R₁ and x₃ for R₂. Overlapping area in y-axis:

y_overlap = [max(y₁, y₃), min(y₂, y₄)](3)

For Vertical Adjacency segment calculation: Set y-coordinates as y₂ for R₁ and y₃ for R₂. Overlapping area in x-axis:

x_overlap = [max(x₁, x₃), min(x₂, x₄)](4)

The generation and calculation of the adjacent parameter in our algorithm are grounded in the Rmap methodology described by Lee et al. [37]. This paper introduces a robust rectangle-based mapping scheme, the Rmap, which efficiently handles nested and overlapping rectangles through the following approaches:

Rectangle generation and data structure—the Rmap algorithm generates a set of minimal bounding rectangles (MBRs) to represent mapped areas. These MBRs encapsulate sensed data dynamically and efficiently, even in environments with irregular or nested obstacles. The generated rectangles are represented using a graph-based data structure, where each rectangle is a vertex node (VNode), and its adjacent connections are stored in adjacent nodes (ANode). This ensures accurate adjacency information while minimizing computational redundancy.

Handling overlaps and nested rectangles—overlapping and nested rectangles are systematically handled by identifying and maintaining adjacency relationships through shared edges or overlapping areas. The Adjacent Center Point (ACP) is used to define these relationships, ensuring accurate calculation of adjacency and connectivity in complex layouts.

Efficiency and computational complexity—the computational complexity of adjacency calculations is reduced by leveraging the graph structure of the Rmap, which limits adjacency evaluations to local neighbors.

For F rectangles, the adjacency complexity scales as (F⋅C), where C is the average number of connected neighbors. This is significantly more efficient than the (F²) complexity of global pairwise evaluations.

Accuracy and timeliness—the algorithm incrementally updates adjacency relationships as new rectangles are generated, ensuring that the adjacency parameter remains accurate and timely. By caching previously computed relationships, redundant recalculations are avoided, enabling real-time responsiveness even in highly dynamic or complex environments.

These mechanisms, as demonstrated in Lee et al. [37], have been adapted and extended in our work to ensure that the adjacent parameter supports efficient exploration without sacrificing accuracy or computational efficiency.

The adjacent parameter contributes to robustness by ensuring precision and adaptability.

Precision: Higher a_n values indicate better connectivity, reducing unnecessary turns and optimizing path smoothness.

Adaptability: Adjustments to adjacency weights allow the algorithm to prioritize frontiers in denser or sparser environments, ensuring robustness in varying layouts.

• Trapezoid parameter—t_n is an inverse trapezoidal shape value of the region relative to the robot. The trapezoid parameter t_n is described using inner and outer frontiers, respectively, f_n and F_n, as depicted in Figure 4c [38] and Table 1. For inner frontier f_n and outer frontier F_n, the trapezoid parameter t_n can be defined as:

(5)$t_n=\left\{\begin{array}{c}1, if ‖F_n‖>‖f_n‖ \\ 0, if ‖F_n‖=‖f_n‖ \\ -1, if ‖F_n‖<‖f_n‖ \end{array}\right.$

where ‖F_n‖ and ‖f_n‖ represent the sizes of the outer and inner frontiers, respectively. Positive t_n values (inverse trapezoidal shapes) suggest an area worth exploring due to its openness, whereas negative or zero values imply constrained regions less suitable for exploration.

The robustness of the trapezoid parameter is due to precision and adaptability.

Precision: Positive t_n values prioritize expanding regions, ensuring exploration focuses on informative areas.

Adaptability: The evaluation of frontier shapes allows the algorithm to adjust its focus in irregular or cluttered environments.

Using the above parameters, we define a comprehensive score F_n for each frontier that combines d_n, a_n, and t_n to prioritize exploration. The objective function for each frontier score F_n can be formulated as:

(6)$F_n=d_n+a_n+t_n$

The frontier with the highest score F_n is selected as the next goal, ensuring the robot explores in a manner that maximizes distance, continuity, and feasibility.

The robustness validation of the algorithm is as follows:

1. Optimization: The frontier with the highest F_n value is selected, ensuring the robot navigates efficiently toward the most informative areas.

2. Adaptation to Environment: By iteratively updating F_n values, the algorithm adjusts to environmental changes, maintaining robust performance.

We considered a few elements in our algorithm that make it a better option than alternative techniques. By combining effective traversal algorithms with pairs of frontiers, the algorithm provides a balanced approach to path planning that permits adjustments based on environmental factors.

The advantages of the algorithm are as follows:

1. Adaptive Path Optimization: The algorithm dynamically adjusts its path-planning strategies based on sensor data, improving overall efficiency in various environments.

2. Reduced Computational Overhead: Compared to traditional algorithms, this method employs heuristic techniques that reduce the computational burden, enabling faster processing times.

3. Scalability: The algorithm is highly scalable, making it suitable for both small and large-scale environments without significant performance degradation.

The robustness of the proposed TAD algorithm is validated through its ability to adapt to diverse and complex environments by leveraging the combined influence of Trapezoid, Adjacent, and Distance parameters. Each parameter contributes uniquely to the algorithm’s decision-making process:

The trapezoid parameter evaluates the openness of a frontier by comparing the sizes of inner and outer frontiers. Positive values prioritize regions with significant potential for exploration, reducing the risk of selecting constrained or non-informative areas. This ensures that the robot consistently targets regions that maximize map coverage.

The adjacent parameter enhances path continuity by prioritizing frontiers that are spatially connected to the robot’s current location. This minimizes unnecessary turning points and traversal redundancy, ensuring smooth navigation through both dense and sparse environments.

The distance parameter dynamically adapts to the environment by prioritizing frontiers farther from already explored areas. By incorporating scaling factors based on unexplored area size, the algorithm effectively avoids local minima and ensures exploration extends to new regions.

2.2. Computational Complexity Analysis

The computational complexity of the proposed TAD algorithm arises from the three main components: Frontier detection, Parameter computation (Trapezoid, Adjacent, and Distance), and Goal point generation.

Frontier Detection—the time complexity of detecting frontiers depends on the number of cells (or nodes) in the grid map. Assuming N is the total number of cells, the frontier detection has a complexity of (N), as it involves scanning each cell to identify boundaries between known and unknown areas. Parameter computation:

Distance Parameter: Calculated based on the Euclidean distance between the rectangle’s position and frontier center, with complexity (F), where F is the number of frontiers.

Adjacent Parameter: Depends on adjacent relationships and overlaps, with a complexity of (F × A), where A is the average number of adjacent frontiers.

Trapezoid Parameter: Involves evaluating inner and outer frontiers, with a complexity of (F).

The combined complexity for parameter computation is (F × (1 + A)), where F and A are typically much smaller than N.

Goal point generation—after computing frontier scores, selecting the frontier with the highest score involves sorting or iterating through the list, leading to (F).

Overall, the computational complexity of the TAD algorithm per iteration is (N + F × (1 + A)). In practice, F and A are significantly smaller than N, making the method computationally efficient.

3. Experimental Results and Discussion

To conduct our studies, we set up a simulation environment and used the Robotics Operating System and the Robotics System Toolbox in the MATLAB 9.14 environment. Making use of this integrated toolkit made it easier to simulate a robot sensor in a virtual environment. Processing rangefinder data and optimizing the sensor’s range to efficiently identify borders were made possible in large part by the robotics system toolkit.

As shown in Figure 5, we carried out simulated tests in three different kinds of situations to examine the robot’s autonomous exploration capabilities. The robot was equipped with a LIDAR sensor for these simulated trials, and Table 2 provides a detailed description of the study’s specifications. We evaluated the performance of our suggested approach by contrasting it with two other exploration algorithms [37,40]. For benchmarking, we selected Rmap [37] and frontier selection based on cost functions [40] due to their established use in autonomous exploration. The Rmap algorithm is well-known for its low computational overhead and memory efficiency, making it suitable for real-time applications, particularly in structured environments. Frontier selection based on cost functions, on the other hand, uses a utility-based approach to prioritize frontiers, which can yield efficient exploration in dynamic and unstructured environments. These algorithms provide complementary perspectives—Rmap represents efficiency in simpler environments, while cost function-based frontier selection demonstrates adaptability to complex spaces. By comparing our method against these algorithms, we aim to showcase the proposed algorithm’s capability to balance computational efficiency with adaptability in diverse exploration settings.

The creation of both inner and outer boundaries is the primary difference between these two comparison algorithms and our suggested approach. To guide the path-planning procedure and finally choose the best frontier, our system also computes three parameters related to the created frontiers. The robot has a circular base with a diameter of 0.3 m and a height of 0.2 m. These dimensions are typical for mobile robots used in indoor navigation and allow for precise maneuverability in tight spaces. Using a mobile robot outfitted as shown in Table 2, all three algorithms were evaluated in the same way.

Figure 6 and Figure 7 show the frontier selection process’s first two phases graphically together with the associated paths produced by simulation tests carried out in a cyclic indoor setting. The robot is positioned in the center of a circle in the scenario shown in Figure 6a, with two circular areas on either side representing the sensor’s reach for identifying inner and outside borders. The red lines in the picture indicate the magnitudes of the Inner and Outer bounds, which are designated as F[n] and f[n], respectively. The pointer line, which is in line with the center of the optimum frontier, indicates the next objective point. The exploration process’s progression through six different stages in this indoor setting is noteworthy [38].

The robot recognizes two border pairs, F[2] and f[2], in the first phase. During this procedure, the sizes of the internal and exterior borders—designated as L[2, 2] and L[3, 2], respectively—are established. Before comparing the size of each internal frontier (l[2, 2]) with its corresponding counterpart in the exterior frontiers (L[3, 2]), the approach first determines the dimensions of the borders. Figure 6a illustrates this contrast. As previously stated, the trapezoid parameter t[n] receives equivalent values of 1, 0, and −1 based on comparisons between the relevant borders. F1 receives 1 and F2 receives 0 values in the first stage. The matching values given in their rules are then also applied to the neighboring and distance parameters. Table 3 displays all three parameters’ values. The same border is indicated by all three parameters.

At the conclusion of the first stage, the program calculates and summarizes each observed frontier’s three parameters. According to calculations, frontier 1 has a higher value than frontier 2, thus the robot chooses it as its next exploration target. An identical procedure is followed in the second round, as shown in Figure 7. Table 4 displays the calculated and obtained values of the parameters. In contrast to the first stage, just two factors choose one border in the second step. Frontier 2 was selected by the algorithm in this stage due to its high values. The algorithm keeps running until the robot has explored every unexplored area.

In Figure 8 and Figure 9, the exploration process is compared in two different surroundings, and the robot’s path is influenced by three different algorithms used in each example. The cost function-based frontier selection method [40], which has more phases than the other two algorithms, is shown in Figure 8b. Since the number of steps in this method matches the number of objective points, it is clear how simple the robot’s navigation is. Conversely, the Rmap algorithm [37] necessitates a longer exploration period and trip distance.

It is clear from looking at Figure 8a and Figure 9a that, in comparison to the other two algorithms, our suggested technique exhibits more effective exploration. The recommended method drastically cuts down on the amount of time and travel distance needed for a comprehensive inquiry [38].

To visually demonstrate the traversal outcomes of the proposed algorithm compared to Rmap and frontier selection based on cost functions, Figure 9 shows the area scanned by each algorithm in small environments. The coverage maps indicate that the proposed algorithm achieves maximal coverage, minimizing gaps and reducing redundant traversal paths. In this environment, the coverage obtained by our algorithm is comparable to Rmap and cost function-based frontier selection. These outcomes highlight the adaptability and effectiveness of the proposed method across various environmental configurations.

Additionally, we conducted experiments on the proposed strategy in a larger simulated environment of 26 m × 20.5 m, as depicted in Figure 5c. The exploration process and the navigation trajectories of the robot using three different path-planning algorithms are illustrated in Figure 10. In Figure 10a,b, the blue lines indicate the robot’s path trajectories, while the circled points represent the goal points generated during the exploration. The trajectory followed by Rmap is distinct from the proposed method and the cost function-based frontier algorithms, as depicted in Figure 10c. Rmap’s trajectory is represented using rectangles.

The Rmap technique [37], which has an incorporated loop closure mechanism within its data structure, is used for map and data structure construction, taking advantage of its remarkable memory efficiency. Additionally, to evaluate performance, a comparison between the memory-efficient approach and the Rmap path-planning algorithm was made in a 13 m × 14.5 m simulated area [37]. A grid map with 75,400 cells and a 5 cm resolution was used for the assessment.

The Rmap representation of the tested environment is shown in Figure 11b. The findings show that while the grid mapping approach used 75,400 cells to describe the full region shown in Figure 11b, Rmap only produced 17 rectangles. Compared to the grid mapping technique, this Rmap representation approach greatly lowers the number of cells needed, improving memory efficiency.

Furthermore, we experimented with the novel path-planning approach in a large simulated area, as shown in Figure 5c. To illustrate the performance differences among the algorithms across various metrics, we used 3D bar charts as shown in Figure 12, Figure 13 and Figure 14. This format was chosen because it allows for the visualization of multiple comparative dimensions—such as algorithm type, environment type, and specific performance metrics (e.g., exploration time, path length, and turning points) within a single chart. The 3D perspective facilitates a clear comparison of how each algorithm performs under different environmental conditions and across multiple evaluation criteria. By presenting the data in this format, we aim to provide readers with a more comprehensive view of the interplay between these variables, enhancing the interpretability of our results. Significant differences between the recently suggested methodology and earlier approaches are clarified by comparing the exploration path distance and step count. It is crucial to stress that any strategy being considered demonstrates the potential to attain thorough exploitation coverage in a variety of environments.

In our previous research [37], we proposed an efficient mapping scheme that ensured 100% coverage of unknown areas while demonstrating excellent memory efficiency. However, the navigation policy of the robot required it to strictly follow the borders of rectangles to explore new environmental data. While this approach guaranteed complete coverage, it resulted in prolonged exploration times and excessive path distances, limiting the efficiency of the method.

The TAD algorithm was developed specifically to address these limitations. By introducing Trapezoid, Adjacent, and Distance parameters, the TAD algorithm optimizes the exploration process, significantly reducing exploration time and path distance while maintaining robust coverage performance. The metrics we initially selected for turning points, path distance, and exploration time were chosen to highlight the improvements made by the TAD algorithm compared to the previous method.

To provide a more comprehensive evaluation, we have incorporated additional metrics. Computational complexity over time—the computational efficiency of the TAD algorithm was evaluated by measuring the average processing time per iteration, including rectangle generation, adjacency updates, and path calculations. Results demonstrate low computational overhead, with average processing times of 12 ms in sparse environments and 65 ms in dense environments, validating its scalability and efficiency.

Accuracy of exploration—while our previous method achieved 100% coverage, the TAD algorithm maintains this high level of coverage while reducing redundant revisits and improving overall efficiency. The coverage percentage remained at 100% in all types of environments.

These additional metrics complement the original ones and provide a more holistic evaluation of the TAD algorithm. They validate its ability to address the limitations of the previous method, offering improved exploration efficiency, and computational scalability all while maintaining robust coverage performance.

By analyzing experimental data, we explore the key metrics in three different settings, including the number of exploration steps, turns, exploration distance, and time spent exploring. The robot’s journey length and time spent are correlated with the effectiveness of the suggested path-planning algorithm. The traversal distance accurately represents the real ground the robot covers throughout the exploratory excursion, while a lower step count indicates a more efficient navigation procedure with fewer target locations.

Figure 12 compares the turning points required by three path-planning algorithms across three types of environments: wide, cyclic small, and non-cyclic small. In the wide environment, the proposed method has the lowest number of turning points (44), closely followed by Frontier-based [40] path planning (49), indicating their efficiency in open spaces, whereas Rmap [37] has significantly more turns (168), showing inefficiency in optimizing paths in such settings. In the cyclic small environment, our method again requires the fewest turns (6), followed by frontier-based path planning (8), while Rmap shows a notable increase with 33 turns, reflecting challenges in navigating cyclic structures efficiently. In the non-cyclic small environment, the proposed and Frontier-based path planning maintain low turning points (10 and 11, respectively), whereas Rmap again has a higher count (39), suggesting reduced adaptability in constrained spaces. Overall, the new method consistently demonstrates the most efficient path navigation across different environments, followed closely by Frontier-based path planning, while Rmap exhibits higher turning points, indicating less efficient traversal.

The comparison analysis presented in Figure 13 compares the total path distances traveled by the three algorithms, the proposed method, frontier-based path planning [40], and Rmap [37] in three types of environments: wide, cyclic small, and non-cyclic small environments. In the wide environment, the proposed method shows the shortest path distance (231), followed by frontier-based path planning (269), while Rmap records a significantly higher path distance (451). This suggests that the proposed method is the most efficient in reducing path length in open spaces, with Rmap performing poorly in optimizing the path. In the cyclic small environment, the proposed method again achieves the shortest distance (36), with frontier-based path planning at 52 and Rmap at 109, indicating that the proposed method is more effective in minimizing path redundancy in cyclic environments. Finally, in the non-cyclic small environment, the proposed method records a path distance of 41, frontier-based path planning shows a slightly longer distance of 53, and Rmap has the longest path distance of 134. This trend demonstrates that the proposed method consistently achieves the shortest path across different environment types, indicating its adaptability and efficiency in path planning. Frontier-based path planning performs moderately well but is less efficient than the proposed method, while Rmap consistently shows the longest path distances, suggesting it is less effective in optimizing path length in diverse environments.

Additionally, Figure 14 compares the time taken by the three algorithms, the proposed method, frontier-based path planning [40], and Rmap [37] in different environments: wide, cyclic small, and non-cyclic small. In the wide environment, the proposed method has the shortest exploration time (629), followed by frontier-based path planning (726), while Rmap [37] has a considerably longer time (1491), indicating that the proposed method is more efficient in large, open spaces, while Rmap is significantly slower. In the cyclic small environment, the proposed method again demonstrates the shortest time (103), with Frontier-based path planning taking longer (182) and Rmap taking the longest time (350). This indicates that the proposed method is well-suited to cyclic layouts, efficiently navigating with minimal time. In the non-cyclic small environment, the proposed method continues to show the fastest exploration (51), followed by frontier-based path planning (139), with Rmap taking the longest time (403). Across all environments, the proposed method consistently achieves the lowest exploration time, demonstrating its adaptability and speed. Frontier-based path planning performs moderately well, but is less efficient than the proposed method, while Rmap consistently has the highest exploration time, highlighting its inefficiency across diverse settings.

To further validate the effectiveness of the proposed algorithm, we conducted an additional comparison with a recently developed path-planning method, such as the signed distance field (SDF) based algorithm by Wang et al. [44]. The results of the comparison are summarized in Table 5. As shown, the proposed algorithm demonstrates superior performance in terms of exploration time and traversal efficiency. Specifically, our algorithm achieved a 39% reduction in path distance and a 42% improvement in exploration time compared to the latest frontier-based method. These results underscore the adaptability and efficiency gains achieved by incorporating Trapezoid, Adjacent, and Distance parameters.

Furthermore, for a consistent evaluation of the proposed algorithm, Rmap, and frontier selection based on cost functions, we standardized critical parameter settings across all tests. Specifically, we maintained a turn angle threshold of 45 degrees, a traversal speed of 0.2 m/s, and a path smoothing factor of 0.5 across all experiments. These standardized parameters were chosen as default values to allow a fair comparison of performance metrics such as path distance, exploration time, and number of turnings. By applying identical conditions to each algorithm, we ensured that observed differences in performance reflect the intrinsic advantages of each algorithm rather than variations in testing conditions. This approach strengthens the reliability and validity of the comparative analysis, allowing a direct evaluation of the proposed algorithm’s improvements. To understand the impact of these parameters, we conducted additional experiments. The results are summarized in Table 6:

To evaluate the performance differences between the proposed algorithm, Rmap, and frontier selection based on cost functions, we conducted statistical tests on exploration time and path distance across both small and large environments. Given our expanded sample size of 50 trials per algorithm per environment type, we used the t-test for normally distributed data and the Mann–Whitney U test for data that did not meet normality assumptions. A significance level of p < 0.05 was set for all tests to establish statistical reliability.

In the small environment, the proposed algorithm showed a mean exploration time of 320 s and a mean path distance of 180 m, significantly outperforming both Rmap (mean exploration time of 390 s, path distance of 220 m) and frontier selection based on cost functions (mean exploration time of 360 s, path distance of 200 m), with p-values below the 0.05 threshold for each comparison. Similarly, in the large environment, the proposed algorithm maintained its advantage with a mean exploration time of 700 s and path distance of 430 m, compared to Rmap (800 s, 480 m) and frontier selection (750 s, 460 m), with p < 0.05 confirming statistically significant differences.

These results indicate that the proposed algorithm consistently achieves shorter exploration times and path distances than the other methods, providing statistically supported evidence of its efficiency across varying environment sizes. The results are presented in Table 7.

In our study, we conducted 50 trials per algorithm per environment type to ensure a statistically robust evaluation of performance. While we acknowledge that it is challenging to account for all possible scenarios, we believe that this sample size provides a reasonable balance between experimental feasibility and capturing the algorithm’s true performance differences.

To strengthen the reliability of our results, we employed the following measures:

Diverse environment types—we carefully designed the test environments to include a wide range of scenarios, including sparse, dense, and dynamic obstacle configurations, to represent a broad spectrum of real-world conditions.

Statistical analysis—for each metric (e.g., exploration time, path distance, and coverage), we calculated mean values and standard deviations across the 50 trials to quantify variability. Additionally, statistical significance was assessed using t-tests and confidence intervals to compare the performance of the algorithms.

Consistency of results—across the 50 trials, the TAD algorithm consistently outperformed the benchmark methods, with low variance in metrics such as path distance and exploration time. This consistency indicates that our sample size is sufficient to demonstrate meaningful differences in performance.

Future work considerations—while our current evaluation provides robust evidence of the TAD algorithm’s advantages, we recognize that additional trials in more diverse environments could further enhance confidence in its generalizability. Expanding the dataset to include more trials and real-world conditions is a potential avenue for future work. We are confident that the selected sample size, combined with the diversity of test environments and the statistical analyses performed, provides a reliable assessment of the TAD algorithm’s performance.

To provide a more comprehensive evaluation of our proposed method, we included an additional test scenario in a wide indoor environment. This environment ranges from 20.5 m to 25.5 m, offering ample space with minimal obstacles, which challenges the algorithms in a controlled, spacious indoor setting. To validate the effectiveness of our proposed method, we conducted a comprehensive comparative analysis with our previous Rmap algorithm, and the cost function-based algorithm proposed by Gomez. The comparison was based on key performance metrics such as the number of turning points, traversal path distance, and traversal time. The proposed algorithm demonstrated superior performance with significantly fewer turning points (44), shorter path distance (231 m), and reduced traversal time (629 s).

The Rmap algorithm showed higher turning points (168), longer path distance (451 m), and longer traversal time (1490 s), indicating less efficiency.

The cost function algorithm performed better than Rmap but was still inferior to the proposed algorithm, with 49 turning points, 269 m path distance, and 726 s traversal time.

While the Rmap algorithm attains maximum coverage area, the new algorithm achieves a coverage area on par with the comparative algorithms. Salient attributes of the algorithm encompass the discerning selection of optimal frontiers based on iteratively calculated inner frontiers. This strategic approach prevents the inadvertent selection of non-informative areas. Additionally, the algorithm adeptly minimizes turning points, thereby reducing exploration time and traversal distance. This nuanced analysis contributes to the broader discourse on the efficiency and adaptability of path-planning algorithms, drawing inspiration from a diverse array of methodologies explored in the literature review.

To assess the computational overhead of the proposed algorithm, we analyzed the processing time and resource utilization required for frontier detection, parameter computation, and path-planning operations in comparison to Rmap and frontier selection based on cost functions. The proposed algorithm’s multi-parameter frontier evaluation approach (involving distance, adjacent, and trapezoid parameters) requires slightly higher initial computational resources due to the calculation of three parameters per frontier. However, once these parameters are computed, the algorithm reduces redundant path traversal, leading to overall computational efficiency during extended exploration tasks.

In tests conducted on environments of varying sizes, the proposed algorithm showed approximately 10% higher computational overhead during the initial frontier evaluation phase compared to Rmap, which utilizes fewer parameters. However, this initial overhead was offset by the decreased traversal time and reduced redundant paths, particularly in larger environments. In contrast, the cost function-based frontier selection method required more frequent recalculations to adapt to environmental changes, resulting in a 15% increase in computational demand compared to our algorithm. These findings suggest that, while the proposed algorithm incurs a modest increase in initial computational cost, it remains computationally efficient in long-term exploration tasks due to its optimized path planning, especially in complex and large-scale environments.

The proposed algorithm incorporates several strategies to handle environments with irregular obstacle layouts and to minimize computational overhead, ensuring practical applicability for real-time exploration tasks:

Adaptive parameter adjustments: The algorithm dynamically adjusts the frontier score based on environmental complexity. For environments with irregular layouts, higher values are assigned to the adjacent and trapezoid parameters to prioritize connectivity and efficient path planning through narrow or cluttered regions.

Frontier clustering: To reduce the computational burden, the algorithm groups spatially close frontiers into clusters and evaluates them collectively. By treating clusters as a single unit during exploration, the algorithm limits the number of individual frontier evaluations, ensuring efficient processing while maintaining exploration accuracy.

Local exploration zones: The environment is segmented into smaller, manageable zones, within which the robot performs localized exploration. This hierarchical segmentation minimizes global computations and focuses resources on the most relevant sections of the environment.

Selective frontier filtering: Frontiers that are unlikely to contribute significantly to exploration progress, such as those with a Trapezoid parameter t_n = −1, are filtered out early in the evaluation process. This selective filtering ensures that computational resources are allocated to promising frontiers, enhancing overall efficiency.

Incremental path updates: Instead of recalculating paths from scratch, the algorithm updates only the affected segments of the path as the robot moves. This incremental approach minimizes redundant computations, ensuring the algorithm remains responsive to dynamic changes in the environment.

These strategies collectively address the challenges posed by irregular obstacle layouts, ensuring smooth navigation and efficient use of computational resources. By integrating these mitigation methods, the proposed algorithm enhances its robustness and scalability, making it suitable for real-time autonomous exploration in diverse and complex environments.

4. Conclusions

In this paper, we presented a novel path-planning algorithm designed to optimize traversal efficiency in various indoor environments. Through extensive comparative analysis with state-of-the-art methods, our proposed algorithm demonstrated significant improvements in reducing the number of turning points, path distance, and traversal time. The key findings from our experiments indicate that our algorithm consistently outperforms existing methods, particularly in wide indoor spaces where it achieved a reduction of approximately 74% in turning points, 49% in path distance, and 58% in traversal time compared to the Rmap algorithm. These results highlight the potential of our approach to enhance navigation efficiency in real-world applications. Moreover, our analysis identified the importance of parameter settings on the algorithm’s performance, providing a roadmap for further optimization and customization based on specific use-case requirements. Future work will involve testing the algorithm on a real mobile robot to validate its practical applicability and refine its performance in dynamic and unstructured environments.

Future Research Directions:

• Real-World Testing: Implementing and testing the algorithm on a real mobile robot to validate its practical performance and adaptability.

• Obstacle avoidance: include the obstacle avoidance algorithm to enhance the method.

• Dynamic Environments: Extending the algorithm to handle dynamic and unpredictable environments, enhancing its robustness and reliability.

• Advanced Sensor Integration: Exploring the integration of advanced sensor technologies to improve data accuracy and path-planning efficiency.

• Multi-Robot Coordination: Investigating the application of the algorithm in multi-robot systems for coordinated path planning and task execution.

In conclusion, our proposed algorithm offers a robust and efficient solution for path planning in indoor environments, paving the way for more effective and reliable autonomous navigation systems. We are committed to advancing this research by integrating real-world testing and further enhancing the algorithm’s adaptability and resilience in diverse operational scenarios.

Author Contributions

Conceptualization, A.B. and A.J.C.; methodology, A.B.; software, A.J.C.; validation, A.B., A.J.C.; formal analysis, A.J.C.; investigation, A.B.; resources, H.S.J.; data curation, A.B.; writing—original draft preparation, A.B.; writing—review and editing, A.J.C. and H.S.J.; visualization, A.B.; supervision, H.S.J.; project administration, H.S.J.; funding acquisition, H.S.J. All authors have read and agreed to the published version of the manuscript.

Data Availability Statement

Data are contained within the article.

Conflicts of Interest

The authors declare no conflicts of interest.

Footnotes

Disclaimer/Publisher’s Note: The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of MDPI and/or the editor(s). MDPI and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.

Figures and Tables

Table 1

Detail information of parameters’ values according to Figure 4.

Frontier	Distance Parameter		Adjacent Parameter		Trapezoid Parameter
Fn	dn	Value	an	Value	tn	Value
F 1	d1 = 4	3	a1 = 4	1	t1 = 4	1
F 2	d2 = 3.5	2	a2 = 3.5	2	t2 = 3.5	−1
F 3	d3 = 1	1	a3 = 1	3	t3 = 1	0

Table 2

Robot’s equipment.

Equipment	Parameter
Long-range distance of sensor	5 m
Short range distance of sensor	0.5 m
Degree of LIDAR	360
Number of sensor’s ray	720
Minimal size of frontier	0.35 m

Table 3

The computation results of all parameters for each detected frontier in the first round.

		Frontier 1	Frontier 2
Trapezoid parameter value		1	0
Adjacent parameter value		2	2
Distance parameter value		2	1
TOTAL		5	3

Table 4

The computation results of all parameters for each detected frontier in the second round.

		Frontier 1	Frontier 2
Trapezoid parameter value		0	1
Adjacent parameter value		1	2
Distance parameter value		2	1
TOTAL		3	4

Table 5

Comparisons with SDF algorithm.

Algorithm	Exploration Time (s)	Path Distance	Goal Number	Coverage
Proposed algorithm	280	53	16	100%
SDF algorithm	420	87	25	92%

Table 6

Comparisons Using Variety Parameters.

Algorithm	Parameter	Value	Turnings	Path Distance	Exploration Time (s)
Proposed Algorithm	Turning Angle Threshold	30 degrees	60	250 m	700
		60 degrees	30	220 m	600
	Traversal Speed	0.1 m/s	44	231 m	1258
		0.4 m/s	44	231 m	314
	Path Smoothing Factor	0.3	50	220 m	650
		0.7	40	240 m	610
Rmap [37]	Turning Angle Threshold	30 degrees	70	270 m	750
		60 degrees	35	240 m	620
	Traversal Speed	0.1 m/s	55	250 m	1300
		0.4 m/s	55	250 m	340
	Path Smoothing Factor	0.3	60	240 m	680
		0.7	45	260 m	640
Frontier Selection (Cost Funcs) [40]	Turning Angle Threshold	30 degrees	65	260 m	720
		60 degrees	32	230 m	610
	Traversal Speed	0.1 m/s	50	240 m	1260
		0.4 m/s	50	240 m	330
	Path Smoothing Factor	0.3	55	230 m	670
		0.7	43	250 m	620

Table 7

Statistical significance analyses.

Algorithm	Sample Size	Environment Type	Mean Exploration Time (s)	Mean Path Distance (m)	p-Value (Exploration Time)	p-Value (Path Distance)
Proposed Algorithm	50	Small	320	180	<0.05	<0.05
		Large	700	430
Rmap [37]	50	Small	390	220
		Large	800	480
Frontier Selection (Cost Functions) [40]	50	Small	360	200
		Large	750	460

References

1. Abror, B.; Azam, M.; Oh, H.J.; Lee, J.D.; Kwon, Y.A.; Jeon, H.S. Internal and external frontier-based algorithm for autonomous mobile robot exploration in unknown environment. Electron. Lett.; 2021; 57, pp. 942-944. [DOI: https://dx.doi.org/10.1049/ell2.12316]

2. Majeed, A.; Hwang, S.O. A Multi-Objective Coverage Path Planning Algorithm for UAVs to Cover Spatially Distributed Regions in Urban Environments. Aerospace; 2021; 8, 343. [DOI: https://dx.doi.org/10.3390/aerospace8110343]

3. Xu, J.; Park, K.-S. Kinematic performance-based path planning for cable-driven parallel robots using modified adaptive RRT*. Microsyst. Technol.; 2022; 28, pp. 2325-2336. [DOI: https://dx.doi.org/10.1007/s00542-022-05319-3]

4. Xu, J.; Kim, B.-G.; Park, K.-S. A collaborative path planning method for mobile cable-driven parallel robots in a constrained environment with considering kinematic stability. Complex Intell. Syst.; 2023; 9, pp. 4857-4868. [DOI: https://dx.doi.org/10.1007/s40747-022-00915-2]

5. Jung, S.; Kim, Y.-J. Extremum Seeking-Based Radio Signal Strength Optimization Algorithm for Hoverable UAV Path Planning. Electronics; 2024; 13, 4064. [DOI: https://dx.doi.org/10.3390/electronics13204064]

6. Xu, J.; Kim, B.-G.; Lu, Y.; Park, K.-S. Optimal sampling-based path planning for mobile cable-driven parallel robots in highly constrained environment. Complex Intell. Syst.; 2023; 9, pp. 6985-6998. [DOI: https://dx.doi.org/10.1007/s40747-023-01114-3]

7. Majeed, A.; Hwang, S.O. Path Planning Method for UAVs Based on Constrained Polygonal Space and an Extremely Sparse Waypoint Graph. Appl. Sci.; 2021; 11, 5340. [DOI: https://dx.doi.org/10.3390/app11125340]

8. Stout, M.S.; Brisson, G.F.; Di Bernardo, E.; Pirjanian, P.; Goel, D.; Case, J.P.; Dooley, M. Methods and Systems for Complete Coverage of a Surface by an Autonomous Robot. U.S. Patent; No. 9,026,302, 5 May 2015.

9. Xu, J.; Park, K.-S. Moving obstacle avoidance for cable-driven parallel robots using improved RRT. Microsyst. Technol.; 2021; 27, pp. 2281-2292. [DOI: https://dx.doi.org/10.1007/s00542-020-05100-4]

10. Li, X.; Yang, Q.; Wu, H.; Tan, S.; He, Q.; Wang, N.; Yang, X. Joints Trajectory Planning of Robot Based on Slime Mould Whale Optimization Algorithm. Algorithms; 2022; 15, 363. [DOI: https://dx.doi.org/10.3390/a15100363]

11. Montiel, O.; Sepúlveda, R.; Orozco-Rosas, U. Optimal Path Planning Generation for Mobile Robots using Parallel Evolutionary Artificial Potential Field. J. Intell. Robot. Syst.; 2015; 79, pp. 237-257. [DOI: https://dx.doi.org/10.1007/s10846-014-0124-8]

12. Šeda, M. Roadmap methods vs. cell decomposition in robot motion planning. Proceedings of the 6th WSEAS International Conference on Signal Processing, Robotics and Automation; Corfu Island, Greece, 16–19 February 2017; World Scientific and Engineering Academy and Society (WSEAS): Stevens Point, WI, USA, 2017; pp. 127-132.

13. Luo, C.; Gao, J.; Li, X.; Mo, H.; Jiang, Q. Sensor-based Autonomous Robot Navigation Under Unknown Environments with Grid Map Representation. Proceedings of the 2014 IEEE Symposium on Swarm Intelligence (SIS); Orlando, FL, USA, 9–12 December 2014; [DOI: https://dx.doi.org/10.1109/SIS.2014.7011782]

14. Mac, T.T.; Copot, C.; Tran, D.T.; De Keyser, R. Heuristic approaches in robot path planning: A survey. Robot. Auton. Syst.; 2016; 86, pp. 13-28. [DOI: https://dx.doi.org/10.1016/j.robot.2016.08.001]

15. Xu, J.; Qian, C.; Park, J.-W.; Park, K.-S. Adaptive Sampling-Based Moving Obstacle Avoidance for Cable-Driven Parallel Robots. IEEE/ASME Trans. Mechatron.; 2022; 27, pp. 4983-4993. [DOI: https://dx.doi.org/10.1109/TMECH.2022.3169812]

16. Xu, J.; Kim, B.-G.; Feng, X.; Park, K.-S. Online motion planning of mobile cable-driven parallel robots for autonomous navigation in uncertain environments. Complex Intell. Syst.; 2024; 10, pp. 397-412. [DOI: https://dx.doi.org/10.1007/s40747-023-01169-2]

17. Khan, M.N.; Rahman, H.U.; Faisal, M.; Khan, F.; Ahmad, S. An IoT-Enabled Information System for Smart Navigation in Museums. Sensors; 2022; 22, 312. [DOI: https://dx.doi.org/10.3390/s22010312] [PubMed: https://www.ncbi.nlm.nih.gov/pubmed/35009853]

18. Nielsen, L.D.; Sung, I.; Nielsen, P. Convex Decomposition for a Coverage Path Planning for Autonomous Vehicles: Interior Extension of Edges. Sensors; 2019; 19, 4165. [DOI: https://dx.doi.org/10.3390/s19194165]

19. Gao, S.; Ding, Y.; Chen, B.M. A Frontier-Based Coverage Path Planning Algorithm for Robot Exploration in Unknown Environment. Proceedings of the 2020 39th Chinese Control Conference (CCC); Shenyang, China, 27–29 July 2020; pp. 3920-3925. [DOI: https://dx.doi.org/10.23919/CCC50068.2020.9188784]

20. Fang, B.; Ding, J.; Wang, Z. Autonomous robotic exploration based on frontier point optimization and multistep path planning. IEEE Access; 2019; 7, pp. 46104-46113. [DOI: https://dx.doi.org/10.1109/ACCESS.2019.2909307]

21. Fan, J.; Zhang, X.; Zou, Y. Hierarchical path planner for unknown space exploration using reinforcement learning-based intelligent frontier selection. Expert Syst. Appl.; 2023; 230, 120630. [DOI: https://dx.doi.org/10.1016/j.eswa.2023.120630]

22. Horvátha, E.; Claudiu, P.; Radu-Emil, P. Robot Coverage Path Planning Based on Iterative Structured Orientation. Acta Polytech. Hung.; 2018; 15, pp. 231-249. [DOI: https://dx.doi.org/10.12700/APH.15.1.2018.2.12]

23. Van Pham, H.; Moore, P. Robot Coverage Path Planning under Uncertainty Using Knowledge Inference and Hedge Algebras. Machines; 2018; 6, 46. [DOI: https://dx.doi.org/10.3390/machines6040046]

24. Groves, K.; Hernandez, E.; West, A.; Wright, T.; Lennox, B. Robotic Exploration of an Unknown Nuclear Environment Using Radiation Informed Autonomous Navigation. Robotics; 2021; 10, 78. [DOI: https://dx.doi.org/10.3390/robotics10020078]

25. Inotsume, H.; Kubota, T.; Wettergreen, D. Robust Path Planning for Slope Traversing Under Uncertainty in Slip Prediction. IEEE Robot. Autom. Lett.; 2020; 5, pp. 3390-3397. [DOI: https://dx.doi.org/10.1109/LRA.2020.2975756]

26. Bergman, K.; Ljungqvist, O.; Axehill, D. Improved Path Planning by Tightly Combining Lattice-Based Path Planning and Optimal Control. IEEE Trans. Intell. Veh.; 2021; 6, pp. 57-66. [DOI: https://dx.doi.org/10.1109/TIV.2020.2991951]

27. Peng, Y.; Wang, Y.; Hu, F.; He, M.; Mao, Z.; Huang, X.; Ding, J. Predictive Modeling of Flexible EHD Pumps using Kolmogorov-Arnold Networks. arXiv; 2024; arXiv: 2405.07488[DOI: https://dx.doi.org/10.1016/j.birob.2024.100184]

28. Peng, Y.; Yang, X.; Li, D.; Ma, Z.; Liu, Z.; Bai, X.; Mao, Z. Predicting flow status of a flexible rectifier using cognitive computing. Expert Syst. Appl.; 2025; 264, 125878. [DOI: https://dx.doi.org/10.1016/j.eswa.2024.125878]

29. Liu, S.; Li, S.; Pang, L.; Hu, J.; Chen, H.; Zhang, X. Autonomous Exploration and Map Construction of a Mobile Robot Based on the TGHM Algorithm. Sensors; 2020; 20, 490. [PubMed: https://www.ncbi.nlm.nih.gov/pubmed/31952240]PMC7013441[DOI: https://dx.doi.org/10.3390/s20020490]

30. Zhang, J.; Wang, W.; Qi, X.; Liao, Z. Social and Robust Navigation for Indoor Robots Based on Object Semantic Grid and Topological Map. Appl. Sci.; 2020; 10, 8991. [DOI: https://dx.doi.org/10.3390/app10248991]

31. Shi, L.; Jiang, W.; Luo, Z.; Yang, L.; Wang, Y. Enhancing Adaptability: Hierarchical Frontier-Based Path Planning for Navigation in Challenging Environments. IEEE Robot. Autom. Lett.; 2024; 9, pp. 8611-8618. [DOI: https://dx.doi.org/10.1109/LRA.2024.3448137]

32. Senarathne, P.G.C.N.; Wang, D. Incremental algorithms for Safe and Reachable Frontier Detection for robot exploration. Robot. Auton. Syst.; 2015; 72, pp. 189-206. [DOI: https://dx.doi.org/10.1016/j.robot.2015.05.009]

33. Lu, L.; Redondo, C.; Campoy, P. Optimal Frontier-Based Autonomous Exploration in Unconstructed Environment Using RGB-D Sensor. Sensors; 2020; 20, 6507. [DOI: https://dx.doi.org/10.3390/s20226507]

34. Jiang, L.; Zhao, P.; Dong, W.; Li, J.; Ai, M.; Wu, X.; Hu, Q. An Eight-Direction Scanning Detection Algorithm for the Mapping Robot Pathfinding in Unknown Indoor Environment. Sensors; 2018; 18, 4254. [DOI: https://dx.doi.org/10.3390/s18124254]

35. Ullah, I.; Adhikari, D.; Khan, H.; Anwar, M.S.; Ahmad, S.; Bai, X. Mobile robot localization: Current challenges and future prospective. Comput. Sci. Rev.; 2024; 53, 100651. [DOI: https://dx.doi.org/10.1016/j.cosrev.2024.100651]

36. Ullah, I.; Adhikari, D.; Khan, H.; Ahmad, S.; Esposito, C.; Choi, C. Optimizing Mobile Robot Localization: Drones-Enhanced Sensor Fusion with Innovative Wireless Communication. Proceedings of the IEEE INFOCOM 2024—IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS); Vancouver, BC, Canada, 20–23 May 2024; pp. 1-6. [DOI: https://dx.doi.org/10.1109/INFOCOMWKSHPS61880.2024.10620739]

37. Lee, C.W.; Lee, J.D.; Ahn, J.; Oh, H.J.; Park, J.K.; Jeon, H.S. A Low Overhead Mapping Scheme for Exploration and Representation in the Unknown Area. Appl. Sci.; 2019; 9, 3089. [DOI: https://dx.doi.org/10.3390/app9153089]

38. Buriboev, A.; Kang, H.K.; Lee, J.D.; Oh, R.; Jeon, H.S. Rmap+: Autonomous Path Planning for Exploration of Mobile Robot Based on Inner Pair of Outer Frontiers. KSII Trans. Internet Inf. Syst.; 2022; 16, pp. 3373-3389. [DOI: https://dx.doi.org/10.3837/tiis.2022.10.009]

39. Yamauchi, B. A frontier-based approach for autonomous exploration. Proceedings of the 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation (CIRA’97); Monterey, CA, USA, 10–11 July 1997; 146.

40. Gomez, C.; Hernandez, A.C.; Barber, R. Topological Frontier-Based Exploration and Map-Building Using Semantic Information. Sensors; 2019; 19, 4595. [DOI: https://dx.doi.org/10.3390/s19204595]

41. Yoo, H.J.; Kim, E.H.; Lee, H. Mobile robots for isolation-room hospital settings: A scenario-based preliminary study. Comput. Struct. Biotechnol. J.; 2024; 24, pp. 237-246. [DOI: https://dx.doi.org/10.1016/j.csbj.2024.03.001]

42. Hwang, S.; Lee, K.; Jeon, H.; Kum, D. Autonomous Vehicle Cut-In Algorithm for Lane-Merging Scenarios via Policy-Based Reinforcement Learning Nested Within Finite-State Machine. IEEE Trans. Intell. Transp. Syst.; 2022; 23, pp. 17594-17606. [DOI: https://dx.doi.org/10.1109/TITS.2022.3153848]

43. Abbasi, R.; Bashir, A.K.; Alyamani, H.J.; Amin, F.; Doh, J.; Chen, J. Lidar Point Cloud Compression, Processing and Learning for Autonomous Driving. IEEE Trans. Intell. Transp. Syst.; 2022; 24, pp. 962-979. [DOI: https://dx.doi.org/10.1109/TITS.2022.3167957]

44. Wang, H.; Lin, Y.; Zhang, W.; Ye, W.; Zhang, M.; Dong, X. Safe Autonomous Exploration and Adaptive Path Planning Strategy Using Signed Distance Field. IEEE Access; 2023; 11, pp. 144663-144675. [DOI: https://dx.doi.org/10.1109/ACCESS.2023.3344218]