Cone stacking algorithim

[RedSon]

Greetings all,

Last weekend I was at my son's football class (soccer). Every week they play this game where the coach scatters a bunch of cones across the field, and the kids pretend they are trees. The goal is to kick the ball from one end of the field to the other without hitting the cones. Anyway that is not what piqued my interest.

What did pique my interest was the time when everyone was made to clean up. What happened was this: The kids all scattered about picking up cones, each had one or two in their hands, then they would look at the kid next to them and they would combine their stacks and each kid would combine their stacks with other kids until the coach came by and added their little stacks to the master stack. But to complicate things, the kids would not stop gathering cones and stacking them, sometimes they would make a new stack, or sometimes they would add to a stack they created. Some kids would then go around and collect other kid's stacks and place them on to their stack. Or sometimes they would leave their stack alone and go collect somewhere else waiting for the coach or some other kid to pick theirs up.

So the question is, how could someone model this real world behavior in code? Does this behavior sound like any known algorithms?

It seemed like a modified merge sort to me, but I like to think of the kids as agent sorters so there must be some kind of recursive element to it. Also there has to be some work in deciding how many agents are optimal, and what is the maximum stack size. Also there is an element of "load balancing" where the little sorting agents will abandon their area if it is stacked and move to a more entropic area.

If anyone would like to start analyzing this behavior with me please add your thoughts.

[JosAH]

It's equivalent to a Capacitated Vehicle Routing Problem (CVRP); it's a filthier problem than just a few 'simple' Travelling Salesmen Problems (TSP) and can take hours to solve when the capacity restrictions vary per vehicle/child. If the coach/depot of the system is moving itself the catastrophy is imminent. Don't go there.

kind regards,

Jos

[RedSon]

Interesting reading. But from what I see a CVRP contains vehicles originating from one depot. So that means this would be particularly difficult since there would be multiple depots in the system.

If anyone has access to literature say from ACM or elsewhere or knows where to find full text research papers on this I would be very thankful if you would share.

[JosAH]

@RedSon
If there's only one coach and all the cones have to be handed over to him/her then this is also a single depot CVRP. The 'C' comes from the fact that kids can only carry so many cones maximum. Most of the time goes into solving a TSP per kid over and over again.

Those problems typically result in a 'flower shape' solution: the coach is the center of the flower and all the tours make up the leaves of the flower. Multiple depots add to the complexity of the CVRP. If the depots are moving I don't even want to try to solve this ;-)

A couple of Greek guys really worked on this problem: Bertsimas and Bertsekas and Papedimitriou come to mind (google for them and double check my spelling). Especially the last guy did quite a bit of work on the big-Oh aspect of these dirty problems. Also check Karel Lenstra and Alexander Schrijver (twp Dutchmen, yea!) who did a lot of work on 'local search' heuristics.

kind regards,

Jos

[Glenton]

It would be interesting to see if you could get similar complex global behaviour from a simple set of local rules. In other words, build a model with a bunch of "koids" (as opposed to "boids") who only see a certain radius. Then they have a couple of simple rules about which direction to go to pick up visible cones, add them to their stack, drop their stack and hand their stack to the coach.

I would bet that a handful of simple rules will give you a good representation of the the way the kids buzz around. It works for boids anyway!

As for optimizing the collection method - well that's a different story altogether... But you could tweak the rules and see if you can find anything that works better. Then the kids just need to be told the new "rules"! Now there's the real challenge...

I'm sure you could find someone to publish it - talk to the Santa Fe Institute!

[RedSon]

Can you describe more about this "boid" thing? Where are you getting that term from?

[Glenton]

It's a mixture of bird and android I guess.
http://en.wikipedia.org/wiki/Boids
http://www.red3d.com/cwr/boids/
developed by Craig Reynolds...