In modern combat scenarios, autonomous vehicles play a crucial role in navigating complex environments. Effective path planning is essential to ensure these vehicles can reach their destinations quickly and safely, even when faced with unexpected obstacles.
Traditional path planning methods focus primarily on speed, but they often fail to account for disruptions that can block the planned route.
This paper introduces robustness as a key factor in path planning – measuring a route’s ability to adapt to obstacles. By incorporating robustness into path planning, we can create routes that are not only fast but also resilient, providing viable alternatives when obstacles arise. This approach uses advanced algorithms and visual tools to help military planners optimize their missions and improve the reliability of autonomous vehicles in the battlefield.
This highly technical paper was originally presented at the 2023 Ground Vehicle Systems Engineering and Technology Symposium (GVSETS) in the US.
Authors: Thomas Jonsson Damgaard, Mikael Rittri PhD, Patrick Franz, and Anika Halota from Carmenta Geospatial Technologies.
Autonomous vehicles rely on path planning to guide them towards their destination. These paths are susceptible to interruption by impassable hazards detected at the local scale via on-board sensors, and malicious disruption.
We define robustness as an additional parameter which can be incorporated into multi-objective optimization functions for path planning. The robustness at any point is the output of a function of the isochrone map at that point for a set travel time.
The function calculates the sum of the difference in area between the isochrone map and the isochrone map with an impassable semi-circle hazard inserted in each of the four cardinal directions. We calculate and compare two different Pareto paths which use robustness as an input parameter with different weights.
The paper applies graph theory and isochrone maps to path planning, introducing the concept of penalty time – the additional travel time required when rerouting due to obstacles. The shrinking behavior of isochrone areas when disruptions occur is central to understanding robustness.
We also explore the duality gap between the shortest path problem and the shortest path tree problem, to connect the understanding of penalty time to maneuverability. This allows us to predict vulnerabilities in the operational areas such as chokeholds, that should if possible be avoided or at least minimized during missions.
The authors propose a region-based robustness algorithm that measures fragility by incorporating no-go zones in cardinal directions. Robustness is defined as the sum of the difference in area between the isochrone map and the isochrone map with an impassable hazard inserted in each cardinal direction.
The algorithm generates a robustness cost map to support path planning decisions, ensuring routes account for potential disruptions.
Figure: An isochrone map originating at the red vertex and bounded by the pink outline (graph edges not shown).
Balancing robustness with travel time requires multi-objective optimization. Pareto-optimal paths represent solutions that maximize both speed and resilience, giving mission planners a set of viable alternatives.
Heat maps visualize robustness across a region, highlighting areas where disruptions would significantly increase travel time. By comparing maps generated with different obstacle sizes, planners can adjust robustness parameters to suit mission needs.
Generating robustness maps requires significant processing time but is feasible for mission planning. Once generated, these maps can be reused for various path planning processes.
One challenge is that robust paths often divert toward open areas, potentially increasing exposure risk. To address this, we propose integrating exposure as a third objective in optimization, balancing resilience with stealth.
Figure: Two routes visualized on a region-based robustness heat map. The heat map’s coloring ranges from green (good robustness) to red (poor robustness).The blue route values travel time higher while the pink route values robustness higher. As the blue route enters red and yellow areas (denoting poor robustness) the pink route avoids the areas by diverting through terrain and avoids narrow city roads.
Robustness is identified as a valuable parameter for autonomous vehicle path planning, with pre-generated robustness maps and operator judgment being crucial for mission planning. Robustness enhances path planning by providing viable alternatives in case of disruptions. Combining robustness with travel time in multi-objective optimization allows for balanced and effective route planning in mission-critical applications.
For a detailed exploration of these concepts, read the full paper: Robust Path Planning in the Battlefield.
Military last-mile resupply using UAS technology with geospatial analysis. Real-time geospatial analysis for UAVs can be used to cope with dynamic challenges, enhancing situational awareness on the battlefield and supporting both human and autonomous decision-making.
Read more
Watch our on-demand webinar about the crucial role of supply lines in the battlefield. Deep dive into the intricacies of determining the best rendezvous points in a resupply mission, taking into account the various threats that exist.
Read more
Resupply missions are critical logistical components of modern warfare. Supply vehicles carrying fuel and ammunition are high-value targets, making the choice of route sensitive to both risk and delivery time. Read our latest whitepaper here.
Read more