2. Related works

In recent years, the use of reconfigurable robots in constrained and obstacle-cluttered environments has gained traction as they provide rich sets of morphologies by reconfiguring their bases and can navigate tight spaces. Reconfigurable robots offer tremendous potential in advancing performance by assuming multiple morphologies concerning their environment. Because of their multifunctionality and adaptability, self-reconfigurable robots have been progressively used in many applications like space and pavement cleaning [Reference Yi, Le, Hayat, Borusu, Mohan, Nhan and Kandasamy10], ship cleaning [Reference Muthugala, Le, Cruz, Elara, Veerajagadheswar and Kumar11, Reference Prabakaran, Le, Kyaw, Mohan, Kandasamy, Nguyen and Kannan12], floor, and stairace cleaning [Reference Le, Kyaw, Mohan, Swe, Rajendran, Boopathi and Nhan13].

Reconfigurable robots were introduced in the late 1980s and have been extensively studied. Reconfigurable robots are classified into three major categories; namely, intra-reconfigurable [Reference Cheng, Mohan, Nhan and Le14,15], inter-reconfigurable [Reference Le, Hayat, Elara, Nhan and Prathap15], and nested-reconfigurable [Reference Le, Prabakaran, Sivanantham and Mohan16] robots. Intra-reconfiguration is where an individual robot can change its morphology from one form to another. Some examples to this end include Scorpio [Reference Tan, Mohan and Elangovan17], a bio-inspired robot capable of switching between rolling, crawling, and wall climbing forms, and RoboMods, a reconfigurable, under-actuated legged robot that could generate distinct walking patterns [Reference Nansai, Rojas, Elara and Sosa18]. Inter reconfiguration is where multiple similar robots come together to form global morphologies by undergoing assembly and disassembly processes. Some examples include Transbot [Reference Vo, Le, Ta, Tran, Van Duc, Vu and Nhan19], Panthera [Reference Yi, Wan, Le, Abdullah Aamir Hayat and Mohan20, Reference Do, Le, Yi, Hoong, Tran, Van Duc, Vu, Weeger and Mohan21], hTrihex [Reference Le, Vo, Dat, Vu and Elara22], hTrihex [Reference Le, Parween, Mohan, Nhan and Enjikalayil23], and Stetro [Reference Prabakaran, Le, Kyaw, Kandasamy, Paing and Mohan24, Reference Le, Pamela, Hayat, Nair, Kyaw, Vu, Vo and Elara25]. The third category is nested robots, which are capable of performing both inter and intra- reconfigurations. One such example is a hinged tetro robot that can change its morphology on its own and can form global morphology by attaching and detaching with a team of other hinged-tetro robots [Reference Kee, Rojas, Elara and Sosa26]. These robots have the capacity to change themselves into various shapes, subsequently productively navigating through compelled areas, which may not be workable for regular fixed-shape robots. However, an efficient path planning by navigation framework with collision-free for reconfigurable robots in higher configurable state dimensions is computationally more expensive than conventional fixed-shaped robots.

Robot navigation in complex environments poses research and development challenges. Simultaneous localization and mapping (SLAM) [Reference Khairuddin, Talib and Haron27] is a significant open problem in mobile robotics. To move precisely, a mobile robot must have an accurate environment map; however, to build an accurate map, the mobile robot sensing locations must be known. In 1990, Smith R., Self M., and Cheeseman P. first proposed using the Kalman filter, extended Kalman filter (EKF) [Reference Smith, Self and Cheeseman28] for incrementally estimating the posterior distribution over robot pose along with the positions of the landmarks. Starting from the unknown location of the unknown environment, the robot locates its position and attitude through repeated observation of environmental features in the movement process. It then builds an incremental map of the surrounding environment according to its position to achieve simultaneous positioning and map purposes. Sensor fusions can use an inertial sensor such as IMU to assist 2D SLAM [Reference Li, Wang, Zhuang and Yan29] to improve the mapping accuracy by compensating for the drifting of the wheel encoder. Further, it incorporates the time dimension into the mapping process to enable a robot to maintain an accurate map while operating in dynamic environments.

