Search and rescue missions require robotic systems that can explore unknown environments, maintain progress under limited time budgets, and improve the chance of finding victims. In indoor disaster settings, the exploration problem is not limited to map coverage. Candidate frontiers may differ in accessibility, visibility, and expected rescue value, even when they are all reachable from the current robot pose. As a result, a frontier selection policy that is appropriate for generic exploration may not be the most suitable policy for search and rescue.
Quadruped robots are a relevant platform for this problem because they can move through cluttered spaces and maintain locomotion in conditions that may be restrictive for wheeled systems. This mobility makes them attractive for reconnaissance and victim search in partially structured environments. However, the advantage of legged mobility alone is not sufficient. Once several exploration alternatives become available, the robot must decide not only where new space can be observed, but also where rescue relevant progress is more likely to be achieved. This difficulty becomes more evident in environments where the layout contains multiple branches, partial occlusions, and clutter that weakens the usefulness of purely geometric frontier selection.
A situation aware frontier prioritization strategy is proposed for single robot quadruped search and rescue. The method preserves the frontier exploration structure, but extends frontier scoring with rescue relevance, observation deficit, terrain penalty, and travel cost. In this way, map expansion is maintained while preference is given to frontiers that are more likely to improve rescue performance. An overview of the proposed framework, including the two evaluation scenarios, the perception and mapping pipeline, the frontier prioritization mechanism, and the main evaluation criteria, is presented.
The method is evaluated in two simulated indoor environments. The first scenario is intentionally simple and is used as a sanity check. The second scenario introduces a higher level of clutter and branching structure, and is used as the main comparison case. The results indicate that the easy scenario is solved by all methods, while the larger and more complex scenario is different. In that setting, the proposed method achieves the highest completion rate and the highest victim recovery. These results suggest that situation aware frontier prioritization is most beneficial when frontier choice is no longer trivial and rescue utility must be balanced against coverage.
The main contributions of this work are summarized as follows:
- A situation aware frontier prioritization method for single robot quadruped search and rescue, in which frontier selection is guided by information gain, observation deficit, rescue relevance, terrain penalty, and travel cost.
- A simulation based evaluation protocol for quadruped search and rescue in two indoor environments with different levels of difficulty, including a simple scenario and a complex scenario designed to reveal differences in frontier selection behavior.
- An experimental comparison against nearest frontier, information gain, and risk aware baselines, showing that the proposed method achieves the best completion rate and victim recovery in the complex scenario.
Related Work
Frontier based exploration is one of the most established approaches for autonomous exploration in unknown environments. In the classical formulation, a frontier is defined as the boundary between known free space and unknown space, and the robot is guided toward one of these boundaries to expand the mapped region. This approach is attractive because of its simplicity, but it does not by itself distinguish between frontiers that are equally reachable yet different in task relevance.
Information based exploration extends this idea by ranking candidate frontiers according to their expected utility for mapping, commonly through entropy reduction or information gain. This formulation is stronger than pure nearest frontier selection because it attempts to maximize map improvement rather than simply minimizing travel distance. However, its objective is still primarily exploratory. In search and rescue, information gain alone may not be sufficient if the most informative frontier is not the most relevant for victim discovery.
Risk aware exploration introduces a different emphasis by accounting for the probability of unsuccessful execution, terrain difficulty, or uncertainty during exploration. These methods are valuable in challenging environments because they reduce the chance of aggressive but unsafe behavior. However, risk aware methods are still not necessarily rescue aware. A frontier may be safe and informative while still being weakly connected to the victim search objective.
Although frontier based exploration, information driven exploration, and risk aware navigation provide strong foundations for autonomous search, an important gap remains for quadruped search and rescue. Existing methods are primarily designed for generic exploration objectives such as coverage, uncertainty reduction, or safe motion, but they do not explicitly rank frontiers according to rescue utility. In search and rescue, this is a relevant limitation, because a frontier that is nearest or most informative for mapping may not be the frontier that best supports victim discovery. This gap becomes more pronounced in cluttered environments where frontier choice is no longer trivial.
This work differs from prior nearest frontier, information gain, and risk aware exploration methods by introducing a rescue oriented frontier selection strategy for a quadruped robot. The proposed method preserves the frontier exploration framework, but augments it with rescue relevance and observation deficit in addition to terrain penalty and travel cost. As a result, the method is designed not only to expand the map, but also to bias exploration toward frontiers that are more likely to improve rescue outcomes. This paper therefore addresses the gap between generic exploration policies and task aware search and rescue exploration, and evaluates that difference in indoor environments with increasing decision complexity.
Problem Formulation
A single quadruped robot is considered in an indoor search and rescue setting represented as an initially unknown environment. The robot must autonomously explore the map, navigate through cluttered passages, and maximize the probability of finding victims within a fixed mission time budget. Let a candidate frontier be extracted from the current occupancy map. The decision problem is to select, at each planning cycle, the frontier that best balances map expansion and rescue oriented utility.
The proposed method assigns a score to each frontier according to a weighted combination of five terms: information gain, observation deficit, rescue relevance, terrain penalty, and travel cost. This formulation preserves the simplicity of frontier based exploration, but extends it toward search and rescue objectives. Information gain promotes continued map expansion, observation deficit favors regions that remain weakly explored, rescue relevance gives preference to frontiers associated with higher victim search potential, terrain penalty discourages difficult or risky regions, and travel cost avoids unnecessarily expensive motion.
System Architecture
The complete system is organized as a perception, planning, and execution pipeline implemented in ROS 2 and evaluated in Gazebo simulation with a Unitree Go2 quadruped model. The architecture contains four main modules: mapping, frontier generation and scoring, victim handling, and local motion execution.
The robot uses onboard sensing to incrementally update a local occupancy representation of the environment. This map is used to distinguish known free space, occupied space, and unknown regions. In parallel, the robot state estimation pipeline provides the pose required for map updates, frontier extraction, and motion control. The mapping layer therefore serves as the common information source for all evaluated methods.
Proposed Method: Situation-Aware Frontier Prioritization
The proposed method, denoted Situation-aware Frontier Prioritization, augments frontier based exploration with rescue oriented decision variables. Its main idea is that frontier selection should reflect not only geometric or informational value, but also the likelihood that a frontier supports meaningful search and rescue progress.
Given the set of candidate frontiers extracted from the current occupancy map, the selected frontier is defined as the one with the highest frontier score. To make rescue relevance explicit, the rescue relevance term is modeled as a function of tentative victim evidence.
Compared with generic exploration, the proposed method differs in three ways. First, it introduces rescue relevance into frontier ranking, which biases the robot toward regions that are more likely to improve victim discovery. Second, it includes observation deficit so that weakly observed regions are revisited when needed instead of being ignored after minimal coverage. Third, it preserves terrain and travel penalties to avoid rescue relevance dominating motion feasibility.
Baseline Methods
The proposed method differs from the baselines because it does not optimize only for distance, map utility, or safety. Instead, it introduces rescue relevance as an explicit term in frontier ranking while preserving the overall frontier exploration framework. Therefore, the comparison is not between frontier exploration and a different planning paradigm, but between generic frontier selection policies and a rescue aware frontier policy.
Results
The results were obtained in the easy scenario (S1) and the complex scenario (S2). In S1, all methods achieve relatively high completion rates, which confirms that the environment functions as a valid sanity check scenario. In this easier setting, the Information Gain baseline achieves the highest completion rate and victim recovery, while the proposed method remains functional but does not surpass the strongest baseline. This suggests that explicit situation awareness is less relevant when frontier selection is simple and most candidate frontiers are similarly useful.
A different pattern is observed in S2. In this complex environment, the proposed Situation-aware Frontier Prioritization method achieves the highest completion rate, reaching 20 out of 20 successful runs. It also achieves the highest victim recovery, with a mean of 2.00 confirmed victims per run. By contrast, the Information Gain baseline completes only 14 out of 20 runs and recovers fewer victims on average. Nearest Frontier and Risk-aware Exploration remain competitive, but both are still outperformed by the proposed method in completion rate and victim recovery.
The mission time and path length values support this interpretation. In S2, the proposed method reaches full mission completion without requiring the longest travel distance. The Information Gain baseline travels substantially farther on average, yet still achieves worse completion and victim recovery. This indicates that the proposed method does not simply increase search effort, but instead allocates that effort more effectively. The main benefit of the proposed methodology therefore appears in frontier decision quality rather than in raw motion alone.
Taken together, the results suggest that situation aware frontier prioritization is most beneficial when the environment contains enough clutter and branching structure for frontier choice to become ambiguous. In the easy scenario, simpler exploration criteria are sufficient. In the complex scenario, however, rescue oriented frontier scoring improves mission reliability and victim recovery.
Conclusion
This paper presented a situation aware frontier prioritization strategy for single robot quadruped search and rescue. The proposed method extends classical frontier exploration with rescue relevance, observation deficit, terrain penalty, and travel cost while preserving the computationally attractive structure of frontier based selection. The method was evaluated in two indoor rescue scenarios representing easy and complex conditions.
The results show that the easy scenario serves as a stable sanity check in which all methods are broadly effective, while the complex scenario is more discriminative. In that setting, the proposed method achieves the highest completion rate and the highest victim recovery, which indicates that rescue aware frontier prioritization becomes useful once frontier choice is no longer trivial. The results therefore support the view that the main value of situation awareness lies in structured cluttered environments where generic exploration objectives are not sufficient by themselves.
Future work should extend the study toward even harder environments, improve victim confirmation under stronger occlusion and uncertainty, and validate the proposed strategy on physical quadruped platforms.
Acknowledgements
The authors of this work would like to thank the Technological University of Uruguay and the Laboratory of Robotics and AI for the support in this work.
Frequently Asked Questions
What makes this frontier prioritization method different from standard frontier exploration? The proposed method augments classical frontier exploration with rescue relevance and observation deficit terms in addition to terrain penalty and travel cost, biasing exploration toward frontiers more likely to improve victim discovery rather than simply expanding map coverage.
Which robot platform was used in the evaluation? The system was implemented in ROS 2 and evaluated in Gazebo simulation using a Unitree Go2 quadruped model operating in two simulated indoor environments.
What results were achieved in the complex scenario? In the complex environment, the proposed method achieved 20 out of 20 successful mission completions and a mean of 2.00 confirmed victims per run, outperforming the nearest frontier, information gain, and risk aware baselines.
When is situation aware frontier prioritization most beneficial? The method provides the most significant advantage in cluttered environments with branching structures where frontier choice is ambiguous and generic exploration objectives are insufficient for effective search and rescue.