Mitigate scaling effects of number of USSs on uss_qualifier test time

[BenjaminPelletier]

(note: I'm reporting this Issue as a member of the US UTM Implementation Technical Committee rather than as a part of InterUSS)

Is your feature request related to a problem? Please describe.
The US UTM Implementation has been using uss_qualifier to verify compliance to ASTM F3548-21 strategic coordination requirements as part of a software quality assurance plan for some time now. Recently, however, test times have grown large (~2.5 hours) as the number of participants has increased (now at 10). Test time is dominated by conflict_equal_priority_not_permitted and conflict_higher_priority primarily because of the number of combinations of USSs that need to be tested.

Describe the solution you'd like
Change uss_qualifier behavior so that test time scales no more than linearly with number of participants. Ideally, a soft target would be roughly an hour to perform the tests currently requiring ~2.5 hours.

Describe alternatives you've considered
A test configuration could sample a subset of USS pairs when testing. However, the pairwise tests do seem to be useful as a number of issues have been discovered between only one specific pair of USSs playing specific roles; therefore subsampling would run the risk of missing important behavior.

USS participants could be required to have more performant systems, but this would be a large burden on the participants and would presumably only make a marginal difference in headroom for the number of USSs that could be tested in a given test duration.

[BenjaminPelletier]

The only approach I have in mind that has a good potential to achieve a time reduction of the magnitude mentioned is running test scenarios in parallel. I think this may be easiest with repetitive scenarios, like running the 100 instances of the same conflict_equal_priority_not_permitted scenario with participants filling different roles.

Parallelization enabler: resources modifier

It seems like perhaps not a huge lift to introduce a "resources modifier" concept that an action generator could use to adjust provided resources differently for each action generated. So, for instance, there could be a resources modifier that modifies a FlightIntentsResource by translating everything to a new location according to action index. Perhaps a user might specify 10km spacing, causing the first action to run with the original resources, the second action to run with resources offset 10km to the east, the third with resources offset +10km east, +10km north, the fourth with offset 0, 10, the fifth with -10, 10, the sixth with -10, 0, and so on continuing the square spiral pattern.

Parallelization of action generators

With a resources modifier that ensures geospatial separation of test actions, I believe those actions could then be performed in parallel fairly straightforwardly. We could make a ParallelActionGenerator that forks the original process once for each action, and then the original process waits for all forks to finish and coalesces the results before continuing with the rest of the test in the original process. I think this has the advantage that we wouldn't need to transition our fairly-sizable requests infrastructure to async (although that would be the obvious choice if starting fresh). Though, it does have the disadvantage of the overhead of so many processes. This could be limited by limiting the size of the multiprocessing pool, but the maximum pool size may be appreciably smaller with this approach than could be achieved by a performance-optimal approach.

Parallelization in general

This could perhaps extend beyond action generators to all test actions. I think this extension would suggest changing our test action collections from lists (as they are now) to graphs. For most of our scenarios, I think this would be fairly seamless. But, there are a few scenarios that depend on other scenarios having been run in order to succeed (e.g., the aggregate analysis scenarios), so we would need some way of expressing and respecting that dependency when test scenario execution order could no longer be easily flattened to a time-sequential list.

I think there may be a few assumptions that scenario B start after scenario A ends in a few of the artifacts (particularly the sequence view index), but it seems like those should not be particularly difficult to overcome. And, I think we would still want the test scenarios identified in a deterministic, ordered way even if they ended up being executed in a different chronological order.

Challenges

This raises a few challenges and risks. First, we don't always achieve separability between test scenarios: when a test scenario fails, it sometimes results in conditions that cause later test scenarios to fail as well, not because of actual non-compliance but because prerequisite assumptions about the later tests were violated by changes in the test environment caused by the earlier tests. This is not a particularly bad problem currently because we can always advise to inspect and resolve the first failure first since it can impact later tests. However, with chronological nondeterminism, it would be harder to distinguish the true original failure from the downstream failures. Second, there are far more ways for things to go wrong in the execution of the test when we're trying to manage parallel processes than if we stick to simple sequential logic.

I think the first challenge may be substantially mitigated by the parallelization prerequisite of geospatially decoupling the test scenarios. Currently, a major downstream failure cause is resources from a prior test not being cleaned up. If the tests are already geospatially decoupled, then not cleaning up resources won't cause downstream failures. This isn't universally true unless all tests are geospatially decoupled from each other, but it's at least some substantial level of mitigation from the current state.

Implementation thoughts

Universal geospatial resource separation

The resources modifier might become much easier to write and be much more broadly applicable if we established a GeospatialResource interface something like:

class GeospatialResource(ABC):
    @abstractmethod
    def get_extents(self) -> LatLngBoundingBox:
        raise NotImplementedError()

    @abstractmethod
    def move(self, meters_east: float, meters_north: float) -> Self | None:
        raise NotImplementedError()

Then, a fairly generic resources modifier could easily geospatially deconflict every resource implementing that interface, even while doing some fancier things like staying inside a country or region boundary.

Abstract dispatch

In order to parallelize using any of the approaches above, we will need to be able to transfer relevant state to a worker, and retrieve results and any state changes from that worker at completion. If we merely fork a process, this transfer is extremely easy as long as there aren't any state changes (to, e.g., resources) that need to be imported back into the coalescing process. Other than resource states, I don't think it is that much more difficult if all state provided to the worker must be serialized. If we could also serialize resource states, I think we could serialize the entire request for the worker, and this would allow us to easily expand well beyond a single machine to fulfill a single uss_qualifier test run.

It seems like a change that would easily enable the above would be to instantiate resources at the start of each scenario instead of instantiating resources once at the beginning of the test run. From a quick pass through our resources, I don't think there are any that would strongly resist this paradigm change.

[barroco]

The options look great. Agree on starting with the ParallelActionGenerator since it probably the best candidate to stay close to the isolation assumption of scenarios. (USSPs may still get some interactions from DSS subscriptions but I think it is ok). Agree as well on the complexity to troubleshoot if too many tests are run in parallel. Keeping the ability to fine tune the complexity in terms of parallelism and load on the eco-system will be a key feature in addition to keeping track of the parallel executions in the report to allow users to correlate possible side effects and define appropriate performance requirements.

[the-glu]

For the tracking and avoid duplicate work:

I'm starting working on geospatial separation

[the-glu]

I'm starting working on geospatial separation

Done in #1465, #1467 and #1468

[the-glu]

I'm starting to work on ParallelActionGenerator

[the-glu]

Done in #1470