Of the current offer by School 42, Fly-In is perhaps an underrated subject. My personal opinion is that, by the time of this writing, the way this project is evaluated barely scratches the surface of what you can actually learn from it.
However, I have found that the core problem this exercise simulates mirrors highly relevant, modern industry challenges, where more robust and informed approaches offer a significant advantage.
My purpose, then, is to explore and discuss this project through a broader lens—focusing on the additional skills we can learn to help us grasp the real-world complexities of these kind of engineering challenge.
To accomplish that goal I will research various methodologies found in available literature and explore existing repositories, including those kindly made public by fellow School 42 students.
Please note that my quest is not intended to judge or critize the work by others; rather, it is about an opinionated best effort to create a curated selection of what appears to be best practices for this kind of problem.
I expect to document my quest on two different places:
- this repository,
- blog's articles, mostly posted on my blog, [https://evaristoc.github.io/re-versing], but also Medium and other online publications.
This repository will be dedicated to host the different ways to approach the Fly-In project that IMO tend to offer the most relevant learnings, and discuss the techniques on the light on existing formal knowledge.
The various solutions will be documented on dedicated folders and might be based on solutions provided by others. To ensure originality and respect other people's code, I will try to replicate their approaches by writing my own versions.
Each folder could contain a README.md with a discussion of the version and its origin, crediting the source when possible.
When not able to make my own version, I will rather discuss the project in a dedicated article instead.
Be aware that the whole repository is a live one, so structure and or content could change without notice.
| Folder | Hightlights |
|---|---|
| v1-hop_based | A solution based on the priority planning method with simplified capacity (capacity always 1). This is a time-expanded solution. Individual drone (aka agent) routes are estimated using the A* algorithm, which takes hop-based heuristic costs from a "distance" table built using a Bellman-Ford-ish algo. Under this assumption, this project reached global optima for all the mandatory exercises, but failed to cope with some custom patterns that deviated from the typical distribution of the mandatory ones, or when modified capacities of the mandatory exercises implied a different expected global optimum. |
| v2-capacity_heuristic_low_traffic | The same priority planning method as before but featuring capacity handling. The registry of the zone use is called "constraint" but they are actually reservations, for which only the number of occupying agents is of use. Similarly to the previous one this one also makes use of a "distance" table built from a Bellman-Ford-ish algo, but with heuristic costs based on a custom capacity-centric calculation inspired in the min-cost max-flow rationale, albeit one that favours low capacity / low traffic regions. This project solves all the mandatory exercises correctly and under the highest score limit, although sometimes slightly sub-optimal for at least one of the "hard" problems (couple of steps more than exact optimum but still under lower limit). It also failed in finding optima for custom graphs involving routes that splitted into high-capacity routes of few steps and low-capacity routes of many steps, favouring the latter. Optimal behaviour from some of the graphs, as shown from the only mandatory that showed to be sub-optimum, might improve when allowing for small manipulations of some of the capacities at configuration, evidencing the importance of clearly understanding the scope of the parameters to find potential adjustments. The project offers insights about the difficulties in capturing the scope of these methods when the number of factors affecting the "cost" calculation increases as well as the challenges of finding strictly admissible and consistent heuristics. |
| v3-capacity_heuristic_high_traffic | Almost exactly the same as the previous one, except for small modifications to the heuristic calculation so it favours high capacity / high traffic regions instead. This project can solve some custom graphs better than the previous version as well as result in global optima without modifying configurable conditions for most of the mandatory exercises, but largerly fails in solving the "impossible dream" exercise, evidencing the sensitivity of the heuristics (and the solving methods in general) to domain-specific conditions. |
| v4-dijkstra | This iteration of the priority planning introduces a fair modification to the agent's pathfinder, shifting it toward an optimized Dijkstra's algorithm that uses waiting ticks as the core metric for "distance" calculation. Due to the project's implementation framework, Dijkstra's algorithm computes distances between time-based states. These states are also subject to constraints imposed by other agents occupying the zones at those specific times, making the entire pathfinding process strictly time-expanded. This project behaves the same as version v3. |
| v5-cbs_hop_based | This is a working draft of an approach to CBS (constraint-based search) method, for simpler Fly-In requirements. CBS was indeed my first idea for Fly-In before submitting a simpler priority planner. In this iteration, the low-level planners implement the Dijkstra of previous version. High level planner implements a best first search on a binary tree of branched constraint nodes, optimized by a very simple pruning by node cost. This version only verify zone conflicts and capacities are all set to 1. RELEVANT: Differently to the previous priority planner techniques, this CBS makes use of constraint entities not as reservations but as forbidden entries. This project helped me to get into a more advanced method to solve this problem, but also reminded me of some of the nuances of working with OOP and the importance of keeping a good track of instances. IMPORTANT NOTE: naive CBS as this one can be optimal but very inefficient; so far I have not tested it for very large datasets, including the challenger. |
| v6-cbs_capacities | This is the same as v5 except that the conflict detection function accounts for zone / edge capacities. It was found that some of the requirements of the Fly-In, such as capacities for zones and edges constraints, might not correspond with classical cases of the CBS method. But there was always an effort to respect the cbs framework. Again, this is a naive CBS implementation so be aware of inefficiencies, specially with very large or complex datasets. |
| v7-departure01 | Departures are versions dedicated to the refactoring or to adding features not strictly related to the solution itself. In this departure I focused on making the code more scalable and modular, in order to facilate the morphing of the original code base into different solutions of the Fly-In problem. As a result, I got a first draft of a version that can handle two of the Dijkstra versions, priority planner (v4) and cbs (v6), with only few modifications. In this version v7, the definition of classes and folder structure are both very different to previous ones. There was also extra care to solve some of the mypy errors. The results point toward a highly flexible time-based agent modelling application, in which users can configure components such as agent selection policies, cost functions, heuristics, algorithm choices, planning methods, and graph structures, with the potential to evolve into a framework similar in spirit to projects like Mesa, supporting advanced agent-based modelling (ABM) approaches and extensible simulation design. For now this project would stay restricted to the scope of the Fly-In, although the idea is to explore its potential beyond that scope. |
The articles will sometimes replicate the READMEs of the folders, enhanced with extra visualizations when applicable.
I will also use the articles to dive into very specific topics uncovered during my quest - for example especific situations only related to the Fly-In project, or practical insights found during the implementations that lack extensive documentation and that might be worth mentioning. I will refrain from discussing concepts that are already well-documented and accessible, opting instead to provide direct links to reference material.
In other articles I might include discussions of repositories and codebases that I consider valuable to analyze but I might not replicate for one or another reason.
Other topic for the articles could consist in the discussion of real-world applications that I hope will whet the reader's appetite by showing cases supporting a deep dive into the techniques applicable to assignments like Fly-In.