Ex7. Search for Vacuum Problem Application of Searching Algorithms

Problem Description Apply the program to the vacuum problem in the next page. (Searching a path from an initial state to the goal state) 次のページにあるような「掃除機問題」を解くプログラムを前回までに学んだことを使って作成してください。 （初期状態（スタート）から目標状態（ゴール）までのパスを求めてください）

The Vacuum Problem The vacuum world: 2 squares 2 4 6 dirt 1 3 5 7 State（状態）: one of the eight states above.（上の8状態が全て） Operators（操作、アクション）: move left（左に移動）, move right（右に移動）, suck（吸取る）. start-state（初期状態）:Right room has dirt, left room has dirt and vacuum is in left room.（上の図の1） goal-state（目標状態）: no dirt left in any square.（上の図の7または8）

Hint for the Vacuum Problem どのようにして状態空間を作るかがポイントです！

Hint for the Vacuum Problem 前回課題の状態空間を思い出してください。 2 1 3 5 7 6 8 9 4

Hint for the Vacuum Problem 前回課題と今回課題の比較 前回課題の「都市」に相当するのが今回の「状態（state）」です。 前回課題では「都市」が全部で10個でしたが、今回の課題は「状態（state）」が全部で8個です。 前回課題ではある「都市」に隣接した「都市」は子ノード（Children）として扱われましたが、今回の課題ではある「状態」から移行可能な次の「状態」を子ノードとして扱います。つまりどの「状態」も必ず3つの子ノード（次状態）を持ちます。

Hint for the Vacuum Problem 前回課題での「都市」 今回課題での「状態」 Move Right Move Left 1 2 Suck 3 Class Node { String name; Vector children; Node pointer; } Class State { int id; boolean dirtInLeftRoom; boolean dirtInRightRoom; boolean vacuum; Vector nextStates; State pointer; }

Hint for the Vacuum Problem 今回の課題の状態空間 Move Right 1 Move Right Move Left Move Left Suck Suck Move Right Move Left Move Right Move Right Move Left 2 3 4 5 Move Right Move Left Move Left Suck Suck Suck Suck Move Right 6 7 Move Left Move Right Move Left Suck Suck

Hint for the Vacuum Problem ここまで出来れば後は簡単ですね 出来上がった状態空間をDepthFirstまたはBreathFirstで探索するだけです。

