Traversability-Aware Cooperative Path Planning for Human-UGV Casualty Evacuation
Authors: Kristian Dalland, Prithvi Poddar, Souma Chowdhury, Karthik Dantu, Ehsan T. Esfahani
Organizations: Department of Mechanical and Aerospace Engineering, University at Buffalo, NY 14260, USA · Department of Computer Science and Engineering, University at Buffalo, NY 14260, USA
Heterogeneous multi-robot path planning is a well-studied problem in which agents with disparate kinematic and dynamic models must coordinate to achieve shared objectives. These formulations, however, treat all agents as robotic-their cost models are mechanical and their traversability is sensor-derived. In human-robot teaming, the human partner remains relegated to command and supervisory roles rather than being modeled as a physical co-navigator with distinct mobility constraints and dynamic energy reserves. This work investigates joint path planning for a two-agent human-UGV team in search-and-rescue casualty retrieval scenarios. We model the human agent using the Pandolf-Santee metabolic cost model with fatigue-modulated speed, and the UGV using a rolling-resistance energy model with terrain-dependent speed limits. By exploiting the complementary traversability of each agent-the human's ability to traverse dense vegetation and shallow water versus the UGV's superior speed on open terrain and roads-we optimize casualty transfer locations, termed switch points, to minimize total mission time. Evaluated across multiple synthetic 1km2 environments with procedurally generated elevation and land-cover data, the optimized strategy reduces mean mission time by 5.3% relative to a human-only baseline and by 7.0% relative to a naive human-UGV strategy without switch point optimization, while reducing human energy expenditure by 17.8% relative to baseline. Notably, the naive strategy reduces human energy expenditure by a larger margin (22.4%) but incurs a 2% increase in mission time relative to baseline, illustrating that switch point optimization is necessary to realize time savings from human-UGV teaming.
Figures & tables
Variable
Description
Unit
Type
P
Metabolic rate
W
Output
η
Terrain factor
-
Input
M
Body mass
kg
Input
L
External load
kg
Input
V
Walking speed
m/s
Input
G
Slope
% grade
Input
TABLE I: Pandolf equation variables.
Constraint
Human
UGV (Warthog)
Water (depth ≤1.2m )
Passable
Impassable
Water (depth >1.2m )
Impassable
Impassable
Dense forest
Passable
Impassable
Slope, unloaded ( ∣g%∣>45% )
Impassable
Impassable
Slope, loaded ( ∣g%∣>20% )
Impassable
Impassable
TABLE II: Agent-specific passability constraints.
Fig. 1: Case 1. Synthetic environment overview. From left to right: (a) terrain gradient map showing percent grade across the environment; (b) human terrain factor ( η ) distribution derived from land-cover classification; (c) composite land-cover map with start position, global goal, and effective UGV goal-the closest traversable cell to the global goal reachable by the Warthog platform.
Land-Cover Class
η
Source
Paved road
1.00
[ 21 ] , Table 11
Dirt / gravel road
1.20
[ 21 ] , Table 11
Tundra
1.30
[ 21 ] , Table 11
Grassland
1.40
[ 21 ] , Table 11
Heavy brush / forest
1.50
[ 22 ] via [ 21 ]
Mud / bog
2.50
Interpolated *
TABLE III: Terrain factor ( η ) assignments by land-cover class.
Surface Type
NALCMS
Crr
vterrain (m/s)
Paved road
-
0.015
4.0
Dirt / gravel road
-
0.06
2.5
Wetland
14
0.10
1.5
Grassland
10
0.12
1.8
Cropland
15
0.18
1.2
Shrubland
8
0.20
1.0
TABLE IV: UGV surface coefficients by NALCMS land-cover class.
Fig. 2: Optimized human-UGV collaborative routing for Case 2. The human carries the casualty through a short region impassable to the UGV while the UGV simultaneously routes around the obstacle, demonstrating how joint path optimization exploits complementary traversal capabilities to reduce total evacuation time.
Fig. 3: Total mission time per Case for the human-only baseline, naive human-UGV, and optimized human-UGV strategies. The optimized strategy achieves the shortest mission time in every scenario.
Fig. 4: Percentage change relative to the human-only baseline for naive and optimized human–UGV strategies. (Top) Mission time: optimized reduces time by 5.3% on average, while naive increases it by 2.0%. (Bottom) Human energy: naive achieves larger reductions (22.4%) than optimized (17.8%), illustrating the time–energy trade-off.
We study cooperative shortest path planning for an unmanned ground vehicle (UGV) assisted by an unmanned aerial vehicle (UAV) scout in environments with unknown road blockages that are only discovered when a robot reaches the damaged point. This formulation generalizes the original Canadian Traveller Problem (CTP), which assumes a single ground vehicle and that the traversability status of all incident edges is revealed upon arrival at a vertex. We first analyze the case where the start and the goal are connected by k disjoint paths, and prove that the worst-case competitive ratio ρ for a single UGV is 2k−1. With UAV assistance, and under the simplifying assumption of negligible initial transit and deadheading UAV costs, the ratio ρ improves to 2(k−1)vG+vAvG+1, where vG and vA denote the UGV and UAV speed, respectively. To address general graphs and non-negligible UAV initial transit and deadheading costs, we present an optimal candidate-path partitioning algorithm that assigns path prefix inspection to the UGV and path suffix inspection to the UAV, and prove the optimality of the UAV inspection strategy on general graphs. We evaluate our algorithm by performing experiments on road networks from the world's 50 most populous cities with randomized blockage locations, and show that the algorithm reduces UGV travel time, with larger improvements as the UAV speed increases.
This paper addresses the Dynamic UGV-UAV Cooperative Path Planning (DUCPP) problem involving one unmanned ground vehicle (UGV) assisted by one or more unmanned aerial vehicles (UAVs) operating on an uncertain road network with potentially impassable edges. DUCPP is particularly relevant for scenarios such as disaster response, emergency supply transport, and rescue operations, where a UGV must reach a specified destination in the presence of partially unknown road conditions. To enable the UGV to travel safely and efficiently to its destination, the UAV(s) dynamically inspect edges in the environment to identify and prune damaged or impassable edges from consideration. We present multiple strategies, including a bidirectional approach, to optimize UGV-UAV cooperation for finding a safe path in an uncertain road network. Furthermore, we explore the impact of using multiple UAVs on reducing the UGV's travel time, and evaluate the associated computation time. The proposed strategies are implemented and evaluated on 100 urban road networks. The results demonstrate that the bidirectional strategy achieves the best performance in most instances, and using multiple UAVs further reduces UGV travel time at the expense of increased computation time. This paper presents a robust framework for DUCPP to achieve efficient UGV-UAV cooperation for path planning and inspection, offering practical solutions for navigation in challenging and uncertain conditions.
Ninh Nguyen, Srinivas Akella
Department of Computer Science, University of North Carolina at Charlotte, NC 28223, USA
Multi-robot path planning in human-shared environments requires a delicate balance between robust inter-robot coordination and socially aware behavior. While diffusion models excel at generating predictable, human-like paths, existing generative planners are often restricted to paths of fixed duration and high computational latency, limiting their adaptability to varying goal distances and hindering real-time deployment. We present Multi-Robot Rolling Diffusion (MRRD), a novel framework that enables real-time, long-horizon navigation for large robot teams through dense crowds. MRRD combines a rolling-horizon scheme to accommodate the limited prediction horizon of human motion, parallelized diffusion inference for scalable generation of human-like paths, and a conflict-based-search mechanism for resolving inter-robot collisions. It further incorporates urgency-based temporal conditioning to generate paths with varying speeds and employs differentiated guidance terms to maximize both social awareness around humans and efficient coordination between robots. Experimental results in crowded environments demonstrate that MRRD successfully scales to 15 robots in real-time, significantly outperforming existing baselines in both safety and mission success rates.