/Path Planning in Dynamic Environments with Adaptive Dimensionality

Path Planning in Dynamic Environments with Adaptive Dimensionality

Anirudh Vemula, Katharina Muelling and Jean Hyaejin Oh
Conference Paper, Proceedings of the Ninth International Symposium on Combinatorial Search (SoCS-2016), July, 2016

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

Path planning in the presence of dynamic obstacles is a challenging problem due to the added time dimension in the 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 suboptimality 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.

BibTeX Reference
@conference{Vemula-2016-5566,
author = {Anirudh Vemula and Katharina Muelling and Jean Hyaejin Oh},
title = {Path Planning in Dynamic Environments with Adaptive Dimensionality},
booktitle = {Proceedings of the Ninth International Symposium on Combinatorial Search (SoCS-2016)},
year = {2016},
month = {July},
}
2017-09-13T10:38:19+00:00