Situation Aware Frontier Prioritization for Quadruped Search and Rescue

Technical Summary: Situation Aware Frontier Prioritization for Quadruped Search and Rescue

Problem Statement
Search and rescue (SAR) missions in unknown indoor environments require robotic systems that can autonomously explore, navigate cluttered spaces, and maximize the probability of finding victims within a fixed time budget. While quadruped robots offer superior mobility in cluttered and restrictive environments compared to wheeled systems, their autonomous exploration faces a specific challenge: classical frontier selection strategies (e.g., nearest frontier, information gain, risk-aware) are designed primarily for generic map coverage or uncertainty reduction. These standard approaches do not explicitly balance map expansion with the likelihood of discovering victims. In complex scenarios with multiple branches, partial occlusions, and clutter, the frontier that is nearest or most informative for mapping may not be the one that best supports victim discovery.

Methodology
The paper proposes a Situation Aware Frontier Prioritization strategy for single-robot quadruped SAR. The method retains the classical frontier-based exploration framework but extends the frontier scoring mechanism to incorporate rescue-specific objectives alongside geometric and informational metrics.

• Scoring Function: Each candidate frontier $f$ is assigned a score $J(f)$ calculated as:
  $$J(f) = w_I I(f) + w_O O(f) + w_R R(f) - w_T T(f) - w_D D(f)$$
  Where:

  • $I(f)$: Information gain (promotes map expansion).
  • $O(f)$: Observation deficit (favors weakly explored regions).
  • $R(f)$: Rescue relevance (the novel component), modeled as a function of tentative victim evidence. It increases the score of frontiers closer to spatial regions with higher rescue utility or tentative victim cues.
  • $T(f)$: Terrain penalty (discourages difficult or risky regions).
  • $D(f)$: Travel cost (penalizes long travel distances).
  • $w$ terms: Weighting coefficients.

• System Architecture: Implemented in ROS 2 and evaluated in Gazebo using a Unitree Go2 quadruped. The pipeline includes:

  1. Mapping & State Estimation: Incremental update of a local occupancy map.
  2. Frontier Extraction & Scoring: Clustering and ranking of frontiers using the proposed multi-objective score.
  3. Victim Handling: A lightweight visual confirmation process where tentative detections are accumulated and spatially deduplicated before being promoted to confirmed victims, ensuring the robot acts as an explorer first and a local inspector second.
  4. Local Motion Execution: A shared local controller and recovery logic used across all methods to ensure performance differences reflect frontier selection rather than low-level control variations.

• Baseline Comparisons: The proposed method is evaluated against three established strategies:

  1. Nearest Frontier: Selects the reachable frontier with the lowest travel distance.
  2. Information Gain: Selects frontiers maximizing expected map utility (entropy reduction).
  3. Risk-Aware Exploration: Introduces penalties for uncertain or unsafe regions.

Experimental Setup
Experiments were conducted in two simulated indoor environments:

1. Scenario S1 (Easy): A simple layout with one victim and limited clutter, serving as a sanity check.
2. Scenario S2 (Complex): A layout with two victims, significant clutter, and ambiguous branching structures designed to reveal differences in frontier selection behavior.
   Each method was tested over 20 runs per scenario with randomized starting poses. Metrics included completion rate, victim recovery (mean confirmed victims), first victim time, mission time, and path length.

Key Results

• Simple Scenario (S1): All methods performed reliably. The Information Gain baseline achieved the highest completion rate (95%) and victim recovery (0.95), while the proposed method remained functional but did not outperform the strongest baseline. This suggests that explicit situation awareness is less critical when frontier choices are trivial.
• Complex Scenario (S2): The proposed method demonstrated superior performance:
  • Completion Rate: 100% (20/20 runs), outperforming Information Gain (70%), Nearest Frontier (90%), and Risk-Aware (95%).
  • Victim Recovery: Achieved a mean of 2.00 confirmed victims per run, the highest among all approaches.
  • Efficiency: The proposed method completed the mission in the shortest time (373.5s) and traveled the shortest distance (57.45m), whereas the Information Gain baseline traveled significantly farther (91.05m) with worse outcomes.

Significance and Claims
The paper claims that situation-aware frontier prioritization is most beneficial when the environment contains sufficient clutter and branching structure to make frontier choice nontrivial. In such complex settings, generic exploration objectives (coverage, uncertainty reduction) are insufficient on their own. By explicitly incorporating rescue relevance and observation deficit into the frontier ranking, the proposed method successfully balances map expansion with victim discovery. The results indicate that the primary value of this approach lies in improving the quality of frontier decisions in structured, cluttered environments, leading to higher mission reliability and victim recovery rates without increasing traversal effort.

Contributions

1. A situation-aware frontier prioritization method for quadruped SAR that guides selection via information gain, observation deficit, rescue relevance, terrain penalty, and travel cost.
2. A simulation-based evaluation protocol using two distinct indoor environments (simple and complex) to differentiate frontier selection behaviors.
3. An experimental comparison demonstrating that the proposed method achieves the highest completion rate and victim recovery in complex scenarios compared to nearest frontier, information gain, and risk-aware baselines.