  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. We also open-source our code in the docker
demo to facilitate future research.