Hint for the Vacuum Problem 実装に関するヒント 前回のNodeクラスをStateクラスに変更します class State { ・・・・ //State ID int id; //左の部屋に埃はあるか boolean dirtInLeftRoom; //右の部屋に埃はあるか boolean dirtInRightRoom; //Vacuumがどちらの部屋にいるか。 //true：左の部屋 //false：右の部屋 boolean vacuum; //現状態から移行可能な三つの次状態 Vector nextStates; //解表示のためのポインタ State pointer;

Hint for the Vacuum Problem 実装に関するヒント コンストラクタにて「現状態」をセットします /** * コンストラクタ * @param id この状態のID * @param dirtInLeftRoom 左の部屋に埃があるかないか * @param dirtInRightRoom 右の部屋に埃があるかないか * @param vacuum Vacuumが右左どちらの部屋にあるか */ State(int id, boolean dirtInLeftRoom, boolean dirtInRightRoom, boolean vacuum) { this.id = id; this.dirtInLeftRoom = dirtInLeftRoom; this.dirtInRightRoom = dirtInRightRoom; this.vacuum = vacuum; nextStates = new Vector(); }

Hint for the Vacuum Problem 実装に関するヒント 「次状態」はVectorに登録します class State { final String MOVE_LEFT = "MOVE LEFT"; final String MOVE_RIGHT = "MOVE RIGHT"; final String SUCK = "SUCK"; ・・・ /** * 現状態から移行可能な全3次状態をセットするメソッド * @param left Vacuumが左に移動した場合の次状態 * @param right Vacuumが右に移動した場合の次状態 * @param suck Vacuumが現在の部屋で吸取りを行った場合の次状態 */ public void setNextState(State left, State right, State suck) { //オペレータをキーとし、次状態インスタンスを値として //Vectorに、左へ移動、右へ移動、吸取りの順番で次の状態を登録する。 nextStates.add(left); nextStates.add(right); nextStates.add(suck); }

Hint for the Vacuum Problem 実装に関するヒント 例えば、 「左の部屋に埃有り、右の部屋に埃有り、掃除機は左の部屋にいる」 という状態インスタンスを作り、更に移行可能な3つの次状態をセットするには public class VacuumProblem { State state[]; ・・・ private void makeStateSpace() { state = new State[8]; state[0] = new State(0, true, true, true); state[0].setNextState(state[0], state[1], state[4]); }

Hint for the Vacuum Problem 実装に関するヒント 注意する点として、「掃除機問題」には2つの目標状態（ゴール）があります。 「左の部屋に埃無し、右の部屋に埃無し、掃除機は左の部屋にいる」 「左の部屋に埃無し、右の部屋に埃無し、掃除機は右の部屋にいる」 public class VacuumProblem { ・・・ State goal, goal2; private void makeStateSpace() { state[6] = new State(6, false, false, true); goal = state[6]; state[7] = new State(7, false, false, false); goal2 = state[7]; }

Hint for the Vacuum Problem 実装に関するヒント また、前回の経路探索問題と違い、次状態に移行する際に使用されたオペレータ（アクション）を出力時に表示させる必要があります。例えば以下のように public class VacuumProblem { ・・・ public void printSolution(State theState) { if (theState == start) { System.out.println(theState.toString()); } else { System.out.println("↑"); System.out.println("[" + theState.getPreviousOperator() + "]"); printSolution(theState.getPointer()); } 「theState」になる為に使われたオペレータを返すメソッド

Hint for the Vacuum Problem 実装に関するヒント 前述した「getPreviousOperator」のようなメソッドを作るには、Stateクラスの中にPreviousOperatorを保存する為の変数が必要です。例えば以下のように class State { ・・・ //解表示のためのポインタ private State pointer; //この状態に移行する為に行われたアクション //解表示の為に必要 private String previousOperator; } previousOperatorに値をセットするタイミングはpointerをセットする時と同じ！

Hint for the Vacuum Problem 出力結果の一例（あくまでも一例ですよ） Breadth First Search STEP:0 OPEN:[State0] closed:[] STEP:1 OPEN:[State1, State4] closed:[State0] STEP:2 OPEN:[State4, State3] closed:[State0, State1] STEP:3 OPEN:[State3, State5] closed:[State0, State1, State4] STEP:4 OPEN:[State5, State2] closed:[State0, State1, State4, State3] STEP:5 OPEN:[State7, State2] closed:[State0, State1, State4, State3, State5]

Hint for the Vacuum Problem 出力結果の続き *** Solution *** (State7) : The left room has no dirt, the right room has no dirt and the vacuum is in the right room. ↑ [SUCK] (State5) : The left room has no dirt, the right room has dirt and the vacuum is in the right room. [MOVE RIGHT] (State4) : The left room has no dirt, the right room has dirt and the vacuum is in the left room. (State0) : The left room has dirt, the right room has dirt and the vacuum is in the left room.

Hint for the Vacuum Problem ソースコードはもちろん、最後のソリューション出力フォーマットについても特に指定は無いので、前ページのコード及び出力結果に縛られること無く自由に実装して下さい。

課題 Understand the vacuum problem Draw the state space Search a solution from a start state to the goal state using breadth-first and depth-first search algorithms. 来週の授業にも続けてください。

Hint for the Vacuum Problem 今回の課題の状態空間 Move Right 1 Move Right Move Left Move Left Suck Suck Move Right Move Left Move Right Move Right Move Left 2 3 4 5 Move Right Move Left Move Left Suck Suck Suck Suck Move Right 6 7 Move Left Move Right Move Left Suck Suck