COMP 790-058: Robot Motion Planning and Multi-Agent Simulation
Auston Sterling
For efficiency reasons, many agents in multi-agent simulations look at a limited number of neighbors when summing social forces or checking for collisions. Usually, these neighbors are selected by choosing the nearest neighbors by straightforward Euclidean distance. This project will investigate and evaluate alternative metrics for selecting the most important neighbors to any given agent.
In the real world, there are often times when pedestrians need to be aware of agents who are further away than many of the nearer neighbors. A bicyclist traveling at a much faster speed than people walking might be on track for a collision in the near future despite being further away. Pedestrians need to be aware of potentially dangerous agents such as cars. An extendable framework for tracking important agents could also be useful in more specialized situations with pursuers and evaders, or with agents who behave more erratically than others. Being able to determine the importance of an agent would help other agents intelligently respond to changing situations at a larger scale.
Euclidean distance has been fairly successful so far, especially for simulations where all agents want to move at approximately the same speed in the same direction, so not much work has been done in this area yet. However, there has been a large amount of work done on amplifying or reducing the effect of social forces between agents after it has been established that they are near each other. Perhaps some of these computations could be moved to be earlier in the process so they can play a role in determining importance. Among the papers in this area are:
I have extended the Menge pedestrian simulation framework to allow for alternative neighbor selection metrics. It's not a particularly elegant system, but it's enough for the purposes of this project. I've written a Menge project file describing a situation where nearest neighbor selection causes collisions. Additionally, I added a few ways to evaluate the performance of these metrics. With those in place, I have been able to test a few importance metrics.
The most successful metric I have found has used predicted time to collision. Each agent can fairly quickly compute the time of a future collision with each other agent assuming that they retain their current velocities. The most important neighbors are selected by choosing the agents with the lowest predicted time to collision. Menge's default k-d tree can be used to limit the number of agents being considered, as long as the cutoff distance is sufficiently large. In my testing so far, this metric has been very effective at selecting the important agents from a large distance away. I've recorded some videos comparing this metric with nearest neighbors, and included them further down this page.
In a previous metric I tested, instead of comparing the distance between the points at the centers of the agents, neighbors are determined by comparing the distance between line segments, with one endpoint at the current agent position and one endpoint at the position the agent is expected to be in a few seconds. This succeeded in prioritizing agents in the direction of an agent's movement, but had some issues of its own. If the segments intersect at t=0 along one line, and t=tmax along the other line, the metric would consider the corresponding agent to be a high importance neighbor, when they're actually never going to come close. The time to collision metric uses the same general idea, while being faster and more effective.
I am also interested in looking into a few other metrics, though these are not yet complete. I want to see about using a very simple metric based on Euclidean distance, but taking into account relative velocities, where similar velocities would indicate that collisions are unlikely. Finally, I've been working on a clustering-based approach, where agents with similar positions and velocities would be clustered together. Neighbors could then be taken from multiple different clusters to ensure diversity. My concerns are that clustering is often slow (especially to do every timestep), it is hard to predict the number of clusters needed, and some qualities of some clustering techniques are undesirable (k-means attempts to have clusters be the same size, for example).
One simple way to evaluate the efficiency of these metrics is to compare the difference in scene update times between runs with different metrics. That information is easy to pull from Menge. It has also been helpful to store the distance between each agent and the designated "important" agents from the first time they were considered neighbors. Effective metrics will have this distance be a large number, while ineffective metrics will not consider them to be neighbors until they are almost adjacent. Finally, counting the number of collisions in a run, especially when using an RVO pedestrian model which ensures collisions normally should never occur, will highlight instances where the metric is failing to consider the appropriate neighbors.
Below is a demonstration of the Menge project I've set up to demonstrate these metrics. This first video shows the case where all agents are always considered to be neighbors. As such, there are no collisions.
The next video is using some of the settings I've found to be common in the other projects, notable nearest neighbor calculation with a maximum of 10 neighbors. This is actually a fairly tame example; in other runs, nearly all of the agents get run over at some point.
The following video shows the same setup, but using the predicted time to collision metric. Notice how the behavior of the blue agents more resembles the movement in the "everyone is a neighbor" video.
This final video shows that the time to collision metric is effective even with a lower maximum number of neighbors. In this case, only five agents can be considered neighbors, but they all manage to avoid the fast agents regardless. The video pauses occasionally as I select agents (highlighted in white) to show which other agents they consider to be their neighbors (with the metric's value overlayed in white text). They consider the fast agents to be neighbors from a long distance away, which allows most of them to avoid collision (though with only 5 neighbors, it's not perfect).
My remaining schedule (more of a to-do list than anything else) is as follows:
1-3 weeks: Investigate possible alternative metrics by studying similar work and gathering ideas. Extend a multi-agent simulator to handle alternatives to Euclidean nearest neighbor selection. Select promising metrics to test.
4-6 weeks: Implement and debug the chosen metrics. Establish quantitative methods for comparing the efficiency and effectiveness of these metrics. Continue modifying metrics as implementations turn up new challenges and approaches.
7-9 weeks: Evaluate metrics using previously established methods. Refine or expand the most successful metrics. Prepare final paper and presentation.