COLLISION PREDICTION: CONSERVATIVE ADVANCEMENT AMONG OBSTACLES WITH UNKNOWN MOTION∗

Collision detection is a fundamental geometric tool for sampling-based motion planners. On the contrary, collision prediction for the scenarios that obstacle’s motion is unknown is still in its in-fancy. This paper proposes a new approach to predict collision by assuming that obstacles are adversarial. Our new tool advances collision prediction beyond the translational and disc robots; ar-bitrary polygons with rotation can be used to better represent obstacles and provide tighter bound on predicted collision time. Comparing to an online motion planner that replans periodically at fixed time interval, our experimental results provide strong ev-idences that our method significantly reduces the number of re-plannings while maintaining higher success rate of finding a valid path.