Safety Hierarchy for Planning With Time Constraints in Unknown Dynamic Environments

We present a planning algorithm for a mobile robot in unknown indoor dynamic environments. The algorithm takes into account the robot's own dynamics and the dynamic obstacles’ future behavior in a safety hierarchy. It also uses an appropriate time horizon for planning and respects the timing constraints on various modules of the planner that are imposed by interleaving of planning and execution. We provide a formulation of this safety hierarchy in a single step via a composite costmap. The planning algorithm has been implemented in Player/Stage. We have run extensive simulations and compared the performance of the full safety hierarchy with various permutations of safety levels, as well as with some baseline algorithms over three different performance measures. We show that our safety hierarchy performs statistically significantly better across most performance measures and most simulation scenarios.