2018年，谷歌DeepMind的AlphaZero程序使用机器学习和特殊算法自学了国际象棋、将棋和围棋，以确定在定义的网格内赢得比赛的最佳动作。据外媒报道，加州理工学院（Caltech）的研究人员为自主机器人开发了一种类似的算法——一种规划和决策控制系统，可帮助自由移动的机器人在现实世界中导航时确定最佳动作。

图片来源：期刊《Science Robotics》

“我们的算法实际上是制定策略，然后探索所有可能的和重要的动作，并通过动态模拟选择最佳动作，就像玩许多涉及移动机器人的模拟游戏一样，”加州理工学院布伦控制和动力系统教授Soon-Jo Chung表示。“这里的突破性创新是，我们已经找到了一种非常有效的方法来找到典型的基于优化的方法无法找到的最佳安全动作。”

相关研究论文发表于期刊《Science Robotics》。该团队描述了这项称之为谱扩展树搜索（SETS）的技术。

许多机器人可以非常自由地向任何方向移动。例如，考虑一个旨在帮助家中老人的人形机器人。这样的机器人在完成任务时遇到障碍物或意外事件时，应该能够以多种不同的方式移动，并且基本上可以在空间内向任何方向移动。例如，该机器人的动作、障碍和挑战将与自动驾驶汽车截然不同。

那么，单一算法如何引导不同的机器人系统做出最佳决策，在周围环境中移动呢？

“你不希望设计师必须亲自设计这些动作，然后说‘这是机器人应该能够做的一组离散动作’，”加州理工学院控制与动态系统研究生、新论文的共同主要作者John Lathrop表示。“为了解决这个问题，我们想出了SETS。”

SETS使用控制理论和线性代数来寻找在物理环境中充分利用机器人平台功能的自然运动。

基本概念基于决策算法蒙特卡洛树搜索（Monte Carlo Tree Search），谷歌的AlphaZero也使用的是这种算法。在这里，蒙特卡洛本质上意味着某种随机的东西，而树搜索是指导航表示系统中数据关系的分支结构。在这样的树中，根分支到通过边连接的所谓子节点。

对于围棋等游戏，使用蒙特卡洛树搜索，可能的走法被表示为新节点，随着尝试更多可能轨迹的随机样本，树会变得越来越大。该算法会执行可能的走法以查看不同节点的最终结果，然后根据点数评估选择提供最佳结果的节点。

Lathrop解释说，问题在于，当将这种分支树结构用于连续动力系统（例如在物理世界中运行的机器人）时，树中的轨迹总数会呈指数增长。“对于某些问题，尝试模拟每一种可能性，然后找出哪种可能性最好，需要数年甚至数百年的时间，” Lathrop表示。

为了克服这个问题，SETS利用探索/利用权衡（exploration/exploitation trade-off）。“我们想尝试模拟以前没有研究过的轨迹——这就是探索，”Lathrop表示。“我们想继续寻找以前产生高回报的路径——这就是利用。通过平衡探索和利用，算法能够快速收敛到所有可能轨迹中的最佳解决方案。”

图片来源：期刊《Science Robotics》

例如，如果机器人开始计算几个可能的动作，它确定这些动作会导致它撞到墙上，那么它就没有必要调查树上该分支上的任何其他节点。

“这种探索/利用权衡和对机器人自然运动的搜索使我们的机器人能够实时思考、移动和适应新信息，”加州理工学院机械和土木工程博士后研究员、论文共同第一作者Benjamin Rivière说道。

SETS可以在大约十分之一秒内运行整个树搜索。在此期间，它可以模拟数千到数万种可能的轨迹，选择最佳轨迹，然后采取行动。循环不断进行，使机器人系统能够每秒做出许多决策。

SETS算法的一个关键特性是它可以应用于几乎任何机器人平台。这些特性和能力不必单独编程。在这篇新论文中，Chung和他的同事在三个完全不同的实验环境中展示了该算法的成功实用性。

在第一个实验中，一架四旋翼无人机能够观察四个悬停的白球，同时避开四个橙球，同时在一个充满随机发生的危险气流或热气流的机场中飞行。无人机实验是在加州理工学院的自主系统和技术中心（CAST）进行的。

在第二个实验中，该算法增强了履带式地面车辆的人类驾驶员的能力，使其能够在狭窄而蜿蜒的轨道上行驶而不会撞到侧轨。在最后的设置中，SETS帮助一对系留航天器捕获并重新定向第三个代理，该代理可以代表另一艘航天器、小行星或其他物体。