Robot plans paths by moving obstacles or exploring unknown space
Navigate or Relocate? Planning Among Movable Obstacles in Unknown Environments
Robotics
Summary
Sometimes robots need to find their way but all paths are blocked by objects. The paper presents a way for a robot to decide if it can navigate around obstacles or if it must move some objects out of the way first. Unlike earlier methods that assume the robot knows everything about its environment, this approach works as the robot discovers new areas using its own sensors. It also plans sequences of moving objects that depend on each other, improving the robot’s ability to find a way through cluttered spaces.
What this means in practice
- •For autonomous robot developers: Create robots that can decide when to move obstacles or explore unknown areas to find a path in cluttered environments.
- •For warehouse automation teams: Implement better navigation strategies for robots in warehouses where pathways may be blocked and need object relocation.
Authors
Yuqing Zhang, Haoyu Zhu, Yiannis Kantaros
Abstract
Conventional robot planning methods seek collision-free paths to a goal but fail when all paths are blocked. In these cases, the robot must determine which objects to relocate, in what order, and where to place them to clear a path---a problem known as Navigation Among Movable Obstacles (NAMO). Most NAMO planners assume a known environment, while existing approaches for unknown environments typically reason locally about relocations and cannot plan interdependent relocation sequences. We consider NAMO in unknown environments revealed through onboard sensing, where the robot must decide whether a blocked route requires relocation or a feasible path may exist through unexplored space. We propose an online framework that addresses this ambiguity by selecting between navigation and relocation using shortest paths that treat discovered movable objects as obstacles or as removable. Navigation relies on existing motion planners, while relocation uses a sampling-based approach that, unlike existing approaches for unknown environments, searches over \textit{interdependent} relocation sequences and uses an LLM to bias sampling. Numerical experiments demonstrate scalability to cluttered environments requiring interdependent relocations and improved plan quality over existing baselines.