Online collision prediction among 2D polygonal and articulated obstacles

Abstract

Collision prediction is a fundamental operation for planning motion in dynamic environments. Existing methods usually exploit complex behavior models or use dynamic constraints in collision prediction. However, these methods all assume simple geometry, such as a disc, which significantly limits their applicability. This paper proposes a new approach that advances collision prediction beyond disc robots and handles arbitrary polygons and articulated objects. Our new tool predicts collision by assuming that obstacles are adversarial. Comparing to an online motion planner that replans periodically at fixed time intervals and a planner that approximates obstacle with discs, our experimental results provide strong evidence that the new method significantly reduces the number of replans while maintaining a higher success rate of finding a valid path. Our geometric-based collision prediction method provides a tool for handling highly complex shapes and provides an approach complementary to those methods that consider behavior and dynamic constraints of objects with simple shapes.