2018年5月
    1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31    

Amazonウィジェット

  • お気に入り
  • 欲しいもの
  • 面白かった本
  • Raspberry Pi
  • ドローン
  • 書籍ランキング

AdSense

  • 広告
無料ブログはココログ

C言語

2018年5月 2日 (水)

コラム:連載の落穂拾い。 pdcursesはprintfと両立できない。

visualStudioのビルド切替機能を使って、簡単に切り替えられるように設定してみた。


printfとの両立ができないのはncursesもpdcursesも同じだったので、
先週までの遺伝的アルゴリズムのプログラムでは最も厄介なところだった。

printfで手軽にリスト形式で内容を書き出したりするのはやはり便利なので、
これが使えないのはちょっと効率が悪い。

そこで、visual studioのビルドメニューにある、
Debugビルド時はprintf有効でcursesなし。
Releaseビルド時はcursesのみ有効になるように、プロパティで設定した。


#ifdef _DEBUG
#include <curses.h>
#endif

などとすれば、DEBUGビルドの時だけincludeが有効になる。


<追記>
pdcursesについて。

initscr()は、メインからコールしないと動かない。
ウィンドウのポインタが影響するらしい。openglでも似たようなことがあった。

// 初期化はmainからコールしないと動いてくれない。
    if (initscr() == NULL) {
        return 1;
    }

pdcurses自体のマニュアル
https://pdcurses.sourceforge.io/doc/PDCurses.md


2018年4月25日 (水)

遺伝的アルゴリズムで育てる「お掃除ロボット」 その10 ~交叉アルゴリズムの改良~

前回までmainべた書きで書いていたところを、
下記のように書き換えた。
以降kousaの中身だけを書き換えることで、アルゴリズムを変更できるようにした。

  //選定
  //ランキング式で選定
  qsort(inds, INDIV_LEN, sizeof(inds[0]), sorter);

  //best record
  if (bestInd.score < inds[0].score) {
   bestInd = inds[0];
  }

  //交叉
  //上位半分をベストと掛け合わせ、バッファ下半分に書き込む。
  //バッファ上半分はペアを作って掛け合わせる。
  //int KOUSA_NUM = 1;
  int kousa_lim = INDIV_LEN / 2; //境界を計算
  for (int i = 0; i < kousa_lim; i++) {
   indiv_t work0 = inds[i];
   indiv_t work1 = bestInd;
   kousa(&work0, &work1);
   inds[i + kousa_lim] = work0;
  }
  
  for (int i = 0; i < kousa_lim; i+=2) {
   kousa(&inds[i], &inds[i+1]);
  }

前回のkousa関数は2点交叉だけを実装したものだったが、 今回は突然変異のコードを入れてみた。 遺伝子を交叉させたあとに、1/2の確率で遺伝子のいずれか一個に変異を起こすようになる。


getStartEnd(int *start, int *end) {
	int a = rand() % GEN_LEN; //0<= a < GEN_LENをとり得る。
	int b = rand() % GEN_LEN + 1; //+1はfor文の終了値のため。
	if (a > b) {
		*end = a;
		*start = b;
	}
	else if (a == b) {
		*end = GEN_LEN - 1;
		*start = GEN_LEN / 2;
	}
	else {
		*end = b;
		*start = a;
	}
}

void kousa(indiv_t *ind_a, indiv_t *ind_b) {

	//二点交叉を使う
	int start, end;
	getStartEnd(&start, &end);
	//printf("start,end = %2d,%2d\n", start, end);

	gen_t temp_a;
	gen_t temp_b;

	for (int i = start; i < end; i++) {
		temp_a = ind_a->gen_set.gen[i];
		temp_b = ind_b->gen_set.gen[i];

		ind_b->gen_set.gen[i] = temp_a;
		ind_a->gen_set.gen[i] = temp_b;
	}

	//突然変異を入れる。
	totsuzen(ind_a);
	totsuzen(ind_b);
}

void totsuzen(indiv_t *ind) {
	int sw = rand() % 2;//変異を起こすかどうかを決めるスイッチ
	int idx = rand() % GEN_LEN; //どのgenを変異させるか

	if (sw) {
		saikoro(&ind->gen_set.gen[idx]);
	}
}

成長をプロットしてみた。 前回とは少しプロットの仕方を変えてみた。

101_

今までの分はベスト遺伝子のスコアのみを世代毎にプロットしていたが、 今回は1世代分のソート済みの各遺伝子のスコアを全部載せてある。 塊1個分が1世代分に当たる。 赤い枠で囲った部分の左端の点がその世代の中でのベストスコアで、 右に行くほど順位が下がっていく。 これによってスコアのばらつき具合が見える。スコアのばらつきが小さいということは、 遺伝子ごとの個性が揃っていて、行動パターンが似通っているということ。 早く成長させるには、個性ができるだけばらついた状態で試行を繰り返すのが効果的であると推測した。

