I've been making a simulation of ants.

 

Basically so far I have just a bunch of ants that randomly walk around the screen. I've done some quadtree magic and I'm able to get thousands of ants walking around at once, on their own little journeys.

 

The movement is very ant-like, so I'm happy with that.

 

My idea is to simulate some kind of collective thinking. They don't necessarily have to be ants (they could be little robots or whatever), but I want to try to simulate something whereby each ant works completely independently, but can learn from the other ants to achieve their tasks as a group.

 

I'm not entirely sure how to go about this. Any suggestions?

 

I was thinking about something like this:

 

- Each 'ant' can see a small distance around himself. Not very far at all (10 pixel circle around him).
- Each ant knows his own position. I'm not sure if I should just give each ant access to his own coordinates or make him work stuff out by how many footsteps he's done in each direction
- Ants can interact with each other if they're standing next to each other and share their information
- Each ant has a limited amount of energy. They can regenerate energy by standing still.
- The will be other insects roaming around (spiders??) that can eat the ants.
- When an ant dies it gives off a 'smell' around him to warn other ants
- There will be a couple of safe zones. The ants wont know where these safe zones are unless they discover them or until they're told about them
- Some of the terrain will have obstacles

 

I also need some kind of objective for the ants. For example, they have to work together to collect as much food from large food piles that they have to discover then make a train to bring back the food to a safe zone.

 

Or maybe they need to collectively discover as much of the terrain as possible and report it back to some source.

 

I dunno. Any ideas? It's completely completely completely pointless and I'm sure it's been done thousands of times before but it's quite interesting to do from scratch.

 

I need some kind of objective and something to time how long it takes them to perform the task, then try to tweak the code so they do it as fast as possible.

 

I'm also thinking about maybe the ants having a limited amount of brain power in which to store the information they know. Hmm.

Limited amount of brainpower? Have you thought of having them contest the next US presidential election?

Bite off bits of a leaf and carry them to a safe zone? It is something ants do in reality and it's facinating to watch.

Real ants leave a scent trail wherever they go, and they can communicate stuff with it too.

 

They have one scent combination for 'normal', i.e. just wandering about. Once they find some food, they leave a different combination of scents on their way back to the nest. Other ants that come accross the scent trail can tell which direction the food is in, so they set off to to get it too.

 

The scent trails deteriorate fairly quickly, so once the food supply runs out ants stop following the trail and it dies off.

 

Think they communicate other stuff, too, but can't remember. Go look it up!

A "limited amount" is considered too much, apparently...

I looked into doing something quite similar for my dissertation; I had planned to have autonomous 'ant' agents, copied from one of a limited number of 'templates', which the user could write using a very simple 'ant programming language' (go forwards, lay pheromone 1, if food lay pheremone 2, etc etc), and see if I could get some kind emergent behaviour out of the colony, and if I could, see what the minimal set of rules / templates was required, or see if they could make it through a maze, and that sort of jazz.

Anyway, I discussed it with some people and had a chat with the university's AI chap (this guy), who fairly promptly told me that this had all been done before and that I'd have to come up with something a bit better for my dissertation. I was pretty gutted, because I'd never heard any of the research that was basically identical to my proposal.

So, anyway, yes, my point is, if you're looking for pointers, there's probably a reasonable wealth of academic works out there that are relevant to you, if you're bothered. Turns out there's a whole wikipedia article on some related stuff: http://en.wikipedia.org/wiki/Ant_colony_optimization

