Gecode 6.5.0 新增开放变量列表支持，可在搜索中动态添加变量

机器人需要从架子上取一个包裹，放到工作台上。听起来很简单：开到架子旁，拿起包裹，开回来，放下。四个动作。除非电量不足。那样的话，机器人必须先去找充电桩，问题就变成了：这次充电应该安排在计划中的哪个位置，以及机器人应该在那里待多久。这就是一个微缩的规划问题：一个起点、若干动作、一个目标，而且没有人告诉我们计划应该有多长。

规划本身是一个独立的研究领域，最常见的第一个想法是用 PDDL 描述问题，然后交给众多能读取它的规划系统之一。对很多问题来说，这是正确的选择。约束编程也是天然契合的方案，尤其是当动作带有诸如电量会耗尽之类的限制时。常见的反对意见是，大多数约束编程求解器在搜索开始前就固定了变量集合，因此我们需要在还不知道计划有多长的情况下，先给计划长度设一个上界。

Gecode 一直允许在搜索过程中添加新的变量和约束，但在 Gecode 6.5.0 之前，并没有对此提供显式支持。Gecode 6.5.0 以 open variable list 的形式加入了这一支持。OpenIntVarList 是一个由普通 IntVar 组成的列表，当传播或搜索需要另一个位置时就会创建这些变量，同时还有一个普通的 IntVar 表示它的长度。当添加一个位置时，transition callback 可以为该步骤创建更多变量并发布约束，比如计划的下一个状态，因此 Gecode 中的任何约束都可以用在会增长的模型里。此外，这个版本还提供了一些常见约束的 open 版本，比如 regular、distinct 和 sequence，它们在整个列表上发布一次，并随着列表增长而跟随它。一个 list brancher 同时决定下一个值以及列表是否应该增长，大多数常见的变量和值选择器都可以作用于这些位置。1 所有这些都基于 Gecode 已有的 propagator 和 brancher 接口构建，只对内核做了少量补充。2 这个版本还包含了两个实验性的搜索引擎：A* 和 complete anytime beam search。本文先对机器人建模，然后是十五数码问题，最后介绍新的搜索引擎。

架子、工作台和充电桩按这个顺序排成一条直线，就像顶部图片所示。机器人从工作台出发，带一格电。每次移动消耗一格电，在充电桩每次充电动作增加一格电，电池容量为五格。拿起和放下包裹不耗电。只有一格电时，机器人能到达架子，但之后就会带着包裹困在那里。最短的可行计划是先去找充电桩。充三次电正好够用，充两次的话机器人会困在架子旁。充四次或五次电也可以，但每多充一次电都会让计划变长，所以求解器找到的第一个计划未必是最短的。在下面试一试，先直接冲向架子，看看会发生什么。

架子 工作台 充电桩 位置工作台充电1 / 5包裹在架子上动作0 每次移动消耗一格电。 重置手动控制 ← 左 右 → 拿起包裹 放下包裹 充电 执行计划 第 0 步，共 9 步 播放最优计划← 上一步 下一步 → 最优计划：右 → 充电 → 充电 → 充电 → 左 → 左 → 拿起包裹 → 右 → 放下包裹 启用 JavaScript 以控制机器人或播放计划。

我想要的是一个只描述动作及其效果的模型，让求解器自己发现这个绕路。一个直接的 CP 模型会为每个动作设一个变量，为每个动作前后的状态设变量，再用一个 transition constraint 把它们关联起来。对于一个包含四个动作的计划，会有四个动作变量和五个状态，第一个状态固定为初始情形，最后一个必须满足目标。对于我们的例子，这个模型无解。

规划编码传统上以两种方式处理未知长度。一种是先用五个动作求解，再用六个，依此类推直到九个，这样找到的第一个计划也就是最短的。另一种是选择一个上界，比如十二个动作，并允许一个未使用的后缀，代价是要对哪些位置是活跃的进行建模，并且从一开始就把直到上界的每个位置都放进模型里。open list 提供了第三种选择：保留十二这个上界，但只在搜索或传播需要时才创建位置。这样模型就会像你手算计划时那样增长：先是充电之行，然后是去架子的行程，一旦包裹送达，我们就可以停止。

完整模型在 open-robot.cpp 中。动作保存在一个 open list 中，它们之间的状态保存在另外三个 open list 中：机器人所在位置、电量以及包裹所在位置。

class Delivery : public IntMinimizeScript { OpenIntVarList actions, at, charge, packet; public: Delivery(const DeliveryOptions& opt) : IntMinimizeScript(opt), actions(*this, IntSet(ToShelf, Charge), [](Space& home, OpenIntVarList, int i) { static_cast<Delivery&>(home).step(i); opt.limit()), at(*this, IntSet(Shelf, Charger), opt.limit()+1), charge(*this, IntSet(0, capacity), opt.limit()+1), packet(*this, IntSet(OnShelf, Delivered), opt.limit()+1) { rel(*this, at.length() == actions.length() + 1); rel(*this, charge.length() == actions.length() + 1); rel(*this, packet.length() == actions.length() + 1); rel(*this, at.get(*this, 0), IRT_EQ, Workbench); rel(*this, charge.get(*this, 0), IRT_EQ, opt.charge()); rel(*this, packet.get(*this, 0), IRT_EQ, OnShelf); post_goal(*this, packet[0], actions.length(), 0);

（原文较长，此处译出前 6000 字，完整内容请点「打开原文」。）