Sign in to follow this  

Collision Resolution ala air traffic control?

This topic is 4817 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey Jeremy, I'm currently trying to implement a collision prediction & resolution system in 2D, much like there [is/should be!] be for aeroplanes. Just to clarify, I'm not talking about collision detection to detect when things have already crashed into each other.. I'm trying to make something that will predict and avoid these crashes altogether :) Basically, given a few point objects that are flying through 2D space, I want an object to be able to look at its own velocity, and other object's velocities (and maybe their acceleration too), and be able to predict if they are about to collide, and then avoid a collision by changing velocity (ie speed or direction). The twist is that the other objects will be doing the same thing, so I have to avoid the case where both objects will swerve to avoid each other, but then crash on their new path. In reality my objects will preferably change speed rather than direction, but the principle's the same. I've been Googling for technical reports on aircraft systems to no avail. I know what a Markov chain is, if that's any help. If anybody has experience in this or even just has an idea to get me started, that'd be great. Sorry if my post is a bit long. Thanks!

Share this post


Link to post
Share on other sites
Who is Jeremy?

It's probably not as difficult a problem as it might seem. Prediction is pretty trivial and then you can perform collision detection on those predictions. A 2D object moving in a straight line will have a roughly rectangular predicted path, its width based on the object and its length based on the object's velocity and the timescale.

When it comes to corrective behaviour, there are a few simple things you can do. You might try a quick search of several different evasion techniques to see which produces predicted paths with no collisions. Such techniques might simply come down to 'steer left', 'steer right', 'slow down', 'speed up', and the other 4 combinations of those. Maybe there are more formal solutions but I don't know if they are necessary for non-critical systems.

Share this post


Link to post
Share on other sites
Think fast! Two cars are headed straight for a head on colision. They both swerve right. Do they still crash?

Some people's gut reaction tends to be "yes, they both turned the same way and hit each other" but if you think for a second, you realize that since they are facing opposite directions "Right" is also in opposite directions.

Ok, I know this example may seem very stupid and that very few people would have said "yes," but it helps to illistrate a very important point.. Even though a problem may seem complex, a simple solution using just a single, or couple small rules often solves the problem perfectly.

For the airplane problem, having them change altitude (randomly assigning which plane rises or falls) and possibly vearly slightly off course should work wonders and depending what exactly you are doing should also be a good approximation of real traffic control.

Share this post


Link to post
Share on other sites
Quote:
Original post by Drakonite
Think fast! Two cars are headed straight for a head on colision. They both swerve right. Do they still crash?


I know what you mean Drakonite. In an air traffic control situation this wouldn't really be a problem, as the decisions are centrally coordinated and both can be instructed with knowledge of what the other is doing.

However in the car situation, if one steers right and one steers left, then they probably will crash, and they don't have the time to phone each other up and ask which way the other one's about the swerve. Similarly, one car could slow down so that the other car passes over its future path, but if the other car slowed down in the same way they'd still crash, only slower. So one of them has to take the initiative, but there has to be some way of choosing the option with the least risk, when neither car knows what action the other is going to take.

PS I don't know what the "hey jeremy" was for, just messing around :)

Share this post


Link to post
Share on other sites
Craig Raynolds' steering behaviours is pretty much tou are looking for: http://www.red3d.com/cwr/steer/

There's tons of other interesting stuff relating ot the issue on his site.

Share this post


Link to post
Share on other sites
You should fallback to traditional geometric collisions, but instead of a bouding box arround the airplane, you should use an hemisphere, which changes size based on the airplane's altitude, attitude and speed.

An hemisphere because the airplane cant possbly collide with anything behind him, and he can change attitude in any XY axis, which multiplied by its speed, makes an hemisphere, if you can picture it.

The hemisphere will be large enough for the airplane to have 5 minutes to avoid collision with other hemispheres, so the radius can be calculated by the airplane's speed, multiplied by the amount of warning time we want, 5 minutes.

