Reciprocal Collision Avoidance of Arbitrary Objects
Course project for COMP 790-058: Multi-Agent Simulation for Crowds and Autonomous Driving
by Zhenyu Tang and Yuexin Ma
There have been many methods for crowd simulation and navigation, including
Vision based system
However, no which method is chosen, the rerepsentation of agents in the scene is important. For large objects, we want to assign a larger area to them and similarly for smalle objects. So what are some good representations?
In Menge simulator, agents are represented as circles of equal size. Circles are the simplest representation of agents. And they are efficient for computatioin.
Latest research extended ORCA model to elliptical agents based on linear approximation and precomputation. Compared with circles, ellipses are more accurate because they bound the agents more tightly. But the tradeoff is that computation time for collision avoidance with elliptical agents is much more expensive than with circles. So precomputation of Minkowski sums must be performed, and then real-time collision avoidance queries can be made.
We present a new representation of agents that can be applied to artitrary objects with better precision using medial axis of objects. The medial axis of an object is the set of all points having more than one closest point on the object’s boundary. In 2D, the medial axis of a subset S which is bounded by planar curve C is the locus of the centers of circles that are tangent to curve C in two or more points, as shown below. If the distance to the boundary is regarded as the radius of medial axis point, we can get medial axis transform (MAT).
Exact presentation of medial axis should be continous but is hard to be used in application. So we use a simplified MAT instead. In most cases, we store a set of medial points (with r) and their neighboring relationship. When reconstructing shape from the stored discrete information, we just linearly interpolate between neighboring medial circles. And the outermost contour is the reconstructed shape. We call this representation as Reconstructed Shape from MAT (RSMAT). Below are some approximated shapes by simplified MAT of the top-down view of several objects in real world. The only difference between our concept and exact MAT is that the medial circle of MAT is internally tangent to shape, but in order to cover the agent, we use circumcircle.
Here are goals we want accomplish within this semester
Simulation framework using RSMAT
Set of experiments and results
Analysis of efficiency and limitations
Oct 24th: Smooth agents movement using methods from paper.
Nov 7th: Compare with ORCA and potentially other models.
Nov 21st: Eliminate unnatural behaviors of our agents.
Dec 5th: Optimization and wrap up.
We are able to simulate various scenarios using our framework. Here are videos of some benchmark scenarios we used:
Circle scenario - a circle of agents are exchanging their positions with the their opposite one.
It can be seen that our algorithm works well in these situations. We also tested how our algorithm performs in terms of efficiency compared with ORCA and ERVO below.
Then we tested how number of tuples used by MAT affects the performance:
Best, Andrew, Sahil Narang, and Dinesh Manocha. "Real-time reciprocal collision avoidance with elliptical agents." Robotics and Automation (ICRA), 2016 IEEE International Conference on. IEEE, 2016.
Harry Bium. A transformation for extracting new descriptions of shape. In Symposium on Modeis for the
Perception of Speech and Visual Form.
Pan Li, Bin Wang, Feng Sun, Xiaohu Guo, Caiming Zhang, and Wenping Wang. Q-mat: Computing medial
axis transform by quadratic error minimization. ACM Transactions on Graphics (TOG), 35(1):8, 2015.
Sahil Narang, Andrew Best, and Dinesh Manocha. Interactive simulation of local interactions in dense crowds
using elliptical agents. Journal of Statistical Mechanics: Theory and Experiment, 2017(3):033403, 2017.
Jur Van Den Berg, Stephen J Guy, Ming Lin, and Dinesh Manocha. Reciprocal n-body collision avoidance. In
Robotics research, pages 3–19. Springer, 2011.