第7章プロジェクト：ロボット

[...] 機械が考えることができるかどうかの問題は [...] 潜水艦が泳ぐことができるかどうかの問題とほぼ同じくらい的外れである。

「プロジェクト」の章では、新しい理論であなたを悩ませるのを少しの間やめ、代わりに一緒にプログラムに取り組みます。プログラミングを学ぶには理論は必要ですが、実際のプログラムを読んで理解することも同様に重要です。

この章のプロジェクトは、仮想世界でタスクを実行する小さなプログラムであるオートマトンを構築することです。私たちのオートマトンは、小包を拾ったり配達したりする郵便配達ロボットになります。

メドウフィールド

メドウフィールドの村はそれほど大きくありません。11の場所とそれらを結ぶ14の道路で構成されています。この道路の配列で記述できます。

const roads = [
  "Alice's House-Bob's House",   "Alice's House-Cabin",
  "Alice's House-Post Office",   "Bob's House-Town Hall",
  "Daria's House-Ernie's House", "Daria's House-Town Hall",
  "Ernie's House-Grete's House", "Grete's House-Farm",
  "Grete's House-Shop",          "Marketplace-Farm",
  "Marketplace-Post Office",     "Marketplace-Shop",
  "Marketplace-Town Hall",       "Shop-Town Hall"
];

村の道路網は*グラフ*を形成しています。グラフとは、点（村の場所）とそれらを結ぶ線（道路）の集合です。このグラフは、ロボットが移動する世界になります。

文字列の配列は、扱うのがあまり簡単ではありません。私たちが興味を持っているのは、特定の場所から到達できる目的地です。道路のリストを、各場所について、そこから何が到達できるかを教えてくれるデータ構造に変換しましょう。

function buildGraph(edges) {
  let graph = Object.create(null);
  function addEdge(from, to) {
    if (graph[from] == null) {
      graph[from] = [to];
    } else {
      graph[from].push(to);
    }
  }
  for (let [from, to] of edges.map(r => r.split("-"))) {
    addEdge(from, to);
    addEdge(to, from);
  }
  return graph;
}

const roadGraph = buildGraph(roads);

エッジの配列が与えられると、`buildGraph` は、各ノードに対して、接続されたノードの配列を格納するマップオブジェクトを作成します。

`split` メソッドを使用して、`"開始-終了"` の形式の道路文字列から、開始と終了を別々の文字列として含む2要素配列に変換します。

タスク

私たちのロボットは村中を移動します。さまざまな場所に小包があり、それぞれが他の場所に宛てられています。ロボットは、小包が来るとそれを拾い、目的地に到着すると配達します。

オートマトンは、各時点で次にどこに行くかを決定する必要があります。すべて小包が配達されると、タスクは完了です。

このプロセスをシミュレートするには、それを記述できる仮想世界を定義する必要があります。このモデルは、ロボットがどこにいるか、小包がどこにあるかを教えてくれます。ロボットがどこかへ移動することを決定した場合、新しい状況を反映するようにモデルを更新する必要があります。

オブジェクト指向プログラミングの観点から考えると、最初に世界のさまざまな要素のオブジェクトを定義し始めるかもしれません。ロボットのクラス、小包のクラス、場所のクラスなどです。これらは、場所にある小包の山など、現在の状態を記述するプロパティを保持でき、世界の更新時に変更できます。

これは間違っています。

少なくとも、通常はそうです。何かがオブジェクトのように聞こえるからといって、自動的にプログラム内のオブジェクトになるべきではありません。アプリケーションのすべての概念に対して反射的にクラスを作成すると、それぞれが独自の内部的で変化する状態を持つ、相互に接続されたオブジェクトのコレクションが残される傾向があります。このようなプログラムは理解するのが難しいため、壊れやすいことがよくあります。

代わりに、村の状態を、それを定義する最小限の値のセットに凝縮しましょう。ロボットの現在の場所と、未配達の小包の集合があります。それぞれに現在の場所と宛先アドレスがあります。それだけです。

