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.

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).

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.

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

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 ;)