Global path planners in robot navigation determine the possible path to reach the goal position. The choice of a global path-planning algorithm depends on the application of the robot. For example, in the case of area coverage robots, grid-based graph search methods for complete coverage path planning have been demonstrated in ref. [Reference Lee, Baek, Choi and Oh30], where they split the map into grid cells for efficient and faster navigation. Another work proposed by Le et al. [Reference Le, Prabakaran, Sivanantham and Mohan16] demonstrated the idea of adapting polyomino tiling theory with path planning on a Tetris-inspired self-reconfigurable floor cleaning robot. They further validated area coverage on the robot using A-star based zigzag planner to maximize coverage on accessible space areas. Regarding logistics transportation, obstacle avoidance and the shortest path are the most preferred criteria while adopting a path planning technique. One approach for estimating the shortest path uses the roadmap method to randomly generate n number of curves connecting the start and end points and choose the best curve as a path to the goal point. Bhattacharya et al. [Reference Bhattacharya and Gavrilova31] presented a path planning algorithm based on Voronoi diagram in the presence of polygonal obstacles in the environment. Similarly, Djikstra [Reference Skiena32] algorithm also uses the roadmap method and solves the problem by assigning cost value to each region of the grid cell map and estimating the path with minimum cost. Another approach to real-time planning on estimating the best path includes heuristic search algorithms, most popularly the A-star search algorithm [Reference Hart, Nilsson and Raphael33] to find optimal paths. The Dhouib-Matrix Shortest Path Problem (DM-SPP) is an efficient algorithm for solving shortest path problems with a time complexity of $O(n + m)$ [Reference Dhouib34]. It is particularly useful for mobile robot path planning in static grid-based environments. Two variants, DM-SPP-24 and DM-SPP-4, enhance its adaptability. DM-SPP-24 allows movement in 24 directions for greater precision, while DM-SPP-4 restricts movement to four primary directions, reducing computational complexity for real-time applications [Reference Dhouib35, Reference Dhouib36].

Sampling-based planners are categorized into multiple-query and single-query approaches. Multiple-query planners construct a roadmap—a graph of collision-free paths—allowing efficient shortest-path computation for various start-goal pairs. In contrast, single-query planners solve specific motion planning instances. Among the most widely used are probabilistic roadmaps [Reference Kavraki, Petr Svestka and Overmars37] for multiple-query scenarios and rapidly-exploring random trees (RRTs) [Reference LaValle and Kuffner38] for single-query tasks. These methods are well-suited for high-dimensional spaces, as they avoid exhaustive obstacle representation required by deterministic grid-based graph-search algorithms like Dijkstra’s algorithm [Reference Edsger and Dijkstra39] or A* [Reference Hart, Nilsson and Raphael33]. Given sufficient time, they ensure probabilistic completeness, guaranteeing a solution if one exists. However, while they generate feasible (collision-free) paths, they do not inherently optimize them.

Several extensions enhance efficiency by incorporating anytime capabilities, such as anytime motion planning with RRT* [Reference Karaman and Frazzoli40], which refines solutions incrementally while maintaining probabilistic completeness and achieving asymptotic optimality. To improve solution quality, RRT* [Reference Karaman and Frazzoli40] iteratively rewires its tree structure for asymptotic optimality. However, its uniform random sampling slows convergence, particularly in high-dimensional problems, requiring longer computation times for near-optimal solutions.

Recent research has focused on enhancing RRT*’s sampling strategies to improve convergence while preserving its theoretical optimal solution guarantees. Techniques such as sample elimination, biased sampling, graph pruning, and direct informed sampling address these limitations [Reference Gammell, Barfoot and Srinivasa9]. Informed RRT* [Reference Gammell, Barfoot and Srinivasa9] leverages direct informed sampling by initially operating as RRT* until a solution is found, then restricting sampling to an $L^2$ -informed subset of the state space containing potentially lower-cost paths accelerating convergence by directing exploration toward promising regions. BIT* [Reference Gammell, Srinivasa and Barfoot41] integrates graph search with sampling-based planning, leveraging heuristics for accelerated convergence. While it offers strong asymptotic optimality and efficiency, its requirement for precomputing the entire planning space limits applicability in dynamic environments or localized tasks.

The efficiency in addressing complex robotic motion planning challenges is a potential research topic. Shahabi et al. [Reference Shahabi, Ghariblu and Beschi42] conducted a comparative analysis of various sample-based motion planning methods applied to redundant robotic manipulators, highlighting their strengths and limitations in high-dimensional configurations, which provides critical insights for optimizing manipulator performance. Dong et al. [Reference Dong, Zhang, Wang, Li, Wang and Wang43] proposed a novel modification RRT* path planning algorithm and obstacle-crossing motion planning strategy for cable trench inspection robots, demonstrating the effectiveness of specialized algorithms in constrained environments. Furthermore, Gao et al. [Reference Gao, Li, Liu, Ge and Song44] explored path planning by sampling-based technology for multi-section continuum robots in confined multiobstacle environments, presenting strategies that enhance maneuverability in complex operational settings. These studies emphasize the growing importance of customized sampling-based methods to meet the diverse demands of modern robotic applications, particularly in challenging and reconfigurable robotic scenarios.

Using the inter-reconfiguration in cleaning and maintaining tasks where multi-robots can connect together, this paper resolves the effective shortest path planning issue by a greedy informed set called RIRRT*; the proposed shortest path planning enhances the algorithm’s convergence rate and the solution path’s qualities.

3. Design inter-reconfigurable robots system

In this section, we present a single reconfigurable unit design as in Figure 1 and a multi-robots inter-reconfigurable system for robot shapes with vertical and horizontal configurations as in Figure 2. Depending on the environment’s layouts, the inter-reconfigurable multi robots framework enables the physical expansion of the robot base footprint of system to access confined spaces. The multi-robot system is inter-reconfigurability in which the two robots in the framework operate together to fulfill the cleaning and maintenance tasks. As a result, rather than having an independent system for each robot and redundant utilization of similar equipment units on each robot, this multi-robots system requires less hardware, perception sensors, and cleaning payloads. The idea of the inter-reconfigurable system owns the advantages as follows:

