Offline and Online Evolutionary Bi-Directional RRT Algorithms for Efficient Re-Planning in Dynamic Environments

Abstract

This paper explores the use of evolutionary algorithms (EAs) to formulate additional biases for a probabilistic motion planner known as the rapidly exploring random tree (RRT) algorithm in environments with changing obstacle locations. An offline EA is utilized to produce a bias in an obstacle filled environment prior to rearranging the obstacles. It is demonstrated that the offline EA finds a bias reflecting the original environment and improves the RRT's efficiency during re-planning in environments with a small number of rearrangements. The rapidly exploring evolutionary tree (RET) algorithm is introduced as a hybrid RRT algorithm employing an online EA. It is demonstrated that the RET can improve the RRT's performance during re-planning in environments with many rearranged obstacles by exploiting characteristics of a balanced spatial kd-tree.