目标导向行动规划回归逻辑混乱

Question

下图显示了 Jeff Orkin 博士的 GOAP 回归搜索原始示例。据解释，规划器在动作空间中回归搜索将角色从起始状态带到目标状态的序列。在回归搜索的每一步中，规划器都会尝试找到一个能够满足未满足的目标条件之一的效果的动作。

我的问题如下：
从图中的例子来看，回归搜索的结果是目标 -> 攻击 -> 加载武器 -> 绘制武器，而执行时则向前，变为绘制武器 -> 加载武器 -> 攻击目标。动作空间中的每个动作仅出现一次。假设行动空间由[攻击、装载武器、拔出武器、使用药水、撤退]组成，那么计划是否只代表实现目标的路线图，而不是完整、完整的行动列表？它如何处理回归搜索需要发生多个攻击动作的情况，例如前向顺序是拔出武器 -> 装载武器 -> 攻击 -> 攻击 -> 攻击？或者这种情况从一开始就有效吗？

博士。 Jeff Orkin 的回归搜索示例

我尝试查找作者的出版物，通过 ChatGPT、Gemini 和 Google Scholars 寻找任何可能的答案，但似乎我没有找到任何解决我困惑的答案。我将不胜感激帮助我消除困惑的帮助。预先感谢您。

Answer 1

有趣的问题 - 我发现 GOAP 通常要么根本不被讨论，要么只在表面层面上被讨论。

OG-GOAP 状态变量的问题

Jeff Orkin 的原始 GOAP 使用 二元状态变量。

我只能猜测原因 - 那是在二十世纪九十年代中期，是为实时射击人工智能开发的，所以性能很可能比功率更重要。如果您使用二进制变量，您可以将整个状态压缩为单个位标志整数并以超快的速度执行按位运算。

在这种设置中，正如您所注意到的，“堆叠”动作以增加效果并不简单（您可以使用可怕的黑客手段来绕过限制，例如按强度克隆动作，但是......这不是一个好的方法时间）。

您问的是回归搜索，但这并不重要 - 前向搜索也有同样的问题。

建立更好的 GOAP

但是... 不一定要这样！ GOAP 不需要使用位标志的实现。

您真正需要的是一个

数据结构，它提供键值映射和相对便宜的随机访问读/写。

这里的惰性选项显然是 HashMap，但是如果您知道所有键

预先，您也可以使用结构或数组（通过将人类友好的键映射到固定数组索引）。

它不会像按位运算那么快，而且我们必须定义一个状态算术（尽管通常就像“使用相同的键添加值”一样简单），但现在我们正在使用整个

范围的数字进行烹饪！

例如，我们现在可以将 AI 目标设置为

MONEY=250

 并给它一个动作 

Work<Pre:(), Eff:(MONEY=+50,)>

，它将正确地计算出以下计划：

Work->Work->Work->Work->Work

。

风格回归

对于回归搜索，这特别好 - 我们可以将

SUCCESS

 状态定义为“无负值状态变量”。

我们从
1. 空白状态开始，
我们
2. 添加所有初始状态变量并从中减去所有目标状态变量，
我们
3. 搜索任何其效果增加负值状态变量的动作，
我们
4. 预测新状态（通过将效果添加到当前状态，然后减去它们的先决条件）
我们在 PriorityQueue 中
5. 排队当前候选计划、其预测状态及其成本。
一旦我们达到州政府不再有负面影响的程度（或者如果您想要精确的解决方案，则全部为零），
6. 我们找到了满足目标的最佳计划！

我的各种 GOAP 发现

• 由于各种半合理的原因，我已经抵制 GOAP 的向后搜索霸权有一段时间了，但 Jeff Orkin 第一次就做对了 - 上一节中的回归搜索方案在复杂计划上大约快 100 倍到 1000 倍，并且仍然支持处理周期。

• 回归规划的计划质量也更高——如果行动空间足够宽广，前瞻性规划者通常会采取完全多余、毫无意义的步骤。回归搜索可以过滤掉那些不会导致任何不稳定状态的贪图者。

• 出于某种原因，添加最大队列大小（即，将普通 AStar 变成波束搜索）具有相当低的限制（取决于动作空间，但 50 似乎是一个最佳点，但它会随着任务的复杂性而扩展）问题）对于回归搜索来说绝对是

  奇迹。与宽/无限光束相比，我们所说的是在调谐良好时可实现 10 倍的加速。