Robot navigation paths found by moving obstacles minimally
A Horizon-slicing Approach to Minimum Obstacle Displacement Planning for Robot Navigation
RoboticsArtificial Intelligence
Summary
Sometimes a robot needs to get to a certain place, but obstacles are in the way and no clear path exists. This paper looks at how to move those obstacles as little as possible to clear a path. The researchers found that figuring out the very best way to do this is very hard mathematically. They then suggest a faster method that doesn’t always find the perfect path but does well enough and lets users balance how far the robot travels against how much obstacles need to be moved.
What this means in practice
- •For robotics engineers: Generate robot navigation plans that minimally rearrange movable obstacles when no direct path exists.
- •For warehouse automation teams: Improve route planning for robots by minimizing disruption to movable inventory or equipment blocking paths.
Authors
Antony Thomas, Giulio Ferro, Fulvio Mastrogiovanni, Michela Robba, Marco Baglietto
Abstract
In this paper, we investigate the Minimum Obstacle Displacement Planning problem from a robot motion planning perspective. The problem involves determining a feasible path to a goal location by displacing movable obstacles when no collision-free path initially exists. We show that this problem is computationally challenging and, in particular, NP-hard when obstacles are modeled as polygons in the plane. Besides an exact formulation of the minimum obstacle displacement problem generalizing other problems in the literature, and the associated optimal solution, this paper proposes an approximate solution that is less intensive from a computational standpoint, and differs from the optimal solution by a fraction of the optimal cost, being able to trade-off between path length and amount of obstacle displacements.