• • Reduce the complexity of hardware and computation by the master and client scheme in multi-robots cooperation where the task is implemented in the master robot with advanced computational hardware component and the client agent with only manipulators and sensors.

• • Efficiency to implement the global shortest path by time and energy criteria to conduct the accessing the confined environment with complex layout setting.

Figure 1.

Design of reconfigurable robot. (a) Robot with the hardware components, (b) robot with cleaning payload.

Figure 2.

Robots shapes with vertical and horizontal configuration.

The inter-reconfigurable multi-robot system is designed with two distinct morphologies to enable adaptive locomotion and efficient operation: the H-shape configuration, representing a horizontal form, and the V-shape configuration, representing a vertical form. The V-shape configuration reduces the base footprint by half compared to the H-shape, making it suitable for navigating narrow passages (Figure 2). In this configuration, the two robots are virtually connected to maintain coordination. For most tasks, such as cleaning, the H-shape configuration is used to maximize the cleaning area. In this mode, the two robots are physically connected via passive hinges mounted at their midpoints, as shown in Figure 1a. Each robot is equipped with a mechanical base featuring additional internal space to house cleaning modules, as depicted in Figure 1b.

The locomotion of each reconfigurable robot is enabled by a holonomic drive system, utilizing a four-wheeled mecanum structure. The free-moving rollers on the mecanum wheels are positioned at a 45-degree angle along the wheel edges, providing omnidirectional movement. Thick, hard-rubber mecanum wheels are employed at the four corners of each robot to minimize slipping on surfaces. This mechanism allows the robots to move freely in the $X_{r}$ and $Y_{r}$ planes and rotate in $\theta _{r}$ orientation without requiring a center of rotation radius.

Holonomic locomotion proves especially advantageous when the two robots are virtually connected or performing shape-shifting maneuvers. This feature allows the robots to move longitudinally along their edges, turn in place, and shift positions without altering their heading orientation. During the transition between configurations, the static rotation of the robots is achieved through holonomic kinematics, with the center of instantaneous rotation set at the hinge. This facilitates seamless shape changes between the horizontal H-shape and vertical V-shape configurations, guided by the path-planning algorithm. The holonomic drive system also enhances the robot’s ability to access confined spaces and reduces path-tracking errors while following global path planning. These capabilities ensure that the robots can adapt effectively to various operational scenarios, from cleaning open areas in the H-shape configuration to navigating tight spaces in the V-shape configuration.

Specifically, the Figure 3 depicts the wheels setup and robot locomotion where the configuration setup $V_{fl},V_{fr},V_{br},V_{bl}$ determine the corresponding speed of wheel. Parameters $a$ and $b$ are the separations from the robot’s middle in the comparing $x$ and $y-axis$ of the robot outline. Following the model in Taheri et al., [Reference Taheri, Qiao and Ghaeminezhad45] forward kinematic conditions are formulated as (1–4), and reverse kinematic conditions of the robot can be composed as (5–7):

(1) \begin{align}&\,\,\, \omega _{fl}=\frac {1}{r}(vel_y-vel_x+(a+b)\omega _\theta ) \end{align}

(2) \begin{align}& \omega _{fr} = \frac {1}{r}(-vel_y+vel_x+(a+b)\omega _\theta ) \end{align}

(3) \begin{align}&\,\,\, \omega _{br}=\frac {1}{r}(vel_y+vel_x+(a+b)\omega _\theta ) \end{align}

(4) \begin{align}& \omega _{bl}=\frac {1}{r}(-vel_y-vel_x+(a+b)\omega _\theta ) \end{align}

where $\omega _{fl},\omega _{fr},\omega _{br},\omega _{bl}$ represents the corresponding angular velocities of each wheel calculated based on the command velocities on $x$ , $y$ , and orientation $\theta$ in the workspace $vel_y,vel_x,\omega _\theta$ received by the robot and $r$ is the radius of each wheel.

(5) \begin{align}&\quad\,\,\, V_{x} = 0.25*(V_{fl}-V_{fr}+V_{br}-V_{bl}) \end{align}

(6) \begin{align}&\quad V_{y} = 0.25*(-V_{fl}+V_{fr}+V_{br}-V_{bl}) \end{align}

(7) \begin{align}& V_{\theta } = 0.25/(a+b)*(V_{fl}+V_{fr}+V_{br}+V_{bl}) \end{align}

After calculating the velocity of the robot based on inverse kinematics equations, Eqs. (8), (9), (10) ate used to estimate the position of the robot relative to the robot environment where $\delta _{t}$ the represents the time step or sampling interval.

(8) \begin{align}& \dot {x} = (V_{x} * \cos {(-\dot {\theta }}) - V_{y} * \sin {(-\dot {\theta })}) * \delta _{t} \end{align}

(9) \begin{align}& \dot {y} = (V_{x} * \sin {(-\dot {\theta })} - V_{y} * \cos {(-\dot {\theta })}) * \delta _{t} \end{align}

