Interactive-FAR: Interactive, Fast and Adaptable Routing for Navigation
Among Movable Obstacles in Complex Unknown Environments
This work proposes a solution for interactive navigation in cluttered unknown environments, focusing on fast and adaptable navigation with environmental interactions.
Abstract: This paper introduces a real-time algorithm for navigating complex unknown environments cluttered with movable obstacles. Our algorithm achieves fast, adaptable routing by actively attempting to manipulate obstacles during path planning and adjusting the global plan from sensor feedback. The main contributions include an improved dynamic Directed Visibility Graph (DV-graph) for rapid global path searching, a real-time interaction planning method that adapts online from new sensory perceptions, and a comprehensive framework designed for interactive navigation in complex unknown or partially known environments. Our algorithm is capable of replanning the global path in several milliseconds. It can also attempt to move obstacles, update their affordances, and adapt strategies accordingly. Extensive experiments validate that our algorithm reduces the travel time by 33%, achieves up to 49% higher path efficiency, and runs faster than traditional methods by orders of magnitude in complex environments. It has been demonstrated to be the most efficient solution in terms of speed and efficiency for interactive navigation in environments of such complexity.
System Overview
Quick Start
Code coming soon.
Docker Installation
1) For computers without a Nvidia GPU
Install Docker and grant user permission.
curl https://get.docker.com | sh && sudo systemctl --now enable docker
sudo usermod -aG docker ${USER}
Make sure to restart the computer, then install additional packages.
sudo apt update && sudo apt install mesa-utils libgl1-mesa-glx libgl1-mesa-dri
2) For computers with Nvidia GPUs
Install Docker and grant user permission.
curl https://get.docker.com | sh && sudo systemctl --now enable docker
sudo usermod -aG docker ${USER}
Make sure to restart the computer, then install Nvidia Container Toolkit (Nvidia GPU Driver should be installed already).
curl -fsSL https://nvidia.github.io/libnvidia-container/gpgkey | sudo gpg --dearmor \
-o /usr/share/keyrings/nvidia-container-toolkit-keyring.gpg \
&& curl -s -L https://nvidia.github.io/libnvidia-container/stable/deb/nvidia-container-toolkit.list \
| sed 's#deb https://#deb [signed-by=/usr/share/keyrings/nvidia-container-toolkit-keyring.gpg] https://#g' \
| sudo tee /etc/apt/sources.list.d/nvidia-container-toolkit.list
sudo apt update && sudo apt install nvidia-container-toolkit
Configure Docker runtime and restart Docker daemon.
sudo nvidia-ctk runtime configure --runtime=docker
sudo systemctl restart docker
Note: If your computer does not have a Nvidia GPU but has Nvidia GPU drivers installed, please uninstall them.
Results
We conduct 10 navigation tasks in simulated environments with different scales. The start and end navigation goals are selected so that the optimal path is larger than a threshold for each environment. with a Velodyne Puck Lidar used as the range sensor for perception, a 1-D force sensor for tactile sensing. The framework runs on a laptop with i7-12700H CPU. We configure the algorithm to update the DV-graph at 2.5Hz and perform path search at each graph update. The spatial resolution is set as 0.15m.
Environments
System Level Comparison
We compare the systematic navigation performance with FAR. The reasons for comparing these two algorithms are: 1) the superiority of FAR over other path search methods has been demonstrated, and 2) the offline implementation of R-NAMO and LAMB make them fail to be applicable navigation systems for comparison.
Average Search Time in [ms]
R-NAMO: Levihn et al. Locally optimal navigation among movable obstacles in unknown environments. International Conference on Humanoid Robots. 2014
LAMB: Muguira-Iturralde et al. Visibility-aware navigation among movable obstacles. ICRA 2023
Path Efficiency Comparison
We use SPL (Sucess weighted by Path Length) to measure the path efficiency.
Video Demo
Interactive-FAR.mp4People
Botao He*
University of Maryland
Guofei Chen*
CMU Robotics Institute
Wenshan Wang
CMU Robotics Institute
Ji Zhang
CMU NREC & Robotics Institute
University of Maryland
University of Maryland
References
B. He, G. Chen, W. Wang, J. Zhang, C. Fermuller, and Y. Aloimonos. Interactive-FAR: Interactive, Fast and Adaptable Routing for Navigation Among Movable Obstacles in Complex Unknown Environments. Submitted. [PDF]