Two-mode UAV pipeline inspection as a MAPF benchmark. 30 nodes, five aircraft with heterogeneous endurance, and two operating regimes that rank the same three solvers in opposite orders.
Capstone of the femi-mapf series. Builds on astar-grid, cbs-from-scratch, eecbs-benchmark and lacam-python.
The three earlier repositories measured CBS, EECBS and LaCAM on synthetic grids and found a clean ordering: optimal is slowest, bounded-suboptimal is a good compromise, greedy is fastest and worst.
This one asks what happens when the domain is a real problem with two regimes.
Patrol. Every node gets inspected on a schedule. Planned hours ahead on the ground. Planning time is nearly free; flight time is battery and airframe hours.
Reactive. A sensor trips mid-round. The fleet is airborne, holding for instructions. Every second of planning is a second the anomaly goes unobserved.
The result: the two regimes rank the solvers in opposite orders, and the crossover is measurable.
| solver | flight min | vs best | round min | plan ms | endurance |
|---|---|---|---|---|---|
| CBS | 492 | 1.000 | 196 | 102 | ok |
| EECBS w=1.5 | 492 | 1.000 | 196 | 98 | ok |
| LaCAM | 547 | 1.112 | 208 | 97 | FAIL |
LaCAM's round is 11% longer. That is not the finding. The finding is the last column.
Those extra 55 minutes are distributed across a fleet whose aircraft carry 40 to 120 minutes of endurance, and for two of them the greedy round exceeds the tank. The plan is not more expensive; it is unflyable.
This is what the battery constraint does to the usual quality-versus-speed trade. On a synthetic grid, 11% worse cost is 11% worse. Here it converts suboptimality into mission failure — and it is the reason patrol mode is worth paying optimal-search prices for.
EECBS matching CBS exactly at w = 1.5 is worth noting too: the bound was never binding on these legs, so bounded-suboptimal search cost nothing at all in quality.
Anomalies injected mid-round, one-second response budget, eight anomalies per fleet size.
| fleet | CBS | EECBS w=1.5 | LaCAM |
|---|---|---|---|
| 5 | 14 ms (100%) | 17 ms (100%) | 12 ms (100%) |
| 10 | 651 ms (75%) | 40 ms (100%) | 26 ms (100%) |
| 15 | 1790 ms (0%, 2/8 solved) | 130 ms (100%) | 34 ms (100%) |
| 20 | — (0/8 solved) | 335 ms (100%) | 47 ms (100%) |
| 25 | — (0/8 solved) | 1024 ms (38%) | 59 ms (100%) |
Percentages are anomalies answered inside the budget.
Crossover: 10 aircraft. That is where CBS starts missing the budget and LaCAM still meets it.
At the operational fleet size of five, none of this matters. All three solvers respond in roughly twelve milliseconds and CBS handles both regimes perfectly well. The reactive advantage does not exist at the size this system is specified for.
It would be easy to present the 20-aircraft column as the headline and leave the 5-aircraft row out. The 5-aircraft row is the operating point, so it leads. What the larger fleets establish is where the current approach stops working — which is the useful engineering result, because fleets grow.
EECBS is the interesting middle: it holds 100% of the budget out to 20 aircraft and only degrades at 25. If the fleet doubled tomorrow, bounded-suboptimal search would be the change to make, not greedy search.
CBS, EECBS and LaCAM all assume agents that can fly forever. A 40-minute airframe 25 minutes from its depot has 15 minutes of useful work left, and a plan ignoring that is a list of places the aircraft will crash.
Endurance is added as a separate layer, and that is a real architectural trade worth stating both sides of.
The cost. Battery is checked after planning rather than during it, so a plan can be optimal for sum-of-costs and still infeasible — exactly what happens to LaCAM above. There is no guarantee the replan loop converges to the endurance-optimal schedule.
The reason. Folding battery into the solvers means modifying all three, at which point they are no longer the solvers benchmarked in the earlier repositories and every comparison in this series becomes approximate rather than exact.
Where battery-aware search belongs inside the low level is the open question this benchmark exists to motivate, and it is a better question for having been measured rather than assumed.
Three consequences the model does capture:
- Range is a round trip. A node 30 minutes out is unreachable for a 40-minute aircraft even though it could get there. The 40-minute airframe reaches 13 of 30 nodes; the 120-minute one reaches all 30.
- Waiting costs battery. Rotors turn whether or not the aircraft is moving, so a hover is charged like a transit.
- Diverting can strand an aircraft. The reactive responder is the nearest aircraft that can reach the anomaly and still get home, not simply the nearest.
Each looked plausible, produced output, and was wrong. All three are recorded in code comments at the point they were fixed.
One-cell corridors made the domain unsolvable, not hard. The first version modelled pipeline segments as single-cell lines. A mid-segment cell then has exactly two neighbours: two aircraft meeting head-on cannot pass, and an aircraft parked on its inspection node blocks everything behind it. Every solver timed out, which looked like a hard benchmark and was actually an infeasible one. Real inspection corridors are survey swaths — the aircraft flies a band either side of the asset — so the corridor is now 3 km wide and aircraft can pass.
Assignment by "least slack" was backwards. Assigning each node to the aircraft for which it is hardest sounds like it reserves long-range airframes for far work. It does the opposite: every node within reach of the smallest aircraft goes to the smallest aircraft. The 40-minute airframe received 13 of 30 nodes while the 120-minute one sat idle. Assignment now balances relative utilisation — projected load as a fraction of each aircraft's own endurance.
Sortie distances were estimated from depot-distance differences. That is exact only when both points lie on the same radial branch and badly under-counts cross-branch hops, so sorties were packed with far more work than the tank could take and every aircraft overflew its endurance. Thirty extra Dijkstra runs cost milliseconds and make the estimate exact.
git clone https://github.com/femi-mapf/inspection-mapf.git
cd inspection-mapf
python -m venv .venv
source .venv/Scripts/activate # Git Bash on Windows
pip install -e ".[dev,dashboard]"All four upstream repositories install automatically from GitHub and must be public.
# Describe the network, fleet and range coverage
inspection network
# Plan a patrol round (exit code 4 if it is endurance-infeasible)
inspection patrol --solver cbs --figure examples/tracks.png
inspection patrol --solver lacam
# Respond to one anomaly with all three solvers
inspection reactive --node N32
# Reproduce every table and figure above (about nine minutes)
inspection study --fleet-sizes 5 10 15 20 25 --anomalies 8 --out examplesstreamlit run src/inspection/dashboard.pyThree tabs: network and fleet, patrol planning by solver, and anomaly response with fleet size as a slider so the crossover can be found live. The dashboard computes nothing of its own — every number comes from the same functions the CLI and tests call.
from inspection import PipelineNetwork, RangeTable, assign_by_range, default_fleet, plan_patrol
network = PipelineNetwork.default()
fleet = default_fleet(network)
ranges = RangeTable(network.to_grid(), fleet, network=network)
plan = plan_patrol(network, fleet, ranges,
assign_by_range(network, fleet, ranges), solver="cbs")
print(plan.summary())
# cbs flight= 492 min round= 196 min legs= 8 plan= 102.2 ms endurance=ok
assert not plan.endurance_failuresThe network is a graph embedded in a grid. Corridor cells are traversable, everything else is obstacle, and the result is an ordinary astar_grid.Grid. That is why all three solvers run here unmodified, and why these numbers are directly comparable with the earlier repositories rather than approximately so.
A patrol round is a sequence of MAPF instances. Each aircraft's assigned nodes split into endurance-feasible sorties, and each sortie into legs. One leg is one cbs.MAPFInstance: starts are current positions, goals are next targets.
Every leg is validated by cbs.validate — the same function used throughout the series, not a checker written for this domain.
Sortie ordering is nearest-neighbour and not optimal. There is a travelling-salesman problem underneath and a proper tour would be shorter. It is left greedy deliberately: the comparison is between MAPF solvers on identical legs, every solver receives the identical sortie structure, and improving the tour would lower all three flight times together without changing any conclusion.
Units are physical. One cell is 1 km, one timestep is one minute — a fixed-wing UAV at 60 km/h. That is what makes 40/60/90/90/120-minute endurance mean something.
pytest
ruff check src tests
mypy104 tests, 93.4% coverage. The build fails below 90%.
Highlights: every node proven reachable; the one-cell-corridor failure captured as a regression test; endurance overflight and stranded-return both caught; assignment proven balanced and range-respecting; every patrol leg validated; the optimal round proven endurance-feasible; all three solvers exercised in both regimes; and the responder proven to be one that can reach the anomaly and get home.
The Streamlit dashboard is excluded from coverage. It is a presentation shell over functions checked strictly elsewhere, and driving Streamlit from pytest would test Streamlit rather than this project.
| repository | role | guarantee |
|---|---|---|
astar-grid |
single-agent A*, instrumentation, benchmark I/O | optimal |
cbs-from-scratch |
constraint tree, optimal baseline | optimal |
eecbs-benchmark |
focal search, EES | cost ≤ w × optimal |
lacam-python |
configuration-space DFS, PIBT | complete only |
inspection-mapf |
two-mode inspection benchmark | — |
Sturtevant's framing was that the challenges of a particular problem determine which strategy is useful. This benchmark's answer is that a single problem can contain both strategies at once:
- Patrol wants best-first search that proves a lower bound and works up. Suboptimality there is not a discount, it is an unflyable plan.
- Reactive wants depth-first search that finds a solution and improves it — past ten aircraft, nothing else answers in time.
Which makes the open question not which to choose, but where the handoff belongs and what a planner switching between them would have to guarantee across the boundary.
MIT. See LICENSE.