(10) \begin{align}&\qquad\qquad\qquad \dot {\theta } = V_{\theta } * \delta _{t} \end{align}

Figure 3.

Reconfigurable robot: kinematic motion model.

To facilitate the transmission of control data to the robot hardware, the robot operating system (ROS) [Reference Quigley, Conley, Gerkey, Faust, Foote, Leibs, Wheeler and Ng46] serves as the foundational middleware framework. The robot’s estimated position and velocity are published as wheel odometry messages on dedicated ROS topics, ensuring efficient communication and data synchronization.

4. Inter-reconfiguration framework

The software framework of the inter-reconfigurable multi-robots system is displayed in Figure 4. The installed Nvidia Jetson Xavier PC is 8 dedicated core CPUs and 8 GB RAM to fulfill the path planning computational load and handle the streaming sensors. The environment perception and localization sensors comprise industrial IMU sensor, wheel odom encoders, and 2D Lidar. In multi-robot operation, robot localization is essential for stable navigation and robot interactions within the known prebuilt map and known other agents’ locations. The sensor fusion technique uses an EKF method incorporating the information of IMU, wheel encoders, and SLAM to get the accurate robot location. During implementation, the robot realizes itself and another robot in the system to define the path from the source to the goal positions. A local planner is created to avoid obstacles while tracking the global path. In the next section, we will describe the fundamental inter-reconfigurable framework that enables our multi-robots system’s inter-operation.

Figure 4.

Software architecture of inter-reconfiguration configuration.

For the inter-reconfiguration state of the robot, a centralized local network configuration is used to establish communication between each robot. As mentioned in the robot system architecture, the software system is developed on ROS framework, which hosts ROS master in a specific local IP address of the robot. ROS master enables the communication between multiple nodes by topics and services within the robot system. In reconfigurable system, we mainly use a robot controller node to handle the robot’s overall control. A sensor fusion node is used to fuse and compute data from 2D lidars used. Moreover, a navigation stack node is used to perform autonomous capability on the robot based on the sensor feedback computed from the robot controller node and sensor fusion node. During the inter-reconfiguration of the robot, multiple ROS masters are multicasted over a locally connected network using a master discovery node. Master discovery node remotely connects ROS masters of ’n’ number of robots and registers topics and services to all locally connected robots. Figure 4 describes the inter-reconfiguration framework for ‘n’ number of interconnected robots. The proposed framework chooses any one robot based on the battery percentage to handle the autonomous tasks given to the robot. For example, If system 3 is chosen to handle the autonomous tasks in Inter reconfiguration mode, as highlighted in yellow in Figure 4 where system 3 handles the navigation stack node and sensor fusion node. The sensor fusion node merges the Lidar sensors highlighted in green color to achieve the maximum field of view for autonomous navigation tasks. The robot controller node in all the interconnected robots works in Inter-reconfiguration mode where the velocity commands generated from the navigation stack node in system 3 will be recomputed to velocity commands for individual wheels of all the interconnected robots. This approach minimizes the computational complexity of each robot with an increasing number of interconnected robots.

5. Global path planning for inter-reconfigurable robot

Since the inter-reconfigurable system can enlarge the footprint by double the size of an individual robot, in theory, it can cover the empty space at double speed. However, to enhance the area coverage of the inter-reconfigurable multi-robots system, the shortest path planning in a confined environment is essential to improving access to the confined hard-to-access area; as a result, an increase in the percentage of area cleaned. The shortest path planning methods for single platform [Reference Kyaw, Le, Veerajagadheswar, Elara, Thu, Nhan, Duc and Vu47, Reference Sriniketh, Le, Mohan, Sheu, Tung, Van Duc and Vu48], appear differently in relation to the proper cleaning and maintenance proposed on the inter-reconfigurable multi-robots cleaning and maintenance frameworks. In this section, by modeling the global path planning of the flexible generic self-reconfigurable robots as geometric planning in high dimensional state spaces, we leverage the anytime sampling-based planning algorithms to find asymptotically optimal solutions in obstacle-rich environments with narrow constrained regions. We define the geometric path planning problem for general self-reconfigurable robots with $n$ -dimensional joints similar to [Reference Karaman and Frazzoli40]. List of acronyms for shortest path planning are mentioned in the Appendix A.