ついでに、ロボットが移動したときにこの状態を*変更*するのではなく、移動後の状況の*新しい*状態を計算するようにしましょう。

class VillageState {
  constructor(place, parcels) {
    this.place = place;
    this.parcels = parcels;
  }

  move(destination) {
    if (!roadGraph[this.place].includes(destination)) {
      return this;
    } else {
      let parcels = this.parcels.map(p => {
        if (p.place != this.place) return p;
        return {place: destination, address: p.address};
      }).filter(p => p.place != p.address);
      return new VillageState(destination, parcels);
    }
  }
}

`move` メソッドは、アクションが発生する場所です。最初に現在の場所から目的地へ行く道があるかどうかを確認し、ない場合は、有効な移動ではないため古い状態を返します。

次に、ロボットの新しい場所として目的地を持つ新しい状態を作成します。ただし、新しい小包のセットも作成する必要があります。ロボットが運んでいる（ロボットの現在の場所にある）小包は、新しい場所に移動する必要があります。また、新しい場所に宛てられた小包は配達する必要があります。つまり、未配達の小包のセットから削除する必要があります。`map` の呼び出しは移動を処理し、`filter` の呼び出しは配達を行います。

小包オブジェクトは、移動されるときに変更されるのではなく、再作成されます。`move` メソッドは、新しい村の状態を提供しますが、古い状態は完全にそのまま残します。

let first = new VillageState(
  "Post Office",
  [{place: "Post Office", address: "Alice's House"}]
);
let next = first.move("Alice's House");

console.log(next.place);
// → Alice's House
console.log(next.parcels);
// → []
console.log(first.place);
// → Post Office

移動によって小包が配達され、これは次の状態に反映されます。ただし、初期状態では、ロボットが郵便局にいて、小包が未配達の状況が依然として記述されています。

永続データ

変更されないデータ構造は、*イミュータブル* または *永続的* と呼ばれます。異なる時間に異なるものを含むのではなく、あるがままの状態でいるという点で、文字列や数値とよく似た動作をします。

JavaScript では、ほとんどすべてのものが*変更*できるため、永続的であると想定される値を扱うには、ある程度の抑制が必要です。`Object.freeze` と呼ばれる関数があり、オブジェクトのプロパティへの書き込みが無視されるようにオブジェクトを変更します。注意したい場合は、これを使用してオブジェクトが変更されないようにすることができます。フリーズするにはコンピューターに追加の作業が必要であり、更新が無視されると、間違ったことをしたのと同じくらい誰かを混乱させる可能性があります。そのため、通常は、特定のオブジェクトをいじらないように指示し、覚えておいてくれることを期待することを好みます。

let object = Object.freeze({value: 5});
object.value = 10;
console.log(object.value);
// → 5

言語が明らかに変更を期待しているときに、なぜわざわざオブジェクトを変更しないようにしているのでしょうか？

プログラムを理解するのに役立つからです。これは、再び複雑さの管理に関するものです。システム内のオブジェクトが固定された安定したものである場合、それらに対する操作を個別に検討できます。特定の開始状態からアリスの家へ移動すると、常に同じ新しい状態が生成されます。オブジェクトが時間とともに変化する場合、この種の推論にまったく新しい次元の複雑さが追加されます。

この章で構築しているような小規模なシステムの場合、その少しの追加の複雑さを処理できます。しかし、どのようなシステムを構築できるかについての最も重要な制限は、どれほど理解できるかです。コードを理解しやすくするものは何でも、より野心的なシステムを構築することを可能にします。

残念ながら、永続データ構造上に構築されたシステムを理解することは容易ですが、特にプログラミング言語が役に立たない場合、それを*設計*することは少し難しい場合があります。この本では永続データ構造を使用する機会を探しますが、変更可能なデータ構造も使用します。

シミュレーション

