EFFICIENT REFORMATION

In this project, we look at groups of vehicles and see how we can derive an efficient transition for them from one formation to the next. First, we formalize the problem statement, and then show how finding efficient formation transitions is analogous to solving instances of James Munkres' assignment problem. Our solution consists of both an implementation of the Hungarian Algorithm and a demo application showcasing some efficient formation transitions.

Table of contents

Problem definition

Let a \(\textit{vehicle}\) be a mobile agent embedded in a plane, and a vehicle \(unit\) be a collection of \(n > 0\) vehicles. A formation \(F: U \rightarrow T\) is a bijection mapping members of unit \(U\) with target positions in \(T\). We say that \(U\) satisfies \(F\) when all members of \(U\) currently occupy the position assigned to them by \(F\).

We now consider what happens when we instruct a unit of \(n\) vehicles to occupy a set of \(n\) target positions \(T\). The question is: what vehicle should be assigned which position? That is to say: which of the \(n!\) possible formations should we choose to satisfy?

Assume that we have in our disposal a function \(C\) that quantifies the cost of choosing formation \(F\), and that we wish to choose \(F\) such that \(C(F)\) is minimized. The first step is to notice that this is an instance of the assignment problem: Matching workers with tasks (as presented in the Wikipedia article) is exactly analogous to our matching of unit members with target positions. If we are able to solve the one, we can solve the other.

The Hungarian Algorithm

The Hungarian Algorithm solves the assignment problem in \(O(n^3)\) time. Its inputs are the two sets to be matched \(A\) and \(B\) (both with size \(n\)), and a cost matrix \(C\) whose member \(C(i, j)\) represents the cost of assigning the \(i\)th item in \(A\) to the \(j\)th item in \(B\). Its output is the bijection \(S: A \rightarrow B\) assigning each member of \(A\) a match in \(B\) such that the total cost of the assignment \(\sum_{i=1}^{n} C(i, S(i)) \) is minimal.

Throughout the algorithm, we will be adding/removing two helper labels from positions in the cost matrix \(C\): "starred" and "primed". We also label rows and columns of \(C\) as either "covered" or "uncovered" (initially, all are uncovered). Lastly, we use \(r(k)\) and \(c(k)\) to denote the members of row/column \(k\) of \(C\), respectively. We now summarize the solution plan in seven steps (paraphrased from here):

  1. For \(1 \le k \le n\), find the minimum in \(r(k)\) and subtract it from all members of \(r(k)\).

  2. Find a zero \(z\) in \(C\) at some row \(i\) and column \(j\). If there is no star in both \(r(i)\) and \(c(j)\), star \(z\). Repeat this step until there are no zeroes left to star this way.

  3. For \(1 \le k \le n\), if \(c(k)\) contains a star, cover \(c(k)\). If this results in \(n\) covered columns, we are done: The starred positions in \(C\) indicate our output bijection, and a starred zero at \(C(i, j)\) indicates \(S(i) = j\). Otherwise, proceed to the next step.

  4. Look for an uncovered zero in \(C\) at some row \(i\). If none exists, go to step 6. If one does, prime it. If there is no star at some column \(j\) in \(r(i)\), go to step 5. Otherwise, cover \(r(i)\), uncover \(c(j)\), and repeat this step.

  5. Let \(C(i, j)\) be the position of the uncovered primed zero found in step 4. Initialize an alternating sequence of primes and stars with \(C(i, j)\). If there is no star in some row \(k\) of \(c(j)\), end the sequence here. Otherwise, add \(C(k, j)\) to the sequence. Then, add the a prime at \(r(k)\) as well. Keep adding stars and primes in this way while they exist. Unstar all stars of the sequence, and star all of its primes. Then, unprime all primes and uncover all rows and column. Go to step 3.

  6. Find the minimum uncovered value \(v\) in \(C\). Add \(v\) to all members of each covered row, and subtract it from all members of each uncovered column. Go to step 4.

Results

We implemented the Hungarian Algorithm in C++. To represent the covered state of rows and columns, we use bit-vectors. To represent the "star" and "prime" labeling of positions, we use the sparse matrix implementation provided by Eigen.

We apply our implementation for our target problem by setting \(A\) to members of a vehicle unit, and \(B\) to target positions of a new formation. Position \(C(i, j)\) in our cost matrix is the distance vehicle \(i\) would need to travel to reach target \(j\). The solution obtained tells us which vehicle should go where. Figure 1 showcases a few solutions for selected transitions.

Figure 1: Our demo includes transitions between a few predetermined formations.

Source code

You can find our implementation of the Hungarian Algorithm here, and the source code for the demo project over here.

See also