Cooperative Multi-Robot Path Finding with Removable Obstacles for Autonomous Environment Modification

Multi-Robot Navigation Among Movable Obstacles (MR-NAMO) is a variant of the Multi-Agent Path Finding (MAPF) problem where the environment consists of both immovable and movable obstacles. In this paper, we introduce a special case of MR-NAMO called the multi-agent path finding with removable obstacles (MAPF-RO) problem in which the robots cooperate to remove some obstacles along the busy paths in the environment. We model the removable obstacles as pits and remove them by filling them using sandbags. Sandbags are modeled as movable obstacles but are removable when they are filled into a pit. The obstacles are removed or moved away from the paths while the total energy required for all robots to reach their goals is minimized. The nearby sandbag to fill a pit is identified by using a kd-tree-based heuristic search. The nearby robot to push a sandbag is identified using directional wavefront propagation algorithm. We simulate the scenario in randomized grid environments consisting of static, movable and removable obstacles. We find that our approach conserves energy by removing only the necessary obstacles and cooperatively shortens the path for other agents. This method can be applied to multi-robot cooperative environment modification, enabling robots to alter their surroundings to optimize task execution for their peers while reducing overall energy expenditure.