配達ロボットは世界を見て、どちらの方向に移動したいかを決定します。そのため、ロボットは `VillageState` オブジェクトを受け取り、近くの場所の名前を返す関数であると言うことができます。

ロボットが物事を記憶できるようにして、計画を立てて実行できるようにしたいので、ロボットにメモリを渡し、新しいメモリを返すことを許可します。したがって、ロボットが返すものは、移動したい方向と、次に呼び出されたときに返されるメモリ値の両方を含むオブジェクトです。

function runRobot(state, robot, memory) {
  for (let turn = 0;; turn++) {
    if (state.parcels.length == 0) {
      console.log(`Done in ${turn} turns`);
      break;
    }
    let action = robot(state, memory);
    state = state.move(action.direction);
    memory = action.memory;
    console.log(`Moved to ${action.direction}`);
  }
}

ロボットが特定の状態を「解決」するために何をする必要があるかを考えてみてください。小包があるすべての場所を訪れてすべて小包を拾い、小包が宛てられているすべての場所を訪れて配達する必要がありますが、それは小包を拾った後でのみです。

うまくいく可能性のある最も愚かな戦略は何でしょうか？ロボットは、ทุกๆรอบにランダムな方向に歩くことができます。つまり、非常に高い確率で、最終的にすべて小包に遭遇し、その後いつか配達されるべき場所に到達します。

それがどのように見えるかを示します。

function randomPick(array) {
  let choice = Math.floor(Math.random() * array.length);
  return array[choice];
}

function randomRobot(state) {
  return {direction: randomPick(roadGraph[state.place])};
}

`Math.random()` は0から1の間の数を返しますが、常に1未満であることを忘れないでください。このような数に配列の長さを掛けて `Math.floor` を適用すると、配列のランダムなインデックスが得られます。

このロボットは何を覚える必要もないので、2番目の引数を無視し（JavaScript 関数は悪影響なく追加の引数で呼び出すことができることを忘れないでください）、返されたオブジェクトの `memory` プロパティを省略します。

この洗練されたロボットを稼働させるには、まずいくつかの小包を持つ新しい状態を作成する方法が必要です。静的メソッド（ここではコンストラクターに直接プロパティを追加することによって記述されます）は、その機能を配置するのに適した場所です。

VillageState.random = function(parcelCount = 5) {
  let parcels = [];
  for (let i = 0; i < parcelCount; i++) {
    let address = randomPick(Object.keys(roadGraph));
    let place;
    do {
      place = randomPick(Object.keys(roadGraph));
    } while (place == address);
    parcels.push({place, address});
  }
  return new VillageState("Post Office", parcels);
};

同じ場所から送られてきた小包は必要ありません。このため、`do` ループは、アドレスと同じ場所を取得すると、新しい場所を選び続けます。

仮想世界を始めましょう。

runRobot(VillageState.random(), randomRobot);
// → Moved to Marketplace
// → Moved to Town Hall
// → …
// → Done in 63 turns

ロボットは、あまりよく先を読んでいないため、小包を配達するのに多くのターンが必要です。すぐにそれを addressed し addressed ます。

シミュレーションをより分かりやすくするために、本章のプログラミング環境で利用可能なrunRobotAnimation関数を使用できます。これはシミュレーションを実行しますが、テキストを出力する代わりに、村の地図上をロボットが移動する様子を表示します。

runRobotAnimation(VillageState.random(), randomRobot);

runRobotAnimationの実装方法は今のところ謎のままですが、WebブラウザにおけるJavaScriptの統合について説明する本書の後の章を読んだ後には、その仕組みを推測できるようになるでしょう。

郵便トラックのルート

ランダムなロボットよりもはるかに良い方法があるはずです。簡単な改善策は、現実世界の郵便配達の仕組みにヒントを得ることです。村のすべての場所を通るルートを見つければ、ロボットはそのルートを2回実行することで、確実に配達を完了できます。そのようなルートの1つを以下に示します（郵便局から開始）。

