Real-Time Concurrent Map Building and Motion Planning of An Autonomous Vehicle Based on An Efficient D*-Lite Model

Wang, Qing, Chaomin Luo, Mohan Krishnan, and Mark Paulik

While vehicles work in unknown environments, map building is required for the vehicles to effectively explore the workspace with obstacle avoidance. Motion planning is an essential issue for intelligent vehicles and many other robotic applications. The ability to perform motion planning and map building is a critical competence for successful exploration in real-word environments of intelligent vehicles.  Consequently, real-time concurrent map building and vehicle motion planning are desirable for efficient performance in many robotics applications.

In this project, a novel D*-Lite algorithm associated with local Vector Field Histogram (VFH) navigation methodology is developed and applied for real-time concurrent map building and motion planning of autonomous vehicles in a completely unknown environment.  Local map composed of square pixels is dynamically created during exploration with 270 degree limited Lidar information.  The VFH is capable of considering the dynamics and shape of the robot and processing uncertainty from sensor and modeling errors by a statistical representation of the robot's environment through histogram grid. A path from a starting point to the goal is created by D*-Lite algorithm, in which the path is dynamically marked by bread-crumbs.  With the exploration of a terrain by the vehicle, a map is dynamically generated and trajectories are planned dynamically. Some simulation studies in U-shaped, unstructured, cluttered, maze-like and multi-obstacle outdoor environments have been accomplished in this project. Comparison studies on the Player/Stage platform demonstrate that the proposed model outperforms over other existing methodologies and the proposed method is capable of planning more reasonable, less cost and shorter collision-free paths in unknown environments. This model has extensive applications such as service, military, underwater, transportation, medical, health rescue and other non-manufacturing robotics applications.