前回よりは劇的によくなったのだが、まだまだ世代毎のばらつきが小さく、 前世代のベストの個体によく似た個体が繰り返し生成されているような印象だった。 もう少しばらつかせる方法を追加しなければならない。 そこで、変異関数で起こす変異の種類を増やしてみた。 適当に区間を選んで、その区間は全く新しい要素を入れ込むだけ。 変異は、何もしない・一個だけ変異・区間で変異。の3種類とした。


void totsuzen(indiv_t *ind) {
	int sw = rand() % 3;//どの変異を起こすかを決めるスイッチ
	int idx;
	int start, end;

	switch (sw) {
	case 0:
		break; //何もしない。
	case 1:
		idx = rand() % GEN_LEN; //どのgenを変異させるか
		saikoro(&ind->gen_set.gen[idx]);
		break;
	case 2:
		getStartEnd(&start, &end);
		for (int i = start; i < end; i++) {
			saikoro(&ind->gen_set.gen[i]);
		}
		break;
	default:
		break;
	}
}

再度プロットを実行。 グラフを見ると、世代毎のスコアのばらつき具合が広くなった。 12世代目までスコア80%を超えることがなかったのだが、今回は5世代目には90%を超えるようになり成長は早くなった。

102_

同じ遺伝子を掛け合わせに使っても、突然変異を導入したことですぐに飽和しないようになった。 ※突然変異の確率が高すぎて、もはや突然でもなんでもなくなってしまったが。。。 そして、時たま100%掃除できる遺伝子が出てくるようになった。 試しに走らせてみた時の動画を公開。 公開用として、試行中の個体のスコアをメーターで表示するようにした。 あとは文字の色をcursesを使っていろいろ触ってみた。 <<注意>>試しに音楽も入れてみたので、ボリュームに気をつけてください。

ようやく

2018年4月18日 (水)

遺伝的アルゴリズムで育てる「お掃除ロボット」 その9 ~選定と交叉の実装~

第一世代の遺伝子群はINDIV_LEN個の遺伝子を乱数で生成する。
生成した各遺伝子(行動パターン)をロボットに書き込んで、シミュレーション環境を走行させ、
マップ中のゴミの数に対して、いくつのゴミを拾ったかをスコアとして記録する。
スコアはパーセンテージで出てくるようにした。スコアが1になればパーフェクト。

一世代分のシミュレーションが完了したら、
qsortを使って遺伝子をスコア順にソートする。毎世代につきベストな遺伝子だけをbestIndに記録する。

第一世代以降は、ソートの結果上位半分をbestIndと交叉させ、
下位半分は新たに乱数で生成することにした。

交叉のやり方はwikipediaにいろいろ載っているのだが、
二点交叉という手法を使うことにした。これをひとまとめに関数として実装した。
※遺伝子の中で適当な区間(開始~終了)を決め、その区間をペア間で入れ替えるやり方。

mainにべた書きでとりあえず試してみた。

void main(void) {
	assert(INDIV_LEN % 4 == 0);

	//ロボットの初期の向き
	point_t ini_d = { 1,0 };

	//乱数セット
	srand(time(NULL));
	
	indiv_t inds[INDIV_LEN];

	for (indNumber = 0; indNumber < INDIV_LEN; indNumber++) {
		makeIndiv(&inds[indNumber].gen_set);
	}

	//世代分だけループを回す。
	static indiv_t bestInd;
	for (generation = 0; generation < EXEC_LEN; generation++) {

		//robotの数だけ試行
		for (indNumber = 0; indNumber < INDIV_LEN; indNumber++) {
			indiv_t *ind = &inds[indNumber];
			initRobot(ind, &ini_d);
			
			//マップを書き込み
			readMap();

			//初期位置にRobotをセット
			setRobotOnMap(ind);

			draw(ind);

			do {
				execRobot(ind);
				draw(ind);
				Sleep(15);

			} while (ind->life > 0);
		}

		//選定
		//ランキング式で選定
		qsort(inds, INDIV_LEN, sizeof(inds[0]), sorter);
    	
    	//best record
	  	if (bestGen.score < inds[0].score) {
	   		bestGen = inds[0];
	  	}
	  	
		//2点交叉
		int KOUSA_NUM = 10;
		int kousa_lim = 2 * KOUSA_NUM;
		for (int i = 0; i < kousa_lim; i+=2) {
			kousa(&inds[i], &inds[i+1]);
		}
		
		//残り半分は新しく生成する。
		for (int i = kousa_lim; i < INDIV_LEN; i++) {
			makeIndiv(&inds[i].gen_set);
		}
	}

	draw_result(&bestInd);
}

ベストスコアを世代毎にプロットして、成長率の遷移を見た。

 91_

世代が上がる毎にスコアが上がると思いきや、世代間に関連性がなくすべて当てずっぽうにやっているのと変わらなかった。 遺伝子の中身を見てみると、どうやら遺伝子がbestIndの内容に収束していっているようだ。 似たもの同士でしか掛け合わせができなくなれば、遺伝的アルゴリズムのメリットはうすい。 一方、 ロボットの動きを見ていると、遺伝子一個当たりの移動距離が長くなると、 なんとなく良い行動パターンが出にくいような気がした。 そこで試しに、遺伝子一個に設定する最大移動距離MAX_MOVLENを5→3に短くしてみた。

