プロジェクト: ロボット

機械が思考できるかどうかという問題は、潜水艦が泳げるかどうかという問題と同じくらい的外れだ。

「プロジェクト」の章では、新しい理論であなたを叩きつけるのを少しだけやめて、代わりに一緒にプログラムを作業します。 プログラムを学ぶには理論が必要ですが、実際のプログラムを読み、理解することも同じくらい重要です。

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

メドウフィールド

メドウフィールド村はそれほど大きくありません。 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 (from in graph) {
      graph[from].push(to);
    } else {
      graph[from] = [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メソッドを使用して、道路の文字列（"Start-End"の形式）から、開始と終了を別々の文字列として含む 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

ロボットは、あまり計画を立てていないため、荷物を配達するのに多くのターンを要します。これについてはすぐに対応します。

シミュレーションをより快適に見るには、この章のプログラミング環境で利用できる runRobotAnimation 関数を使用できます。これにより、シミュレーションが実行されますが、テキストを出力する代わりに、ロボットが村の地図を動き回る様子が表示されます。

runRobotAnimation(VillageState.random(), randomRobot);

runRobotAnimation がどのように実装されているかは、今のところ謎のままですが、JavaScriptのWebブラウザへの統合について説明する後の章を読めば、どのように動作するのか推測できるようになるでしょう。

郵便トラックのルート

ランダムロボットよりもずっと優れたことができるはずです。簡単な改善策は、現実世界の郵便配達の仕組みからヒントを得ることでしょう。村のすべての場所を通過するルートを見つければ、ロボットはそのルートを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つが目標である場合、完了したルートを返すことができます。それ以外の場合は、以前にこの場所を見たことがない場合は、新しい項目がリストに追加されます。以前に見たことがある場合は、最初に短いルートを見ているので、その場所へのより長いルート、または既存のルートとまったく同じ長さのルートを見つけたことになり、探索する必要はありません。

これは、開始位置から這い出る既知のルートのWebとして視覚化できます。これは、すべての側で均等に成長しますが、（それ自体に絡み合うことは決してありません）。最初のスレッドが目標位置に到達するとすぐに、そのスレッドが開始位置までトレースされ、ルートが提供されます。

グラフが接続されている、つまり、すべての場所が他のすべての場所から到達できることがわかっているため、コードは作業リストに作業項目がなくなった状況を処理しません。常に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 には、アイテムを追加または削除して新しいセットを作成するメソッドはありません。

値を格納する新しいクラスPGroupを作成してください。これは、第6章のGroupクラスに似ています。Groupと同様に、add、delete、およびhasメソッドを持ちます。ただし、addメソッドは、指定されたメンバーが追加された新しいPGroupインスタンスを返し、古いインスタンスは変更しないままにします。同様に、deleteは、指定されたメンバーを除いた新しいインスタンスを作成する必要があります。

このクラスは、文字列だけでなく、あらゆる型の値に対して機能する必要があります。多数の値で使用する場合に効率的である必要はありません。

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

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

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