Closed form characterization of collision free velocities and confidence bounds for non-holonomic robots in uncertain dynamic environments

Navigating non-holonomic mobile robots in dynamic environments is challenging because it requires computing at each instant, the space of collision free velocities, characterized by a set of highly non-linear and non-convex inequalities. Moreover, uncertainty in obstacle trajectories further increases the complexity of the problem, as it now becomes imperative to relate the space of collision free velocities to a confidence measure. In this paper, we present a novel perspective towards analyzing and solving probabilistic collision avoidance constraints based on our previous works on non-linear time scaling. In particular, we have shown earlier that a time scaled version of collision cone constraints can be solved in closed form and thus can be used to efficiently characterize the space of collision free velocities. In the current proposed work, we present a probabilistic version of time scaled collision cone constraints obtained by representing obstacle states through generic probability distributions. We present a novel reformulation of the probabilistic constraints into a family of deterministic algebraic constraints. The solution space of each member of the family can be derived in closed form and at the same time, can also be related to the lower bound on confidence measure through Cantelli's inequality. Thus, the proposed work represents a significant improvement over the current state of the art frameworks where probabilistic collision avoidance constraints are solved through exhaustive sampling in the state-control space. We also present a cost metric which serves as the basis for the construction of the various collision avoidance maneuvers based on factors like deviation from the current path, acceleration/de-acceleration capability of the robot, confidence of collision avoidance etc. We very briefly explain how the current robot state can be connected to the solution space of safe velocities in smooth time optimal fashion. Finally, the validity of the proposed formulation is exhibited through extensive numerical simulation results.