92_

同じプロットを試してみると、やはり成績が良くなる傾向になり、 スコアが100%になる回数が多くなった。 ただしこの条件は、このマップにしか当てはまらないかもしれないので偶然かもしれない。 どちらにしても、もう少し交叉のやり方を工夫しなければならない。 突然変異の実装はまだなので、次回はそれを試すことにした。 続く。

2018年4月11日 (水)

遺伝的アルゴリズムで育てる「お掃除ロボット」 その8 ~ちょっと修正~

前回までで、とりあえずシミュレーション環境でロボットが走るようになった。
しかしいくつか構造的な問題が見つかった。。。

その6で書いていた、普段の掃除モードと、壁当たり後の回避モードの切替のところで、
search,hittedの配列をグローバルで宣言していたのだが、
新しい遺伝子を作成したときに、そこの配列が一緒に更新されていなかった。

遺伝子を作成する関数と、robotの変数を初期化する関数を別々にし、
searchとhit時の行動パターンの入れ替え(移動の際に読み取るgen_t[]の区間の切替)を、
専用の関数を作って対処した。

最初から遺伝子を作る部分と、シミュレーション開始時のロボットの初期化をする部分を
分けて作っておけばよかった。


searchとhittedのgen_t[]配列を、ロボットの状態に合わせて簡単に切り替えるために、
2つの配列についての共用体と構造体を組み合わせて新しい型を作った。

typedef union {
	gen_t gen[GEN_LEN];
	struct {
		gen_t search[SEARCH_LEN];
		gen_t hitted[HITTED_LEN];
	}div;
}genSet_t;

typedef struct {
	int movCnt;//movement counter
	int curr;//current gen index
	int bufLen;
	gen_t *buff;
	int hittedFlag;
}work_t;

typedef struct{
	//value
	int life;
	int item;
	double score;
	//position
	point_t pos;
	point_t delta;
	//parameter
	work_t work;
	genSet_t gen_set;
}indiv_t;

gen_tのポインタ*buffに、search,hittedのどちらのアドレスを入れるかでアクセスする配列が切り替わる。 ただし切替の時に一緒にbufLenを入れないといけない。 上記共用体はindiv_tにいれる。work_tはこれまでに書いたときと変更なし。


void changeMode(indiv_t *ind, mode_t mode) {
	//カウンタ等はこの構造体で一括初期化することで、bufLenなどの書き忘れを防止した。
	//buffの中身の切り替えは分岐の中で直接ポインタ代入。
	work_t search_init = { 0,0,SEARCH_LEN,NULL,0 };
	work_t hitted_init = { 0,0,HITTED_LEN,NULL,1 };

	if (mode == search)
	{
		ind->work = search_init;
		ind->work.buff = ind->gen_set.div.search;
	}
	else
	{
		ind->work = hitted_init;
		ind->work.buff = ind->gen_set.div.hitted;
	}
}


//ind->gen_setが入った状態で呼び出す。
//ここで初期化セットされるのはそれ以外のパラメータ。
void initRobot(indiv_t *ind, point_t *ini_delta){

	//最初の位置
	ind->pos.x = INI_X;
	ind->pos.y = INI_Y;

	//最初の移動方向
	ind->delta.x = ini_delta->x;
	ind->delta.y = ini_delta->y;

	ind->life = INI_LIFE;
	ind->item = 0;
	ind->score = 0;
	
	//お掃除モードで始動
	changeMode(ind,search);

	//初期の移動方向をセット。
	rotRobot(ind, forward);
}


void execRobot(indiv_t *ind){
	//alias
	work_t *w = &ind->work;
    //life count
	ind->life--;

	point_t p;
	p.x = ind->pos.x + ind->delta.x;
	p.y = ind->pos.y + ind->delta.y;

	char c = getMapVal(p);
	if (c != CH_WALL) {
        //if movable
        moveRobot(ind,ind->delta.x,ind->delta.y);

		if (c == CH_ITEM) {
			getItem(ind);
		}

		w->movCnt++;
        if(w->movCnt > w->buff[w->curr].num-1){
			//movCnt一巡後
            w->curr++;

            if(w->curr > w->bufLen-1){
				//curr一巡後
                w->curr = 0;

				//hittedMode一周したら元のモードへ
				if (ind->work.hittedFlag) {
					changeMode(ind,search);
				}
            }
            w->movCnt = 0;
			rotRobot(ind, w->buff[w->curr].dir);
        }
	}
	else {
		//if hitted
		changeMode(ind, hitted);
        //puts("hitted");
		
		rotRobot(ind, w->buff[w->curr].dir);
	}
}

こまごまとした関数。乱数でgen_tを作るところはsaikoro関数。 配列の要素一個分を作るやつなので、引数は"&g->gen[i]"となっている。 moveRobotのマップ更新のところは本当はmap.cのほうに入れたかったが、あまり厳密にやっても面倒なのでそのままにした。

