Abstract
Traditional robotic navigation systems typically treat all obstacles as static, leading to inefficient detours in cluttered environments. This paper presents Interactive-FAR, a real-time navigation framework designed for Navigation Among Movable Obstacles (NAMO). By integrating interaction costs into a sparse Directed Visibility Graph (DV-graph), the system enables robots to actively manipulate obstacles to clear paths. The framework adapts to real-time force feedback to handle unknown object properties, achieving significant improvements in path efficiency and computational speed compared to state-of-the-art static and interactive planners.
Introduction
In autonomous navigation, the standard paradigm has long been obstacle avoidance. However, in human-centric environments like homes or offices, many obstacles—such as chairs, boxes, or carts—are movable. A robot that can only avoid these objects is fundamentally limited, often forced into long detours when a simple push could reveal a much shorter path.
The challenge of Navigation Among Movable Obstacles (NAMO) is computationally intensive (NP-hard). Existing approaches often struggle with "geometric overload," where solving the physics of the entire environment takes too long for real-time application, or they rely on static assumptions that fail to account for the robot's ability to change its surroundings. Interactive-FAR addresses these issues by treating interaction as a navigable edge in a sparse graph, allowing for millisecond-level replanning in unknown, complex environments.
Methodology
1. The Directed Visibility Graph (DV-graph)
Interactive-FAR utilizes a sparse graph representation rather than a dense grid or voxel map. The core of this representation is the Directed Visibility Graph (DV-graph), which uses the vertices of detected polygons to define paths.
- Hybrid Representation: The graph consists of standard "visibility edges" (unobstructed paths) and "interaction edges" (paths that require moving an object).
- Hierarchical Mapping: To maintain efficiency, the system employs a dual-layer approach. A local layer processes raw sensor data into polygons and interaction strategies, while a global layer maintains the overall connectivity of the environment. This allows the robot to navigate large-scale maps while focusing heavy computation only on its immediate vicinity.
2. Adaptable Interaction Planning
When the robot encounters a blocking object, it must decide if pushing is more efficient than a detour. This is handled through a multi-step process:
- Problem Decomposition: The system identifies specific blocking polygons and determines how to reconnect the visibility graph by moving them.
- Hybrid A* Search: A kinodynamic search finds a feasible "stable push" strategy, ensuring the robot can move the object reliably without losing control or requiring complex dynamic modeling.
- Heuristic Polygons: To accelerate the search, the framework uses the geometric "width" of the blocking object as a heuristic to estimate the effort required to clear it.
- Online Affordance Learning: A critical feature of Interactive-FAR is its ability to learn from physical interaction. Using force sensors, the robot estimates an object's friction and mass in real-time. If an object proves too heavy to move (an "unaffordable" interaction), the robot immediately updates the DV-graph with a high-cost edge and replans a detour.
Experimental Evaluation
The framework was evaluated in various simulated environments using the Gazebo simulator, ranging from small-scale rooms (32m x 32m) to large-scale industrial complexes (330m x 270m). The performance was benchmarked against classical planners (A, RRT, BIT*), existing NAMO methods (R-NAMO, LAMB), and the static FAR planner.
Key Results
- Path Efficiency: Interactive-FAR reduced total travel time by 33% and increased path efficiency by up to 49% compared to planners that strictly avoided obstacles.
- Computational Speed: The system demonstrated remarkable efficiency, handling global replanning in under 10ms on standard hardware. This is orders of magnitude faster than previous NAMO methods, which often require seconds or minutes to solve local manipulation tasks.
- Reliability: In complex "Office" and "Tunnel" scenarios, Interactive-FAR achieved a 100% success rate. In contrast, static planners often failed or took massive detours because they could not perceive the possibility of clearing a blocked path.
Discussion and Limitations
Interactive-FAR successfully collapses complex manipulation physics into a graph-search problem by treating interaction as a directed edge. This sparsity is the key to its real-time performance. However, several areas for future work remain:
- Sim-to-Real Gap: While the model uses force feedback, real-world physics involves noise—such as objects tipping or snagging—that may require more sophisticated control loops.
- Multi-Object Manipulation: The current framework focuses on moving one object at a time. In highly cluttered environments, robots may need to move multiple objects simultaneously, a significantly more complex combinatorial problem.
- Manipulation Diversity: The current implementation focuses on pushing. Integrating pulling, lifting, or grasping into the DV-graph structure would further expand the robot's navigational capabilities.
Conclusion
Interactive-FAR represents a significant step toward robots that can navigate the world as dynamically as humans do. By treating the environment as a set of opportunities for interaction rather than just a collection of obstacles, the framework enables faster, more efficient, and more adaptable autonomous navigation in the face of uncertainty.
Summary updated