HEHA: Bounded Suboptimal Planning for Constrained Routing and Its Use in Heterogeneous Multi-Robot Exploration of Unknown Environments

arXiv:2510.04161 · cs.RO · Submitted 2025-10-05 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: We're looking at the paper: "HEHA: Bounded Suboptimal Planning for Constrained Routing and Its Use in Heterogeneous Multi-Robot Exploration of Unknown Environments".

Dev: Here's the gist of the paper. The gist: HEHA proposes Hierarchical Exploration with Heterogeneous Agents to solve the large-scale constrained optimization problem arising from allocating heterogeneous robots to unknown areas and determining their visiting order subject to traversability constraints Problem Definition The exploration problem seeks a set of trajectories for multiple robots such that every surface is perceived and the exploration time is minimized Let W ⊆ R 3 denote a bounded 3D space to be explored, and let S ⊂ W denote all the surfaces in the workspace to be mapped.

Rosa: The goal of the exploration problem considered in this paper is to find a set of trajectories such that each trajectory is feasible, all surfaces are perceived, and the exploration time maxi∈I cost(τ i) reaches the minimum.

Dev: A trajectory is feasible if it satisfies both the kinodynamic constraints of the robot and traversability constraints.

Rosa: Global Planning The global planning in HEHA involves solving a Min-Max Multiple Hamiltonian Path Problem (mHPP), which seeks to minimize the maximum path cost among all agents (i.e.

Title and authors: Rosa: So we're looking at this paper today about HEHA: Bounded Suboptimal Planning for Constrained Routing and Its Use in Heterogeneous Multi-Robot Exploration of Unknown Environments. It deals with finding trajectories for different robots, like drones, wheeled vehicles, and legged robots, to map an unknown space while minimizing the time it takes to finish exploring everything.

Dev: Right. It tackles that big constrained optimization problem—how to pick which robot goes where and in what order—subject to all those physical constraints about what each robot can actually do on certain terrain. The authors are proposing a way to break that huge problem down into global planning and local planning stages, which they call HEHA.

Taro: I'm thinking about the core challenge here is that when you have different robots, their capabilities—like a wheeled robot being stuck on stairs while a legged one can climb them—that creates these assignment constraints that make traditional planners struggle exponentially as you add more robots or surfaces.

Rosa: Exactly. And the paper's main contribution, according to the abstract and page one is this hierarchical decomposition into global planning and local planning, with a specific focus on their global planning component called PEAF <ref:2510.04161#pg1,into global planning and local planning>. They suggest this structure lets them find solutions faster than just trying to solve it all at once.

Dev: Speaking of PEAF, that's their routing algorithm for the global part. The paper explains that they use an A-like search to plan paths in a joint graph, and they introduce heuristics like gmax(l) and fest(l) to estimate the remaining cost-to-go for any given state.

Taro: And then they use focal search to keep track of the open list and the focal list, prioritizing labels based on things like how many nodes have been visited, or their f-value, or gsum(l). That sounds like a way to intelligently select partial solutions that are already doing well.

Rosa: But what's interesting is how they handle the assignment constraints in this global planning phase. They use something called the Min-Max Multiple Hamiltonian Path Problem, or mHPP, which they try to solve by minimizing the maximum path cost among all agents, which is essentially trying to minimize the makespan.

Dev: And they admit that simply using existing min-sum planners can lead to infeasible paths because they ignore those assignment constraints about which robot can go where, or it just results in a much longer exploration time because of how the objective function is set up.

Title and authors: Taro: The paper points out that off-the-shelf planners like Google OR-Tools have options for solving min-max mHPP with assignment constraints, and they've been used before six or in other multi-robot path planning problems twenty-three <ref:2510.04161#pg1>. But they found those planners sometimes produce poor quality solutions or no feasible solutions if there are too many assignment constraints to describe the different terrain traversability of the robots.

Rosa: So, HEHA is trying to bypass that curse of dimensionality by planning one robot at a time during each step in PEAF, while using dominance checks and pruning techniques to keep the search space manageable. That seems like a way to handle those huge numbers without getting totally stuck on every single possibility.

Dev: The local planning part also gets attention. Since they are dealing with heterogeneous robots, they have to consider how different types of robots interact when exploring the same area, which means avoiding repeated or duplicated exploration among them.

Taro: And they do this by clustering the frontiers into subsets based on position and then formulating a Traveling Salesman Problem, or TSP, for each robot to visit those representative frontiers locally.

Rosa: They even introduce two tricks for handling heterogeneity in the local planning. The first is something called Hetero-Frontier Cost adjustment, where they change the edge cost from one node to another by taking the maximum of that edge cost and some user-defined non-negative real number c0, encouraging robots to explore different types of frontiers early on.

Dev: And the second trick is Priority Assignment. This assigns those frontiers that overlap in local regions—like a specific area where two robot types might both be able to go—to robots with higher priority based on their specific capabilities. That's smart resource allocation right there.

Taro: I wonder how effective this dynamic priority assignment is when the real-time terrain analysis changes things mid-exploration, or if it just gets stuck in a local optimum because the initial priority was set too rigidly.

Rosa: Well, the experimental results they show are pretty strong on efficiency. They found that HEHA can reduce exploration time by up to thirty percent compared to baselines, and when they compared their PEAF against Google OR-Tools and a greedy method for PEAF, their PEAF found a solution with up to forty-seven percent smaller makespan.

Dev: And they also tested it against two other baselines that adapt the popular next-bestview planner, NBVP, and a greedy method, and HEHA required up to thirty point two percent less exploration time and up to thirty-one point eight percent shorter total path length across three different environments.

Title and authors: Taro: The real robot tests are interesting too; they deployed this system in a space with both flat ground and stairs of size around thirty-five by thirty-five meters using a legged robot and a wheeled robot, and it finished the exploration in one hundred forty seconds. That's tangible proof it works outside the simulation.

Rosa: And they showed that HEHA can intelligently navigate that way; the wheeled robot explored the vast flat areas while letting the legged robot handle those stair regions to minimize the total finish time. The ablation study showed that with an intermediate alpha of zero point six, HEHA achieved the shortest exploration time, while alpha of zero point eight produced a shorter path length instead.

Dev: So it seems like they've successfully decomposed the problem and then layered in specific heuristics to manage the complexity arising from those heterogeneous constraints at both the global and local levels of planning.

Taro: The paper is pretty clear about what this method does, but they also point out a limitation on their approach; specifically, the way they handle heterogeneity in their local planning might rely too much on a fixed assignment constraint or priority rule that isn't perfectly adaptive to real-time terrain analysis.

Rosa: That makes sense. They aren't saying it solves everything dynamically, just that this hierarchical approach gives them a solid framework for multi-robot exploration under terrain variability. Overall, the HEHA paper is about making sure you can quickly find *good enough* solutions in these massive planning problems instead of waiting forever for the absolute best one.

Dev: Yeah, it's less about finding the mathematically perfect solution and more about being able to get a solution that is good enough to actually finish the mission in a reasonable amount of time. That's what they are focusing on with this paper on HEHA: Bounded Suboptimal Planning for Constrained Routing and Its Use in Heterogeneous Multi-Robot Exploration of Unknown Environments.

Taro: For my take, it shows that breaking down a huge coordination problem into smaller, more manageable steps—global routing and then local pathfinding with specific robot considerations—is a solid way to tackle these kinds of complex spatial problems.

Rosa: It’s definitely useful for real applications where you have a team of robots with different physical abilities trying to map out an unknown area quickly. We'll be looking at how this framework holds up when the environment gets even more unpredictable in future work.

Dev: Right, that’s what we need to keep watching as they move into those more complex, real-time scenarios where things change on the fly during exploration.

The paper's summary: Rosa: So, HEHA is basically taking this massive problem of figuring out where to send different robots—like drones and legged walkers—to explore an unknown area and planning their order, which has these weird rules about what each robot can actually do on certain surfaces.

Dev: Right. It breaks that huge optimization mess down into two steps: global planning and local planning, using a new routing algorithm called PEAF for the first part.

Rosa: PEAF is designed to find a solution quickly even if it's not the absolute perfect one, which is important because in exploration, you need something fast. They use an A-like search on this joint graph where each node represents a location that needs visiting.

Dev: And they tackle the assignment problem by minimizing the maximum path cost among all agents, which is trying to keep everyone moving at a similar pace. That's the makespan we want to keep low for exploration time.

Rosa: The paper shows their PEAF algorithm can find solutions with up to forty-seven percent smaller makespan than some other planners they tested against, even when those other planners are pretty advanced.

Dev: And that’s the number that really sticks, it means for complex missions, this method cuts the time needed by nearly a third. But we gotta remember the caveat they mention—that it's bounded suboptimal planning; it finds a solution quickly but maybe not always the absolute best one mathematically possible.

Rosa: Exactly. And then there’s the local planning part, which is where they really get specific about how to use those different robots together in real-time as they move.

Dev: They cluster the areas that need visiting by position and then use a Traveling Salesman Problem for each robot to figure out its local path through those specific clusters.

Rosa: Plus, they introduce these two tricks for handling the heterogeneity—one that adjusts the cost of moving between locations to encourage robots to explore different types of terrain early on, and another one that assigns high priority to robots capable of accessing overlapping areas.

Dev: So what this means for you listening right now is that if you’re thinking about deploying a team of diverse robots in a big unknown space, HEHA gives you a framework to get an efficient schedule without getting bogged down in the impossible complexity of checking every single possible robot assignment at once.

Rosa: It moves the focus from finding one perfect answer to finding a really good, usable answer fast enough for exploration. Next up, we’re going to look at how they test this whole setup in the real world with actual robots on stairs and flat ground.

The paper's improvements: Rosa: So, we're talking about how HEHA can be improved beyond just the basic global and local planning structure they proposed in this paper.

Dev: Right, the authors actually suggest a few tweaks to make it more robust, especially when dealing with those real-world situations where things get messy.

Rosa: They point out that for their global planning, PEAF can be made even faster by adding more aggressive pruning when it’s generating successor labels in the search. That means cutting down the number of paths it checks without losing too much quality initially.

Dev: That makes sense from a controls standpoint; reducing the branching factor helps keep the loop rate stable and minimizes latency during those planning steps, even if you explore slightly less promising paths at first.

Rosa: Then they look at the local planning again and suggest making that priority assignment dynamic instead of fixed, so robots can react in real-time to what terrain analysis tells them about overlapping areas.

Dev: So it means the system doesn't just follow a pre-set rule; it’s supposed to be able to adjust its priorities on the fly if the robot encounters something unexpected on a surface. That’s important for safety and reliability in an autonomous loop.

Rosa: They also mention tuning that alpha parameter in the hetero-frontier cost calculation, suggesting they use something adaptive instead of a fixed number, so robots can be more proactive about exploring different types of surfaces without getting stuck in weird zig-zag patterns.

Dev: It sounds like they’re trying to get rid of those situations where the robot just keeps re-exploring the same small area because the cost calculation didn't change enough. That improves efficiency by focusing exploration on new ground.

Rosa: And finally, for post-optimization refinement, they suggest bringing in reinforcement learning to help tweak the final path optimization and load balancing steps to adapt better across different robot types during the actual execution of the mission.

Dev: So what this means for us is that while HEHA gives you a solid foundation for multi-robot exploration under variable terrain, these improvements push it toward being more adaptive and less reliant on perfectly tuned initial parameters.

Rosa: It’s about making sure the system doesn't just find *a* solution, but a really good one that performs well when the world throws some curveballs at it.

Dev: Exactly. And those refinements could make the whole thing more reliable for real-time loops where failure modes are something you have to manage constantly.

Rosa: Next time we talk about these systems, we’ll be looking at how they handle those unpredictable terrains in actual trials with physical robots and see if these theoretical tweaks actually hold up when the ground isn't perfectly smooth.

Conclusion: Rosa: So we’re wrapping up on HEHA: Bounded Suboptimal Planning for Constrained Routing and Its Use in Heterogeneous Multi-Robot Exploration of Unknown Environments, by summarizing how they broke the complex problem into global and local planning with PEAF.

Dev: Yeah, it’s a solid framework for multi-robot exploration where you have to juggle different robot types and terrain constraints while keeping the planning fast enough for real-time loops.

Rosa: The implication is that we can move away from solving every single constraint perfectly right away and instead find a high quality solution in a reasonable amount of time, which is crucial when exploration needs to happen as soon as possible.

Dev: And the results showed that this method actually outperforms some established baselines by reducing exploration time by up to thirty percent across different environments.

Taro: I just want to push on the real-world aspect, because while the simulation looks great, how does this structure handle a sudden change in environment that wasn't part of the initial map?

Rosa: That’s a fair question, Taro. The paper flags that the method doesn't necessarily guarantee perfect robustness when things misbehave drastically outside of what was modeled initially.

Dev: From an engineering standpoint, we see this as a strong foundation because it gives you a predictable way to manage the latency and failure modes within the loop, even if those failures are unexpected.

Taro: So, it's less about predicting every single thing and more about having a plan that allows for graceful recovery when things go sideways on the ground.

Rosa: Exactly. It changes how we approach these large coordination problems by focusing on iterative improvement rather than getting stuck in an exhaustive search for perfection.

Dev: So, overall, HEHA provides a robust method for tackling constrained routing in complex, heterogeneous settings with a much better efficiency profile than many existing solutions.

Taro: I think the future work should really focus on those post-optimization refinements they mentioned earlier to see if we can make it even more adaptable to dynamic changes on the fly.

Rosa: Right, that’s where we’ll be looking next, and how this kind of hierarchical decomposition might fit with learning-augmented trajectory planning for handover missions.

Longrui Yang, Yiyu Wang, Jingfan Tang, Yunpeng Lv, Shizhe Zhao, Chao Cao, Zhongqiang Ren

Shanghai Jiao Tong University · Carnegie Mellon University

cs.RO

Submitted: 2025-10-05

Updated: 2026-10-21

Comments: 16 Figures

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 80/100

The gist: The gist: HEHA proposes Hierarchical Exploration with Heterogeneous Agents to solve the large-scale constrained optimization problem arising from allocating heterogeneous robots to unknown areas and

Key concepts

Global Planning (mHPP): This is the high-level strategy that decides which robot goes where and in what order to visit all unknown areas. It's framed as a Min-Max Multiple Hamiltonian Path Problem, meaning the goal is to find paths for all robots such that the longest path taken by any single robot is as short as possible.
PEAF Algorithm: Partial Anytime Focal search is a specific search algorithm used for global planning. It's designed to quickly find a good, though not necessarily perfect, solution to the complex routing problem by iteratively planning paths and using heuristics to guide the search towards minimizing the maximum path cost.
Local Planning Heterogeneity: This involves making local decisions for individual robots based on their specific type. The system clusters frontiers and uses a Traveling Salesman Problem (TSP) for each robot, but it adds tricks like 'Hetero-Frontier Cost' to encourage different robots to explore different areas.
Hetero-Frontier Cost: This is a cost adjustment used in local planning. It modifies the travel cost between points based on the robot type, encouraging robots that are better suited for certain terrains (like stairs) to explore those specific areas early, thus preventing redundant exploration.

Terminology

Hierarchical Exploration with Heterogeneous Agents — 1× in this paper
Planner — 1× in this paper · explained in 3 episodes

Summary

The gist: HEHA proposes Hierarchical Exploration with Heterogeneous Agents to solve the large-scale constrained optimization problem arising from allocating heterogeneous robots to unknown areas and determining their visiting order subject to traversability constraints

Problem Definition

The exploration problem seeks a set of trajectories for multiple robots such that every surface is perceived and the exploration time is minimized Let W ⊆ R 3 denote a bounded 3D space to be explored, and let S ⊂ W denote all the surfaces in the workspace to be mapped. The goal of the exploration problem considered in this paper is to find a set of trajectories such that each trajectory is feasible, all surfaces are perceived, and the exploration time maxi∈I cost(τ i) reaches the minimum. A trajectory is feasible if it satisfies both the kinodynamic constraints of the robot and traversability constraints.

Global Planning

The global planning in HEHA involves solving a Min-Max Multiple Hamiltonian Path Problem (mHPP), which seeks to minimize the maximum path cost among all agents (i.e. makespan) such that maxi∈I C(π i) reaches the minimum. This is formulated on a complete graph G = (V, E), where V is the set of Nv target nodes and each node corresponds to a frontier q ∈ SE(3) to be visited. The cost between two nodes u, v ∈ V when traversed by robot i is denoted as c i(u, v), which is estimated by solving a small path planning problem based on kinodynamic constraints.

The PEAF algorithm (Partial Anytime Focal search) is proposed to solve this mHPP. PEAF uses an A-like search to iteratively plan paths in the joint graph G from the joint start vertex⃗vs towards their joint goals ⃗vg. The algorithm employs a partial expansion strategy, planning the path of robots one by one, which helps reduce the branching factor. Heuristics are introduced, including gmax(l) and fest(l), to estimate the remaining cost-to-go for any label l. Focal search is used to maintain an open list LO and a focal list LF, prioritizing labels based on criteria like the number of visited nodes B(l), the f-value f(l), and gsum(l).

Local Planning

The local planning in HEHA considers heterogeneity by prioritizing robots of different types based on their traversability to avoid repeated and duplicated exploration among the robots. For a set of frontiers Q(Di) to be visited by robot i, HEHA clusters them into subsets Q(Di) = Q1 ∪ Q2 ∪ · · · ∪ QK based on position, and a Traveling Salesman Problem (TSP) is formulated to obtain a local path π i local for robot i to visit all these representative frontiers.

Two tricks are introduced for the heterogeneous robots in the local planning. First, Hetero-Frontier Cost adjusts the edge cost from v0 to some other vertex v in Glocal by changing it to max[cA(e) − αc0, 0], where c0 is a user-defined non-negative real number, encouraging early exploration of hetero-frontiers. Second, Priority Assignment assigns hetero-frontiers in overlapping local regions (Di,j) to robots with higher priority based on their capabilities.

Experimental Results

The experimental results show that HEHA can reduce up to 30% of the exploration time than the baselines. Specifically, when compared against Google OR-Tools and a greedy method for PEAF, our PEAF finds a solution with up to 47% smaller makespan. Furthermore, comparing HEHA in several maps against two baselines that adapt the popular next-bestview planner (NBVP) and a greedy method shows that HEHA requires up to 30.2% less exploration time and up to 31.8% shorter total path length than the baselines. In physical robot tests, HEHA was able to intelligently navigate the legged robot to explore the staired regions while letting the wheeled robot explore the vast flat ground areas so as to minimize the finish time of the entire exploration. The ablation study in a village environment showed that with an intermediate α = 0.6, HEHA achieves the shortest exploration time while α = 0.8 produces the shortest path. Finally, simulations against Nearest and NBVP baselines consistently show HEHA outperforms them by 2.3%-35% in both the exploration time and total path length across three different environments.

Exploration with Real Robots

The system was deployed to explore a space with both flat ground and stairs of size around 35m×35m using a legged robot and a wheeled robot. The exploration finished in 140 seconds, demonstrating the capability of the system in real-world scenarios.

Conclusion

HEHA successfully addresses the challenge of planning for autonomous exploration by decomposing it into global and local planning, utilizing PEAF for mHPP and incorporating heterogeneity into both levels to achieve significant improvements in exploration efficiency. The proposed method demonstrates superior performance over existing baselines in terms of reduced exploration time and total path length across various complex environments. The integration of heterogeneous constraints into the global routing and local path planning provides a robust framework for multi-robot exploration under terrain variability.

--- Page 1 ---

HEHA: Hierarchical Planning for Heterogeneous Multi-Robot Exploration of Unknown Environments Longrui Yang1, Yiyu Wang1, Jingfan Tang1, Yunpeng Lv1, Shizhe Zhao1, Chao Cao2, Zhongqiang Ren1† Abstract—This paper considers the path planning problem for autonomous exploration of an unknown environment using multiple heterogeneous robots such as drones, wheeled, and legged robots, which have different capabilities to traverse complex terrains. A key challenge there is to intelligently allocate the robots to the unknown areas to be explored and determine the visiting order of those spaces subject to traversablity constraints, which leads to a large scale constrained optimization problem that needs to be quickly and iteratively solved every time when new space are explored. To address the challenge, we propose HEHA (Hierarchical Exploration with Heterogeneous Agents) by leveraging a recent hierarchical method that decompose the exploration into global planning and local planning. The major contribution in HEHA is its global planning, where we propose a new routing algorithm PEAF (Partial Anytime Focal search) that can quickly find bounded sub-optimal solutions to minimize the maximum path length among the agents subject to traversability constraints. Additionally, the local planner in HEHA also considers heterogeneity to avoid repeated and duplicated exploration among the robots. The experimental results show that, our HEHA can reduce up to 30% of the exploration time than the baselines. I. INTRODUCTION Autonomous exploration seeks to navigate one or multiple robots in a bounded unknown environment so as to map the environment as soon as possible, which is of fundamental importance in robotics and arises in applications such as underground mining [19] and planetary exploration [13]. This paper considers autonomous exploration using a team of heterogeneous robots such as drones, wheeled, and legged robots, which have different capabilities to traverse complex terrains. For example, wheeled robots cannot pass stairs while drones and legged robots can do so. In particular, we consider all robots always stay in communication, and focus on the planning aspects of the problem: how to quickly plan paths for the robots to minimize the exploration time while considering their heterogeneous terrain traversability. Autonomous exploration involves various challenges such as mapping [22], [32], planning [6], [31] and coordination [37], [11]. While the problem has been extensively investigated recently, few of the existing work considers heterogeneous traversability for exploration planning. The major challenge is that the planner has to consider the allocation of robots to the unknown areas to be explored as well as the visiting order of those areas subject to traversablity constraints, which leads to a large scale constrained optimization problem that needs to be quickly and iteratively solved every time when new space are explored. The authors are at 1Shanghai Jiao Tong University in China, 2Carnegie Mellon University, PA, 15213. Correspondence: zhongqiang.ren@sjtu.edu.cn Fig. 1. Exploration using a ground vehicle (GV) and a legged vehicle (LV). (a) shows the results after exploration where the orange and red lines show the robots’ trajectories. (b-d) are images of the real world for the areas (i-iii) in (a). The stairs in area (i) as shown in (b) is first found by GV but is only accessible by LV. Our planner considers such traversability constraints during path planning. Our video attachment shows the exploration process.

--- Page 2 ---

Fig. 2. System Overview. (a) shows the global planning where the dashed window shows the local planning.

Improvements for AI systems

Hierarchical Planning for Heterogeneous Multi-Robot Exploration: The system can intelligently allocate robots to unknown areas and determine visiting order by leveraging a hierarchical decomposition into global planning (PEAF) and local planning, which is crucial for solving large scale constrained optimization problems quickly.
PEAF Algorithm Enhancement: The Partial Anytime Focal search (PEAF) can be improved by incorporating more aggressive dominance pruning when generating successor labels to reduce the branching factor further, even if it means exploring slightly less promising paths initially.
Local Planning Heterogeneity Integration: The local planner can be improved by dynamically adjusting the priority assignment based on real-time terrain analysis, allowing robots to proactively avoid duplicated exploration in overlapping regions by assigning higher priorities to agents capable of accessing specific hetero-frontiers.
Hetero-Frontier Cost Tuning: The system can be improved by refining the parameter alpha in the hetero-frontier cost calculation, using a learned or adaptive approach instead of a fixed value, allowing the robot to tend to have lower cost edges more proactively and avoid zig-zag paths resulting from overly aggressive exploration.
Post-Optimization Refinement: The post-optimization phase can be enhanced by integrating reinforcement learning to refine the 2-opt optimization and load balancing steps, allowing for more adaptive path improvements that minimize makespan across different robot types dynamically.