読者です 読者をやめる 読者になる 読者になる

人工知能に関する断創録

人工知能、認知科学、心理学、ロボティクス、生物学などに興味を持っています。このブログでは人工知能のさまざまな分野について調査したことをまとめています。最近は、機械学習、Deep Learning、Kerasに関する記事が多いです。



単純な追跡アルゴリズム

Javagame

もっとも単純な追跡アルゴリズムを実装してみます。環境はタイルワールドで追跡者が獲物を追いかけます。プレイヤーは矢印キーで獲物を操作でき、追跡者はAIが操作します。絶対逃げ切れないけどせいぜいがんばってください(笑)

chase_test.jar

追跡処理

追跡するのは追跡者(Predator)です。なのでPredatorクラスにchase()を実装します。chase()の引数は追いかけるべき獲物です。

    /**
     * 最も基本的な方法で獲物を追跡する
     * 
     * @param prey 獲物
     */
    public void chase(Prey prey) {
        if (x > prey.x) {
            x--;
        } else if (x < prey.x) {
            x++;
        }

        if (y > prey.y) {
            y--;
        } else if (y < prey.y) {
            y++;
        }
    }

追跡者のx座標と獲物のx座標を比較して追跡者のx座標の方が大きかったらxを減らし、小さかったらxを増やしています。また追跡者のy座標と獲物のy座標を比較して追跡者のy座標が大きかったらyを減らし、小さかったらyを増やしています。これだけ。非常に単純な方法です。こうすると追跡者と獲物の間隔が徐々に小さくなって追跡者が獲物に近づくことになります。

問題点

この方法の問題点は最短経路を通って追跡しない点です(下図)。

f:id:aidiary:20100518151629j:plain

この手法はif文が並ぶかっこうなのでxとyを同時に減らす、つまり対角上の移動が優先されてしまいます。その結果、上の図のように対角上に移動した後まっすぐ獲物に近づくという不自然な経路になってしまうわけです。追跡者と獲物間にひいた直線上を通って最短経路で追跡する手法がLOS追跡です。今度取り上げます。