In the general inter-reconfigurable multi-robot system, let $\mathcal{W}=\mathbb{R}^{n}$ be the n-dimensional environment consisting of obstacles, $\mathcal{O} \subset \mathcal{W}$ . Let $\mathcal{X}$ be the state space of a self-reconfigurable robot with $n$ -dimensional joints and $\textbf{x} \in \mathcal{X}$ denotes the state of a robot in which $\textbf{x}=(x, y, z, roll, pitch, yaw,j_0, \\ j_1, \ldots, j_{n-1})$ , where $(x, y, z, roll, pitch, yaw)$ denotes the 6 variants Special Euclidean group in SE(3) 3D space representation and $(j_0, j_1, \ldots, j_{n-1})$ are the positions of $n$ joints in $\mathbb{R}^n$ space. Let $\mathcal{X}{\textrm{obs}} \subseteq \mathcal{X}$ denote the set of all states, $\textbf{x}$ , that are obstructed due to reconfiguration, $\mathcal{O}$ , and let $\mathcal{X}{\textrm{free}} = \mathcal{X} \setminus \mathcal{X}{\textrm{obs}}$ represent the corresponding set of states free from collisions. Define $\textbf{x}I \in \mathcal{X}{\textrm{free}}$ as the starting state and $\textbf{x}G \in \mathcal{X}{\textrm{free}}$ as the target state. Let $\pi : [0,1] \to \mathcal{X}{\textrm{free}}$ be a continuous and valid path. A safe path on a map refers to a collision-free route that a robot can follow while avoiding obstacles and considering environmental constraints. It ensures that the robot does not enter restricted areas, maintains sufficient clearance from obstacles, and adheres to constraints such as narrow passage navigation and energy saving. The objective of the optimal path planning problem is to identify an admissible path $\pi ^*$ , as described in (11), connecting $\textbf{x}_I$ to $\textbf{x}G$ through collision-free space, while minimizing the path cost function, $c : \Sigma \to \mathbb{R}{\geq 0}$ .

(11) \begin{equation} \pi ^* = \underset {\pi \in \Sigma }{\operatorname {\arg \min }} \left \{c(\pi ) \mid \pi (0)=\textbf{x}_{I},\ \pi (1)=\textbf{x}_{G}, \forall s \in [0,1],\ \pi (s) \in \mathcal{X}_{\textrm{free}} \right \}, \end{equation}

where $\Sigma$ denotes the set of all non-trivial paths and $\mathbb{R}_{\geq 0}$ is the set of nonnegative real numbers.

We validate the optimal global path planning algorithm with a proposed inter-reconfigurable multi-robot system as the 2D shortest path planning study case. Note that each platform has four independent steering units designed for omnidirectional locomotion, and two system body frames can also be expanded to H- shape and compressed to V- shape by independently controlling the additional passive physical connected hinge to traverse through tight spaces. Hence, the state of the multi-robots system in the world frame can then be represented as 4-dimensional space, $\{x, y, \theta, j_0\}$ , where $\{x, y, \theta \}$ denotes the location state space and $\{j_0 \in (0, \pi )\}$ are the controllable join of reconfigurable robots. The angles for each steering unit of the robot are taken into account during the planning process, as the focus is on geometric path planning within a 2D environment. The paths generated by the proposed global planner comprise waypoints that represent the state space of the multi-robot system, while an external local trajectory controller ensures the execution of these waypoints following.

5.1. The RIRRT* for reconfigurable system

Among the sampling-based path planning, IRRT * as recommended in ref. [Reference Gammell, Barfoot and Srinivasa9] tends to speed up the RRT and RRT* convergence *’s rate by focusing the search space using heuristics based on a cost function. Since the calculation’s union rate corresponds to the size of the hyperellipsoid, we improved IRRT* more by contracting the size of its $n$ -dimensional hyperellipsoid. Rather than utilizing the current arrangement cost as the hyperellipsoid’s cross-over width, this paper suggests utilizing the current arrangement’s greatest heuristic expense as the cross-over measurement, bringing down the hyperellipsoid’s size and upgrading the assembly rate.

Figure 5.

Illustration of the $L^2$ greedy informed set and its advancement with safe path.

Building upon IRRT*, the RIRRT* algorithm (Algorithm1) incrementally grows a tree, $ G = (V, E)$ , where $ V$ represents a set of vertices and $ E$ denotes edges in the collision-free space. This process aims to improve the solution path iteratively. Similar to IRRT*, RIRRT* rewires the graph with newly added vertices to reduce the cost-to-come of nearby vertices, optimizing the overall solution (Algorithm1, Lines 21–28).

Once an initial solution is available, the algorithm biases random sampling toward a reduced subset of the hyperellipsoid called the greedy informed set (Algorithm1, Lines 18, 16). This subset includes states capable of producing improved solutions relative to the maximum heuristic cost from the current solution path (Algorithm1, Lines 7–11). The greedy informed set focuses on states with a cost-to-come $ g(\textbf{x})$ , cost-to-go $ h(\textbf{x})$ , and total cost $ f(\textbf{x}) = g(\textbf{x}) + h(\textbf{x})$ balancing exploitation and exploration through the greedy biasing ratio, $ \epsilon$ (Algorithm1, Line 9). For $ \epsilon = 1$ , sampling is confined to the greedy informed set; for $ \epsilon = 0$ , uniform sampling is applied. Adjusting $ \epsilon$ optimizes exploration and exploitation, leading to faster convergence.