void saikoro(gen_t *g) {
	g->dir = rand() % NUMOFDIR;//kind of dir = 3
	g->num = 1 + rand() % MAX_MOVLEN;//min>=1
}

void makeIndiv(genSet_t *g) {
	for (int i = 0; igen[i]);
	}
}

void getItem(indiv_t *ind) {
	ind->life += ITEM_UP_MOUNT;
	ind->item += 1;

	ind->score = ind->item / (double)puttedItem;
}

void moveRobot(indiv_t *ind,int dx,int dy) {

	map[getIndex(ind->pos)] = ' ';//元居た場所を消す
	ind->pos.x += dx;
	ind->pos.y += dy;
	map[getIndex(ind->pos)] = CH_Robot;//新しい位置に書き込む
}

まだもう少し続く。

2018年4月 4日 (水)

VisualStudioにncurses(pdcurses)を導入する。

今回はお掃除ロボットをいったん休憩して、CUIでグラフィカルな表示をするためのライブラリを導入する。

さらにgccのライブラリであるncursesを使うと、
GUIのメニューのような仕組みを導入することができるようになる。

linuxでは比較的簡単にインストールできるし、情報も多い。
ところがVisualC++への導入については日本語の情報がなかなか出てこなかったので
仕方なく自分でやってみた。

調べてみると、VC++にはPDCursesというのが使えそう。

gitのreadmeによると、VisualStudio(VS)の場合はnmakeというコマンドを使うらしい。
Microsoftのページによると、そのコマンドにMakefile的なファイルを-fオプションを使って渡すようになっている。

※Makefileというのはコンパイルの仕方を書いたスクリプトファイルみたいなもの。


nmakeが走った後はたぶん.libファイルができて、
それをプロジェクト作成のときにインクルードすれば使えるようになりそうだ。

<仕様>
使用中のVisualStudioは、Community 2017 Version 15.5.4。
パソコンのOSはwin10。

<手順>

0.gitクローンでpdcursesをダウンロード。適当な場所に解凍。

1.スタートメニューのVisualStudioのメニューからたどれる、
VS2017用 x64_x86 Cross Toolsコマンドプロンプトを起動して実行した。
※このプロンプトからだとnmakeなどが絶対パスなしで使える。

2.パス?を通す。
解凍したフォルダへの絶対パスを書き込む。

set PDCURSES_SRCDIR=c:\pdcurses

3.ビルドする。

make -f makefilename

最初にやったとき3で躓いた。ファイルが見つからないというエラー。
相対パスで指定していたのでそれは当然か。

下記実際の例
このようにMakefile.vcまでパスをすべて書いた。

>nmake -f c:\PDCurses-master\wincon\Makefile.vc

実行に成功すると、VSのツールコマンドプロンプトの居たディレクトリ下に、
デモ用のexeファイルがドバドバと現れる。そのなかに一個だけ.libファイルがある。
これが必要なファイル。

pdcurses自体のマニュアル

https://pdcurses.sourceforge.io/doc/PDCurses.md

2018年3月28日 (水)

遺伝的アルゴリズムで育てる「お掃除ロボット」 その7 ~ロボット動作の改良~

前回のソースを動かしてみた。
計算は合っているのだがなんだか思っていた動きと違っている。


詳細に調べてみると、やはり前回までのやり方ではお掃除ロボットの動きを再現できていなかった。

そもそもお掃除ロボットって後退なんかしただろうかと思う。



そこで、移動方向は後退を除く直進、左折、右折の3種類とした。

旋回方向と方角の管理方法についてももっと汎用的な方法に見直すことにした。

だいぶ前にyoutubeで1時間でテトリスを作るという動画を見たとき、 ブロックの回転に、座標変換に使う回転行列を使っているのをみた。

これは今回も使えるのではないかと思い、うろ覚えで回転行列を書いてみた。

回転行列を出すには、加法定理を使ったり、 座標系を回した絵をかいて、そこから方程式を立てて行列にしたり。 昔はいろいろやっていたのだが、このやり方を知っていれば一発で回転行列を出せる。

 

2次元マップで90度回転しかしないので、回転行列はこんな風になる。
単純に配列で要素を並べて、掛け算すればいいレベル。

Kaitengyoretsu90deg enumで移動方向の名前を定義して、その名前で受け取るようにした。
下記が完成したコード。

//移動の向き
typedef enum { left, forward, right }dir_t;

//旋回後の移動方向を計算
void rotRobot(indiv_t *ind, dir_t d) {
	const int dim[][4] = {
		{ 0,1,-1,0 }, //left
		{ 1,0,0,1 }, //forward
		{ 0,-1,1,0 }, //right
	};
	int x = dim[d][0] * ind->dx + dim[d][1] * ind->dy;
	int y = dim[d][2] * ind->dx + dim[d][3] * ind->dy;
	//printf("%2d*%2d + %2d*%2d = %2d\n", dim[d][0], ind->dx, dim[d][1], ind->dy, x);
	//printf("%2d*%2d + %2d*%2d = %2d\n", dim[d][2], ind->dx, dim[d][3], ind->dy, y);
	ind->dx = x;
	ind->dy = y;
}

