Проект: Робот

Оригинал: Project: A Robot

Переводчик: Фэйлун

Протокол: CC BY-NC-SA 4.0

С гордостью использую Google Translate.

[...] Сомнительно, может ли компьютер мыслить [...] Это всё равно что сомневаться, может ли подводная лодка плавать.

Айзек Азимов, «Угроза из космоса»

В разделе «Проект» я перестану рассказывать вам новые теории и вместо этого мы вместе выполним проект. Изучение теории программирования необходимо, но чтение и понимание реального плана также важно.

Наш проект в этой главе — построить автомат, небольшую программу, которая выполняет задачи в виртуальном мире. Наш автомат будет роботом-почтальоном, который доставляет посылки.

Meadowfield

Деревня Медоуфилд не очень большая. Она состоит из 11 мест и 14 дорог. Её можно описать с помощью массива roads:

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, чтобы преобразовать строки вида "Start-End" в двухэлементные массивы, содержащие начальную и конечную точки как отдельные строки.

Задача

Наш робот будет перемещаться вокруг деревни. В разных местах есть посылки, которые нужно доставить в другие места. Робот забирает посылку при получении и доставляет её, когда прибывает в пункт назначения.

Автомат должен решить, куда идти дальше, находясь в каждом месте. Когда все посылки будут доставлены, задача будет выполнена.

Чтобы смоделировать этот процесс, мы должны определить виртуальный мир, который описывает его. Эта модель сообщает нам, где находится робот и где находятся посылки. Когда робот решает переместиться в другое место, нам нужно обновить модель, чтобы отразить новую ситуацию.

Если вы думаете о объектно-ориентированном программировании, ваш первый порыв может быть начать определять объекты для всего в мире. Робот, посылка, возможно, даже место. Затем они могут содержать атрибуты, описывающие их текущее состояние, например, кучу посылок в каком-то месте, и мы можем изменить эти атрибуты при обновлении мира.

Это неправильно.

По крайней мере, обычно это так. То, что звучит как объект, не обязательно должно быть объектом в вашей программе. Отражение каждого понятия в приложении в виде класса часто приводит к серии взаимосвязанных объектов, каждый со своим собственным внутренним состоянием изменений. Такие программы обычно трудно понять и легко сломать.

Вместо этого давайте сведём состояние деревни к минимальному набору значений, которое определяет его. Текущее местоположение робота и набор посылок, каждая из которых имеет текущее местоположение и целевой адрес. Этого достаточно.

Когда мы достигаем нового места, давайте сделаем так, чтобы перемещение робота не изменяло это состояние, а вместо этого вычисляло новое состояние после перемещения.

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, мы предоставляем случайный индекс массива.

Поскольку этому роботу не нужно ничего запоминать, он игнорирует свой второй параметр (помните, что можно вызывать функции 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 в веб-браузерах вы сможете догадаться, как она работает.

Маршрутизация почты

Мы должны быть в состоянии сделать лучше, чем случайный робот. Одно простое улучшение состоит в том, чтобы получить подсказки из реальных почтовых маршрутов. Если мы найдём маршрут, который проходит через все точки деревни, робот сможет пройти этот маршрут дважды, и тогда он гарантированно завершит работу. Вот такой маршрут (начиная с почтового отделения).

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 шагов), но обычно требуется меньше.

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

Поиск пути

Однако я не буду слепо следовать фиксированному интеллектуальному поведению поиска пути. Если робот адаптирует своё поведение к работе, которую необходимо выполнить, он может работать более эффективно.

Для этого он должен иметь возможность целенаправленно двигаться к заданной посылке или к месту, куда посылка должна быть доставлена. Тем не менее, даже если цель находится дальше, чем на расстоянии одного шага от нас, всё равно потребуется какая-то функция поиска пути.

Проблема поиска пути на графике является типичной проблемой поиска. Мы можем определить, является ли данное решение (маршрут) эффективным решением, но мы не можем вычислить решение напрямую, как 2 + 2. Вместо этого мы должны продолжать создавать потенциальные решения, пока не найдём эффективное решение.