So, if the airplane travels at 600Km/h, and we want a 5 minute warning time, thats a 50Km radius for the hemisphere, which may seem large, but you are working in 3D, so you can instruct planes to go into higher/lower division planes.

You can also build "3D vapor structures" arround airports.

Imagine one of those buildings used to park cars, with multiple stories. The car has to navigate a certain path to get from ground floor to floor 10.

Thats what your airplanes have to do in an aproach vector. They have to go into a waiting stack, then into an aproach vector, and finally land. There are as much aproach vectors as there are runways, so...

That's what i could come up with from the top of my head...

Share this post


Link to post
Share on other sites
Quote:
Original post by memon
Craig Raynolds' steering behaviours is pretty much tou are looking for: http://www.red3d.com/cwr/steer/

There's tons of other interesting stuff relating ot the issue on his site.


That's a really good site and actually what gave me the original inspiration for this project :) I'll check it out again in case there's something handy I missed out.

Yes, these guys seem to be avoiding crashes pretty well.
http://www.red3d.com/cwr/steer/Unaligned.html

What you said was helpful, Prozak, some interesting ideas about the hemisphere and stuff.

Thanks all

Share this post


Link to post
Share on other sites
With planes, you have a REALLY helpful attribute to make all these calculations much simpler: Location (from GPS or the like).

Using the location attribute, you can do something like make the 'lower left' plane slow down while the 'upper right' plane does not, and things like that. If you're using an actual globe, then instead of 'lower left' it might be 'southeastern most' or somesuch.

This way you automatically have a way to distinguish between planes in a deterministic way and always have one perform one action and the other do another action.

Also, you could do '1 pass' on all the planes to calculate the changes and instead of directly implementing them, have them run the tests again using the changes calculated from the first 'pass'. This could be acomplished in real life by having some kind of transmitter on each so that the planes themselves would be in constant communication (probably via radia. You'd need some good error correction and the like, and you'd have to allow for lack of communication in extreme circumstances).

Share this post


Link to post
Share on other sites
Quote:
Original post by Extrarius
you'd have to allow for lack of communication in extreme circumstances
In my system there is no communication between vehicles, so it's always an extreme circumstance! They're meant to be cars and the time to a potential collision will generally be in the range of 1 second or so. So I was wondering if there was some uncertainty algorithm, to at least maximise the chance of not crashing?

I just remembered that I learnt some stuff on Game Theory, can anybody else remember anything relevant to that? Like the Prisoner's Dilemma where neither prisoner knows whether the other one's going to confess and they have to choose a strategy to maximise their chance of getting set free.

Share this post


Link to post
Share on other sites
Quote:
Original post by NickNickNick
Quote:
Original post by Extrarius
you'd have to allow for lack of communication in extreme circumstances
In my system there is no communication between vehicles, so it's always an extreme circumstance!


Is it essential that there is no knowledge exchanged? And which is more important to you, reducing the number of collisions overall, or providing the illusion that each vehicle is doing its best to reduce collisions (which may not be as effective)?

Quote:
I just remembered that I learnt some stuff on Game Theory, can anybody else remember anything relevant to that?


I doubt game theory will help here as you don't have much of a trade off... either both vehicles crash or both don't. Game theory would work better when the opponent is trying to make you crash and avoid a collision themselves, or vice versa.

In fact, I expect that using game theory to come up with an optimal solution would probably result in the algorithm being something trivial such as 'always turn left', which will work almost all of the time but be boring from a behavioural point of view.

Share this post


Link to post
Share on other sites
Quote:
Original post by NickNickNick
Quote:
Original post by Extrarius
you'd have to allow for lack of communication in extreme circumstances
In my system there is no communication between vehicles, so it's always an extreme circumstance! They're meant to be cars and the time to a potential collision will generally be in the range of 1 second or so. So I was wondering if there was some uncertainty algorithm, to at least maximise the chance of not crashing? [...]
Well, you could still simulate communication by having each car process its own changes as well as approximate changes of other cars based on their speed, acceleration, etc. This would allow you to continually make changes as neccessary while potentially avoiding situations where the 'first pass' changes would cause a collision.

