Lazy Reconfiguration Forest (LRF) - An Approach for Motion Planning with Multiple Tasks in Dynamic Environments

Abstract

We present a novel algorithm for robot motion planning in dynamic environments. Our approach extends rapidly-exploring random trees (RRTs) in several ways. We assume the need to simultaneously plan and maintain paths for multiple tasks with respect to the current state of a moving robot in a dynamic environment. Our algorithm dynamically maintains a forest of trees by splitting, growing and merging them on the fly to adapt to moving obstacles and robot motion. In order to minimize tree maintenance, we only validate the task paths, rather than the entire forest. The root of the inhabited tree moves with the robot. Dynamic re-planning is integrated with tree and forest maintenance. Coupling the robot motion with the planner enables us to support multiple tasks, for example providing an "escape" path while moving to a goal. The robot is free to move along whichever task path it chooses. We highlight the work by showing fast results in simulated environments with moving obstacles.