Ant Clustering

on

アント・クラスタリングは蟻の行動を手本として効率化を図るアルゴリズム（Ant Colony Optimization / ACO）の一種で、単純な規則に従うエージェントによって類似した物体を集合させます。





蟻をまねる
蟻の巣には、食べかすや死骸を集めたゴミ捨て場や、幼虫を成長段階ごとに分けた保育室があります。蟻は進化の過程で、全体を見渡せなくても空間的な整理を行う方法を身につけました。

この蟻の行動をコンピュータで再現してみます。



このデモではユニットの特徴を色として表現しています。グレーはエージェントです。

1000ステップ毎にキャプチャした画像を約1000枚をつなげているので、計100万ステップを実行しています。再生するといきなり塊ができているように見えますが、実は最初の数千ステップである程度の大きさとなっています。その後、時間をかけて特徴の選別が進み、最後のフレームでは色の塊ができています。


シミュレーションの方法
端と端がつながった平面上に、規則に従って行動するエージェント（蟻）と特徴を持ったユニット（ゴミ・幼虫）を置きます。

エージェントは以下の規則に従って行動します。
・上下左右のいずれかへ動く
・周囲の物体の密度が、低ければ持ち上げ、高ければ置く
・周囲の物体との類似度が、低ければ持ち上げ、高ければ置く

これを何度も繰り返すと、特徴ごとに分かれた塊が徐々にできてきます。

３種類のユニット（縦横50マス、エージェント数500、ユニット数500）

無段階の特徴（縦横50マス、エージェント数500、ユニット数500）


コード

エージェントが持ち上げる・下ろすを判断する部分のコードです。

float kCrowd  = 8;//持ち上げるときの閾値

// 持ち上げるかどうかを判定する。引数はエージェントが重なったユニットのID
void Agent::pick(int _id){
    vector unitArray = app->getUnitArray();//全てのユニットを取得
    
    int aroundNum = unitArray[_id]->getAroundUnitNum();//対象ユニットの周辺のユニット数
    float density = powf(aroundNum, 2) / ( powf(aroundNum, 2) + powf(kCrowd, 2) );//周囲の密度 　多1〜少0
    float difference = unitArray[_id]->getAroundDifference();//周囲との色差。　違1〜似0
    
    float pick = (1-density) * powf(difference, 4);//値が大きい程、持ち上げやすい
    
    if ( ofRandom(1) < pick ) {
        isCarry = true;
        carryUnitID = _id;
    }
}

// 持っているユニットを下ろすかどうかを判定する。引数はエージェントが重なったユニットのID
void Agent::drop(int _id){
    
    vector unitArray = app->getUnitArray();//全てのユニットを取得
    int aroundNum = unitArray[_id]->getAroundUnitNum();//対象ユニットの周辺のユニット数
    
    float density = powf(aroundNum, 2) / ( powf(aroundNum, 2) + powf(kCrowd, 2) );//周囲の密度 　多1〜少0
    float difference = unitArray[_id]->getAroundDifference();//周囲との色差。　違1〜似0
    float drop = density * (　1-powf(difference, 4)　);//値が大きい程、持ち上げやすい
    
    if (ofRandom(1) < pDrop) {
        isCarry = false;
        carryUnitID = -1;
    }
}
まとめ 単純なルールに従うだけで、無秩序から構造が現れてくるのはとてもおもしろいです。サンプルでは色の塊を作りましたが、ルールを変える事で格子や縞などの模様を作る事もできそうです。

デモを実行しながら部屋の方付けをしていたので、ルンバが自動で散らかった部屋をクラスタリングしてくれたらいいのに、と思いました。