Scaling to larger warehouse sizes (more robots, zones, etc.)
As the warehouse and number of robots increase, the complexity of the path planning problem increases as well, and potentially exponentially along the lines of O((NxM)**2 * R) where NxM is warehouse size and R is the number of robots, as the number of robots increase there is an increase in the complexity of the search with more dynamic obstacles, but for the current mapf1 st_astar algorithm which solves per robot in order, it is still linear.
Tracking a run over a world size of NxM =(42, 48) with R = 88 robots, 96 item zones, 52 stations running for a little over 3 hours, all calls to generate_path where put on a log histogram which shows the mean time was around 7.7ms, with the worst happening only once at 162ms.
Tracking a run over a world size of NxM =(42, 48) with R = 88 robots, 96 item zones, 52 stations running for a little over 3 hours, we had 1 collision where 2 robots ended up on top of each other around step T=262 of 11,425, at
2023-05-16 11:16:02,341 - world_sim - ERROR - World State invalid, collision(s): {13: [(15, 14), (15, 14)], 0: [(15, 14), (15, 15)], 'type': 'Robot overlap collision'}
The system was able to recover from that, having the robots path out from each other to continue, and it contiun
2023-05-16 11:16:01,420 - robot_allocator - INFO - Starting job Job [Robot 9, Task task:station:5:order:5:22:0: Progress OPEN, P 53 0 0 for Robot 9
2023-05-16 11:16:01,421 - robot_allocator - DEBUG - Robot 68 not yet to item zone (27, 15) -> (28, 14)
2023-05-16 11:16:01,421 - robot_allocator - DEBUG - Robot 73 not yet to station zone (11, 17) -> (1, 23)
2023-05-16 11:16:01,421 - robot_allocator - DEBUG - Robot 59 not yet to station zone (20, 15) -> (16, 22)
2023-05-16 11:16:01,421 - robot_allocator - DEBUG - Robot 33 not yet to robot home (16, 20) -> (35, 1)
2023-05-16 11:16:01,421 - robot_allocator - DEBUG - Robot 39 not yet to item zone (31, 2) -> (19, 14)
2023-05-16 11:16:01,421 - robot_allocator - DEBUG - Robot 83 not yet to item zone (36, 39) -> (27, 17)
2023-05-16 11:16:01,421 - robot_allocator - DEBUG - Robot 2 not yet to robot home (1, 23) -> (4, 1)
2023-05-16 11:16:01,421 - robot_allocator - DEBUG - Robot 51 not yet to item zone (9, 40) -> (20, 14)
2023-05-16 11:16:01,437 - robot_allocator - INFO - generate_path took 14.147 ms
2023-05-16 11:16:01,437 - robot_allocator - INFO - Sending robot 13 to station for task task:station:21:order:60:7:1
2023-05-16 11:16:01,438 - robot_allocator - DEBUG - Robot 24 not yet to station zone (45, 34) -> (46, 34)
2023-05-16 11:16:01,438 - robot_allocator - DEBUG - Robot 62 not yet to item zone (22, 36) -> (36, 14)
2023-05-16 11:16:01,438 - robot_allocator - DEBUG - Robot 37 not yet to robot home (39, 6) -> (39, 1)
2023-05-16 11:16:01,438 - robot_allocator - DEBUG - Robot 45 not yet to item zone (9, 15) -> (10, 14)
2023-05-16 11:16:01,438 - robot_allocator - DEBUG - Robot 46 not yet to station zone (31, 21) -> (41, 22)
2023-05-16 11:16:01,440 - robot_allocator - INFO - Task task:station:48:order:48:8:2 complete, Robot 82 successfully dropped item
2023-05-16 11:16:01,440 - robot_allocator - DEBUG - Robot 48 not yet to robot home (6, 38) -> (6, 40)
2023-05-16 11:16:01,440 - robot_allocator - DEBUG - Robot 26 not yet to robot home (2, 3) -> (28, 1)
2023-05-16 11:16:01,440 - robot_allocator - DEBUG - Robot 40 not yet to station zone (6, 16) -> (28, 22)
2023-05-16 11:16:01,440 - robot_allocator - DEBUG - Robot 34 not yet to robot home (39, 11) -> (36, 1)
2023-05-16 11:16:01,440 - robot_allocator - DEBUG - Robot 80 not yet to station zone (24, 16) -> (4, 19)
2023-05-16 11:16:01,441 - robot_allocator - DEBUG - Robot 77 not yet to robot home (17, 29) -> (35, 40)
2023-05-16 11:16:01,441 - robot_allocator - DEBUG - Robot 8 not yet to item zone (8, 13) -> (9, 17)
2023-05-16 11:16:01,441 - robot_allocator - DEBUG - Robot 19 not yet to station zone (33, 16) -> (1, 18)
2023-05-16 11:16:01,441 - robot_allocator - INFO - Robot 32 item picked 45
2023-05-16 11:16:01,441 - robot_allocator - DEBUG - Robot 6 not yet to robot home (8, 17) -> (8, 1)
2023-05-16 11:16:01,441 - robot_allocator - DEBUG - Robot 20 not yet to robot home (22, 12) -> (22, 1)
2023-05-16 11:16:01,441 - robot_allocator - DEBUG - Robot 0 not yet to item zone (15, 15) -> (15, 14)
2023-05-16 11:16:01,441 - robot_allocator - DEBUG - Robot 7 not yet to item zone (34, 15) -> (38, 14)
2023-05-16 11:16:01,441 - robot_allocator - DEBUG - Robot 55 not yet to station zone (14, 17) -> (4, 22)
2023-05-16 11:16:01,441 - robot_allocator - DEBUG - Robot 86 not yet to station zone (2, 31) -> (1, 37)
2023-05-16 11:16:01,441 - robot_allocator - DEBUG - Robot 60 not yet to item zone (18, 40) -> (14, 17)
2023-05-16 11:16:01,441 - robot_allocator - INFO - Robot 43 item picked 40
2023-05-16 11:16:01,441 - robot_allocator - DEBUG - Robot 72 not yet to station zone (8, 19) -> (16, 19)
2023-05-16 11:16:01,441 - robot_allocator - DEBUG - Robot 17 not yet to station zone (40, 16) -> (9, 22)
2023-05-16 11:16:01,441 - robot_allocator - DEBUG - Robot 14 not yet to robot home (10, 19) -> (16, 1)
2023-05-16 11:16:01,442 - robot_allocator - DEBUG - Robot 29 not yet to robot home (13, 8) -> (31, 1)
2023-05-16 11:16:01,442 - database_world_manager - DEBUG - 'update_robots' Start
2023-05-16 11:16:01,446 - database_world_manager - DEBUG - 'update_robots' End. Took 4.307 ms
2023-05-16 11:16:01,446 - robot_allocator - INFO - update end, took 103.594 ms, processed 88/88 jobs, assigned 0/0 available robots
2023-05-16 11:16:01,446 - robot_allocator - DEBUG - Step end
2023-05-16 11:16:02,342 - robot_allocator - INFO - Step start T=262 timestamp=1684260962339-0 -----------------------------------------------------------------------------------------
2023-05-16 11:16:02,342 - robot_allocator - DEBUG - update start
2023-05-16 11:16:02,343 - robot_allocator - DEBUG - Robot 71 not yet to station zone (42, 15) -> (46, 28)
2023-05-16 11:16:02,343 - robot_allocator - DEBUG - Robot 55 not yet to station zone (13, 17) -> (4, 22)
2023-05-16 11:16:02,343 - robot_allocator - DEBUG - Robot 80 not yet to station zone (23, 16) -> (4, 19)
2023-05-16 11:16:02,343 - robot_allocator - DEBUG - Robot 83 not yet to item zone (35, 39) -> (27, 17)
2023-05-16 11:16:02,343 - robot_allocator - DEBUG - Robot 73 not yet to station zone (11, 16) -> (1, 23)
2023-05-16 11:16:02,343 - robot_allocator - DEBUG - Robot 51 not yet to item zone (9, 39) -> (20, 14)
2023-05-16 11:16:02,343 - robot_allocator - DEBUG - Robot 9 not yet to item zone (11, 1) -> (42, 14)
2023-05-16 11:16:02,343 - robot_allocator - DEBUG - Robot 7 not yet to item zone (35, 15) -> (38, 14)
2023-05-16 11:16:02,343 - robot_allocator - INFO - Robot 0 item picked 7
2023-05-16 11:16:02,344 - robot_allocator - DEBUG - Robot 47 not yet to station zone (17, 16) -> (1, 28)
2023-05-16 11:16:02,344 - robot_allocator - DEBUG - Robot 63 not yet to robot home (22, 23) -> (21, 40)
2023-05-16 11:16:02,344 - robot_allocator - DEBUG - Robot 62 not yet to item zone (22, 35) -> (36, 14)
2023-05-16 11:16:02,344 - robot_allocator - DEBUG - Robot 34 not yet to robot home (39, 10) -> (36, 1)
2023-05-16 11:16:02,344 - robot_allocator - DEBUG - Robot 5 not yet to robot home (7, 7) -> (7, 1)
2023-05-16 11:16:02,344 - robot_allocator - DEBUG - Robot 77 not yet to robot home (17, 30) -> (35, 40)
2023-05-16 11:16:02,344 - robot_allocator - DEBUG - Robot 37 not yet to robot home (39, 5) -> (39, 1)
2023-05-16 11:16:02,344 - robot_allocator - DEBUG - Robot 25 not yet to item zone (29, 9) -> (36, 17)
2023-05-16 11:16:02,344 - robot_allocator - DEBUG - Robot 45 not yet to item zone (10, 15) -> (10, 14)
2023-05-16 11:16:02,345 - robot_allocator - DEBUG - Robot 70 not yet to station zone (9, 16) -> (1, 34)
2023-05-16 11:16:02,345 - robot_allocator - DEBUG - Robot 39 not yet to item zone (30, 2) -> (19, 14)
2023-05-16 11:16:02,345 - robot_allocator - DEBUG - Robot 26 not yet to robot home (2, 2) -> (28, 1)
2023-05-16 11:16:02,345 - robot_allocator - DEBUG - Robot 33 not yet to robot home (17, 20) -> (35, 1)
2023-05-16 11:16:02,345 - robot_allocator - DEBUG - Robot 23 not yet to robot home (9, 21) -> (25, 1)
2023-05-16 11:16:02,345 - robot_allocator - DEBUG - Robot 86 not yet to station zone (2, 32) -> (1, 37)
2023-05-16 11:16:02,345 - robot_allocator - DEBUG - Robot 13 not yet to station zone (15, 14) -> (31, 19)
2023-05-16 11:16:02,345 - robot_allocator - DEBUG - Robot 19 not yet to station zone (32, 16) -> (1, 18)
2023-05-16 11:16:02,348 - robot_allocator - INFO - generate_path took 0.338 ms
2023-05-16 11:16:02,348 - robot_allocator - INFO - Sending Robot 82 back home for task:station:48:order:48:8:2
2023-05-16 11:16:02,349 - robot_allocator - DEBUG - Robot 81 not yet to item zone (34, 34) -> (33, 14)
2023-05-16 11:16:02,349 - robot_allocator - DEBUG - Robot 8 not yet to item zone (8, 14) -> (9, 17)
2023-05-16 11:16:02,349 - robot_allocator - DEBUG - Robot 22 not yet to item zone (24, 7) -> (43, 14)
2023-05-16 11:16:02,349 - robot_allocator - DEBUG - Robot 75 not yet to station zone (7, 19) -> (19, 19)
2023-05-16 11:16:02,349 - robot_allocator - DEBUG - Robot 65 not yet to station zone (15, 16) -> (11, 19)
2023-05-16 11:16:02,349 - robot_allocator - DEBUG - Robot 54 not yet to item zone (19, 15) -> (37, 14)
2023-05-16 11:16:02,349 - robot_allocator - DEBUG - Robot 49 not yet to robot home (11, 20) -> (7, 40)
2023-05-16 11:16:02,350 - robot_allocator - INFO - generate_path took 0.366 ms
2023-05-16 11:16:02,351 - robot_allocator - INFO - Sending robot 10 to station for task task:station:48:order:48:8:1
2023-05-16 11:16:02,351 - robot_allocator - DEBUG - Robot 72 not yet to station zone (8, 19) -> (16, 19)
2023-05-16 11:16:02,351 - robot_allocator - DEBUG - Robot 68 not yet to item zone (28, 15) -> (28, 14)
2023-05-16 11:16:02,352 - robot_allocator - INFO - generate_path took 0.260 ms
2023-05-16 11:16:02,352 - robot_allocator - INFO - Sending robot 32 to station for task task:station:34:order:61:45:3
2023-05-16 11:16:02,352 - robot_allocator - DEBUG - Robot 35 not yet to robot home (3, 23) -> (37, 1)
2023-05-16 11:16:02,353 - robot_allocator - DEBUG - Robot 2 not yet to robot home (1, 22) -> (4, 1)
2023-05-16 11:16:02,353 - robot_allocator - DEBUG - Robot 38 not yet to robot home (30, 21) -> (40, 1)
2023-05-16 11:16:02,353 - robot_allocator - DEBUG - Robot 48 not yet to robot home (6, 39) -> (6, 40)
2023-05-16 11:16:02,353 - robot_allocator - DEBUG - Robot 29 not yet to robot home (13, 7) -> (31, 1)
2023-05-16 11:16:02,353 - robot_allocator - DEBUG - Robot 85 not yet to item zone (12, 31) -> (10, 17)
2023-05-16 11:16:02,353 - robot_allocator - DEBUG - Robot 17 not yet to station zone (39, 16) -> (9, 22)
2023-05-16 11:16:02,353 - robot_allocator - DEBUG - Robot 28 not yet to robot home (17, 3) -> (30, 1)
2023-05-16 11:16:02,353 - robot_allocator - DEBUG - Robot 6 not yet to robot home (8, 16) -> (8, 1)
2023-05-16 11:16:02,355 - robot_allocator - INFO - Task task:station:50:order:50:45:0 complete, Robot 24 successfully dropped item
2023-05-16 11:16:02,355 - robot_allocator - DEBUG - Robot 14 not yet to robot home (10, 19) -> (16, 1)
2023-05-16 11:16:02,355 - robot_allocator - DEBUG - Robot 20 not yet to robot home (22, 11) -> (22, 1)
2023-05-16 11:16:02,356 - robot_allocator - DEBUG - Robot 41 not yet to robot home (3, 19) -> (43, 1)
2023-05-16 11:16:02,356 - robot_allocator - DEBUG - Robot 60 not yet to item zone (18, 39) -> (14, 17)
2023-05-16 11:16:02,356 - robot_allocator - DEBUG - Robot 59 not yet to station zone (20, 16) -> (16, 22)
2023-05-16 11:16:02,356 - robot_allocator - DEBUG - Robot 12 not yet to item zone (10, 2) -> (5, 17)
2023-05-16 11:16:02,356 - robot_allocator - DEBUG - Robot 40 not yet to station zone (6, 16) -> (28, 22)
2023-05-16 11:16:02,356 - robot_allocator - DEBUG - Robot 44 not yet to station zone (45, 31) -> (46, 37)
2023-05-16 11:16:02,356 - robot_allocator - DEBUG - Robot 46 not yet to station zone (32, 21) -> (41, 22)
2023-05-16 11:16:02,356 - robot_allocator - DEBUG - Robot 67 not yet to station zone (1, 27) -> (1, 31)
2023-05-16 11:16:02,356 - database_world_manager - DEBUG - 'update_robots' Start
2023-05-16 11:16:02,360 - database_world_manager - DEBUG - 'update_robots' End. Took 4.153 ms
2023-05-16 11:16:02,360 - robot_allocator - INFO - update end, took 17.971 ms, processed 88/88 jobs, assigned 0/0 available robots
2023-05-16 11:16:02,360 - robot_allocator - DEBUG - Step end
TBD why this happened
2023-05-16 11:14:37,464 - robot_allocator - INFO - generate_path took 162.422 ms
2023-05-16 11:14:37,465 - robot_allocator - WARNING - No path to station for Job [Robot 63, Task task:station:26:order:26:24:2: Progress ITEM PICKED, P 43 0 0
2023-05-16 11:14:37,475 - robot_allocator - INFO - generate_path took 10.728 ms
2023-05-16 11:14:37,476 - database_world_manager - DEBUG - 'update_robots' Start
2023-05-16 11:14:37,481 - database_world_manager - DEBUG - 'update_robots' End. Took 5.294 ms
2023-05-16 11:14:37,482 - robot_allocator - INFO - update end, took 198.103 ms, processed 45/88 jobs, assigned 0/0 available robots
Trying different vCPU requests
Built true heuristic grid in 15695.54 ms # 0.1 vCPU, 200 Mi memory
Built true heuristic grid in 7896.30 ms # 0.2 vCPU, 200 Mi memory
Built true heuristic grid in 2793.27 ms # 0.5 vCPU, 500 Mi memory
With 200Mi memory the cluster was getting 80%+ memory usage, and container OOM/crashes were happening
Adding more vCPU and memory brings building true heuristic grid time down dramatically, this correlates with generate_path time. If we bring it down too low, a generate_path may take > 500ms which causes the robot allocator to revert that update step, but that path search still exists, so it gets stuck in a loop. This puts a lower bound on an individual container vCPU/memory to have the worst case generate_path be less than the threshold to revert an update step.