To navigate narrow passages, RIRRT* incorporates a dynamic mechanism for adjusting the robot’s base width. Initially, edges are validated using the maximum base width; if unsuccessful, the width is reduced incrementally until a valid configuration is found or the edge is deemed invalid. This approach enables adaptability while preserving the robot’s larger default size when feasible. At each iteration, the algorithm selects the goal vertex $ {\textbf{x}}_i$ with the lowest cost-to-come $ g(\textbf{x})$ (Algorithm1, Line 5) and determines the maximum heuristic cost from the current solution path ( $ c_{\textrm{max}}$ ) for sampling (Algorithm1, Lines 6–11). If no solution path exists, sampling spans the entire state space (Algorithm1, Line 6-11). RIRRT* preserves the rewiring radius $ r_{\textrm{rewire}}$ from IRRT* (Algorithm1, Line 23), ensuring efficient tree refinement. Additionally, vertices within the goal region are incorporated into the solution set $ X_{\textrm{soln}}$ when their cost-to-come is minimal (Algorithm1, Lines 29–30).

The algorithm ensures probabilistic completeness and asymptotic optimality (Appendices B, C) by adhering to the core principles of RRT* and IRRT*. RIRRT* guarantees probabilistic completeness (Appendix B) by ensuring each sample has a nonzero selection probability, progressively covering the feasible space. Meanwhile, its adaptive rewiring mechanism (Algorithm1, Lines 4–14) maintains asymptotic optimality by iteratively refining solution quality as iterations increase.

Specifically, to further enhance convergence, RIRRT* integrates cost-to-come, maximum heuristic cost, and greedy informed sampling with parameter $\epsilon$ , balancing global exploration and local exploitation. An adaptive cost-to-go heuristic refines sampling weights, guiding the planner toward lower-cost solutions more effectively. As demonstrated in Appendix, the algorithm improves convergence by reducing the effective problem dimensionality through greedy informed sampling, increasing the likelihood of selecting optimal path states. Theoretical analysis, including the worst-case sample count impact theorem, quantifies the trade-off between focused sampling and probabilistic optimality, demonstrating efficiency gains without compromising solution quality. These refinements strengthen the exploration-exploitation balance, enhancing solution quality while reducing computational overhead, particularly in high-dimensional and constrained planning of inter-reconfigurable robots.

Algorithm 1.

RIRRT* for reconfigurable robot $({\textbf{x}}_I, {\textbf{x}}_G, {\mathcal{X}}_{\textrm{free}}, \epsilon )$

6. Experimental results and discussion

The RIRRT* algorithm for inter-reconfigurable multi-robot system was evaluated in both simulation environment (Section 6.2) and real-world experiments (Section 6.3). Simulations were run in Ubuntu 20.04 on a workstation with 16 GB of RAM and Ryzen 5 3600 6-core processor. All the experiments use the same hyperparameters and are tuned in faith to perform better. The maximum edge length of the tree is set to $2.5$ for all the planners, and IRRT*-like planners share the same rewiring factor constant of $4.5$ . Simulation experiments were run $50$ trials with different pseudorandom seeds.

Figure 6.

Illustrations of the large workspace set up for the simulation experiments.

6.1. Large simulation environment with shortcuts

We demonstrate the ability of RIRRT* to find optimal solutions with a faster convergence rate in a large simulation environment with various obstacles, depicted in Figure 6(a). The environment is $29$ m wide and $70.5$ m long, and consists of several obstacles and narrow passage shortcuts for the reconfigurable robot to traverse through it. Since reconfigurable robot navigates only on a planar surface, a 2-dimensional occupancy grid map [Figure 6(b)] is used during planning by projecting a map of the simulation environment onto 2D plane based on robot’s height. The $\textbf{x}_I$ and $\textbf{x}_G$ in Figure 6(b) represent the initial and final states of the reconfigurable robot footprint, and the planner has to find a solution path from $\textbf{x}_I$ to $\textbf{x}_G$ , where both states are in the fully expanded footprints. This task is challenging as several solutions exist, and only one unique shortcut to the goal is available, which can only be achieved traversing through by reconfiguring each reconfigurable robot’s gait. Therefore, we investigate the performance of the tested planners in a simulation environment where the cost objective minimizes the distance through a four-dimensional search space. Note that the distance cost function is the summation of the Euclidean distance for $\mathbb{R}^n$ state spaces and angular distance for SO(n) state spaces. All planners RRT*, IRRT*, BIT*, and proposed RIRRT* were given $300$ s of planning time, and the median solution costs were calculated from the total $50$ trials by recording the solution cost of each planner at every $100$ ms from a separate thread and interpolating each trial. If no solution has been discovered during the recording process, the solution cost is assigned a value of infinity to facilitate the calculation of the median. In order to accelerate finding a narrow passage shortcut, we intentionally set a fixed value to the SO(2) component of 4-dimensional state space for half the planning time and used uniform random sampling for the rest.

Figure 7.

An example of solution paths found by the planners after $30$ seconds of planning time. (a) RRT* with path length, (b) Inform RRT* with path length 2.38, (c) BIT* with path length 2.31, (d) RIRRT* with a path length of 2.18.

