Motion planning algorithms for identifying collision-free paths in presence of moving obstacles are critical for robotic applications including self-driving cars, UAVs, service robots, mobile manipulators and autonomous wheelchairs, However, motion planning in dynamic environments is challenging. Even in the simplest case, where a 2D holonomic robot must avoid collision with polygonal obstacles moving at constant velocities, planning has been shown to be NP-Hard and in PSPACE. Thus, identifying complete solutions, in real-time and in the presence of robot dynamic constraints, obstacle motion uncertainty, and a large number of obstacles, is practically unachievable. Therefore, many real-time planning algorithms sacrifice completeness for practicality. These algorithms vary drastically in methodology, obstacle information usage, and computational requirements. This diversity in algorithms has motivated prior surveys, which discussed the variety in methodology and their desirable properties. In addition, in depth discussion on the complexity of planning in dynamic environments can be found in [14]. A review focusing on sampling-based methods for dynamic environments is available in [25]. We extend all prior review work by contributing in this work a detailed comparison of a set of algorithms implemented in navigation that requires dynamic obstacle avoidance.
展开▼
