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.
Abstract Safe and efficient path planning for mobile robots in large dynamic environments is still a challenging research topic. In order to plan collision-free trajectories, the time component of the path must be explicitly considered during the search. Furthermore, a precise planning near obstacles and in the vicinity of the robot is important. This results in a high computational burden of the trajectory planning algorithms. However, in large open areas and in the far future of the path, the planning can be performed more coarsely. In this paper, we present a novel algorithm that uses a hybrid-dimensional multi-resolution state × time lattice to efficiently compute trajectories with an adaptive fidelity according to the environmental requirements. We show how to construct this lattice in a consistent way and define the transitions between regions of different granularity. Finally, we provide some experimental results, which prove the real-time capability of our approach and show its advantages over single-dimensional single-resolution approaches. Safe navigation for mobile robots in unstructured and dynamic environments is still a challenging research topic. Most approaches use separate algorithms for global path planning and local obstacle avoidance. However, this generally results in globally sub-optimal navigation strategies. In this paper, we present an algorithm which combines these two navigation tasks in a single integrated approach. For this purpose, we introduce a novel search space, namely, a × lattice with hybrid dimensionality. We describe a procedure for generating high-quality motion primitives for a mobile robot with four-wheel steering to define the motion in this lattice. Our algorithm computes a hybrid solution for the path planning problem consisting of a trajectory (i.e., a path with time component) in the imminent future, a dynamically feasible path in the near future, and a kinematically feasible path for the remaining time to the goal. Finally, we provide some results of our algorithm in action to prove its high solution quality and real-time capability. 