Starlings

This kind of natural beauty is what got me interested in swarm intelligence.

3D Boid Flock Video

I made a new video with our SwarmVis tool. This flocking is created with traditional Reynolds boid rules. Check it out!



A higher resolution version of this 3d flocking is available (8.2mb quicktime).

Tetrahedron Swarm

In my data visualization class, my group partner Niels Kasch and I have been working on a swarm visualization program (Niels has done most of the programming). It's not quite done yet, so a description of the software will come at a later date. I did however, want to show off one of my favorite domains: the three-dimensional tetrahedron swarm.


A high quality video of the tetrahedra (6.3mb quicktime) is available.


Here are some screenshots:




The shape is formed by agents adhering to the following procedure.

First, four corners are selected by the swarm via a simple election algorithm.
The agents follow the following rules:

• If a corner, be attracted to the three other corners very slightly.


• If not a corner, be attracted to the two closest corners with great, but equal, strength. That is, the output force vector of this rule is the sum of two vectors of magnitude f. Note that when an agent is on the line formed by its two closest corners, the forces cancel each other out.


• Avoid any agents that get too close.

The behavior can be changed pretty easily. With only three corners (instead of four), a triangle is formed. With four corners, but corners are only attracted to the two closest corners, a square is formed. More complex shapes are hard to do with these sets of rules. However, more rules (such as forming a circle) can be added to make the edges more robust.

It is amazing that these simple rules result in such neat behavior. This is what made me interested in this topic.

Hill-Climbing On Boid Swarm Configurations

I implemented a rather silly hill-climbing algorithm that I used on my boid density domain to find a configuration of boid parameters that will produce a flock of a desired density.

The algorithm is as follows:

1. Generate a bunch of random points around the best solution in the boid 4-dimensional parameter space (number of agents, alignment factor, avoidance factor, cohesion factor)


2. Check each one to see what the actual density is for that configuration


3. If the density is closer to the goal density than the best solution, then this solution is the new best solution and go back to step 1


4. If at any time a solution is found that is within the error bounds, stop

I made a video of this process (11MB).

This is pretty stupid. This will serve as a good starting point or framework for later more complex algorithms. I really need to use some kind of search with memory, so that I can predict where I should hill-climb next... or some kind of machine learning technique like k-nearest neighbor or kernel density estimation. Also, I hope to have some more search algorithms, such as simulated annealing, applied to this problem. At least now I have a nice little framework going so plugging in new algorithms should be rather simple.

Refactored My Swarn Source Code

Tonight I spent a significant amount of time putting my boid density domain together into coherent python script. I figure since I'll be having some people working with me now, I shouldn't put them through the same pain I go through whenever trying to integrate my scripts with bigger things. With this new script, all you have to do is call the run_boids and it spits out the density that it got.

Also, I made a pretty bad ass python vector class. I basically wanted a tuple where tup1 + tup2 is the mathematical sum, not the concatenation. Honestly, this was the first time I have used inheritance in python and I must say I wasn't disappointing. Plus, I heavily overloaded operators to make the coding easier. I'm probably more excited about this than I should be. It really will make my coding easier, though.

AGI '09 Paper: "Understanding the Brain's Emergent Properties"

I just recently submitted a paper to The Second Conference on Artificial General Intelligence. The paper is a position statement describes how our work in swarm-level interactive control could be applied to building artificial general intelligence. This paper was done in collaboration with Marc Pickett and Dr. Marie desJardins.

To read more about rule abstraction, check out our AAMAS '09 paper that is currently still under review.

Title: Understanding the Brain's Emergent Properties

Abstract:
In this paper, we discuss the possibility of applying rule abstraction, a method designed to understand emergent systems, to the physiology of the brain. Rule abstraction reduces complex systems into simpler subsystems, each of which are then understood in terms of their respective subsystems. This process aids in the understanding of complex systems and how behavior emerges from the low-level interactions. We believe that this technique can be applied to the brain in order to understand the mind and its essential cognitive phenomena. Once a sufficient model of the brain and mind is created, our framework could then be used to build artificial general intelligence that is based on human intelligence.



Link: Understanding the Brain's Emergent Properties by Don Miner, Marc Pickett, and Marie desJardins

New Swarm Videos

I added a few videos to my research site's video section. If you've never checked out my older videos, you should. They are probably more interesting than the ones talked about in this post.

First, there are videos of my Form Circle and Boid Density experiments, which are described in detail in my AAMAS '09 Paper: "Learning Abstract Properties of Swarm Systems" (currently under review). In addition, there is a video of a 3-dimensional boids domain I have been playing with.

I would like to mention that these videos were made by taking still image frames dumped by my simulations, then made into a video with the excellent program called FrameByFrame.

Form Circle
formcircle1.mov (3.6mb quicktime movie)

Boids in this demonstration self-organize into a circle. We varied the avoidance factor and the number of agents and ran several experiments to see what the radius would be. Our final goal was to create a mapping between the low-level parameters and the high-level property of radius.

Boid Density
boiddensity.mov (3.5mb quicktime movie)

Boids in this demonstration flock towards a goal (red dot). We record the average density on the way to the goal. Our final goal was similar to that of the form circle domain: creating a mapping between boid density and the low-level parameters.

3D Boids
boids1.mov (2.2mb quicktime movie)

Boids moving around in a 3 dimensional environment. Bigger boids are closer to the screen than smaller boids. Boids are dynamically color coded based on their flock. This program hasn't been integrated in my research yet.


Link: Don's Swarm Videos

AAMAS '09 Paper: "Learning Abstract Properties of Swarm Systems"

Update: This paper has been rejected :(. Time to address the reviewers' comments and get ready for IJCAI 09.

I just recently submitted a paper to the Eighth International Conference on Autonomous Agents and Multiagent Systems (AAMAS '09). The paper describes work done by myself and my adviser Dr. Marie desJardins and describes our current endeavors in swarm-level interactive control.

To make a long story short, this paper discusses the method of rule abstraction, which is used to define high-level properties of swarms that emerge out of low-level behaviors. We provide an example implementation of rule abstraction and apply it to two domains: agents that self-organize into circles (shown in the image in this post) and boid agents that flock.

Title: Learning Abstract Properties of Swarm Systems

Abstract:
Rule abstraction is an intuitive new tool that we propose for implementing and controlling swarm systems. The methods presented in this paper encourage a new paradigm for designing swarm applications: engineers can interact with a swarm at the abstract (swarm) level instead of the individual (agent) level. This is made possible by modeling and learning how particular abstract properties arise from low-level agent behaviors. In this paper, we present a procedure for building abstract properties and discuss how they can be used. We also provide experimental results showing that abstract rules can be learned through observation.



Link: Learning Abstract Properties of Swarm Systems by Don Miner and Marie desJardins