/Safe and Efficient Navigation in Dynamic Environments

Safe and Efficient Navigation in Dynamic Environments

Anirudh Vemula
Master's Thesis, Tech. Report, CMU-RI-TR-17-40, Robotics Institute, Carnegie Mellon University, August, 2017

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.


For mobile robots to become ubiquitous, they need to be able to navigate in dynamic environments in a safe and efficient way. This is a challenging problem due to the added time dimension in the search space and the subtle interactions between dynamic agents that are extremely difficult to model. In this thesis, we will address both of these challenges.

The challenge of dimensionality is addressed by proposing a novel path planning algorithm in environments with dynamic agents with quick planning times. 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 nonholonomic vehicle navigation 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.

We tackle the challenge of modeling interactions by presenting a novel statistical model to capture cooperative behavior in human crowds. Previous approaches have used hand-crafted functions based on proximity to model human-human and human-robot interactions. However, these approaches can only model simple interactions and fail to generalize for complex crowded settings. We develop an approach that models the joint distribution over future trajectories of all interacting agents in the crowd through a local interaction model that we train using real human trajectory data. The interaction model infers the velocity of each agent based on the spatial orientation of other agents in his vicinity. During prediction, our approach infers the goal of the agent from its past trajectory and uses the learned model to predict its future trajectory. We demonstrate the performance of our method against a state-of-the-art approach on a public dataset and show that our model outperforms when predicting future trajectories for longer horizons.

Finally, we lay out future directions of research in the domain of robot navigation in dynamic environments, and the challenges remaining. We plan to verify and validate the proposed work in this thesis on a robot placed in a real human crowd. Other challenges include more accurate long-term prediction, uncertainty associated with predictions and real-time incremental planning algorithms.

BibTeX Reference
author = {Anirudh Vemula},
title = {Safe and Efficient Navigation in Dynamic Environments},
year = {2017},
month = {August},
school = {Carnegie Mellon University},
address = {Pittsburgh, PA},
number = {CMU-RI-TR-17-40},