An example of the solution paths obtained by the planners in this simulation environment is illustrated in Figure 7, along with the reconfigurable robot’s footprint. The edges generated by the planners are highlighted in red, while the current best solution paths, including the reconfigurable robot’s footprint, are depicted in green. The red ellipsoidal regions represent the informed sets of each planner. Notably, the proposed RIRRT* efficiently identifies a shortcut path through the narrow passage and commands the system to transition from an H-Shape to a V-Shape to navigate through the constrained space. In contrast, other planners have not yet discovered this shortcut within the given planning time. When reconfiguration is enabled [Figure 7(d)], RIRRT* consistently finds the lowest-cost path through narrow passages, demonstrating the advantage of dynamic reconfigurability. Meanwhile, IRRT* and BIT* require significantly more planning time to explore these constrained areas effectively. Despite allowing reconfiguration, IRRT* and BIT* struggle to find paths through the narrow passage within the allocated planning time, highlighting their slower convergence in highly constrained environments. As a result, RIRRT* outperforms these approaches by quickly identifying viable paths and optimizing traversal through confined spaces. Overall, the results in Figure 7 confirm that RIRRT* not only discovers better-quality solution paths but also converges faster toward an optimal solution compared to existing state-of-the-art planners. Its ability to dynamically adjust the robot’s configuration enhances both efficiency and adaptability in complex environments.

Figure 8.

Simulation workspace includes complex planning problems containing narrow passage gap with $\textbf{x}_I$ and $\textbf{x}_G$ represent the start and goal states.

6.2. Planning on narrow passage problems

The planners were also tested on simulated planning problems in $\mathbb{R}^2$ , $\mathbb{R}^4$ , and $\mathbb{R}^8$ , as illustrated in Figure 8. The test environment includes two distinct homotopy classes, featuring a narrow passage with a width of 0.04. The initial and goal states are positioned at $[-0.3,0.0,\ldots, 0.0]^T$ and $[0.3,0.0,\ldots, 0.0]^T$ , respectively. To ensure a comprehensive evaluation, the allocated planning time varied according to the problem complexity and the dimensionality of the state space. Each planner was executed for 50 trials with different pseudorandom seeds. The solution cost was recorded every $10^{-4}$ seconds via a separate thread. If a solution had not yet been found at the time of recording, its cost was set to infinity for median computation purposes.

Table I quantifies the a statistical comparison of IRRT*, BIT*, and RIRRT* performance with and without reconfiguration scenarios in terms of path length and energy cost at different iteration steps (2000, 5000, and 10,000). To ensure statistical reliability, the results include standard deviations (SD) and 95% confidence intervals (CIs), providing insights into the consistency and robustness of each planner.

Table I.

Average comparison results from 50 trials of planners in terms of with (w) configuration and without (wo) reconfiguration on a narrow passage gap of large simulation environment problem, including standard deviations (SD) and 95% confidence intervals (CI).

As these results, highlighted in Table I, RIRRT* demonstrates a significant advantage in reconfiguration scenarios, efficiently adapting to narrow passage constraints. While BIT* improves upon IRRT* in terms of path length and energy cost, RIRRT* consistently outperforms both across all iteration levels. At 10,000 iterations with reconfiguration, RIRRT* achieves the shortest path length (2.18) and lowest energy cost (4.30), surpassing BIT* (2.31, 4.50) and IRRT* (2.38, 4.55). At higher iteration counts, RIRRT* significantly reduces energy cost, demonstrating a favorable trade-off between computational effort and solution quality. Even without reconfiguration, where performance differences are less obvious, RIRRT* maintains its lead, achieving the shortest path (2.28) and lowest energy cost (5.43) at 10,000 iterations. This underscores its ability to generate efficient solutions across diverse planning environments, reinforcing its adaptability and effectiveness. Additionally, RIRRT* exhibits the lowest standard deviation, reinforcing its stability and reliability across multiple trials. For path length, RIRRT* has the lowest SD = 0.07 (wo reconfiguration) and SD = 0.08 (w reconfiguration). For energy cost, RIRRT* also has the lowest SD = 0.06 (wo) and SD = 0.09 (w).

Figure 9 illustrates the success rate (top row of each subfigure) and solution cost (bottom row of each subfigure) as a function of computation time for three path planning algorithms—IRRT* (red), BIT* (purple), and RIRRT* (green)—in different dimensional spaces: $\mathbb{R}^2$ , $\mathbb{R}^4$ , and $\mathbb{R}^8$ . The shaded regions in the plots represent the confidence intervals and standard deviations, providing a clear measure of variability in success rate and cost. Additionally, significance tests are performed to validate the statistical differences between the planners. The success rate consistently increases over time across all dimensions, with RIRRT* achieving faster convergence compared to the other planners. For example, in $\mathbb{R}^2$ , the success rate of RIRRT* is approximately 9.12% higher within the first $10^{-2}$ seconds compared to IRRT*. In $\mathbb{R}^4$ , RIRRT* achieves a 15.26% improvement in success rate over BIT* within the same time frame. In higher-dimensional space $\mathbb{R}^8$ , RIRRT* outperforms both planners with a gain of nearly 22.68% in success rate at early computation times.

Figure 9.