再びロボット作成の関数から。

void makeRobot(indiv_t *ind, int ini_dx, int ini_dy){
	ind->pos.x = INI_X;
	ind->pos.y = INI_Y;

	//初期位置にagentをセット
	point_t p = { INI_X, INI_Y };
	map[getIndex(p)] = CH_Robot;

	ind->life = INI_LIFE;
	ind->item = 0;
	ind->scr = 0;
	
	for (int i = 0; i

gen[i] = search[i]; //printf("(%d,%d)", ind->gen[i].dir, ind->gen[i].num); } int gidx = SEARCH_LEN; for (int i = 0; i < HITTED_LEN; i++) { saikoro(&hitted[i]); ind->gen[gidx] = hitted[i]; gidx++; } //お掃除モードで始動 ind->work = searchMode; //最初の移動方向 ind->delta.x = ini_dx; ind->delta.y = ini_dy; //初期の移動方向をセット。 rotRobot(ind, forward); }



移動方向の計算 ロボットの移動方向がdx,dyで保持されていて、 これに回転行列をかけることで旋回後のdx,dyに変換されるようになっている。

genに固定値を入れて動かし、最後にロボットが辿り着く座標を見ることで、 動作検証を行った。

同じgenを入れていてもdxdyへの初期値として何を入れるかで、 その後の動きと最終地点はガラリと変わってしまう。


検証の時はそこまで考慮して作らないといけない。 初期状態は一個しかないのであればそれでもいいが、 気まぐれで変えたときに隠れていたバグが突然発症することもある。

makeRobot関数の中の、gen[]の中身を乱数で作るほうをコメントアウトし、 下記のような検証用コードを入れた。

	////---debug
	//dir_t dir[] = { right,right,right,right };
	dir_t dir[] = { right,left,right,left };
	//dir_t dir[] = { forward,forward,forward,forward };
	dir_t dir[] = { forward,left,forward,right };
	int nums[] = { 5,4,6,5 };
	for (int i = 0; i < SEARCH_LEN; i++) {
		search[i].dir = dir[i];
		search[i].num = nums[i];
	}
	hitted[0].dir = left;
	hitted[0].num = 2; //num>=1が条件
	hitted[1].dir = left;
	hitted[1].num = 2;
	for (int i = 0; i

gen[i] = search[i]; //printf("(%d,%d)", ind->gen[i].dir, ind->gen[i].num); } int ggidx = SEARCH_LEN; for (int i = 0; i < HITTED_LEN; i++) { ind->gen[ggidx] = hitted[i]; ggidx++; } ////---debug

このコードを少し書き換えて、壁に当たったときの動作も見た。 だいぶ雰囲気が出てきた。

動作時の動画

そろそろ表示方法の改良を考えても良いころ合いだろうか。
次回はncursesを使ったCUIの凝った使い方をやっていく。

続く


<余談>
数式エディタを使っいたかったのだが、もしかしたらと思いオンライン数式エディタで検索したらmathcha.ioというのが出てきた。 昔LaTeXでゴソゴソと書いていたのが嘘のように簡単に操作できる。 matrixが使いたくて、mと打ったらすぐに候補が表示され、そこから選ぶだけですごく使いやすい。

2018年3月21日 (水)

遺伝的アルゴリズムで育てる「お掃除ロボット」 その6 ~動かしてみた!!~

遺伝的アルゴリズムを使ったお掃除ロボットのシミュレーションシリーズ。 今まで作った関数を連結して、動かす段階に来た。

void main(void) {
	srand(time(NULL));
	indiv_t ind;
	
	readMap();
	makeRobot(&ind,1,0);
	draw();

	while (1) {
        puts("----------\n");
		execRobot(&ind);
		draw();
		
		Sleep(100);

		if (ind.life < 1) {
			break;
		}
	}
}

動かしたときの動画がこちら




一応正しい動きはしているのだが、もうちょっとランダムに動いてくれないと面白くない感じだ。

壁にぶつかると、移動できずにlifeだけが減っていく処理になっているのだが、 ロボットなのだからバンパーセンサぐらいは付けたい。

そこで、壁にぶつかったと判定されたら、回避行動をとる仕組みを入れることにした。



これはかなり大規模な変更になる。


というのも、移動方向はマップの上から見た状態で指定している。
もし、壁にぶつかったら左に避けろとプログラムしたとすると、 上に移動していて左に避けるなら簡単だ。

ところが右に移動していて左に避けるということは、 今の指定の仕方だと、ロボットにとっては後退になる。


つまり、ロボットローカルの移動方向で指定できるような仕組みが必要ということ。

ロボットの構造体の中で、東西南北どの方角を向いているかを管理する必要が生じる。

ロボットの移動方向は0:前、1:右、2:下、3:左の4種類。 ロボットの向いている方角を、0:北、1:東、2:南、3:西とした。 移動方向と方角を別々に管理するのでかなりややこしい。

ロボットを旋回させたあとの向きの計算方法は思いつくまでそれほどかからなかった。 ロボットの向いている方角に、移動方向を足したらよさそうだ。

場合を書き下した図

Idouhoukoku_saisyonokanngaekata_3

これをベースにして試作コードを書き下してみた。

//引数:robotの向きに対してどちらを向くかを指定。
int calcDir(int curr_dir, int temp_dir){
	int newdir;
	newdir = curr_dir + temp_dir;
    if(newdir > NDIR-1){
       return newdir - NDIR;
    }
    return newdir;
}






次にgenの構成方法を変更しに取り掛かった。

今までは遺伝子の配列genにgen_tを一様に入れただけだったが、
普段の掃除モードと、壁当たり後の回避モードの2種類をgen配列に設けることにした。

配列のある区間をインデックスで分けると、ちょっと実装を変更するだけで影響を受けそうなので、 構造体の外に配列を別々に用意した。

//ロボットのモードごとの状態を管理する構造体
typedef struct {
	int movCnt;//movement counter
	int curr;//current gen index
	int bufLen;
	gen_t *buff;
	int hittedFlag;
}work_t;

//ロボット1体分のデータを保持する構造体
typedef struct{
	//value
	int life;
	int item;
	double scr;
	//position
	point_t pos;
	point_t delta;
	//parameter
	work_t work;
	gen_t gen[GEN_LEN];
}indiv_t;

static gen_t search[SEARCH_LEN];
static gen_t hitted[HITTED_LEN];

static work_t searchMode = { 0, 0, SEARCH_LEN, search, 0 }; //お掃除モード
static work_t hittedMode = { 0, 0, HITTED_LEN, hitted, 1 }; //回避モード

動かし方を変えたので、それに合わせてexecRobotを修正。

void execRobot(indiv_t *ind){
	//alias
	work_t *w = &ind->work;
    //life count
	ind->life--;
	
	//dx,dy table (switch)
	const int dir_defx[] = {  0,1,0,-1 };
	const int dir_defy[] = { -1,0,1, 0 };

    //load dir
	int dest_dir = w->buff[w->curr].dir;

    int dest_idx = calcDir(ind->dir, dest_dir);
	ind->dir = dest_dir;
	
	int dx = dir_defx[dest_idx];
	int dy = dir_defy[dest_idx];

	char c = getMapVal(ind->x + dx, ind->y + dy);
	if (c != CH_WALL) {
        //壁でなければ
        moveRobot(ind,dx,dy);

		if (c == CH_ITEM) {
			getItem(ind);
		}

        w->movCnt++;
        if(w->movCnt > w->buff[w->curr].num-1){
            w->curr++;
            if(w->curr > GEN_LEN-1){
                w->curr = 0;
            }
            w->movCnt = 0;
        }
	}
	else {
		//壁に当たったら
		*w = hittedMode;
        puts("hitted");
	}
}

ロボットを動かしているときの変数は、すべてwork_tという構造体で管理している。

このように切り分けることによって、search(お掃除モード)とhitted(回避モード)の切り替えを、 構造体の代入の形で簡単に切り替えられるようにした。

壁に当たったと判定されると、

*w = hittedMode;

でhittedModeという定数で初期化済みの構造体が代入される。

ind->workをいちいち書くとソースの見通しが悪くなるので、 最初に短い名前で置き換えてしまうことにした。

work_t *w = &ind->work;

構造体から何度も同じメンバを取り出したり、 ネストされた構造体の深いところにあるメンバを使う時は、 別な名前で置き換えると速度的にも有利になる。



次回も続々改良編。
続く。

2018年3月14日 (水)

遺伝的アルゴリズムで育てる「お掃除ロボット」 その5 ~マップの読み込みと表示~

今日はシミュレーション環境を構築する話。
マップをロードして、シミュレーション環境を表示するところを作る。

mapをテキストファイルからロードする。

void readMap(void) {
	FILE *fp;
	fp = fopen("map.txt", "r");
	if (fp == NULL) {
		printf("file open error\n");
		exit(1);
	}

	char buff[BUFSIZE];
	int n = 0;
	while (fgets(buff, BUFSIZE, fp) != NULL) {
		memcpy(&map[n*W], buff, W);
		n++;
	}

	countItem();
	fclose(fp);
}

fgetsでbuffに1行分取り出して、memcpyでmap配列に入れる。 最初作ったときはfgetsを久しぶりに使って四苦八苦した。

BUFSIZEはもちろんマップの幅Wと同じ値にしてはいけない。
改行文字とナル文字を考慮してW+2とかにすればよいのでしょうとやってみたら、
なぜか#が次の行へ押し込まれてしまう。

よくよく調べてみると、
1行とは改行コード(\n)または読み込みバイトがファイルサイズに達するまでであると思っていたのだが、
指定文字数に達した時点でfgetsは終了。残りは次回の読み込みで取得されていた。

fgetsの引数にある文字数は、余裕をもっておくのがよい。
CUI画面に出すサイズから考えて、とりあえず256にした。

fgetsの使い方についてはこちらを参照しました

次は、mapの表示をする関数。

void draw(void) {
	for (int i = 0; i < W*H; i++) {
		printf("%c", map[i]);
		if (i%W == W - 1) {
			puts("");
		}
	}
}




CUI表示だったらこれだけで済む。

ほとんどprintfデバッグの延長程度しかない。
あとでGUIで表示したいときはここだけ書き換えればよい。
表示と内部処理をはっきり分けていると後々楽になる。


次は、いよいよ連結して動かす段階へ。
次回に続く。

2018年3月 7日 (水)

遺伝的アルゴリズムで育てる「お掃除ロボット」 その4 ~遺伝子の作成~

まずは、ロボットの構造体に遺伝子つまり行動パターンをセットして、動かすための準備をする。


遺伝子に入れる塩基一個は移動の向きと移動回数がセットになった構造体で、それぞれに乱数を使って入れる。移動の向きは上下左右の4種類。移動の回数は最低1~MAX_MOVLENとした。

とりあえずここまで作って、Ideoneで動かしてみた。
IdeoneはオンラインでC言語がコンパイルできる開発環境で、ちょっとだけ動かして試すのにとても便利。

使い方はこちらをご参照ください。

#define MAX_MOVLEN 5

	while (1) {
		int d = rand() % 4;//kind of dir = 4
		int n = 1 + rand() % MAX_MOVLEN;
		printf("%d,%d\n",d,n);
	}

出力はこんな感じになった。while(1)の無限ループなので、
途中で処理が打ち切られてRuntimeエラーとなったようだ。

Runtime error	#stdin #stdout 0s 4336KB
3,2
1,1
1,1
2,3
1,2
2,3
2,5
3,2
0,2
0,2
3,4
3,5
2,1
2,4
3,1
1,3

どこかで
srand(time(NULL));
を呼び出して、乱数のシードをセットする。

srand(time(NULL));

int d = rand();

これはPCの持っている時刻timeを乱数のシードとしてセットする関数。
この操作をしないと、何度やっても同じ値が出てきてしまう。

反対に、この操作をrandを使う度に呼び出してしまうと、
これも同じ値が出てくる現象を起こしてしまう。
時刻が変わらないうちに同じ時刻をシードとしてセットすると、
出てくる乱数も変わらないため。

久しぶりに使うとその辺の知識を忘れてしまい、いろいろ不具合を起こすことが多い。
evernoteにメモしておいて、キーワード検索できるようにしておくと楽。



ロボットを作成する関数。

void makeRobot(indiv_t *ind) {
	ind->x = INI_X;
	ind->y = INI_Y;
	ind->curr = 0;

	for(int i=0;i < GEN_LEN;i++){
		int d = rand() % 4; //kind of dir = 4
		int n = 1+rand() % (MAX_MOVLEN);
		
		ind->gen[i].dir = d;
		ind->gen[i].num = n;
	}
	//-------------------debug
	//test data
	//ind->gen[0].dir = right; //テストケース1:右端左端を2往復し、左端でちょうどlife=0となる。
	//ind->gen[0].num = 10;
	//ind->gen[1].dir = left;
	//ind->gen[1].num = 10;

	//ind->gen[0].dir = down; //上下端を2往復し、上端でちょうどlife=0となる。
	//ind->gen[0].num = 10;
	//ind->gen[1].dir = up;
	//ind->gen[1].num = 10;
	//-------------------debug

	ind->life = INI_LIFE;
	ind->movCnt = ind->gen[0].num;//カウンタ初期値セット
}

移動回数のカウントはmovCntでやることにした。
移動を実行する関数の中でインクリメントし、0になったら次のgen_tを取り出す。
gen_tの配列genのいくつ目の要素を取り出すかはcurr変数でやることにし、
こちらもインクリメントしていってgen_tの最後まで来たら0に戻す操作をすることにした。

途中に書いたテストケースは、
いきなり乱数がONになった状態でロボットの移動をテストすると、
テスト実行のたびに移動パターンが変わってしまって、効率が悪いから。
最初から全機能を連結してテストせず、機能を絞ってからやるのはとても重要。


次はロボットの移動をする関数。

void moveAgent(indiv_t *ind){
	int dx=0;
	int dy=0;
	
	switch(ind->gen[ind->curr].dir){
		case up:
			dy = -1;
			break;
		case right:
			dx = 1;
			break;
		case down:
			dy = 1;
			break;
		case left:
			dx = -1;
			break;
	}
	
	char c = getMapVal(ind->x + dx, ind->y + dy);
	if (c != CH_WALL) {
		map[getIndex(ind->x, ind->y)] = ' ';//元居た場所を消す
		ind->x += dx;
		ind->y += dy;
		map[getIndex(ind->x, ind->y)] = CH_AGENT;//新しい位置に書き込む

		if (c == CH_ITEM) {
			ind->life += ITEM_UP_MOUNT;
		}
	}
	ind->life--;
	ind->movCnt--;

	if(ind->movCnt < 1){
		ind->curr++;
		if(ind->curr > GEN_LEN-1){
			ind->curr = 0;
		}

		ind->movCnt = ind->gen[ind->curr].num;
	}
}

gen[curr]から取り出した、移動方向のデータを使ってswitchしている。
switch文はたまに使うと、結構トラブルを起こす。
breakがなくてもコンパイルエラーとならず、それらしく動いてしまうので、
文法チェッカなどがないgcc環境などで使うと、いつまでも不具合に気付かなかったりする。

if文で書いてしまってもよかったのだが、それはそれで結構見通しが悪い。
switch文は最も苦手な書き方なので、毎回どこかのHPでサンプルコードを見ながら書く。

こういうのは、配列を使って置き換えてもよい。
たいていswitchを使うより、なにか別の手段を使って書くほうが好みだ。
配列を使うなら、

//上右下左の順番にdx,dyを格納
const int ddx[] = {0,1,0,-1};
const int ddy[] = {-1,0,1,0};

//移動方向を取り出す。
int idx = ind->gen[ind->curr].dir;

//配列から、対応するdx,dyを取り出す。
dx = ddx[idx];
dy = ddy[idx];


最初に作ったときはテストをほったらかして、
とりあえずそれらしく動くまでデバッグし、
厳密な正しさをごまかしながら雰囲気で楽しんでいた。
しかしちょっと遺伝のさせ方をいじろうとしたとき、
ちっとも思ったようにいかず、そのプログラムは成長が止まってしまった。

今作っているプログラムは初代版のコードを部品に切り出してテストしながら、
基本動作ができるようになった先を見据えて作っている。
Q学習やらもっと高度な人工知能が試せるようになるとよいな。

次は表示の部分を作っていく。

次回に続く

2018年2月28日 (水)

遺伝的アルゴリズムで育てる「お掃除ロボット」 その3 ~1次元配列で2次元マップを作る~

今回は、1次元配列で2次元マップを作る方法を紹介。

2次元配列の代わりに一次元配列を使って2次元マップを作る場合、
XY座標を入れたら一次元配列のどの要素になるか、つまり配列のインデックスを返す関数があると便利だ。今後の基礎となる機能なので、確実に検証したい。

robotを動かすマップは16x16マスくらいは欲しいが、最初からその大きさでデバッグすると効率が悪い。そこで、4x4マスの極小サイズできちんと検証する。


一次元配列を2次元マップにするとどうなるのか、
インデックスを4x4マスに並べてみるといい。

ここで、(X,Y)が(1,1)と与えられたら、インデックスは5となる。

これは、”index = X+W*Y”

として表される。ただしW=4。

ちなみに、この関数はお絵かきツールのために作った関数の使いまわし。
XYがmapの範囲外だった場合は、-1を返すようになっている。

mapの外に出ようとしてもせき止められるように処理するのに使える。




お絵かきツールを最初に作ったときに、この関数を十分に確認しないまま塗りつぶし機能やらGUIやらを載せたので、常にグラグラと不安定な動作しかできなかった。

最初の土台が肝心なので、時間がかかっても確実に。




//
//int x,yを別々にメンバにすると見通しが悪いので、
//構造体にしてまとめた。
//
typedef struct {
    int x;
    int y;
}point_t;

//
//関数プロトタイプ
// XY座標をmapのインデックスに変換する関数。
//
int getIndex(point_t p);

//
//戻り値:map[]のインデックスを返す。
//        もしmapの外に出ていたら-1を返す。
//
int getIndex(point_t p) {
    if (
        (p.x < 0 || W - 1 < p.x) ||
        (p.y < 0 || H - 1 < p.y)
        ) {
        return -1;
    }
    return p.x + p.y * W;
}

検証に使ったコードはこちら。今回のロボットの課題には使わないのだが、mapの範囲から出たら-1を返す機能も併せて検証するために、-4~W+4までの範囲でループを回している。

	point_t p;
	
	for (int i = -4; i < H + 4; i++) {
		for (int j = -4; j < W + 4; j++) {
			p.x = j;
			p.y = i;
			int idx = getIndex(p);
			printf("%2d,", idx);
		}
		puts("");
	}

printfもフォーマットをうまく使えば表みたいに出力できる。検証データをこうやって一覧にすると見やすくて楽。

-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1, 0, 1, 2, 3, 4, 5, 6, 7,-1,-1,-1,-1,
-1,-1,-1,-1, 8, 9,10,11,12,13,14,15,-1,-1,-1,-1,
-1,-1,-1,-1,16,17,18,19,20,21,22,23,-1,-1,-1,-1,
-1,-1,-1,-1,24,25,26,27,28,29,30,31,-1,-1,-1,-1,
-1,-1,-1,-1,32,33,34,35,36,37,38,39,-1,-1,-1,-1,
-1,-1,-1,-1,40,41,42,43,44,45,46,47,-1,-1,-1,-1,
-1,-1,-1,-1,48,49,50,51,52,53,54,55,-1,-1,-1,-1,
-1,-1,-1,-1,56,57,58,59,60,61,62,63,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,
-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,

次は遺伝子を処理する部分を実装

次回に続く

より以前の記事一覧