Technical Whitepaper

Robust Path Planning in the Battlefield

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.

Graph Theory and Isochrone Maps

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.

Region-Based Robustness Algorithm

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).

Multi-Objective Optimization

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.

Performance and Efficiency

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.

Conclusion

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.

Download the full Whitepaper