Indeed after researching ant behaviour at the library for ages, I end up finding that someone has already done something very similar before with genetic programming (his thing is based in C#).

 

It's hugely sparked my interest in genetic programming, though. I've knocked up a few prototype engines in javascript, and I'm next going to attempt to make various 2d models teach themselves to walk.

 

Ants, though, humpf. I really like the idea.

Has it been done with Bees?

If anyone's interested in genetic programming:

 

A couple of friends and I have set up a good project for messing around with the idea of getting a ragdoll to walk using GP.

 

http://code.google.com/p/gp-movement-engine/

 

We've only just started. We're planning to do it using flash with box2d.

 

I've started a prototype in javascript just to get an idea of what works well and what doesn't. Feel free to mess around with the source in the svn. If anyone's quite interested in helping us out with the project then please feel free to help out and i can add you to the dev list :)

 

Anyway, here's my little prototype experiment so far:

 

http://beta.mylotro.eu/images/gp.html (best viewed in chrome!!!)

 

The idea is that it takes the 3 expressions in the boxes at the top, and mutates them until it finds an expression that equals 10000 (or close to).

 

Currently the population pool is massive. It starts at 90 but becomes 900 by the 2nd generation and stays at 900. I'll eventually try to reduce it once I've worked out exactly what works best with the mutation and crossover.

 

Also currently nodes are only doing self-crossover. I'd like to it eventually cross over in pairs.

 

But yeah. It finds 10,000 in ~7 generations at the moment.

I couldn't find the rag doll! :(

Still in development ;)

http://beta.mylotro.eu/images/test.swf

 

Teaching himself to stand up.

 

The physics are completely borked, mind you.

 

Oh, not to mention that it's running in real time instead of speeded up, so it'll take around a week/month(??) to get him standing up properly. PLUS, he's not being dropped in various poses, so it's not REALLY him getting to stand up.

 

So, it's bollocks really. But we're still developing it ;)

 

The next steps are:

 

1) fix the physics
2) give him the ability to actually pick up his upper legs (he currently has no muscles joining his hips to his upper legs).
3) Give the option to speed it up. Currently it's doing one test every 2.5 seconds. We could get this down to about 5-6 tests per second if we're clever. Flash has no real multi threading capabilities, so we're going to attempt to introduce basic threading and allow it to use more than one core.
4) Introduce a test that actually does something. Gotta do things like.. stand him in a position and hit him with a random force and allow him to steady himself. If we keep the force random each time it should give us something actually worthwhile.
5) Actually allow the damn data to be saved. Currently it doesn't! I'm going to make it so that everyone is working together to improve one instance, instead of everyone have their own instances (which restart every time!)

 

It's an experience trying to get this working :) i'm sure we're making huge mistakes, but I'm sure we'll iron them out as we go along.

 

Currently with the program I've been running at home for the past 4-5 hours I have a dude that is standing straight (and balanced) the majority of tests run :)

 

The physics stuff is really frustrating me, though. trying to emulate muscles is a real pain in the bum.

updated slightly with a speed slider ;)

 

still gotta add loading/saving before it's worth really trying out properly.

 

What kind of variables do you think each muscle will need to know about to keep it stable?

 

currently they know about the tension of all the other muscles, and they know the position of the 'torso'.

 

I'm thinking they'll probably need to know the angle of the other limbs and maybe how much pressure is on the limb, and the center of gravity for the entire skeleton.

 

hmmmmmm.

 

(sorry using this thread as a semi blog. makes it easier for me to keep focus!)

Left it running over night..

 

67 generations so far (929 tiny mutations each generation, so 62243 mutations!) and he's um.. falling over :(

I've got very little idea what methods you're using to do this, but I have to say that it hits some extraordinary balancing acts just before it resets and tries again.

Very very very simple methods at the moment.

 

- Generate 30 random equations for each limbs movements (possible variables to play with are the tension of all the other muscles), then spawn 30 mutated equations for each of those 30. so you have 900.
- Try every single equation and order them by which held him upright the longest
- Take the top 30 best and mutate them 30 times, so you have 900 again
- Find the best of those
- etc.etc.etc.

 

It uses various methods for mutation - stuff like swapping chromosomes with others or just altering a value or function to another.

 

The big problem for me will be the input data, I think. Knowing what variables each of the muscles will need to know about in order to know how much to tense. Currently it only knows the basic stuff.

Congratulations on making a John Cleese silly walks generator.

 

I love all this software learning program stuff.

I left it running overnight and it crashed Firefox :D I can only assume he stood up, went for a walk and got bored.

Doh >.<

You clearly need to skin it as Michael Jackson.

 

(Not the whisky expert. The other one.)