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

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?

Prior State-of-the-art

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.

Semester Goal

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



We are able to simulate various scenarios using our framework. Here are videos of some benchmark scenarios we used:

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.
Performance comparison of ORCA, ERVO with precomputation, MATRVO and MATRVO with precomputation in the antipodal circle scenario.
Then we tested how number of tuples used by MAT affects the performance:

Performance comparison of MATRVO without precomputation, when underlying agents have different numbers of tuples in the CTMAT representation.