Technical Whitepaper:

Risk-adaptive Rendezvous Planning for Resupply Missions in the Battlefield

Resupply missions are critical logistical components of modern warfare. Supply vehicles carrying fuel and ammunition are high-value targets, making the choice of route to approach such a mission sensitive to both risk and delivery time.

Addressing the Challenge of Secure Path Planning

In this highly technical paper recently presented at GVSETS in the US (the Autonomy, Artificial Intelligence & Robotics Track), we address the problem of a supply vehicle that needs to find a secure path to link up with a mobile frontline unit on a fixed itinerary.

Introducing the Adaptive Intercepting Path Planning (AIPP) Algorithm

The paper presents a resupply path planning algorithm developed by Carmenta, called the Adaptive Intercepting Path Planning (AIPP) algorithm. This algorithm balances risk and travel time to identify the most suitable rendezvous point among several options, generating the least risky route that meets the rendezvous deadline.

Figure: The AIPP algorithm has found the safest path by choosing the most suitable rendezvous point.

Graph Theory Application in Route Evaluation

Using graph theory, a cost matrix is produced that evaluates each possible decision when traversing an operational area. Travel time is assessed based on vehicle model, terrain, road network, and risky areas – defined as a geographical area that the vehicle should avoid if possible – using a penalty system.

Combining Optimization Methods for Route Selection

From the theory of multi-objective optimization, the linear scalarization method and the epsilon constraint method are combined with multiple layers of individual cost matrices. This approach generates a set of possible Pareto routes to choose from.

Figure: Pareto front with the additional deadline vertical line. Any Pareto path to the right of the line is considered tardy while anything on the left is punctual.

Enhancing Performance with the Shortest Path Tree Problem

To speed up the evaluation among the many possible rendezvous points, the shortest path tree problem is employed, generating all possible routes from the supply vehicle’s current location within a defined a search area. If large enough, this area covers all rendezvous points from which routes can later be reconstructed again, dramatically increasing performance.

Bisection Iteration for Optimal Path Identification

Using bisection iteration, the AIPP algorithm successfully identifies the least risky route to the optimal link-up point that also meets the rendezvous deadline. Alternatively, the AIPP algorithm can produce a set number of alternatives, each presented with an estimated time of arrival and threat exposure time, outlining challenges along the route.

Figure: AIPP results using safety factor s = 1/2, iteration three. 

Effective Path Planning in Dynamic Battlefields

This presented method is highly effective when operating in a dynamic, ever-changing environment like the modern battlefield, as it automatically suggests the optimal path while minimizing time spent in risky areas. The approach ensures that the operational user is not overwhelmed by an excessive number of computer-generated paths, as can happen with multi-objective path planning algorithms without deadlines.

Download the full Whitepaper