Path planning in the presence of dynamic obstacles is a challenging problem due to the added time dimension in search space. In approaches that ignore the time dimension and treat dynamic obstacles as static, frequent re-planning is unavoidable as the obstacles move, and their solutions are generally sub-optimal and can be incomplete. To achieve both optimality and completeness, it is necessary to consider the time dimension during planning. The notion of adaptive dimensionality has been successfully used in high-dimensional motion planning such as manipulation of robot arms, but has not been used in the context of path planning in dynamic environments. In this paper, we apply the idea of adaptive dimensionality to speed up path planning in dynamic environments for a robot with no assumptions on its dynamic model. Specifically, our approach considers the time dimension only in those regions of the environment where a potential collision may occur, and plans in a low-dimensional state-space elsewhere. We show that our approach is complete and is guaranteed to find a solution, if one exists, within a cost sub-optimality bound. We experimentally validate our method on the problem of 3D vehicle navigation (x, y, heading) in dynamic environments. Our results show that the presented approach achieves substantial speedups in planning time over 4D heuristic-based A*, especially when the resulting plan deviates significantly from the one suggested by the heuristic.
Other approaches @cite_12 @cite_11 delegate the dynamic obstacle avoidance problem to a local reactive planner which can effectively avoid collision with dynamic obstacles. These methods have the disadvantage that they can get stuck in local minima and are generally not globally optimal.
@cite_12 @cite_11
2117211893 2131505299
This approach, designed for mobile robots equipped with synchro-drives, is derived directly from the motion dynamics of the robot. In experiments, the dynamic window approach safely controlled the mobile robot RHINO at speeds of up to 95 cm sec, in populated and dynamic environments. Many applications in mobile robotics require the safe execution of a collision-free motion to a goal position. Planning approaches are well suited for achieving a goal position in known static environments, while real-time obstacle avoidance methods allow reactive motion behavior in dynamic and unknown environments. This paper proposes the global dynamic window approach as a generalization of the dynamic window approach. It combines methods from motion planning and real-time obstacle avoidance to result in a framework that allows robust execution of high-velocity, goal-directed reactive motion for a mobile robot in unknown and dynamic environments. The global dynamic window approach is applicable to nonholonomic and holonomic mobile robots.