raja-s / orca Goto Github PK
View Code? Open in Web Editor NEWAn attempt at a simple implementation of the ORCA algorithm π€π’π€π
Home Page: http://gamma.cs.unc.edu/ORCA/
License: MIT License
An attempt at a simple implementation of the ORCA algorithm π€π’π€π
Home Page: http://gamma.cs.unc.edu/ORCA/
License: MIT License
As is well explained in both the paper and the book, the linear program that maximizes a vector in the intersection of a set of half-planes could at any point in time not have any solution. In the implementation, this translates into an exception called LinearProgramInfeasibleException
thrown at any point where the linear program is found to be infeasible.
When running the demos, I get this exception way too many times, especially in cases where the agents are clearly far from one another and can't possibly be on a collision course.
Line 189 in 4d4e2bb
So the Line
class is implemented based on the equation: y = a x + b, where a is the slope of the line and b is its y-intercept. This is not ideal in my opinion. For example, in case of a vertical line, the slope is set to std::numeric_limits<double>::infinity()
from the limits package.
A better implementation could be based on the equation: a x + b y + c = 0, which I think represents all orientations of a line in a cleaner way.
Another possibility to consider is to represent a line by a point and a vector, which is equivalent to a line parametrization:
x = x0 + vx t
y = y0 + vy t
As the whole implementation is still buggy, reimplementing the Line
class and readapting all the other classes using it might help uncover bugs and hopefully fix them.
I refer to this as the βΟ-βt problemβ because it all revolves around the choice of the values of Ο and βt (which correspond to ORCA::tau_
and ORCA::deltaT_
in the implementation). Here's an explanation of these two values based on the paper:
Ο represents the amount of time for which we want to βplan aheadβ. More formally, it is the minimum amount of time in the future during which we want to guarantee that no collisions will occur between agents. So the greater the value of Ο, the earlier agents will become aware of the presence of other agents moving closer to them.
βt represents the amount of time during which we want to move our agents with their new velocities obtained by planning ahead for Ο time.
This means that the following constraint must hold: 0 < βt <= Ο, otherwise collision-free navigation is not guaranteed.
To me, it makes sense to have βt significantly smaller than Ο. If instead we set βt = Ο, then when agents compute collision-free velocities, they will go all the way until they are literally stuck to one another at which point they recompute new velocities. That is because the ORCA algorithm is optimal by construction, in the sense that agents will deviate as little as possible to avoid collision.
Here's a screenshot of the demo running with this configuration:
If we do set βt to be smaller than Ο, agents will start slowing down smoothly as expected and deviate from their current trajectories when crowds start forming. The problem is that with this configuration, for some reason agents suddenly start penetrating one another and moving around while they're overlapping.
Here are two screenshots of the demo showing this effect:
Note that in a real-world application with physical robots for example, agents would obviously bump into one another instead, and the behavior from that point on would probably be undefined.
What confuses me even more is the fact that the formulation of the algorithm only mentions βt once, in the equation for updating positions at every iteration, and it doesn't say anything about the relationship between Ο and βt.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
π Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. πππ
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google β€οΈ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.