Mission Planning and Dynamic Re-planning

UAVs, increasingly vital to the success of military operations, operate in a complex and dynamic environment, sometimes in concert with manned aircraft.  An extensible modeling framework for the solution to the dynamic resource management (DRM) problem is demonstrated, where airborne resources must be re-assigned to time-sensitive tasks in response to changes in battlespace conditions.  The DRM problem is characterized by diverse tasks with time windows, heterogeneous resources with fuel- and payload-capacity limitations, and multiple competing objectives.  An integer linear programming (ILP) formulation for this problem is provided.  Although motivated by airborne military operations, the general modeling framework is applicable to a wide array of settings, such as disaster relief operations.  Additionally, land- or water-based operations may be modeled within this framework, as well as any combination of manned and unmanned vehicles.  This research was sponsored by AFOSR and ONR.

An “intelligent” branch-and-bound solution approach for the problem of dynamically re-routing UAVs in response to pop-up threats was proposed in a recent paper.  This approach solves the dynamic resource management problem in a timely fashion, a critical feature because in-flight assets must be quickly re-tasked to respond to the changing environment.  This procedure features three key components: (1) a technique for reducing the solution space, (2) support for branching on multiple decision variables simultaneously, and (3) the incorporation of additional valid cuts to strengthen the minimal network constraints of the underlying mixed integer linear programming model.  In this model, decision variable xtvij = 1 if UAV v is assigned to travel along a path connecting targets i and j, arriving at j at some discrete time t.  The solution approach leverages this decision variable definition by generating UAV routes that start from each UAVs current location.  Thus, the choice of a branching variable is based on a candidate set of next-destination nodes.

The procedure begins with a solution space reduction technique that limits the number of candidate arcs for each UAV in the updated mission plans.  An example of the solution space reduction approach is shown in Figure 1a, where a pop-up target (node 7) appears at time 3.  Bracketed numbers above each node represent the allowable time windows, while numbers below nodes represent the time at which the UAV was initially assigned to begin service at that node.  The reduced solution space is represented in Figure 1b, where node j is shown as a dark square if j is a candidate destination. Node 5 is not included in this set because it lies outside of the shaded area formed by overlapping circles of a variable size.  Note that, although node 6 lies within the shaded area, its time window does not intersect the windows for nodes 1 and 2.

Initial assigned route for the UAV. Tasks 4–6 were initially assigned to other UAVs.

Figure 1a: Initial assigned route for the UAV. Tasks 4–6 were initially assigned to other UAVs.

The UAV’s candidate targets, shown as square nodes, were determined by the solution space reduction approach.

Figure 1b: The UAV’s candidate targets, shown as square nodes, were determined by the solution space reduction approach.

Thus, the proposed solution space reduction approach takes into account the spatiotemporal aspects of the initial mission plan by including tasks that are “near” the initial route and also have time windows that overlap the time windows of the nodes contained in the initial route.  It should be noted that for circles of a small radius, the UAV may visit only initially-assigned targets and pop-ups; as the radius increases, additional targets become eligible for assignment. Our solution approach dynamically varies the size of these circles.

Next, with a tightened solution space, the intelligent branch-and-bound procedure commences by solving the LP relaxation of the modified problem.  The LP relaxation will likely result in many fractional arcs that would call for portions of each UAV to be split across numerous arcs (or possibly along the same arc at different times).  Our approach uses a guided tree search to build each UAV’s path forward through the network, starting at the UAV’s initial location and terminating at a base node prior to exhausting its fuel supply.

In the branching process, the “left” branches in the branch-and-bound tree correspond to the assignment of a UAV to an arc, whereas the “right” branches correspond to the prohibition of the UAV from taking said arc at any time.  The exact nature of each assignment is determined by the task type of the destination node in the candidate arc. Unlike standard branch-and-bound approaches, in which a nonzero decision variable is selected, our approach may select a decision variable with a value of zero in the LP relaxation.  In this assignment branch, a selected UAV is forced to travel a certain arc.  Depending upon the task type, the assignment may be at the earliest feasible time, or it may be over a range of times.  As each arc is assigned, additional valid cuts are added to strengthen the network constraints.  These cuts are motivated by the relative weakness of the network formulation.  Although the network formulation is valid, it is designed to be minimal, thus requiring fewer constraints to define the still-sizable model.  The advantage of this approach is that the model may be generated more quickly.  The obvious drawback is that the LP relaxation is not as tight.  However, by adding constraints on an as-needed basis, the network constraints are strengthened in a more efficient manner, thus reducing the number of redundant constraints.

One of the key features of the branching rules is that decision variable assignments that occur during the branching process do not require the selection of a decision variable containing a nonzero fractional value in the LP relaxation.  Instead, the branching rules use the LP relaxation to find candidate arcs between nodes in the network, and then the appropriate UAV is routed to the next node at the earliest feasible time. As a result, the effective solution space is reduced.  Additionally, rather than setting a single decision variable value equal to zero when taking the “right;’ (prohibit) branch in the branch-and-bound tree, the approach prohibits a UAV from taking an arc at any time.  Numerical analysis indicates that this approach outperforms CPLEX on a set of realistically sized problems and provides improved solutions in a limited time.

An overview of the branch-and-bound algorithm is provided in Figure 2, where multiple rules are used to determine the selected branching variables, the size of the circles used to identify candidate targets for each UAV, and the preferences for utilizing the initial mission plan versus maximizing overall mission effectiveness by generating new routes for each UAV are varied according to the solution quality.

Algorithm flowchart

Figure 2: Algorithm flowchart

An extensive numerical analysis indicated that this approach significantly outperforms traditional branch-and-bound methodologies and is capable of providing improved feasible solutions in a limited time.  Although inspired by the dynamic resource management problem in particular, this approach promises to be an effective tool for solving other general types of vehicle routing problems.

References: