Q学習について

Question

###前提・実現したいこと
強化学習(Q学習)でスタート地点からゴール地点までの最適な道のりを求めようとしています。
###発生している問題・エラーメッセージ
今、プログラムを50回回しても答えが出なかったら次の試行に行くようにしているのですが、次の試行に移った時にxy座標が更新されません。
また、ネットなどで調べてみると、最終的にQ学習は答えが収束すると書いてあったのですが、プログラムの試行回数を増やしても答えが収束しません。
この2つに悩んでいます。

お力を貸していただけると嬉しいです。
よろしくお願いします。

###ソースコード

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define _USE_MATH_DEFINES
#include <math.h>

typedef struct car {
	double x;	//現在位置x
	double y;	//現在位置y
	double dx;	//次の位置x
	double dy;	//次の位置y
	double max_x;	//xの最大値
	double max_y;	//yの最大値
	int s;
	int sd;
	int L = 50;
}agent;

int move(car *agent, int a, int sd);
int select_action(car *agent, int num_a, double** Qtable);
double max_Qval(car *agent, int num_a, double** Qtable);
int epsilon_greedy(car *agent, int epsilon, int num_a, double** Qtable);
int xy2s(car *agent, int a);

int main() {
	FILE *file;
	file = fopen("car.csv", "w");
	car agent;

	int num_step;	//ステップ数
	int num_trial; //試行回数
	int i, j;
	int a;
	double alpha, gamma;

	int reward; //報酬

	int num_a;	//行動
	int num_s;	//状態
	double **Qtable;
	double Qmax;
	int epsilon;

	//パラメータの設定
	alpha = 0.5;
	gamma = 0.9;
	epsilon = 10;

	num_step = 50;
	num_trial =500;

	num_a = 4;

	//エリアの数
	num_s = 25;
	int sepa = 5;

	//乱数の初期化
	srand((unsigned)time(NULL));

	//Q-table
	Qtable = new double*[num_s];
	for (i = 0; i < num_s; i++) {
		Qtable[i] = new double[num_a];
	}

	//Q-tableの初期化
	for (i = 0; i < num_s; i++) {
		for (j = 0; j < num_a; j++) {
			Qtable[i][j] = 0;
		}
	}

	//agentの初期設定
	agent.x = 25.0;
	agent.y = 25.0;
	agent.max_x = 250.0;
	agent.max_y = 250.0;

	agent.s = (int)agent.x / agent.L + (int)agent.y / agent.L * sepa;

	//学習開始
	for (i = 0; i < num_trial; i++) {
		fprintf(file, "i=%d\n", i);
		for (j = 0; j < num_step; j++) {
			//fprintf(file, "j=%d\n", j);
			flag:
			a = epsilon_greedy(&agent, epsilon, num_a, Qtable);//どの方向に動くか決める
			agent.s = (int)agent.x / agent.L + (int)agent.y / agent.L * sepa;//現在のarea
			
			agent.sd = move(&agent, a, agent.s);
			printf("%f,%f\n", agent.x, agent.y);

			//ここで障害物の設定
			//障害物があるagent.sに入るとrewardに-10が入り試行を終了する
			//Goalに入るとrewardに+10が入り試行を終了
			//その他はreward=0なのでそのまま続行

			if (agent.s == 20) {
				reward = 1000;
			}
			else if(agent.s == 15) {
				reward = -10;
			}
			else {
				reward = 0;
			}
			if (agent.dx < 0 || agent.dx > agent.max_x || agent.dy < 0 || agent.dy > agent.max_y) {
				goto flag;
			}

			Qmax = max_Qval(&agent, num_a, Qtable);
			Qtable[agent.s][a] = (1 - alpha)*Qtable[agent.s][a] + alpha * ((double)reward + gamma*Qmax);//??

			fprintf(file, "%f,%f,a=%d,s=%d,sd=%d,%d\n", agent.x, agent.y, a, agent.s, agent.sd,reward);
			
			if (reward < 0) {
				//失敗
				agent.x = 25.0;
				agent.y = 25.0;
				agent.s = (int)agent.x / agent.L + (int)agent.y / agent.L * sepa;
				break;
			}
			else if (reward > 0) {
				//成功
				agent.x = 25.0;
				agent.y = 25.0;
				agent.s = (int)agent.x / agent.L + (int)agent.y / agent.L * sepa;
				break;
			}
			else {
				//続行
				agent.x = agent.dx;
				agent.y = agent.dy;
				agent.s = agent.sd;
			}
		}
	}

	fclose(file);
	return 0;
}

int move(car *agent, int a, int sd) {

	switch (a) {
	case 0://↑
		agent->dy = agent->y + 50.0;
		agent->dx = agent->x;
		break;
	case 1://→
		agent->dx = agent->x + 50.0;
		agent->dy = agent->y;
		break;
	case 2://↓
		agent->dy = agent->y - 50.0;
		agent->dx = agent->x;
		break;
		case 3://←
		agent->dx = agent->x - 50.0;
		agent->dy = agent->y;
		break;
	}
	//sdはアクションが起こった後のagent.sを表す
	agent->sd = (int)agent->dx / agent->L + (int)agent->dy / agent->L * 5;
	return agent->sd;
}


int select_action(car *agent, int num_a, double**Qtable) {
	double max;
	int i = 0;
	int* i_max = new int[num_a];
	int num_i_max = 1;
	int a;
	i_max[0] = 0;
	max = Qtable[agent->s][0];

	for (i = 0; i < num_a; i++) {
		if (Qtable[agent->s][i] > max) {
			num_i_max = 1;
			i_max[0] = i;
		}
		else if (Qtable[agent->s][i] == max) {
			num_i_max++;
			i_max[num_i_max - 1] = i;
		}
	}

	a = i_max[rand() % num_i_max];
	return a;
}

double max_Qval(car *agent, int num_a, double** Qtable) {
	double max;
	int i = 0;

	max = Qtable[agent->s][0];//?
	for (i = 0; i < num_a; i++) {//1?
		if (Qtable[agent->s][i] > max) {
			max = Qtable[agent->s][i];
		}
	}
	return max;
}

int epsilon_greedy(car *agent, int epsilon, int num_a, double** Qtable) {
	int a;
	if (epsilon > rand() % 100) {
		a = rand() % num_a;
	}
	else {
		a = select_action(agent, num_a, Qtable);
	}
	return a;
}

###補足情報(言語/FW/ツール等のバージョンなど)

Comments

[WoodenHamlet]

typedef で agent にしてるのに car 型で定義してしかも変数名が agent なのはなぜ？

[mikamikan]

すみません。初心者なものでネットで調べたものを使いました。
少し見づらくてすみません。

typedef struct employee {

char name\\\[12\\\];
double hours;
int wage;
} EMPLOYEE;
EMPLOYEE yamada; // EMPLOYEE 型の変数 yamada を作成

[WoodenHamlet]

その例では、
① struct employee 型を typedef によって EMPLOYEE として使えるようにしている(別名)
②EMPLOYEE 型の変数 yamada を定義

Cでは本来 struct employee yamada と、構造体変数の宣言時は頭に struct を付けなければならないのを、「EMPLOYEE」=「struct employee」として簡単に書けるようにしているのです。

たいして質問者さんのコードでは、car で変数型を宣言している(C++でなら許されるんじゃないかな？)、typedef で別名に指定した agent を変数名にしているのでわかりづらいコードになってしまっているように思います。

一度 typedef を調べてみてはいかがでしょうか

Answer 1

学習については門外漢なんだけど、ざっとコード見た感じの思ったこと。

構造体の宣言に初期値って宣言できたっけ？

class AGENT {
public:
AGENT():L(50){};
    double x;    //現在位置x
    double y;    //現在位置y
    double dx;    //次の位置x
    double dy;    //次の位置y
    double max_x;    //xの最大値
    double max_y;    //yの最大値
    int s;
    int sd;
    int L;
};

new したら delete

    //Q-table
    Qtable = new double*[num_s];
    for (i = 0; i < num_s; i++) {
        Qtable[i] = new double[num_a];
    }
// ここにコード
   for (i=0; i< num_s; ++i)
    {
		delete[] Qtable[i];
    }
	delete[] Qtable;
}

他の個所でも配列を new でメモリ確保しているけど、delete してなさそうな感じがする。

これは見当違いかもしれないけど、ココは括弧で括らなくてもいい？

   //sdはアクションが起こった後のagent.sを表す
//    agent->sd = (int)agent->dx / agent->L + (int)agent->dy / agent->L * 5;
      agent->sd = ((int)agent->dx / agent->L + (int)agent->dy / agent->L )* 5;
    return agent->sd;

Comments

[mikamikan]

回答ありがとうございます。
知らなかったので調べてみたところ構造体の宣言時に初期値を宣言するのはダメっぽいですね。
また、deleteもしていませんでした。

あと、agent->sd = (int)agent->dx / agent->L + (int)agent->dy / agent->L * 5;のところですが、空間座標の分割というサイトを参考にしたxy座標を用いて現在のエリアを算出する式なので括弧でくくらなくても大丈夫です。

自分では気づけないところがたくさんありました。
ありがとうございます!

[WoodenHamlet]

reword による分岐で j ループの外に出てるけど、i ループの中でまだまわっているのは狙い通りの動きかな？

goto flag;
が、j を更新していないのは正しい？（ref. continue 文）

理想通りの動きをしたとき、どんな標準出力でどんな出力ファイルになるべきかがわかるともっと回答しやすいかな、と思いますよ。私もこのサイトは初心者なので偉そうなことは言えませんがｗ