If the vehicles have an internal model of the road system, this could be made even easier since it could be presumed that all cars want to stay on the road (Which helps in predicing future speed/accel/etc since you know that if the road turns ahead, the vehicle in front of you will either turn or hit the divider if there is one).

Also, I think 1 second would be plenty of time to help avoid collisions that the Nth pass still misses (which shouldn't be many), and if you use a client-client radio-like system the delay wouldn't be much at all (maybe 100ms or so under common conditions since you aren't transmitting very far, and you could do the communication at the same time that you're running the simulated communication and prediction to help avoid losing time. Thus you could run an initial algorithm for .1 sec while also receiving the other cars destination and future plans and then run a second algorithm with the new data for the next .3 sec while implementing the initial algorithm's changes and then you still have .6 sec to adjust the initial algorithm's changes using the outcome of the second algorithm).

Share this post


Link to post
Share on other sites
Relative orientation is also a good deterministic method.

The rules for boats could be applied here fairly easily, it seems to me:
1) If I'm heading straight toward a boat that's headed straight at me, strafe right.
2) Don't run into a boat infront of me
3) Avoid ( arbitrary maneuver ) any boat approaching from starboard. ( And therefore expect any boat approaching from port to avoid me )

And since you know ( since it's a simulation ) that the other boat is actually going to do what it's supposed to :P, collisions should be avoided if at all possible.

Of course, with more than 2 agents it's more difficult. Maybe you can use a BOIDS-style action-combination system to incorperate avoidance of all the different boats.

Share this post


Link to post
Share on other sites
Sounds good. I think the best solution would be to mix the continual reassessment suggested by Extrarius, with me22's idea of having different prescribed behaviour depending on the angle of the collision. I'll also try to work in some randomness to each object, even if it's just something like increasing the odds of it attempting to accelerate beyond the point of collision.

I think I've got enough info to make a start on this. Thanks for all your input guys!

Nick

Share this post


Link to post
Share on other sites
Quote:
Original post by NickNickNick
Quote:
Original post by Drakonite
Think fast! Two cars are headed straight for a head on colision. They both swerve right. Do they still crash?


I know what you mean Drakonite. In an air traffic control situation this wouldn't really be a problem, as the decisions are centrally coordinated and both can be instructed with knowledge of what the other is doing.

However in the car situation, if one steers right and one steers left, then they probably will crash, and they don't have the time to phone each other up and ask which way the other one's about the swerve. Similarly, one car could slow down so that the other car passes over its future path, but if the other car slowed down in the same way they'd still crash, only slower. So one of them has to take the initiative, but there has to be some way of choosing the option with the least risk, when neither car knows what action the other is going to take.


I think you may have missed my point... Even if you have some rule prohibiting you from coordinating the avoidance efforts at the time of the crash there should still be a very simple set of at most a couple rules that as long as both entities are programmed to follow the same set of rules (they never have to communicate to do this) you should be able to avoid collisions the majority of the time.

Just because you can't communicate doesn't mean a well placed rule doesn't work. If you are implying that you don't even get to control the programming of the opposing vehicle so you don't know if they'll follow the "steer right" rule, then unless you can outperform the other vehicle to the degree they couldn't hit you if they wanted it, you can't guarentee not to get in a crash.

If that is the case I'd just pick the most sensible, effective, and simple plan I could and hope whoever was controlling the other vehicle came to the same conclusion. Perhaps the link posted earlier is a better solution, but meh. I'm all for simplicity :)

Just for completeness sake, for two airplanes the simple rule would most likely be...

if(my Center Is Below Their Center)Dive;
if(my Center Is Above Their Center)Climb;
if(my Center Is To The Right Of Their Center)Steer Right;
if(my Center Is To The Left Of Their Center)Steer Left;
if(I Can Go Slower And Not Fall)slowDown;

In other words... Steer away and hit the breaks ;)

Share this post


Link to post
Share on other sites

This topic is 4817 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this