Further optimize st-a* true heuristic

[Elucidation]

check that true heuristic weighting appropriately causes A* to go along path without branching out more than necessary

[Elucidation]

Right now the score is based solely on the heuristic, which isn't exactly A but more of a optimized DFS that when using the true heuristic becomes A with no obstacles (since the true heuristic is A*).

[Elucidation]

Collecting some logs from before/after the change, we can see

Local test run scatter plot comparing # of cells visited versus duration of generate path (ms) before and after change 455576f shows that despite the number of cells visited increasing, the overall search time decreases.

This is a bit counter-intuitive, as I'd expect total search time to be positively correlated (linear or quadratic) with number of cells visited. On further inspection, looking at path length we see our answer

Here, clearly path length is strongly correlated with total generate path time.

It looks like with the proper scoring system, we no longer fall into extremely!! (1000+) long path length searches from before vs after. This means before with our DFS-like search we were getting trapped in long crazy routes when trying to follow the true heuristic, since st-astar allows searching with no motion except time, likely this involves paths where the robot waits in place for long periods of time until the true heuristic path is available.

We can see this in the histograms of generate_path times before/after

[Elucidation]

Changes pushed to GCE instance at 11:30am and running for a couple hours, we see a dramatic improvement in generate path times as expected (top-left heat 2D histogram in logy mode). The rate at which items are being added appears to be slightly better (~0.53/s vs ~0.51/s), CPU utilization after the change spike has returned to better than before

Notably, the memory used doesn't appear to have changed

[Elucidation]

The improvement here is drastic, the 99th percentile of generate_paths has dropped from ~80ms to ~5.5ms, more than a 10x improvement.

This means 99% of the time up to 90 robots could be processed at once, and in practice more. This will allow us to start scaling up the size of the warehouse.

It doesn't appear the mean time has increased either, despite the number of visited cells likely increasing. The benefit of optimal paths outweighs the DFS-like nature of the previous algorithm dramatically.

[Elucidation]

Running on dev machine, can easily scale up to ~220 robots, after the front-loaded path-finding, which scales at around ~30 path searches per ~100ms (the arbitrary threshold used), it is able to run all 220 robots per cycle since not every robot is searching for a path at the same time. This comes out to a mean ~3.3ms per generate path, at the initial bump.

2023-06-19 12:36:27 2023-06-19 19:36:27,719 - robot_allocator - INFO - update end, took 116.401 ms, processed 30/222 jobs, assigned 0/0 available robots to 1 available tasks

Because the path finding duration is much more stable and low now, this sets the stage for parceling out processing tasks to worker nodes to scale up for larger quantities of robots nicely.