Recent progress on sampling based dynamic motion planning algorithms

This paper reviews recent developments extending sampling based motion planning algorithms to operate in dynamic environments. Sampling based planners provide an effective approach for solving high degree of freedom robot motion planning problems. The two most common algorithms are the Probabilistic Roadmap Method and Rapidly Exploring Random Trees. These standard techniques are well established, however they assume a fully known environment and generate paths ahead of time. For realistic applications a robot may be required to update its path in real-time as information is gained or obstacles change position. Variants of these standard algorithms designed for dynamic environments are categorically presented and common implementation strategies are explored.

I. Introduction

Robots commonly operate in changing and unknown environments and need to be able to modify motion plans as information changes. This is particularly challenging for high Degree of Freedom (DOF) systems where motion planning is a computationally expensive operation. Sampling Based Planning (SBP) algorithms have proven to be an effective way to solve high-DOF planning problems [1], however conventional algorithms assume a static, known environment. Recent work on SBPs has expanded these algorithms to perform real-time planning in dynamic or unknown environments allowing new behaviours and interactions for high DOF robotic systems.