const mailRoute = [
  "Alice's House", "Cabin", "Alice's House", "Bob's House",
  "Town Hall", "Daria's House", "Ernie's House",
  "Grete's House", "Shop", "Grete's House", "Farm",
  "Marketplace", "Post Office"
];

ルートに従うロボットを実装するには、ロボットのメモリを使用する必要があります。ロボットは残りのルートをメモリに保存し、毎ターン最初の要素を削除します。

function routeRobot(state, memory) {
  if (memory.length == 0) {
    memory = mailRoute;
  }
  return {direction: memory[0], memory: memory.slice(1)};
}

このロボットはすでにかなり高速です。最大で26ターン（13ステップのルートの2倍）かかりますが、通常はそれよりも少なくなります。

runRobotAnimation(VillageState.random(), routeRobot, []);

経路探索

それでも、決められたルートを盲目的にたどる行動を、本当に知的な行動と呼ぶことはできません。ロボットは、実際に行う必要のある作業に合わせて行動を調整できれば、より効率的に作業できます。

そのためには、指定された荷物、または荷物を配達する必要がある場所に向かって意図的に移動できる必要があります。目標が1回の移動以上離れている場合でも、それを行うには、何らかの経路探索機能が必要になります。

グラフを通るルートを見つける問題は、典型的な*探索問題*です。与えられた解（ルート）が有効な解であるかどうかは判断できますが、2 + 2のように解を直接計算することはできません。代わりに、有効な解が見つかるまで、潜在的な解を作成し続ける必要があります。

グラフを通る可能なルートの数は無限です。しかし、*A*から*B*へのルートを検索する場合、*A*から始まるルートのみに関心があります。また、同じ場所を2回訪れるルートにも関心はありません。これらは明らかに最も効率的なルートではありません。そのため、ルートファインダーが考慮する必要があるルートの数が削減されます。

実際、私たちが最も関心があるのは*最短*ルートです。そのため、長いルートを見る前に、短いルートを必ず確認するようにします。良いアプローチは、開始点からルートを「成長」させ、ルートが目標に到達するまで、まだ訪問していないすべての到達可能な場所を探索することです。そうすれば、潜在的に興味深いルートのみを探索し、目標への最短ルート（または複数の場合は最短ルートの1つ）を見つけることができます。

これを行う関数を以下に示します。

function findRoute(graph, from, to) {
  let work = [{at: from, route: []}];
  for (let i = 0; i < work.length; i++) {
    let {at, route} = work[i];
    for (let place of graph[at]) {
      if (place == to) return route.concat(place);
      if (!work.some(w => w.at == place)) {
        work.push({at: place, route: route.concat(place)});
      }
    }
  }
}

探索は正しい順序で行う必要があります。最初に到達した場所を最初に探索する必要があります。場所に到達したらすぐに探索することはできません。なぜなら、それは*そこから*到達した場所もすぐに探索されることを意味し、他のより短いパスがまだ探索されていない場合でも、探索が続いてしまうからです。

そのため、この関数は*作業リスト*を保持します。これは、次に探索する必要のある場所の配列と、そこに到達するためのルートです。最初は開始位置と空のルートのみです。

次に、検索はリストの次の項目を取得して探索することで動作します。つまり、その場所から伸びるすべての道路が調べられます。それらの1つが目標であれば、完成したルートを返すことができます。そうでない場合、この場所を以前に調べていない場合は、新しい項目がリストに追加されます。以前に調べていた場合は、短いルートから見ているため、その場所へのより長いルート、または既存のルートとまったく同じ長さのルートが見つかったことになり、探索する必要はありません。

これを視覚的に想像すると、既知のルートの網が開始位置から外側に広がり、均等に成長していく（ただし、決して自身に絡みつくことはありません）様子がわかります。最初の糸が目標位置に到達するとすぐに、その糸が開始位置までたどられ、ルートが得られます。

