-
Notifications
You must be signed in to change notification settings - Fork 3
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Further optimize st-a* true heuristic #91
Comments
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*). |
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. We can see this in the histograms of generate_path times before/after |
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). Notably, the memory used doesn't appear to have changed |
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. |
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. |
check that true heuristic weighting appropriately causes A* to go along path without branching out more than necessary
The text was updated successfully, but these errors were encountered: