Collision Prediction: Conservative Advancement Among Obstacles with Unknown Motion

Yanyan Lu and Zhonghua Xi and Jyh-Ming Lien

Overview

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 infancy. 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; arbitrary 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 evidences that our method significantly reduces the number of replannings while maintaining higher success rate of finding a valid path.

Source Code

Download MPBox2D, a motion planner using ECT in C++

Below are videos for Collision Prediction Based Motion Planning in Complicated Dynamic Environment

Point-Polygon Case	Polygon-Polygon Case	Point-Aritculated Case

Publications

Online Collision Prediction Among 2D Polygonal and Articulated Obstacles, Yanyan Lu and Zhonghua Xi and Jyh-Ming Lien, International Journal of Robotics Research (IJRR), Apr. 2016
Web Site / Paper(pdf) / BibTeX

Predict Collision Among Rigid and Articulated Obstacles with Unknown Motion, Yanyan Lu and Zhonghua Xi and Jyh-Ming Lien, The Eleventh International Workshop on the Algorithmic Foundations of Robotics (WAFR), Aug. 2014
Web Site / Paper (pdf) / BibTeX

Collision Prediction Among Polygons with Arbitrary Shape and Unknown Motion, Yanyan Lu and Zhonghua Xi and Jyh-Ming Lien, IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Sep. 2014
Web Site / Paper (pdf) / BibTeX

Collision Prediction: Conservative Advancement Among Obstacles With Unknown Motion, Yanyan Lu and Zhonghua Xi and Jyh-Ming Lien, International Design and Engineering Technical Conferences & Computers and Information in Engineering Conference (IDETC/CIE), ASME, Aug. 2014
Web Site / Paper (pdf) / BibTeX

Path Planning in Similar Environments, Yanyan Lu, Aug. 2013
BibTeX

Conservative Collision Prediction Among Polygons with Unknown Motion, Yanyan Lu and Zhonghua Xi and Jyh-Ming Lien, George Mason University, (Technical Report), 2013
Web site / Paper (pdf) / BibTeX

Main Contributions

Our new method adaptively replans only when necessary.
While maintaining high success rate, our method provides the following benefits:

Compared to strategies that replan at fixed time intervals, our method significantly reduces the number of replans
Compared to conservative optimal strategies, our method is able to handle more practical problems

Comparison To Fixed-Time Strategy

Our method using predicted collision helps robot achieve nearly optimal success rate with a small number of replans.

Point-Polygon Case

Polygon-Polygon Case

Point-Articulated Case

Results from our implementation

Comparison on Collision Prediction based and fixed-time based strategy
In the following videos, static obstacles are in black while dynamic obstacles are in light grey. For our collisions prediction based method, a red obstacle is the one which introduces earliest collision with robot. A red dot shows the position of robot and a green curve shows the trajectory that robot has traversed. A blue curve is the path which robot is going to take, if it will not replan. A brown dot indicates where the predicted collision happens. For the fixed-time strategy, a brown dot means where the robot will be at a fixed moment.

Conservative Advancement among obstacles with unknown trajectory

The following video simulates conservative advancement of a point robot on the pre-planned path. Every obstacle moves with its maximum speed in order to minimize the time that robot remains collision free. We are interested in detecting the time when earliest collision (the lighting) happens.