Results from the $50$ different trials of the planners.

In terms of solution cost, RIRRT* consistently produces better results. In $\mathbb{R}^2$ , the solution cost is reduced by approximately 10.56% compared to IRRT*. Similarly, in $\mathbb{R}^4$ and $\mathbb{R}^8$ , the cost achieved by RIRRT* shows improvements of 16.15% and 19.12%, respectively. The proposed RIRRT* achieved better performance with gains of 9.8% in path length and 8.5% in energy cost in the without reconfiguration case and gains of 17.79% in path length and 15.26% in energy cost in the reconfiguration case. Overall, RIRRT* demonstrates superior performance in both success rate and solution cost, particularly in higher dimensions, with significant gains of up to 25% over competing planners.

6.3. Planning of reconfigurable robot platforms in real-world environment

To evaluate the efficiency of saving the energy and time spent by the proposed inter-reconfigurable system with global path generated by RIRRT* in the real-world environments, we integrated the RIRRT* to ROS navigation package as the global path planning plugin and compare its efficiency with other existing planning plugins. We set the predefined source and destination in real-world environments for both the reconfiguration four-dimensional state space (consisted of 2d position: $x, y$ , orientation and hinge angle) and without reconfigurable three-dimensional state space (consisted of 2d position: $x, y, orientation$ ). Note that we select the solutions of planners after 180 $s$ planning time to conduct the navigation experiment. Meanwhile, A* and D* as the default global path planner integrated into ROS navigation stack [Reference Quigley, Conley, Gerkey, Faust, Foote, Leibs, Wheeler and Ng46]. The workspace scenario is mapped using SLAM [Reference Koide, Miura and Menegatti49] with 2D laser sensor. Once the global paths are generated for the built map to connect these waypoints, the inter-reconfigurable multi-robots system follows the path tracking from the velocity commands issued by a local trajectory controller to visit the waypoints orderly. The spent time and the consumed energy were recorded from reconfigurable robot’s battery management system after each navigation. The reported runtime includes both the path planning time and the time taken by the robot to complete navigation along the planned path. This comprehensive measurement ensures a realistic evaluation of the system’s performance in real-world conditions. The runtime is influenced by factors such as the complexity of the environment, the need for reconfiguration in narrow passages, and the dynamic execution of path adjustments during navigation.

In the first scenario as shown in Figure 10, RIIRT with (w) and wo (without) reconfigurable is compared against the conventional global path planning methods A*, D*, IRRT*, and BIT*. The workspace consists of possible options (Paths 1 and 2) with different path lengths to connect the defined source to destination waypoints. The example path of each tested method with the platform actions while navigating through the narrow space is shown in Figure 11.

Figure 10.

The workspace setup of the real environment with narrow space.

Figure 11.

The robot navigation trajectories (green color) in the 2D map of the real testbed workspace. (a) The A* without reconfiguration, (b) D* without reconfiguration, (c) IRRT* with reconfiguration, and (d) RIRRT* with reconfiguration.

Based on the software architecture described in Section 4.1, the transformation between the V-shape and H-shape configurations is executed seamlessly while navigating narrow passages, with minimal delay (typically less than 100 ms). In each iteration, the transformation process remains consistent, ensuring that the robot’s positional identity is maintained. Furthermore, the transformation does not introduce any positional offset between the two reconfigurable robot platforms, preserving spatial alignment for effective inter-reconfiguration.

To validate the effectiveness of RIRRT* with other advanced path planners in more complex environments, the second scenario featuring a multi-room layout with obstacles and varied terrain is presented in Figure 12. The test map spans approximately 90 m by 80 m. In this experiment, the robot is equipped with cleaning modules to perform maintenance tasks. These applications demand a comprehensive path planning algorithm to ensure that the robot moves from one location to another location separated by multiple narrow constrained spaces to thorough cleaning in areas requiring attention.

We can realize that the RIRRT* outperformed the IRRT* in terms of energy and time use, and the outperform margin increases significantly when the search space increases. Although the A* and D* methods perform better than the random path, they consume considerably more energy and time than both RIRRT* and the IRRT* methods, which have reconfiguration implemented to shapeshift through the narrow passage. When comparing the inter-reconfigurable and non-reconfigurable setups of RIRRT*, the inter-reconfigurable configuration achieves shorter and more efficient paths. Additionally, the RIRRT* method demonstrates smoother trajectories with fewer turns in the reconfigurable setup, outperforming IRRT* in terms of path smoothness and efficiency.

Figure 12.

The map with complex multi-room layouts. The red and blue arrows annotate the perspective of location and orientation toward the actual view of the test environment.

The results clearly demonstrate that RIRRT* outperforms the other planners in both execution time and energy consumption under all tested conditions. The SD and CI results strengthen the reliability and robustness of these findings. While IRRT*, BIT*, and D* deliver competitive performance, RIRRT* consistently leads in efficiency, making it the optimal choice for applications requiring both rapid execution and low energy usage. The statistical significance of these results confirms RIRRT*’s advancements over the other planners, solidifying its position as the most effective solution in this context.