Elucidation / mapf-multiagent-robot-planning

Multi-Agent PathFinding (MAPF) for 2D Robots moving inventory on a grid - Practice building environment + robots + planning + inventory management etc.
MIT License
11 stars 3 forks source link

Rework static/dynamic obstacle calculations #105

Closed Elucidation closed 1 year ago

Elucidation commented 1 year ago

profiling found that in the robot allocator update step, the largest bottleneck was static/dynamic obstacle generation which is done from the existing robot positions/paths and item zones.

Some optimizations:

Elucidation commented 1 year ago

WIP that on robot allocator restart, trying to generate paths for all robots is very expensive and for say 500 robots will likely take > 1 cycle.

The simplest option, clear all paths and have robots wait in place will cause gridlocks on a less sparse grid, which is the case fora big warehouse with 500 robots, as no robot can find a valid path home because other robots are stationary in the way.

The next option is on restart, to let robots continue on their existing paths (world sim has access to existing paths on redis db), and assign a new restart-return-home type job that waits till they complete their current paths. This avoids gridlock and also defers path planning into the update step where it can be batched by time