Skip to content

Latest commit

 

History

History
384 lines (277 loc) · 18.4 KB

7.md

File metadata and controls

384 lines (277 loc) · 18.4 KB

七、项目:机器人

原文:Project: A Robot

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

[...] 置疑计算机能不能思考 [...] 就相当于置疑潜艇能不能游泳。

艾兹格尔·迪科斯特拉,《计算机科学的威胁》

在“项目”章节中,我会在短时间内停止向你讲述新理论,相反我们会一起完成一个项目。 学习编程理论是必要的,但阅读和理解实际的计划同样重要。

我们在本章中的项目是构建一个自动机,一个在虚拟世界中执行任务的小程序。 我们的自动机将是一个接送包裹的邮件递送机器人。

Meadowfield

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

move会使包裹被送达,并在下一个状态中反映出来。 但最初的状态仍然描述机器人在邮局并且包裹未送达的情况。

持久性数据

不会改变的数据结构称为不变的(immutable)或持久性的(persistent)。 他们的表现很像字符串和数字,因为他们就是他们自己,并保持这种状态,而不是在不同的时间包含不同的东西。

在 JavaScript 中,几乎所有的东西都可以改变,所以使用应该持久性的值需要一些限制。 有一个叫做Object.freeze的函数,它可以改变一个对象,使其忽略它的属性的写入。 如果你想要小心,你可以使用它来确保你的对象没有改变。 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的实现方式现在仍然是一个谜,但是在阅读本书的后面的章节,讨论 Web 浏览器中的 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 这样,直接计算解决方案。 相反,我们必须不断创建潜在的解决方案,直到找到有效的解决方案。

图上的可能路线是无限的。 但是当搜索AB的路线时,我们只关注从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)});
      }
    }
  }
}

探索必须按照正确的顺序完成 - 首先到达的地方必须首先探索。 我们不能到达一个地方就立即探索,因为那样意味着,从那里到达的地方也会被立即探索,以此类推,尽管可能还有其他更短的路径尚未被探索。

因此,该函数保留一个工作列表。 这是一系列应该探索的地方,以及让我们到那里的路线。 它最开始只有起始位置和空路线。

然后,通过获取列表中的下一个项目并进行探索,来执行搜索,这意味着,会查看从该地点起始的所有道路。 如果其中之一是目标,则可以返回完成的路线。 否则,如果我们以前没有看过这个地方,就会在列表中添加一个新项目。 如果我们之前看过它,因为我们首先查看了短路线,我们发现,到达那个地方的路线较长,或者与现有路线一样长,我们不需要探索它。

你可以在视觉上将它想象成一个已知路线的网,从起始位置爬出来,在各个方向上均匀生长(但不会缠绕回去)。 只要第一条线到达目标位置,其它线就会退回起点,为我们提供路线。

我们的代码无法处理工作列表中没有更多工作项的情况,因为我们知道我们的图是连通的,这意味着可以从其他所有位置访问每个位置。 我们始终能够找到两点之间的路线,并且搜索不会失败。

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,但仍然绝对不是最优的。

练习

测量机器人

很难通过让机器人解决一些场景来客观比较他们。 也许一个机器人碰巧得到了更简单的任务,或者它擅长的那种任务,而另一个没有。

编写一个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 环境中提供的大多数数据结构不太适合持久使用。 数组有sliceconcat方法,可以让我们轻松创建新的数组而不会损坏旧数组。 但是Set没有添加或删除项目并创建新集合的方法。

编写一个新的类PGroup,类似于第六章中的Group类,它存储一组值。 像Group一样,它具有adddeletehas方法。

然而,它的add方法应该返回一个新的PGroup实例,并添加给定的成员,并保持旧的不变。 与之类似,delete创建一个没有给定成员的新实例。

该类应该适用于任何类型的值,而不仅仅是字符串。 当与大量值一起使用时,它不一定非常高效。

构造函数不应该是类接口的一部分(尽管你绝对会打算在内部使用它)。 相反,有一个空的实例PGroup.empty,可用作起始值。

为什么只需要一个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