Возможные маршруты на графике бесконечны. Однако, когда мы ищем маршрут от A до B, нас интересует только маршрут, начинающийся с A. Нас также не волнует посещение одного и того же места дважды — это определённо не самый эффективный маршрут. Таким образом, мы можем уменьшить количество маршрутов, которые должен рассмотреть искатель.

Фактически, нас больше всего интересует кратчайший маршрут. Поэтому мы должны убедиться, что рассмотрим более короткие маршруты перед более длинными. Хороший способ сделать это — начать с начала и исследовать все доступные места, которые ещё не были достигнуты, пока маршрут не достигнет цели. Таким образом мы исследуем только интересные потенциальные маршруты и находим кратчайший путь (или один из кратчайших путей) к цели.

Это реализация:

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)});
      }
    }
  }
}

Исследование должно быть выполнено в правильном порядке — сначала следует исследовать места, которые были достигнуты первыми. Мы не можем достичь места и сразу же исследовать его, потому что это означало бы, что места, достижимые оттуда, также будут исследованы немедленно, хотя могут быть более короткие пути, которые ещё предстоит исследовать.

Поэтому эта функция сохраняет список задач. Это список мест, которые необходимо исследовать, и маршрут туда. Сначала он содержит только начальное местоположение и пустой маршрут.

Затем, исследуя следующий элемент списка и выполняя поиск, мы просматриваем все пути от этого места. Если один из них является целью, мы можем вернуть завершённый маршрут. В противном случае, если мы раньше не видели это место, мы добавим новый элемент в список. Если мы видели его раньше, поскольку мы сначала исследуем более короткие пути, мы обнаружим, что путь к этому месту длиннее или такой же длины, как существующий путь, поэтому нам не нужно исследовать его.

Вы можете представить это визуально как сеть известного маршрута, выходящую наружу из начальной позиции и равномерно растущую во всех направлениях (но не оборачивающуюся назад), чтобы предоставить нам маршрут. Как только первая линия достигнет целевой позиции, остальные линии вернутся к исходной точке, предоставив нам маршрут.

Наш код не обрабатывает случай, когда в списке задач больше нет элементов, потому что мы знаем, что наш график связан, что означает, что мы можем добраться до каждого места из любого другого места. Мы всегда сможем найти маршрут между двумя точками, и поиск никогда не потерпит неудачу. Этот фрагмент представляет собой программный код на языке JavaScript. В нём описывается алгоритм работы робота, который должен доставлять посылки. Робот выбирает маршрут с помощью функции findRoute, которая принимает в качестве аргументов граф дорог (roadGraph), место отправления (place) и место назначения (parcel.place или parcel.address).

Робот начинает работу с выбора не доставленной посылки из массива parcels. Если посылка уже была доставлена по текущему адресу (parcel.place == place), то робот строит маршрут к месту доставки посылки (findRoute(roadGraph, place, parcel.address)). Иначе строится маршрут от текущего местоположения к местоположению посылки (findRoute(roadGraph, place, parcel.place)).

В результате работы алгоритма возвращается направление маршрута (direction) и список остальных точек маршрута (memory).

Далее описывается работа робота в виде анимации. Для запуска анимации используется функция runRobotAnimation, которой передаются начальное состояние деревни (VillageState.random()), сам робот (goalOrientedRobot) и пустой массив ([]).

Также приводится сравнение двух роботов: routeRobot и goalOrientedRobot. Первый робот выполняет задачу доставки 5 посылок примерно за 16 раундов. Второй робот справляется с задачей немного хуже.

Затем предлагается реализовать функцию compareRobots, которая будет сравнивать двух роботов. Функция должна принимать двух роботов и их начальные состояния памяти, а затем выполнять 100 задач для каждого робота и выводить среднее количество шагов, затраченных на выполнение каждой задачи.

После этого предлагается улучшить робота goalOrientedRobot, чтобы он выполнял задачу быстрее. Также предлагается проанализировать поведение робота и предложить способы его улучшения.

Наконец, предлагается создать новый класс PGroup, который будет похож на класс Group из шестой главы, но будет иметь методы add, delete и has. Класс должен работать с любыми типами значений и создавать новые экземпляры при добавлении или удалении элементов.