私たちのコードは、作業リストに作業項目がなくなった場合の状況を処理していません。なぜなら、私たちのグラフは*連結*されている、つまりすべての場所が他のすべての場所から到達可能であることがわかっているからです。2つの地点間のルートは常に見つけることができ、検索は失敗しません。

function goalOrientedRobot({place, parcels}, route) {
  if (route.length == 0) {
    let parcel = parcels[0];
    if (parcel.place != place) {
      route = findRoute(roadGraph, place, parcel.place);
    } else {
      route = findRoute(roadGraph, place, parcel.address);
    }
  }
  return {direction: route[0], memory: route.slice(1)};
}

このロボットは、ルート追跡ロボットと同様に、メモリ値を移動方向のリストとして使用します。そのリストが空になると、次に何をすべきかを判断する必要があります。セット内の最初の未配達の荷物を取り、その荷物がまだ集荷されていない場合は、そこへのルートを計画します。荷物が*すでに*集荷されている場合は、配達する必要があるため、ロボットは代わりに配達先住所へのルートを作成します。

どのように動作するか見てみましょう。

runRobotAnimation(VillageState.random(),
                  goalOrientedRobot, []);

このロボットは通常、約16ターンで5つの荷物の配達タスクを完了します。これはrouteRobotよりわずかに優れていますが、それでも最適とは言えません。

演習

ロボットの測定

いくつかのシナリオを解かせるだけでは、ロボットを客観的に比較することは困難です。あるロボットはたまたま簡単なタスク、または得意な種類のタスクを取得しただけかもしれませんが、他のロボットはそうではありませんでした。

2つのロボット（とその開始メモリ）を受け取る関数compareRobotsを書いてください。100個のタスクを生成し、各ロボットにこれらのタスクをそれぞれ解決させます。完了したら、各ロボットがタスクごとにかかった平均ステップ数を出力する必要があります。

公平を期すため、ロボットごとに異なるタスクを生成するのではなく、各タスクを両方のロボットに必ず与えてください。

function compareRobots(robot1, memory1, robot2, memory2) {
  // Your code here
}

compareRobots(routeRobot, [], goalOrientedRobot, []);

ロボットの効率

goalOrientedRobotよりも速く配達タスクを完了するロボットを書くことができますか？そのロボットの動作を観察すると、明らかに愚かなことは何ですか？それらをどのように改善できますか？

前の演習を解決した場合は、compareRobots関数を使用して、ロボットが改善されたかどうかを確認できます。

// Your code here

runRobotAnimation(VillageState.random(), yourRobot, memory);

永続的なグループ

標準のJavaScript環境で提供されるほとんどのデータ構造は、永続的な使用にはあまり適していません。配列には、古い配列を破損することなく新しい配列を簡単に作成できるsliceメソッドとconcatメソッドがあります。ただし、たとえばSetには、項目を追加または削除した新しいセットを作成するためのメソッドがありません。

第6章の`Group`クラスと同様に、値のセットを格納する新しいクラス`PGroup`を書いてください。 `Group`と同様に、`add`、`delete`、`has`メソッドがあります。

ただし、そのaddメソッドは、指定されたメンバーが追加された*新しい* PGroupインスタンスを返し、古いインスタンスは変更されないままにする必要があります。同様に、deleteは、指定されたメンバーのない新しいインスタンスを作成します。

クラスは、文字列だけでなく、あらゆるタイプの値で動作する必要があります。大量の値で使用する場合、効率的である必要は*ありません*。

コンストラクターは、クラスのインターフェースの一部であるべきではありません（ただし、内部的には間違いなく使用したいと思うでしょう）。代わりに、開始値として使用できる空のインスタンスPGroup.emptyがあります。

新しい空のマップを作成する関数を毎回用意するのではなく、1つのPGroup.empty値だけが必要なのはなぜですか？

class PGroup {
  // Your code here
}

let a = PGroup.empty.add("a");
let ab = a.add("b");
let b = ab.delete("a");

console.log(b.has("b"));
// → true
console.log(a.has("b"));
// → false
console.log(b.has("a"));
// → false